온라인 알고리즘/Caching (3) 썸네일형 리스트형 최적 페이지 교체 알고리즘 (Optimal Page Replacement Algorithm) 삼 년 전, 저는 유명한 온라인 최적화(online optimization) 문제 중 하나인 온라인 캐싱(online caching)을 소개하고, 이를 해결하는 유명한 방법인 LRU(least recently used) 알고리즘의 경쟁성을 증명하였습니다. [캐싱 / Caching] LRU는 얼마나 좋은 알고리즘일까? 세세한 부분을 많이 놓치기는 하겠지만, 간략히 말해 컴퓨터는 다음과 같이 동작합니다. 메모리에서 데이터를 프로세서로 가지고 와서 사칙 연산, 대소 비교 등과 같이 어떠한 작업을 수행한 다 gazelle-and-cs.tistory.com 글의 서론에서 저는 캐시 미스가 발생했을 때 캐시 메모리 상에서 가장 마지막에 사용되는 자료를 삭제하는 정책인 LFD(longest forward distan.. LRU보다 좋은 페이지 교체 알고리즘 (Randomized Marking Algorithm) 캐시 메모리(cache memory)는 프로세서와 주 메모리 사이에 위치한 용량은 작지만 속도는 빠른 저장 장치를 의미합니다. 이 장치의 용도는 어떤 프로세스가 동작할 때 많이 접근하는 자료를 저장해 두는 것이죠. 프로세스가 특정한 자료를 필요로 할 때 해당 자료가 최신의 상태로 캐시 메모리에 존재한다면, 주 메모리에 직접 접근하지 않고 캐시 메모리에 접근하여 자료를 가져옴으로써 상당한 시간적 이득을 꾀할 수 있습니다. 프로세스가 호출하는 자료의 단위를 페이지(page)라고 부르겠습니다. 만약 프로세스가 어떤 페이지를 필요로 하는데, 최신의 해당 페이지가 캐시 메모리에 존재하는 때를 캐시 히트(cache hit), 그렇지 않을 때를 캐시 미스(cache miss)라고 부릅니다. 전자의 경우에는 캐시 메모.. [캐싱 / Caching] LRU는 얼마나 좋은 알고리즘일까? 세세한 부분을 많이 놓치기는 하겠지만, 간략히 말해 컴퓨터는 다음과 같이 동작합니다. 메모리에서 데이터를 프로세서로 가지고 와서 사칙 연산, 대소 비교 등과 같이 어떠한 작업을 수행한 다음 결과값을 다시 메모리에 저장합니다. 여기서 많은 경우 프로세서의 수행 시간에 비해 메모리 접근 시간이 훨씬 오래 걸리기 때문에 전체 수행 시간의 병목은 얼마나 많이 메모리에 접근했는가로 결정됩니다. 캐시 메모리(cache memory)는 프로세서와 주 메모리 사이에 자그마하지만 처리 속도는 빠른 기억 장치를 의미합니다. 프로세서가 어떤 자료를 필요로 할 때 만약 캐시 메모리에 최신의 그 자료가 존재한다면 프로세서는 굳이 주 메모리에서 자료를 가지고 올 필요가 없습니다. 캐시 메모리에서 바로 가지고 오면 되니까요. 이는.. 이전 1 다음
