[OS] 9-2. Virtual Memory II

Chapter 9-2. Virtual Memory II

Replacement Algorithm

* 빨간색 숫자는 page fault를 의미한다.

* 노란색 숫자는 Reference 가 일어날 때를 의미한다.

가장 먼 미래에 사용될 page를 알고 있다는 가정하에 구성된 알고리즘이다.(= Belady's optimal algorithm, MIN, OPT)

가장 먼 미래에 사용될 page를 실제로 알 수 없으므로 실제로 시스템에서는 사용할 수 없다.

실제 시스템에서 쓰이지는 않고 다른 알고리즘의 성능에 대한 upper bound를 제공한다.

4번이 가장 오랜 후에 참조될 것을 미리 알고 4가 위치한 frame에 5를 내어준다.

* 빨간색 숫자는 page fault를 의미한다.

* 노란색 숫자는 Reference 가 일어날 때를 의미한다.

먼저 들어온 페이지를 먼저 쫓아낸다.

* FIFO Anomaly(3:9 -> 4:10)

= 사용 가능한 frame수를 늘려주면 page fault가 증가하게 된다. 즉 성능이 더 나빠지게 된다.

1번이 가장 먼저 들어온 숫자이므로 1을 가장 먼저 쫓아낸다.

* 빨간색 숫자는 page fault를 의미한다.

* 노란색 숫자는 Reference 가 일어날 때를 의미한다.

가장 덜 최근에 사용된, 오래전에 사용된 페이지를 내쫓는 알고리즘이다.

   LFU(Least Frequently Used) Algorithm

가장 덜 사용된, 참조 횟수가 가장 적은 페이지를 내쫓는 알고리즘이다.

최저 참조횟수인 page가 여러 개일 경우에 임의로 선정하게 된다.

성능 향상을 위해 이 안에서 LRU로 선정한다.

LFU는 LRU보다 구현이 복잡하다.

LRU vs LFU

LRU : 오래된 지혜를 갖고 있는 노인을 쫓아내려하는 알고리즘.

Linked List 형태로 참조 시간 순서대로 관리한다.

최근에 참조된 것들을 계속 마지막으로 바꾼다.

자동적으로 쫓아낼 페이지는 head 노드가 된다.

= O(1) time complexity

LFU : 이제 막 떠오르려고 하는 신인을 무조건 쫓아내려하는 알고리즘.

Linked List 자료구조를 사용하게 되면,

다른 페이지들의 참조횟수들과 비교를 해야 하는 경우가 발생한다.

= O(n) time complexity

그래서 Heap 구조를 사용한다. -> 완전 이진 트리 구조

밑으로 내려갈 수록 자주 참조된 페이지들로 구성되고, 비교시에 직계자식과 비교를 하게 된다.

따라서 재구성하는데 걸리는 시간이 = O(log n) time complexity이 된다.

Paging System 에서 LRU, LFU 알고리즘을 적용할 수 있는가?

무슨 뜬금없는 소리냐고 생각할 수 있지만,

알고리즘이 존재할 수 있는 것이지, 실제로 적용되는 문제는 아직 논하지 않았다.

살펴보면,

OS는 valid인 경우에 하드웨어와 CPU간의 주소변환을 통해서 메모리에 접근하게 된다.

하지만 Invalid인 경우에는 trap(page fault)이 발생하게 되고,

이 때가 되서야, 이때만 OS 가 개입하게 된다.

즉, OS는 page fault가 발생한 경우에 CPU제어권을 받게 되는 것이다.

그렇기 때문에, OS는 가장 오래 전에 참조된 것, 참조횟수가 가장 적은 것에 대한 정보가 없다.

위에서 설명한 자료구조들을 조작할 수 없는 것이다.

그래서 사용하는 알고리즘이 Clock Algorithm이다.

Chapter 9-2. 끝

이 포스팅은 이화여대 반효경 교수님 강의를 듣고 요약한 내용을 담고 있습니다.