[Algorithms] Replacement Algorithms: LRU

Replacement Algorithms: LRU

---

포스트 난이도: HOO_Middle

[Notice] 포스트 난이도에 대한 설명

---

 

# LRU

이전 포스트에서 Replacement algorithms에 해당하는 FIFO와 Optimal에 대해서 알아보았다.

---

https://whoishoo.tistory.com/250

[Programming] Replacement Algorithms: Optimal

---

https://whoishoo.tistory.com/248

[Programming] Replacement Algorithms: FIFO

---

이번에는 LRU algorithm에 대해서 살펴보도록 하자.

Optimal 알고리즘을 알고 있다면 LRU 알고리즘을 이해하는 건 쉽다.

OPtimal이 앞으로 나올 페이지에 대한 예측을 했다면, LRU는 이전에 나왔던 페이지를 비교하여 교체하는 특징을 가지고 있다.

LRU는 이전에 가장 오랫동안 페이지 교체가 이루어지지 않았던 페이지를 우선적으로 교체해주는 알고리즘이다.

예를 들어 1,3,5,7이라는 페이지가 Stack 되어 왔는데 9라는 새로운 페이지를 Stack 하고자 기존 페이지를 교체해야 한다면, 이 과정에서 1의 경우 가장 오랫동안 페이지가 교체된 적이 없는 경우이기에 1을 교체하여 9를 Stack 해준다.

여기서 유의할 점은 마치 예시만 보면, FIFO로 보일 수는 있지만 처음 적재되었던 페이지를 교체하는 FIFO와는 다를다.

예를 들어서, 1,3,5,7,1,9라는 페이지 예제가 있다고 가정해보자.

이 경우 FIFO에서는 9라는 페이지를 Stack 해주기 위해서 1을 교체하고 9를 넣어준다.

하지만 LRU에서는 9 이전에 1이 한번 Hit 되었기 때문에 그다음 오랫동안 Hit이 되지 않았던 3이 9로 페이지 교체가 이루어진다.

이처럼 LRU는 지속적으로 나오지 않는, 즉 Hit이 가장 오랫동안 되지 않았던 페이지를 새로운 페이지와 교체해준다.

---

# LRU Examples

페이지 교체가 이루어지는 LRU 예제를 살펴보도록 하자.

Optimal과의 차이를 살펴보기 위해 이전 Optimal 포스트의 예제와 조건은 동일하게 지정하였다.

# Example of memory blocks 
7012030423031423454676 

# Description 
2 way set cache with 4 blocks

제시된 memory blocks들을 LRU 알고리즘을 통해 페이지 교체를 해줄 예정이며, 조건은 2 way set에 chache는 4 blocks이기 때문에 2개의 set으로 나뉘어 있다는 걸 알 수 있다.

0
2
7
1

# Example of memory blocks 
7012030423031423454676 
MMMMH

# Description 
2 way set cache with 4 blocks

3의 경우는 STACK 되어 있지 않은 페이지이기 때문에 LRU 알고리즘을 사용하여 교체해줘야 한다.

이때 LRU이기 때문에 제일 오랫동안 HIT 되지 않았던 7과 교체가 이루어진다.

0	0
2	2
7	3
1	1

# Example of memory blocks 
7012030423031423454676 
MMMMHMH

# Description 
2 way set cache with 4 blocks

그다음 4의 경우도 페이지 교체가 이루어져야 하기 때문에 0과 2 중에서 제일 오랫동안 H이 되지 못한 2가 4로 교체된다.

0	0	0
2	2	4
7	3	3
1	1	1

# Example of memory blocks 
7012030423031423454676 
MMMMMMHM

# Description 
2 way set cache with 4 blocks

이런 식으로 계속 반복하여 페이지 교체를 하는 것이 LRU algorithm이다.

---