PINTOS (3) Virtual Memory

Project 3 - Virtual Memory

100개 가까운 테스트를 통과하고 Project3 - Virtual Memory에 도달하여 매우 기쁘지만, 아래와 같은 문구가 Project 3에서 우릴 기다리고 있다. 이제까지 제대로 만들었길 기도하자. (이번에도 도대체 뭐하라는거야 가 기다리고 있으니 너무 기대하지 말자.)

 

"You should take care to fix any bugs in your project 2 submission before you start work on project 3, because those bugs will most likely cause the same problems in project 3." 

 

간략한 과제 내용은 아래와 같다.

 

0. 프로그램을 실행하려면, 실행에 필요한 데이터(Ex : Code)를 물리메모리(RAM)에 올려야 한다. 지금은 실행 전에 load(), load_segment()라는 함수에서 실행에 필요한 모든 데이터를 물리메모리에 올려버리고 있다. 이 방식은 매우 비효율적이므로, 모든 데이터를 다 올리는 대신에 실행 중에 해당 데이터가 필요하게 되면 그 때 물리메모리에 올리는 방식으로 변경하자.(Lazy Load)

 

1. 현재 스택은 한개의 Page만 할당되어 있고, 한 Page 이상의 데이터를 저장하는 경우는 고려되지 않았다. 한 Page를 넘는 데이터를 저장하더라도 유동적으로 늘릴 수 있도록 변경하라.(Stack Growth)

 

2. 프로그램을 많이 실행하거나, 많은 데이터를 저장하다보면 물리메모리가 가득 차서 무언가를 빼내야 하는 상황이 발생한다. 이를 고려하여 임시로 저장하는 공간인 Swap Disk를 만들고 빼낸 데이터는 잠시 이 곳에 넣어두기로 한다. Swap Disk는 갈 곳이 없는 것들만 넣어두는 것이고, File에서 불러온 데이터는 다시 File에 쓰면 된다. 

 

Project 3 - 개념

Project 3을 진행하기 위해서는 아래의 내용들을 이해해야 한다.

 

우선 전체적인 그림을 한번 알아보자.

 

  Pintos 내에서 생성되는 모든 Thread는 각자 독립된 가상주소공간(0 ~ KERN_BASE)을 가진다.  KERN_BASE가 0x8004000000이므로, 각 프로세스는 550Giga Byte의 주소공간을 표현할 수 있다.(하지만 실제로 사용되는 공간은 매우 작다.) 각자의 Thread가 KERN_BASE 이하의 특정 주소의 데이터를 읽으려고 하면, Thread에 저장되어있는 Page Table에서 이 주소를 실제 물리 주소로 변경한 뒤 실제 물리주소에서 데이터를 읽어오게 된다.

 

0) Virtual Address

  위에서 말한 가상주소공간은 Thread별로 할당된 것이며, 각각의 Thread는 이 가상주소공간만큼의 크기를 모두 쓸 수 있을 것만 같은 착각을 가진다. 하지만 사용자가 0x400000에 data를 Write하라고 명령을 내리더라도, Thread는 이 주소를 실제 물리주소로 변환한 뒤에 그곳에 Write한다. 이렇게 함으로써 OS는 사용자가 만든 Thread가 실수를 하더라도 다른 Thread의 공간을 침범하는 것을 막을 수 있다.

 

1) Page

  가상 공간의 Data에 대한  정보를 저장하고 있는 구조체이다. 모든 물리메모리공간은 Page(1024Bytes)단위로 관리된다. Page 내에는 어떤 인자들이 있는지 확인해보자.

  

 

1. operations

  Page는 anon, uninit, file이라는 3가지 Type이 존재한다. 이유는 Stack이나 Code, 등 데이터의 종류에 따라 다른 방식으로 처리해줘야하기 때문이다. 아래와 같이 type별로 swap_in, swap_out, destroy 시 실행해야 하는 함수를 별도로 저장해두고 실행한다.

 

 

* Swap in : 해당 Page를 물리 메모리(RAM)에 Load하는 행위

* Swap Out : 해당 Page를 물리 메모리에서 제거하는 행위. 돌아갈 곳이 없는 Page는 Swap Disk에, Disk에 다시 써도 되는 녀석들은 Disk에 Write하는 행위를 해줄 것이다.

* Destroy : 해당 Page를 제거하는 행위

 

2. va : 데이터가 저장된 가상주소의 시작점이다. 

 

3. frame : page와 matching된 frame을 가리킨다.

 

2) Frame

  : 물리공간에 대한 정보를 가지고 있는 구조체이다. Page Table에는 Page의 va : Frame의 kva가 매칭되어 있다.

 

1. kva : 실제 물리주소이다. (실제 저장되는 물리주소는 (kva - KERN_BASE)이긴 하다.)

 

3) Page Table

  모든 Thread는 각각 pml4라는 이름의 Page Table을 가지고 있다. (thread_create()함수의 pml4_create() 참고) Page Table에는 va : kva로 mapping이 되어있기 때문에, 가상주소에서 물리주소로의 번역이 가능하다. Mapping 정보를 확인하기 위해 va를 가지고 Page Table을 찾았는데, 매칭되는 kva가 없다면 Page Fault가 발생한다.

