풀이 보관함
[OS] LRU 알고리즘이란? 정의부터 구현까지 알아보자! 본문
LRU 알고리즘이 어디에 쓰이는 무엇인지 그리고 어떻게 구현하는지 개괄 정리해보겠습니다.
background
운영체제라는 강의나 관련 서적을 읽었으면 절대 빠지지 않고 나오는 이 알고리즘은 자주 나오는 만큼 중요한 알고리즘이다.
어떤 공간에 여러 요소들이 꽉 차있다고 생각해보자.
근데 더 이상 자리가 없는데 그 공간에 새로운 것을 넣어야 한다면?
공간을 차지하는 무엇인가를 빼서 자리를 만든 후 넣어야 되지 않겠어요?
한정된 공간에 빼야할 요소를 정하는 알고리즘을 replace algorithm이라고 하며, 컴퓨터에서는 한정된 공간이 {메모리, 캐시, 저장공간}이 되며 요소들이 {스레드, 프로세스, 자원}이 될 수 있다. 운영체제에서는 저 한정된 공간을 알뜰하게 쓰는게 바로 효율성이기 때문에 굉장히 이 replace algorithm를 중요하게 생각한다.
이 replace algorithm (교체 알고리즘) 중 대표적인 예가 LRU 알고리즘이며, 페이지 교체 알고리즘(page replace algorith)에서 중요한 역할을 한다.
>> page fault와 page replace algorithm 간단 정리
컴퓨터는 메인 메모리와 디스크라는 저장장치가 있다. 사용자가 데이터를 불러오든 프로그램을 켜든 컴퓨터는 사용자 요청이 들어오면 디스크에서 해당 데이터를 부랴부랴 가져와서 메인 메모리에 적재를 해야만 사용이 가능하다. 그렇게 메인 메모리에는 프로세스와 데이터들이 쌓이며 공간을 차지하게 된다. (더 정확히는 가상 메모리를 공부하세요! 😉)
여기까지가 사전 지식이고.. 메인 메모리에 물리적으로 없는 데이터를 불러 버리는 것을 page fault라고 한다. 필요한 페이지를 빨리 메인 메모리에 가져와야하는데 찐 RAM 물리 메인 메모리가 꽉 찼다면? 운영체제는 아무 문제도 없는 척하기 위해 빨리 페이지 하나를 골라 비워버리고 호출된 걸 실행시키고 싶어한다!! 이 때, 호출한 부분이 있는 페이지를 적재할 수 있도록 비우고 적재 페이지 대상을 교체하는 알고리즘이 page replace algorithm이다.
LRU Algorithm (Least Recently Used)
Least Recently Used . 즉 가장 오랫동안 사용하지 않은 요소를 빼자는 것이 오늘 주제인 LRU 알고리즘이다.
- 유사 replace algorithm : LFU (Least Frequently Used)
어떻게 하면 최근에 썼는지 안 썼는지 알지?
똑같은 거 여러번 부를 수도 있으면 갱신해야할텐데?
그거 순서를 매번 어떻게 관리하지?
어떤걸 고려해야하지?
등등 아무튼 어떻게 구현할지 5초 정도는 고민해보자.
[구현 방법]
LRU 알고리즘을 구현하는 방법은 아래처럼 다양할 수 있겠다.
출처에 들어가면 여러 구현 방법과 장단점이 있으니 관심이 있는 사람은 읽어보는 것을 추천드립니다! (출처)
- LRU using Queue and Hashing
- LRU using Doubly Linked List + Hashing
- LRU using Deque
- LRU using Stack
- LRU using Counter implementation
- LRU using Lazy Update
이 중에 LRU using Doubly Linked List + Hashing을 좀 자세히 알아보자.
1. lru cache의 저장공간 사이즈를 정한다. (예시에서는 3)
2. key - value 로 매칭되는 hash 형태로 doubly linked list 로 넣는다.
-> 이중 연결 리스트이기 때문에 O(1)로 새로운 노드를 추가할 수 있다는 장점
The idea is very basic, i.e. keep inserting the elements at the head. if the element is not present in the list then add it to the head of the list if the element is present in the list then move the element to the head and shift the remaining element of the list Note that the priority of the node will depend upon the distance of that node from the Head, the closest the node is to the head, higher the priority it has. So when the Cache size is full and we need to remove some element, we remove the element adjacent to the tail of the doubly linked list.
하나 하나의 과정을 잘 보자. 왜 이중 연결리스트를 사용했는지 말보다 그림을 보는 것이 이해가 빠르다.
예를 들어서 만약에 저장용량이 5인 캐시에 10개의 원소를 넣어보며 어떻게 되는지 보면 LRU 알고리즘을 더 잘 이해할 수 있다!
[1] CAPACITY 5 만큼만 넣었을 때
int arr[10] = {1, 2, 3, 4, 5, 2, 10, 7, 11, 1};
// doubly linked list의 내부
[1]->[0]->[0]->[0]->[0]->NULL
[2]->[1]->[0]->[0]->[0]->NULL
[3]->[2]->[1]->[0]->[0]->NULL
[4]->[3]->[2]->[1]->[0]->NULL
[5]->[4]->[3]->[2]->[1]->NULL
[2] CAPACITY 를 초과하여 원소를 넣었을 때 -> 교체 필요 순간
[5]->[4]->[3]->[2]->[1]->NULL
// 위 상태에서 2 를 집어넣으려고 한다. 그런데 이미 2는 있다!
// 이중 연결리스트이므로 앞뒤 노드만 수정해서 2의 노드를 최근 사용한 것처럼 앞으로 땡겨오자.
// -> 탐색에 최대 O(CAPACITY) 필요
[2]->[5]->[4]->[3]->[1]->NULL
나머지 원소들도 [2]의 논리를 반복해서 값이 들어가게 된다.
진짜 "간단" 구현
// this code is contributed by shivanisinghss2110
#include <iostream>
using namespace std;
//이중 연결 리스트
struct doublelinkedlist {
int val;
struct doublelinkedlist* next;
struct doublelinkedlist* prev;
};
// 노드의 시작과 끝을 알리는 더미 노드들
struct doublelinkedlist* head;
struct doublelinkedlist* tail;
struct doublelinkedlist* temp;
int status;
int AddNode(int value)
{
if (head == NULL) {
head = (struct doublelinkedlist*)malloc(
sizeof(struct doublelinkedlist));
if (head == NULL) {
cout << "Unable to allocate space\n";
return -2;
}
head->val = value;
tail = head;
head->prev = NULL;
}
else {
temp = tail;
tail->next = (struct doublelinkedlist*)malloc(
sizeof(struct doublelinkedlist));
if (tail->next == NULL) {
cout << "Unable to allocate space\n";
return -2;
}
tail->next->val = value;
tail = tail->next;
tail->prev = temp;
}
tail->next = NULL;
return 0;
}
int PrintCache(void)
{
if (head == NULL) {
cout << "Add a node first\n";
return -2;
}
else {
temp = head;
while (temp != NULL) {
cout << "[" << temp->val<<"]->";
temp = temp->next;
}
cout << "NULL\n";
}
return 0;
}
int GetKey(int value)
{
if (head == NULL) {
cout << "Add a node first\n";
return -1;
}
temp = head;
while (temp != NULL)
{
if (temp->val == value)
{
while (temp != head) {
temp->val = temp->prev->val;
temp = temp->prev;
}
head->val = value;
return 0;
}
temp = temp->next;
}
temp = tail->prev;
while (temp != NULL) {
temp->next->val = temp->val;
temp = temp->prev;
}
head->val = value;
return 0;
}
/*
위까지 double linked list 구현 아래부터 LRU
*/
int NodesInLRU(int number)
{
static int i = 0;
for (i = 0; i < number; i += 1) {
status = AddNode(0);
// if status is 0 then
// it will return
if (status < 0) {
cout << "Could not assign node\n";
return status;
}
}
return 0;
}
void LRUOperations(int arr[], int n)
{
for (int i = 0; i < n; ++i) {
GetKey(arr[i]);
if (status < 0) {
exit(1);
}
status = PrintCache();
}
}
int main()
{
int CAPACITY = 5;
status = NodesInLRU(CAPACITY);
int n = 10;
int arr[] = { 1, 2, 3, 4, 5, 2, 10, 7, 11, 1 };
LRUOperations(arr, n);
return 0;
}
출처 : https://www.geeksforgeeks.org/lru-cache-implementation-using-double-linked-lists/