Memory Management 1

  이 글에서는 OS가 하는 일 중 하나인 메모리 관리에 대해 알아보자. 많은 프로그램이 메모리에 올려져서 실행이 되는데 OS는 여려개의 응용 프로그램들이 한정된 메모리 자원을 사용하는 것을 관리해야 한다. 컴퓨터가 막 나온 1950년대 초반같은 경우에는 effective address가 실제 물리적인 메모리 주소였었다. 이때는 전체 시스템에 대한 접근이 제한되지 않은 채 한번에 하나의 프로그램만 실행될 수 있었다.

fig 1

  그 이후에는 다중 프로그래밍이 등장하였는데 2개 이상의 프로그램에서 CPU나 I/O 작업이 겹치게 될 경우에는 처리량이 증가하였다. 어쨌든 이러한 이유로 fig 1처럼 메모리에 여러 프로그램을 올려야 했다. 이때 각 프로그램이 올려지는 위치는 서로 독립적으로 하여 프로그래밍이나 스토리지 관리를 용이하게 하기 위해 base register를 사용하고, 또한 각각의 프로그램들은 서로에게 영향을 끼치면 안되기 때문에 bound register도 사용하였다.

  이렇듯 한번에 많은 프로그램을 돌리게 되면서 '메모리의 용량은 가장 많은 메모리를 차지하는 프로그램의 용량보다 커야한다'라는 문제가 멀티태스킹을 원할하게 하지 못하게 했다. 이를 해결하기 위해 가상 메모리(virtual memory)라는 개념이 등장했다. 이를 사용하는 OS는 프로그램을 실행하는데 필요한 메모리 양에 집중하지 않고 프로그램을 실행하는데 필요한 최소한의 메모리 양에 집중하였다. 여기서는 가상 메모리에 대해 이해하고 이를 통해 메모리를 관리하는 방법에 대해 알아볼 것이다.

Virtual Memory: Goal

  우선 가상 메모리를 이용하여 이루고자 하는 목표에 대해 짚고 넘어가자.

• Transparency: 각각의 프로세스들은 메모리가 공유되고 있다는 것을 인지하지 못하게 하여 메모리를 혼자 쓰는 것 처럼 느껴지게 한다. 즉 프로그래밍시 메모리에 올려질 때의 환경이나 상황을 고려하지 않고 추상화하여 이를 고려하지 않을 수 있는 것이다.
• Efficiency
  • space: 프로그램들이 사용하는 메모리 공간은 서로 다르기 때문에 메모리 공간은 쪼개서 써야한다. 이때 쓰이지 않고 남아있는 공간이 있을 수 있다. 기본적으로 프로그램은 연속적인 메모리 공간을 사용하기 때문에 최대한 작은 fragment가 없게끔 하는 것이 유리하다.
  • time: 메모리를 여러 프로그램이 나눠쓰기 때문이 처리속도가 느려질 수 밖에 없다. 이를 개선하기 위해 HW적인 도움을 받아야 한다.
• Protection: 프로세스들이 동시에 실행되는데 이때 서로간의 protection을 제공해줘야 한다. 즉 OS나 다른 프로세스가 자신의 자원에 접근하는 것을 방지(isolation)하거나 만약 프로세스간 협력이 필요하면 메모리 공간을 공유할 수도 있어야 한다.

 

Accessing Memory

fig 2

  c에서 포인터를 처음 배웠을 때 봤을법한 예제이다. 두번의 실행에서 변수 n의 주소가 모두 동일한 것을 확인할 수 있다. 그렇다면 지금이야 순차적으로 두번을 실행한 것이지만 만약 이 프로그램 2개를 동시에 실행하게 되면 어떻게 될까? 동시에 같은 메모리 주소에 접근하게 되어 오류가 발생할 것 같지만 실제로는 아무런 문제도 발생하지 않는다. 왜냐하면 각각의 프로그램은 독립적인 주소 공간(Address Space)를 가지기 때문이다.

