디스크 캐시

• 캐시 메모리(주기억장치보다 더 작고 빠르면서 주기억장치와 처리기 사이에 위치하는 메모리)의 원칙을 디스크 메모리에 적용
• 디스크 섹터를 저장하기 위한 주기억장치의 버퍼
• 특정 섹터에 대해 입출력 요청 -> 그 섹터가 디스크 캐시 안에 있는지 검사 -> 존재하면 입출력 작업은 캐시에서 완료 / 존재하지 않으면 요청된 섹터가 디스크로부터 디스크 캐시로 읽혀짐
• 참조의 지역성 특성 적용

교체 전략 - 페이지 교체 알고리즘

새로운 섹터를 디스크 캐시로 가져올 때 현존하는 블록들 중 하나는 교체되어야 함

LRU(Least Recently Used)

참조 없이 가장 오랫동안 캐시에 존재했던 블록을 교체
논리적으로 캐시는 스택으로 구성되어 블록이 참조되면 스택의 위쪽으로 다시 들어감
스택의 맨 밑에 위치한 블록을 제거하고 새로 들어온 블록을 스택의 맨 위에 놓는 방식

LFU(Least Frequently Used)

집합 중에서 참조 횟수가 가장 적은 블록을 교체
블록이 캐시로 들어오면 카운터 값 1이 배정되고 참조될 때마다 카운터 값이 1씩 증가하여 카운터 값이 가장 작은 블록을 교체시키는 방식
문제: 지역성 효과가 있는데 참조 카운트가 블록이 바로 다시 참조될 확률을 정확히 반영하지 못함
=> 빈도 기반 교체를 통한 문제 해결

빈도 기반 교체(Frequency-based Replacement)

• LRU와 비슷한 논리적 스택 구조
• 스택 상부의 일정 블록들은 새로운 섹션용으로 예약되어 있음
• 캐시 적중이 발생하면 참조된 블록이 스택 상부로 이동
  - 그 블록이 이미 새로운 섹션 내의 블록이라면 참조 카운트 증가 X
  - 새로운 섹션 내의 블록이 아니라면 카운트값+1
• 새로운 섹션이 충분히 크면 짧은 시간 동안 반복적으로 재참조되는 블록들의 참조 카운트는 변하지 않음
• 캐시 적중 실패가 발생한 경우 새로운 섹션에 속하지 않는 블록 중 참조 카운트가 가장 작은 블록이 선택되어 교환됨
• 카운트 값이 같은 경우 가장 오래 전에 참조된 블록이 선택되어 교환됨

빈도 기반 교체 - 성능 평가

• LRU가 빈도기반 교체 알고리즘보다 우수한 성능을 나타내는 것처럼 보이지만 동일한 구조를 가지는 캐시에서 동일한 참조 패턴을 이용하면 빈도기반 교체 알고리즘이 훨씬 우수함