Memory Management 2 - Paging

  저번 글에서 메모리 관리를 위해 사용하는 방법에 대해서 알아봤다. dynamic relocation의 방법 중 fixed/variable partitions와 segmentation에 대해 알아봤었는데 paging이라는 방법도 있다고 했다. 이 방법은 셋 중 가장 보편적으로 사용되는 방법이고 내용도 상대적으로 많기 때문에 이 글에서 따로 다뤄볼 생각이다.

Structure of Virtual Memory

  paging에 대해 알아보기 전에 우선 가상메모리가 어떤 식으로 구성되는지 간단히 알아보자. 

fig 1

  가상 메모리는 각각의 프로세스에게 굉장히 많은 메모리 공간이 있는 것처럼 보이게 한다고 했다. 이러한 가상 메모리 공간의 크기는 어떻게 될까 컴퓨터 OS, 프로그램 등을 설치할 때 32bit/64bit로 버전이 나눠져 있는 것을 볼 수 있다. 여기서 32bit라는 것은 2^32bit(4GB) 크기만큼의 메모리 공간을 인식할 수 있다는 뜻이기도 하다. 그렇다면 64bit는 2^64bit(매우 크다)만큼의 메모리 주소를 가리킬 수 있다는 뜻 임을 알 수 있다. 이렇게 큰 크기의 가상 메모리의 가상 주소를 physical memory address로 변환하기 위해 fixed/variable partitions, segmentation 등의 방법을 사용하는 것이고 이 글에서는 paging이라는 방법에 대해 자세히 알아볼 것 이다.

 

Paging

  paging은 segmentation보다 개선된 방법이니 segmentation의 문제점을 해결해야 한다. segmentation의 주요 문제점은 segment가 클 수 있기 때문에 external fragmentation이 심해질 수 있다는 것이다. 이를 해결하는 paging은 프로세스의 physical address space를 비연속적으로 만든다. 즉 동일한 세그먼트의 데이터들을 메모리 상에서 떨어뜨릴 수 있는 것이다.

 이 방법에서는 가상 메모리를 고정된 크기로 나누는데 각각을 page라고 한다. 그리고 실제 메모리도 동일한 사이즈로 나누는데 각각을 frame(page라고 해도 됨)라고 한다. 그리고 이 page의 사이즈는 2의 거듭제곱이다. 우리가 흔히 쓰는 컴퓨터의 page 크기는 대부분 4KB이다. OS는 free 상태의 frame들을 추적하고 있다가 어떤 프로그램이 n개의 page를 필요로 한다면 n개의 free frame을 요청하고 거기에 프로그램을 로드한다. 그리고 page table을 설정하여 가상 주소를 실제 물리적 주소로 변환해줘야 한다.

fig 2

  fig 2를 보자. 프로세스 A, B가 각각 가상 메모리에 연속적으로 위치되어 있다. 만약 32bit 시스템이라면 각 프로세스마다 '0~2^32-1'(4GB)의 가상 주소 공간을 가질 수 있고 '2^32 / 2^12 = 2^20'개의 page를 가질 수 있다. 그리고 각각의 page를 page table에 넣고 돌려보면 오른쪽 처럼 실제 메모리에서는 각 프로세스의 frame(page)가 비연속적으로 위치한 것을 확인할 수 있다.

  그리고 확인할 수 있는 것은 프로세스의 수만큼 page table을 가져야 한다는 것이다. 그 이유는 프로세스마다 동일한 가상 주소 값을 가질 수 있기 때문이다. fig 2에서 각 프로세스가 0번 page를 가질 수 있는 것 처럼 말이다. 하지만 가상 주소가 같아도 실제 메모리 주소는 서로 다르게 맵핑되어야 하기 때문에 프로세스마다 각각의 page table을 가져야한다. OS에 메모리 공간을 요청하면, OS는 '가상 메모리의 page n에 메모리를 할당하려고 하네? 그럼 내가 frame m을 줄테니깐 page table에 n->m을 기록해놔.'라고 생각한다고 보면 된다.

  예를 들어 page 4에 접근한다고 하자. 이때 page table의 [4]인덱스를 확인해보니 5였으니 frame 5로 이동해야겠다고 생각할 수 있다. 그런데 page table 역시 메모리에 위치해야한다(레지스터에 넣기에는 큰 크기이니) 이런 page table의 시작주소는 OS가 가상 주소 공간을 만들면서 page table을 만들 때 알 수 있다. 이 주소를 PCB에 기록한 다음 context switcing이 일어날 때마다 이를 읽어와서 cpu의 register에 설정해준다. 

 

