[운영체제] 메모리 관리의 이해 - 메모리 할당, 단편화, 페이징
메모리가 무엇인가? 메모리는 어디에 쓰이는가? 이런 기초적인 부분에 대해선 간단하게 언급만 하고 넘어간다.
하드디스크(보조기억장치)에 저장된 프로그램이 CPU에서 실행되려면 필요한 데이터가 메모리(주기억장치)로 넘어 와야 한다. CPU에서 다이렉트로 하드 디스크를 조작하기엔 속도 차이가 엄청나게 많이 나기 때문에 요즘은 CPU가 하드디스크에 직접 접근하는 일은 없도록 되어 있다. 여기서는 이정도만 알면 아래 내용을 이해하는데 문제가 없다.
자, 메모리는 하나인데 프로세스는 여러개이다. 이 자원을 어떻게 효율적으로 사용 할 것인가?
Contiguous Memory Allocation
연속적 메모리 할당
Base and Limit방식이다. 메모리에 프로세스를 연속적으로 할당하는 방식으로, 특정 프로세스가 메모리의 어떤 위치에 올라가 있다면 그 시작 위치가 base이고, 그 끝 위치가 limit이다.
CPU나 프로세스의 관점에서는 base부터 limit까지의 공간만 인식 할 수 있다. 이걸 Logical Address라고 한다. 만약 4GB의 메모리가 있다면 Physical Address는 4GB의 공간 안에서 특정 위치를 엑세스하는 주소이지만, 어떤 프로세스가 10MB의 메모리를 사용하고 있다면 Logical Address는 그 10Mb안의 주소밖에 보지 못하고 그걸 전체로 인식하는 것이다.
당연히 Logical Address 를 Physical Address로 Mapping 해 주는 무엇인가가 있을 것이다. 이 역할을 하는 하드웨어가 MMU(Memory Management Unit)이다. 이 하드웨어의 동작을 간소화 하여 설명 하자면
base가 14000이고 limit이 16000인 어떤 프로세스가 접근 할 수 있는 메모리는 0~1999이다. 만약 433번 주소에 접근을 원한다고 하면 MMU는 14000 + 433 를 해서 물리적인 메모리의 실제 주소인 14433번으로 엑세스 하게 해 준다.
아주 간단하고 편한 방식 같이 보인다. 하지만 이 방식은 아주 옛날에 사용했던 방식이고 요즘은 전혀 사용하지 않는다. 어떤 문제가 있었기 때문일까?
가장 대표적인 문제는 External Fragmentation(외부 단편화)이다. 만약 전체 용량이 1GB인 메모리가 30%정도 차 있다고 한다. 지금 가용한 메모리 공간은 700Mb가 있지만 700Mb은 연속적인 빈공간이 아니다. 메모리가 연속적으로 할당되었다가 해제되기 때문에 중간중간 사용되고 있는 부분이 있고, 빈공간이 있는 형태이다. 이 빈공간을 hole이라고 부르는데 그걸 다 합치면 700Mb라는 것이다. 만약 hole이 200Mb, 300Mb, 100Mb, 100Mb으로 나누어져 있다고 하면 메모리가 400Mb가 필요한 프로세스는 실행 될 수가 없다. 전체빈공간이 700Mb나 있는데 말이다.
이 문제를 해결하는 방법은 딱 한개가 있다. 바로 Compaction이다. 공간이 많이 쪼개진것 같으면 현재 사용되고 있는 메모리를 한곳으로 몰아서 이동시킴으로써 연속적인 빈 공간을 확보하는 것이다. 물론 cost가 작진 않을 것이다. 결국 External Fragmentation이 발생하지 않게 하는 궁극적인 방지책은 없다. 그래서 Base and Limit방식이 요즘 사용될수 없는 것이다.
물론 오랫동안 사용되었던 방법이므로, 그런 문제를 완화시키려는 여러 이론들이 있었을 것이다. 가장 간단한 문제가 빈공간이 여러가지 크기로 남아 있을때 새로운 프로세스가 메모리 어딘가에 할당 되어야 한다면 어디에 할당 시켜야 External Fragmentain 발생 빈도가 적도록 하는가이다. 아래 세가지 방법이 있다.
- First Fit : 그냥 들어갈 수 있는 가장 앞에 있는 공간에 넣는다.
- Best Fit : 들어갈 수 있는 공간 중 가장 작은 공간에 넣는다.
- Worst Fit : 들어갈 수 있는 공간 중 가장 큰 공간에 넣는다.
이름만 보고 좋고 안좋음을 따지면 안된다. 한개씩 살펴 보자면, 가장 간단한 방법은 First Fit이다. 하지만 공간이 어떻게 남게 될지 알 수 없으므로 자원의 효율을 신경쓴 방법은 아니다.
두 번째는 이름만 보면 아주 절절한 방법 같다. 그 의미를 따져 보더라도, 프로세스의 크기과 hole의 크기가 가장 비슷한 곳에 넣으므로 hole이 가장 작게 남기 때문에 좋아 보인다. 하지만 이렇게 되면 어디에도 쓰기 애매한 작은 hole들이 많이 발생하게 된다.
세 번째는 이름만 보면 가장 안좋아 보이지만 의외로 가장 적절한 방법이다. 그냥 제일 큰 공간에 찾아 들어가는 것이다. 남는 공간도 넉넉하기 때문에 애매한 공간이 남게 될 확률도 적다.
하지만 그 어떤 방법도 Contiguous Allocation의 궁극적인 문제를 해결하진 못한다. 프로세스의 크기가 가변적이가 때문에 어떻게 할당 하더라도 공간이 낭비가 생길 수 밖에 없다.
Non-contiguous Memory Allocation
비연속적 메모리 할당
그래서 결국 해결법은 contiguous하지 않게 하는 것이다. 물리적 메모리를 작은 Frame 단위로 나눈 후, 프로세스도 그에 맞게 여러개의 Page로 잘라서 할당하는 것이다. 그렇게 되면 공간이 애매하게 남고, 그걸 방지 하기 위해 어디에 할당 되어야 하고.. 이런 구질구질한 문제가 생기지 않는다. 물론 프로세스가 페이지의 크기보다 작거나, 여러개의 페이제 할당 하고 마지막 페이지를 전체 다 사용하지 못할 경우 페이지 내부엔 짜투리 공간이 조금 남을 수도 있다. 이것이 Internal Fragmentation(내부단편화)이다. 하지만 이는 외부 단편화에 비하면 크게 고려할만한 문제는 아니다.
Paging
하지만 Contiguous Allocation에선 없었던 문제가 또 생겼다. Contiguous Allocation에서는 base, limit만 있으면 원하는 physical address를 찾기 쉬웠지만, Non-countiguous Allocation에서는 프로세스가 쪼개져서 메모리 공간 어디든 들어갈 수 있기 때문에 그 위치를 다 저장 해 둬야 한다.(각 page의 base정보) 그래서 이런 정보를 모아둔 Page Table이란게 따로 있다.
메모리에 접근 할때 마다 메모리의 Page Table을 한번 거쳐야 되기 때문에 Contiguous Allocation방식에 비해 속도 저하의 원인이 될 수 있다. 그래서 Memory가 아닌 TLB(Table Lookaside Buffer)라는 별도의 Cache를 사용한다.
Page Table엔 모든 Logical page number에 대응되는 Physical frame number가 저장되므로, 일차원 배열을 사용한다. Logical page number가 index로 사용되는 것이다. 하지만 TLB는 일부만 캐싱하므로 페이지 넘버와 프레임 넘버 정보를 모두 가지고 있어야 한다.
그리고 지금 주소의 구조를 보면 p와 d, 그리고 f와 d로 나눠져 있는걸 확인 할 수 있다. 이는 주소값이 page number, frame number와 offset으로 나눠져 있다는 것을 의미한다. Page와 Frame의 크기는 같으므로 그 안의 내용은 그대로이다. 즉, page가 어느 frame인지만 알면 그 안의 세부 address(offset)는 따로 찾을 필요가 없다는 것이다. 그래서 Logical address와 Physical address를 매핑할때 접두부에 있는 page number만 매핑하고 나머지 주소는 그대로 사용한다.
Two-Level Page
이 부분은 바로 예를 봄으로써 이 level hierarchy가 왜 필요하고 어떻게 구성하는지 보겠다. 32bit 컴퓨터이고 페이지 사이즈는 1kb를 사용한다고 한다. 32bit 컴퓨터는 32bit 짜리 logical address를 사용한다는 말이다. 이 중 1kb인 10비트가 offset으로 사용된다. 나머지 22비트가 페이지 수라고 할 수 있다. 그렇다면 페이지 테이블의 사이즈는
222 * 페이지 테이블 엔트리에 저장되는 정보들
만큼이 된다. 페이지 테이블에는 프레임 넘버, 벨리드 플레그 등등 여러 정보들이 들어가는데, 약 4byte정도가 된다고 한
다. 그렇다면 222bit * 212bit = 232bit = 224byte ≒ 16Mb정도가 된다.
한 페이지에 1kb를 담을 수 있는데, 페이지 주소를 담은 페이지 테이블이 16Mb이다. 그렇다면 필요한 페이지 수는 214 개이다. 이정도 사이즈라면 메모리에 연속적으로 할당할 수가 없다. 페이지 테이블도 여러 페이지에 나눠져 들어가야 하는 것이다.
그럼 또 페이지 테이블이 들어간 프레임의 주소를 저장해둔 별도의 페이지 테이블이 필요하게 된다. 이 페이지 테이블은
엔트리의 수가 2의 14승이 되고, 페이지 테이블 전체 크기는 아까의 계산법을 그대로 적용하면 2의 18승 바이트가 된다. 페이지의 크기가 2의 10승 바이트이므로 또 2의 8승 = 62개의 페이지가 필요하게 된다.
여기서 64개의 페이지 정보는 메모리의 어딘가에 연속적으로 저장을 해 둔다고 가정을 해야한다. 시스템이 그렇게 되어 있어서 Two-level paging이 가능하다. 그렇다면 이 64개의 연속된 페이지는 그냥 크기가 2의 14승인 배열로 생각하면 된다.
즉, 14비트를 사용하면 일단 원하는 페이지에 접근 가능하다. 하지만 그 페이지 안에는 또 다른 페이지 테이블의 주소가 있을 뿐이다. 한 페이지의 크기가 1kb이고 페이지테이블 엔트리의 크기가 4byte라고 했으므로 2의 8승개의 페이지 정보가 저장 되어 있을 것이다. 그럼 거기에 8비트를 사용 해야 한다.
즉, 14비트 + 8비트 + 오프셋 10비트로 구성되어서 총 32bit가 되는 것이다.
페이지 엔트리의 크기가 늘어나면 Two level이 아니라 3, 4 level까지 늘어날 수도 있고 그러다 보니 요즘은 32bit 체계가 아닌 64bit 메모리 체계까지 나오게 되는 것이다.
Hashed Page Table
Page Table에서 해쉬를 사용하기도 한다. logical address의 페이지넘버를 hash function을 통해 hashed page table에서 대응된 frame을 찾는다. 보통은 빠른 속도를 위해 hash를 쓰지만 여기서는 offset방식보다 빠르지 못하다. 그런데 hashed table을 사용하는 이유는 보통 메모리 사용량이 10~30%정도 밖에 되지 않기 때문이다. 위에서 배웠던 offset방식에선 메모리를 5%만 쓰고 있더라도 16Mb의 메모리를 모두 비워 놓고 flag만 invalid로 걸어 둬야 한다. 이런 낭비를 막기 위해서 딱 필요한 page - frame 대응 정보만 저장하기 위해 hashed 테이블을 사용 하기도 한다. 하지만 요즘은 많이 사용되지 않는다.
Inverted Page Table
index로 frame number로 가진 큰 일차원 배열을 page table을 사용한다.
Segmentation
일정한 frame의 크기대로 page를 나누는 것이 아니라, 프로그램 내부적으로 용도별 segment로 세분화 한다. 무슨 말이냐 하면 한 프로세스를 subtoutine, stack, programcode들의 요소들로 나누어서 메모리에 할당 하는 것이다. 단위가 작아졌기 때문에 External Fragmentaion의 정도는 작아지겠지만, 요소 하나하나의 사이즈는 variable이고 각각 contiguous하게 메모리에 할당되므로 contiguous allocation의 문제를 어느정도 안고 가는 것이다. 하지만 중복된 부분을 여러 프로세스에서 공유할 수 있다는 장점이 생긴다.