Beyond Physical Memory: Policies(1)

앞서 physical memory의 한계를 극복하기 위해 main memory를 hard disk의 캐시처럼 사용하는 demand paging을 살펴보았다.

이제 demand paging에서 메인 메모리가 부족할 때 전에 캐싱된 내용의 변경(swapping)이 어떤 정책으로 일어나는지를 살펴보자.

 

average memory access time (AMAT)

TM = Memory Access Latency

TD = Disk Access Latency

Pmiss = 1 - Phit

 

위의 수식에서 알 수 있듯이 hit ratio는 전체 성능에 큰 영향을 주고, 이 hit ratio에 큰 영향을 주는 것이 교체 정책이다.

 

 

교체 정책 (page replacement policies)

 

1. Optimal policy

optimal policy는 미래를 예측하여 앞으로 가장 오랫동안 사용되지 않을 캐시를 교체하는 정책이다.

하지만 미래를 예측한다는 것은 실제로 구현이 불가능하므로 실제 구현이 가능한 다른 정책이 필요하다.

 

2. FIFO (first in first out)

FIFO는 먼저 들어온 것을 먼저 교체하는 정책이다.

Locality를 전혀 고려하지 않고 단지 들어온지 가장 오래된 것을 제거한다.

FIFO정책에서는 메모리를 늘렸는데 오히려 성능이 안좋아지는  Belady's anomaly가 발생할 수 있다.

 

3. Random

Random은 말 그대로 랜덤하게 아무거나 교체하는 정책이다.

10000번을 시도한다고 했을 때 대략 40%정도는 6번 hit (=optimal policy와 같은 결과), 또 상당부분은 5번 hit가 일어나며 꽤 좋은 결과를 보인다.

하지만 최악의 경우, 거의 hit하지 못하게 되는 상황도 간간히 발생할 수 있는 등 일관된 성능을 기대하기는 어렵다.

 

4. LRU (least recently used)

LRU는 최근에 가장 적게 사용된 것을 교체하는 정책이다.

Locality (temporal locality)를 고려하여, 사용 패턴에 따라 해당 내용을 제거할지 말지를 결정한다.

하드디스크에서 메모리로 올라온 것을 리스트로 관리하며, 해당 내용이 읽히면 리스트의 맨 앞으로 이동하여 메인메모리에서 제거되지 않도록 관리한다.

 

하지만 looping reference문제가 있다는 단점이 있다.