Zzong's Notes

LRU

1 min read

LRU(Least Recently Used)는 가장 오래 사용되지 않은 항목을 먼저 제거하는 replacement policy다. cache와 페이지 교체 알고리즘에서 자주 등장한다.

핵심 아이디어

최근에 접근한 데이터는 가까운 미래에도 다시 접근될 가능성이 높다는 locality 가정에 기대고 있다. 그래서 접근 시점을 계속 갱신하고, 공간이 부족해지면 마지막 접근 시점이 가장 오래된 항목을 내보낸다.

실무에서 볼 점

정확한 LRU는 접근 순서를 매번 갱신해야 하므로 구현 비용이 든다. 그래서 운영체제나 대규모 cache에서는 clock algorithm처럼 LRU를 근사하는 방식도 많이 쓴다.

링크된 언급

4
First In First Out

...는 것과 앞으로 안 쓰인다는 것은 다른 이야기다. 자주 쓰이는 페이지도 오래됐다는 이유로 쫓겨나 곧바로 다시 Page Fault 가 나는 일이 생긴다. 그래서 실제로는 마지막 사용 시각을 보는 LRU 나 사용 빈도를 보는 LFU 를 더 쓴다. FIFO 에는 프레임 수를 늘렸는데 오히려 page fault 가 늘어나는 Belady’s anomaly 라는 현상도 있다.

LFU

LFU(Least Frequently Used)는 사용 빈도가 가장 낮은 항목을 먼저 제거하는 replacement policy다. cache나 페이지 교체 알고리즘에서 LRU와 함께 비교된다. LRU와의 차이 LRU는 “얼마나 최근에 썼는가”를 보고, LFU는 “얼마나 자주 썼는가”를 본다. 자주 쓰이는 hot item을 오래 보존하는 데는 LFU가 유리하지만, 예...

NUR

Not Used Recently. 페이지 교체 알고리즘 의 하나로, 최근에 쓰이지 않은 Page 를 골라 내보낸다. LRU 와 목적은 같지만, 마지막 사용 시각을 정확히 기록하는 대신 비트 두 개로 대충 근사한다. LRU 를 정확히 구현하려면 페이지에 접근할 때마다 시각을 갱신해야 하는데, 이 갱신은 메모리 접근마...

페이지 교체 알고리즘

algorithms/First In First Out 교체 알고리즘 LRU 교체 알고리즘 LFU 교체 알고리즘 NUR 교체 알고리즘리즘

함께 보면 좋은 글

LFU

LFU(Least Frequently Used)는 사용 빈도가 가장 낮은 항목을 먼저 제거하는 replacement policy다. cache나 페이지 교체 알고리즘에서 LRU와 함께 비교된다.

First In First Out

먼저 들어온 것을 먼저 내보내는 처리 순서다. 줄을 선 순서대로 처리한다고 보면 되고, 이 규칙을 구현한 자료구조가 큐(queue) 다. 반대는 나중에 들어온 것을 먼저 꺼내는 LIFO 이고, stack 이 그쪽이다.

페이지 교체 알고리즘

swap out 을 위한 Page 를 선정하기 위한 알고리즘 Memory 에서 앞으로 사용할 가능성이 적은 페이지를 대상 Page 로 선정하여 Page Fault 를 줄이고, 시스템의 성능을 향상한다.

NUR

Not Used Recently. 페이지 교체 알고리즘 의 하나로, 최근에 쓰이지 않은 Page 를 골라 내보낸다. LRU 와 목적은 같지만, 마지막 사용 시각을 정확히 기록하는 대신 비트 두 개로 대충 근사한다.

cache

Cache 는 느린 저장소나 계산 결과 앞에 더 빠른 저장 공간을 두어 반복 접근 비용을 줄이는 구조다. OS/architecture 에서는 CPU cache, page cache, disk cache 등이 대표적이다.

stack

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조 (LIFO - Last In First Out) 으로 되어 있다.

amortized analysis

amortized analysis 는 주어진 알고리즘을 실행할 때 얼마나 많은 자원 (특히 시간 또는 메모리) 가 필요한지를 분석하는 방법이다.

BFS

BFS(Breadth First Search)는 시작 node 에서 가까운 node 부터 층별로 방문하는 graph/tree traversal 방식이다. 보통 queue 를 사용한다. 동작 흐름 시작 node 를 queue 에 넣고 방문 처리한다.

Selection Sort

선택 정렬은 다음과 같은 순서로 이루어진다. 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 하나의 원소만 남을 때까지 위의 과정을 반복한다.

greedy algorithm

매 단계에서 그 순간 가장 좋아 보이는 선택을 하고, 한 번 고른 것은 되돌리지 않는 방식이다. 전체를 내다보지 않으므로 계산이 싸지만, 그 대가로 최종 답이 최적이라는 보장이 사라진다.