Paging

오늘날 사용되는 가상 메모리 기법

Created Apr 22, 2024 - Last updated: Apr 22, 2024

들어가며

지난 번에는 virtual memory에서 virtual memory의 필요성과 구현 방법에 대해서 알아보았었습니다.

static relocation과 dynamic relocation에 대해 알아보고, dynamic relocation의 구현 방법인 Fixed partition, segmentation에 대해서 알아보았었죠.

그렇지만 segmentation 기법 역시 단점이 있었기에 이번 글에서는 오늘날 사용되는 paging 기법을 소개해 드리려고 합니다.

Paging기법은 간단하게는 segmentaton 기법을 더 쪼갰다고 생각하면 됩니다. segmentation에서는 segment 단위로 프로세스에게 메모리를 주었지만 Paging은 page 단위로 메모리를 주는 것입니다.

그리고 간단하게 용어를 정리하자면, page와 frame이라는 단어가 많이 쓰일 것인데 page는 가상 메모리를 이루는 단위, frame은 물리 메모리를 이루는 단위입니다.

이 둘은 512B ~ 8KB사이의 크기를 가지는데 보통은 4KB입니다.

Segmentation에서 segment 표가 있었듯이 Paging기법에서는 page를 frame으로 바꾸기 위한 page table이 존재합니다. 그리고 이 page table은 프로세스 당 하나씩 가지고 있죠.

이런 paging 기법을 위해서 viratual address는 어떻게 구성되어있나 살펴보겠습니다.

virtual address는 VPN(Virtual Page Number)와 offset으로 이루어져있습니다.

VPN은 page table의 몇번째 page를 가리키는지를 의미합니다. 그러므로 vpn을 통해 특정 page를 가리키면, 그 page는 page table을 통해서 PFN(Page Frame Number)로 변환되게 됩니다.

PFN은 실제 메모리 주소를 의미하는데, PFN에 offset을 더해 메모리의 원하는 지점에 접근할 수 있는 것입니다.

한편 아까 page나 frame의 사이즈는 보통 4KB라고 하였으니 offset은 12bit로 이루어져있습니다. 2^12 = 4096이니까요.

그렇기에 64비트 시스템의 경우 VPN은 보통 52bit로 이루어져있고, 그 중 페이지를 가리키는데 사용하는 bit의 수는 대략 40개입니다. 나머지 bit는 추후 보겠지만 protection bit 등으로 쓰이게됩니다.

이렇게 virtual address를 운영할 때 중요한 것은 한 프로세스가 다른 프로세스의 영역을 침범하지않도록 보호하는 것일 것입니다.

이러한 protection은 두 가지 방식을 통해서 일어나게 됩니다.

하나는 satp라는 레지스터가 있어서, 현재 돌아가는 프로세스의 페이지 테이블을 가리키고 있습니다.

그러므로 다른 프로세스의 페이지 테이블을 이용할 일이 없습니다.

또 하나는 PTE(Page table entry), 즉 페이지 테이블의 각각의 항목에 몇 개의 비트를 flag처럼 사용하여 protection을 완성합니다.

그 예시로 PTE는 아래와 같이 생겼고, PFN 앞에 여러 비트들이 있습니다.

한편 프로세스가 돌아갈 때 그 프로세스가 사용하는 모든 page가 실제로 메모리가 올라가있지는 않습니다.

메모리 관리의 효율성을 위해 page들의 일부분만 메모리에 올라와있고, 만약 올라와있지않은 page에 대한 요청이 들어오면 page fault라는 것을 내서, 해당 page를 메모리에 로드한 후, 기존의 동작을 이어가게 됩니다.

여기서 Page fault란 cpu가 invalid PTE에 접근할 때 발생하는 exception입니다.

invalid PTE란 invalid bit가 켜져있는 PTE인데 여기에 접근하면 page fault가 나게되는 것이죠.

이 때 page fault는 두 가지 종류로 나뉩니다.

하나는 Major page fault이고, 하나는 Minor page fault입니다.

Major page fault란 invalid 표시가 되어있지만 실제론 valid한 경우로, 디스크에 페이지가 내려가있는 경우입니다.

이 경우엔 디스크에서 페이지를 다시 메모리로 로드하는 방식으로 fault를 해결합니다.

Minor page fault는 malloc 같은 것을 한후 heap access를 했는데 lazy allocation으로 인해 아직 heap이 할당되지않은 상태로, 따로 I/O없이 바로 os가 해결해줄 수 있는 page fault입니다.

Page fault가 발생했을 때 해결되는 전체적인 과정을 아래와 같습니다.

trap은 간단하게는 exception, illegal instruction 등을 포함하는 말인데 xv6 trap을 참고해보시면 좋을 것 같습니다.

dynamic relocation의 마지막 방법인 Paging기법은 어떤 장단점을 가지고 있을까요?

우선 장점으로는 external fragmentation이 없고, 할당과 해제가 빠르다는 장점이 있습니다.

또 특정 부분을 쉐어하고 공유하기가 매우 편하죠.

하지만 단점으로는 메모리에 접근하기 위한 오버헤드가 커지고, page table을 위한 추가 공간이 필요하다는 문제점이 있습니다.

이렇게 모든 virtual memory의 구현 방법에 대해 알아보았는데, 각각의 장단점과 그로 인한 발전 방향을 살펴보시면 도움이 될 것 같습니다.