[Algorithms] Replacement Algorithms: Optimal

Replacement Algorithms: Optimal

---

포스트 난이도: HOO_Middle

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

---

# Optimal

FIFO Repalcement algorithm에 이어 Optimal에 대해서 살펴보도록 하겠다.

https://whoishoo.tistory.com/248

[Programming] Replacement Algorithms: FIFO

Optimal replacement algorithm은 FIFO와 다른 점은 사전에 미리 사용할 페이지에 대해서 알고 있다는 점이다.

Optimal은 앞으로 나올 페이지 중에 제일 오래 사용이 되지 않을 페이지를 교체해주는 알고리즘 방식이다.

LRU에 대해서도 다음 포스트에서 살펴볼 예정이지만 Optimal과 LRU를 미리 비교하자면 LRU의 경우는 가장 오래 사용이 되지 않은 알고리즘을 교체하는 반면에 Optimal은 앞으로 가장 오래 사용이 되지 않을 페이지를 교체해준다는 점에서 비슷하면서도 방식의 차이를 보인다.

---

# Optimal Example

# Example of memory blocks
7012030423031423454676

# Description
2 way set
cache with 4 blocks

위의 예제에서는 memory block, 2 way set, 4 block cache에 대한 조건을 제시하고 있다.

이 조건을 가지고 Optimal algorithm을 통해 페이지 교체를 할 경우 아래와 같은 과정이 도출된다.

0
2
7
1

# Example of memory blocks
7012030423031423454676
MMMMM

# Description
2 way set
cache with 4 blocks

---

0	4
2	2
7	3
1	1

# Example of memory blocks
7012030423031423454676
MMMMMMHMHM

# Description
2 way set
cache with 4 blocks

2 set이기 때문에 페이지 교체를 4와 3이 동시에 처리하여 작성하였다.

실제로 문제를 풀거나 표를 사용하여 Optimal을 표현할때는 메모리당 하나의 페이지 교체씩 이루어지니 참고하기 바란다.

(빠른 예제 결과를 나타내기 위해서 2개를 동시에 교체했지만 정석대로 표현하면 하나씩 메모리에 교체해야 한다.)

따라서 사실상 위의 과정에서는 4 페이지가 먼저 교체되기 때문에 4 페이지 교체 후 3 페이지는 다음 메모리에서 교체해주면 된다.

---

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

# Example of memory blocks
7012030423031423454676
MMMMMMHMHMMHHH

# Description
2 way set
cache with 4 blocks

Hit인 경우에는 페이지 교체가 필요 없지만 여기서 보듯이 0이 나와 페이지 교체가 필요할 경우, 앞의 페이지를 확인하여 제일 오랫동안 나오질 않은 페이지와 교체를 해주면 된다.

이렇듯 하나의 페이지가 교체되면 나머지 set의 경우는 기존의 페이지가 그대로 유지된다.

---

Optimal algorithm에서는 앞으로 나올 페이지에 대한 부분을 예상하고 오랫동안 나오질 않을 페이지를 우선적으로 교체해주는 것이 주요 특징이다.

또한 2 way set이며, cache가 4 block이기에 2 set로 문제를 해결해야 한다.

만약에 4 way set이며, 4 block이 조건일 경우에는 1 set로 산출하면 된다.

n, m, k가 임의의 값이라고 가정한다면 n blck / m way set = k set 인 것이다.

 

---