16 > Page Replacement

* 해당 게시물은 경북대학교 컴퓨터학부 강의초빙교수, 배준현 교수님의 강의를 보고 작성되었음을 미리 알려드립니다. ( 개인적인 공부를 정리한 글입니다. )

 

> 주니온 TV Youtube Channel.  https://www.youtube.com/channel/UCOcPzXDWSrnaKXse9XOPiog

주니온TV 아무거나연구소

 

> 주니온 TV Inflearn page.  https://www.inflearn.com/users/@joonion

주니온님의 소개 - 인프런 | 온라인 강의 플랫폼

---

만약 free frames가 없다면? page를 교체해주어야 한다.

알고리즘에서 victim을 정하고, 이를 page out 시키고 invalid 상태로 올린다.

그럼 invalid한 page를 backing store에서 요구한 뒤 page를 재 시작한다.

Figure 10.10 Page replacement.

[  ] Two major problems to implement demand paging:

- Frame-allocation algorithm:

  how many frames to allocated to each process?

- Page-replacement algorithm:

  select the frames that are to be replaced.

- Since the secondary storage I/O is so expensive,

  even slight improvements in demand-paging methods

  can yield large gains in system performance.

 

page fault의 비율을 낮추어야 한다. 이것을 위해서 frame 수를 높일 수 있다.

 

- FIFO Page Replacement:

Oldest page를 victim으로 설정한다.

그러나 Belady's Anmaly 에서 확인할 결과, Page frame은 늘렸는데 이상하게 page fault가 더 많이 발생하는 현상이 일어난다.

Figure 10.13 Page-fault curve of FIFO repl c ement on a reference string.

 

 

- Optimal Page Replacement

가장 사용 안 할 것 같은 page를 victim으로 설정한다. 하지만 이것을 계산하기는 실질적으로 불가능하기에(미래의 상황을 예측할 수 없다) 비교 대상군으로 사용한다.

 

- LRU (Least-recently-used) > 시간

가장 오래 사용되지 않은 페이지를 교체한다. 많은 운영체제가 이 방식을 채택하고 있다.

이를 구현하기 위해 Count나 Stack을 사용할 수 있다.

Figure 10.17 Second-chance (clock) page-replacement algorithm.

위와 같이 한번 돌 때를 기준으로 사용하면 1, 사용하지 않으면 0을 두어 victim을 선정할 수 있다.

 

- LFU (Least-frequently-used) > 횟수

LRU의 문제는 계속해서 사용된 page가 역할을 끝냈을 때, 더 이상 사용하지 않더라도 참조횟수가 높아서 메모리에 계속 잔류할 가능성이 높다.

이것을 해결하기 위해 가장 참조 횟수가 적은 페이지를 교체하는 것이다.

 

- MFU(Most-frequently-used)

LFU의 반대, 오히려 가장 적은 참조 횟수를 가진 page가 미래에 자주 쓰일 가능성이 높기에 채택한다.

 

LFU, MFU의 기본 Concept부터 애매하고, 각 page의 counting을 해야 하기 때문에 자원도 소모된다. 더불어 LRU의 성능 보다 항상 좋다고 볼 수도 없기에 자주 사용되지 않는다.

 

[  ] Thrashing

- a situation that a process is busy swapping pages in and out.

- If a process does not have enough pages, the page-fault rate is very high.

page fault가 일어나면 process는 계속해서 wait 상태로 전환 되었다가 다시 동작한다. 이것이 매우 많이 발생한다면 막상 CPU는 작업을 하지 않고 Page를 기다리는 시간이 높아진다. 이를 Thrashing이라 한다.

 

Figure 10.20 Thrashing.

working-set window(slice window)를 지정한다. 해당 slice window 안에 들어온 page를 recent page라 본다.

이 밖을 벗어나면 victim으로 선정한다.

Figure 10.22 Working-set model.