💡페이지 교체

페이지 부재(page fault)가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어와야 한다. 이때 물리적 메모리에 빈 프레임이 존재하지 않을 수 있습니다. 이 경우 물리적 메모리에 올라와 있는 페이지 중 하나를 선택해서 디스크의 스왑 영역으로 보내야 한다.

스왑이라함은 시스템에 메모리가 부족할 경우 하드 디스크의 일부 공간을 활용해서 작업을 도와주는 영역 → 즉 메모리 공간 부족을 위한 임시방편

이와 같은 과정을 페이지 교체라고 합니다.

💡FIFO(First In First Out) 알고리즘

(페이지에 올라온 순서를 큐에 저장)

페이지 교체 시 물리적 메모리에 가장 먼저 올라온 페이지를 우선적으로 내보내는 알고리즘이다.

• 단점 : 오래전에 적재되었지만 반복적으로 사용되는 페이지가 교체될 수 있다.

활발하게 사용 중인 페이지를 계속해서 교체한다면 페이지 부재율이 높아지고 실행속도가 떨어질
위험이 있다.

💡OPT (Optimal Page Replacement)알고리즘 → 최적 알고리즘

앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 알고리즘이다.

최적 알고리즘은 수행하기 전에 선행되어야 할 전제조건이 있다. 프로세스가 앞으로 사용할 페이지를 미리 알아야 한다는 것이다. 이 전제 조건이 실제 활용에서는 알 방법이 없기 때문에 최적 알고리즘은 구현이 불가능한 알고리즘 이다.

때문에 이 알고리즘은 실제 구현 목적보다 다른 알고리즘과 비교 연구 목적을 위해 주로 사용된다.

💡LRU(least-recently-used)알고리즘

가장 오래 사용되지 않은 ****페이지를 교체하는 알고리즘이다.

→ 직역하면 '최근 최소 사용 페이지 교체 알고리즘이라고도 한다

최적 알고리즘은 실제 구현이 불가능하므로, 최적 알고리즘의 방식과 비슷한 효과를 낼 수 있는 방법
을 사용한 것이 LRU 알고리즘이다. 최근에 사용하지 않았으면, 나중에도 사용되지 않을 것이라는 아이디어에서 나왔다.

최적 알고리즘은 페이지가 사용될 시간을 미리 알고 있다. 미리 아는 것이 불가능하다면, 과거의 데이터를 바탕으로 페이지가 사용될 시간을 예측하여 교체하는 것은 가능하다. 예측 방법으로 가장 오랜 기간 사용되지 않은(least recently used) 페이지를 교체하는 방식을 사용하는 것이다.

각 페이지마다 타임- 스탬프용 카운터를 두어서 현시점에서 가장 오래 전에 사용된 페이지를 제거

💡LFU (Latest Frequently Used page replacement)알고리즘

'최소 빈도 사용 알고리즘' 이라고도 한다. LFU 페이지 교체 알고리즘은 페이지가 몇 번 사용 되었는 지를 기준으로 대상 페이지(victim page)를 선정한다. 다시 말해 현재 프레임에 있는 페이지마다 그 동안 사용된 횟수를 세어 횟수가 가장 적은 페이지를 스왑 영역으로 옮긴다.

💡NUR (Not Recently page replacement )알고리즘

LRU, LFU 페이지 교체 알고리즘 성능이 거의 비슷하면서도 불필요한 공간 낭비 문제를 해결한 알고리즘이다. NUR 페이지 교체 알고리즘은 '최근 미사용 페이지 교체 알고리즘'이라고도 불린다.

[OS] 페이지 교체 알고리즘 (FIFO, LRU, LFU, NRU, NUR)

참고

페이지 교체(page-replacement) 알고리즘

[OS] 페이지 교체 알고리즘 - FIFO/LRU/LFU/MFU/NUR