[운영체제] 페이지 교체 Page Replacement

1. 페이지 교체

1) 페이지 교체란?

Demand paging 방식을 사용하더라도 프로그램 실행에 따라 요구 페이지가 늘어나고, 언젠가는 메모리가 가득 차게된다.

메모리가 가득 차면 추가 페이지를 가져오기 위해 어떤 페이지는 backing store로 몰아내고(page-out), 그 빈 공간으로 페이지를 가져온다. (page-in)

 

이 때 backing store로 쫓겨난 페이지를 victim page 라고 한다.

 

 

2) Victim Page

(1) Page-out시 페이지를 backing store에 write 해야할까?

page-out 할 때 victim page가 명령어라면 backing store에 이미 있었기 때문에 새로 write할 필요가 없다.

하지만 실행하면서 바뀐 내용이 있다면 write해야한다.

 

(2) 어느 페이지를 몰아낼 것인가?

추가 write를 하지 않는 page를 몰아내는 것이 I/O시간을 절약할 수 있다. 즉, modify되지 않은 페이지를 선택하는 것이 효율적이다.

이를 위해 modified bit(=dirty bit)를 사용한다.

 

 

2. 페이지 교체 알고리즘 Page Replacement Algorithm

0) 페이지 참조열 Page Reference String 

CPU가 내는 주소가 100 101 102 432 612 103 104 611 612 라고 가정해보자.

Page size는 100 bytes 라면, 페이지 번호는 1 1 1 4 6 1 1 1 6 6 이 된다.

여기서 Page reference string은 1 4 6 1 6 이다.

연속된 중복값은 없어지는데 그 이유는 page 차원에서 연속된 주소는 의미가 없기 때문이다. 같은 페이지를 읽게되면 page fault가 일어나지 않기 때문에 건너뛴다. 

 

 

 

아래는 여러 페이지 중 어떤 페이지를 victim으로 선택할 것인가를 결정하는 페이지 교체 알고리즘이다.

 

1) First In First Out (FIFO)

각 페이지가 메모리에 적재될 때마닫 그 때의 시간을 기억시켜 가장 오래 있었던 페이지를 교체하는 기법이다.

초기화 코드는 더이상 사용되지 않을 것이라는게 FIFO 기반에 깔린 생각이다.

가장 이해하기 쉽고, 프로그래밍이 간단하다.

 

예시)

페이지 참조열 : 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

프레임 수 : 3

7	2	4	0	7
0	3	2	1	0
1	0	3	2	1

page fault 15번 일어난다. (맨 처음 포함)

 

페이지 프레임 수가 많으면 페이지 부재의 수가 줄어드는 것이 일반적이지만, 페이지 부재가 더 많이 일어나는 벨레이디의 모순(Belady's Anomaly) 현상이 발생한다. 스택 속성을 따르지 않기 때문인데, 

https://www.prepbytes.com/blog/operating-system/beladys-anomaly/

 

 

FIFO의 단점을 보완한 Second Chance Replacement (SCR) 기법이 있다. 가장 오랫동안 메모리에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 방법이다.

 

 

2) Optimal (OPT)

  앞으로 가장 오랫동안 사용하지 않을 페이지를 victim page로 선택하는 기법이다.

 

예시) 

페이지 참조열 : 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

프레임 수 : 3

7	2	7
0	4	0
1	3	1

 

Page Fault 9번 발생한다.

 

그러나 OPT 알고리즘은 비현실적이다. 왜냐하면 미래에 어떤 페이지를 사용할지/안할지 예측하는 것은 불가능하기 때문이다.

(CPU 스케줄링에서 Shortest Job First(SJF) 같이 현실적으로 사용하기 어려운 알고리즘)

 

3) Least-Recently-Used (LRU)

OPT가 효율적이지만, 앞으로 사용될지 안될지를 예측하는 것이 불가능하다. 앞으로 사용 안될 페이지를 예측하는 방법으로 최근에 사용했는가로 판단하는 방법이다.

최근에 가장 오랫동안 사용하지 않은 페이지를 교체한다.

각 페이지마다 계수기나 스택을 두어 현 시점에서 가장 오랫동안 상요하지 않은(=가장 오래 전에 사용된) 페이지를 교체한다.

 

예시)

페이지 참조열 : 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

프레임 수 : 3

7	2	4	0	1
0	3	0
1	3	2	7

 

 

Page fault가 12번 발생한다.

 

 

4) Least Frequently Used (LFU)

사용 빈도가 가장 적은 페이지를 교체하는 기법이다.

프로그램 실행 초기에 많이 사용된 페이지가 그 후로 사용되지 않아도 프레임을 계속 차지할 수 있다는 단점이 있다.

 

 

5) Not Used Recently (NUR)

최근에 사용하지 않은 페이지를 교체하는 기법이다.

최근 사용 여부를 확인하기 이해서 각 페이지마다 참조 비트 Reference bit와 변형 비트 Modified bit(=dirty bit) 2개의 비트를 ㅅ가용한다.

참조 비트와 변형 비트의 값에 따라 교체될 페이지의 순서가 결정된다.

교체 순서	참조 비트 Reference bit	변형 비트 Modified bit
1	0	0
2	0	1
3	1	0
4	1	1

 

 

6) Global vs Local Replacement

•  Global replacement : 메모리 상의 모든 프로세스 페이지에 대해 교체
•  Local replacement : 메모리 상의 자기 프로세스 페이지에 대해 교체

 

성능 비교

  - 대체적으로 Global replacement가 더 효율적일 수 있다.