페이지 교체 알고리즘
DRAM은 한정되어있는데, process는 여러개이므로 페이지를 교체한다.
-
Demanding paging
: fault 발생 / 요청 있을때 page frame 할당
→ physical memory가 꽉 차면 이미 mapping된 page frame 하나 내보내서 공간 마련
↔ **prefetch** : fault가 안났는데 미리 갖고옴 -
이떄 evicted page는 다시 disk로
→ 반드시 가장 최신 이미지여야함
→ dirty bit = 1이면 다시 써주기 (store operation등 정보 update)
→ dirty bit = 0이면 just overwrite the page with new data\
-
목적 : fault의 최소화
→ thrashing 피하기
Belady's Algorithm
→ optimal algorithm
: replcae the page that will not be used for the longest time in the future
-
evicting the best page
→ 알고리즘의 목적이 page fault 수 줄이기이므로 다시 접근하지 않을/ 가장 오랫동안 참조가 안될 page를 내보냄
e.g. page frame이 3개일때
B C B A E B D E C B E B
→ E : 앞으로 fault가 잘 발생하지 않을 것 같은 A를 교체
→ D : 가장 나중에 fault가 발생하는 B를 replace
→ B : 앞으로 fault가 발생하지 않는 D나 C중 교체
-
현실적이지 않음
∵ 미래의 instruction 알 수 x
-
how well ny iplement algorithm is doing compared to the optimal
∵ 이 알고리즘보다 더 좋을 수는 x
e.g. optimal과 random의 fault rate 비교
NRU
: Not Recently Used page replacement algorithm
-
각 page는
-
R bit : set when page is referenced (read/write)
→ 최근에 access됐는지?
: R=1이면 마지막 clock interrupt ~ page fault사이에 접근됨
→ locality로 또 access 하겠구나 판단
-
M bit : set when page is modified (witten)
→ 대부분 TLB가 처리하는데,
M = 1이면, disk에 써줘야함 ∵ DRAM의 내용과 disk의 내용이 다름
-
매 memory reference마다 R,M bit는 HW에 의해 업데이트되고, OS에 의해 리셋됨
→ 매 clock interrupt마다 R bit =0 으로 clear
∵ 어떤 page가 최근에 reference됐는지 알기 위해
-
-
Pages are classified
-
class 0 : R=0, M=0
-
class 1 : R=0, M=1
-
class 2 : R=1, M=0
-
class 3 : R=1, M=1
→의 순으로 먼저 바꿔줌
∵ M=1이면 disk에 다시 써줘야 하므로 같은 조건에서 modified되지 않은 page replace
→ fault시 쭉 훑어서 class0~ 부터 찾음, 같은 class내에서는 아무거나
-
FIFO
- DRAM에 가장 오래전에 들어왔던 frame replace
→ 문제점 : program의 locality 전혀 반영 x
e.g. 3 page frame에서
reference stream : A B C A B D A D B C B
- optimal : A B C A B D A D B C B → fault 5번
- FIFO : A B C A B D A D B C B → fault 7번
: FIFO한정으로 memory 더 꽂아도 fault가 줄어든다는 보장이 없음
- page fault가 많이 발생하면, 일반적인 해결방법은 memory 더 꽂기
→ 이때, replace algorithm에 따라 메모리 더 꽂아도 fault 줄어들지 않는 경우
e.g.
i) 4 page frames using FIFO
1 2 3 4 1 2 5 1 2 3 4 5 → fault 10번
ii) 3 page frames using FIFO
1 2 3 4 1 2 5 1 2 3 4 5 → fault 9번
Second Chance Page Replacement Algorithm
→ FIFO의 변형
- FIFO
→ fault시 제일 먼저 로딩된 A가 replace- SC
→ R bit = 1일때 chance를 한번 더 : 그냥 뒤로 보내고 다음거를 replace-
locality 일부 반영
-
If A has R = 0, evict it from memory
→ M bit에 따라 그냥 overwrite되거나 disk에 쓰여짐 -
If A has R = 1, A is put into the end of the list & R bit = 0
-
모든 frame이 R=1이면, pure FIFO와 같이 동작
-
linked list로 매번 연결 → 비효율적
The Clock Page Replacement Algorithm
→ #4와 알고리즘은 같은데 구조만 circualr
- 떼서 맨 뒤로 옮기는 것이 아닌 포인터만 oldest → oldest.right & R bit reset
- R = 0: evict the page
- R = 1: clear R & 포인터옮기기
LRU
: Least Recently Used
-
과거의 Access pattern 살펴봄
→ evict the page that hasn't been used for the longest amount of time
→ page access할 때마다 기록 : time stamp이용 -
program의 locality 이용
-
기록시의 오버헤드가 높음
e.g. ld R0, st R0, pc ←
수행시의 target cycle : 1-2 cycle
→ 수행마다 Memory update, PT에 기록해야함
→ 구현가능성 x
→ 실제 사용에서는 update overhead가 너무 커져서 사용 x
LRU의 Possible Implementations
- keep a linked list of all pages in memory
→ circular가 훨씬 overhead 적음
→ 매 memory reference 마다 리스트를 update
→ access된 page를 앞으로 옮김- use counter in each page table entry
: 각 insruction마다 자동으로 counter ++
→ lowest counter value의 page를 replace
→ 원래 정의는 시간
: access시마다의 시간 기록해도 fault시 제일 오래전에 access한거 replace
Simulating LRU in SW
➀ NFU
not frequently used
- 매 clock interrupt마다 각 page의 R bit check → counter에 더하기
<span style:"color:red">→ 문제점
→ 이전 counter의 값이 누적되어 locality가 제대로 반영되지 않음!
- fault시 R bit check → counter 갱신 → 갱신한 counter값 비교해 replace → replace된 page는 counter = 0
➁ Aging
: shift register 이용
-
매 clock interrupt 마다
-
Shift register 1 bit
-
Add R bit to the left most bit
(최근에 access에 가장 큰 rate를 줌)
-
-
fault시 : shift → +rbit 해서 replace할 페이지 정하기 & R bit 리셋
→ 문제점
-
cannot distinguish two references in the same clock interval
→ 한 clock내에 여러번 access해도 1번으로 -
limited by a finite number of bits of counter
→ pure LRU의 경우에서는 A가 replace돼야 함
→ **granuality**가 커서 정확한 반영이 안됨!!