LRU 알고리즘 (Least Recently Used Algorithm)

LRU 알고리즘 (Least Recently Used Algorithm)

LRU 알고리즘 : 가장 오랫동안 참조되지 않은 페이지를 교체하는 기법

LRU 알고리즘의 자세한 설명에 앞서 간단한 배경 지식을 설명하겠습니다!

페이지 교체 알고리즘

페이지 교체 알고리즘은 페이징 기법으로 메모리를 관리하는 운영체제에서, 페이지 부재가 발생 하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 방법입니다.

페이지 교체 알고리즘의 예로, FIFO, LFU, LRU 알고리즘 등이 있습니다.

FIFO : 페이지가 주기억장치에 적재된 시간을 기준으로 교체될 페이지를 선정하는 기법

단점 : 중요한 페이지가 오래 있었다는 이유만으로 교체되는 불합리. 가장 오래 있었던 페이지는 앞으로 계속 사용될 가능성이 있음.

LFU : 가장 적은 횟수를 참조하는 페이지를 교체

단점 : 참조될 가능성이 많음에도 불구하고 횟수에 의한 방법이므로 최근에 사용된 프로그램을 교체시킬 가능성이 있고, 해당 횟수를 증가시키므로 오버헤드 발생

LRU : 가장 오랫동안 참조되지 않은 페이지를 교체

단점 : 프로세스가 주기억장치에 접근할 때마다 참조된 페이지에 대한 시간을 기록해야함. 큰 오버헤드가 발생

참조 링크 : https://m.blog.naver.com/PostView.nhn?blogId=kyung778&logNo=60164009610&proxyReferer=https%3A%2F%2Fwww.google.com%2F

오늘은 그 중, LRU 알고리즘에 대해 공부해보겠습니다!

LRU 알고리즘 그림 설명

Input : 123145

Output : 5413

4초 : 1은 재참조된 것이므로, 가장 오랫동안 참조되지 않은 순으로 저장된 순서를 변경한다.

6초 : cache size가 가득차 5가 들어갈 수 없으므로, 가장 오랫동안 참조되지 않은 2를 제거한 후 저장한다.

LRU 알고리즘 코드 설명

참조 링크 : https://www.geeksforgeeks.org/lru-cache-implementation/

주요 코드

내가 실습하려고 했을 때에는 위의 헤더파일이 없어서 list와 unorderd_map 컨테이너를 따로 추가해 주었다.

먼저, 위 코드의 함수들에 대한 설명

list 컨테이너

참고 링크 : http://www.cplusplus.com/reference/list/list/

size : container 원소의 개수를 반환한다.

back : container의 마지막 원소의 reference를 반환한다. iterator를 반환하는 list::end와 달리, 이 함수는 직접적인 reference를 반환한다.

pop_back : contaioner의 마지막 원소를 제거하고 size를 하나 감소한다.

erase : 1) 위치 2) 범위[first,last)에 따라 값을 제거한다.

push_front : list의 맨 앞, 첫 번째 원소 앞에 새로운 원소를 삽입한다. 삽입된 원소로 값이 복사 또는 이동된다. 동시에 size를 하나 증가시킨다.

begin : contaioner에서 iterator가 가리키고 있는 첫 번째 원소를 반환한다.

unorderd_map 컨테이너

참고 링크 : http://www.cplusplus.com/reference/unordered_map/unordered_map/

end : sequence에서 iterator가 가리키고 있는 past-the-end 원소를 반환한다.

     contanier의 경우, cont.end()를 반환한다. cont는 member end 가 정의되어 있는 클래스 형태의 객체이다.

find : container에서 key 값을 갖는 원소를 찾아 iterator를 반환하고, 찾지 못하면 unordered_map::end의 iterator를 반환한다.

erase : 1) 위치 2) 키 3) 범위[first,last)에 따라 값을 제거한다.

unorderd_map::erase의 예시

 mymap["U.S."] = "Washington";
  mymap["U.K."] = "London";
  mymap["France"] = "Paris";
  mymap["Russia"] = "Moscow";
  mymap["China"] = "Beijing";
  mymap["Germany"] = "Berlin";
  mymap["Japan"] = "Tokyo";

  // erase examples:
  mymap.erase ( mymap.begin() );      // erasing by iterator
  mymap.erase ("France");             // erasing by key
  mymap.erase ( mymap.find("China"), mymap.end() ); // erasing by range




Possible output:

Russia: Moscow Japan: Tokyo U.K.: London

