[운영체제-양희재 교수님]25-26강 페이지 교체

경성대학교 양희재 교수님의 운영체제 25강

경성대학교 양희재 교수님의 운영체제 26강

페이지 교체(Page Replacement)

• Demand Paging
  • 요구되는 페이지만 backing store에서 가져온다.
  • 프로그램을 계속 실행하고 요구 페이지가 늘어나면 언젠가 메모리가 가득 차게 된다.
• 메모리가 가득 차는 경우 ⇒ Page Replacement
  1. 추가로 페이지를 가져오기 위해 victim page를 backing store로 몰아내고(page-out)
  2. 그 빈 공간으로 페이지를 가져온다(page-in).

Victim Page

• 어느 페이지를 몰아낼 것인가
  • 페이지에 수정 사항이 없다면 하드 디스크에 있는 내용 = 메모리에 올라와 있는 내용
  • 페이지에 수정 사항이 생겼다면 하드 디스크에 있는 내용 ≠ 메모리에 올라와 있는 내용
  • 따라서 하드 디스크 작성을 위한 IO 시간 절약을 위해 modify 되지 않은 페이지를 victim으로 선택
  • 페이지 테이블에 modified bit(dirty bit)를 두어 modified되지 않은 페이지를 고른다.
• 여러 victim 후보 중에서 무엇을 victim으로 선택하는가
  • Random ⇒ 성능도 random
  • First-In First-Out(FIFO) ⇒ 가장 먼저 메모리에 올라와 있던 페이지를 선택
  • 그 외 여러 page replacement algorithms 존재

페이지 교체 알고리즘

• Page reference string(페이지 참조열)
  • 같은 페이지를 연속해서 읽으면 페이지 폴트가 일어나지 않으므로 연속되는 페이지 번호는 무시하는 것
  • CPU가 내는 주소가 100 101 102 432 612 103 104 611 612 이고, Page size가 100 바이트라고 가정
    • 페이지 번호 ⇒ 1 1 1 4 6 1 1 6 6
    • Page reference string ⇒ 1 4 6 1 6

First-In First-Out(FIFO)

• Simplest, 가장 간단하다.
  • 메모리에 가장 먼저 올라온 페이지가 victim page
  • Idea: 초기화 목적의 코드는 처음 실행 이후 더 이상 사용되지 않을 것
• Belady’s Anomaly
  • 메모리 용량이 증가하면, 즉 프레임 수가 늘어나면 PF가 증가하는 지점이 있다.

  

  Page-fault curve for FIFO replacement on a reference string

Optimal(OPT)

• Replace the page that will not be used for the longest period of time
• 미래는 알 수 없으므로 unrealistic
  • 참고) SJF CPU scheduling algorithm도 마찬가지로 이상적이지만 비현실적

Least-Recently-Used(LRU)

• Replace the page that has not been used for the longest period of time
  • Idea: 최근에 사용되지 않으면 나중에도 사용되지 않을 것
• 대부분의 컴퓨터는 LRU 사용

Global vs. Local Replacement

• Global replacement
  • 메모리상의 모든 프로세스 페이지에 대해서 victim page를 선택하여 교체
• Local replacement
  • 메모리상의 자기 프로세스 페이지에 대해서 victim page를 선택하여 교체
• 성능은 Global replacement가 더 효율적일 수 있다.