Page Replacement Policy (페이지 교체 정책)

 

Page Replacement Policy

 

페이지 교체가 필요한 이유는 RAM의 크기가 제한적이고 그에 반해 RAM에 올라갈 페이지들은 많기 때문이다.

 

지금의 환경은 멀티 프로세스 환경으로 한번에 여러 개의 프로세스가 메모리에 올라가야 한다. 그래서 램이 꽉 차거나 혹은 어느 일정 정해진 수준을 넘어서게 되면 보조 기억장치와의 swap이 필요하다. 이때 램의 어떤 페이지를 교체하겠냐를 정할 때 필요한 정책이 replacement policy이다.

 

캐시 미스, 캐시 히트, 평균 메모리 접근 시간으로 어떤 알고리즘이 더 효율적인가를 따질 수 있다.

(캐시 미스의 횟수를 최소화하고 캐시 히트 횟수를 최대화한다.)

 

1. 캐시 미스(Cache miss)

찾으려고 하는 페이지가 물리메모리에 존재하지 않을 때 캐시 미스라고 한다.

 

2. 캐시 히트(Cache hit)

접근한 페이지가 이미 메모리 위에 존재했을 때의 횟수를 캐시 히트라고 한다.

 

3. 평균 메모리 접근 시간(Average Memory Access Time, AMAT)

캐시미스와 캐시 히트의 정보를 안다면 AMAT는 다음과 같은 식으로 계산할 수 있다.

AMAT = Tm + (Pmiss * Td)

• Tm은 메모리 접근 비용
• Td는 디스크 접근 비용
• Pmiss 는 캐시에서 데이터를 못찾을 확률(미스)를 나타낸다.
• (Pmiss는 각각 0.0 에서 1.0 사이의 값을 가지며 때때로 확률 대신 퍼센트 미스율을 언급하기도 한다.)

여기서 알 수 있는 점은 메모리 접근 비용은 항상 지불해야 하고, 메모리에서 데이터를 못 찾을 경우 디스크로부터 데이터를 가져오는 비용을 추가로 지불해야 한다.

 

1.  Optimal replacement policy(최적 교체 정책)

가장 나중에 접근될 페이지를 교체하는 방식이다. 

 

장점  - 가장 먼 미래에 접근될 페이지를 버림으로써 최근에 접근될 페이지를 접근할 때 캐시 미스가 나지 않는다. 앞으로 나올 어떤 알고리즘보다 높은 히트율을 갖는다.

 

한계-  미래를 미리 알기 힘들다 -> 구현이 힘들다

 

*cold start miss(최초 시작 미스) : 처음에 비어있는 상태로 시작하기 때문에 당연히 미스

2.  FIFO

들어온 순서대로 교체하는 방식이다.

 

장점 - 구현이 매우 쉽다

 

한계 - 공간 지역성을 고려할 수 없다. 많이 참조가 되어 중요한 페이지 임에도 불구하고 먼저 들어왔다는 이유로 메모리에서 방출될 수 있다는 한계가 있다. 최적 교체 정책에 비해 매우 성능이 좋지 않다.

 

문제점 - 벨라디의 모순(Belady's Anomaly) 발생

 

3.  Random selection

메모리 상에 올라가있는 페이지 중에서 무작위로 선택해서 교체하는 방식이다.

 

장점 - 구현이 매우 쉽다

 

한계 - 선택할 때 운에 의존하는 정책이다. 어떠한 때는 좋은 성능을 보일 수도 있고 아닐 수도 있다.

 

4.  LRU, LFU

지역성의 원칙에 기반을 둔 정책들이다. 과거에 사용했던 이력을 참조해서 교체할 페이지를 고르는 정책이다.

 

1) LRU 

Least Recently Used로 가장 오래 전에 사용하였던 페이지를 교체하는 방식이다. 거의 최적 교체 정책과 비슷한 수준의 결과까지 보여줄 수 있다.

 

2) LFU 

Least Frequently Used 로 가장 적은 빈도로 사용된 페이지를 교체하는 방식이다.

 

<-> MFU(Most-Frequently -Used), MRU(Most-Recently-Used) 는 가장 자주 쓰인 페이지나 가장 최근에 쓰인 페이지를 교체하는 정책인데 잘 작동하지 않는다. ( 대부분의 프로그램에서 관찰되는 지역성의 원칙을 오히려 무시하는 정책이기 때문)

 

5 . NRU

Not Recently Used 로, LRU보다 적은 오버헤드로 비슷한 성능 달성을 목적으로 한 정책이다.

