메모리 관리

논리 주소 vs 물리 주소

논리 주소

• 프로세스마다 독립적으로 가지는 주소 공간
• 각 프로세스마다 0번지 부터 시작
• CPU가 보는 주소는 logical address임

물리 주소

• 메모리에 실제 올라가는 위치

주소 바인딩

• symbolic address -> loical address -> physical address
  • symbolic address: 변수로 메모리 주소를 표현하는 것
• logical address에서 physical address로 언제 변환하는 지에 따라서 주소 바인딩 방법이 나뉜다.

compile time binding

• 컴파일시 물리적 주소가 정해진다.
• 물리적 주소를 변경하고 싶다면 재컴파일 해야한다.
• 컴파일러는 절대코드(absolute code)를 생성한다.

load time binding

• 실행시 물리적 주소가 정해진다.
• loader의 책임하에 물리적 메모리 주소가 부여된다.
• 컴파일러가 재배치 가능 코드(relocatable code)를 생성한 경우 가능하다.

run time binding

• 실행시 물리적 주소가 정해진다.
• 실행 후 물리적 주소 위치가 변경될 수 있다.
• CPU가 주소를 참조할 때마다 binding을 점검해야한다. (address mapping table)
• 이를 위해 하드웨어적인 지원이 필요하다. (base and limit registers, MMU)

Memory Management Unit(MMU)

• logical address를 physical address로 맵핑해주는 hardware device

MMU scheme

• 사용자 프로세스가 CPU에서 수행되며 생성해내는 모든 주소값에 대해 limit register 값 이하인지 확인하고 base register의 값을 더한다.
  • base register(relocation register): 접근할 수 있는 물리적 메모리 주소의 최소값
  • limit register: 논리적 주소 범위
  • limit register 값을 확인하는 이유는 프로세스가 본인의 최대 메모리 영역 외 다른 메모리 영역에 접근하고자하는 시도를 막기 위해서다.
    

메모리 관련 용어

Dynamic Loading

• 프로세스 전체를 메모리에 올리는 것이 아닌 해당 루틴이 불려질 때 메모리에 load 하는 것
• memory utilization(메모리 이용률) 향상
• 가끔 사용되는 큰 용량의 코드에 유용
• 진정한 의미의 Dynamic Loading은 운영체제의 지원 없이 프로그램 자체에서 구현된 것을 의미한다.

Overlay

• Dynamic Loading과 같이 메모리 프로세스 중 실제 필요한 일부 정보만 올린 것을 의미한다.
• 역사적 의미로 이전에 메모리크기가 매우 작을 때 메모리 보다 큰 사이즈의 프로세스를 실행시키기 위해 프로그래머가 프로그램에 코드로 직접 구현한 것을 의미한다.

Swapping

• 프로세스를 일시적으로 메모리에서 swaping area로 쫓아내는 것을 의미한다.
• 진정한 의미의 swapping은 해당 프로세스 메모리 전체를 쫓아내는 것을 말한다.
• swap out할 스케줄러 선택은 중기 스케줄러에 의해 수행된다.
  • priority based CPU scheduling: 우선순위가 낮은 프로세스의 메모리를 swap out
• compile time 또는 load time binding은 swap in 시에 원래 메모리 위치로 돌려놔야한다.
• run time binding은 아무 곳에나 swap in 할 수 있다.
• swap time은 대부분 transfer time 으로 swap되는 양에 비례한다.

Dynamic Linking

• Static Linking과 대비되는 개념
  • 라이브러리가 컴파일 시 실행파일에 포함되는 것을 의미
  • 실행 파일의 크기가 커지고 동일한 라이브러리가 여러 프로세스에서 사용되는 경우 프로세스마다 메모리에 올려지기 때문에 메모리 낭비가 심하다.
• Dynamic Linking
  • 라이브러리 코드가 실행시에 link 됨
  • 라이브러리 호출 부분에 라이브러리 루틴의 위치를 찾기 위한 stub이라는 코드를 둠
  • 라이브러리가 이미 메모리에 있으면 그 루틴의 주소로 가고 없으면 디스크에서 읽어옴
  • 운영체제의 도움이 필요

메모리 할당

contiguous allocation 연속 할당

