(2022.03.18) Return To Pintos + COW 가이드라인

원서 작성 + 동아리 qual로 4일 정도 보낸 뒤 복귀했다. 이제 수업에서는 플젝 1 제출이 코앞이기에 먼저 제공된 가상 머신에 플젝 1 내용을 올려 테스트해보기로 한다. 전부 잘 통과하는 것을 볼 수 있다.

pass tests/threads/alarm-single
pass tests/threads/alarm-multiple
pass tests/threads/alarm-simultaneous
pass tests/threads/alarm-priority
pass tests/threads/alarm-zero
pass tests/threads/alarm-negative
pass tests/threads/priority-change
pass tests/threads/priority-donate-one
pass tests/threads/priority-donate-multiple
pass tests/threads/priority-donate-multiple2
pass tests/threads/priority-donate-nest
pass tests/threads/priority-donate-sema
pass tests/threads/priority-donate-lower
pass tests/threads/priority-fifo
pass tests/threads/priority-preempt
pass tests/threads/priority-sema
pass tests/threads/priority-condvar
pass tests/threads/priority-donate-chain
pass tests/threads/mlfqs/mlfqs-load-1
pass tests/threads/mlfqs/mlfqs-load-60
pass tests/threads/mlfqs/mlfqs-load-avg
pass tests/threads/mlfqs/mlfqs-recent-1
pass tests/threads/mlfqs/mlfqs-fair-2
pass tests/threads/mlfqs/mlfqs-fair-20
pass tests/threads/mlfqs/mlfqs-nice-2
pass tests/threads/mlfqs/mlfqs-nice-10
pass tests/threads/mlfqs/mlfqs-block
All 27 tests passed.
make[1]: Leaving directory '/root/project-1/threads/build'
root@cs330-20:~/project-1/threads#

make archive를 통해 tar.gz를 만들어 제출한다.

 

그럼 이제 다시 내가 하던 부분으로 돌아가 COW를 생각할 차례이다. 지속해서 언급해 오던 이 지긋지긋한 내용을 끝낼 때가 왔다. COW, Copy On Write는 개념적으로는 간단하다. 가상 페이지는 실체인 프레임과 매핑이 되어 있기 때문에 복사하는 순간에는 프레임까지 복사하지 말고, 새롭게 생성된 페이지를 기존 프레임으로 매핑시켜 프레임을 공유하게 한다. 만약 복사된 페이지들 중 어느 하나에서 프레임에 쓰기 요청이 발생한다면, 그제서야 프레임을 복사하는 것이다. 그래서 Copy "On Write"이다.  

 

이 쓰기 요청을 OS 입장에서 판단하기 위해 매뉴얼에서는 페이지를 쓸 수 없는 페이지로 만들라고 한다. 이러면 해당 페이지에 접근해 쓰기 요청을 할 때, page fault가 날 것이기에, 해당 부분에서 핸들링 할 수 있다는 것이다.

 It is a simple idea: Make a page fault on write accesses. This can be easily implemented with the support of the memory management system, by just marking write-protected page as unwritable at all.

 

핀토스에서는 가상 메모리 자원을 복사할 때, 즉 supplemental_page_table_copy를 호출할 때는 fork 밖에 없다. 따라서 해당 순간에 어떻게 복사를 관리할지가 관건이다. 페이지 타입과 메모리에 해당 프레임이 올라가 있는지의 여부에 따라 가지로 분리해서 각 복사 루틴을 생각해보는 것이 좋을 것이다.

1-1) VM_UNINIT

애초에 메모리에 프레임이 올라가 있지 않은 페이지이다. 복사할 것이 없다고 생각하면 간단하다고 볼 여지가 있는데 그리 간단하지는 않다. 추후에 쓰기 요청이 아닌 단순 읽기 요청이 들어왔을 때는 일반적인 프레임이 없어서 발생하는 page fault가 나기 때문에 해당 프레임은 page fault가 발생한 프로세스 뿐만이 아닌 해당 프레임을 공유하는 프로세스 모두에게 연결이 이루어져야 한다. 그와 동시에 VM_UNINIT이었던 페이지의 상태 또한 갱신해주어야 한다. 따라서, 페이지 구조체 내에서는 어떤 방식으로든 해당 페이지와 프레임을 공유하는 다른 프로세스의 페이지에 대한 정보를 들고 있어야 추적이 가능하다. 

 

