캐시 교체 정책 & 페이지 교체 알고리즘

별점: ★★★★★ | 기본 필수

답안.

Ⅰ. 개요

FIFO에서 프레임 수 ↑ → 페이지 폴트 ↑ 역설 예) 참조열: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 프레임 4: 페이지 폴트 10번 (더 나쁨!)

Ⅱ. 핵심 구성요소

FIFO에서 프레임 수 ↑ → 페이지 폴트 ↑ 역설

예) 참조열: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
프레임 3: 페이지 폴트 9번
프레임 4: 페이지 폴트 10번 (더 나쁨!)

원인: FIFO가 지역성을 고려하지 않기 때문
해결: LRU, Clock 알고리즘 사용

[카운터 방식]
각 페이지에 접근 시간 기록
최소 카운터 = 가장 오래된 = 교체 대상
오버헤드: 비교 연산 많음

[스택 방식]
참조 시마다 스택 최상단으로 이동
스택 바닥 = 가장 오래된 = 교체 대상

[Clock 알고리즘 (근사 LRU)]
원형 큐 + 참조 비트(R bit)
  접근 시: R=1 설정
  교체 시: R=1이면 0으로 초기화 후 이동
           R=0이면 교체

실제 OS: Clock 또는 변형 알고리즘 사용

해당 키워드의 기술적 구성요소와 동작 원리를 서술한다.

Ⅲ. 특징 및 비교

핵심 기술의 장단점과 유사 기술과의 차이를 분석한다.

Ⅳ. 적용 사례

실무 환경에서의 적용 사례와 기대효과를 제시한다.

Ⅴ. 전망

최신 기술 동향과 향후 발전 방향을 서술한다.