[OS] Page Replacement

 

 

 

 

페이지 교체 (Page Replacement)

 

demand paging : 요구되는 페이지만 backing store에서 가져온다.

하지만 프로그램 실행이 계속되면 요구하는 페이지가 늘어나게 되고 context switching한 다음 프로세서는 메인 메모리가 가득차게 된다.

 

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

 

이 때 쫓겨난 페이지를 victim page라 하고 전체적인 과정을 page replacement라 한다.

 

한 페이지를 하드디스크로 보내면 cpu에 의해 page 내용이 바뀌지 않았다면 하드디스크에 굳이 write할 필요가 없다.

하지만 page내용이 바뀌었다면 하드디스크에 변경된 내용을 write해주어야 한다. 이 때 write하는데 시간이 소요된다.

page내용의 변경유무를 페이지 테이블에 modified bit 를 추가해 변경되면 1로, 변경되지 않으면 0으로 표시해준다.

 

 

 

 

 

Victim Page

i / o 시간을 절약하기 위해 modify bit 값이 0인 페이지를 victim 으로 선택한다.

 

victim page를 고르는 법

1. Random → 성능도 랜덤하다

2. First in First out

3. page replacement algorithms

 

 

 

page replacement algorithms

 

page reference string

cpu가 100번지 주소를 내었는데 메인 메모리에 100번지가 없다면 page fault가 발생한다.

하드디스크를 뒤져 한 페이지 전체를 메인메모리로 로드한다. (100 ~ 199 까지)

이후 101번지, 102번지,,, 에서는 page fault가 발생하지 않는다.

cpu가 내는 주소를 reference string으로 바꿀 수 있어야 한다.

 

cpu가 내는 주소

100

101

102

432

612

103

104

611

612

1(O)

1(x)

1(x)

4(o)

6(o)

1

1(x)

6

6(x)

• FIFO (First in First out)

메인메모리에 먼저 올라온 것을 victim 페이지로 해서 내보냄.

장점 : 간단하다. 구현이 쉽다.

단점 : 이상 현상 발생

ex ) 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

7 메인메모리에 없음 → page fault 발생 → 하드디스크에서 가져옴

0 메인메모리에 없음 → page fault 발생 → 하드디스크에서 가져옴

1 메인메모리에 없음 → page fault 발생 → 하드디스크에서 가져옴

2 메인메모리에 없음 → page fault 발생 → 하드디스크에서 가져옴 → 메인메모리 꽉차서 가장 오래된 7 내보냄 → 빈 공간 2로 채움(victim = 7)

0 메인메모리에 있음 → page fault 발생 x

3 메인메모리에 없음 → page fault 발생 → 하드디스크에서 가져옴 → 메인메모리 꽉차서 가장 오래된 0 내보냄 → 빈 공간 3로 채움(victim = 0)

0 메인메모리에 있음 → page fault 발생 x

4 메인메모리에 없음 → page fault 발생 → 하드디스크에서 가져옴 → 메인메모리 꽉차서 가장 오래된 1 내보냄 → 빈 공간 4로 채움(victim = 1)...........

 

2를 내쫓아내자 마자 2가 필요한 경우가 발생한다.

 

fifo방식을 사용하면 메모리 용량이 증가함에도 불구하고 page fault가 증가하는 anomaly현상이 발생한다.

anomaly : 상식에 어긋나는 일. 항상 일어나는 것은 아니고 page reference string이 특정한 경우 fifio를 사용하면 발생

 

page fault는 메인메모리 용량이 작을수록 자주 일어난다. 메인메모리 용량이 작을 수록 빨리 차고 page fault가 더 자주 일어나기 때문

프레임 수가 증가하면서(=메모리 용량 증가) page fault 가 감소해야 하는데, 오히려 page fault가 증가하는 현상

page reference string이 특정할 때 발생한다.

 

 

 

 

 

• OPT (Optimal)

앞으로 오랜기간 동안 사용되지 않을 번호를 골라 쫓아내는 방법

단점 : 미래에 어떤 프로세서가 사용될지 현실적으로 알 수 없어 적용하기 어렵다.

 

ex ) 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

7 메인메모리에 없음 → page fault 발생 → 하드디스크에서 가져옴

0 메인메모리에 없음 → page fault 발생 → 하드디스크에서 가져옴

1 메인메모리에 없음 → page fault 발생 → 하드디스크에서 가져옴

2 메인메모리에 없음 → page fault 발생 → 하드디스크에서 가져옴 → 메인메모리 꽉차서 가장 오래랜기간 발생하지 않을  7 내보냄 → 빈 공간 2로 채움(victim = 7)

0 메인메모리에 있음 → page fault 발생 x

3 메인메모리에 없음 → page fault 발생 → 하드디스크에서 가져옴 → 메인메모리 꽉차서 가장 오랜기간 발생하지 않을 1 내보냄 → 빈 공간 3로 채움(victim = 1)

0 메인메모리에 있음 → page fault 발생 x

4 메인메모리에 없음 → page fault 발생 → 하드디스크에서 가져옴 → 메인메모리 꽉차서 가장 오랜기간 발생하지 않을 0내보냄 → 빈 공간 4로 채움(victim = 0)...........

 

 

• LRU (Least Recently Used)

과거를 보고 미래를 짐작하는 알고리즘 → 대부분의 컴퓨터가 적용하는 방식

optimal 보다는 자주 일어나고 fifo보다는 덜 일어남

최근에 가장 적게 사용된 것 내보냄.

ex ) 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

 

7 메인메모리에 없음 → page fault 발생 → 하드디스크에서 가져옴

0 메인메모리에 없음 → page fault 발생 → 하드디스크에서 가져옴

1 메인메모리에 없음 → page fault 발생 → 하드디스크에서 가져옴

2 메인메모리에 없음 → page fault 발생 → 하드디스크에서 가져옴 → 메인메모리 꽉차서 가장 오래랜기간 발생하지 않을  7 내보냄 → 빈 공간 2로 채움(victim = 7)

0 메인메모리에 있음 → page fault 발생 x

3 메인메모리에 없음 → page fault 발생 → 하드디스크에서 가져옴 → 메인메모리 꽉차서 가장 오랜기간 발생하지 않을 1 내보냄 → 빈 공간 3로 채움(victim = 1)

0 메인메모리에 있음 → page fault 발생 x

4 메인메모리에 없음 → page fault 발생 → 하드디스크에서 가져옴 → 메인메모리 꽉차서 가장 오랜기간 발생하지 않을 2내보냄 → 빈 공간 4로 채움(victim = 2)...........

 

 

 

 

Global & Local Replacement

 

메인메모리에 올라와있는 프로세서 수는 3개이다.

p1 → p2 → p3 순으로 context switching이 일어날 때 p1,p2,p3를 모두 채우면 메인메모리가 꽉 찬다.

 

• Global replacement

메인메모리 전체에서 victim을 선택해 내보냄(FIFO, LRU, Optimal)

• Local replacement

프로세서 하나에서만 victim을 선택해 내보냄(FIFO, LRU, Optimal)

 

 

 

메모리 사용효율 면에서는 global replacement가 더 좋다.