[OS] Paging을 사용한 고정 크기 메모리 관리 및 추상화 - OS 공부 12

안녕하세요 Pingu입니다~

 

지난 글에서는 가변 크기로 메모리를 할당하여 사용할 때 발생하는 external fragmentation(외부 단편화)와 이를 최소화하기 위한 방법들, 여유 공간을 관리하는 방법에 대해 알아봤습니다. 이번 글에서는 가변 크기로 메모리를 사용하는 것이 아닌 고정 크기로 메모리를 사용하는 방법인 paging 방법에 대해 알아보려고 합니다. 제가 공부할 때 참고하고 있는 OSTEP 책에서는 Chapter 18 - Paging: Introduction 부분입니다!

Paging: Introduction

메모리 공간을 관리하는 방법은 두 가지가 있습니다. 하나는 지금까지 알아본 segmentation을 사용한 가변 크기를 사용하는 방법이었습니다. 하지만 메모리 할당을 가변 크기로 할당 하게 되면 외부 단편화 문제가 발생하게 됐었죠. 이 문제의 해결을 위해 이번 글에서는 또 다른 방법인 paging이라는 방법에 대해 알아보려고 합니다. Paging은 프로세스의 가상 주소 공간을 가변 크기가 아닌 고정 크기로 나누어서 메모리에 할당하는 아이디어입니다. 이때 가상공간에서 나누어진 고정 크기 단위를 page라고 합니다. 그리고 이러한 가상공간의 page를 실제 메모리에 할당하게 되는데 실제 메모리에는 이를 page frame이라는 단위로 사용합니다. 즉 가상 메모리에서는 page, 실제 메모리에서는 frame이라고 불리는 고정 크기의 공간으로 프로세스를 실행하겠다! 라는 말입니다.

A Simple Example And Oveview

그럼 Paging 방법을 이해하기 위해 간단한 예를 살펴보겠습니다.

위의 그림을 보면 프로세스의 가상주소공간 64 바이트 크기를 16바이트 4개로 쪼개 놨습니다. 여기서 쪼개진 16바이트 공간을 page라고 부릅니다.

그리고 위의 그림은 실제 메모리로 128바이트의 메모리를 16바이트 8개로 쪼개놨습니다. 이렇게 쪼개진 실제 메모리의 16 바이트 공간을 page frame이라고 부릅니다. 위의 그림은 아까 본 64바이트 크기의 프로세스의 page들을 실제 메모리에 할당한 상태를 나타낸 것인데요, 몇 개의 page frame에 프로세스의 page들이 할당되어 있는 것을 볼 수 있습니다.

 

이러한 paging 기법은 이전에 사용하던 segmentation 기법에 비해 많은 장점이 있습니다. 먼저 flexibility(유연성)이 개선됩니다. 이 말은 가변 크기 할당 방법에서는 heap, stack이 커지는 방향과 같은 메모리를 사용하는 방법을 고민했어야 했는데 고정 크기 할당 방법에서는 이를 고민할 필요가 없습니다. 또 다른 장점은 여유 공간의 단순함입니다. 지난 글에서 가변 크기 할당을 사용할 때 여유 공간을 관리하는 방법에 대해 알아봤었는데 고정 크기 할당에서는 이를 고민하지 않아도 됩니다. 그냥 프로세스 크기에 맞게 실제 메모리의 빈 frame에 할당하면 되니까요!

 

하지만 이러한 paging기법을 사용하기 위해서는 프로세스의 page들이 실제 메모리의 어디에 위치하는지를 기억하는 page table을 가지고 있어야 합니다. 아까의 예를 page table과 함께 다시 보면...

위와 같이 각 page들에 대한 실제 메모리의 위치를 기억하고 이를 활용해 주소변환 할 수 있습니다. 여기서 중요한 것은 paging을 사용한다면 모든 프로세스에 page table이 존재한다는 것입니다. 그럼 이번에는 page table을 사용해서 어떻게 주소 변환을 하는지 살펴보겠습니다.

