페이지 교체 알고리즘의 개요
프로세스가 요구한 페이지가 현재 메모리에 없으면 페이지 부재가 발생한다. 페이지 부재가 발생하면 스왑 영역에서 페이지를 메모리로 가져오는데, 만약 메모리가 꽉 찼다면 메모리에 있는 페이지를 스왑 영역으로 내보내야 한다. 페이지 교체 알고리즘은 스왑 영역으로 보낼 페이지를 결정하는 알고리즘이다.
페이지 교체 알고리즘의 종류
- 간단한 알고리즘
무작위: 무작위로 대상 페이지를 선정하여 스왑 영역으로 보낸다.
FIFO: 처음 메모리에 올라온 페이지를 스왑 영역으로 보낸다
- 이론적 알고리즘
최적: 미래의 메모리 접근 패턴을 보고 대상 페이지를 선정하여 스왑 영역으로 보낸다.
- 최적 접근 알고리즘
LRU: 시간적으로 멀리 떨어진 페이지를 스왑 영역으로 보낸다.
LFU: 사용 빈도가 적은 페이지를 스왑 영역으로 보낸다
NUR: 최근에 사용한 적 없는 페이지를 스왑 영역으로 본낸다.
FIFO변형: FIFO알고리즘을 변형하여 성능을 높인다.
무작위 페이지 교체 알고리즘
random page replacement algorithm은 페이지 교체 알고리즘 중 가장 간단하게 구현할 수 있는 방법이다.
FIFO페이지 교체 알고리즘
선입선출 페이지 교체 알고리즘이라고도 하는 FIFO는 시간상 가장 먼저 들어온 페이지를 대상 페이지로 선정하여 스왑 영역으로 쫓아낸다. 페이지 부재로 인해 원하는 페이지가 메모리에 없는 경우 F fail로, 원하는 페이지가 메모리에 있는 경우 S success로 표시한다. 큐로 구현하는데 메모리 맨 위에 있는 페이지는 가장 오래된 페이지이고, 새로운 페이지는 항상 맨 아래에 삽입된다. 메모리가 꽉 차면 맨 위의 페이지가 스왑 영역으로 가고 나머지 페이지들은 위쪽으로 이동하며, 새로운 페이지가 아래쪽에 남은 공간에 들어온다.
최적 페이지 교체 알고리즘
optimal page replacement algorithm은 앞으로 사용하지 않을 페이지를 스왑 영역으로 옮긴다. 메모리가 앞으로 사용할 페이지를 미리 살펴보고 페이지 교체 선정 시점부터 사용 시점까지 가장 멀리 있는 페이지를 대상 페이지로 선정한다.
최근 최소 사용 알고리즘인 LRU Least Recently Used, 최소 빈도 사용 알고리즘인 LFU Least Frequently Used, 최근 미사용 알고리즘 NUR Not Used Recently 등이 개발되었다. 이러한 알고리즘은 과거의 데이터를 바탕으로 미래의 접근 패턴을 추정하기 때문에 최적 근접 알고리즘 optimal approximation algorithm이라고 부른다.
LRU 페이지 교체 알고리즘: 페이지에 접근한 시간을 기준으로 대상 페이지를 선정한다.
LFU 페이지 교체 알고리즘: 페이지가 사용된 횟수를 기준으로 대상 페이지를 선정한다.
LRU페이지 교체 알고리즘
Least Recently Used page는 '최근 최소 사용 페이지 교체 알고리즘'이라고도 한다. 메모리에 올라온 이후 가장 오랫동안 상용되지 않은 페이지를 스왑 영역으로 옮기는데 최근에 사용된 페이지는 놔두고 오래전에 사용된 페이지를 대상 페이지로 선정한다.
페이지 접근 시간에 기반한 구현
LRU 페이지 교체 알고리즘의 가장 간단한 형태는 페이지에 접근한 시간을 기록하여 구현한 것이다. FIFO는 페이지 교체 알고리즘이 메모리에 올라온 시간을 기준으로 가장 오래된 페이지를 교체한다면, LRU페이지 교체 알고리즘은 페이지에 접근한 지 가장 오래된 페이지를 교체한다.
참조 비트 시프트 형식
LRU페이지 교체 알고리즘을 실제로 구현하기 위해 참조 비트 시프트 reference bit shift방식을 사용할 수도 있다. 참조 비트 시프트 방식은 각 페이지에 일정 크기의 참조 비트를 만들어 사용하는 것이다. 참조 비트의 초깃값은 0이며 페이지에 접근할 때마다 1로 바뀐다. 또한 참조 비트는 주기적으로 오른쪽으로 한 칸씩 이동한다. shift
LFU페이지 교체 알고리즘
Least Frequently Used은 '최소 빈도 사용 알고리즘'이라고도 한다. LFU페이지 교체 알고리즘은 페이지가 몇 번 사용되었는지를 기준으로 대상 페이지를 선정한다. 다시 말해 현재 프레임에 있는 페이지마다 그동안 사용한 횟수를 세어 횟수가 가장 적은 페이지를 스왑 영역으로 옮긴다.
LFU 페이지 교체 알고리즘의 단점은 LRU 페이지 교체 알고리즘과 마찬가지로 낭비되는 메모리 공간이 많다는 것이다. 페이지 접근 횟수를 표시하는데 추가 공간이 필요하므로 그 만큼 메모리가 낭비된다.
NUR페이지 교체 알고리즘
Not Used Recently Page replacement algorithm은 LRU, LFU페이지 교체 알고리즘과 성능이 거의 비슷하면서도 불필요한 공간 낭비 문제를 해결하였다. NUR페이지 교체 알고리즘과 성능이 거의 비슷하면서도 불필요한 공간 낭비 문제를 해결하였다. NUR 페이지 교체 알고리즘은 '최근 미사용 페이지 교체 알고리즘'이라고도 불린다.
참조 비트: 페이지에 접근 read/execute 하면 1이 된다.
변경 비트: 페이지가 변경 write/append 되면 1이 된다.
모든 페이지 초기 상태는 (0,0)이다. 이 상태에서 페이지에 읽기 또는 실행 같은 '접근'이 발생하면 (1,0)으로 바뀐다. 만약 페이지에 쓰기 또는 추가 같은 '변경'이 일어나면 (0,1)이 된다. 또한 접근과 변경 두 가지 연산이 다 발생하면 (1,1)이 된다.
이때 NUR페이지 교체 알고리즘에서 모든 페이지가 (1,1)이 되면 모든 페이지 비트를 (0,0)으로 초기화된다.
FIFO 변형 알고리즘
FIFO단점을 개선한 알고리즘 2차 기회 페이지 교체 알고리즘과 시계 알고리즘이 있다.
2차 기회 페이지 교체 알고리즘
2차 기회 페이지 교체 알고리즘은 FIFO페이지 교체 알고리즘과 마찬가지로 큐를 사용하지만 , 특정 페이지에 접근하여 페이지 부재 없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동하여 대상 페이지에서 제외한다는 차이점이 있다. 다시 말해 성공한 페이지를 큐의 맨 뒤로 옮김으로써 기회를 한 번 더 준다.
시계 알고리즘
clock algorithm은 2차 기회 페이지 교체 알고리즘과 유사하여 두 알고리즘을 같은 알고리즘으로 보기도 하지만 실제 구현은 서로 다르다. 2차 기회 페이지 교체 알고리즘은 큐를 사용하지만 시계 알고리즘은 원형 큐를 사용하는 것이 가장 큰 차이점이다. 시계 알고리즘에서는 스왑 영역으로 옮길 대상 페이지를 가리키는 포인터를 사용하는데, 이 포인터가 큐의 맨 아래로 내려가면 다음번에는 다시 큐의 처음을 가리키게 된다.
퀴즈
1. 시간상 가장 먼저 들어온 페이지를 대상 페이지로 선정하여 스왑 영역 최근 접근 영억은?
2. 페이지에 접근한 시간을 기준으로 대상 페이지를 선정하는 것은?
3. 페이지가 사용된 횟수를 기준으로 대상 페이지를 선정한다.
4. LRU에서 사용하는 방식으로 각 페이지에 일정 크기의 참조 비트를 만들어 사용하는 것을 무엇이라 하는가?
5. 페이지에 접근 read/execute 하면 1이 된다는 것을 무슨 비트라고 하는가?
6. 페이지가 변경 write/append 되면 1이 된다는 것을 무슨 비트라고 하는가?
7. NUR페이지 교체 알고리즘에서 모든 페이지가 (1,1)이 되면 모든 페이지 비트는 무엇이 되는가?
8. NUR말고 또다른 이름은 무엇인가?
9. LRU,LFU,NUR를 묶어서 부르는 것을 무슨 알고리즘이라고 하는가?
10. 성공한 페이지를 큐의 맨 뒤로 옮김으로써 기회를 한 번 더 준다. 무슨 알고리즘 인가?
11. 스왑 영역으로 옮길 대상 페이지를 가리키는 포인터를 사용하는데, 이 포인터가 큐의 맨 아래로 내려가면 다음번에는 다시 큐의 처음을 가리키게 된다. 무슨 알고리즘 인가?