나는 코드를 처음 봤을 때, 라인 38, 52, 56를 이해하지 못해서 공부한 후 이해할 수 있었다!

1) Line 38        if (ma.find(x) == ma.end())

unorderd_map::find(val)는 값을 찾지 못할 경우, end()를 반환한다.

그러므로, ma에 입력한 값이 없을 경우, 조건문이 성립된다.

2) Line 52        dq.erase(ma[x]);

3) Line 56        ma[x] = dq.begin();

unorderd_map에 관한 설명을 보면, 이 부분이 있다.

unordered_map containers are faster than map containers to access individual elements by their key, although they are generally less efficient for range iteration through a subset of their elements.

[]연산자를 이용하여, 키 값에 직접 접근할 수 있다는 것!

이걸 보고 list의 값을 찾아 지우고 값을 넣을 수 있다는 것을 알 수 있었다.

그럼 코드를 이해하기 위한 함수 공부를 끝냈으니 본격적인 코드 설명!!

/* Refers key x with in the LRU cache */
void LRUCache::refer(int x) 
{ 
    // not present in cache 
    if (ma.find(x) == ma.end()) 
    { 
        // cache is full 
        if (dq.size() == csize) 
        { 
            //delete least recently used element 
            int last = dq.back(); 
            dq.pop_back(); 
            ma.erase(last); 
        } 
    } 
  
    // present in cache 
    else
        dq.erase(ma[x]); 
  
    // update reference 
    dq.push_front(x); 
    ma[x] = dq.begin(); 
} 

input : 123145

cache size : 4

1 2 3 : ma에서 값을 찾을 수 없으므로 dq의 front와 ma에 값을 채워 넣는다.

ma (1, {1}), (2, {2}), (3, {3})

dq 3, 2, 1

1 :  ma에서 값을 찾을 수 있으므로 dq에서 현재 넣은 값을 제거하고 dq의 front와 ma에 값을 채워 넣는다.

<가장 오랫동안 참조되지 않은 값을 dq의 back에 놓기 위함>

ma (1, {1}), (2, {2}), (3, {3})

dq 1, 3, 2

4 : ma에서 값을 찾을 수 없으므로 dq의 front와 ma에 값을 채워 넣는다.

ma (1, {1}), (2, {2}), (3, {3}), (4, {4})

dq 4, 1, 3, 2

5 : ma에서 값을 찾을 수 없고 cache가 꽉 찼으므로 dq의 back의 값을 dq와 ma에서 제거한 후, 현재 값을 dq의 front와 ma에 채워 넣는다.

ma (1, {1}), (3, {3}), (4, {4}), (5, {5})

dq 5, 4, 1, 3

Output : 5413

전체 코드

/* We can use stl container list as a double 
   ended queue to store the cache keys, with 
   the descending time of reference from front 
   to back and a set container to check presence 
   of a key. But to fetch the address of the key 
   in the list using find(), it takes O(N) time. 
    This can be optimized by storing a reference 
    (iterator) to each key in a hash map. */
#include <iostream>
#include <list>
#include <unordered_map>
using namespace std; 
  
class LRUCache 
{ 
    // store keys of cache 
    list<int> dq; 
  
    // store references of key in cache 
    unordered_map<int, list<int>::iterator> ma; 
    int csize; //maximum capacity of cache 
  
public: 
    LRUCache(int); 
    void refer(int); 
    void display(); 
}; 
  
LRUCache::LRUCache(int n) 
{ 
    csize = n; 
} 
  
/* Refers key x with in the LRU cache */
void LRUCache::refer(int x) 
{ 
    // not present in cache 
    if (ma.find(x) == ma.end()) 
    { 
        // cache is full 
        if (dq.size() == csize) 
        { 
            //delete least recently used element 
            int last = dq.back(); 
            dq.pop_back(); 
            ma.erase(last); 
        } 
    } 
  
    // present in cache 
    else
        dq.erase(ma[x]); 
  
    // update reference 
    dq.push_front(x); 
    ma[x] = dq.begin(); 
} 
  
// display contents of cache 
void LRUCache::display() 
{ 
    for (auto it = dq.begin(); it != dq.end(); 
                                        it++) 
        cout << (*it) << " "; 
  
    cout << endl; 
} 
  
// Driver program to test above functions 
int main() 
{ 
    LRUCache ca(4); 
  
    ca.refer(1); 
    ca.refer(2); 
    ca.refer(3); 
    ca.refer(1); 
    ca.refer(4); 
    ca.refer(5); 
    ca.display(); 
  
    return 0; 
} 
// This code is contributed by Satish Srinivas