movl <virtual address>, %eax

위와 같이 가상 주소를 eax 레지스터에 저장하는 것을 잘 살펴봐야합니다. 프로세서의 가상 주소를 변환하기 위해서는 virtual page number(VPN)와 page의 offset이라는 두 가지를 알아야 합니다. 위의 예에서는 가상 주소의 크기가 64바이트이므로 가상 주소를 나타내는데 필요한 비트 수는 6입니다. 따라서 6비트를 다음과 같이 표현할 수 있습니다.

위와 같이 나타낸 6비트에서 VPN, offset을 구분해야 하므로 비트를 구분하면 아래와 같아집니다.

아까 예에서는 64바이트 크기의 가상공간을 16바이트의 page로 나눠 사용했으니 총 4개의 page가 사용될 수 있습니다. 4개의 page를 구분하기위해 상위 2비트에 저장하는 것이죠. 그리고 하위 4비트에는 offset는 각 page의 자세한 위치를 알려줍니다. 여기서는 page의 크기가 16바이트였으니 2^4 = 16이므로 4비트가 offset으로 사용되는 것이죠. 그럼 위의 예에서 21이라는 가상 주소를 변환해보겠습니다.

movl 21, %eax

21은 2진수로 표현하면 010101입니다. 이를 그림으로 나타내면..

이렇게 나타나게 되고 이를 해석하면 가상 주소 21은 가상 page 01 인덱스에 존재하는 page의 5바이트를 가리키는 것입니다. page table의 01인덱스에는 실제 메모리에서 physical frame number가 저장되어 있는데 여기서는 7이네요. 그럼 이제 이 정보를 사용하여 physical frame number(PFN)으로 변환하면 실제 메모리의 주소를 얻을 수 있습니다.

아까 예에서 실제 메모리의 크기는 128바이트 였습니다. 따라서 필요한 실제 메모리를 나타내는데 필요한 비트 수는 7이고 아까 page table을 보니 page 01 인덱스는 PFN 7이었습니다. 이렇게 VPN -> PFN으로 변환해주고 offset은 그대로 사용하면 됩니다. 그럼 위와 같이 실제 메모리 주소는 1110101이 됩니다.

 

Paging 기법을 사용할 때 주소변환이 어떻게 수행되는지 이해하셨나요? 그럼 이제 page table은 어디에 저장되는지 여기에는 어떤 정보가 들어있는지가 궁금하지 않나요? 그리고 지금 변환 과정이 뭔가 긴거같은데 성능이 저하되지 않는지도 궁금할 것 같습니다. 물론 안 궁금하시더라도... 계속 읽어주세요ㅠ.ㅠ

Where Are Page Tables Stored?

그럼 이제 page table이 어디에 저장되는지 살펴보겠습니다. 우선 page table은 가변 크기 할당에서 사용하던 segment table이나 base, limit 레지스터를 사용하는 것 보다 필요한 크기가 훨씬 커질 수 있습니다. 예를 들어 4KB page를 갖는 32 비트의 가상 주소 공간을 생각해보겠습니다. 이 가상 주소는 20비트의 VPN, 12비트의 offset으로 분할됩니다. VPN이 20개의 비트로 표현된다라는 말은 OS가 각 프로세스에 대해 관리해야 하는 page수가 100만 개 정도 된다는 것입니다. 또한 하나의 page의 정보를 저장하기 위한 page table의 크기가 4바이트라고 한다면 4바이트 * 100만 = 4MB입니다. 이러한 프로세스가 100개라면... 400MB의 메모리를 필요로 하게 됩니다. 이를 CPU의 레지스터에 저장한다는 것은 불가능하므로 page table은 메모리에 저장하게 된다고 일단 생각하겠습니다. 실제로는 메모리에 저장되는 것이 아닙니다.  나중에 OS가 사용하는 메모리가 가상화될 수 있다는 것을 알게 되는데요, page table은 OS 가상 메모리에 저장됩니다. 또한 디스크로 swap 될 수도 있습니다. 