Address Translation

  가상 주소에서 실제 주소를 찾아내느 과정을 더 자세히 알아보자. 우선 가상 주소를 <VPN(Virtual Page Number), Offset>으로 쪼갠다. 예를 들어 page 크기가 4KB인 32bit 시스템 기준으로 0x0000 0000 ~ 0x0000 0FFF는 page 0의 주소임을 알 수 있다. 즉 상위 5자리수로 몇 번 page인지 구분하고 하위 3자리수로 page내 byte의 정확한 위치를 특정할 수 있는 것이다.

  page내에서의 데이터 위치는 주소 변환 뒤에도 변함이 없으니 Offset값에는 변함이 없을 것이다. 그러므로 실제 주소는 <PFN(Physical Frame Number), Offset>으로 구성되니, VPN만 PFN로 변환시켜주면 된다. 보통 가상 공간이 더 넓은 주소 공간을 가지게 되므로 대부분 VPN의 크기는 PFN보다 크다.

  이 때문에 page table을 두는 것이고 이것은 VPN을 입력으로 주면 PFN을 알 수 있게 한다. 이말은 가상 주소공간의 하나의 page마다 하나의 PTE(Page Table Entry)를 가져야 한다는 뜻이기도 하다.

fig 3

  fig 3를 통해 다시 정리하자면, CPU가 logical(virtual) 주소를 통해 메모리에 접근하려면 page table을 통해 실제 주소로 변환하여 메모리에 접근해야한다. 여기서 displacement(offset)은 그대로지만 page table을 통해 p->f를 얻어서 'f에서 d만큼 떨어진 곳에 접근하면 되겠구나'라는 과정을 통해 주소를 변환할 수 있다. 

fig 4

  fig 4를 보자. 0xFFA8AFDC를 0xFFA8A FDC로 나눌 수 있다. 0xFFA8A를 10진수로 변환하면 '101478'이고 page table base register를 통해 page table의 시작주소를 알 수 있다. 여기서 101478만큼 떨어진 곳에 접근하면  PFN인 '003A0'을 알 수 있다. 이것을 offset인 FDC와 붙이면 실제주소 '0x003A0FDC'를 얻을 수 있게 된다.

 

Page-level Access Control (Protection)

fig 5

  위와 같은 작업이 page단위로 이뤄지기 때문에 protection의 컨트롤을 페이지마다 설정해 줄 수 있다. 예를 들어 system page들은 관리자 권한을 가졌을 때만 접근 가능하게 하는 것 등이 가능해진다. 이러한 정보들은 fig 5처럼 PTE(Page Table Entry)에 같이 넣어준다. 그러므로 fig 3처럼 page table에 접근할 때, 접근 관련 정보를 통해 다른 프로세스의 주소 공간에 접근하려고 한다거나, 읽기/쓰기 권한이 없는 경우에는 page fault를 발생시켜 줄 수 있다. fig 5의 각 필드의 정보는 다음과 같다.

• V(Vaild): 해당 PTE가 현재 사용되고 있는지
• R(Reference): 해당 페이지가 참조된 적이 있는지
• M(Modify): 해당 페이지가 변경된 적이 있는지
• P(Protection): Read/Write/Excute 등의 권한에 대한 정보
• PFN: PFN을 결정

 

Demanding Paging

  프로그램의 크기가 클 때 접근하려는 코드나 데이터가 메모리에 없고 스토리지에 있을 수 있다. 이 스토리지에 있는 코드나 데이터를 가져오는 것이 바로 Demanding paging이다. 무슨 말이냐면 일단 프로세스가 가상 메모리에 올려졌을 때 현대의 컴퓨터에서는 프로그램 전체가 메모리에 올라와지는 게 아니라는 것이다(간단한 프로그램은 당연히 한번에 올려지겠지만). 대신 필요한 코드나 데이터가 있으면 page 단위로 스토리지에서 메모리로 불러온다.

  그렇기 때문에 가상 메모리의 해당 페이지가 실제 메모리에 있는지 스토리지에 있는지 나타낼 필요가 있다. 그래서 fig 5의 valid bit를 이용한다. 가상 주소에 접근해서 주소를 물리적 주소로 변환하려고 할 때 vaild bit가 설정되어 있지 않으면 접근하려고 하는 데이터가 현재 메모리에 없으니 현재 주소 변환을 할 수 없음을 인지하고 HW가 page fault를 발생시킨다. 이를 OS가 받아서 필요로 하는 데이터를 스토리지에서 메모리의 physical page로 가져오게 된다. 

fig 6

  fig 6을 보자. 가상 메모리에 데이터들이 불려와져 있는데 실제 메모리에는 A, C, F 데이터만 올라와져 사용되고 있는 상태이다. 그래서 page table에서도 A, C, F 인덱스의 엔트리만 valid하다. 그렇기 때문에 이외의 엔트리의 PFN은 현재 메모리에 올라와있는 상태가 아니기에 비어져 있다. 이후 프로그램이 실행되면서 H에 접근한 이후의 동작은 다음과 같다.

