페이지 교체 알고리즘.md

1. MIN(OPT)

   • 최근 미래에 안 쓰이는거 교체
   • 이론상 베스트인데 실제 상황에선 참조 예측이 안되니 구현 불가능
   • 비교 연구 목적

2. Random 알고리즘

   • 진짜 랜덤

3. FIFO 알고리즘

   • 가장 오래전에 들어온 페이지가 희생자
   • 자주 사용되는 페이지 교체가능성 큼 (지역성 고려 없음)

4. LFU(Least Frequently Used)

   • 사용횟수가 가장 적은 페이지가 희생자
   • 구현 비용이 비싸고 성능 별로
   • 초기에만 많이 쓰는건 교체 잘 안됨
   • 방금 들어온 페이지가 잘 교체됨

5. LRU(Least Recently Used) 알고리즘

   • 가장 오래전에 참조한 페이지가 희생자
   • 지역성에 기반한 알고리즘
   • Stack, Counter 등을 추가 저장해야해서 HW 지원 필요

6. NUR(Not Used Recently)

   • 이론적인 알고리즘
   • LRU보다 적은 오버헤드로 비슷한 성능
   • 참조비트와 변형비트 활용
     • 참조비트: 참조된 적 있는지 여부, 주기적으로 0으로 초기화
     • 변형비트: 변형, 수정된 적 있는지 여부
     • (R,M) (0,0),(0,1),(1,0),(1,1) 순서로 교체 우선순위 높음

7. Clock 알고리즘

   • NUR 실 적용 예
   • 참조비트만 사용(참조시 1로 변경되는 비트) → 주기적 초기화없음
   • 프레임을 순차적으로 가리키는 포인터 사용
   • 포인터가 돌면서 0인 페이지를 교체 대상으로 선정
   • 먼저 적재되었으면서 최근에 참조되지 않은 페이지가 교체됨

8. Second Chance 알고리즘

   • NUR 실 적용 예2
   • Clock + 변형비트
   • 검색 시간 길어짐
   • (0,1) to (0,0)으로 변하는 경우 write-block list에 추가됨

9. Working Set algorithm

   • 특정 기간동안 사용했던 프레임 목록을 적재
   • 프레임 갯수 정해지지 않음
   • Working set: 어떤 시점에 자주 참조하는 page의 집합 (시간에 따라 변함)
   • W(t-Δ, t): [t-Δ, t] 동안 참조된 page의 집합 (Δ는 고정)
   • allocated: 적재된 페이지 수
   • page fault, 평균 allocated 수로 성능 평가함
   • 특징
     • 적재 없어도 반납, 적재 있어도 교체 없는 경우 있음
   • 단점
     • 모니터링으로 인한 오버헤드

10. Page Fault Frequency algorithm

    • residence set size를 page fault rate에 따라 결정
      • page fault 낮으면 frame 수 감소, 높으면 증가
    • Page fault 발생시 inter fault time 계산 (현재 fault 시간 - 이전 fault 시간)
      • inter fault time이 기준치 이상이면 이전 fault 이후 ~ 현재 사이에 쓰였던 것만 유지
      • 기준치 이하면 추가
    • 메모리가 fault일 때만 변화해서 Working set보다 오버헤드 낮음

11. VMIN algorithm

    • optimal 처럼 이론적으로 최적인 알고리즘
    • 델타만큼의 미래 안에 다시 사용되는 메모리만 유지함 (t, t+델타]
    • 있으면 유지 없으면 즉시 삭제