[운영체제] CH9. Virtual Memory(2)

그럼, 어떤 알고리즘이 가장 좋은 알고리즘일까?

Page Replacement Algorithm

 

Optimal Algorithm

이론적으로 가장 최적의 알고리즘이다.

가장 먼 미래에 참조되는 page를 victim으로 선정한다.

미래에 참조될 페이지를 모두 알고 있다는 가정을 하기 때문에 어떤 프레임을 쫓아내야 할지 알 수 있는 것이다.

따라서 실제 시스템에서는 사용될 수 없는 알고리즘이다.

다만, 다른 알고리즘의 성능에 대한 upper bound를 제공해준다.

 

9 page faults. -> 이보다 적게 page fault가 날 수 없다.

 

 

실제로 사용하는 알고리즘은 미래를 알 수 없기 때문에, 과거의 정보를 바탕으로 victim을 선정한다.

 

FIFO(First In First Out) Algorithm

가장 단순한 알고리즘으로, 먼저 들어온 것을 먼저 내쫓는 알고리즘이다.

15 page faults

• Belady's Anomaly

  페이지 프레임 수를 늘렸는데 page fault 수가 증가하는 경우가 있다.

  e.g) 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

 

LRU(Least Recently Used) Algorithm

가장 덜 최근에 사용된 프레임을 victim으로 선정하는 알고리즘이다.

즉, 사용한지(참조된지) 가장 오래된 프레임을 쫓아낸다.

12 page faults

 

LFU(Least Frequently Used) Algorithm

참조 횟수(reference count)가 가장 적은 페이지 프레임을 victim으로 선정하는 알고리즘이다. 참조 횟수가 적은 페이지가 뒤에도 참조될 가능성이 낮을 것이라는 가정을 둔 알고리즘이다.

 

최저 잠조 횟수인 페이지가 여러 개인 경우에는

• LFU 알고리즘 자체에서는 여러 페이지들 중 임의의 페이지를 선정한다.
• 성능 향상을 위해서 가장 오래 전에 참조된 페이지를 선정할 수도 있다.

MFU(Most Frequently Used) Algorithm

LFU 알고리즘과 반대로 참조 횟수가 가장 많은 페이지 프레임을 victim으로 선정하는 알고리즘이다. 참조가 많이 된 페이지가 앞으로는 참조될 가능성이 낮을 것이라는 가정을 둔 알고리즘이다.

 

LFU, MFU와 같이 Counting에 기반한 두 알고리즘은 Optimal Algorithm의 성능에 제대로 근사하지 못하기 때문에, 잘 쓰이지 않는다.

 

LRU & LFU 구현

LRU

Linked List로 구현할 수 있다.

참조되는 페이지를 가장 밑으로 보내주면 된다.

LFU

참조 횟수를 비교해주어야 하므로 리스트로 구현하면 최악의 경우 O(n) 이 걸린다.

따라서 Heap을 이용해서 구현한다. Heap을 이용하면 O(log n) 으로 줄일 수 있다.

 

 

 

 

 

본 포스팅은 이화여대 반효경 교수님의 강의와 경북대 탁병철 교수님의 강의를 토대로 작성한 글입니다.