[운영체제] Memory Management - Paging

물리 메모리를 할당하는 방법

• Contiguous allocation
  이 방법은 프로세스를 분리하지 않고, 연속적인 공간에 적재하는 방법입니다. 메모리에는 여러 프로세스가 임의의 시간에 올라갔다 내려가기 때문에, 이 방법으로는 효율적으로 메모리를 관리하기 어렵습니다.
• Noncontiguous allocation
  위의 방법과 달리, 하나의 프로세를 적절히 나눠서 물리 메모리에 할당하는 방법입니다. 위의 방법보다 더 복잡하지만 공간을 효율적으로 사용할 수 있으며 현대의 컴퓨터는 이 방법을 사용합니다. 이 방법은 다시 크게 세 가지로 나눠집니다.
  • Paging
  • Segmentation
  • Paged Segmentation

Paging

Paging은 논리 메모리를 동일한 크기의 여러 공간(page)으로 나누고 이 페이지가 들어갈 수 있도록 물리 메모리도 같은 페이지 크기의 구획(frame)으로 나눠놓습니다. 그리고 비어있는 공간(frame)에 나눈 page를 할당하는 방법입니다.

Page Table

이때 논리 메모리의 페이지가 물리 메모리의 어디에 들어갔는지를 나타내는 것이 'Page table'입니다. 보통 페이지의 크기가 4Kb이기 때문에, 여러 프로세스 크기를 이 4kb로 나누면 백만개가 필요합니다. 따라서 CPU안에 레지스터 안에 올리지 못하고 메모리에 저장합니다.

Translation look-aside buffer(TLB)

모든 페이지 접근 연산은 2번의 메모리 접근이 필요합니다. 페이지 테이블 접근에 한번, 물리 메로리로 접근에 한번. 이 과정이 오래 걸리기 때문에 TLB라는 고속의 lookup hardware cache를 사용합니다.

이 케시는 접근이 잦은 페이지 주소를 모아서 캐시에 저장해둡니다. 그래서 먼저 TLB를 탐색하고, 발견하지 못하면 페이지 테이블을 탐색하는 식입니다.
원래의 페이지 테이블은 배열구조이기 때문에 인덱스를 통해 O(1) 속도로 찾을 수 있습니다. 반면, TLB는 잦게 요청되는 일부만 가지고 있기 때문에 인덱스를 통해 찾을 수 없고 key-value쌍으로 되어 있습니다. key에는 pageNumber가 value에는 frame number가 저장됩니다. 이를 순회하며 찾으면 오래 걸리기 떄문에, TLB는 병렬 조회가 가능합니다. 동시에 모든 공간을 탐색하는 방법으로 속도를 높였습니다.

그리고 CPU의 사용자가 다른 프로세스로 바뀌는 Context Switch 때, TLB도 같이 flush됩니다.

Two-Level Page Table

그런데 페이지 테이블의 크기가 너무나 큰 문제가 있습니다. 하나의 page가 4kb로 상당히 작으니 메모리에 올라갈 프로세스들의 크기를 4kb로 나눠도 여전히 엄청난 공간을 필요로합니다. 따라서 공간을 효율적으로 사용할 수 있는 방법이 필요하고, 그 해답이 Two-Level Page Table입니다. 서울을 여러 구로 한번 나누고, 동으로 한번 더 나눈 것입니다.

 

그럼 페이지 테이블의 크기는 얼마나 필요할까요?

우선 32bit 컴퓨터를 기준으로 설명하겠습니다. 32bit 컴퓨터라는 것은 CPU의 주소 레지스터의 최대 처리값이 32bit라는 것입니다. 그리고 1bit는 2가지를 표현할 수 있고(2^1) 10bit는 2^10가지를 표현할 수 있음으로, 32bit는 총 2^32 가지를 표현할 수있습니다. 다시 말해, 32bit 컴퓨터에서는 2^32개의 메모리 주소 값을 표현할 수 있습니다. 또한 하나의 메모리 주소는 1byte를 가지고 있습니다. 따라서 32bit컴퓨터의 메모리리는 최대 4GB (4 * 2^30 * byte)가 됩니다.

그리고 하나의 페이지 크기는 4KB이기 때문에, 1M개 (4GB / 4KB)의 page table entry가 필요합니다. 그리고 각 page table entry는 4Byte의 크기가 필요함으로, 프로세스당 4MB page table이 필요합니다. 여러 프로세스가 동시에 올라가기 때문에 더 많은 공간을 필요로 합니다.

 

Two-level Page의 이점

그런데 이 페이지 중에는 실제 프로그램이 동작할 때 쓰이지 않는 공간이 많기 때문에, 자주 쓰이는 페이지만 따로 페이지 테이블을 만들면 좋을 것 같습니다. 하지만, 페이지 테이블은 인덱스 연산을 하는 배열임으로 중간의 page entry를 임의로 제거 할 수는 없습니다. 이런 문제를 해결하는 것이 Two-Level page Table입니다.

Two-level page table은 기존의 테이블을 outer-page table과 page table 두 개로 나눕니다. 실제 물리 주소를 가리키는건 page table이고, outer-page table은 page table 안에 있는 page table의 page를 가리킵니다. 이렇게 하면서 얻는 이 점은, 잘 쓰이지 않는 페이지를 생략할 수 있다는 것입니다. page table의 page들은 한 프로세스의 모든 영역을 담고 있지 않고, 필요한 부분만을 담고 있습니다. 그리고 이것들을 가리키는 outer-page table은 모든 영역에 대한 공간을 만들지만, 모든 page table의 page를 가리키지는 않습니다. 다시 말해, outer-page table은 모든 페이지에 대해서 만들되, 쓰이지 않는 페이지는 null을 기리키도록하고 안쪽 테이블에서 생략합니다.

 

동작 과정

이것이 작동하는 순서는 다음과 같습니다. 우선 local address는 아래처럼 세가지 영역으로 나눠집니다. P1은 outer-page table의 index이고, p2는 page table의 page의 변위(시작지점부터 떨어진 거리)이고, page offset은 물리 메모리의 frame의 변위 (시작지점으로부터의 거리)입니다.
p1이 가리키는 곳을 따라가면 out-page table이 page table의 몇 번째 page 찾아가라고 가리켜줍니다. 해당 page로 도착하면 p2 더해 찾아갑니다. 그럼 여기서는 물리 주소의 frame 주소를 알려주고, 여기에서 page offset을 더해 찾고자하는 주소에 도달합니다.

참조

반효경 [운영체제] 20. Memory Management 3