[ 운영체제 ] 메모리 관리 1 - 페이징(Paging)

드디어 대망의 메모리 관리 파트다. '메모리 계층 구조'부터 '주소 공간'까지 아직 안 읽었다면 읽고 오는 것을 추천한다. 앞의 내용을 숙지하고 있어야 이번 챕터를 잘 이해할 수 있기 때문이다. 

 

이번 글은 논리적 주소를 물리적 주소로 mapping 할때 연속적으로 mapping 하면 어떤 문제가 발생하는지, 이에 대한 해결책은 무엇인지 알아본다. 해결책은 제목에 떡하니 나와 있다. 

연속 할당의 문제점 - 외부 단편화(External Fragmentation)

바로 이전 글에서 논리적 주소를 설명하면서 '연속 할당'의 개념을 다뤘었다. 다시 한 번 상기시켜보자. 연속 할당이란 한 프로세스의 모든 논리적 주소에 동일한 base register를 더해주는 것이다. 이는 MMU에 의해 이뤄지며 주소는 Execution time에 바인딩 된다는 특징이 있다. 모든 프로세스는 논리적 주소가 0번지부터 시작해서 차례대로 증가하기 때문에, 물리적 주소도 시작 주소만 다르지 연속적으로 배치되어 있다. 그림으로 보면 아래와 같다. 

Contiguous Memory Allocation

 

이제 새로운 용어 두 개가 등장한다. Partition과 Hole의 정의는 아래와 같다.

Partition : 프로세스의 메모리 공간.
Hole(Free Partition) : 메모리에서 할당 받지 못한 공간. 사용 가능한 공간.

 

운영체제는 Hole을 제외한 파티션의 개수 만큼 동시 실행 가능하다. 만약에 새로운 프로그램을 실행하려고 하는데, 요구하는 프로세스의 용량이 Hole의 크기보다 크면 메모리에 올라갈 수 없으므로 실행되지 못한다. 이를 잘 기억해놓자. 이제 아래와 같은 상황에서 '프로세스 F' 를 실행시킬 수 있는지 판단해보자.

크게 어렵지 않은 문제다. 프로세스 F가 들어갈 연속된 자리가 없으므로 당연히 프로세스 F는 실행 불가능하다. 그런데 따지고 보면 프로세스 F가 들어갈 빈 공간은 충분하다. 위에서 흰색 칸이 Hole에 해당하는데, Hole의 합은 60MB로 프로세스 F의 크기보다 크기 때문이다. 이렇게 메모리에 공간이 있음에도 불구하고 연속된 Hole의 크기가 프로세스의 크기보다 작다는 이유로 할당되지 못하는 문제를 외부 단편화라고 한다. 

외부 단편화(External Fragmentation)
: 메모리에 공간이 충분히 있음에도 불구하고 연속된 Hole의 크기가 프로세스의 크기보다 작다는 이유로 할당되지 못하는 문제

 

저명하신 학자님들의 분석에 따르면, 연속 할당을 할 경우 외부 단편화로 인해 메모리 공간의 1/3 을 낭비한다고 하는데 이를 '50 percent rule'이라고 한다.

 

그렇다면 외부 단편화를 해결하는 방법이 없을까? 

외부 단편화 해결 방법 1 - Compaction

파티션들을 재배치해서 모든 Hole들을 한 곳으로 결합하는 방법이다. 예를 들어 아까 예제에서 '프로세스 F' 가 들어갈 수 있도록 아래와 같이 파티션들을 재배치 하는 것이다. 

Compaction : Hole들을 하나로 결합

그런데 Compaction을 하려면 기존의 메모리를 임시 공간에 복사해야 한다. 메모리에 복사할 수 없기 때문에 하드디스크에 복사해야 하는데, 하드디스크에 복사했다가 다시 가져오는 행위는 시간적 소모가 너무 심하다. 따라서 Compaction은 가능하긴 하지만 오버헤드가 굉장히 심하므로 사용하지 않는 방법이다. 

외부 단편화 해결 방법 2 - 불연속 할당

외부 단편화의 발생 원인은 '연속 할당'이었다. 그러면 주소를 불연속적으로 할당하면? 당연히 외부 단편화는 발생하지 않는다. 이렇게 주소를 불연속적으로 할당하는 메모리 관리 구조를 Paging이라고 한다. 

Paging

페이징은 아까 말했듯이 외부 단편화의 해결 방법으로, 주소를 불연속적으로 할당하는 메모리 관리 구조를 말한다. 페이징을 공부하면서 자주 등장하는 용어 두 개가 있다. 바로 '페이지'와 '프레임'이다.

