page fault 발생을 최소화하기 위한 page replacement 기법에 대해서 알아보자
이 포스팅에서는 Fixed allocation(FA) based 교체 기법을 정리했다.
- Local replacement : 각 프로세스가 고정된 크기의 메모리를 받아서 프로그램이 실행하는 동안 메모리크기가 변하지 않는경우.
프로세스가 교체돼야할때 자신의(local) page와 교체해야하기 때문에 local이다.- Fixed allocation based 교체 기법
- MIN(OPT, B0) algorithm
- Random algorithm
- FIFO(First In First out) algorithm
- LRU(Least Recently Used) algorithm
- Additional reference-bits algorithm
- LFU(Least Frequently Used) algorithm
- NUR(Not Used Recently) algorithm
- Clock algorithm
- Enhanced clock algorithm
- Fixed allocation based 교체 기법
- Global replacement : 교체돼야할때 내 프로세스의 page가 아닌 다른 프로세스의 page가 교체될 수도 있는 기법
- Variable allocation based 교체 기법
- VMIN(Variable MIN) algorithm
- WS(Working Set) algorithm
- PFF(Page Fault Frequency) algorithm
- Variable allocation based 교체 기법
MIN algorithm (OPT, B0 algorithm)
OPT인 이유는 MIN 기법이 최적의 기법이기 때문이다. 그럼 이 기법말고 다른 기법이 왜 존재하는지 의문이 들 수 있지만 최적의 기법이라도 overhead도 봐야하기 때문에 무조건 사용할 수는 없다.
또 한가지는 이 기법은 실행하기 전에 페이지 참조 순서 (reference string)을 미리 알고있다는 가정하에 사용하는 알고리즘이기 때문에 구현이 불가능하다.
그래서 성능 측정 도구로 사용한다.
- Scheme
- 앞으로 가장 오래동안 참조되지 않을 page를 교체
- Tie-breaking rule : page 번호를 기준으로 가장 크거나 가장 작은 page를 교체.(정하기 나름)
- Unrealizable (구현불가능)
- Usage : 성능측정도구로 사용
w가 들어와야하는 상황이다. x,y,z 중 현재 시점 기준으로 앞으로 제일 늦게 참조될 예정인 y를 victim으로 선정한다.
추가로 현 시점에서 참조될 예정인 시간까지의 거리를 Df(y), forward distance라고 한다.
time6을 보면, memory가 모두 꽉차있는 상태이기 때문에 새로 들어올 page5의 victim page를 찾아야하는 상황이다. Df(y) 즉 가장 늦게 참조될 예정인 page는 6이기 때문에 victim page로 page6을 선정한다.
time12에서는 page1,2의 Df(y)값이 없는 상태이기 때문에 tie breaking rule을 적용해 page 번호가 더 작은 page1을 victim으로 선정했다.
Random algorithm
랜덤으로 victim을 선정하기 때문에 policy가 없는거나 마찬가지인 기법이지만,
overhead가 적다는 장점이 있다.
FIFO algorithm
- Scheme : 메모리에 로딩된 시점이 가장 오래된 page를 교체한다.
- Requirements : Timestamping (memory load시점 기록)
- Characteristics : 자주 사용되는 페이지를 교체하는 단점이 있다.
메모리에 로딩된지 가장 오래된 page z가 victim으로 선정된다.
- FIFO anolmaly(변칙) : 일반적으로 메모리 할당을 늘려주면 더 많은 page를 메모리에 넣어 fault가 줄어들지만, fifo기법에서는 다음과 같이 가끔 메모리 할당을 늘려주면 fault가 늘어나는 현상이 발생한다.
LRU algorithm
- Scheme : 가장 오래동안 사용되지 않은 page를 victim으로 선정한다.
- Requirements : Timestamping (page reference 시간)
- Characteristics
- MIN algorithm에 가장 근접하게 성능이 좋다.
- program locality에 기반을 두고있다. -> 최근에 참조된 페이지가 또 참조된다는 개념인 temporal locality를 반대로 말하면 가장 오래동안 참조되지 않은 페이지가 앞으로도 참조되지 않을 가능성이 높다고 말할 수 있다.
따라서 최근에 참조된 page는 앞으로도 참조될테니 메모리에 유지시켜서 page fault를 줄이는데 좋은 성능을 보이는거다.
- 단점
- Timestamping을 하는데 발생하는 overhead -> timestamping 하지 않고 LRU 구현하는 방법이 있어서 해결가능
- 특정 프로세스가 충분히 할당받지 못하면 page fault가 급격하게 증가한다. <- (page 4개를 반복하는 loop인데, 할당받은 page frame이 3개일 경우)
MIN algorithm은 미래를 보고 victim을 정한 반면에 LRU algorithm은 과거를 보고 victim을 정한다. 현재 시점 기준으로 페이지가 참조된 거리를Db(x),backward distance라고한다.
LFU algorithm
- Scheme
- 참조횟수가 가장 적은 page를 victim으로 선정한다.
- Tie-breaking rule : LRU
- Requirements : Page reference count를 저장해야한다.
- Characteristics : time-stamping을 하는 LRU보단 overhead가 적다.
- 단점
- 최근에 새롭게 참조된 page를 교체할수있다.
- reference count하는데 발생하는 overhead
참조횟수가 가장 작은 y가 victim으로 정해진다.
time12에서 tie가 생겨서 LRU 기법으로 2번 page가 나간것을 확인할 수 있다.
NUR(Not Used Recently) algorithm
LRU와 비슷한 기법이다.(locality기반)
-
LRU 기법보다는 적은 overhead (hardware적으로 구현된 bit vector를 사용하기때문에 overhead가 적음)
-
bit vectors 사용
- Reference bit vector
- Update bit vector
-
Scheme
-
reference/update bit을 확인해 victim을 선정한다.
-
Order of replacement (reference bit : r, update bit : m)
- (r,m) = (0,0)
- (r,m) = (0,1)
- (r,m) = (1,0)
- (r,m) = (1,1)
순서를 보면,
reference bit== 0 인것이 교체 우선순위가 높다. 0이라면 최근에 접근되지 않았다는 소리이므로 LRU와 비슷한 맥락으로 victim으로 선정하는 것이다.
update bit== 0 인 page의 우선순위가 높은 이유는 1이라면 victim으로 선정하고 swap-out시킬때 write-back을 해줘야하기 때문에 가급적 write-back을 미루자는 이유이다.
-
Clock algorithm
- reference bit을 사용하지만 주기적인 reset은 하지 않는다.
- Scheme
- page fault 발생 시 pointer가 시계방향으로 돌면서 victim page를 찾는다.
- Mechanism
reference bitr을 확인한다- r == 0 이면, victim page로 선정
- r == 1 이면,
reference bit을 0으로 바꾸고 계속 돌아간다.
- Characteristics
- 메모리에 로딩된지 오래된 page가 victim이 될 가능성이 높다 <- FIFO와 유사
- reference bit에 기반한 (locality에 기반한) replacement <- LRU,NUR 유사
Time4에서 page fault가 발생하고, a를 가리키던 pointer는 residence bit==1 이므로 0으로 바꾸고 b를 본다. b,c,d 모두 같은 상황이므로 pointer가 한바퀴돌면 모두 bit == 0이 되고, 한바퀴 돈 시점에서 a/0이므로 이 자리에 e가 들어오게된다.
Enhanced clock algorithm
- Scheme
- clock algorithm과 같은 방식으로 pointer를 돌려가며 victim page를 찾는다.
- Mechanism
- pointer의 (r,m)확인
- (0 , 0) : victim으로 선정, 포인터를 다음으로 돌린다.
- (0 , 1) : (0 , 0)으로 바꿔준 후
write-back후에 6번으로 감 - (1 , 0) : (0 , 0)으로 바꿔준 후 6번으로 감
- (1 , 1) : (0 , 1)으로 바꿔준 후 6번으로 감
- Advances the pointer , 1번으로 감
page write인지 read인지 구분하기 위한 w가 있기 때문에 조금 복잡하지만 천천히 보면 어렵지 않다.
Other algorithms
수학적 분석만을 위한 알고리즘이 두가지 더있다.
- MRU(Most Recently Used) algorithm <-> LRU
- MFU(Most Frequently Used) algorithm <-> LFU
Algorithm 선택 기준
- 기법이 locality를 충분히 고려헀는지
- Overhead