What's Actually In The Page Table?

Page table이 어디에 저장되는지 알았으니 그럼 이번에는 page table에는 어떤 정보가 저장되는지 살펴보겠습니다. Page table의 역할은 가상 주소를 실제 메모리 주소로 변환해줄 때 사용하는 자료구조입니다. 이를 위한 가장 간단한 구조는 1차원 배열을 사용하는 것입니다. VPN으로 해당 프로세스의 page table 배열을 인덱싱하고 변환을 위해 해당 인덱스의 page table entry(PTE)를 조회합니다. 여기서 PTE는 page table에서 각 page의 정보라고 생각하면 됩니다. PTE의 구조는 아래와 같습니다.

0번 인덱스 부터 살펴보겠습니다.

• P : 현재 실제 메모리나 디스크에 존재하는 page인지 확인하는 비트
• R/W : page가 쓰기가 허용되는지 여부를 결정하는 비트
• U/S : User Mode 프로세스가 page에 접근할 수 있는지에 대한 비트
• PWT, PCD, PAT, G : page에 대해 하드웨어 캐싱이 작동하는 방식을 결정하는 비트
• A : 최근 참조된 적이 있는지에 대한 정보 (페이지 교체 정책에서 사용됨)
• D : page가 수정된 적이 있는지에 대한 정보

그리고 나머지는 page frame number로 구성됩니다.

Paging: Also Too Slow

지금까지 알아본 page를 사용하는 방법은 어떤가요? 뭔가 메모리 사용도 많이 하고 변환도 기존 방법보다 복잡하지 않나요? 이러한 형태로 수행되기 때문에 paging방법은 느립니다. 예를 들어서 paging이 느린 이유를 자세히 살펴보겠습니다. 

movl 21, %eax

위의 예는 아까도 살펴본 가상 주소 21을 변환하는 예입니다. 지금 원하는 것은 가상 주소 21을 아까 구한 실제 메모리 주소인 117로 변환하는 것입니다. 이 과정을 살펴보면

1. 프로세스의 page table을 살펴봅니다.
2. Page table의 정보를 통해 주소 변환을 합니다.
3. 실제 메모리에서 데이터를 가져옵니다.

위와 같은 과정을 위해서 하드웨어는 현재 실행중인 프로세스에 대한 page table위치를 알아야 합니다. 먼저 프로세스의 가상 주소로 VPN(virtual page number)과 offset을 알아냅니다. 그런 뒤 해당 프로세스의 VPN값으로 page table에서 프로세스의 PTE정보를 가지고 옵니다. 가지고 온 PTE(page table entry) 정보에서 PFN(page frame number)을 추출하고 offset, PFN을 사용하여 실제 메모리 주소를 얻습니다. 이 과정은 아래와 같습니다. 

// 가상 주소에서 vpn만 추출한다.
VPN = (VirtualAddress & VPN_MASK) >> SHIFT

// Page table 주소에 vpn 값으로 현재 접근하는 프로세스의 PTE 찾는다.
PTEAddr = PageTableBaseRegister + (VPN * sizeof(PTE))

// 가상 주소에서 offset만 추출한다.
offset = VirtualAddress & OFFSET_MASK

// offset과 PFN 값으로 실제 메모리 주소를 얻는다.
PhysAddr = (PFN << SHIFT) | offset

이렇게 얻어진 실제 메모리 주소의 데이터를 %eax 레지스터에 넣으면 드디어 메모리에서 값을 가져오는 데 성공하는 것입니다. 어떤가요? 복잡하지 않나요.. 이를 수행하면 메모리에서 데이터를 가지고 오는데 메모리를 한 번 참조하는 것이 아닌 두 번 참조하게 되고 성능도 그만큼 저하되게 됩니다. 즉 성능 저하라는 문제가 발생하게 되죠. Paging 방법을 사용하는 것은 메모리 가상화를 위한 좋은 방법처럼 보이지만 성능도 안 좋고 메모리도 많이 사용하는 방법인 것입니다. 즉 이를 극복해야 실제로 사용할 수 있습니다.

