페이지 교체 알고리즘
운영체제는 주기억장치보다 더 큰 용량의 프로그램을 실행하기 위해 프로그램의 일부만 주기억장치에 적재하여 사용한다. 이를 가상메모리 기법이라 한다.
페이징 기법으로 메모리를 관리하는 운영체제에서 필요한 페이지가 주기억장치에 적재되지 않았을 시 (페이지 부재), 어떤 페이지 프레임을 선택하여 교체할 것인지 결정하는 방법을 페이지 교체 알고리즘이라 한다.
페이지 교체 알고리즘은 스왑 영역으로 보낼 페이지를 결정하는 알고리즘으로, 메모리에서 앞으로 사용할 가능성이 적은 페이지를 대상 페이지로 선정하여 페이지 부재를 줄이고 시스템의 성능을 향상한다.
페이지 교체 알고리즘의 종류
1. OPT - Optimal: 미래의 메모리 접근 패턴을 보고 대상 페이지를 선정하여 스왑 영역으로 보낸다.
2. FIFO - First In First Out
3. LRU - Least Recently Used: 가장 오랫동안 사용되지 않은 페이지 교체
4. LFU - Least Frequently Used: 사용 빈도가 적은 페이지를 스왑 영역으로 보낸다.
5. MFU - Most Frequently Used: 참조 횟수가 가장 많은 페이지 교체
6. NUR - Not Used Recently: 최근에 사용하지 않은 페이지 교체
OPT (Optimal)
앞으로 가장 오랫동안 사용되지 않을 페이지 교체
가장 이상적이지만, 프로세스가 앞으로 사용할 페이지를 미리 알아야 하기 때문에 불가능에 가깝다.
비교 연구 목적을 위해 사용된다.
FIFO (First In First Out)
가장 먼저 들어온 페이지를 교체
간단하고 초기화 코드에 대해 적절한 방법이다.
들어온 시간, 혹은 올라온 순서를 큐에 저장한다.
직관적으로 생각할 때, 프레임의 수가 많아질 수록 페이지 결함 횟수는 감소한다.
메모리에 올라온 시간만 고려하기 때문에 자주 사용되는 페이지가 스왑 영역으로 옮겨지기도 한다.
이러한 문제를 개선한 것이 2차 기회 페이지 교체 알고리즘이다.
LRU (Least Recently Used)
가장 오랫동안 사용되지 않은 페이지 교체
FIFO 페이지 교체 알고리즘이 메모리에 올라온 시간을 기준으로 가장 오래된 페이지를 교체한다면, LRU 페이지 교체 알고리즘은 페이지에 접근한 지 가장 오래된 페이지를 교체한다.
가장 오랫동안 사용하지 않았던 데이터라면, 앞으로도 사용하지 않을 확률이 높다고 가정한다.
시간 지역성 성질을 고려한다. (최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높은 성질)
프로세스가 주기억장치에 접근할 때마다 참조된 페이지 시간을 기록해야 하므로 막대한 오버헤드가 발생한다.
접근 시간이나 참조 비트를 유지하기 위한 메모리가 추가로 필요하기 때문에 낭비되는 메모리 공간이 많다.
LFU (Least Frequently Used)
페이지가 사용된 횟수를 기준으로 대상 페이지를 선정한다.
LRU는 직전 참조의 시점만을 반영하지만, LFU는 참조횟수를 통해 장기적 시간 규모에서의 참조 성향을 고려할 수 있다.
하지만, 가장 최근에 불러온 페이지가 교체될 수 있으며, 구현이 더 복잡하고 막대한 오버헤드가 발생한다.
LRU 페이지 교체 알고리즘과 마찬가지로 낭비되는 메모리 공간이 많다.
페이지 접근 횟수를 표시하는 데 추가 공간이 필요하므로 그만큼 메모리가 낭비된다.
MFU (Most Frequently Used)
참조 횟수가 가장 많은 페이지 교체
가장 많이 사용된 페이지가 앞으로는 사용되지 않을 것이라고 가정한다.
NUR (Not Used Recently)
최근에 사용하지 않은 페이지 교체
LRU와 근사한 알고리즘으로, 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 못한다.
LRU, LFU 페이지 교체 알고리즘과 성능이 거의 비슷하면서 불필요한 공간 낭비 문제를 해결한 알고리즘이다.
페이지마다 참조 비트와 변경 비트를 가지기 때문에 페이지마다 추가되는 메모리 공간이 2비트 뿐이다.
- 참조 비트: 페이지에 접근(Read/Execute)하면 1이 된다.
- 변경 비트: 페이지가 변경(Write/Append)되면 1이 된다.
모든 페이지의 초기 상태는 (0, 0)이다.
이 상태에서 페이지에 읽기 또는 실행과 같은 '접근'이 발생하면 (1, 0)이 된다.
만약 페이지에 쓰기 또는 추가 같은 '변경'이 일어나면 (0, 1)이 된다.
또한 접근과 변경, 두 가지 연산이 다 발생하면 (1, 1)이 된다.
NUR 페이지 교체 알고리즘에서 우선 고려 대상은 참조 비트이다.
참조 비트가 0인 페이지를 먼저 찾고, 변경 비트가 0인 페이지를 찾는다.
만약 같은 비트의 페이지가 여러 개라면, 무작위로 대상 페이지를 선정한다.
흔한 경우는 아니지만, 모든 페이지의 비트가 (1, 1)일 때는 어떤 페이지가 더 자주 사용되는지 알 수 없어 NUR 페이지 교체 알고리즘을 정상적으로 적용할 수 없다.
그러므로 모든 페이지가 (1, 1)이 되면 모든 페이지 비트를 (0, 0)으로 초기화한다.
클럭 (Clock) 알고리즘
클럭 알고리즘은 FIFO 알고리즘의 문제점을 보완하기 위해 고안된 방식이다.
FIFO처럼 순차적으로 페이지를 확인하지만, 단순히 가장 오래된 페이지를 교체하지는 않는다.
각 페이지에 참조 비트(R)가 존재하며, 시계 모양의 원형 큐를 사용하여 포인터가 R=0인 페이지를 찾을 때까지 이동한다.
한 번 참조된 페이지(R=1)는 즉시 제거되지 않고 다시 기회를 가진다. (Second Chance Algorithm 이라고도 불린다.)
- 페이지가 참조되면 해당 페이지의
R비트를 1로 설정 - 페이지를 교체해야 할 때, 시계 모양의 원형 리스트(Queue)에서 포인터가 가리키는 페이지를 확인
- R=0이면 해당 페이지를 교체
- R=1이면 R을 0으로 만들고 포인터를 다음 페이지로 이동
- R=0인 페이지를 찾을 때까지 반복
- 해당 페이지를 교체하고, 포인터를 다음 페이지로 이동
FIFO는 가장 오래된 페이지를 무조건 제거하지만, 클럭 알고리즘은 최근에 사용된 페이지(R=1)를 다시 살릴 기회를 주는 것이 차이점이다.
클럭 알고리즘은 FIFO의 단순함과 LRU의 성능 사이에서 절충된 페이지 교체 방식으로, 운영체제에서 자주 사용되는 알고리즘 중 하나이다.
클럭 알고리즘과 NUR 알고리즘의 차이는?
클럭 알고리즘은 FIFO를 보완한 단순한 페이지 교체 기법으로,R비트만을 사용해 비교적 가볍게 동작한다.
NUR 알고리즘은R비트와M비트를 함께 활용하여 디스크 입출력을 줄이고 최적의 교체 대상 페이지를 찾는 방식이지만, 주기적인 비트 초기화 과정이 필요하다.
속도가 중요하면 클럭 알고리즘을, 효율적인 페이지 관리가 중요하면 NUR 알고리즘을 선택하는 것이 좋다.
페이지 부재를 최소화하려면 어떻게 해야 하나요?
적절한 페이지 교체 알고리즘을 적용해서 페이지 부재를 최소화해야 합니다.
페이지 교체 알고리즘에는 다양한 방식이 존재합니다.
클럭 알고리즘
특정 시간동안 다시 참조되지 않은 페이지를 교체하는 방식입니다. 이 알고리즘은 하드웨어적인 지원으로 동작하기 때문에, 효율적이고 빠릅니다.
이 때문에 대부분의 시스템에서 클럭 알고리즘을 사용하고 있는 것으로 알고 있습니다.선입선출(FIFO) 알고리즘
물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫓는 방식입니다.LRU 알고리즘
가장 오래전에 참조가 이루어진 페이지를 쫓아내는 방식입니다.LFU 알고리즘
참조 횟수가 가장 적은 페이지를 쫓아내는 방식입니다.
Swapping이란 무엇인가요?
하드디스크의 일부를 RAM처럼 사용하는 기법입니다.
메모리 공간이 부족할 때, 실행 중인 프로세스를 다른 저장 장치로 옮겨두는 메모리 관리 기법입니다.
Swapping의 과정을 설명해주세요.
중기 스케줄러가 스왑 아웃할 프로세스를 선정합니다.
그리고 스왑 아웃 대상으로 선정된 프로세스는 현재 메모리에 올라가 있는 주소 공간의 내용을 통째로 디스크 스왑 영역으로 스왑 아웃 당하게 됩니다.
여유가 생긴 메모리 공간에 필요한 프로세스의 메모리 주소 공간을 스왑 인 시킵니다.
Swapping의 장단점을 설명해주세요.
장점은 물리적인 RAM이 부족할 때 디스크를 활용하여 실행 중인 프로세스를 더 많이 유지할 수 있습니다.
또한 여러 프로세스를 동시에 실행할 때, 당장 필요하지 않은 프로세스를 디스크로 옮겨 메모리를 확보할 수 있습니다.
단점은 디스크 입출력 속도는 RAM보다 훨씬 느리므로, 프로세스를 디스크에서 다시 불러오는 과정에서 시스템 성능이 저하될 수 있습니다.
또한 자주 참조되는 데이터를 스왑 아웃하면 페이지 폴트가 증가하여 시스템 속도가 느려질 수 있습니다.
페이지 교체 알고리즘 FIFO에 대해 설명해주세요.
FIFO 알고리즘은 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내쫓는 방식입니다.
페이지 교체 알고리즘 LRU에 대해 설명해주세요.
LRU는 페이지 교체시 가장 오래전에 참조되었던 페이지를 메모리에서 쫓아 냅니다.
최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높다는 시간 지역성이란 성질을 활용한 알고리즘입니다.
하지만 과거로부터 가장 많이 참조되었지만 가장 오래전에 참조 되었던 페이지를 내쫓는 경우가 발생할 수 있습니다.
페이지 교체 알고리즘 LFU에 대해 설명해주세요.
LFU는 페이지 교체시 가장 적게 참조되었던 페이지를 메모리에서 쫓아냅니다.
페이지가 메모리에 올라온 이후부터 참조 횟수를 카운트하는 인캐시 LFU가 있고, 페이지의 과거 총 참조 횟수를 카운트하는 퍼팩트 LFU가 있습니다.
하지만 가장 최근에 불러온 페이지가 교체될 수 있으며, 페이지 접근 횟수를 표시하는데 추가 공간이 필요하므로 그만큼 메모리가 낭비된다는 문제가 있습니다.
페이지 교체 알고리즘 클럭 알고리즘에 대해 설명해주세요.
클럭 알고리즘은 오랫동안 참조되지 않은 페이지를 내쫓는 알고리즘입니다.
LRU를 근사시킨 알고리즘이라고 할 수 있습니다.
현재 메모리에 적재된 페이지들의 참조 비트 정보를 원형으로 배치시키고, 시계방향으로 따라가며 참조 비트를 확인합니다.
참조 비트가 1인 경우에는 참조비트를 0으로 바꾼 후 지나갑니다.
참조 비트가 0인 경우에는 해당 페이지를 교체합니다.
자주 사용되는 페이지라면 시계방향으로 한 바퀴 확인하는 동안 참조 비트가 1로 세팅되어 교체되지 않으므로 클럭 알고리즘은 최근에 참조가 일어나지 않은 페이지를 교체하는 알고리즘이라고 할 수 있습니다.