이에 해당 구조를 생각해보자. 페이지마다 페이지의 리스트를 가리키는 포인터를 둔다. shared_pages라는 이름의 이 포인터는 해당 페이지에 연결된, 또는 연결될 프레임을 공유하는 페이지의 풀을 가지고 있다. 공유가 되지 않은 페이지라도 shared_pages에는 각자의 페이지가 들어가게 된다. (일괄적 관리를 위한 것) fork를 해줄 때에는 복사를 할 페이지의 포인터에 새롭게 만든 페이지를 추가해주고, 해당 페이지의 shared_pages로서 포인터를 복사해준다. 어쨌거나 shared_pages는 언제나 NULL이 아닌 값이 들어가게 해준다는 것이 핵심이다. 해당 구조를 사용하여 앞으로 다른 기능의 구현을 어떻게 하는지 살펴볼 것이다.

 

추가적으로 VM_UNINIT에서 들고 있는 aux의 경우, 각 페이지를 initialize할 때 각각 free가 되었기 때문에 지금까지는 새롭게 할당을 해 준 뒤, 내용을 복사를 해 주었다. 그러나 지금부터는 내용이 채워질 프레임을 각 페이지가 공유하면서 aux가 1번만 사용되면 되기 때문에 포인터 자체를 복사해주면 된다.  

1-2) 메모리에 프레임이 올라와 있는 VM_ANON

shared_pages에 새롭게 복사한 페이지를 넣고 포인터 값을 복사해 온다. 메모리에 프레임이 현재 올라와 있기 때문에 복사 시점에서는 새롭게 페이지를 만들 때 새로운 프레임을 할당하는 것이 아닌, 해당 프레임으로 매핑을 형성한다. 할당된 프레임 내에서는 shared_pages 포인터를 이미 갖고 있기 때문에 프레임에서는 새롭게 생성된 페이지를 추적할 수 있으며, 페이지에서 프레임을 찾을 수 있도록 프레임 포인터를 갖도록 하면 충분하다. 

1-3) 디스크에 프레임 내용이 있는 VM_ANON (swapped-out)

shared_pages에 새롭게 복사한 페이지를 넣고 포인터 값을 복사해 온다. 프레임의 내용이 disk에 있는 상태이기 때문에, disk에 내용이 저장되어 있는 sector number를 복사해올 필요가 있다. 해당 정보를 복사하면 끝이다.

1-4) 메모리에 프레임이 올라와 있는 VM_FILE

페이지 내에 가지고 있는 기반 정보를 복사한다. 메모리에 프레임이 있는 VM_ANON과 마찬가지로 shared_pages에 새롭게 복사한 페이지를 넣고 포인터 값을 복사해 온다. 기존에 존재하던 프레임과 새 페이지간의 매핑을 완성한다. VM_FILE에서 추가적으로 해야 하는 다른 점은 파일을 reopen하는 루틴이 필요하다는 것이다. 이 루틴은 기존에 만들어 놓은 루틴대로 하면 된다. 

1-5) 디스크에 프레임 내용이 있는 VM_FILE (swapped-out)

복사하려는 페이지의 정보는 모두 복사해서 가져가도록 한다. 다른 페이지와 마찬가지로 shared_pages에 새롭게 복사한 페이지를 넣고 포인터 값을 복사해 온다. mmap_fp는 이 때 복사하려는 프로세스와는 분리해서 가지고 있도록 한다. 그래야 추후 write가 일어나서 분리가 일어나더라도 한 프로세스 내에서의 파일 통일성은 유지할 수 있다.

 

2~5까지 기존 페이지의 va에 지정된 dirty와 access bit를 새로운 페이지의 va에 지정하는 것 또한 잊으면 안 된다.

 

---

 

다음으로 vm_try_handle_fault에서 각 페이지 종류별로 bogus page fault 중 lazy-load와 swapped-out, write-protect 각각의 경우 어떻게 대응해야 할지 생각해보자. fork에서 지정한 경우 외에 write가 실제로 막혀야 할 경우가 있다. read-only로 호출된 mmap 같은 경우에는 비단 fork로 호출되지 않더라도 write-protect가 가동될 것이다. 지금까지는 그냥 종료되도록 루틴이 짜여졌지만, 이제부터는 write-protect 중에서도 정당한 경우에는 다시 프로세스 루틴으로 복귀할 수 있도록 설정해주어야 한다. 

 

만약 ready-only 페이지에 write 접근이 들어온다면, 페이지 구조체의 rw 멤버를 확인하도록 한다. 만약 rw가 true라면, 해당 페이지는 write 접근이 정당하다는 뜻이며. 현재는 fork로 인해 write-protect가 걸렸다는 의미이다. 이 경우, 적당한 대응을 한 뒤 정상 궤도로 복귀하도록 한다. 만약 rw가 false라면 그대로 프로세스를 죽이도록 하자. 

2-1) VM_UNINIT

