cs/운영체제

Page Fault algorithms

Woouuk 2025. 11. 16. 00:58

Page Fault algorithms

메모리는 용량이 한정되어 있다. 페이지 프레임도 마찬가지다. 일반적으로 페이지 수가 페이지 프레임 수보다 많고 특정 페이지를 읽으려고 했을 때 페이지 프레임이 꽉 차있을 수 있다.

이 때 페이지 프레임을 비우게 되는 Page Fault가 발생한다.

여기서 자주 쓰이는 페이지를 삭제하는 것은 금방 다시 요청할 것이기에 좋지 않고, write가 있던(dirty bit가 1인) 페이지라면 디스크에 꼭 옮겨놓은 뒤 삭제해야 한다.

 

Optimalpage Replacement algorithms

이상적이지만 적용불가하여 성능평가의 지표로만 사용된다.

간단하게 가장 나중에 참조될 페이지를 삭제하는 것이다.

 

프로세스를 먼저 실행시킨 뒤 로그를 참조하여 가장 먼 미래에 참조될 페이지를 내보내는 것인데, 사용자마다 stress나 환경이 다르고 프로세스를 먼저 실행시키는 것도 굉장히 비효율적이기에 벤치마킹에만 사용된다.

 

Not Recently Used Page Replacement algorithms(NRU)

페이지 테이블 엔트리에 R bit와 M bit가 있었다.

간단하게 R bit는 read/write이 발생한 경우, M bit는 write이 발생한 경우에 1이 되는데 이에 따라 R, M이 네 가지 중 하나의 상태로 존재하게 된다. 이 때, R bit는 주기적으로 0으로 초기화한다. ( R bit끼리에서도 순서를 정하기 위함 )

R M

0 0 - 초기화 이후 참조된 적도, 수정된 적도 없음

0 1 - 초기화 이후 참조된 적은 없으나 수정됨

1 0 - 초기화 이후 참조되었으나 수정은 안됨

1 1 - 초기화 이후 참조되었고 수정도 되었음

 

위의 순서대로 내보낼 페이지를 정한다. 00을 먼저 내보내고 그다음 01, 10, 11 순서이다.

이 때 01이 먼저 내보짐에 주의해야 한다. 수정된 것보다 초기화 이후 최근에 참조되었다는 것을 더 높은 priority로 본다.

 

FIFO 알고리즘

말그대로 선입선출 페이지이다. 연결 리스트로 큐를 구현하여 처리한다.

자주 사용되는 페이지와 관계없이 가장 오래된 페이지를 내쫓는다는 단점이 있다.

 

Second Chance 알고리즘

 

R bit 여부에 따라 기회를 한번 더 주는 알고리즘이다.

R bit가 0이면 FIFO처럼 바로 내보내고, 1이라면 0으로 초기화하고 most recently loaded page로 취급한다.

이렇게 R bit가 0인 가장 오래된 페이지를 찾을 때까지 순회하여 내보낸다.

이 방법 또한 당연히 느릴 것이다.

 

The Clock 알고리즘

위의 second chance 알고리즘과 작동 방식은 비슷하나, R bit가 1이면 0으로 초기화한 뒤 시계바늘(헤드)을 시계방향으로 돌려서 다시 R bit 확인하고.. 돌리고.. 하는 알고리즘이다. (원형 큐와 비슷하다)

 

Least Recently Used

얘는 페이지 프레임에 들어온 순서가 아닌 사용한지 가장 오래된 페이지 프레임을 버리는 알고리즘이다.

위와 같이 카운터(counter)를 사용해 구현한다. 위의 2차원 매트릭스로 하드웨어 상에 구현되어 있다.

n번 페이지 사용 시 n번 row(행)를 1로 세팅한 뒤 n번 col(열)을 0으로 바꾼다.

페이지 폴트 발생 시 행의 합을 보았을 때 합이 가장 작은 행의 페이지를 내보내는 것이다. - 가장 적게 사용했다는 뜻이다.

e에서는 0번 페이지가, j에서는 1번 페이지가 제거될 것이다.

 

Not Frequently Used