[10-2] Virtual Memory : Page Replacement
[ Virtual Memory : Page Replacement ]
logical memory에서 어떤 한 page가 필요해서 page table을 참조했더니 invalid로 되어있었다.
그래서 page in을 하려고 할 때, 만약 free frame이 없다면? physical memory가 전부 사용 되고있을 가능성이 있는 것이다.
→ 사용 중인 page를 교체해야 한다.
[ Page Replacement ]
free frame이 없을 경우, 비워야할 frame을 찾아야 함.
physical memory내에서 page replacement algorithm에 의해 victim frame이 정해지면, page out 시키고 page table에서 invalid bit로 변경하고, 로드할 page를 page in.
page in한 page는 page table에서 valid bit로 변경한다.
[ Two major problems to implement Demand Paging ]
1) Frame-allocation algorithm
- 각 process에 frame들을 얼마나 할당할지 ?
2) Page-replacement algorithm
- 교체될 frame을 선택할 방식
Major problem인 이유
→ 폰 노이만 아키텍쳐에서 하드디스크에 대해 I/O하는 것은 매우 비싼 연산이기 때문
Damand paging 방식에 약간의 개선만 있어도 많은 performance 향상을 기대할 수 있다.
[ Evaluation of Page Replacement Algorithms ]
목표 : Page fault 빈도를 측정해서 최소화 하자 !
기본적으로, 사용가능한 frame 개수가 많을수록 page fault 횟수가 반비례하여 적어진다.
[ FIFO Page Replacement ]
The simplest algorithm.
Choose the oldest page when a page must be replaced.
위 예시에서 15번의 page fault 발생.
- Belady's Anomaly
직관적으로, 할당된 frame의 개수가 증가한다면 page-fault rate가 감소해야할 것이다.
하지만, FIFO에서는 page-fault rate가 증가하는 경우가 존재함.
[ Optimal Page Replacement ]
The lowest page-fault rate와 Belady's anomaly가 발생하지 않는 optimal algorithm을 찾아야한다.
가장 오랫동안 쓰일 예정이 없는 page를 교체하면 되지 않을까?
이론상 the lowest possible page-fault rate를 보장한다.
FIFO의 15번과 달리 9번의 page fault 발생.
→ 문제는 미래에 사용될 예정인 page를 미리 알 수가 없음.
현실적으로 구현 불가능하니 다른 방식의 알고리즘을 찾아보고, 최적에 가까운지 비교하기 위해 이 개념을 사용하자
[ Recall the Shortest-Job-First CPU schedular ]
CPU Scheduling Algorithm을 생각해보자.
현재와 비슷한 상황이 있었다.
Shortest-Job-First CPU schedular : 과거를 보고, 미래를 비슷하게 예측해보자.
→ 과거로부터 매우 오래 사용되지 않은 page는 미래에도 그럴 가능성이 높으니 교체해보자.
[ LRU Page Replacement ]
LRU : Least Recently Used
가장 오래 사용되지 않은 것은 미래에도 사용되지 않을 가능성이 높지 않을까 ?
page마다 마지막에 사용된 시각을 기록하고, 참조된지 가장 오래된 page를 victim으로 선택해서 교체한다.
Page-fault rate : 12/20
LRU : 12/20
FIFO : 15/20
OPT : 9/20
LRU의 성능은 상당히 좋으나, "마지막으로 언제 사용됐는지"를 알기 위해서는 구현하기가 상당히 힘들다.
→ 하드웨어의 지원을 받아야한다. (counter와 stack 방식이 가능함)
LRU는 OPT와 같이 Belady's anomaly가 발생하지 않는다.
[ Two implementation methods for the LRU ]
- Counter implementation
page가 참조될 때, counter 또는 system clock을 기록
counter가 가장 작은 page를 교체.
- Stack implementation
reference된 page를 stack에 저장해두고, 현재 사용되면 stack의 중간에서 빼내고 다시 top에 push
→ 가장 최근에 사용된 page는 top에, 가장 오래된 page는 아래에 위치하므로 가장 아래에 있는 page를 빼내서 교체한다.
(중간에서 빼내므로 배열이 아닌 linked list를 기반으로한 stack으로 만드는게 나을 수도 있다)
[ LRU-Approximation ]
LRU를 하드웨어를 통해 직접적으로 구현하기가 힘들어 많은 system들은 reference bit 방식을 제공한다.
각 page에 reference bit를 추가해서 참조된다면 1로 세팅하고, bit가 0인 page를 교체한다.
→ 이 방식을 선택할 경우 참조된 순서는 알 수 없게 됨.
[ Second-Chance Algorithm ]
FIFO에 reference bit를 추가해서 사용한다.
page가 선택됐을 때, reference bit가 0이라면 replace 한다.
1이라면, 0으로 바꾸고(second chance) 다시 차례가 된다면 victim page로 선정하여 교체한다.
→ 결국 구현이 힘든 LRU를 간접적으로 구현하기위해 흉내내는 것임
[ The Issues for Frame Allocation ]
프로세스 단위로 frame을 몇 개씩 할당할 것인가 ?
1) Equal vs Proportional
- equal allocation
- proprotional allocation
모든 process들에게 평등하게 나눠줄지, size가 큰 process에 많이 줄 것인지
2) Global vs Local
- local replacement
- global replacement
자신의 process에만 할당된 frame만 선택할 것이지, 시스템내의 다른 process를 포함하여 모든 frame들로 부터 교체할 frame을 선택할 것인지
해결책은 교재에 있으나, 개념이 더욱 중요
[ Thrashing ]
Process가 page in, page out을 하느라 정작 process가 해야 할 일을 못하는 현상
충분한 page를 갖고있지 않을 때, page-fault rate가 너무 높을 때
→ process가 너무 많이 실행될 때
process 개수(degree of multiprogramming)가 점점 많아지다가, thrashing이 발생하면 CPU utilization이 급격히 감소함.
ex) process가 100개, frame이 100개 있다고 가정하자.
각 process당 할당된 frame은 최소, 최대 1개이다.
모든 process가 계속해서 page fault가 일어나므로 CPU utilization이 급격히 감소하는 것.
CPU 사용량이 100%가 아닌데도 메모리가 99%이상 가득차서 컴퓨터가 버벅일 때, Thrashing을 의심해볼 수 있다.
[ Working-Set model ]
Memory reference pattern을 분석해보니, 특정 page를 집중적으로 사용하면서, 인접한 page들을 자주 계속 사용하게 됨.
→ Locality가 존재한다.
Working-Set Model
Locality 가정에 기반함.
parameter Δ 에 해당하는 sliding window인 working-set window를 정의해보자.
아이디어는 가장 최근의 Δ page references (참조된 페이지들의 window 크기만큼의 범위 묶음)를 계산해서 들고있게 하는것.
*working-set : the set of pages in the most recent Δ page references
이렇게 Working-set을 만들어두고, 시간에 따라 window 단위로 업데이트하며 메모리에 적재한다면
locality가 높은 집합이므로 page-fault rate가 적을 것이다.
page가 active use라면, working set내에 있을 것이고,
page가 더 이상 사용되지 않고 있다면, working set 바깥에 있을 것이므로
working-set 바깥에 있는 것을 victim으로 선정해 준다.
→ 시간에 따라 working-set window가 변경되어 이동할 때만 page fault가 발생할 것이며, 그 빈도는 적다.
Locality 덕분에 page-fault rate가 적어지고, Thrashing 문제 또한 완화될 수 있음.