페이지 교체 알고리즘이란?
필요한 페이지가 메모리에 없을 때 page-fault가 발생하고 Backing Store에서 해당 페이지를 찾아 빈 프레임에 로딩해야 하는데, 이때 빈 프레임이 없을 경우 희생 당할 프레임(victim frame)을 고르는 알고리즘이 페이지 교체 알고리즘이다.
page-fault의 발생 비율을 줄이는 것이 펭디지 교체 알고리즘의 목표라고 할 수 있다.
운영체제의 스와퍼는 물리 메모리에 동작하고 있는 모든 프로세스를 로드하지 않고 운영체제의 페이저는 프로세스의 모든 페이지를 물리메모리에 로드하지 않는다. (물리메모리를 효율적으로 사용하기 위해서) 그래서 프로그램의 페이지가 물리 메모리에 부재할 수 있는데 이것을 page-fault라고 한다.
page-fault가 발생하게 되면 해당 페이지를 가상 메모리 내에서 찾아야 하는데 이렇듯 운영체제가 page-fault를 해결하는 과정을 요구 페이징(Demand Paging)이라고 한다.
만약 물리 메모리상에 비어있는 프레임이 없다면 희생 프레임을 골라 이를 가상 메모리에 저장한 후 필요 페이지를 물리 메모리에 로드해야 한다. 이 과정에서 페이지 교체 알고리즘이 사용된다.
페이지 교체 알고리즘 종류
FIFO (선입선출 페이지 교체 알고리즘)
- 시간상으로 메모리에 가장 먼저 들어온 페이지를 대상 페이지로 선정하여 스왑 영역으로 쫓아낸다.
- 메모리가 꽉 차게 되면 맨 위의 페이지(제일 먼저 들어왔던 오래된 페이지)가 스왑 영역으로 가고 나머지 페이지들이 위쪽으로 이동하며 새로운 페이지가 아래쪽 공간으로 들어온다.
- 오래된 페이지가 자주 사용되는 페이지일지라도 무조건 오래된 페이지를 대상 페이지로 선정하기 때문에 성능이 떨어진다.
OPT (최적 페이지 교체 알고리즘)
- 앞으로 사용하지 않을 페이지를 스왑 영역으로 옮긴다.
- 메모리가 앞으로 사용할 페이지를 미리 살피고 페이지 교체 선정시점부터 사용 시점까지 가장 멀리 있는 페이지를 대상 페이지로 선정한다.
- 이상적인 방법이지만, 실제로 구현할 수 없다.
- 위 사진에서 보면 4번째 페이지 요구에서 A, B, C 중 C가 9번째에 필요한 페이지로 가장 늦게 필요하기 때문에 C를 스왑 영역으로 보낸다.
LRU (최근 최소 사용 페이지 교체 알고리즘)
- 메모리에 올라온 후 가장 오랫동안 사용되지 않는 페이지를 스왑영역으로 옮긴다.
- 최근에 사용된 페이지는 놔두고 오래전에 사용된 페이지를 대상 페이지로 선정한다.
- 해당 알고리즘은 시간을 기준으로 구현할 수 있으며 카운터나 참조비트를 이용하는 방법도 있다.
- 위 사진에서 보면 4번째 페이지 요구에서 A, B, C 중 A가 가장 최근에 1번째 페이지 요구에서 사용되었기 때문에 A를 스왑 영역으로 보낸다.
페이지 접근 시간에 기반한 구현
- 페이지에 접근한 시각을 기록하여 판단하는 것이다.
- 메모리가 추가적으로 필요하다는 단점이 있다.
카운터에 기반한 구현
- 메모리를 추가적으로 사용해서 페이지에 접근한 시각이 아닌 몇 번째로 접근했는지를 기록하는 것이다.
- 페이지 접근 시간을 기록하는 방식과 큰 차이가 없다.
- 메모리가 추가적으로 필요하다는 단점이 있다.
참조 비트 시프트 방식
- 페이지에 일정 크기의 참조 비트를 만들어 사용하는 것이다.
- 참조 비트의 초기값은 0이며 페이지에 접근할 때마다 1로 바뀐다.
- 참조 비트는 주기적으로 한칸씩 오른쪽으로 시프트된다.
- 메모리가 추가적으로 필요하다는 단점이 있다.
- 위 사진에서 보면 (c) 시점에서 C가 가장 최근에 사용되지 않았으므로 C가 대상 페이지가 된다. (참조 비트 값중 가장 작은 값을 대상 페이지로 선정한다.)
- LFU과 다른점은 가장 많은 페이지 접근을 가진 C임에도 불구하고 참조 비트값이 가장 작기 때문에 대상 페이지로 C가 선정된다는 점이다.
LFU (최소 빈도 사용 페이지 교체 알고리즘)
- 페이지가 몇 번 사용되었는지를 기준으로 대상 페이지를 선정한다.
- 현재 프레임에 있는 페이지마다 그동안 페이지가 사용된 횟수를 세어 횟수가 가장 적은 페이지를 스왑 영역으로 옮긴다.
- 페이지 접근 횟수를 표시하는데에 추가 공간이 필요하므로 메모리가 낭비되지만 FIFO보다 성능은 우수하다.
- 위 사진에서 보면 5번째 페이지 요구에서 B가 두번째로 요구되었으므로 B 아래 있는 접근 횟수를 1에서 2로 바꾸어주는 것을 확인할 수 있다.
MFU (최대 빈도 사용 페이지 교체 알고리즘)
- 이 알고리즘은 LFU와 반대로 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘이다.
NUR (최근 미사용 페이지 교체 알고리즘)
- LRU, LFU는 알고리즘 성능은 좋으나 추가 메모리 공간이 필요하여 오버헤드가 크기 때문에 NUR은 이를 개선한 방식이다.
- 페이지마다 참조비트와 변경비트를 주어 페이지에 접근하면 참조비트를 1로 만들어주고 페이지가 변경되면 변경비트를 1로 만들어준다.
- 초기 상태는 (0. 0)이지만 모든 페이지가 (1, 1)이 되면 (0, 0)으로 초기화된다.
- 대상 페이지를 찾을 때 참조비트가 0인 페이지를 먼저 찾고, 없으면 변경 비트가 0인 페이지를 찾는다.
- 같은 비트의 페이지가 여러개라면 무작위로 대상 페이지를 선정한다.
2차 기회 페이지 교체 알고리즘(FIFO 변형)
- FIFO와 마찬가지로 큐를 사용하지만 특정 페이지에 접근하여 페이지 부재 없이 성공할 경우 해당 페이지를 큐의 맨 뒤로 이동하여 대상 페이지에서 제외시킨다.
- 위 사진에서 보면 5번째 페이지 요구에서 페이지 부재 없이 성공했는데, 이때 맨 위에 있던 B를 맨 아래로 보내준다.
시계 알고리즘
- 2차 기회 페이지 교체 알고리즘에 비해 각 페이지에 참조 비트가 하나씩 추가된다.
- 참조 비트의 초기값은 0으로 메모리에 있는 페이지를 성공적으로 참조하면 0에서 1로 변경한다.
- 대상 포인터는 메모리가 꽉 찰 경우 스왑 영역으로 쫓겨날 페이지를 가리킨다. (원형 큐를 사용)
- 가리키는 페이지가 스왑 영역으로 쫓겨나면 대상 포인터를 밑으로 이동시키는데 이때 참조비트가 1인 페이지는 0으로 만든 후 건너뛴다.(2차 기회를 준다)
실제 운영체제가 선택하는 알고리즘
Linux, Windows, macOS와 같은 대표적인 운영체제들은 LRU와 시계 알고리즘을 혼용해서 페이지 교체를 한다고 한다. 가장 오랫동안 사용되지 않는 페이지를 찾는데에 효과적이고 최근에 참조된 페이지를 보존하는 데에 효과적인 두 알고리즘의 장점을 조합하여 페이지 교체의 효율성을 높였다고 한다.
기본적으로 LRU을 채택하되 Window는 Clock, 리눅스는 Second Chance, mac은 LRU Approximation을 사용한다고도 한다.
참고
쉽게 배우는 운영체제(조성호 지음)
https://mgyo.tistory.com/483
https://sommda.tistory.com/67
https://rob-coding.tistory.com/37
https://velog.io/@kangdev/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B2%B4-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Page-Replacement-Algorithm
