[운영체제] 페이지 교체 알고리즘1 (FIFO with Belady's Anomaly)

지난번, 가상 메모리와 페이지 폴트에 대해 정리해봤다. [메모리 관리해야지, 어떻게? 블로그 글]

방금 운영체제 과목 중간 시험을 봐서 머리가 따끈따끈하다 ㅎㅎ 

 

어떤 페이지를 희생해야할까

페이지 폴트시 이용하는 알고리즘 종류에 대해 정리해보자.

페이지 교체 알고리즘 (page-replacement algorithm)

FIFO

가장 먼저 온 것을 교체한다.

page frames가 3개이고, string이 위와 같이 주어질때,

page fault가 일어나는 경우, page frames를 일종의 queue로 생각해, head에 있는 값을 Poll()한다.

그러나 아래와 같은 문제점이 있다. [Belady's Anomaly(벨라디의 이상현상)]

 

이론상, 물리 메모리의 페이지 프레임을 늘려 페이지 수를 늘려준다면, 사용하려는 페이지가 물리 메모리에 없는 page fault 현상이 발생 빈도가 줄어든다.

또한 page fault 발생 빈도가 줄어들어 실행속도가 빨라진다.

🧨 그런데 page fault가 적어져야하는데, 일부구간에서 늘어나는 현상이 발생한다!

이를 Belady's Anomaly라고 한다.

이와 관련해서 찾아보다가 Belady의 논문을 찾았다. 와,, 무려 1969년에 쓰인 논문이다...

이해가 될지 모르겠지만 이왕 시험 끝났으니 끈질기게 읽어보자. 적어도 시험공부보다는 재밌을 거 같다

 

Belady's Anomaly 의 예시

위에서 숫자 string 내 숫자 각각은 간단화한 가상 메모리의 페이지 인덱스이다.

즉, 프로세스가 시간순으로 접근한 가상 페이지 번호들을 나타낸 것.

물리 주소와 page fault는 3개의 물리 주소 페이지 프레임 내에서 해당 페이지 번호가 없으면 발생한다.

서술된 예시는 page frame이 3개인 경우이다. 

이때, page fault는 총 9번 발생한다.

그러나, page frame이 4개인 경우는, page fault가 다음과 같이 총 10번 발생한다. 이것이 이상현상의 예시이다.

• 1 2 3 4 1 2 5 1 2 3 4 5

1 x x x

1 2 x x

1 2 3 x

1 2 3 4

1 2 3 4 (no page fault)

1 2 3 4 (no page fault)

2 3 4 5

3 4 5 1

4 5 1 2

5 1 2 3

1 2 3 4

2 3 4 5

이상현상이 왜 발생할까?

 

 

참고자료

https://medium.com/@ioseunggi/beladys-anomaly-4d2bafe4f735

Belady’s Anomaly

https://cano721.tistory.com/18

[운영체제] 페이지 교체 알고리즘(FIFO, OPT, LRU), 쓰레싱, working set