Swapping Policies

Cache Management의 목표는 cache miss의 수를 최소화 하는 것이다.

그렇다면 어떤 기준으로 cache를 설정하면 될까?

이것이 Tracing the Optimal Policy이지만 현실적으로 미래를 알 수 없으므로 불가능하다.

FIFO 방식으로하면 Hit rate이 36.4%로 급격히 낮아진다. 0이 계속 들어올 것이지만 제거해버렸기 때문이다.

당연히 cache가 커지면 hit rate가 오를 것이라고 생각하겠지만 FIFO에서는 오히려 줄어들 수 도 있다. ex) 3->4

 

차라리 Random하게 cache에 저장하는 것이 오히려 효율적 일 수 있다.(약 45%)

때때로는 Random이 optimal처럼 좋을 수도 있다.

---

위 두 개의 history( recency, frequency )를 사용해보자.

LRU( least recent used )를 사용하면 hit rate이 약 54% 나온다.

No-Locality Workload에서는 LRU,FIFO,RAND 모두 똑같이 linear한 Hit Rate를 보인다.

하지만 작업 80-20 workload라면 LRU는 효과가 있다.

80-20이란 80%의 작업이 20%의 page에서 이뤄지고 20%의 작업이 80%의 page에서 이뤄진다는 것이다.

즉, LRU는 locality가 있는 work에 대해서 효과가 있다.

50개의 page를 순차적으로 하는 작업 방식이라면 FIFO와 LRU는 작업에 locality가 없기 때문에 page가 50개를 넘기 전까지는 hit rate가 0%이다.

 

사실 모든 history를 확인하는 것은 매우 비효율적이다. 따라서 LRU를 대략적으로 구현해주는 방법이 필요하다.

Clock algorithm은 LRU를 대략적으로 표현하기 위해 만들어진 algorithm이다.

Clock Algorithm을 구현하기 위해서는 hardware의 도움이 필요한대, 만약 page가 참조되었다면 hardware가 use bit을 1로 고쳐줘야 한다. Hardware는 절대 bit을 clear하지 않으므로 OS가 해줘야 한다.

 

Clock algorithm

• 모든 page system이 circular list에 저장된다.
• clock hand point가 시작하는 특장한 page를 가리킨다.
• use bit가 0인 값을 찾을 때까지 시계 방향으로 clock hand point가 움직인다.

Clock Algorithm을 적용하면 LRU와 거의 비슷한 Hit rate를 보여주고, 모든 history를 확인 할 필요도 없다.

 

Considering Dirty Pages

• 하드웨어는 dirty bit를 가지고 있는데 ,만약 page의 dirty bit가 1이라면 변형 된 정보로 disk에 다시 쓰여진 뒤 evict되어야 한다.
• Page가 변형되지 않았다면 eviction은 마음대로 일어날 수 있다.

---

Prefetching

fetching을 할 때, OS가 page2에도 접근 할 것이라고 예측하여 page2에 접근하기 전에 미리 memory에 올려놓는것.

 

Clustering, Grouping

Disk에 한번에 하나의 page를 저장하는 것이 아니라 여러 개의 page를 Clustering하여 한번에 적는 것

 

Thrashing

프로그램을 너무 많이 돌리게 되면 어느 순간 부터 Swapping 하는 cost가 커지게 되면서 I/O가 많이 발생해 많은 process가 block 되고 CPU Utilization이 줄어들게 된다.