Page (페이지) : 가상 메모리를 일정한 크기로 나눈 블록
Frame (프레임) : 물리 메모리를 일정한 크기로 나눈 블록

페이지 크기 = 프레임 크기

 

'일정한 크기'로 나눈 이유는 메모리의 효율적 관리를 위해서다. 페이지와 프레임의 크기는 같은데, 이렇게 함으로써 페이지에 대응되는 프레임을 좀 더 쉽게 찾을 수 있다. 이는 곧 나오는 예제를 통해 이해할 수 있을 것이다. 요점은 페이지의 크기가 정해지면 이 크기가 메모리 단위가 된다는 것이다. 참고로 페이지의 크기는 CPU에서 정의된다.

 

이제 모든 프로세스는 페이지 크기만큼 조각화되고, 물리적 메모리도 페이지 크기만큼 조각화된다. 그리고 프로세스의 각 페이지는 물리적 메모리의 조각인 프레임에 불연속적으로 할당된다. 이때, 페이지와 프레임의 대응 관계도는 '페이지 테이블'에 저장되어 있다. 그림으로 정리하면 아래와 같다. 논리적 메모리에서는 연속적이던 페이지들이 페이지 테이블을 거치고 나서는 불연속적으로 바뀐 것에 주목하자.

 

페이징의 핵심은 'Page Table'에 있다. 프로세스의 페이지가 어떤 식으로 프레임에 mapping 되는지 이해하면 페이징은 완벽하게 이해한 것으로 봐도 된다. 참고로 페이지 테이블은 모든 프로세스마다 개별적으로 가지고 있는 정보다. 따라서 n개의 프로세스가 있다면 페이지 테이블 또한 n개 있다는 뜻이다. 페이지 테이블은 커널에 저장되어 있다. 

 

이런 구조를 사용함으로써 얻을 수 있는 이점은 무엇이 있을까?

 

우선 주소를 연속적으로 할당함으로써 외부 단편화를 해결할 수 있다. 위 그림에서 물리적 메모리의 2번 인덱스가 비어있지만 페이지와 프레임의 크기가 똑같으므로 다른 페이지가 2번 인덱스에 들어갈 수 있기 때문이다. '빈 공간(프레임)'이 있어도 크기가 항상 페이지와 같으므로 더이상 '빈 공간'은 걱정하지 않아도 된다. 연속 할당에서 외부 단편화가 발생한 이유가 이 '빈 공간' 때문이었다.

 

프로세스끼리 메모리 공유도 훨씬 용이해진다. 왜냐하면 프로세스별로 공유하는 페이지의 물리적 주소를 페이지 테이블에 저장하면 되기 때문이다. 말로 하면 더 헷갈리니깐 그림으로 보자. 

위 그림에서 P1, P2, P3는 페이지 ed1, ed2, ed3를 공유하고 있다. 각 프로세스의 페이지 테이블에 ed1, ed2, ed3의 물리적 주소를 저장해두면 메모리 공유를 쉽게 할 수 있다. 물리적 메모리에는 code와 같이 공유하는 부분을 저장해두고, 프로세스의 페이지에는 힙, 스택과 같은 private 테이터를 저장해두면 메모리 낭비를 줄일 수 있다. 

 

이제 페이지가 어떻게 프레임에 할당되는지 알아보자. 위 그림에서 P1의 ed1이 페이지 테이블을 거쳐 물리적 메모리의 ed1까지 접근하는 원리를 이해하는 것이 목표다. 

 

반응형

[ Page → Frame ] Mapping 과정 이해하기

1. 오프셋 (Offset)

먼저 '오프셋(Offset)'이란 개념을 이해해야 한다. 크게 어려운 개념은 아니다. '위치를 찾기 위해 더해주는 값' 정도로 이해하면 된다. 바로 예제를 살펴보자. 주소 공간을 0 ~ 31 로 설정하고 페이지 크기를 4로 설정하자. 그러면 아래와 같이 8개의 페이지가 생성된다. 

여기서 모든 주소를 페이지로 표현하려면 어떻게 해야할까? 아래와 같이 나타낼 수 있다.

현재 주소 = ( #페이지 * 페이지 크기 ) + offset

ex1)   3 = (0 * 4) + 3    // 3번지 주소는 Page0의 3번째 인덱스
ex2)  6 = (1 * 4) + 2     // 6번지 주소는 Page1의 2번째 인덱스
ex3)  17 = (4 * 4) + 1   // 17번지 주소는 Page4의 1번째 인덱스
ex4)  30 = (7 * 4) + 2  // 30번지 주소는 Page 7의 2번째 인덱스 