• PC는 H의 가상 주소를 가리키게 될 거고 이 주소를 가지고 page table을 살펴본다.
• 7번 엔트리를 살펴보니 PFN가 없는 상태이니 HW가 page fault를 발생시킨다.
• 이것을 OS가 받아서 왜 fault가 발생했는지 살펴본 뒤, 7번 엔트리의 vaild bit가 invalid해서 fault가 발생한 것을 인지한다.
• 스토리지에 있는 H라는 데이터를 physical memory의 빈공간에 가져온다.
• 해당 공간의 주소를 page table 7번 엔트리 PFN에 넣어준 뒤, vaild bit를 valid하게 변경한다.
• 이러한 fault handling을 끝내고 다시 OS가 HW한테 fault가 발생했던 지점부터 다시 실행하라고 명령한다.
• 이제는 page table을 통해 physical memory에 있는 H 데이터에 접근하는 것이 가능하다.

Page In & Out

fig 7

  위와 같은 과정을 Page In&Out이라고도 한다. fig 7을 보면 프로그램 A에 해당하는 page들을 스토리지에 넣고, 프로그램 B가 필요로 하는 전체 페이지를 메인 메모리로 가져오는 경우에 대해서 보여주고 있다.

  정리하자면 Demanding paging을 통해서, 프로그램을 page 단위로 잘게 쪼개서 해당 프로그램이 physical memory보다 크더라도 수행될 수 있는 구조를 가지게 되고, 프로그램을 실행할 때 모든 코드나 데이터를 메모리에 가져오는 것이 아니라 필요할 때 메모리에 올릴 수 있게끔 할 수 있다. 예를 들어 파워포인트를 실행할 때 애니메이션 효과를 추가했다고 하면, 이 기능에 대한 코드는 메모리에 안 올라왔을 수 있다. 이 기능에 접근하게 되면 page fault가 발생하게 되고 스토리지에서 해당 기능에 관한 것만 메모리에 올려서 해당 기능을 다시 실행할 수 있는 것이다.

 

Physical Memory as a Cache

  정확히 기억은 안나지만 '컴퓨터 구조'에서 처리속도가 CPU>Memory>Storage 순으로 빠르다고 했었다. 그렇기 때문에 메모리에 자주 사용되는 데이터를 CPU의 L1/L2 cache 같은 곳에 따로 저장하여 메모리의 접근을 줄였었다. 이 관계는 (physical)Memory와 Storage에서도 적용이 가능하다. 즉 메모리를 디스크에 있는 page들에 대한 캐시라고 볼 수 있는 것이다. 그렇기 때문에 기존 캐시에서 다뤘던 issue들을 여기서도 가질 수 있다.

• Placement: 어디에/어떻게 메모리의 page를 위치/탐색하는가?
• Replacement: 메모리에 공간을 만들 때는 어떤 page가 삭제되어야 하는가?
• Granularity of mamagement: page는 large/small/uniform 중 어떤 형태를 가져야 하는가?
• Write policy: write through or write back

 

Supporting Virtual Memory

  앞선 내용을 통해 가상 메모리는 SW와 HW의 도움을 동시에 필요로 하는 것을 알 수 있다. 각 프로세스마다 가지는 page table은 physical memory에 위치한다. 그러므로 page table에 접근한다는 것은 메모리에 한번은 접근해야 한다는 것인데, 실제로 데이터에 접근한다는 것은 page table에 한번, 실제 데이터가 있는 곳에 한번해서 두번의 메모리 접근을 필요로 한다.

  이렇게 두 번의 메모리 접근을 한번에 해주기 위해서 TLBs라는 것을 이용해 HW적인 도움을 받는데, 이는 VA(Virture Address)에 대한 PA(Physical Address)의 정보를 담고 있어서 VA가 들어왔을 때 page table에 접근하는 것이 아니고 TLBs를 통해 바로 PA로 접근하는 것이다. 이러한 TLBs는 CPU에 위치하였기 때문에 page table에 접근하여 PA를 알아내는 과정은 CPU에서 이뤄지고 PA의 데이터에 접근할 때에만 때에만 메모리를 참조하면 되는 것이다.

  이러한 것들을 담당하는 HW를 MMU(Memory Management Unit)이라고 한다. 이 안에 TLBs, page table base registers, page walkers가 포함되어 있다. page table register는 메모리에 있는 page table의 시작주소가 담기는 register이다. 이를 이용하여 page table에 접근할 수 있다. VA를 PA로 변환하기 위해 page table을 확인할 때 메모리에 있는 page table을 확인하고 valid하지 않으면 fault를 발생시킨다고 했다. 이러한 과정을 'page table을 걷는다'라고 표현하기 때문에 이 역할하는 것을 page walker라고 한다.

  OS는 이러한 MMU를 활용하여 어떤 프로세스에 대한 page table을 만들고 이것이 어디에 위치해야 할지 정하고 context switching이 일어날 때마다 page table register를 바꿔주고 page fault를 처리하는 등의 역할을 해야한다.

 

