LRU (least recently used) | frame
2024. 10. 3. 22:27ㆍ정보처리,전산/운영체제
반응형
LRU(Least Recently Used)는 페이지 교체 알고리즘 중 하나로, 가장 오랫동안 사용되지 않은 페이지를 교체하는 방식이다. 캐시 메모리에서 사용되며, 페이지 교체 시 가장 오래된 페이지를 선택해 교체한다.
- 시간적 지역성을 기반으로 함: 자주 사용된 데이터는 앞으로도 사용될 가능성이 높고, 오랫동안 사용되지 않은 데이터는 앞으로도 사용되지 않을 가능성이 높다는 가정.
- 페이지 미스: 캐시에 없는 페이지를 요청할 경우 이를 가져와야 하며, LRU 알고리즘을 통해 가장 오랫동안 사용되지 않은 페이지를 교체한다.
- Belady 변이 없음: 페이지 프레임의 수가 증가할수록 페이지 미스가 감소하는 경향이 있으며, LRU는 이러한 상황에서 예외적인 페이지 미스 증가(Belady의 변이)를 일으키지 않는 알고리즘 중 하나이다.
LRU 알고리즘 과정:
- 페이지 요청이 발생하면, 해당 페이지가 캐시에 있는지 확인한다.
- 캐시에 없으면 페이지 미스가 발생하며, 가장 오랫동안 사용되지 않은 페이지를 캐시에서 제거하고 새로운 페이지를 넣다.
- 페이지가 교체된 이후, 최근 사용된 페이지는 캐시 내에서 우선순위가 높아진다.
■ 프레임이란
프레임은 메모리에서 페이지를 저장하는 공간이다. 프로세스는 메모리에서 실행될 때 필요한 데이터를 메모리로 불러오며 데이터를 페이지 단위로 나누어 저장한다. 프레임은 페이지를 저장할 수 있는 메모리의 작은 단위이다. 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)
- Cache Hit: 요청된 페이지가 캐시에 이미 존재하면, 해당 페이지를 제거하고 다시 캐시의 맨 위(최근 사용된 페이지)로 이동한다.
- if page in cache: 조건에서 캐시에 해당 페이지가 있으면, 이 페이지를 remove(page)로 제거하고, append(page)로 캐시의 마지막에 추가한다. 이 과정에서 가장 최근에 사용된 페이지가 캐시의 맨 뒤에 위치하게 된다.
- Cache Miss: 요청된 페이지가 캐시에 없을 때:
- 캐시에 빈 공간이 있으면, 단순히 페이지를 캐시에 추가한다.
- 캐시가 꽉 찼을 경우, 가장 오래된 페이지(캐시의 첫 번째 페이지)를 제거하고, 새로운 페이지를 추가한다.
- 캐시에 해당 페이지가 없을 때는, 캐시 미스가 발생하고 page_faults를 증가시킨다.
- 캐시가 꽉 차지 않았으면, 단순히 cache.append(page)로 새로운 페이지를 추가한다.
- 캐시가 꽉 찼으면 del cache[0]을 통해 가장 오래된 페이지를 삭제하고 새로운 페이지를 추가한다.
반응형
'정보처리,전산 > 운영체제' 카테고리의 다른 글
비선점형 SJF (Shortest Job First) (0) | 2024.10.19 |
---|---|
FIFO (0) | 2024.10.04 |
운영체제의 발달 과정 (0) | 2024.09.27 |
UNIX CPU 스케줄링 (1) | 2024.08.16 |
PROCESS (0) | 2024.08.16 |