페이지 교체 알고리즘

이 포스트 내용은 박미진 컴퓨터일반과 시나공 정보처리기사 요약집를 참고하여 작성한 글입니다.

페이지 교체 알고리즘

페이지 부재가 발생했을 때 가상 기억장치의 필요한 페이지를 주기억장치에 적재해야 하는데, 이떼 주기억장치의 모든 페이지 프레임이 사용중이면 어떤 페이지 프레임을 선택하여 교체할지 결정하는 기법이다.

OPT ^{OPTimal Replacement,최적교체}

• 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법
• 각 페이지의 호출 순서와 참조 상황을 미리 예측해야하므로 실현 가능성이 희박

FIFO ^{First In First Out}

• 각 페이지가 주기억장치에 적재될 때마다 그 때의 시간을 기억시켜 가장 먼저 들어와서 가장 오래 있었던 페이지를 교체하는 기법
• 페이지 프레임 수가 많으면 페이지 부재의 수가 줄어들어야하지만, 페이지 프레임 수를 증가시켰는데도 불구하고 페이지 부재가 더 많이 일어나는 벨레이디의 모순현상(Belady’s Anomaly)이 발생

LRU ^{Least Recently Used}

• 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법
• 각 페이지들이 참조될 때마다 그때의 시간을 테이블에 기억시키는 막대한 오버헤드를 초래하게 된다.
• 지역성을 이용한다.

LFU ^{Least Frequently Used}

• 사용 빈도가 가장 적은 페이지를 교체하는 기법

NUR ^{Not Used Recently}

• 최근의 사용하지않은 페이지를 교체하는 기법
• 참조 비트와 변형비트 값에 따라 교체될 페이지의 순서가 결정된다

SCR ^{Second Chance Replacement}

• 기본적인 알고리즘은 FIFO 알고리즘으로 LRU와 비슷한 성능을 지니지만 과부하가 적은 알고리즘이다
  • 1 . 각 프레임의 사용여부를 나타내는 참조비트를 추가하여 페이지가 메모리 내의 프레임에 처음 적재되었을 때 1로 설정한 후 그 페이지 계속 참조될 때도 1로 설정된다.
  • 2 . 페이지를 교체할 시기에 참조비트가 0인 프레임을 찾기 위해 이동할 때 참조비트가 1인 프레임을 0으로 변환시킨다.
  • 3 . 그 페이지에 2차적 기회를 주고 다음에 검사될 때까지 교체되지 않는다.
  • 4 . 다음 순환 시 처음으로 0을 만나면 그 프레임을 교체한다.

OS

👉 디스크할당 2021.11.12

👉 디스크 스케줄링 2021.11.10

👉 워킹셋과 스래싱 2021.11.09

👉 Locality 2021.11.08

👉 페이지 교체 알고리즘 2021.11.07

👉 메모리(기억장치) 관리 기법 - 가상기억장치 2021.11.06

👉 메모리(기억장치) 관리 기법 - 주기억장치 2021.11.05

👉 메모리(기억장치) 관리 정책 2021.11.04

👉 프로세서 스케줄링 2021.11.02

👉 교착상태 2021.10.13

👉 병행 프로세스 2021.10.12

👉 스레드 2021.10.11

👉 프로세스 2021.10.10

👉 가상화(virtualization) 2021.10.10

👉 링커/로더 2021.10.07

👉 운영체제의 운용 기법 2021.10.07

👉 운영체의 개요 2021.10.06