페이지 교체 알고리즘 - LRU(Least recently used)

페이지 교체 알고리즘 

페이징 기법. 메모리 관리하는 os에서, 페이지 부재가 발생하여 새로운 페이지를 할당하기 위해, 현재 할당된 페이지 중 어느것과 교체할 지 결정하는 방법 

FIFO - first in first out 

LFU - least frequently used

LRU - least recently used 

 

Cache 

Cache Hit - 캐시 메모리에 찾는 데이터가 존재 

Cache Miss - 캐시 메모리에 찾는 데이터가 존재하지 않음 -> 메모리 저장소로부터 필요한 데이터를 찾아 캐시메모리에 로드 

LRU 알고리즘

 

참조 스트링 순서대로 저장

4초 - 1이 재참조 되었으므로, 순서 변경

6초 - cache size 가 찻으므로, least recently used item 제거 , 5 저장 

 

cache_size = 4

reference = [1,2,3,1,4,5]

cache = []

for ref in reference:
	if not ref in cache: #cache miss
    	if len(cache)<cache_size:
        	cache.append(ref)
        else:
        	cache.pop(0)
            cache.append(ref)
    else: #cache hit 
    	cache.pop(cache.index(ref))
        cache.append(ref)