Zzong's Notes

LFU

2 min read

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

LRU와의 차이

LRU는 “얼마나 최근에 썼는가”를 보고, LFU는 “얼마나 자주 썼는가”를 본다. 자주 쓰이는 hot item을 오래 보존하는 데는 LFU가 유리하지만, 예전에 많이 쓰였던 항목이 계속 남는 cache pollution 문제가 생길 수 있다.

실무에서 볼 점

실제 시스템에서는 빈도에 시간 감쇠를 넣거나, LRU와 LFU를 섞어 recency와 frequency를 같이 본다. 추천, 검색, feature store cache처럼 트래픽 패턴이 크게 바뀌는 환경에서는 단순 LFU만으로는 부족한 경우가 많다.

링크된 언급

2
First In First Out

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

페이지 교체 알고리즘

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

함께 보면 좋은 글

LRU

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

First In First Out

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

페이지 교체 알고리즘

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

cache

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

BFS

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

stack

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

DFS

Depth-First Search. 그래프나 트리에서 한 갈래를 끝까지 따라 내려간 뒤, 더 갈 곳이 없으면 한 칸 되돌아와 아직 안 가본 갈래로 다시 내려가는 탐색 방식이다. “깊이 우선” 이라는 이름은 이웃을 폭넓게 훑기 전에 한 방향으로 먼저 파고든다는 뜻이다.

amortized analysis

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

post-order

Post-Order Traversal Post-order traversal은 tree traversal에서 왼쪽 subtree → 오른쪽 subtree → 현재 node 순서로 방문하는 방식이다.

Finite State Transducer

Finite State Transducer(FST)는 문자열 같은 입력 시퀀스를 읽으면서, 그 입력에 대응하는 출력 값을 함께 반환할 수 있는 finite state machine이다.