1일 1커밋 !

Memory Management

메모리 관리의 목표는 크게 세 가지이다.

  1. 쉽게 사용할 수 있도록 추상화 제공
  2. 메모리를 효율적으로 사용할 수 있도록 도움
  3. 메모리 프로텍션 제공

Batch programming 에서는 하나의 프로세스가 메모리 전체를 사용했지만 Multiprogramming 으로 바뀌면서 여러 프로세스가 메모리에 동시에 올라가니 관리가 필요해졌다.

메모리관리란 여러 프로세스 지원하는데, 실제 메모리는 1기가인데 2기가짜리 프로그램을 어떻게 돌릴 것인가, 프로세스 간 독립(프로텍션), 메모리 공유를 어떻게 할 것인지 뜻한다.

이를 가능케 하고자 Virtual Memory가 등장하였다. 이는 크게 두 가지 기능을 제공한다.

Virtual Memory

  1. Virtual address 와 Physical address의 매핑
  2. 무한대의 Virtual address를 지원

메모리 주소는 명령어를 실행할 때 사용된다. 메모리의 몇 번지를 읽어 CPU 레지스터에 가져오는 load 명령어가 존재한다. 이 떄 Logical 메모리 주소를 Physical 메모리 주소로 Binding 하는 시점에 대한 이야기가 나온다. Virtual(Logical) Address를 언제 Physical Address로 바꿀 것인가?? 즉 프로그램 안에서 사용하는 주소를 어떻게 실제 메모리 주소로 바꿀 것인가?? 이에 대한 답으로 총 세 가지 시점이 존재한다.

image

  1. Compile time 컴파일 시에 메모리 주소를 결정한다. 컴파일 시 메모리 주소를 0번지부터 저장한다고 했으면 실제 메모리에 0 번째에 저장한다. 다른 메모리와 겹치면 메모리 공간이 남아도 프로세스를 실행시킬 수 없다. 하나의 프로그램만 실행되는 아두이노 같은 경우에는 사용하기 적합하다. image

  2. Load time 컴파일할때는 Vritual address로 두고, 로딩시에 Base 주소를 Binding 해서 모든 주소를 변환한다. 프로세스 내 메모리 주소를 모두 한 번에 Physical 하게 바꿔야하니 로딩 시간이 너무 오래걸린다.

    image

  3. Execution time Base 어드레스만 정해놓고 그 메모리 주소를 사용하는 명령어를 실행할 때 Base 어드레스를 더한 주소로 메모리에 접근한다.

    image

명령어를 실행할 때 CPU 내부에서 Virtual address를 Physical address로 바꿔주는 하드웨어 로직을 MMU(Memory Management Unit)이라 한다.

image

Contiguous Allocation

이제는 하나의 프로세스가 아닌 여러 프로세스를 실제 메모리에 어떻게 쌓을지에 대한 이야기이다. 가장 간단한 방법으로는 순서대로 쌓는 방법이 있다. 각 프로세스마다 Base address만 정하면 나머지 메모리 주소에 더하기만 하면 되는 가장 단순하고 쉬운 방법이다. Logically Contiguous 한 것을 Physically Contiguous하게 만들어준다. 참조할 수 없는 메모리를 참조할 수 있으니 메모리 주소에 base 어드레스를 더한 값이 메모리 주솟값을 넘어가면 안된다. 따라서 Limit register를 넘어가면 exception을 건다. 프로세스를 Contiguous 하게 쌓다 중간에 있는 프로세스가 비어버리는 것을 Hole이라 한다.

image

Dynamic Storage-Allocation Problem

프로세스가 종료되어 생긴 메모리 영역도 당연하게 사용되어야한다. 따라서 Hole 을 어떻게 사용할 지 세 가지 방법이 존재한다.

  1. First-fit : 들어오는 순서대로 Hole에 들어갈 수 있으면 바로 집어넣는다
  2. Best-fit : Hole 의 크기와 프로세스의 크기를 최대한 맞춰 집어넣는다
  3. Worst-fit : 나머지 공간에 다른 프로세스들이 또 들어갈 수 있도록 가장 큰 Hole에 프로세스를 집어넣는다.

Fragmentation

하지만 당연하게도 모든 hole 과 다음 프로세스들의 크기는 정확하게 맞지 않는다. hole 에 프로세스를 집어넣고 남은 공간을 fragment 라 부른다.

  1. External Fragmentation : Hole의 크기와 프로세스의 크기가 맞지 않아 사용하지 못하는 빈 공간.
  2. Internal Fragmentation : Page로 자를 때의 남는 빈 공간. 15를 크기가 4인 페이지에 집어넣는다고 하면 마지막에는 1의 공간이 남게된다. page에 대해서는 바로 알아보자.
  3. Compaction : Hole을 없애기 위해서 프로세스의 위치를 옮겨 여러 Hole들을 하나로 합치는 것. I/O 오버헤드가 매우 크다.

Paging

Logically contiguous 하지만 phsically contiguous 하지 않게 만드는 방법이다.

프로세스를 특정 크기의 페이지로 잘라서 실제 메모리에 Frame으로 쌓는다. 프로세스를 특정 크기로 자른 것을 Page, 실제 메모리를 같은 크기로 자른 것을 Frame 이라 한다. Page, frame의 크기는 가변적이지만 일반적으로 4kb을 사용한다.

image

문제는 페이지 매핑을 관리하는 것이다. 이를 관리하기 위해 주소를 사용한다. 주소는 페이지 넘버와 페이지 내 offset가 저장된다. page 넘버는 Frame 넘버로 변환되지만 offset은 동일하다. 즉 하나의 프로세스를 여러 page 로 자른 후 frame에 배치하더라도 page의 순서와 매핑된 frame의 순서가 동일하다는 뜻이다. 또한 Table은 프로세스마다 필요하다. (p,d) => (f,d)