※ 인덱스는 0부터 시작함에 유의 !!

 

위와 같이 모든 주소는 '페이지 번호'에 '페이지 크기'를 곱해주고, '페이지 크기'보다 작은 값을 더해주면 된다. 여기서 더해주는 값을 '오프셋'이라고 한다. 오프셋의 크기는 페이지 크기보다 항상 작다. 

 

위 예시를 수학적으로 접근해보자. 우리는 주소 공간을 0 ~ 31 까지로 설정했는데 이는 5개의 비트로 표현 가능하다. 그리고 페이지 크기는 4(2^2)로 설정했는데 이는 2개의 비트로 표현 가능하다. 그런데 '주소의 개수'와 '페이지 크기'를 알고 있으면 '페이지 개수'는 자동으로 구해진다. 왜냐하면 '주소의 개수'를 '페이지 크기'로 나눈 값이 '페이지 개수'가 되기 때문이다. 식으로 정리하면 아래와 같다. 

주소 공간의 크기 = 2^5 (5 bit)
페이지 크기 = 2^2 (2 bit)
페이지 개수 = 2^5 / 2^2 = 2^3 (3 bit)

 

우리는 이제 비트에만 관심을 가질 것이다. 위 식으로부터 '주소 공간의 크기' 비트와 '페이지 크기' 비트만 결정되면 '페이지 개수' 비트는 자동으로 결정됨을 확인했다. 생각해보면 당연하다. 이 아이디어를 잘 기억하고 있자.

2. 페이지 테이블 (Page Table)

페이지 테이블에 저장되어 있는 값은 정확하게 말해서 각 페이지의 '물리적 주소에서의 시작 주소값'(base address)이다. 즉, 모든 논리적 주소는 페이지 테이블에서 자신의 base address를 찾고 이 값에 offset을 더해주면, 더해준 값이 물리적 주소가 되는 것이다. 한편, 페이지 테이블 또한 메모리에 저장되는 정보이기 때문에 '인덱스-값'의 자료구조를 가진다. 그러면 페이지 테이블의 인덱스는 몇 개가 필요할까? 당연히 페이지의 개수만큼 필요하다. 예를 들어 7개의 페이지가 있으면 페이지 테이블은 7개의 값을 가져야 한다. 페이지와 페이지 테이블의 값은 일대일 대응 관계다. 

 

이제 각 페이지가 어떻게 페이지 테이블에 매핑 되는지 알아보자. 해답은 논리적 주소에 있다. CPU에 의해 생성되는 모든 논리적 주소는 아래와 같이 두 부분으로 나뉜다. 

논리적 주소 공간의 크기 =  2^m (byte)
페이지 크기 = 2^n (byte)
페이지 테이블의 크기 = 2^(m-n)  (byte)

page number(p) = m - n (bit)
page offset(d) = n (bit)

※ offset은 n개의 비트로 표현 가능한 수로, 페이지 크기(2^n) 보다 항상 작다

 

예를 들어 보자. 16 bit CPU의 경우 논리적 주소는 16 비트로 표현된다. 만약에 페이지 크기를 4비트로 정하면 페이지 개수는 12비트로 자연스럽게 구해진다. 그런데 페이지의 개수는 페이지 테이블이 가지는 값의 개수와 일치해야 하므로 page number를 page table index로 봐도 무방하다. 따라서 페이지와 페이지 테이블의 매핑 관계를 그림으로 정리하면 아래와 같다. 

 

여기서 base address에 페이지의 offset 값을 더할 수 있는 이유는 페이지의 크기와 프레임의 크기가 동일하기 때문이다.

 

한편, 페이지 테이블의 참조는 굉장히 빈번하게 일어나므로 하드웨어의 도움을 받아야 한다. 이전 글에서 주소 바인딩을 할 때 MMU의 도움을 받았었다. 이 경우도 마찬가지로 MMU의 도움을 받는다. MMU의 기능만 다를뿐이다. 연속 할당일때와 불연속 할당일때의 MMU 구조는 아래와 같다. 

왼쪽이 연속 할당일때의 MMU 구조, 오른쪽이 불연속 할당일때의 MMU 구조

3. 논리적 주소로 Page, Offset 구해보기

논리적 주소와 페이지 오프셋이 주어졌을때, 이 주소가 몇 번째 페이지의 몇번째 오프셋인지 구해보는 예제를 살펴보자. 직접 해보길 바란다. 해답은 아래에 접은글 펼치기를 누르면 된다. 

