Cache Management
메인 메모리가 page들을 가지고 있다면 그 페이지들은 virtual memory page들의 cache로 볼 수 있다.
따라서 우리의 목표는 disk에서 fetch 해올 때 cache miss를 최소화하는 replacement policy를 선택하는 것이다. (또는 cache hits 최대화)
cache hit과 cache miss는 AMAT(Average Memory Access Time)로 계산할 수 있다.
과 는 각각 Memory와 Disk에 접근하는 cost이고, 과 는 각각 hit와 miss가 발생할 확률이다.
AMAT를 계산할 때 은 100 nanoseconds, 는 10 milliseconds 정도로 가정한다. 따라서 를 줄이는 것보다 를 최대화 하는 것이 더 효율적이다.
Optimal
- 가장 나중에 접근할 메모리를 evict
- Compulsory miss(cold start: 처음에 cache가 비어 있으니 무조건 miss)
- 구현 불가능
FIFO
- 먼저 들어온 페이지를 evict (old page를 evict)
- Compulsory miss(cold start)
- 장점: 간단하다
- 단점: Not considering locality Belady's anomaldy(메모리를 늘렸는데 더 비효율적인 경우 = stack property 무시)
- stack property
cache size를 n에서 n+1로 늘렸을 때 기존 n이 스택에 그대로 들어있는 성질 (OPT, LRU는 보장해 줌)
Random
- 빼야 할 때 아무거나 뺀다.
- Compulsory miss(cold start)
- 장점: 간단하다
- 단점: Not considering locality, 예측 불가능(같은 input에 같은 결과를 기대할 수 없음)
LRU(Least-Recently-Used)
- Compulsory miss(cold start)
- hit면 MRU로 보냄 → miss면 LRU를 evict
- 최근에 가장 적게 사용한 page evict
- 장점: temporal locality 고려
- 단점: loop reference, 구현의 어려움
Workload Examples
- No-Locality Workload
우선은 locality를 없애기 위해 모두 다른 페이지에 접근한다고 가정하자.(no locality)
두 가지 사실을 알 수 있다.
첫째, locality를 무시하면 OPT를 제외한 정책들의 hit rate이 모두 같다.
둘째, cache size가 매우 크면 정책이 무의미하다.(100, 100)
- 80-20 Workload
일반적인 locality 성질: 80%의 접근이 20% 페이지에 몰린다고 가정.
OPT가 가장 효율적이고, 다음으로 LRU가 효율적이다.
- Looping-Sequential Workload
50개의 unique 한 페이지에 0부터 loop을 돌면서 접근한다고 가정하자.
OPT는 무난한 hit rate를 보이고, RAND는 그다음으로 효율적이다.
FIFO와 LRU는 50 페이지를 기준으로 hit rate가 0% 거나 100%다.
Approximating LRU
LRU는 꽤 효율적이지만 memory access를 할 때마다 node들을 관리해야 하기 때문에 비효율적이다.
따라서 H/W의 도움을 받아 LRU를 최적화해야 한다.
use bit(reference bit: LD or ST)을 이용해서 한 번이라도 참조된 페이지를 1로 표시한다.
- Clock Algorithm
clock algorithm으로 LRU를 최적화할 수 있다. 먼저 모든 페이지들이 circular list 형태로 존재한다고 가정하자.
clock hand는 페이지를 하나 가리키고 있다. 이후 replacement가 필요할 때 clock hand가 가리키는 페이지의 use bit를 확인한다.
use bit가 1인 경우 최근에 사용한 페이지이므로 교체하지 않는다. 대신 해당 페이지의 use bit를 0으로 바꾸고 다음 페이지를 가리킨다.
아래 Workload는 clock algorithm을 랜덤하게 적용한 경우를 측정한 것이다.
ex
아래 예시를 살펴보자.
0, 1, 2 세 프레임이 있고, 화살표는 clock hand, *는 use bit를 나타낸다.
처음에 2와 3은 frame이 비어 있어서 그냥 들어오고, clock hand가 하나씩 내려간다.
그 다음 2가 들어올 때, 2가 이미 있으므로 clock hand는 움직이지 않는다.
그렇게 세 프레임에 2 3 1이 들어있고 5가 들어오려 한다.
clock hand는 2부터 use bit가 0인지 확인하면서, 1인 경우 use bit를 0으로 만든다.
그렇게 한 바퀴를 다 돌고 다시 0번 프레임(값 : 2)를 가리키고, use bit가 0이므로 2를 evict한다.
이후 clcok hand가 하나 이동해 5 밑에 있는 1번 프레임(값 : 2)를 가리킨다.
오른쪽에서 4번째 [3* | →2 | 4]를 보면, 이미 있는 2가 들어오려 해서 hit가 발생한다.
그래서 replace가 발생하지 않고 2의 use bit를 1로 바꿔 준다. [3* | →2* | 4]
Considering Dirty Pages
Clock algorithm에 사용하기 위해 dirty bit를 도입했다.
페이지가 수정되었는지 여부를 dirty bit(= modified bit)로 표시한다.
한번 쓰인 페이지를 다시 사용하려면 I/O를 이용해 디스크를 지워야하기 때문에 cost가 많이 필요하다. 반면 한 번도 쓰이지 않은 Pysical frame은 쉽게 재사용 할 수 있다.
이런 dirty bit를 clock algorithm에 쉽게 추가할 수 있다. 예를 들어 use bit가 0인 페이지들 중에 dirty bit도 0인 경우를 가장 먼저 replace 하도록 할 수 있다.
Uploaded by Notion2Tistory v1.1.0