fig 3. (Virtual) Address Space

  fig 3는 프로세스가 가지는 메모리 공간의 abstract view이다. 그 말인 즉슨 각 프로세스는 fig 3의 공간을 가지지만 실제 physical한 환경과 어떻게 mapping될지는 아직까지 모른다는 것이다. 각 구조에 대해서는 '시스템 프로그래밍'에서 알아본 적이 있으니 넘어가자.

 

Virtual Memory

  정리하자면 가상 메모리는 가상의 주소공간을 각 프로세스에게 제공해주는 것이다. 이 공간은 굉장히 크고 연속적이고 각각 private하다. 그리고 우리가 여태껏 프로그래밍하면서 봐왔던 메모리 주소들은 기본적으로 모두 virtual address였다. 그렇기 때문에 가상의 주소공간을 실제 물리적 메모리(Physical memory) 주소로 변환할 수 있어야 한다. 이것을 address translation이라고 하며 이는 런타임에 수행된다.

  또한 가상 메모리를 통해 프로그램 실행 시 모든 것을 메모리에 올리는 것이 아니라 그때그때 필요한 부분만 메모리에 올려서 사용할 수 있게된다. 이렇게 되면 시작할 때 언급했던 '메모리의 용량은 가장 많은 메모리를 차지하는 프로그램의 용량보다 커야한다'라는 문제를 해결할 수 있게 된다. 이를 lazy allocation이라 한다.

fig 4

  fig 4를 보자. P1과 P2 모두 실행되어서 가상 메모리 공간을 할당받은 상태에서 어느 data에 접근하고 있다. 이때의 가상 주소는 둘다 0x100이 찍힐 수도 있으나 실제 address translation이 일어나면 접근되는 physical memory address는 서로 다른 것이다.

  그럼 현재 virtual memory의 테크닉들을 살펴보기 전에, 예전에는 어떻게 메모리를 관리해왔는지 알아보자.

 

Static Relocation

fig 5

    fig 5의 왼쪽을 보자. 프로그램은 항상 0번 주소부터 시작한다고 하자. 이 프로그램이 실제 메모리에 올라가려면 오른쪽 처럼 주소를 변환할 필요가 있는 것이다. 만약 메모리에 프로그램이 0x1000부터 위치한다면 즉 시작주소가 0x1000이라면 이것을 각각의 code나 data 주소에 더해주는 것이다. 이렇게 하면 상대적 주소로 나타낸 프로그램을 메모리의 절대적인 주소로 표현할 수 있다.

Pros and Cons

  이 방법의 장점은 단순히 시작 주소를 더해주면 되기 때문에 HW적인 도움이 필요없다는 것이다. 즉 굉장히 단순하다는 것이다.

  단점으로는일단 protection이 불가능하다. 즉 메모리에 프로그램이 불러와질 때 OS나 다른 프로세스의 메모리 영역을 침범할 수 있고 어떤 메모리 주소도 읽는게 가능하기 때문에 privacy도 지켜지지 않는다. 그리고 일단 메모리에 프로세스가 위치하게 되면 주소공간을 이동할 수 없다. 그렇기 때문에 fig 5의 오른쪽 그림처럼 빈 공간(회색)이 띄엄띄엄하게 생기게 된다. 이것이 심해지면 다른 프로세스를 돌릴 수 있을만큼의 공간이 있어도 그 프로세스를 돌리지 못하는 경우가 발생하게 되는 것이다. 이것을 external fragmentation이 발생했다고 한다.

 

Memory Fragmentation

  조금 전 external fragmentation에 대해 언급했었다. 이 (external) Fragmentation은 정확히 무엇일까?