image

실제 메모리에서는 비어있는 frame 의 리스트를 관리하는 free-frame list 를 가지고 있다. 그러면 각 프로세스는 frame 을 할당받아 자신의 Page 를 해당 frame 에 저장하게된다.

image

Page Table

Page table entries 의 크기는 CPU MMU안에 집어넣을 수 없기 때문에 테이블은 메모리에 존재한다.

메모리에 저장하는 과정에서 메모리에서 테이블을 가져와 위치를 읽고 그 위치의 메모리에 저장하거나 읽으려면 메모리에 두 번 접근하는 문제가 발생한다. 이를 해결하기 위해 TLB를 사용한다.

TLB

TLB는 MMU 내에 존재한다! MMU가 paging에서 하는 일은 TLB를 관리해 매핑, Translation 해준다. 그리고 작은 프로세스는 대부분이 invalid인 Table이다.

자주 사용되는 메모리에 대한 정보만 캐시 메모리에 넣어 TLB(Translation Look-aside Buffer)라고 부른다. Associative Memory로 page 번호를 넣으면 table로 맞는 frame 번호가 나오며 이를 TLB Hit! 라 한다.

image

Locality

프로세스에서 20%의 영역이 전체 실행 시간의 80% 를 차지하는 경우가 많다. 소수의 메모리 주소가 대부분의 실행시간을 차지하는 것이다. 따라서 자주 사용되는 메모리 주소는 더 쉽게 접근할 수 있도록 하는 개념이 Locality 이다.

  • Temporal locality : 코드 영역에서 while 같은 반복문의 경우이다. 시간적인 지역성을 뜻한다. 지금 참조되었으면 조만간 다시 참조될 가능성이 매우 높다!
  • Spatial locality : 공간적인 지역성을 뜻한다. 데이터 영역에서 배열의 0번이 참조되면 1번도 참조될 확률이 높다!

TLB miss

  1. TLB miss 면 page table로 간다(메인메모리). MMU (CPU)가 알아서 하드웨어적으로 찾아가는 방법.

    MMU에 page table의 위치가 있어야하고 context switch할 때마다 최신화되어야한다.

  2. Interrupt를 통해 OS가 어디로 가야할 지 알려주는 방법. 오버헤드가 너무 크다.

Memory Protection

메모리 보호의 기본은 해당 메모리 주소를 참조 여부를 확실하게 표현하는 것이다. 따라서 Valid / Invaild 표시를 통해 참조할 수 있는 영역인지 구분한다. 이후에 더 확장된다.

image

Hierarchical Paging

outer page 에서 각각의 페이지가 메모리 주소를 가르키는 것이 아니라 paga of page table 을 가르키는 형태이다. page number가 20bit 라고 가정할 때 총 2^20 entries 가 필요하며 하나당 4B 라면 4MB 가 필요하다. 하지만 이를 outer page를 사용한다면 4KB (Outer) + 4MB (Page Table) 이 필요하다. 모든 페이지가 사용될 때는 계층적 페이징이 아무런 효과가 없는 것처럼 보인다.

image

하지만 계층적 페이징은 적은 페이지를 다룰 때 매우 효과적이다. 만약 하나의 페이지만 사용된다고 하면, 기존에는 원래 4MB 가 고정적으로 필요했지만 지금은 Outer 4KB 와 Page Table 4KB 로 총 8KB 만 필요하다.

image

Hashed Page Table

Page Table을 최대로 잡지 않고 동적으로 잡는 방법이다. 하지만 오버헤드가 너무 커서 사용하지 않는다.

image

Inverted Page Table

프로세스별로 Page Table을 가지고 있으니 크기가 너무 크다. 따라서 모든 프로세스의 페이지 테이블을 하나로 모은다는 개념이다. Frame table 과 똑같다. 특정 프로세스에 대한 정보를 다 뒤져서 찾아야하니 큰 사이즈에 대해서 오버헤드가 너무 크다.

image

Shared Pages

코드는 같고 데이터만 다르면 Frame에 코드는 하나만 올려놓고 사용할 수 있다. 같은 것을 중복으로 올리지 않는다는 점에서 효율적이다.

Shared library (DLL) : 라이브러리를 링킹할 때 해당 프로세스와 합쳐서 실행 파일을 만들던지, 메모리에 하나만 올려 놓고 실행할 때 Shared library를 접근해서 사용하는 방법이다. 구현할 때 아주 용이하다. Dynamic Linking 에 사용되는 것!

image

Segmentation (contigious -> page -> 다음!)

고정크기의 Page로 프로세스를 나누다보니 Code/Data/Stack/Heap 영역의 구분이 사라진다는 문제점이 있다. Code / Data를 걸친 Page는 write가 되는지 안되는지 정의하기 어렵다. 의미 있는 단위로 자르자! 에서 시작되어 Segement대로 자르자!가 되었다. Code/Data/Stack/Extra Segment로 4개 단위로 자른다.

  • Segment 번호 / Offest, limit / base를 체크하고 Physical memory에 접근한다.
  • Segmentation 단위로 Contiguous 하게 실행한다.
  • 프로세스가 Code Segment가 같다면 Share 할 수 있다.
  • Segement로 하니 의미있어 R/W/E 정의하기 쉽지만 크기가 가변적이기 때문에 External fragmentation 이 발생한다.

Hybrid approach : Segment를 다시 Paging 하면된다!! Segmentation + Hierachical 2 level paging

image image

업데이트:

댓글남기기

참고