Some OS Jobs for VM

  VM에서 OS의 역할에 대해 정리하자면 우선 frame이 free한 상태인지를 추적한 다음 frame을 page에 할당해주고 만약 이용가능한 physical page가 없다고 했을 때, 어떤 것들을 메모리 밖으로 내보내야 하는지 판단해야 한다. 그리고 프로세스간 page를 공유할 때 최적화도 해줘야 할 것이다. 몇 가지 경우에 대한 OS의 동작을 알아보자.

Page Fault: A Miss in Physical Memory

 page fault는 physical memory에 접근하고자하는 page가 없어서 발생한다고 했다. 그리고 이외에도 protection 관련해서(ex. 쓰기 권한이 없는데 쓰려고 함) page fault가 발생하기도 한다.

fig 8

fig 9

  fig 8을 보자. falut 발생 전 상황에서 CPU가 접근하려는 VA의 page에 해당하는 frame이 Disk에 있다. 이때 CPU가 page table에 접근하는 순간 demand page fault가 발생할거고, 이때 OS가 메모리를 할당받아서 맵핑 정보를 설정하게 된다. fig 9을 살펴보면 과정을 이해할 수 있을 것이다.

 

Shared Memory

  Shared Memory는 여러 프로세스가 데이터를 공유할 수 있게 해주는 것이다. 각 프로세스는 각자의 page table을 가지고 있는데 이때 서로 다른 프로세스가 같은 frame을 가리키도록 한다는 것이다. 이 경우에는 각자가 다른 protection value를 가지고 있고, 만약 frame이 invalid 된다면 이를 참조하는 PTEs를 모두 업데이트 해줘야 한다.

fig 10

  stdio 라이브러리를 많은 프로세스가 사용하지만 하나만 메모리에 올라와 있으면 프로세스들이 이것을 공유해서 사용할 수 있는 것이 shared memory의 예시라고 할 수 있겠다.

 

Copy-on-Write

  copy-on-write이란 copy를 write가 필요한 시점까지 지연시키는 것이다. page를 copy하는 대신에 공유가 되게끔 같은 page frame들을 만들어 놓는다. 이것을 같이 쓰다가 어떤 프로세스가 write를 하여 공유되고 있는 page frame들이 분리될 필요가 있을 때 copy를 수행하는 것이다.

  예를 들어 fork()를 생각해보자. 이것이 수행되면 부모 프로세스에 있는 자원을 자식 프로세스가 받아온다. 이때 copy가 발생하는데 이 말은 겹치는 데이터를 공유한다는 것이 아니라 각자의 copy를 가진다는 것이다. 반면 쓰레드가 생성될 때는 heap이나 data가 공유가 되니깐 copy가 있는 것이 아니라 하나를 공유하는 것이다. 

fig 11. fork()

  fork()시 처음에는 자식 프로세스는 부모 프로세스의 자원을 공유하기 때문에 자원이 동일한 physical memory의 같은 곳을 가리키고 있다. 이후 자식 프로세스의 데이터에 새로운 내용이 쓰이게 되면 이때 copy가 발생하여 복사본이 만들어지는 것이다. 모든 자원에 대해 복사본을 가지고 있을 필요는 없기 때문에 이처럼 최대한 lazy하게 copy를 수행하게 된다.

  기본적으로 공유 page들은 읽기 전용으로 보호되고 있는 상태이다. 그 상태에서 자식 프로세스가 이를 변경하려고 접근하게 되면 page fault가 발생하게 되고 이에 대한 handling으로 복사본이 생성되는 것이라 이해하면 될 것 같다.

 

Three Major Issue

  앞으로 다뤄볼 문제들에 대해 설명하고 이 글은 여기서 마친다.

• 큰 사이즈의 page table을 어떻게 저장하고 접근할 것인지
• translation, access control의 과정을 어떻게 더 빠르게 할 것인지
• 얻어낸 PA를 통해 cahce에 접근하는데 오랜 시간이 소요됨

---

• Operating System Concepts, Avi Silberschatz et al.
• Operating Systems: Three Easy Pieces
  • Remzi H.Arpaci-Dusseau andAndreaC.Arpaci-Dusseau
  • Available(withseveraloptions)athttp://ostep.org