운영체제 (OS: Operating System)

본 토픽은 현재 준비중입니다. 공동공부에 참여하시면 완성 되었을 때 알려드립니다.

페이지 교체 알고리즘

FIFO (First In First Out)

가장 오래 있었던 페이지를 교체

벨레이디의 모순 (Belady's anomaly)이 존재 : 페이지 수를 증가시켰는데도 페이지 부재가 더 많이 일어나는 경우

OPT (OPTimal Page Replacement 최적 페이지 교체)

앞으로 가장 오랫동안 사용하지 않을 페이지를 교체

현실적으로 구현 어려움

비교 연구 목적

LRU (Least Recently Used)

가장 오랫동안 사용하지 않은 페이지를 교체

계수기 (Counters) 또는 스택 (Stack) 을 이용하여 구현

LRU 근사

Additional-Reference Bits (부가적 참조 비트 알고리즘)

SCR (Second-Chance Replacement 2차 기회 알고리즘)

Enhanced SCR (개선된 2차 기회 알고리즘)

Count-Based (계수-기반 페이지 교체)

알고리즘 구현 비용이 높고 OPT 에 근사하지 못해 자주 쓰이지 않는다. 

LFU (Least Frequently Used)

사용 빈도가 가장 적은 페이지를 교체

실행 초기에 많이 사용된 페이지가 그 후로 사용되지 않을 경우 프레임을 계속 차지하는 문제점이 있음

참조 회수를 일정한 시간마다 하나씩 오른쪽으로 시프트해서 지수적으로 그 영향력을 감소시켜 보완할 수 있음

MFU (Most Frequently Used)

가장 적은 참조 회수를 가진 페이지가 최근에 메모리로 적재되었고, 앞으로 계속 사용될 것이라는 상황에 사용

댓글

댓글 본문
graphittie 자세히 보기