[운영체제] 메모리 관리(페이지 교체 알고리즘)

메모리는 한정되어 있기 때문에 스와핑이 많이 일어나며, 페이지 교체 알고리즘을 기반으로 스와핑이 일어난다.

 

필요한 페이지가 메모리에 없을 때 페이지 폴트가 발생하고, 저장 매체에서 해당 페이지를 찾아 빈 프레임에 로딩해야 하는데,

이때 빈 프레임이 없을 경우, 희생 당할 프레임(victim frame)을 고르는 알고리즘이 페이지 교체 알고리즘이다.

 

페이지 교체 알고리즘은 효율적인 스와핑을 통해 페이지 폴트를 줄이는 것을 목표로 한다.

 

FIFO(First In First Out)

가장 먼저 온 페이지를 교체 영역에 가장 먼저 놓는 방법이다. 구현은 간단하지만 성능이 좋진 않다. 

페이지가 올라온 순서를 따로 저장하거나, 큐를 이용해서 저장할 수 있다. 

 

LRU(Least Recently Used)

참조가 가장 오래된 페이지를 바꾼다. '오래된 것'을 파악하기 위해 각 페이지마다 계수기, 스택을 두어야 하는 문제점이 있지만 성능이 좋은 편이며 많은 운영체제가 채택하고 있는 방법이다.

NUR(Not Used Recently)

LRU 알고리즘에서 발전한 알고리즘이다. 일명 clock 알고리즘이라고도 불린다.

먼저 0과 1을 가진 참조 비트를 이용하는데, 1은 최근에 참조되었고 0은 참조되지 않음을 의미한다. 

클럭 알고리즘은 그림처럼 참조 비트(reference bit)를 순차적으로 조사하며 동작한다.

1. 프레임 내의 페이지가 참조될 때 하드웨어에 의해 1로 자동 세팅된다.

2. 클럭 알고리즘은 한 바퀴 돌며 참조되지 않은 페이지의 참조 비트 값을 0으로 바꾼 후 지나간다.

3. 참조 비트가 0인 페이지를 방문하면 해당 페이지를 교체한다.

 

즉, 페이지가 참조되어 1이 되고, 한 바퀴 도는 동안 사용되지 않으면 0이 되고 다시 한 바퀴를 도는 동안 사용되지 않는 페이지는 참조되지 않았으므로 교체 대상 페이지로 선정하는 알고리즘이다.

 

LFU(Least Frequently Used)

가장 참조 횟수가 적은 페이지를 교체한다. 이때 가장 적은 참조 횟수를 가지는 페이지가 여러 개라면 LRU에 따라 더 오래 쓰지 않은 페이지를 교체한다.