10.4 Page Replacement (페이지 교체)

• 메모리 과할당

  • 다중 프로그래밍 정도를 올렸을 때 발생

  ex) 40개의 프레임과, 10개의 페이지 중 5개만을 사용하는 프로세스 6개.

  → 이 경우 40 - (5*6) = 10개의 프레임을 남기고 높은 CPU 활용률과 처리율을 얻을 수 있음.

  But. 만약 이 프로세스들이 10페이지를 모두 사용해야 한다면?

  → 60프레임을 필요로 하게 된다.

• 메모리 과할당의 발생 순서

  1. 프로세스가 실행하는 동안 페이지 폴트 발생
  2. 운영체제가 필요로 하는 페이지가 보조 저장장치에 저장된 위치를 알아냄
  3. 가용할 수 있는 프레임이 없음을 발견

→ 이 경우 페이지 교체가 수행되어야 한다.

10.4.1 Basic Page Replacement (기본적인 페이지 교체)

1. 보조 저장장치에서 필요한 페이지의 위치를 알아냄
2. 빈 페이지 프레임을 찾음
   1. 비어 있는 프레임이 있다면 그것을 사용함
   2. 비어 있는 프레임이 없다면 희생될(victim) 프레임을 선정하기 위하여 페이지 교체 알고리즘을 가동 시킴
   3. victim 페이지를 보조 저장장치에 기록하고, 관련 테이블을 수정
3. 빼앗은 프레임에 새 페이지를 읽어오고 테이블을 수정
4. 페이지 폴트가 발생한 지점에서부 프로세스를 계속

10.4.2 FIFO Page Replacement (FIFO 페이지 교체)

FIFO는 가장 단순한 페이지 교체 알고리즘으로, 메모리에 옮겨진 메모리들 중 가장 오래된 페이지를 Victim으로 선택한다.

그림에서 처음 7, 0, 1번 페이지에 대해 페이지 결함이 발생하고, 이들 페이지는 순서대로 프레임이 할당된다.

다음으로 2번 페이지의 요청에서 페이지 결함이 발생하고, FIFO 알고리즘에서는 가장 먼저 프레임을 할당받았던 7번 페이지를 Victim으로 선택해, 7번 페이지를 디스크에 기록하고 원래 7번이 할당받은 프레임을 2번 페이지에 새로 할당한다.

• Belady의 모순

  프로세스에 프레임을 더 주었는데 오히려 페이지 폴트가 더 증가하는 현상

  ex) 위 그래프에서 3개의 프레임 할당 시 페이지 폴트가 9번 일어나지만,

  4개의 프레임 할당 시 페이지 폴트가 10번 일어난다.

10.4.3 Optimal Page Replacement (최적 페이지 교체)

Belady's Anomaly가 발견된 후, 결과적으로 모든 알고리즘 중 가장 적은 페이지 결함을 나타내고 Belady's Anomaly가 발생하지 않는 최적의 페이지 교체 알고리즘이 연구되었다.

OPT 페이지 교체 알고리즘은 가장 오랫동안 사용되지 않을 페이지를 Victim으로 선택한다.

프로세스 스케줄링의 SJF 알고리즘과 마찬가지로, Optimal 페이지 교체 알고리즘은 참조 문자열의 미래 내용을 알고 있어야 한다는 전제가 필요해 구현하기가 어렵다는 단점이 있다.