A Memory Trace

그럼 paging의 메모리 사용 과정을 다시 한번 보며 어떻게 메모리에 접근하는지 살펴보겠습니다. 우선 간단하게 정수형 배열을 만들고 배열의 모든 요소를 초기화 하는 예로 이 과정을 살펴보겠습니다.

int array[1000];

for(int i = 0; i < 1000; i++) {
    array[i] = 0;
}

이 과정중 한 번의 반복을 어셈블리로 나타내면 아래와 같습니다.

가상주소 
1024   movl  $0x0, (%edi, %eax, 4) 
1028   incl  %eax
1032   cmpl  $0x03e8, %eax
1036   jne   0x1024

이를 설명하면 우선 0x0위치로 이동합니다. 여기서 (%edi, %ead, 4)의 의미는 %edi는 배열의 시작 주소입니다. %eax는 인덱스 값 아까 C언어 코드에서는 i에 해당하는 값이죠. 그리고 4는 정수형 배열이므로 인덱스당 4바이트만큼을 사용한다는 뜻입니다. 그다음 줄인 incl은 %eax의 값을 증가시키는 명령이고 그다음 줄의 cmpl은 i < 1000 부분을 처리하는 곳이죠. 여기서 true가 발생하면 jne명령에 의해 다시 1024로 이동하여 반복을 수행하게 됩니다.

 

그럼 이 예를 직접 수행해보겠습니다. 이 때 프로세스의 가상 주소는 64KB이고 page 크기는 1KB라고 가정해보겠습니다. 수행하기 위해 알아야 할 것은 page table의 내용과 실제 메모리의 주소입니다.

 

VPN 1페이지에 Code에 대한 정보가 있고 이는 PFN 4로 연결된다고 가정하겠습니다. 또한 array의 VPN은 39, 40, 41, 42라고 가정하고 각각의 PFN은 7,8,9,10이라고 가정하겠습니다.

그럼 위와 같은 구조로 주소변환이 이뤄지게 됩니다. 그럼 이제 메모리접근을 추적해보겠습니다. 코드가 실행될 때 명령어 fetch는 두 개의 메모리 참조를 생성합니다. 하나는 page table에 관한 것이고 하나는 명령어 자체에 관한 것이죠.

위의 그림은 1000번의 반복 중 5번의 반복의 메모리 접근을 나타낸 그림입니다. 한 번의 반복이 아까 어셈블리로 나타내면 4줄의 어셈블리 코드로 나타났었죠? 이를 통해 우선 4번의 메모리 접근이 발생합니다. 한 번의 반복이 진행될 때 코드 부분의 page에는 4번의 메모리 접근, 1번 Array 메모리에 접근해서 업데이트, 그리고 5번의 page table 접근이 발생합니다. 즉 한 번의 반복을 위해서 10번의 메모리 접근이 발생하는 것이죠. 이런 간단한 반복 한 번을 수행하기 위해 이렇게 복잡한 과정이 수행되는 것입니다. 이를 최적화하는 방법은 없을까요?

Summary

이번 글에서는 메모리 가상화를 하기 위하여 고정 크기 할당 방법인 paging에 대해 알아봤습니다. Paging은 가변 크기 할당 방법인 segmentation에 비해 장점들이 몇 가지 있었습니다. 첫 번째는 외부 단편화가 해결되었고, 두 번째는 유연성 이었습니다. 메모리 여유 공간을 사용하는 방법과 같은 문제들을 생각할 필요가 없었죠.

 

하지만 paging을 아무렇게나 사용한다면 메모리 접근이 너무 잦아져서 성능 저하가 발생했으며 page table을 위한 메모리도 할당해줘야 하므로 메모리 낭비도 발생했습니다. 따라서 다음글에서는 이러한 문제들을 보완하는 방법들을 알아보겠습니다!

 

감사합니다.