Page Replacement

이 글은 KOCW 강좌 중 경성대학교 양희재 교수님의 '운영체제' 강의를 정리한 글입니다.

 

Page Replacement

Page Replacement

Demand Paging에서 필요한 Process의 Page를 Backing Store에서 가져온다.

Memory에 Page가 Load 되다 보면 Memory가 가득 차게 된다.

Memory가 가득 찼을 때, Backing Store에 Page를 몰아내고(Page-out)

Page를 몰아내서 얻은 빈 공간에 필요한 Page를 가져온다.(Page-in)

이 때, 공간을 만들기 위해 Backing Store로 간 Page를 Victim Page라 한다.

Victim Page

I/O 시간을 절약하기 위해서 기왕이면 변경 사항이 없는 Page를 Vitim Page로 한다.

변경사항이 있게 되면 Write 작업도 진행하기 때문이다.

판단하기 위해서 Page Table에 modified bit를 추가해서 bit값으로 변경 사항을 체크한다.

Page Replacement Algorithm

First-in First-Out

FIFO는 간단한 알고리즘이다.

가장 먼저 Memory에 Load 한 Page를 Victim Page로 하는 것이다.

초기화 코드가 더 이상 사용되지 않을 것이라는 아이디어에서 시작되었다.

FIFO는 간단하지만 비효율적이다.

Frame 수 증가하면(Memory 증가하면) Page Fault가 줄어드는 것이 정상이지만

증가하다 특정 Frame 수에 가면 Page Fault 수가 증가하는 현상이 발생하는데 이를 Belady' Anomaly라 한다.

Optimal

OPT는 가장 효율적인 알고리즘이다.

가장 오랫동안 사용되지 않을 거 같은 Page를 Victim Page로 선택한다.

대신 OPT는 현실적으로 불가능하다.

미래에 어떤 Process가 사용될 지 알 수 없다.

Least-Recently-Used

LRU는 최근에 사용되지 않는 Page를 Victim Page로 선택한다.

최근에 사용되지 않으면 나중에도 사용되지 않을 것이라는 아이디어에서 나왔다.

Global vs Local Replacement

• Global Replacement -> Memory상 모든 Process Page에 대해 교체
• Local Replacement -> Memory상 자기 Process Page에 대해 교체

일반적으로 Global Replacement가 Memory 사용 효율이 높다.