fig 6

  fig 6의 첫번째 그림 보자 free한 공간 24K가 두 개 있다. 그 다음 user 4&5 프로세스가 도착해서 메모리에 올려져서 두번째 그림처럼 된다. 이후 user 2&5가 종료되어 메모리에서 없어지면 메모리 상태는 세번째 그림처럼 된다. 이 때의 빈 공간만 보면 56K의 빈공간을 확인할 수 있다. 이는 연속된 공간이 아니다.

  그런데 (지금까지는) 프로그램이 메모리에 올려지려면 그 크기에 해당하는 연속적인 공간을 할당 받아야 했다. 이에 따르면 56K라는 빈 공간이 있지만 이보다 작은 48K의 프로그램을 메모리에 올리는 것이 불가능한 것이다. 

Dynamic Relocation

  Static Relocation의 문제를 해결하기 위한 위한 방법이 바로 Dynamic Relocation이다. 이것은 HW의 도움을 받는다. MMU(Memory Management Unit)라는 HW는  memory를 참조하는 instruction마다 address translation을 수행한다. 이를 수행하면서 가상 주소가 유효한지 아닌지 판단하고 아니라면 exception을 날려서 처리해준다. 그러므로 OS는 context switching이 발생할 때마다 MMU에게 현재 실행하고 있는 프로세스의 유효한 주소 공간에 대한 정보를 알려줘야 한다.

  현재 대부분의 컴퓨터에서는 Dynamic Relocation을 사용하고 있는데 이를 수행하기 위한 방법으로는 다음이 있다. 이것들에 대해서 하나씩 살펴보자.

• Fixed or variable partitions
• Segmentation
• Paging

 

Fixed Patitions

fig 7

  이 방법은 메모리를 고정된 크기의 파티션들로 나누는 것이다. 이 파티션의 수만큼 프로세스들이 올라올 수 있다. 각각의 파티션은 시작 주소를 가지게 되는데 예를 들어 1번 파티션에서 돌게되는 프로세스의 base register 값은 0x2000이다. 그러므로 0x0362라는 가상주소는 1번 파티션에 올라가게 되면 0x2362라는 실제 메모리 주소로 변환되는 것이다.

  이 방법은 base register의 HW적인 도움이 필요하다. 하지만 그렇게 복잡한 구조는 아니다. 실제주소를 얻으려면 가상 주소에 base register의 값을 더하기만 하면 되기 때문이다. 이러한 base register는 context switching 발생 시, OS에 의해 로드된다. 이러한 점 때문에 상대적으로 구현이 간단하고 빠르게 context switcing이 가능하다.

  하지만 단점이 당연히 존재한다. 우선 partition의 크기보다 현저히 작은 프로세스가 올라오게 되면 나머지 부분은 낭비가 된다. fixed partition에서는 프로세스가 다른 프로세스의 파티션에 접근할 수 없기 때문이다. 이렇듯 프로세스가 필요한 양보다 더 큰 메모리 공간이 할당되어 메모리가 낭비되는 상황을 internal fragmentation이라고 한다. 또한 하나의 파티션 크기보다 큰 프로세스는 올라올 수 없는게 문제가 될 수 있다.

fig 8

  이러한 단점을 개선한 것이 fig 8처럼 파티션의 사이즈를 다르게 설정하는 것이다. 이렇게 하면 프로세스는 적은 공간이 필요한 프로세스냐 큰 공간이 필요한 프로세스냐에 따라 적절한 파티션을 선택할 수 있다. 프로세스들을 파티션에 할당하기 위한 전략으로는 각 파티션 사이즈마다 큐를 두거나, 하나의 큐에 first fit이나 best fit 방법을 선택할 수 있다. first fit은 빈 파티션에 들어갈 수만 있다면 그 파티션에 프로세스가 들어오는 것이고, best fit은 현재 비어있는 파티션 중 가장 공간 낭비가 적은 것을 선택하는 것이다. 이 방법은 모든 파티션을 다 탐색하는 데에서 오버헤드가 상대적으로 크게 발생할 수 있다.

 

Variable Partitions