• 각각의 프로세스가 메모리의 연속적인 공간에 적재 (프로세스 전체가 분할되지 않고 연속적으로 메모리에 적재)
• 주소 변환시 메모리 주소가 limit 크기를 넘지 않는지 확인하고 넘지 않으면 물리 메모리 시작 주소를 가상 메모리 주소에 더하는 방식으로 물리 주소를 알 수 있다. (MMU scheme 방식과 동일)

Fixed partition allocation 고정 분할 할당

• 메모리를 고정된 크기만큼 분할한 뒤 분할 당 하나의 프로세스를 할당하는 방법
• 프로세스의 크기보다 큰 공간에 할당되는 경우 내부 단편화 현상이 발생하고 프로세스들을 할당한 뒤 크기가 작아 사용되지 못한 공간들이 남는 외부 단편화도 발생한다.
• 메모리에 동시에 load되는 프로그램 수가 고정되고 최대 수행 가능 프로그램 크기도 제한된다.

Variable partition allocation 가변 분할 할당

• 프로그램 크기를 고려해서 할당하는 방법
• 메모리 분할의 크기와 개수가 동적으로 변함
• 할당되 프로세스가 종료돼 메모리가 비거나 하면서 외부 단편화가 발생한다.

Hole

• 가용 메모리 공간을 말한다.
• 메모리 할당을 하다보면 hole 생기고 hole은 여러곳에 흩어져있게 된다.
• 프로세스가 도착하면 수용 가능한 hole에 할당한다.
• hole 할당 방법
  • first fit: 할당 가능한 hole 중 탐색 과정에서 발견한 가장 첫번째 hole에 할당하는 방법
  • best fit: 모든 hole을 탐색해 가장 잘 맞는 hole에 할당하는 방법, 탐색 overhead가 발생하고 작은 hole들이 많이 발생할 수 있다.
  • worst fit: 모든 hole을 탐색해 가장 큰 hole에 할당하는 방법, 탐색 overhead가 발생하고 비교적 큰 hole들이 생긴다. 가장 성능에 안좋다.

Compaction 압축

• 외부 단편화 현상을 해결하는 방법
• 사용 중인 메모리 영역을 한군데로 몰하 hole을 합쳐 큰 hole로 만드는 것
• 비용이 큼
• 최소한의 메모리 이동으로 compaction하는 것을 매우 복잡함
• runtime binding의 경우에만 가능

불연속적 할당

• 각각의 프로세스가 메모리에 연속적으로 적재되지 않고 분할되어 적재되는 방식

Paging

• 고정 분할
• 프로세스의 가상 메모리를 동일한 사이즈의 page 단위로 나눔
• 물리 메모리도 동일한 사이즈의 frame으로 나눔
• 가상 메모리의 내용이 page 단위로 비연속적으로 저장됨
• 일부는 backing storage(swap area & file system)에 저장하고 일부는 physical memory에 저장한다.
• 물리 메모리를 page와 동일한 크기인 frame으로 나누는 고정 분할 방식으로 외부 단편화는 발생하지 않지만 내부 단편화는 발생할 수 있다.
• 가상 메모리와 물리 메모리의 맵핑 정보는 page table(배열, 인덱스로 접근)에서 관리된다.
  • 논리 주소는 페이지 번호와 해당 페이지 내부에 위치를 알 수 있는 offset으로 구성된다. 물리 주소가 할당되어도 해당 프레임 내 offset은 논리 주소의 offset과 동일하다.
  • page table은 main memory에 상주한다.
  • Page-table base register(PTBR)은 page table의 시작 위치를 가리킨다.
  • Page-table length register(PTLR)은 테이블 크기를 저장한다.
  • Page-table은 프로세스별로 존재한다.
  • Page-table은 물리 주소값과 함께 valid-invalid bit가 존재하는데 이 값은 해당 주소에 데이터가 존재하는지 아닌지를 나타낸다.
  • Page-table에는 Protection bit도 존재하는데 메모리에 저장된 데이터에 대한 action을 제한한다(read/write/read-only)
  • 모든 주소 연산에는 2번의 메모리 접근이 필요하다. (페이지 테이블 접근 후 물리 주소 접근)
  • 속도 향상을 위해 translation look-aside buffer(TLB) 캐시를 사용한다.
    • TLB는 페이지 테이블과 달리 주소 일부만 가지고 있기 때문에 인덱싱 자료구조가 아닌 key-value 형태(가상주소-물리주소)로 되어있다.
    • TLB는 조회시 전체 조회를 수행해야하며 오버해드가 큰작업이기 때문에 associative register를 이용해 병렬로 조회할 수 있다.
    • TLB 조회 후 캐시 미스가 나면 페이지 테이블로 다시 조회해야한다
    • TLB는 context switch때 모두 flush(remove old entries) 된다.
