[CS 상식 - 운영체제] 페이지 교체와 프레임 할당

---

01. 요구 페이징 (demand paging)

• 프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 방법
• 기본적인 양상
  1. CPU가 특정 페이지에 접근하는 명령어를 실행
  2. 해당 페이지가 현재 메모리에 있을 경우(유효 비트가 1) CPU는 페이지가 적재된 프레임에 접근
  3. 해당 페이지가 현재 메모리에 없을 경우(유효 비트 0) 페이지 폴트 발생
  4. 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효비트를 1로 설정
  5. 다시 1번을 반복
• 순수 요구 페이징(pure demand paging)
  • 실행에 필요한 페이지가 어느 정도 적재된 이후부터 페이지 폴트 발생 빈도가 떨어짐
• 페이징 시스템이 안정적으로 작동하기 위한 조건: 페이지 교체, 프레임 할당
• 페이지 교체 알고리즘: 쫓아낼 페이지를 결정하는 방법

---

02. 페이지 교체 알고리즘

• 좋은 페이지 교체 알고리즘: 일반적으로 페이지 폴트를 가장 적게 일으키는 알고리즘
• 페이지 폴트 횟수: 페이지 참조열(page reference string)을 통해 알 수 있음
  • CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
  • 연속된 페이지를 생략하는 이유: 중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않기 때문
  • 페이지 폴트가 일어나지 않을 연속된 페이지에 대한 참조는 고려하지 않음

---

03. FIFO 페이지 교체 알고리즘 (First-In First-Out Page Replacement Algorithm)

• 적재된 페이지 순서대로 교체하는 알고리즘
• 2차 기회 페이지 교체 알고리즘(second chance page replacement algorithm)
  • FIFO 알고리즘의 변형
  • 한번 더 기회를 제공
  • 만일 참조 비트가 1일 경우, 바로 교체하지 않고 참조 비트를 0으로 바꾼 후 적재 시간을 설정

---

04. 최적 페이지 교체 알고리즘 (optimal page replacement algorithm)

• CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘
• 앞으로 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘
• 가장 낮은 폴트율을 보장하는 알고리즘
• 실제로 구현하기 어려움
  • 프로세스가 앞으로 메모리 어느 부분을 어떻게 참조할지 미리 알기 어려움
  • 페이지 교체 알고리즘을 평가하기 위해 사용

---

05. LRU 페이지 교체 알고리즘 (LRU; Least Recently Used Page Replacement Algorithm)

• 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘

---

06. 스레싱과 프레임 할당

• 페이지 폴트가 자주 발생하는 이유: 나쁜 페이지 교체 알고리즘, 프로세스가 사용할 수 있는 프레임 수가 적음
• 스레싱 (htrashing): 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제
• 멀티 프로그래밍의 정도 (degree of multiprogramming): 메모리에서 동시 실행되는 프로세스의 수
  • 정도가 높음: 현재 메모리에 많은 프로세스가 동시에 실행 중
  • 정도가 낮음: 현재 메모리에 적은 프로세스가 동시에 실행 중
• 동시에 실행되는 프로세스의 수를 늘린다고 CPU 이용률이 그에 비례해서 증가하는 것이 아님
  • 필요이상으로 늘리면 각 프로세스들이 사용할 수 있는 프레임 수가 적어짐
  • 페이지 폴트가 지나치게 빈번히 발생
  • 이에 따라 CPU 이용률이 떨어져 전체적인 성능이 저해됨
• 균등 할당 (equal allocation): 모든 프로세스에 균등하게 프레임을 제공하는 방식
• 비례 할당 (proportional allocation): 프로세스의 크기에 따라 프레임을 배분하는 방식
• 프로세스를 실행하는 과정에서 배분할 프레임을 결정하는 방식: 작업 집합 모델(working set model), 페이지 폴트 빈도(PFF: Page-Fault-Frequency)
  • 작업 집합 모델: 작업 집합의 크기만큼만 프레임을 할당하는 방식
    • 작업 집합 (working set): 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합
  • 페이지 폴트 빈도: 페이지 폴트율에 상한선과 하한선을 정하고, 그 내부 범위 안에서만 프레임을 할당하는 방식

---