[운영체제/OS] Copy-on-Write와 Page Replacement

Copy-on-Write (COW)는 부모와 자식 프로세스가 메모리의 같은 페이지를 공유할 수 있게 해줍니다.

프로세스 생성을 훨씬 효율적으로 하게 해줍니다. 최적화 기술 중 하나로 쓰입니다.

 

Resourse를 공유하다가 Resource를 수정하는 경우, 이전의 Resource 복사본을 쓰게끔 하는 것입니다. 그 후에 각각 프로세서의 포인터를 변경만 해주면 됩니다. 

 

원래는 zero-fill-on-demand 페이지들의 pool로부터 할당됩니다. 0으로 채워서 reset하는 것이죠.

Page Replacement

Free Frame이 만약에 없다면 어떻게 하는가? 

Page replacement - 새 page 위해 기존 page(잘 안 쓰이는 애, 가급적 수정 안 된 애)를 내쫓는다. (최대한 overhead 줄이기). 

write된 frame을 또 고르는 경우는 백업(write back) 작업의 수고가 드므로, 읽기만 수행한 frame이 더 좋다.

over-allocation(메모리크기보다 큰 페이지 할당)을 방지해야 한다.

modify(dirty) bit를 사용하여 수정된 페이지만 디스크에 write되었는지 체크하여 오버헤드를 줄인다.

 

1. 디스크에서 요청 페이지의 위치를 찾는다.

2. free frame을 찾는다. 

 free frame을 찾으면, 사용한다.

 free frame이 없다면, place replacement 알고리즘을 사용해 victim frame을 고른다.

   victim frame이 dirty(write흔적있는애)하다면 disk로 백업

3. 요청 페이지를 free frame으로 부르고, 페이지와 frame table을 업뎃.

4. 명령어 재실행

 

이 작업을 위해서 사용하는 frame-allocation, page-replacement 알고리즘들이 있습니다.

프레임 수가 증가할수록 page fault의 횟수는 감소합니다.

 

 

First-In-First-Out (FIFO) 알고리즘

가장 오래된 애를 쫓아내는 알고리즘이라고 보면 됩니다. 알고있는 FIFO 그대로 들어온 순서대로 나가는 거죠.

 

요청 순서: 7 0 1 2 0 3 0 4 2 3 0 3 0 3 2 1 2 0 1 7 0 1 

총 15번의 page faults가 발생합니다. 이는 굉장히 비효율적이지만 구현은 쉽습니다.

요청 순서에 따라 물론 다르겠지만, 프레임을 추가하는 것이 더 많은 page faults를 발생시킵니다. 

이는 Belady의 이상현상이라고 불립니다.

 

Belady의 이상현상(Belady's Anomaly)

프레임을 더 늘였는데 오히려 page fault가 더 증가하는 현상.

FIFO 알고리즘은 이 Belady의 이상현상이 발생합니다.

ex) 1 2 3 4 1 2 5 1 2 3 4 5 요청 순서일 때

3개의 프레임에선 9번의 page fault가 발생하지만,

4개의 프레임에서 10번의 page fault가 발생하며 프레임증가와 모순적으로 page fault횟수도 증가했습니다.

 

Optimal(최적의) Algorithm 

가장 이상적인 알고리즘이랑 실제 구현은 사실상 불가능합니다. 예측하는 것이 쉽지 않기 때문입니다.

가장 오랜 시간 사용되지 않을 페이지를 replace해주는 알고리즘입니다.

하지만 미래를 예측하는 것은 불가능하죠.

보통 알고리즘 테스트용으로만 사용됩니다.

7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 요청순서일때

2를 넣기 위해 교체할 페이지를 고를 때 이미 존재하는 7, 0, 1 중에 이후 가장 오래 사용되지 않는 7을 고릅니다.

이런식으로 victim frame을 골라나갑니다.

 

Least Recently Used (LRU) Algorithm

Optimal 알고리즘에 최대한 가까운 알고리즘으로, 과거 데이터를 통해 미래를 예측하는 알고리즘입니다.

마찬가지로 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 요청순서일때

2를 넣기 위해 과거의 데이터를 보고 7, 0, 1 중 7이 가장 오래전에 사용되었기 때문에 7을 victim frame으로 고릅니다.

이렇게 timer기록으로 가장 오래된 애로 victim frame을 골라나갑니다. 

하지만 이는 search 구현이 필요합니다.

 

LRU 알고리즘 구현하기

-Counter implementation : 프레임이 참조될 때마다 counter가 증가. 하지만 매번 counter 횟수 세는 search시간이 오래걸린다.

-Stack implementation : double linked list를 사용하여 tail이 가장 오래된 애를 빼간다. search가 필요없다.

 

Reference bit

모든 페이지 초기화는 0으로 

페이지가 참조될 때마다, reference bit을 1로  바꾼다.

0의 reference bit를 가진 아무 페이지를 참조하여 내쫓는다. 

 

Second-chance(clock) algorithm

FIFO와 하드웨어가 추가된 reference bit 

clock을 두고 일정 주기마다 모든 reference bit을 0으로 replace한다.

reference bit = 0이면 replace

reference bit = 1이면, 0으로 set하고 페이지를 메모리에 둔다. 다음 페이지를 replace한다.(같은과정)

 

Enhanced Second-chance Algorithm

reference bit과 함께 modify bit도 추가

(reference, modify) 쌍으로

(0, 0): 최근에 사용x, 수정 x - replace하기 가장 좋음

(0, 1): 최근에 사용x, 수정 o - 전자만큼 좋진 않음, replacement 전에 반드시 백업(write out)

(1, 0): 최근에 사용o, 수정 x - 곧 사용될 예정

(1, 1): 최근에 사용o, 수정 o - 곧 사용될 예정, replacement 전에 반드시 백업(write out)

 

Counting Algorithms

참조할 때마다 계수를 하여 그 값으로 판단하는 알고리즘

-LFU(least frequently used) : 참조횟수가 가장 적은 페이지를 교체

이에 반대되는 알고리즘이

-MFU(most frequently used) : 가장 많이 참조된 애를 교체(앞으로 사용되지 않을 것이라고 예상)

잘 쓰이지는 않고, 모든 페이지의 각 횟수가 일정하다는 가정으로 쓰인다.

그래서 연속적인 대량의 읽기 작업할 때 더 효율적이다.

페이지 버퍼링(Page-Buffering) 알고리즘

place replacement 알고리즘과 병행하여 사용된다.

가용 프레임 여러개를 풀(pool)로 유지하고 필요할 때 풀에서 꺼내주는 방식

 

매번 프로세스가 대기하면 시간이 오래 걸리므로 가용프레임을 두어 바로 할당해주고 

나중에 디스크에 기록하고 가용 프레임 풀에 추가한다.