• Two-Level Page Table
  • 페이지 테이블이 차지하는 메모리 크기가 굉장히 큼
    • 32bit 환경에서 주소 공간은 2^32(4GB) 메모리
      • page size 가 4K면 1M개의 page table entry(인덱스)가 필요
      • 각 page entry(인덱스)가 4B시 프로세스당 4M의 page table 용량이 필요하다.
      • 그러나 대부분 프로그램은 4G의 주소 공간 중 극히 일부만 사용하기 때문에 Page table이 차지하는 메모리 낭비가 심해진다.
  • 페이지 테이블은 그 크기에 비해 실제로 사용되는 공간은 매우 적기 때문에 현재 유효하게 사용되는 메모리 공간만 페이지 테이블로 관리하기 위해 Two--level Page table을 사용한다.
    • 실제 사용되는 메모리의 page table만 생성되고 그 page table의 entry 주소 정보를 갖는 outer-page table이 생성된다.
    • 주소 변환시 outer-page-table => page of page table 순으로 접근한다.
    • 공간 낭비는 줄일 수 있지만 메모리를 두번 접근해야하기 때문에 시간은 더 소요된다.
    • logical address는 Outer-page-table entr와 page-table entry 그리고 offset으로 구성된다.
• Multi-level Page Table
  • two-level page table 보다 단계가 더 많은 페이지 테이블을 사용한다.
  • 메모리 접근 시간이 더 늘어나는데 TLB를 이용해 접근 시간을 줄일 수 있다.
  • TLB 접근 시간과 히트/미스 비율을 이용해 페이지 테이블 단계를 정할 수 있다.
• Invertes Page Table
  • 논리 주소를 entry로 물리 주소를 알아내는 것이 아닌 물리 주소를 entry로 논리 주소를 저장한다.
  • 현재 사용중인 메모리들로만 page-table이 구성되고 하나의 page-table로 모든 프로세스 주소 변환을 할 수 있다.
  • 주소 변환시 논리 주소를 담고 있는 entry를 알기 위해 모두 조회해야하는 단점이 있다. (associative register를 이용해 병렬 조회가 가능하면 성능을 개선할 수 있음)
  • 논리 주소만 저장했을 때 여러 프로세스에서 같은 논리 주소를 사용할 수 있기 때문에 이를 식별하기 위해 PID를 같이 사용한다.
• Shared Page
  • 여러 프로세스에서 공유하는 Shared Code는 read-only로 하여 프로세스 간에 하나의 code만 메모리에 올린다.
  • Shared code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야한다.

Segmentation

• 가변 분할
• 프로그램은 의미 단위인 여러 개의 segment로 구성한다.
  • 작게는 함수 하나가
  • 크게는 프로그램 전체를
  • 일반적으로는 code, data, stack 부분이 하나씩 세그먼트로 정의된다.
• Logical address는 segment 번호와 offset으로 구성된다.
• Segment 테이블은 Page 테이블과 다르게 해당 Segment의 크기 정보(limit)를 함께 갖는다.
  • Logical address의 offset이 limit보다 크면 접근이 불가능하다.
• Segment-table base register(STBR): segment 테이블의 시작위치
• Segment-table length register(STLR): setment 길이(entry 수)
• 외부 단편화과 발생할 수 있다.
• 의미단위이기 떄문에 공유나 보안에 있어 paging 보다 효과적
• Segment-table이 Page-table보다 메모리 공간 측면에서 효율적
• 현재는 Segmentation 기법 단독으로 사용하는 경우는 거의 없다.
  

  

Segmentation with Paging

• 하나의 segment가 여러개의 page로 구성되는 방식(segment하나는 page 배수의 크기를 갖게됨)
• 따라서 페이지 테이블은 각 segment별로 존재함
• 메모리는 page 단위로 올라가고 의미 단위 관리가 필요한 것들만 segment 기준으로 관리한다.
• Segment 기법의 단점을 보완하고 장점을 취한 방식