페이지 교체 알고리즘
-
운영체제에서 주기억장치보다 더 큰 용량의 프로그램을 실행하기 위해서 가상메모리 기법을 활용해서 처리함
-
이때 페이징 기법으로 메모리를 관리하는 운영체제에서는 필요한 페이지를 요구할 때 해당 페이지를 물리 메모리에 로딩함
-
여기서 필요한 페이지가 잘 있으면 문제가 없지만, 없을 경우에 이 페이지를 찾아 빈 프레임에 로딩하는데 여기서 또 페이지를 올릴 빈 프레임이 없을 경우가 있음
-
이때 새로 올릴 페이지와 교체할 프레임을 찾는 알고리즘을 페이지 교체 알고리즘이라고 함
FIFO(First In First Out)
-
가장 간단한 알고리즘으로, 메모리에 올라온 지 가장 오래된 페이지를 교체함
-
이 알고리즘을 수행하기 위해서 각 페이지가 올라온 시간을 페이지에 기록하거나 페이지가 올라온 순서를 큐에 저장하는 방식을 사용할 수 있음
-
이해가 쉽고 구현이 간단함
- 하지만 성능이 항상 좋다고 장담할 수 없음, 위의 예시를 보면 페이지 7의 경우 프로세스 초기에 쓰고 안 써서 교체해서 문제가 없지만
- 위와 같이 페이지 4와 페이지 2가 교체되고 또 다시 페이지 2를 사용하려고 다시 불러들임, 이런식으로 사용중인 페이지를 계속해서 교체하면 페이지 부재율이 높아지고 실행속도가 떨어질 위험이 있음
OPT(Optimal)
-
앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 알고리즘임
-
이 알고리즘을 수행하기 전에 선행되어야 할 전제조건이 있는데 프로세스가 앞으로 사용할 페이지를 미리 알아야 한다는 것임
-
하지만 이 전제 조건이 실제 활용에서 알 방법이 없기 때문에 최적 알고리즘은 구현이 불가능한 알고리즘임, 그래서 실제 구현 보다 다른 알고리즘과 비교 연구 목적을 위해 사용함
-
최적 교체 알고리즘은 가장 오랫동안 사용되지 않을 페이지를 알고 교체하기 때문에 모든 페이지 교체 알고리즘을 통틀어 가장 페이지 교체 수가 적음
-
페이지 7의 경우 나중에 쓰일 것을 미리 알고 있어서 페이지 2와 교체함, 페이지 1 역시도 마찬가지
LRU(Least Recently Used)
-
가장 오래 사용되지 않은 페이지를 교체하는 알고리즘
-
최적 알고리즘에서 처럼 페이지가 사용될 시간을 미리 알고 있는 것은 불가능하지만, 과거의 데이터를 바탕으로 페이지가 사용될 시간을 예측하여 교체하는 것은 가능함
-
예측 방법으로 가장 오랜 기간 사용되지 않은 페이지를 교체하는 방식을 사용하는 것임
-
이는 페이지마다 카운터가 있고, 큐로 구현하여서 사용한 데이터를 큐에서 제거하여 맨 위로 다시 올리고, 프레임이 모자랄 경우 맨 아래에 있는 데이터를 삭제함
-
하지만 그만큼 페이지 시간을 계속 기록해야 하므로 오버헤드가 발생할 수 있음
-
최적 알고리즘보다 교체 횟수가 높지만 FIFO보다 효율적임
-
{2, 0, 3}인 상황에서 가장 오랫동안 사용되지 않은 페이지 2를 페이지 4와 교체함 -
{4, 3, 2}인 상황에서도 페이지 4가 가장 오랫동안 사용되지 않았으므로 0과 교체함
LFU(Least Frequently Used)
-
페이지 참조 시마다 각 페이지가 현재까지 참조된 횟수를 카운팅할 수 있는데 LFU는 참조 횟수가 가장 작은 페이지를 교체하는 알고리즘임
-
만약 교체 대상인 페이지가 여러 개일 경우, LRU 알고리즘에 따라 가장 오래 사용되지 않은 페이지로 교체함, 아래와 같이
- 단, 여기서 초기에 한 페이지를 집중적으로 참조하다가 이후 다시 참조하지 않는 경우 문제가 될 수 있음, 앞으로 사용하지 않아도 초기에 사용된 참조 횟수가 높아 메모리에 계속 남아있는 것임(아래와 같이)
MFU(Most Frequently Used)
-
LFU 알고리즘과 반대로, 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘임
-
참조 횟수가 적은 페이지가 최근에 사용된 것이기 때문에 앞으로 사용될 가능성이 높다는 판단임
교체 방식
-
Global 교체 : 메모리 상의 모든 프로세스 페이지에 대해 교체하는 방식
-
Local 교체 : 메모리 상의 자기 프로세스 페이지에서만 교체하는 방식
-
다중 프로그래밍의 경우, 메인 메모리에 다양한 프로세스가 동시에 올라올 수 있음, 따라서 다양한 프로세스의 페이지가 메모리에 존재함
-
이것은 기준에 따라 다 다르고 방식도 다름 하지만 효율적인 부분에 따라 다름(전체를 기준으로 페이지를 교체하는 것이 더 효율적이라고 함, 자기 프로세스 페이지에서만 교체하면 교체를 해야할 때 각각 모두 교체를 진행해야 하므로 비효율적임)
