2020-11-27 운영체제 기초(12) 메모리 할당

Allocation of Physical Memory

  • 메모리는 OS상주영역과 사용자 프로세스 영역으로 나누어진다.
    • OS상주 영역 : 낮은 주소를 사용
    • 사용자 프로세스 영역 : 높은 주소 영역 사용
  • 사용자 프로세스의 영역할당
    • 연속할당(Contiguous allocation) : 각각의 프로세스가 메모리의 연속적인 공간에 적재
      • fixed partition allocation
      • variable partition allocation
    • 비연속할당(Noncontiguout allocation) : 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라간다.
      • paing
      • segmentation
      • paged segmentation

연속할당

  • 연속할당도 고정분할 방식과 가변분할 방식으로 나눈다.
  • 낭비되는 조각을 외부조각과 내부조각으로 부른다.
    • 외부조각(external fragmentation) : 프로그램 크기보다 분할의 크기가 작은 경우, 아무 프로그램에도 배정되지 않은 빈공간인데도 프로그램이 올라갈 수 없는 작은 분할
    • 내부조각(Internal fragmentation) : 프로그램의 크기보다 분할의 크기가 큰 경우, 하나의 분할 내부에서 사용되지 않는 메모리조각, 특정 프로그램이 배정되었지만 사용되지 않은 공간
  • 고정분할(Fixed Partition)방식
    • 물리적 메모리를 몇개의 영구적 분할(partition)으로 나눈다.
    • 분할의 크기가 모두 동일한 방식과 서로 다른 방식이 존재
    • 분할당 하나의 프로그램 적재
    • 융통성이 없다 => 동시에 메모리에 로드되는 프로그램수가 고정, 최대 수행 가능 프로그램 제한
    • 내부조각, 외부조각 둘 다 발생
  • 가변분할 방식
    • 프로그램의 크기를 고려해서 할당
    • 분할의 크기, 갯수가 동적으로 변한다.
    • 기술적 관리 필요
    • external fragmentation발생

가변분할 방식을 사용하게 되면 프로그램 실행과 종료 사이에 Hole이 여러개 생긴다. 생긴 hole중에 어떤 hole에 프로세스를 할당할지 Dynamic Storage-Allocation Problem을 통해 찾는다.

  • First-fit : size가 n이상인 것 중에 최초로 찾아지는 hole에 할당
  • best-fit : size가 n이상인 가장 작은 hole을 찾아서 할당
    • hole들의 리스트가 크기순으로 정렬되지 않을 경우 모든 hole의 리스트를 탐색
    • 많은 수의 아주 작은 hole들이 생성
  • worst-fit : 가장 큰 hole에 할당, 모든 리스트를 탐색, 상대적으로 아주 큰 hole들이 생성
  • first-fit과 best-fit이 worst-fit보다 속도와 공간 측면에서 효과적이다.

  • hole들을 모아서 compaction을 할수도 있다.

  • compaction : 외부조각 문제를 해결하는 방법
    • 사용중인 메모리 영역을 한군데로 몰고, hole들을 다른 한곳으로 몰아서 큰 block을 만든다.
    • 매우 비용이 많이 든다 => 바인딩을 다 관리해야되서
    • 최소한의 메모리 이동으로 compaction을 하는 방법 => 매우 복잡한 문제
    • compaction은 프로세스의 주소가 실행 시간에 동적으로 재배치 가능한 경우에만 수행될 수 있다.

실제 컴퓨터 시스템은 불연속할당 방식을 사용한다

불연속할당

  • paging : 프로세스의 가상 메모리를 동일한 사이즈의 페이지로 나눈다
    • 가상메모리의 내용이 페이지 단위로 불연속하게 저장된다
    • 일부는 backing store에 일부는 물리메모리에 저장
  • Basic method : 물리 메모리를 동일한 크기의 frame으로 나눈다.
    • 논리 주소를 동일 크기의 page로 나눈다(frame과 같은 크기)
    • 모든 가용 frame 들을 관리
    • 페이지 테이블을 사용하여 논리 주소를 물리주소로 변환
    • External Fragmentation 발생안하고, internal fragmentation 발생가능

Paging

  • 논리적인 메모리를 동일한 크기의 page로 자르고 각 페이지를 물리메모리에 비어있는 위치가 있으면 올린다.
  • 페이지 테이블을 사용. 각각의 논리적인 페이지들이 메모리 어디에 올라가있는지 확인. 논리적인 페이지의 갯수만큼 페이지 테이블이 생성
  • 물리메모리에서 페이지가 들어가는 공간을 페이지프레임이라고 부르고, 프레임은 페이지와 동일한 크기
  • Page Table : main memory에 상주한다.
    • page-table base register(PTBR)가 page table을 가리킨다
    • page-table length register(PTLR)이 테이블의 크기를 보관
    • 모든 메모리 접근 연산에는 2번의 메모리 접근이 필요 => 페이지테이블 1번, 실제 data 1번
    • 속도향상을 위해 associative register 혹은 translation look-aside buffer(TLB)라 불리는 고속의 캐시를 사용한다.
  • TLB는 페이지테이블에서 자주 접근되는 페이지들을 캐싱한다. 일부만 담고 있다.
  • 메모리에 접근할때 우선 TLB부터 확인. TLB에 있으면 TLB를 통해 접근하고, TLB에 없으면 페이지 테이블을 통해 접근한다. 이때 TLB 전체를 탐색한다. 시간이 오래걸리기때문에 TLB는 병렬 탐색이 가능한 associative register를 함께 사용한다.
  • 페이지테이블은 각각의 프로세스마다 존재
  • Associative Register : TLB에서 병렬 탐색을 가능하게 한다.
  • Address translation : 페이지 테이블의 일부가 associative register에 보관되있다.
    • 만약 page #이 associative register에 보관되있으면 곧바로 frame #을 얻는다 그렇지 않으면 메인메모리에 있는 페이지 테이블로 부터 frame #을 얻는다
    • TLB는 context switch 때 flush(오래된 엔트리를 비운다)
Effective Access Time
  • associative register에서 찾는 시간e, 메인메모리에 접근하는 시간 , tlb로 주소변환이 되는 비율 a
  • 메모리접근 시간 : (1+e)a + (2+e)(1-a) => 2+e-a

Two-Level Page table

  • 2단계 페이지테이블을 사용하면 속도가 줄어들지 않고, 공간이 줄어든다.
  • 현대 컴퓨터는 address space가 크다. 32-bit address사용시 2^32 => 4gb 주소공간이 필요
    • 32비트 주소를 사용하면 각 프로그램은 최대 4GB만큼 가상메모리를 쓸 수 있다.
    • page size가 4kb일시 1M개의 페이지 테이블 엔트리가 필요
    • 각 페이지 엔트리가 4byte라면 프로세스당 4mb의 페이지 테이블이 필요하다. 하지만 4g의 주소공간 중 일부만 쓰기 때문에 페이지 테이블 공간이 심하게 낭비된다.
  • 페이지 테이블 자체를 페이지로 구성하고, 사용되지 않는 주소공간에 대한 outer page table의 엔트리 값을 null로 처리한다.
    • 논리주소에서 20bit는 page number, 12bit는 page offset으로 구성
    • 페이지 테이블 자체가 페이지로 구성되기 때문에 pagenumber는 10bit의 page number와 10bit의 page offset으로 구성된다.
    • p1은 outer table의 index이고, p2는 outter page table에서의 변위.
Written on November 27, 2020