LRU와 달리 두개의 bit vector를 사용한다. Refrence bit vector(r) 그리고 Update bit vector(m) 사용한다.

* Reference bit vector - 최근에 참조되었는 지 여부

* Update bit vector - 메모리에 로드된 이후에 업데이트(쓰기)가 발생했는지 여부 (페이지의 내용이 변경되었는지)

 

그래서 교체하는 데 우선순위가 생기게 되는데 숫자가 높을수록 나중에 교체한다. 또한 일정 시간마다 모든 페이지 프레임의 reference bit를 0으로 초기화한다.

 

교체 순서

1등 (r, m) = (0, 0)
2등 (r, m) = (0, 1)
3등 (r, m) = (1, 0)
4등 (r, m) = (1, 1)

 

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

그래서 비슷한 동작을 하면서도 가벼운 방법이 필요한데 그것이 바로 Clock Algorithm이다.

 

Clock Algorithm

 

 

모든 page가 순환 리스트를 이루고 특정 page를 시계바늘 돌듯이 가리킨다고 가정할 때 

현재 가리키고 있는 임의의 페이지를 가리키는 clock hand로 페이지를 교체할 시점에 어느 페이지를 선택할 지 결정한다.

<clock algorithm에서 교체할 page를 선택하는 방법>

clock hand가 가리키는 page의 reference bit가 1인 경우, 0으로 바꾸고 Clock hand가 다음 페이지를 가리키도록 한다.(최근에 사용되었다는 의미이므로 skip).

이 과정을 반복하다가 reference bit가 0인 페이지를 만나면 최근에 사용되지 않은 페이지이므로 해당 페이지를 교체한다.

모든 reference bit이 1이면 모든 페이지가 reference되고 있다는 의미이므로 메인 메모리가 현재 Over Commit되고 있다는 의미이며(실제로 모든 페이지가 메모리에 유지되어야 하지만 현재 시스템은 그만큼의 메모리를 제공할 수 없는 상황을 의미), 모든 페이지가 빈번하게 접근되고 있어 skip 구간이 굉장히 많이 되므로 clock hand도 빠르게 회전하게 된다.

-> clock algorithm은 LRU를 기반으로 업그레이드한 것이지만, 메모리 Over Commit이 일어나게 되면 FIFO 로 전환된다.

 

과거의 기록을 모두 가지고 있지 않기 때문에 LRU만큼 효율적이지는 못하다. 하지만 그만큼 구현이 단순해지고 시간, 공간적 오버헤드가 줄어든다는 장점이 있다.

 

Enhanced second chance algoritm

clock 알고리즘과 다르게 NRU 알고리즘처럼 reference bit(r) 와 update bit(m)을 모두 사용한다. 

 

(r, m) 이

(0,0) 이면 교체 페이지로 결정한다.

(0,1) 이면 (0,0)으로 바꾸고 write-back-list에 추가한 뒤에 이동한다.

(1,0) 이면 (0,0)으로 바꾼 후에 이동한다.

(1,1) 이면 (0,1)로 바꾼 후에 이동한다.

 

*write-back-list : 주로 캐시나 버퍼와 같은 메모리 관리 시스템에서 변경된 데이터가 임시로 저장된다. 변경된 페이지의 내용을 임시로 저장하는 용도로 사용된다.

페이지가 교체되기 전에 해당 페이지의 변경된 데이터가 "write-back-list"에 저장되면, 이후에 디스크로의 실제 쓰기 작업이 수행될 때 해당 변경된 데이터가 디스크로 영구적으로 저장된다.

 

 

Belady's anomaly

 

FIFO 정책에서 페이지 프레임이 많아짐에도 불구하고 페이지 폴트의 수는 오히려 증가하는 현상을 말한다.

 

FIFO 알고리즘은 가장 오래된 페이지를 우선적으로 교체한다. 페이지 프레임 수가 증가하더라도, 새로운 페이지가 캐시되는 비율은 증가하지 않아서 시간이 지남에 따라 더 오래된 페이지가 계속해서 교체되어 페이지 부재(page fault)율이 증가.

 

 

Page Selection Policy

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

 

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

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

 

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

 

 

 

참조

 

책 / 운영체제 아주 쉬운 세 가지 이야기

https://velog.io/@jewelrykim/%ED%8E%98%EC%9D%B4%EC%A7%80-%EA%B5%90%EC%B2%B4-%EC%A0%95%EC%B1%85-A-to-Z#%EF%B8%8F-%EC%B6%94%EA%B0%80beladys-anomaly

https://hyeo-noo.tistory.com/102#Workload%--Example%C-%A-

https://jiming.tistory.com/176