해당 페이지의 경우 swapped-out 상태에서 불리는 page fault는 없다. lazy-load 될 경우, 복사 시 공유된 페이지 정보를 기반으로 load할 프레임과 연결될 모든 페이지에 해당 프레임이 메모리에 로드되었다는 것을 통보하고, 전환 과정 및 매핑을 거치도록 해야 한다. 다음으로는 write-protect인데, 사실 지금 구현 상태로 VM_UNINIT 상태에서 write-protect가 불릴지는 확실하지 않다. write를 하기 위해 접근을 할 때, VM_UNINIT으로 존재하지 않는 페이지로 인한 fault가 먼저 이루어질 것이기에 VM_ANON이나 VM_FILE로 진화 후에 write-protect로 인한 fault가 불릴 것이기 때문이다.

 

그래도 상황을 상정을 해보자면 write-protect의 경우, 해당 페이지에 쓰면서 페이지들의 프레임 공유 풀에서 벗어나겠다는 의미이므로, shared_pages에서 호출된 페이지를 제외하고, shared_pages를 새롭게 할당하여 본연의 shared_pages를 갖도록 한다. fork 할 때 aux를 단순히 포인터 복사를 통해 사용했는데, 지금은 기존 풀에서 분리가 되는 순간이므로, aux는 새로운 공간을 malloc한 뒤 내용을 복사할 수 있도록 한다. write를 하겠다는 뜻은 프레임에 접근하겠다는 뜻이므로, 프레임도 하나 할당해주고 매핑을 모두 완료하도록 한다.

2-2) VM_ANON

해당 페이지의 경우 swapped-out된 페이지이거나 write-protect가 불린 경우일 것이다. swapped-out된 프레임을 불러올 때는 해당 프레임을 공유하는 모든 페이지에 통보 및 후속 작업을 진행한다. 

 

write-protect일 경우, 해당 페이지는 이제 기존 공유되던 페이지와는 분리하여 봐야 한다는 것이다. 이 때도 swapped out이 되어 있을지는 모르겠다. VM_UNINIT 처럼 프레임이 존재하지 않음으로 인한 page fault가 먼저 이루어질 것이기 때문이다. 일단 그래서 swapped-out 된 경우는 구현하지 않고 테스트를 해보도록 하자. 우선 shared_page에서 fault가 난 페이지를 제외한다. 항상 연동된 프레임이 메모리에 올라온 상태라고 가정한다면, 우선 내용을 복사할 새로운 프레임을 구한다. 이 상황에서 프레임을 구할 때 정말 재수없게 evict되는 프레임이 기존 shared 되던 프레임일 수 있다. 그래서 어차피 다시 또 기존 프레임이 swapped-out 된 경우를 고려할 사항이 생겼다. ㅋㅋㅋㅋㅋㅋㅋㅋ

 

암튼 swapped-out된 프레임이라면 기존에 구현했던 함수를 사용해 디스크에서 새로운 프레임으로 내용을 복사하도록 한다. 만약 swapped-out 되지 않았다면 단순 복사 후 사용하도록 한다. 기존에 있던 access bit와 dirty bit는 그대로 옮겨오도록 한다. 

2-3) VM_FILE

기존 방식이 다소 잘못된 것 같아 수정하였다. 기존에 swapped-out된 페이지에 대해서도 claim_page를 하면서 프레임이 할당되었기에 swapped-out 여부와는 상관 없이 프레임 내용을 채웠어야 했다. 그런데 현재 구현 상태는 메모리에 올라와 있는 경우에만 내용을 채워 넣었기에 수정을 해 주었다.

 

암튼 다시 돌아와서 생각을 해 보자. swapped-out의 경우에는 VM_ANON과 같은 처리를 해 주는 것이 맞다. 다만, 이 경우에는 swap-in을 할 수 있는 fp가 여러 개이다. 내용은 모두 COW의 원리에 의해 통일되고 있을테니 걱정할 것은 없다. 선택할 수 있는 fp 중 하나를 골라 swap-in 해주고, 매핑을 일일이 해주도록 한다.

 

write-protect로 write가 일어나는 경우, 우선 기존 shared_pages에서 나오고 새로운 shared_pages를 할당하도록 한다. eviction에 의한 재수없는 경우 외에는 메모리에 내용이 상주하고 있을 것이다. 새로운 프레임을 할당해 프레임의 내용을 복사하거나, 디스크에서 내용을 가져오는 식으로 프레임을 채우고, 새로운 매핑을 한 다음 반환하도록 한다. 

 

다른 관점으로 생각하면, 뭔가 기존에 supplemental_page_table_copy를 할 때 페이지의 init 용도로 사용되었던 루틴이 대부분 write-protect에서의 루틴으로 옮겨간 느낌이다. 

 

---

 

