LRU (least recently used) | frame

LRU(Least Recently Used)는 페이지 교체 알고리즘 중 하나로, 가장 오랫동안 사용되지 않은 페이지를 교체하는 방식이다. 캐시 메모리에서 사용되며, 페이지 교체 시 가장 오래된 페이지를 선택해 교체한다.

 

• 시간적 지역성을 기반으로 함: 자주 사용된 데이터는 앞으로도 사용될 가능성이 높고, 오랫동안 사용되지 않은 데이터는 앞으로도 사용되지 않을 가능성이 높다는 가정.
• 페이지 미스: 캐시에 없는 페이지를 요청할 경우 이를 가져와야 하며, LRU 알고리즘을 통해 가장 오랫동안 사용되지 않은 페이지를 교체한다.
• Belady 변이 없음: 페이지 프레임의 수가 증가할수록 페이지 미스가 감소하는 경향이 있으며, LRU는 이러한 상황에서 예외적인 페이지 미스 증가(Belady의 변이)를 일으키지 않는 알고리즘 중 하나이다.

LRU 알고리즘 과정:

1. 페이지 요청이 발생하면, 해당 페이지가 캐시에 있는지 확인한다.
2. 캐시에 없으면 페이지 미스가 발생하며, 가장 오랫동안 사용되지 않은 페이지를 캐시에서 제거하고 새로운 페이지를 넣다.
3. 페이지가 교체된 이후, 최근 사용된 페이지는 캐시 내에서 우선순위가 높아진다.

 

 

■ 프레임이란

프레임은 메모리에서 페이지를 저장하는 공간이다. 프로세스는 메모리에서 실행될 때 필요한 데이터를 메모리로 불러오며 데이터를 페이지 단위로 나누어 저장한다. 프레임은 페이지를 저장할 수 있는 메모리의 작은 단위이다. LRU 알고리즘은 캐시(프레임)가 꽉 찬 상태에서 새로운 페이지가 들어와야 할 때, 가장 오래 사용되지 않은 페이지를 교체하는 방식이다.

 

def lru_page_replacement(page_requests,frame_count):
    frames=[-1]*frame_count #캐시메모리 프레임 수만큼 초기화
    page_faults=0 #패이지부재 카운트
    recent_use=[] #최근 사용 페이지 목록 lru 관리
    
    for page in page_requests:
        if page not in frames: #캐시에 없으면 page miss  
            page_faults += 1#page miss +1
            
            if -1 in frames: #빈 프레임 삽입
                empty_index=frames.index(-1) #-1 첫인덱스를 찾아
                frames[empty_index]=page #write
            else:
                lru_page=recent_use.pop(0)
                lru_index=frames.index(lru_page)
                frames[lru_index]=page
                
        #LRU 리스트 업데이트
        if page in recent_use:
            recent_use.remove(page)
        recent_use.append(page)
        
        #캐시상태
        print(f"pagereqest:{page},frame:{frames}")
        
    print(f"total page fault:{page_faults}")
    
    
page_requests=[3,2,1,0,3,2,1,4,1,5,6,2,1]
frame_count3=3
frame_count4=4


print("LRU with 3 frames:")
lru_page_replacement(page_requests,frame_count3)

print("LRU with 4 frames:")
lru_page_replacement(page_requests,frame_count4)

4frame

 

1. Cache Hit: 요청된 페이지가 캐시에 이미 존재하면, 해당 페이지를 제거하고 다시 캐시의 맨 위(최근 사용된 페이지)로 이동한다.
   • if page in cache: 조건에서 캐시에 해당 페이지가 있으면, 이 페이지를 remove(page)로 제거하고, append(page)로 캐시의 마지막에 추가한다. 이 과정에서 가장 최근에 사용된 페이지가 캐시의 맨 뒤에 위치하게 된다.
2. Cache Miss: 요청된 페이지가 캐시에 없을 때:
   • 캐시에 빈 공간이 있으면, 단순히 페이지를 캐시에 추가한다.
   • 캐시가 꽉 찼을 경우, 가장 오래된 페이지(캐시의 첫 번째 페이지)를 제거하고, 새로운 페이지를 추가한다.
     
     • 캐시에 해당 페이지가 없을 때는, 캐시 미스가 발생하고 page_faults를 증가시킨다.
     • 캐시가 꽉 차지 않았으면, 단순히 cache.append(page)로 새로운 페이지를 추가한다.
     • 캐시가 꽉 찼으면 del cache[0]을 통해 가장 오래된 페이지를 삭제하고 새로운 페이지를 추가한다.