Updated:

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

페이지 교체 알고리즘

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

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을 만나면 그 프레임을 교체한다.

댓글 쓰기