다음으로 COW를 도입했을 때의 eviction policy와 공유되고 있는 프레임을 evict하는 작업 과정을 살펴보자. 지금까지 eviction policy가 제대로 동작했던 것은 프레임 별로 연결된 페이지는 하나라는 보장이 있었고, 해당 페이지의 va의 access bit를 통해 evict될 프레임을 선택했기 때문이다. 따라서, eviction policy에서는 이제 여러 페이지의 access bit을 보고 결정해야 할 것이다.

 

임의로 지금은 access bit이 하나라도 0이 아닐 경우에는 살려두는 것으로 정하자. two-handed clock의 R 포인터는 연결된 모든 페이지의 access bit을 0으로 돌리도록 한다. 특성상 clock interval 사이에는 언제나 victim이 결정되기 때문에 임의로 결정해도 큰 문제는 없을 것이다. 

 

이제 evict될 프레임이 선택이 됐다고 생각하자. 프레임 공유는 fork에서만 발생하므로 evict될 프레임과 연결된 페이지들이 다른 종류인 경우는 없다. 또한 특성상 VM_UNINIT 페이지가 연결되어 있을 일 또한 없다.

3-1) VM_ANON

프레임 자체를 인자로 넣어 swap-out할 수는 없다. 따라서 연결된 페이지 중 하나를 골라 swap-out을 시켜야 하는데, 그 과정에서 다른 페이지와 해당 프레임간의 연결도 끊어줄 수 있도록 한다. swap out 후에는 swap disk의 어느 섹터에 넣었는지 인덱스가 반환될 것이다. 해당 인덱스는 모든 페이지에 넣어놔, 후에 어떤 페이지로 fault가 불리더라도 정상적으로 swap in 될 수 있도록 한다. 

3-2) VM_FILE

COW의 특성상 공유된 페이지는 언제나 dirty bit가 동일하다. 만약 복사할 당시 dirty bit가 켜지지 않았는데 쓰기 요청이 들어온다면 위에서 설명한대로 페이지가 공유풀에서 분리됐을 것이며, 복사할 때부터 dirty bit가 켜졌을 경우에도 상황은 같다. 어쨌든 evict될 프레임과 연결된 페이지의 dirty bit을 조사해 파일에 프레임의 내용을 쓸 지 여부를 결정한 뒤, 연결을 모두 해제하도록 한다. 이 때, 어떤 fp를 선택하더라도 연결된 inode는 모두 같을 것이기에 상관 없다.

 

---

 

마지막으로 한 프로세스가 종료될 때, 또는 munmap 등으로 페이지가 없어질 때를 생각해보자.

4-1) VM_UNINIT

공유하고 있는 aux를 해제할지의 여부는 shared_pages에 페이지가 얼마나 남아있는지를 보고 결정할 수 있다. 만약 shared_pages에 본인 페이지를 제외하고 하나도 남지 않았다면, 공유되고 있지 않다는 뜻이므로 해제하고, shared_pages에 할당된 자원 또한 해제해 주도록 한다. 만약 1개 이상 남아있다면 aux, shared_pages 모두 해제하지 않고 넘어간다.

4-2) VM_ANON

shared_pages에서 없애려는 페이지를 제외한다. 만약 shared_pages가 비어있지 않다면 다른 페이지에서는 여전히 공유가 일어나고 있다는 것이므로 차지하고 있는 swap disk idx, 프레임은 해제하지 말고, 현재 연결만 끊어주면서 페이지를 해제해준다.

4-3) VM_FILE

사실 제일 까다로울 수 있었던 부분인데 잘 넘긴 것 같다. mmap_fp는 복사가 일어날 때 각 프로세스가 고유하게 들고 있는 것이기에 닫아준다고 해도 문제가 되지 않는다. munmap으로 해제가 되던, exit에 의해 해제가 되던, mmap_fp는 고유 자원이므로 공유 문제에서 자유롭다. 

 

파일에 write-back을 해줄 때 신경을 써야 하는 것이 있다. copy를 하기 전 dirty bit가 켜져있었던 경우, 공유된 모든 페이지의 va에 dirty bit가 켜져있을 것이다. 그 중 하나가 munmap으로 write back이 되게 되면, 현재 공유되고 있는 페이지의 내용과 파일의 내용이 동기화되면서, 이후에는 파일에 write back할 이유가 없어지게 된다. 따라서, 나머지 shared_pages에 있는 페이지의 va에서 dirty bit를 해제해 주는 것이 중요하다. swap out을 할 때 shared_pages에 있는 페이지의 dirty bit을 제거하도록 구현하면 일괄적으로 적용할 수 있을 것으로 보인다.

 

---

 

이제 살펴볼 수 있는 대부분의 내용은 살펴본 것 같다. 정정해야 할 부분이 많지만 하나씩 천천히 해 나가면 언젠간 끝낼 수 있을 것이다. 기간도 비교적 넉넉한 편이니 시작해보자.