4장 : 기억장치 - (8) 교체 알고리즘

<요약>

• 교체 알고리즘
  • FIFO
  • 최소 최근 사용 알고리즘(LRU)
• 쓰기 정책
  • Write-through
  • Write-back
• 다중 캐시
  • 계층적 캐시
  • 분리 캐시

---

1. 교체 알고리즘

• 세트 연관 사상에서 어느 라인에 있는 블록을 삭제하고 적재할지 정하는 것
• 종류
  • FIFO
  • 최소 최근 사용 알고리즘(LRU)
  • 최소 사용 빈도 알고리즘(LFU) — 학습X
  • 랜덤(Random) —학습X
• 적중률(H)
  • 캐시 적중 횟수 / 전체 횟수 = H

2. FIFO

• 의미
  • 캐시에서 가장 오래된 블록 삭제

3. LRU

• 의미
  • 캐시에서 가장 사용된지 오래된 블록 삭제

4. 쓰기 정책

• 의미
  • 캐시의 내용 변경 시, 기억장치에 반영하는 시기 결정
• 종류
  • Write-through
    • 캐시 수정 시, 기억장치에 바로 반영
    • 장점
      • 캐시, 기억장치의 내용은 항상 같음
    • 단점
      • 속도 감소(계속 기억장치에 접근하므로)
  • write-back
    • 캐시에서 블록이 빠질 때, 빠지는 블록의 내용을 기억장치에 갱신(수정이 있을 시에 갱신)
    • ⇒ 캐시 미스마다, 기억장치에 2번 액세스
      • 새로 들어오는 블록 1번 + 교체당한 블록의 기억장치 수정 작업 1번
    • 블록의 수정 여부 확인
      • 상태 비트
        • = 0 (유효 : 원래 값)
        • = 1 (수정 : 수정된 값)
        • ⇒ 블록의 상태 비트가 1이면 캐시에서 빠져나갈 때, 기억장치에 반영
    • 장점
      • 기억장치 쓰기 동작 횟수 최소
    • 단점
      • 데이터 불일치
        • 캐시,기억장치 내용의 불일치
      • 캐시 제어회로 복잡
        • 캐시의 블록 교체마다, 블록의 내용을 확인하고 기억장치에 수정하는 복잡한 수행 과정
  • 쓰기 정책 문제
    • PPT - 9p(문제가 애매모호해서 실제 과제로 문제를 받아봐야 할 것 같음)
      • 애매모호
        • 기억장치 접근 시, 캐시도 우선 접근해야되는데, 이 경우를 고려안함
        • 평균 기억장치 액세스면 주기억장치만? 아니면 주기억장치+캐시 접근을 말하는 건가?
        • 두 경우 모두 문제 풀 때 답지에 대한 모순이 있음

5. 다중 캐시

• 의미
  • 캐시 여러개
• 종류
  • 계층적 캐시
  • 분리캐시

6. 계층적 캐시

※ 온-칩 캐시 : CPU 칩 내에 있는 캐시

• 구조
  • 캐시 L1
    • 온-칩 캐시
  • 캐시 L2
    • CPU - 기억장치 사이에 존재하는 캐시
    • L1보다 큼
• 특징
  • L1 < L2
    • L1의 내용은 L2에 전부 있음
    • L1의 용량보다 L2가 더 큼
  • cpu → L1 → L2
    • L1 → L2 순으로 데이터 찾기
• 적중률

• 풀이
  • H2가 전체 기억장치 액세스들에 대한 L2의 적중률
    • H2가 전체 100%에서 90%로 데이터를 가지고 있는 것
    • 따라서, L2는 전체 100에서 90을 가져갈 수 있음
    • 하지만 H1에서 70을 가져감
    • H1의 내용 전체를 가지는게 H2이므로, H2의 90에서 H1의 70이 빠짐
    • 따라서, H2는 20을 가져감
    • H3는 남은 10
  • H2가 L1에서 미스 된 기억장치 액세스들에 대한 L2의 적중률
    • L1에서 미스된 양은 30
    • 30에 대한 적중률 90%이니, 0.3*0.9를 가져감
    • 즉, L1 = 0.30.910
    • H3는 남은 것들을 전부 가져가니 1 - (0.7+0.27)을 가져감

7. 분리 캐시

• 의미
  • 캐시 분리
    • 명령어 캐시
    • 데이터 캐시
    • ⇒ 명령, 데이터에 대한 버스가 각각 만들어지게 됨으로, 더 빠른 액세스 가능