5) Page Fault

  사용자가 원하는 임의의 가상 주소에 접근하려고 했을 때, thread는 해당 주소가 포함된 Page의 시작 주소(va)를 찾은 뒤(=pg_round_down(va)), 이것에 매칭된 물리주소(kva)가 있는지 Page Table에서 찾는다. 만약 matching 된 정보가 없다면 Page Fault를 발생시킨다. Page Fault Handler에서 Page Fault에 대한 처리를 하면, 해당 가상 주소는 이제 접근이 가능하게 된다. 현재는 Page Fault Handler에서 아무런 조치를 하지 않는다. 이런 경우 외에도, 읽기 전용인 페이지에 Write를 하려고 해도 Page Fault가 발생한다.

  Page Table에 va : kva 매핑하는 작업은 install_page(), 매핑된 정보를 제거하는 작업은 clear_page()를 참고하자.

6) Bitmap

  메모리공간의 사용가능여부를 나타내는 Bit들의 집합이다. 1이면 사용중, 0이면 비어있음을 나타내도록 사용할 수 있다. bitmap.c 파일에 자세히 나와있다.

7) MMAP

  사용자가 명시적으로 파일의 내용을 물리메모리에 올리도록 요청하는 System Call이다. 사용자가 요청하는 바는 디스크에 있는 파일의 데이터를 물리메모리에 올리라는 것이나, 당장 사용하지 않을 데이터를 모두 한정된 물리메모리에 올려놓는 것은 비효율적이기 때문에 load_segment와 마찬가지로 페이지 정보만 등록해놓고 필요할 때 물리메모리에 Load하기로 한다.

8) Supplemental Page Table

  Lazy Load를 구현하려면, Page에 대한 정보(어디서 가져와야 하는 데이터인지, 어떤 데이터인지..)를 어디엔가 등록해놓은 뒤 Page Fault가 발생하면 이 정보를 찾아 메모리에 Load해야 한다. 따라서 Page에 대한 정보를 저장해놓을 공간이 필요한데, 이게 SPT다. SPT에서 Page에 대한 정보를 찾는 시간을 최소화하기 위해 Hash Table을 사용한다.

 

9) Swap Table

  위에서 설명했듯이, 물리메모리가 가득찼을 때 기존에 있던 Page들 중 하나를 밖으로 빼내고 새로운 Page를 넣어야 한다. 새로 물리 메모리에 Load되는 Page는 Swap In 된다고 하고, 기존에 물리메모리에 올려져 있었으나 꺼내지는 Page는 Swap Out 된다고 부른다. 

  위에서 살펴봤듯이, Page의 종류는 3가지가 있다. Uninit, Anon, File이다. Uninit Type은 초기화되지 않은 Page로 Page 정보는 생성되었으나 사용자가 해당 Page에 접근하지 않았다는 것을 의미한다. 따라서 물리메모리에 올라가있는 페이지가 Uninit일수는 없다. File Type은 mmap된 Page이다. File Type은 Swap In될 때 disk에서 직접 읽어오면 되고, Swap Out될 때는 직접 Disk에 다시 쓰면 된다. Anon Type은 Stack, Text 등을 포함한다. Anon Type은 Swap Out될 때 디스크에 다시 돌아갈 곳도 없고, 무작정 제거하면 다음에 접근할 수 없다. 따라서 물리 Disk에 Swap Disk란 공간을 별도로 할당해서 이곳에서 Swap In/Out되는 Anon Type Page들을 관리한다.

  Swap Table은 Swap Disk의 할당 정보를 포함하고 있는 Table이라고 생각하면 된다. bitmap을 사용하여 Swap Table을 구현할 수 있다.

 

* 교체 Policy

  물리메모리가 가득 차서 현재 Load된 Page들 중 하나를 빼낼 때 어떤 녀석을 빼낼 것인가에 대한 정책이다. FIFO도 가능하고, LRU 등 다양한 교체 알고리즘이 있다. Test Case들은 FIFO 방식으로 구현해도 시간은 충분했다. (컴퓨터 환경에 따라 조금씩 다를 수 있다.)

* Accessed and dirty bit

  File Type Page가 Swap Out되는 경우를 생각해보자. 만약 데이터를 사용자가 읽기만 하고 변경하지 않았다면, 굳이 disk에 다시 써줄 필요가 없다. 고맙게도 CPU는 사용자가 특정 Page를 수정했다면 dirty bit를 1로 바꿔주는데, 이를 확인한 뒤 Disk Write back을 할지 말지 결정한다.

 

* Copy On Write

  기본적으로 fork 구현 시 frame을 모두 새로 할당하여 복사해주었을 것이다. 이런 경우도 마찬가지로 비효율을 초래할 수 있다. 따라서 fork할 때 자식은 부모가 할당한 물리 메모리 공간을 가리키게 하되, writable을 0으로 해준다. 읽는 것은 가능하지만, 무언가 쓰려고 하면 Page Fault가 발생할 것이고 이 때 새로 물리메모리 공간을 할당해서 복사를 진행한다. writable을 0으로 모두 할당할 것이지만, 기존에 존재하던 Page의 writable여부도 반드시 저장해서 새로 물리공간을 할당할 때 update해줘야 한다는 것을 잊지 말자.

Project 3 - 구현

  전체적인 그림을 한번 잡고 시작할 수 있다면 더 좋을 것 같다.(가능할진 모르겠지만) 위의 내용들을 이해했고 무엇을 해야할지 파악했다면, 구현하는건 조금이나마 더 수월할 것이다. 제대로 된 데이터가 Load되는지, Swap In/Out 된 데이터가 일치하는지 여부를 hex_dump()함수를 활용하여 직접 확인해보는 것을 추천한다.

끝-!