메모리 교체 정책들의 구현 및 벤치마킹 프로그램을 통한 모의실험

프로젝트의 목적

ㆍ 다양한 페이지 교체 알고리즘을 직접 구현해 봄으로써 동작 과정을 이해한다.

ㆍ 각 알고리즘의 페이지 교체 과정을 분석하여 특성을 파악한다.

ㆍ 구현한 프로그램을 통해 모의실험을 함으로써 각 알고리즘을 평가해 본다.

---

프로젝트의 내용

ㆍ 여러 가지 페이지 교체 알고리즘에 대응하는 벤치마킹 프로그램을 구현한다.

ㆍ 구현한 벤치마킹 프로그램을 이용해 모의실험을 진행한다.

ㆍ 모의실험을 통해 각각의 알고리즘을 평가한다.

---

페이지 교체 알고리즘의 테스트

ㆍ 각 페이지 교체 알고리즘을 공평하게 평가하기 위하여 위 표와 같은 입력 예제를 각 알고리즘에게 동일하게 주어 테스트를 진행하였다.
ㆍ 각 페이지 알고리즘은 Effective Access Time(EAT)으로 평가하였다.

 

 

ㆍ 4가지 입력 예제에 대해 각 알고리즘의 hit, fault, EAT 지수를 표로 나타낸 것이다.
ㆍ EAT 지수는 메모리 접근 시간을 200 nanosecond로, fault의 평균 시간을 8 millisecond의 시간으로 가정을 하고 계산한 수치이다.
ㆍ 각 알고리즘의 성능평가는 EAT 지수에 의해서 평가한다.

---

테스트 결과 분석

ㆍ 예제 1에 대한 각 알고리즘의 EAT 지수를 막대그래프로 나타내 보았다.
ㆍ 그래프를 보면 Optimal의 성능이 가장 좋고 LRU의 성능이 가장 안 좋다는 것을 알 수 있다.
ㆍ FIFO, LFU, MFU 알고리즘은 EAT 지수가 똑같다는 것을 알 수 있다.

 

 

ㆍ 예제 2에 대한 각 알고리즘의 EAT 지수를 막대그래프로 나타내 보았다.
ㆍ 예제 1과 마찬가지로 Optimal의 성능이 가장 좋고 LRU의 성능이 가장 좋지 않다는 것을 알 수 있다.

 

 

ㆍ 예제 3에 대한 각 알고리즘의 EAT 지수를 막대그래프로 나타내 보았다.
ㆍ 그래프를 보면 Optimal의 성능이 가장 좋고 차례대로 FIFO의 성능이 좋지 않다는 것을 알 수 있다.

 

 

ㆍ 예제 4에 대한 각 알고리즘의 EAT 지수를 막대그래프로 나타내 보았다.
ㆍ 역시나 Optimal의 성능이 가장 좋다는 것을 알 수 있다.

---

페이지 교체 알고리즘의 분석과 평가

FIFO 알고리즘

ㆍ 메모리에 가장 먼저 들어오는 페이지를 가장 먼저 교체해주는 방법이다.
ㆍ 구현하기가 제일 간단한 알고리즘이었다.
ㆍ 테스트를 진행할 때 4가지 예제에 대해서 가장 성능이 좋지 못했던 알고리즘이기도 하다.

 

LFU 알고리즘

ㆍ 참조 횟수가 가장 적은 페이지를 교체해주는 방법이다.
ㆍ 테스트 결과 대체로 FIFO 알고리즘보다 괜찮은 성능을 보였다.
ㆍ 벤치마킹 프로그램을 구현할 때 참조 횟수를 저장하는 방법으로 할당될 페이지의 수만큼 배열을 선언했다. 실제 시스템 상에서 구현을 하면 공간 복잡도가 높아질 우려가 있다고 생각한다.

MFU 알고리즘

ㆍ LFU 알고리즘과는 반대로 참조 횟수가 가장 많은 페이지를 교체해주는 방식이다.
ㆍ 테스트 결과 대체로 FIFO 알고리즘보다는 괜찮을 성능을 보였으며, LFU 알고리즘과 마찬가지로 중간 이상의 성능을 보였다.
ㆍ MFU 알고리즘 또한 참조 횟수를 저장하는 방법으로 할당될 페이지의 수만큼 배열을 선언했다. 실제 시스템 상에서 구현을 하면 공간 복잡도가 높아질 우려가 있으니 주의해야 할 필요가 있다.

LRU 알고리즘

ㆍ 메모리에서 가장 오랜 시간을 보낸 페이지를 교체하는 방식의 알고리즘이다.
ㆍ 예제 1, 예제 2에서는 가장 성능이 안 좋았지만, 예제 3, 예제 4의 경우 우수한 성능을 보였다.
ㆍ 대체적으로 좋은 성능을 보인다고 알려진 알고리즘이다. 좀 더 많은 예제에 대해 테스트를 진행해 보아야 성능을 정확히 파악할 수 있다고 생각한다.

Optimal 알고리즘

ㆍ 앞으로 참조될 확률이 제일 낮은 페이지를 교체하는 방식의 알고리즘이다.
ㆍ 모든 예제에 대해서 가장 우수한 성능을 보인 알고리즘이다.
ㆍ 특정 페이지가 미래에 참조될 확률을 구한다는 것 자체가 불가능하므로, 현실적으로 시스템에 구현하기란 어려울 것이라고 생각한다.

---

GitHub - qlsdud0604/memory-replacement-manager: 여러가지 메모리 교체 정책들의 구현 및 벤치마킹 프로그램