에듀테크 프로젝트 대시보드
페이지 교체 알고리즘 (Page Replacement)
운영체제는 프로그램의 메모리를 페이지 단위로 잘라 관리한다. 실제 RAM(물리 프레임)은 프로그램 전체보다 작아서, 필요한 페이지만 올려 쓴다. 그런데 프레임이 꽉 찬 상태에서 새 페이지가 필요해지면(페이지 폴트) 지금 있는 페이지 중 하나를 골라 내보내야 한다. "누구를 내보낼까?"를 정하는 규칙이 페이지 교체 알고리즘이다.
참조 문자열은 프로세스가 접근하는 페이지 번호를 시간 순으로 나열한 것이다. 「한 스텝」을 누르면 다음 페이지를 참조한다. 이미 프레임에 있으면 적중(hit), 없으면 폴트(fault)가 나고 알고리즘 규칙대로 한 칸을 비운다.
| 알고리즘 | 내보낼 페이지 선택 기준 | 필요한 정보 | 메모 |
|---|---|---|---|
| FIFO | 가장 먼저 들어온 페이지 (큐의 맨 앞) | 적재 순서 | 구현이 가장 쉽다. Belady의 역설이 나타날 수 있다. |
| OPT | 앞으로 가장 나중에 다시 쓰일(또는 안 쓰일) 페이지 | 미래 전체 | 이론상 폴트 최소. 미래를 알아야 하므로 실제로는 불가능, 성능 상한 비교용. |
| LRU | 가장 오래전에 마지막으로 쓰인 페이지 | 과거 사용 시각 | OPT의 좋은 근사(과거로 미래를 추측). 정확 구현은 비용이 큼. |
| CLOCK | 시곗바늘이 가리키는 페이지 중 참조 비트 R=0 인 첫 페이지 | 페이지당 1비트 | LRU의 값싼 근사(2차 기회). 실제 OS가 쓰는 방식. |
R 비트를 1로 켠다. 폴트가 나면 바늘이 가리키는 페이지를 본다: R=1 이면 "한 번 봐준다"며 R=0 으로 끄고 바늘을 다음 칸으로. R=0 인 페이지를 만나면 그 자리를 교체한다.
상식적으로 프레임(=RAM)을 늘리면 페이지 폴트는 줄어야 한다. LRU·OPT는 실제로 항상 그렇다(스택 알고리즘). 그런데 FIFO는 프레임을 늘렸는데 폴트가 오히려 늘어나는 경우가 있다. 아래는 그 유명한 예시다.
참조 문자열: 1 2 3 4 1 2 5 1 2 3 4 5 · 알고리즘 FIFO
# 해시맵 + 이중 연결 리스트 = O(1) LRU class LRUFrames: def __init__(self, capacity): self.cap = capacity self.order = OrderedDict() # 앞=오래됨, 뒤=최근 self.faults = 0 def access(self, page): if page in self.order: self.order.move_to_end(page) # 최근 사용으로 갱신 → hit return "hit" self.faults += 1 if len(self.order) >= self.cap: self.order.popitem(last=False) # 맨 앞(LRU) 제거 self.order[page] = True return "fault"