[운영체제] Page Replacement Policy (페이지 교체 알고리즘)

[운영체제] Swapping #1

Swap과 관련된 메커니즘에 이어서 page replacement policy에 대해서 알아보자

 

 

replacement의 목적은 Cache miss를 최소화하기 위함이다.

Cache가 여기서 왜 나왔을까? > 메모리는 하드디스크의 cache역할을 하기 때문이다.

 

Average Memory access time(AMAT) - 평균 메모리 접근 시간

AMAT = (Phit * Tm) + (Pmiss * Td)

 

• Tm : 메모리에 접근하는 시간
• Td : 디스크에 접근하는 시간
• Phit : cache에 찾고자 하는 data가 있을 확률
• Pmiss : cache에 찾고자 하는 data가 없을 확률

일반적으로 Td가 Tm보다 훨씬 크기 때문에 Pmiss를 줄이는 게 성능 향상에 매우 도움이 된다.

---

여러 가지 Replacement Policy에 대해서 알아보자

 

1. Optimal Replacement Policy

 

미래에 어떤 data를 사용할지 미리 알고 있는 경우에 사용 -> 가장 먼 미래에 사용될 page를 쫓아낸다

(미래를 알 수는 없으므로 실제로는 사용이 불가능한 policy)

다른 알고리즘의 성능을 비교하는 비교군으로 사용됨.

 

Optimal Policy의 동작을 알아보자

cold start : 시스템에서 캐시된 데이터가 없는 상태로 시작되는 경우를 의미한다.

 

 

아래는 Optimal replacement policy를 적용한 BOJ 문제이다.

[백준 1700] 멀티탭 스케줄링 C++

optimal replacement policy를 문제에 적용해서 익혀보고 싶다면 풀면 좋을지도?

그리디 알고리즘에서 자주 적용되는 방식이기도 하다

---

2. Simple Policy : FIFO (Queue)

page를 들어온 순서대로 replace 하는 방식이다.(매우 간단)

 

FIFO의 동작을 자세히 알아보자

 

 

 

FIFO의 가장 큰 문제점은 BELADY'S ANOMALY가 발생할 수 있다는 점이다.

 

BELADY'S ANOMALY

 

 

 

 

 

 

cache의 개수가 늘어남에도 불구하고 cache miss의 횟수가 증가하는 현상을 그래프로 보여주고 있다.

 

실제로 캐시의 크기가 3일 때, 4일 때 직접 수행해 보면 캐시의 크기가 4일 때 캐시 미스가 증가함을 볼 수 있다.

---

3. Simple Policy : Random

무작위로 내보낼 page를 선택한다

---

과거의 접근을 바탕으로 미래의 접근을 예측하는 방법을 사용해야 한다.

 

과거의 접근을 사용하는 알고리즘 중에서 가장 많이 사용되는 것이 LRU 방식이다.

LRU(Least Recently Used) : 마지막으로 사용된 시간이 가장 오래된 page를 쫓아내는 방식

• 지역성을 기반으로한 알고리즘
• Stack을 사용한 알고리즘(queue를 사용하지 않기 때문에 Belady's anomaly가 없음)
• 구현이 어렵다. (시간 오버헤드, 공간 오버헤드가 크다 -> page가 언제 접근되었는지 모두 기록하고 있어야 함)
• 모든 workload에 유용하지는 않다. (아래에서 확인)

 

LRU를 사용한 replacement의 동작을 자세히 알아보자

 

첫 번째 Miss를 보면 3에 접근함과 동시에 2를 방출한다.

3에 접근하기 이전에 접근했던 기록을 보면 1, 0, 2 순으로 최근에 접근했다.

따라서 가장 접근한 지 오래된 2번 프레임을 테이블에서 방출할게 된다.

 

사용된지 가장 오래된 page를 Evict 하고 있다.

---

Workload Example 

100개의 page에 랜덤으로 접근하는 상황 : The No-Locality Workload

page의 지역성이 적용되지 않기 때문에 최적 페이지 교체 알고리즘 이외의 모든 알고리즘은 캐시의 크기게 비례해서 Page Hit Rate가 높아진다.

---

80%의 접근 시도가 20개의 페이지에 국한되고, 20%의 접근 시도가 80개의 페이지에 국한된다 : The 80-20 Workload

지역성을 기반으로 한 알고리즘인 LRU 가 FIFO나 RAND 알고리즘보다 효율적임을 알 수 있다.

 

---

 50개의 page가 loop를 돌면서 순차적으로 접근되는 상황 : The looping Sequential

LRU와 FIFO는 Cache의 크기가 49까지 모두 cache miss가 발생한다. (최악이 된다)

---

LRU는 page가 언제 접근되었는지 모두 기록하고 있어야 하므로 구현이 어렵고 공간 오버헤드가 크다.

따라서 LRU와 비슷한 동작을 하면서도 가벼운 방법이 필요하다

 

그 중 대표적인 하나가 Clock Algorithm이다.

 

Clock Algorithm

• 모든 page가 순환 list를 이룬다고 가정
• 특정 page를 시계바늘 돌듯이 가리킨다고 가정

 

 

 

Clock 알고리즘은 과거의 기록을 모두 가지고 있지 않기 때문에 LRU만큼 효율적이지는 못하다.

하지만 그만큼 구현이 단순해지고 시간, 공간적 오버헤드가 줄어든다는 장점이 있다.

모든 컴퓨터 공학은 Trade-Off.

 

---

Page Selection Policy

- 어떤 페이지를 어떤 순서로 불러올 것인가?

 

 

Prefetching : OS가 어떤 page를 사용할지 예측해서 미리 page를 읽어오는 방식

- 순차 접근인 경우 매우 유용하다.

 

Clustering, Grouping : 작은 크기의 Write 여러 개 보다, 큰 크기의 Write 하나를 통해서 입출력 overhead를 줄이는 방식