[컴퓨터 구조] 캐시의 교체 알고리즘과 쓰기 정책

1. 교체 알고리즘

필요성

직접 매핑하는 경우에는 라인 별로 들어 갈 수 있는 곳이 정해져서 필요하지 않지만 연관, 세트연관 매핑의 경우 임의로 블록이 들어가기 때문에 교체 알고리즘이 필요하다. 그리고 이 교체하는 과정을 빠르게 하기 위해 알고리즘이 하드웨어로 구현되어야 한다.

대표적인 알고리즘

1) LRU(Least Recently Used) : 캐시 내에서 가장 오랫동안 참조되지 않은 블록을 교체하는 방식으로 

                                         구현이 단순하여 가장 널리 사용되는 알고리즘

2) FIFO(First In First Out) : 캐시 내에서 가장 오랫동안 있던 블록을 먼저 교체하는 방식

3) LFU(Least Frequency Used) : 가장 적게 참조되었던 블록을 교체하는 알고리즘

 2. 쓰기 정책

필요성

캐시는 프로그램 속도를 빠르게 하기 위한 운송업체 같은 역할일 뿐 실제 프로그램은 메인 메모리에서 수행한다. 따라서 캐시의 데이터가 변화하면 메인 메모리에도 똑같이 반영이 되어야 프로그램을 완벽하게 수행할 수 있으므로 캐시의 내용을 메모리에 다시 반영하는 쓰기 정책이 필요하다.

Write Through

가장 간단한 기법으로 캐시에 생기는 변화가 즉각적으로 메인 메모리에 반영이 되어지는 것이다. 하지만 메인 메모리의 사용량이 증가하여 병목현상이 발생할 수 있다.

Write back

위의 방법을 보완하는 방법으로 캐시 내의 데이터만 갱신이 되고 메모리는 나중에 캐시에서 데이터를 다시 가져오는 과정에서 갱신이 되는 점이다. 따라서 캐시의 데이터와 메모리의 데이터가 서로 달라지는 모습을 자주 보이는데 이 상태를 Dirty, 더럽혀 졌다고 한다.  속도는 개선되는 방면에 회로가 복잡하고 디바이스를 제어하는 경우 캐시의 내용을 디바이스로 전달을 안하는 경우가 간혹 발생한다.