fig 9

  이 방법에서는 limit register가 추가되어 현재 프로세스가 얼마만큼의 영역을 사용할지 설정한다. 우선 가상 주소와 limit register의 값과 비교하여 가상 주소에 값이 크다면 접근하지 말아야 할 공간에 접근 중이므로 protection fault를 일으킨다. 만약 그게 아니라면 base register의 값을 더해 실제 주소를 획득하여 접근할 수 있다.

  이러한 점 때문에 이 방법은 단순하면서 구현이 간단한 편이다. 그리고 파티션이 고정된 사이즈를 가지지 않고 필요한 만큼의 공간을 받을 수 있기 때문에 internal fragmentation을 없앨 수 있긴 하지만 external fragmentation은 발생할 수 있다.

  하지만 fixed partitions와 동일하게 각각의 프로세스들은 실제 메모리에서 연속적인 공간을 할당받아야 한다. 이것이 external fragmentation을 발생시키는 원인이다. 그리고 파티션의 일부를 다른 프로세스와 공유하는 것이 불가능하다.

 

Segmentation

  여기서 좀 더 발전한 방법이 Segmentation이다. 이 방법은 우리가 계속 배웠던 'code, data, stack, heap'등의 영역으로 address space를 쪼갠다. 하나의 프로세스를 여러개의 segment로 분할하였기 때문에 가상 주소는 '<Segment #, Offset>'으로 표현될 수 있다. 각각의 segment는 독립적으로 physical memory에 위치하게 되며 확대되거나 축소될 수 있고,  protect될 수도 있다.

  헷갈릴 수 있는 걸 정리하고 넘어가자면, variable partitions는 프로세스 당 하나의 segment가 있는 것이고 segmentation은 프로세스 하나에 여러개의 segment가 있는 것이다. 

fig 10

  fig 10을 보면 code, data, heap, stack에 따라 segment로 나누고 상위 비트를 이용하여 segment를 구분하고 있다. 그리고 각각의 segment에는 base, limit, protection, valid, direction(아래/위로 확대되는지)에 대한 정보를 담고 있다. 그리고는 variable partition과 유사한 방법으로 메모리 접근 가능 여부를 판단한 뒤에 메모리에 접근한다. 

  그렇기 때문에 segmentation은 프로세스의 쪼개진 일부분을 idle한 메모리 공간에 넣어줄 수 있고 segment 단위로 쉽게 protection이 가능하다. valid bit를 줄 수도 있고 segment마다 다른 protection bits를 두는 것도 가능하다. 이렇게 되면 code 영역은 읽기 전용, 시스템 영역은 커널모드에서만 접근할 수 있게 하는 것도 가능하다는 것이다. 또한 segment 단위로 공유도 가능하다. 예를 들어 shared library 같은 경우에는 code 영역을 공유할 수 있게 만들어 줌으로써 각각의 프로세스가 각각의 코드를 모두 올릴 필요없이 해당 영역을 가리키면서 공유하면서 사용하는 것이다. 그리고 각각의 세그먼트는 빈공간에 차곡차곡 들어가도록 할 수 있게끔 dynamic relocation을 돕는다.

  이 방법의 단점은 프로세스를 분할할 수는 있지만 segment 각각은 연속적으로 할당된다는 것이다. 그렇기 때문에 external fragmentation을 완전히 해결하지는 못한다. 특히 segment의 크기가 크면 이것이 더 심해질 수 있다. 그리고 fig 10처럼 segment를 구분하기 위해 segment table을 사용하는데 이것이 메인 메모리의 공간을 차지하고 속도를 위해 HW cache를 사용해야 한다. 그리고 segment를 공유할 때 이를 공유하는 segment들은 공유 segment의 포인터 정보등을 알고있어야 하므로 이것이 오버헤드가 된다.

---

• Operating System Concepts, Avi Silberschatz et al.
• Operating Systems: Three Easy Pieces
  • Remzi H.Arpaci-Dusseau andAndreaC.Arpaci-Dusseau
  • Available(withseveraloptions)athttp://ostep.org