[OS] Cache

3년간 산업기능요원으로 복무 하고, 복학해 컴공과 수업을 듣고 있습니다. 그동안 많이 배웠다고 생각했는데, 여전히 부족한 부분이 많네요 ^^;; 역시 세상도 넓고 공부의 길도 넓은 것 같습니다.

들어가며

요 포스트는 운영체제를 공부하면서 짧게 메모 했던 것들을 모은 글 입니다. OS 내용을 복습하면서 살펴보면 좋을 것 같습니다 🙂

Cache Write

• Write Through
  • 캐시 블록에 업뎃이 있을 때, 즉시 물리 저장소에 쓰기
• Write Back
  • 캐시 블록이 교체 될 때, 물리 저장소에 쓰기

Cache Lookups

• Fully-associative
  • 남은 슬롯 중에 한 곳에 저장함.
  • 캐시 검색 때는, 모든 슬롯을 전체 탐색해서 매칭 하는 슬롯이 있으면 반환.
  • Conflict Miss 횟수가 낮음
• Direct-mapped
  • Hash 함수를 사용해 슬롯의 위치를 결정함.
  • 빠른 탐색
  • Conflict Miss 횟수가 높음
• Set-associative
  • Hash 함수로 어떤 세트에 저장할지 결정
  • 세트가 결정되면, 그 세트의 슬롯 중 하나에 저장함.
  • 캐시 검색 때는, 그 세트의 슬롯을 전체 탐색.

Page Fault is Trap

Trap vs. Interrupt에 대해선 요기 참고!

Sys Call은 모두 Trap임. HW 관련 핸들링은 Interrupt임.

Direct Memory Access

본래 디스크의 데이터를 메인 메모리에 적재하려면 CPU가 이걸 수행해야 했음. 그런데, CPU 대신 이 작업을 위임 받아 수행하는 테크닉임.

Bookkeeping Bits

• page modified
• page recently used

Bookkeeping Bits는 TLB와 Page Table 둘다 관리하고, Page 수정이나 접근이 발생 했을 때, 두 곳 모두에 반영함. (19p)

Cache Replacement Policy

Cache miss가 발생 했을 때, 어떤 캐시 슬롯을 evict 할 건지!!

Hashing 기반으로 캐시에 접근하는 Direct Mapped Cache에서는 고려하지 않아도 됨!

MIN (best algorithm)

최적의 Cache Exchange 알고리즘이 증명됨. Cache Miss 횟수가 가장 적음.

앞으로 가장 오랫동안 사용되지 않을 캐시 항목을 Evict 하는 전략임

LRU (near best)

MIN에 가장 근접한 알고리즘.

현재 캐시 슬롯에 올라간 항목 중에서 가장 오랫동안 사용하지 않은 항목을 Evict 하는 전략.

Cache 사이즈를 늘리면 Miss가 줄어들까?

Nope! 캐시 사이즈를 늘려도 Cache Miss 횟수가 줄지 않는 경우도 있음. (Belady’s Anomaly라고 함.) (34p)

사실 요 문제는 FIFO에서만 발생하는 거라고 함. 이유는 캐시 슬롯 수가 증가하면서, 교체 순서가 바뀌면서 오히려 분리하게 동작할 수 있어서라고 함. LRU에서는 겪지 않는다고 함.

Page Pool

ppt 내용을 읽는데, 설명이 명확하지 않아서 이해하는데 한참 걸림;;

Frame Table에 있는 페이지들의 최근 사용 여부를 보조 해주는 자료구조이자 메커니즘임.

Page Pool에선 각 페이지를 클린 페이지와 더티 페이지로 구분함. Page Fault로 인해 Frame Table에서 페이지를 하나 비워야 하는 상황이라면

• 페이지가 클린 페이지라면
  • 즉시 교체 가능
• 페이지가 더티 페이지라면
  • Write back 후 교체 가능

여기까지는 기존 Frame Table이랑 동일함. 핵심은 지금부터인데, OS는 Page Pool을 비동기(async)하게 관리함. 그래서 주기적으로 돌면서 더티 페이지는 Write Back을 수행해 클린 페이지로 만들어줌.

이것은 더티 페이지를 Write Back 하는데 시간이 걸리니, 이런 상황이 Page Fault에서 최대한 발생하지 않도록 하기 위한 메커니즘임!

Thrashing

가용 메모리 공간이 아주아주 낮아서, 메모리 영역에 접근할 때 마다 Page Fault가 발생하거나, 시스템 전반적으로 Page Fault 발생 빈도가 높은 상태. 심각한 성능 저하가 일어나고 있다는 의미임.

Working Set을 지원해 줄 만큼 물리 메모리가 충분하지 못 한 상황에서 발생함.

이런 현상을 방지하려면??

• 각 프로세스가 필요로 하는 최소한의 프레임 갯수를 보장해줘야 함.
• 시스템에 동시에 실행되는 프로세스 수를 줄여서 메모리 결쟁을 완화 한다.
• 좀더 효율적인 페이지 교체 알고리즘을 채택 한다.
• 그냥 물리 메모리를 증설한다.

44p부터 볼 것