캐시 교체알고리즘 과 상황별 효율성

학습목표

• LRU캐시 알고리즘외에 다른 캐시알고리즘은 어떤것이 있는지 알아보자.
• 찾아본 캐시알고리즘은 어떤 방식으로 캐시를 교체할까??
• 알아본 캐시알고리즘들은 어떤상황에 쓰면 더 효율적일까??

캐시알고리즘의 종류

1. FIFO(First In First Out)
2. LRU(Least Recently Used)
3. LFU(Least Frequently Used)
4. MFU(Most Frequently Used)
5. NUR(Not Used Recently)
6. SCR(Second Chance Replacement)
7. Random

FIFO

가장 간단한 알고리즘으로, 메모리에 올라온지 가장 오래된 페이지를 교체한다.

각 페이지가 올라온 시간을 기록하거나, 큐에 저장하는 방식등으로 구현

https://medium.com/pocs/페이지-교체-page-replacement-알고리즘-650d58ae266b

가장간단하게 구현할수있으나, 적재순서에 따라 교체되므로, 활발하게 사용중인 페이지가 교체될수 있고, 그에따라 성능저하가 예상된다.

LRU

가장 오래 사용되지 않은 페이지를 교체한다. 최적알고리즘은 실제 구현이 불가능하므로, 최적알고리즘의 방식과 비슷한 효과를 낼 수 있는 방법이다.

https://medium.com/pocs/페이지-교체-page-replacement-알고리즘-650d58ae266b

현재 대부분의 캐시교체 알고리즘으로 사용되지만, 페이지 교체횟수가 많다. 즉 오버헤드가 많이 발생하는 단점을 갖고 있다. 추가적으로 Temporal Locality가 강한 프로그램에서는 좋은 성능을 보이지만, Spartial Locality가 강한 곳에서는 그렇지 못한 것 같다. 순차적이고 휘발성이 강한 작업들이라면 모든 메모리에 균등하게 접근 될것이다.

LFU

참조횟수가 가장 작은 페이지를 교체한다. 만약 교체대상 페이지가 여러개인 경우 LRU알고리즘을 따라 가장 오래 사용되지 않은 페이지를 교체한다.

https://medium.com/pocs/페이지-교체-page-replacement-알고리즘-650d58ae266b

LFU알고리즘은 초기에 한페이지를 집중적으로 참조하다가, 이후 다시 참조하지 않는 경우에 문제가 될 수 있다. 앞으로 사용하지 않아도, 초기 참조횟수때문에 메모리에 남아있기 대문이다. 아래 그림을보고 더 쉽게 이해 해보자.

https://medium.com/pocs/페이지-교체-page-replacement-알고리즘-650d58ae266b

초기에 쓰인 7이 계속 메모리에 상주해 낭비가 일어난다.

MFU

LFU알고리즘과 반대로, 참조횟수가 가장 만은 페이지를 교체하는 알고리즘이다. 참조횟수가 적은것은 최근에 사용된 것이기 때문에 앞으로 사용될 가능성이 높다는 판단이다.

https://medium.com/pocs/페이지-교체-page-replacement-알고리즘-650d58ae266b

LFU와 MFU는 실제 사용에는 잘 쓰이지 않는다.

• 구현에 상당한 비용이 든다.
• 비용대비 LRU만큼 성능이 나오지 않기 때문이다.

NUR

LRU알고리즘과 비슷한 방식으로 최근에 사용하지 않은 페이지를 교체한다.

LRU교체 알고리즘의 단점인 교체에 따른 오버헤드를 줄인 방법이다.

최근 사용여부를 나타내기 위해 각 페이지 마다 두개의 비트(참보비트/변형비트)를 ㅏㅅ용한다.

• 참조비트 : 페이지가 호출되면 1, 호출되지 않으면 0
• 변형비트 : 페이지 내용이 변경되었을 때는 1, 변경되지 않았을 때는 0

SCR

가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 것으로, FIFIO기법의 단점을 보완

각 페이지 마자 참조비트를 두고, FIFO기법을 이용해 페이지 교체 수행중, 참조 비트가 0 일경우에는 교체, 1일경우에는 0으로 지정하고 FIFO리스트의 가장 마지막으로 피드백시켜 다음 순서를 기다리게 한다.

Random

아무 규칙없이 임의의 페이지를 교체하는 알고리즘

딱히 설명은 필요 없을것 같다.. 캐시를 사용하는데에 있어 특별한 경향성을 발견하지 못하면 사용된다고 한다.

알게된 점

• LRU캐시 알고리즘외에 다른 캐시알고리즘은 어떤것이 있는지 알아보자.
  • FIFO : 가장 오래된 캐시를 교체
  • LRU : 가장 오랫동안 사용되지 않은 캐시를 교체
  • LFU : 가장 적게 참조된 캐시를 교체 (덜 참조 됬으니, 앞으로도 덜 쓸것이다)
  • MFU : 가장 많이 참조된 캐시를 교체(많이 참조됬으니, 이제 안 쓸것이다)
  • NUR : LRU 와 비슷하며, 최근에 사용되지 않은 캐시를 교체한다. 교체가 많이 됨에 따라 오버헤드가 증가하는 LRU의 단점을 보완함
  • SCR : FIFO방식에서 참조비트를 두고, 참조 되었으면 가장 맨뒤로 피드백되어 순번을 기다린다.
  • Random : 임의의 캐시를 삭제
• 찾아본 캐시알고리즘은 어떤 방식으로 캐시를 교체할까??
  • 위의 설명과 같다.
• 알아본 캐시알고리즘들은 어떤상황에 쓰면 더 효율적일까??
  • 솔직히 잘 모르겠다. 내일까지 쭉 더 생각해봐야겠다.
  • LRU가 temporal Locality에 강하지만, 그렇지 않은 소프트웨어에서는 캐시미스가 많이 난다고 한다. 즉 모든 메모리에 비교적 균등하게 접근되는 작업에서는 큰 쓸모가 없을것이다. ex) 배열의 순회?..
  • DNS가 LRU알고리즘으로 구현하기 좋은 예가 아닐까 생각해본다.

Reference

페이징 교체 알고리즘

캐시 메모리 및 가상메모리 교체 알고리즘

[정보처리기사] 페이지 교체 알고리즘 (FIFO/LRU/LFU/NUR)

페이지 교체(page-replacement) 알고리즘