페이지 교체 알고리즘
요구 페이징 환경에서 메모리에 빈 프레임이 없을 때, 새로운 페이지를 적재하기 위해 어떤 페이지를 제거할지 결정하는 알고리즘이 페이지 교체 알고리즘입니다.
기본 원리 (Basic Goal)
페이지 교체의 주된 목표는 페이지 부재율(page-fault rate)을 최소화하는 것입니다. 이상적으로는 앞으로 가장 오랫동안 사용되지 않을 페이지를 희생자(victim)로 선택해야 합니다.
페이지 교체 과정:
빈 프레임을 찾습니다.
빈 프레임이 없다면, 페이지 교체 알고리즘을 사용하여 희생자 페이지를 선택합니다.
희생자 페이지를 보조 저장 장치로 스왑 아웃(페이지 아웃)합니다. 페이지 테이블을 수정하고, **수정 비트(modify bit)**를 확인하여 수정되지 않았다면 디스크에 쓸 필요가 없습니다.
새로운 페이지를 확보된 프레임으로 읽어 들이고 페이지 테이블을 업데이트합니다.
프레임 할당 (Frame Allocation)
운영체제는 각 프로세스가 최소한의 페이지를 가질 수 있도록 보장해야 합니다.
최소 프레임 수: 명령어 실행에 필요한 최소한의 페이지 수입니다.
할당 방식:
고정 할당(Fixed Allocation): 프로세스의 크기에 비례하여 프레임을 할당합니다.
우선순위 할당(Priority Allocation): 우선순위가 높은 프로세스는 더 많은 프레임을 할당받습니다.
전역 대 지역 교체 (Global Versus Local Replacement)
지역 교체(Local Replacement): 프로세스가 자신이 할당받은 프레임 내에서만 희생자 페이지를 선택합니다.
전역 교체(Global Replacement): 프로세스가 다른 프로세스에게 할당된 프레임을 포함하여 모든 프레임 중에서 희생자 페이지를 선택할 수 있습니다.
장점: 시스템 전체 스루풋이 높아지고 성능이 향상될 수 있습니다. (대부분의 운영체제가 사용)
페이지 교체 알고리즘의 종류
최적 알고리즘 (Optimal Algorithm, OPT):
원리: 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체합니다.
실현 가능성: 미래를 예측해야 하므로 실현 불가능합니다. 다른 알고리즘의 성능 평가를 위한 기준으로 사용됩니다.
FIFO (First-In, First-Out) 알고리즘:
원리: 가장 오래 전에 메모리에 들어온 페이지를 교체합니다.
단점: 가장 오래된 페이지가 가장 자주 사용되는 페이지일 수 있습니다.
벨라디의 이상(Belady's Anomaly): 프레임 수를 늘려도 페이지 부재율이 증가하는 현상이 발생할 수 있습니다.
LRU (Least Recently Used) 알고리즘:
원리: 가장 오랫동안 사용되지 않은 페이지를 교체합니다. OPT의 실용적인 근사치입니다.
구현 어려움: 카운터나 스택을 사용하여 구현해야 하므로 하드웨어 지원이 필요하며 비용이 비쌉니다.
LRU 근사 알고리즘 (LRU Approximation Algorithms): LRU의 구현 비용을 줄이기 위해 사용됩니다.
이차 기회 알고리즘 (Second-Chance Algorithm): FIFO 알고리즘에 **참조 비트(reference bit)**를 추가합니다. 참조 비트가 1이면 기회를 주고 0으로 바꾼 뒤 다음 페이지를 검사합니다.
개선된 이차 기회 알고리즘: 참조 비트와 **수정 비트(modify bit)**를 결합하여 네 가지 클래스(0,0: 최근 사용X, 수정X ~ 1,1: 최근 사용O, 수정O)로 분류하고 낮은 클래스(0,0)를 우선 교체합니다.
계수 기반 알고리즘 (Counting-Based Algorithms):
LFU (Least Frequently Used): 참조 횟수가 가장 적은 페이지를 교체합니다.
MFU (Most Frequently Used Used): 참조 횟수가 가장 많은 페이지를 교체합니다.
페이지 버퍼링 (Page Buffering): 성능 향상을 위해 교체된 페이지를 디스크로 쓰기 전에 버퍼에 보관합니다.
자유 프레임 리스트: 교체된 프레임들을 리스트에 보관하여, 페이지 오류 발생 시 빠르게 재사용할 수 있습니다.
이 내용이 사용자님의 파일 기준 **10.4장 '페이지 교체 알고리즘'**의 정확하고 완전한 내용입니다. 다음 섹션인 **10.5장 '프레임 할당'**에 대해 계속 진행할까요?
Last updated