Virtual Memory Management-2

Least Recently Used (LRU) Algorithm

그렇다면 LRU를 어떻게 구현할까?

 

1. Timestamp 

  모든 page마다 counter를 가지게해서 구현한다

2. Stack 

  stack 형태로 구현한다

 

1, 2번 모두 overhead가 크고 이를 지원할만 한 hw도 없다. 따라서 Referenced bit을 이용해서 Approximation 대충 근사치를 구해보자 

referenced bit은 처음 os에 의해 0으로 설정되어있다가 페이지가 참조되었을 때 hw에 의해 1로 set된다.

 

 

LRU-Approximation

1.  Reference bit을 이용하는 방법

각 page마다 8bit짜리 참조비트를 부여한 다음 일정시간(timer interrupt마다 참조되었을경우 shift 연산을 수행한다. 따라서 최근 8bit를 보고 history를 유추할수있다. unique하지 않으므로 겹치는경우 fifo같은 추가 규칙 필요

example)

page0 11000100

page1 01110111

 

1은 참조되었다는 뜻

page 1 is replaced

젤 작은값이 교체된다

 

2. Second-Chance Algorithm

요거는 fifo + reference bit을 활용하는 방식이다. 일단은 fifo 방식으로 순서대로 돈다.

쉽게 생각해서 reference bit이 0, 1로 되어있을텐데 0이면 바로 교체하고 1이면 0으로 바뀐뒤 arrival time을 current time으로 reset한다. 즉 다시 돌아올동안 또 참조된다면 그 page는 자주 사용되는 page 이므로 교체되지 않을것이다.

이를 구현하기 위해서 circular queue를 이용한다. 만약 한바퀴 돌았는데 다 1이면 0으로 reset한다.

 

 

2-1 enhanced Second-Chance Algorithm (NRU)

먼저 reference bit 과 modify bit 두개를 사용한다.  modify bit은 

(0,0) 최근 사용되지도 변경되지도 않은 page - 변경하기 best

(0,1) 최근 사용되지는 않았지만 변경됐음 - 애매하다 교체전에 사용될 수도 있음

(1.0) 최근 사용되었지만 변경되진 않음 - 아마 또 사용될거임.

(1,1) 최근 사용되었고 변경된 page - 또사용될거고 교체전이라서 방금 교체됨.

 

LRU를 근사시킨 알고리즘, 최근에 사용하지 않은 페이지를 교체하는 기법
LRU 알고리즘은 가장 오래전에 참조된 페이지를 교체하는것에 비해, 클럭 알고리즘은 오랫동안 사용하지 않은 페이지중 하나를 교체한다.
즉, 최근에 참조되지 않은 페이지를 교체대상으로 선정한다는 측면에서 LRU와 유사하지만 교체되는 페이지의 참조시점이 가장 오래되었다는 것을 보장하지는 못한다는 점에서 LRU를 근사시킨 알고리즘으로 볼 수 있다.

 

출처 : https://eunhyejung.github.io/os/2018/07/24/operatingsystem-study15.html

위의 순서대로 우선순위를 배정해서 교체한다.

이전에 배웠던 Table Page Entry에 대해서 다시 알아보자

 

여기서 R과 M이 enhanced Second-Chance Algorithm 방식에 쓰이는거다. 그리고 이 modify bit은 cache memory를 update할때도 쓰인다.( modify가 1이라면 변경됐다는거니까 그때 갱신한다)

 

 

 

---

그럼 다음 문제인 Allocation of Frames 에 대해 생각해보자

이 문제는 process에 얼만큼의 frames을 할당할건지에 대한 고민이다.

 

 

정해진만큼 할당해 줄것인가

우선순위에 따라 더 할당해 줄 것인가

 

Global : 모든 frame에 대해서 교체할 대상 고른다

Local : 할당받은 frame 중에서 교체할 대상 고른다.

 

 

frame 개수와 page-fault의 관계

 

 

 

Thrashing

여기서 만약 frame number가 부족하다면 어떻게 될까?

프로세스는 충분한 frame이 없다면 계속해서 page fault를 발생시킨다. 이러한 상태를 Thrashing이라고 한다.

paging time > excution time

 

어느 수준 이상으로 multi processing을 실행시키면 page-fault 처리한다고 cpu 다써서 효율성이 쭉 떨어진다.

 

Thrashing을 제어하기 위한 방법으로 local replacement algorithm을 생각해 볼 수 있다.

만약 특정 process에서 thrashing이 발생하더라도 local하게 자신의 frame을 넘어 다른 process들에게는 영향을 안주니까. 하지만 이 방법이 완전한 해결 방법은 아니다. 만약 몇몇의 process들이 trashing 상태라면 그렇지 않은 process의 서비스 시간에도 영향을 준다.

완전한 해결을 위한 방법은 바로 process들에게 필요한만큼 최대한 많이 주는것이다. 하지만 여기서 궁금한점은 바로 process가 얼마만큼의 frame이 필요로하는지이다. 이를 알아보기위한 전략으로 locality model을 사용한다.

아래 그림을 보면 알듯이 process가 실행될때 locality에서 locality로 움직인다. 특정 집단을 이루며 이 집단대로 이동함을 알 수 있다.

 

locality in a memory

---

Thrashing 해결 방법.

Working-Set model

이런 locality의 추정에 기반한것이 working set model이다. 

이 모델을 활용하기 위해선 delta로 표시되는 working set window를 먼저 정해야한다. 이 window를 통해 working set을 정의한다. 

위의 그림은 window가 10인 경우이다. 10개씩 끊어서 Working set을 정할 수 있다. 이 set에서 구한 size(t1인경우 5 t2인 경우 2) 만큼 frame을 할당해주면 thrashing을 피할 수 있다.

 working set의 정확성을 위해서는 이 window의 크기를 잘 정해야한다. window가 너무 크면 locality가 겹칠것이고 너무 작으면 locality의 특성을 반영하지 못한다. 

 

 

 

Page-Fault Frequency

working set model 보다 좀 더 직관적인 방법이 있다.

 

그냥 frames에 따른 page-fault보고 적정선 만큼 frame을 할당해주는 방식이다.

---

또 다른 고민거리

Fragmentation 입장에서는 작은게 좋고 나머지는 큰게 좋다.

 

 

 

예시

---