운영체제 #8 — 메모리 관리와 페이지 교체

이 편은 강의 슬라이드가 아니라 실습 질문들에서 나온 것들이다. 답을 쓰면서 정리된 것이라 앞 편들보다 짧고, 대신 "그래서 어느 쪽을 고를 거냐"에 대한 내 판단이 들어 있다.

할당 전략 — best fit, first fit, worst fit

빈 메모리 공간에 프로세스를 배치할 때 어디를 고를 것인가.

Best fit은 필요한 크기와 가장 비슷한 크기의 공간을 할당한다. external fragmentation이 적게 발생한다. 하지만 가장 작은 적당한 공간을 찾아야 하므로 시간이 오래 걸린다.

First fit은 가장 먼저 발견한 빈 공간에 할당한다. 구현이 쉽고 시간이 적게 걸린다. 하지만 external fragmentation 문제가 심할 수 있다.

Worst fit은 가장 큰 공간에 할당한다. 가장 큰 공간을 나누어 쓰므로, best fit에서 할당하고 남은 자투리가 아예 못 쓰이는 상황이 줄어들 수 있다.

어느 것이 더 좋고 나쁜지는 상황에 따라 다르다. 그런데 xv6의 경우 paging 기법을 쓰기 때문에 external fragmentation을 걱정할 필요가 없다. 그러면 best fit의 장점이 사라지므로, 속도가 가장 빠른 first fit을 쓰는 게 가장 좋을 것 같다는 게 당시 결론이었다.

세 전략의 장단점이 결국 "external fragmentation을 얼마나 감수하고 탐색 시간을 얼마나 아낄 것인가"의 트레이드오프인데, 그 축 하나가 paging 때문에 사라지면 남는 축이 하나뿐이라는 게 이 문제의 요점이었다.

페이지 교체 — FIFO, LRU, LFU

FIFO는 가장 오래된 page를 교체한다. frame 수가 많아질수록 page fault가 오히려 많이 일어나는 일이 생긴다.

LRU는 가장 오래전에 접근한 page를 교체한다. 그래서 최근에 접근한 page를 계속 들고 있을 수 있다.

LFU는 count를 이용해 가장 적게 접근되는 page를 교체한다. 최근에 접근했더라도 전체적으로 거의 접근하지 않는 page라면 교체할 수 있다.

서버와 클라이언트라면 어느 쪽을 쓸까

실습 문제가 재밌었다. 서버와 클라이언트 각각에 어떤 정책이 좋겠냐는 것이었다.

서버는 하나의 클라이언트와만 데이터를 주고받지 않는다. 여러 클라이언트가 빈번하게 접근하는 page를 들고 있는 게 좋다. 그러니 LFU가 낫다고 봤다.

클라이언트는 빈번하게 같은 데이터에 접근할 수도 있고, 최근에 접근한 데이터를 다시 접근할 수도 있다. 그러니 LFU든 LRU든 어느 쪽을 써도 괜찮을 것 같다.

xv6에 넣는다면

각 페이지가 count라는 변수를 가지게 해서 가장 최근에 사용된 page가 높은 count를 갖도록 하고, page fault가 일어났을 때 가장 작은 count를 가지는 page를 replace하도록 할 것이다. 즉 LRU다.

Copy-on-Write

CoW는 공통으로 사용하는 데이터나 코드를 여러 프로세스가 공유하고, 데이터를 바꿀 때만 새로 만드는 기법이다. 메모리 사용량이 줄고, 불필요한 데이터를 만드는 데 드는 오버헤드가 준다.

구현은 이렇게 한다. 페이지 테이블을 공유해서 page를 공유하고, 공유하고 있다면 read only로 flag를 표시한다. 수정이 필요해지면 그때 가서 page를 copy하고 수정할 부분을 수정한다.

fork와 exec에서 특히 필요한 이유

xv6에서 CoW가 특히 중요한 게 fork와 exec 조합이다.

CoW를 쓰지 않으면 fork를 할 때 모든 페이지를 복사해야 한다. 그런데 exec를 실행할 때는 보통 fork 하고 바로 exec를 하기 때문에, 그 복사가 통째로 불필요한 경우가 생긴다. 복사해놓고 곧바로 다른 프로그램으로 덮어쓰는 것이다.

CoW를 쓰면 fork 시점에 불필요한 복사를 하지 않으므로 메모리를 절약할 수 있고 operation의 수행 시간도 줄어든다.

#3에서 "fork()는 그냥 부모의 주소 공간을 복제하고, exec()를 해야 그때 프로그램으로 채워진다"고 정리했는데, CoW는 그 "그냥 복제"를 최대한 미루는 방법이라고 이해하면 된다.