no free frames???
[ 가정 ]
-
40 frames(물리메모리)
-
6 processes + 10 pages
프로세스당 10개의 페이지를 할당받는다. -
한 프로세스당 5개의 페이지만 필요하다
그래서 10가 남을 정도로 가동이 되는데, 만약 큰 메모리 버퍼에 의해서 over-allocationg이라면???
-
1번 프로세스는 B가 page-out
-
2번 프로세스는 G가 page-out
만약 page fault가 발생한 B가 필요로 하다면, free list가 없는데, 어떻게 할당???
Page Replacement
메모리에서 어떤 프레임을 내쫓아야 하는데 누구를???
victim을 page-out하고 demanding을 그자리에 넣는다.
Two major problems
PR algorithm이 메인임.
(I/O가 비용이 매우비싸서)
page fault줄이기 위해서,
- memory reference를 페이지 번호 단위로 나열
reference로 page fault를 최소화 방안을 계산
7012... -> 페이지 번호
(참조하고 계속 써먹음.)
근데 페이지 크기가 3이라면, over-allocated
2번은 어떻게 처리???
Solution.
- FIFO(First-In-First-Out)
- page hit면 pass
- 가장 오랜된 것 방출
Belady's Anomaly
프레임이 증가시켰는데, page fault가 증가한다???(4번 프레임 참고)
page-fault rate하는 방법은?
- OPT
앞으로 쓸 일이 없는 것 같은 것을 제거
3이 들어가야 하는데, 1이 가장 멀리 있다. -> 이 자리에 swap
- page fault 9번
그런데 미래를 어떻게 아나??? future knowledge 모름.
SJF를 참고하면, 과거를 보고 미래를 예측
near future로 예측한다.
(아주 오랜기간동안 안쓴거 방출)
- LRU(Least Recently Used)
그런데, 이 frame이 언제 마지막으로 사용되었나???
-
Counter가 가장 작다 = 엄청 안써서 Count가 낮다
-
Stack은 중간에 빠져나가는데 Stack 맞나?
그래서 SW보단 HW가 더 쉽다
그래서 reference bit를 쓰는데, 0인 것들 중에서 1개를 선택한다.
(순서는 모름)
LRU가 근본적인 컨셉
실제로 아래 알고리즘 중 LRU를 쓴다.
-
FIFO
-
OPT
-
LRU, 참고로 reference bit를 쓴다.
프로세스 단위로 프레임 몇 개를 배정???
-
local replacement 프로세스 영역 내에서만 victim을 선정한다
-
global replacement 남의 프레임을 가져다 쓴다.
어떤 process가 page in/out이 바빠서 일을 수행할 수 없다.
프로세스가 많아질수록 한정된 메모리를 부족하게 사용할 수 밖에 없어서, page fault가 증가한다.
그래서 일처리는 못해서, CPU가 놀기 시작한다.
(ex. CPU는 낮은데 메모리가 가득참.)
인접한 특정 페이지를 자주 사용한다.
그래서 슬라이딩 윈도우로 자주 쓰는 거 쓴다.