16 bit CPU
Logical Address : 46027 = 1011001111001011(2)

1) page offset = 4 bit
2) page offset = 8 bit
3) page offset = 12 bit

 

 

이 문제로부터 알 수 있는 사실이 하나 있다. 바로 페이지 개수와 페이지 크기는 trade-off 관계라는 것이다. 페이지 개수가 너무 많으면 페이지 테이블의 크기 또한 커지므로 배보다 배꼽이 커지는 상황이 발생할 수 있다. 반대로 오프셋 크기가 너무 크면 내부 단편화가 발생할 수 있다. 내부 단편화는 다시 다루니깐 넘어가도록 하자.

4. 페이징 예제

아래와 같이 데이터가 실제로 저장되어 있는 예제다. 페이지의 데이터와 프레임 데이터는 당연히 일치해야 한다. 논리적 주소가 주어졌을때, 어떤 과정으로 물리적 주소로 매핑되는지 직접 해보자. 해답은 아래에 접은글 펼치기를 누르면 된다. 문제에서 왼쪽이 논리적 주소 공간, 오른쪽이 물리적 주소 공간이다. 

 

위 그림과 같이 Page Table Index, Offset 을 각 비트에 맞게 나누면 한 눈에 들어온다. 필기 내용 그대로 따라가면 된다. 11번지 주소만 같이 보자. 우선 논리적 주소에서 11번지에 해당하는 알파벳은 ' l ' 이다. 페이지 테이블 인덱스 값은 2고, 오프셋 값은 3이다. 따라서 Base Adderss는 4고, 여기에 오프셋을 더하면 물리적 주소는 7이 된다. 물리적 주소의 7 인덱스 값은 알파벳 ' l '이다. 따라서 옳게 찾아간 것을 알 수 있다. 

풀리지 않은 의문점

혹시 여기까지 읽으면서 '어? 이상하다?' 라고 생각한 부분은 없는지 점검할 필요가 있다. 왜냐하면 약간 말이 안 되는 부분이 있기 때문이다. 세 가지를 소개할텐데 만약에 이를 다 캐치했으면 진짜 리스펙한다. 

 

1. 빈 프레임은 누가 할당하는가?

 

우리는 아직 위 문제를 해결하지 못했다. 물리적 주소를 할당하기 전에 할당 가능한 주소를 찾는 게 선행되어야 한다. 이는 운영체제가 알아서 해주는데, free-frame list에 가용 프레임을 저장해놓고 새로운 프로세스가 생성되면 가용 프레임 주소를 페이지 테이블에 할당해준다.  '가상 메모리'파트에서 더욱 자세히 다룰 예정이다. 그림으로 보면 아래와 같다. 

 

왼쪽이 할당 전(a), 오른쪽이 할당 후(b)

 

 

2. 페이지 테이블의 물리적 주소는?

 

논리적 주소의 0번지 주소는 페이지 테이블의 0번째 인덱스를 참조할 것이다. 그러면 페이지 테이블의 0번째 인덱스는 물리적 주소의 몇번지 주소와 대응될까? 생각해보면 페이지 테이블도 메모리에 저장되어 있는 값이기 때문에 '페이지 테이블에 접근하기 위한 Base Register'도 필요하다. 이를 Page-table base register(PTBR)이라고 한다. 또한 자신의 메모리 공간의 보호를 위해 Limit Register도 필요한데, 이를 Page-table length register(PTLR)이라고 한다. 그림으로 보면 아래와 같다. 

 

정리하자면 만약에 어떤 프로세스의 세 번째 페이지(Page3)의 page number 값이 k라면, 물리적 주소에서 (k + PTBR) 주소에 있는 값이 Page3의 실제 물리적 주소다. 

 

 

3. 페이지 테이블은 연속적인데..?

 

우리가 지금까지 페이지 테이블을 신나게 다뤘지만 한 가지 간과한 게 있다. 연속 할당의 대안으로 불연속 할당이 나왔는데, 자세히 보면 페이지 테이블은 연속적이기 때문이다. 따라서 이러한 모순(?)을 해결하기 위해 페이지 테이블 구조를 새롭게 디자인할 필요가 있다. 오늘은 글이 너무 길어져서 페이지 테이블 구조는 다음 글에서 다루도록 하겠다. 오늘 좀 많은 내용을 다뤘는데 이해가 안 된다면 반복해서 읽어보기를 바란다. 내가 할 수 있는 설명은 다했다.