CS/운영체제

페이지 교체 알고리즘

haong_ 2025. 4. 29. 18:43

기본개념

  • 페이징 기법에서는 모든 페이지 프레임이 사용 중일 때 새로운 페이지를 적재하기 위해 교체 대상을 선택해야 함
  • 목표:
    • 앞으로 가장 오래 사용하지 않을 페이지를 교체하는 것 (이론적 최적)
    • 현실적으로 미래를 예측할 수 없기 때문에 좋은 근사 방법을 선택해야 함

교체 제외 페이지

  • 페이징을 위한 커널 코드 영역
  • 보조기억장치 드라이버 영역
  • 시간을 맞춰 동작해야 하는 코드 영역 
  • 입출력장치를 위한 데이터 버퍼 영역 등 

FIFO(First-In First-Out)

  • 메모리에서 가장 오래 있었던 페이지 교체 
  • 큐 이용 
[Page1] → [Page2] → [Page3] → [Page4]
(Front)                        (Rear)
  • 새 페이지가 필요하면 Front(제일 오래된) 페이지 교체

단점

  • 자주 사용하는 페이지도 오래됐으면 교체될 수 있음
  • Belady의 이상현상: 프레임 수를 늘려도 페이지 폴트가 줄지 않고 늘어날 수 있음

LRU(Leat Recently Used)

  • 메모리에서 가장 오랫동안 사용되지 않은 페이지 교체 
  • Locality(지역성) 휴리스틱에 기반함
  • 참조시각 또는 리스트 이용

참조시각을 이용한 구현

  • 각 페이지 참조 시 마다 현재 시간 저장
  • 교체 시 가장 오래된 시각을 가진 페이지 교체
Page Table:
Page1: t=5
Page2: t=8
Page3: t=10

가장 오래된 Page1 교체

 

리스트를 이용한 구현

  • 참조될 때마다 리스트 맨 앞에 이동
  • 교체할 때 리스트 끝에 있는 페이지 교체
[Page3] → [Page2] → [Page1]
(최근 사용)               (오래된 사용)

Page1 제거

장점

  • Belady 이상현상 발생하지 않음
  • 최적화에 근접하는 선택 가능

단점

  • 지역성이 맞지 않는 상황도 존재 
  • 막대한 오버헤드:
    • 매 참조 시 마다 리스트 수정/시각 기록 필요
    • 하드웨어 지원 없이 구현하면 매우 비효율적

LFU(Leat Frequently Used)

  • 메모리에서 참조 횟수가 가장 적은 페이지 교체 
  • 참조횟수 이용 
Page Table:
Page1: 5 hits
Page2: 2 hits
Page3: 7 hits

(→ 2 hits인 Page2 교체)

단점

  • 최근에 들어온 페이지가 참조 횟수가 적어 바로 교체될 수 있음
  • 예전에 많이 참조됐지만 지금은 거의 안 쓰는 페이지가 오래 살아남음
  • 막대한 오버헤드: 참조 횟수 관리 부담

2차 기회 페이지 교체

  • 참조 비트가 0이면서 메모리에 가장 오래 있었던 페이지 교체 
  • FIFO 큐와 참조 비트 이용 
  • 참조 비트로 최근 참조 여부 체크  
    • 각 페이지가 메모리에 적재될 때는 참조 비트 0 
    • 적재된 상태에서 추가로 참조되면 참조 비트 1 

1. 참조할 페이지가 메모리에 없는 경우 

  • 빈 페이지 프레임이 있으면 
    • 페이지 적재
    • 큐에 추가
    • 참조 비트 0
  • 빈 페이지 프레임이 없으면
    • 큐의 Front page 꺼내 참조 비트 확인
    • 참조 비트 1이면
      • 참조 비트를 0으로 리셋
      • 페이지를 큐 뒤로 이동
      • 다시 다음 Front 페이지를 검사
    • 참조 비트 0이면
      • 해당 페이지를 교체
      • 새 페이지를 적재하고 큐 뒤에 추가
      • 참조 비트 0 설정

2. 참조할 페이지가 메모리에 있는 경우 

  • 큐 위치 변화 없이 참조 비트만 1로 설정 
[Page 요청 발생]
    ↓
[메모리에 있는가?]
    ↓
[YES]                [NO]
참조 비트 = 1         ↓
(큐 변화 없음)       빈 프레임 있는가?
                          ↓
                 [YES]         [NO]
           새 페이지 적재     큐 Front 검사
           참조 비트 = 0       참조비트 1 → 0으로 변경 후 뒤로
                               참조비트 0 → 교체 후 적재

클럭 페이지 교체

  • 원형 큐 + 포인터 이용 (시계바늘처럼 동작)
  • 포인터는 마지막에 추가된 페이지의 다음 위치를 가리킴 
  • 새 페이지 필요 시:
    • 포인터가 가리키는 페이지의 참조 비트 확인
      • 참조 비트 0이면 → 교체
      • 참조 비트 1이면 → 0으로 리셋하고 포인터 이동
  • 빈 페이지가 있으면 그냥 삽입
(시계 방향 원형 구조)

   [Page1(ref=0)]
        ↓
   [Page2(ref=1)]
        ↓
   [Page3(ref=0)]
        ↓
   [Page4(ref=1)]
        ↓
(포인터 회전)

포인터:
- ref=1 → ref=0 만들고 이동
- ref=0 → 교체

프로세스별 페이지 집합 관리 

  • 운영체제에서 각 프로세스는 실행되기 위해 일정량의 메모리 페이지를 필요로 함 
  • 프로세스마다 일정 개수의 페이지 프레임을 메모리에 유지되는 페이지 집합 
  • 페이지 집합 크기 작을수록 시스템 처리량 증가, 페이지 폴트 증가
  • 페이지 집합 크기 클수록 페이지 폴트 감소, 실행 가능한 프로세스 수 감소

적절한 페이지 집합 크기 관리는 운영체제 성능 최적화에 핵심 

워킹세트(Working set) 알고리즘

  • Denning이 제안한 페이지 폴트 비율 감소 모델
  • 워킹 세트 W(t, Δ)
     = 시각 t에서 직전 Δ시간 동안 참조된 모든 페이지 집합
  • 짧은 시간(Δ시간) 동안 프로세스가 참조한 페이지 집합을 메모리에 항상 올려두자는 아이디어
    • 시간 지역성 때문, 방금 쓴 것을 또 쓸 가능성 높음 

원칙

  • 워킹 세트를 메모리에 유지하는 원칙
  • 워킹 세트 미유지 시 계속 디스크로부터 페이지를 가져오는 상황(=쓰래싱) 발생

문제점

  • Δ시간 동안의 참조 이력을 전부 추적해야 함
  • 엄청난 시간/공간 오버헤드 발생
  • 구현이 너무 복잡해서 현실에서 그대로 적용하기 어렵다

PFF 알고리즘 (Paga Fault Frequency)

  • 페이지 폴트 빈도를 이용해 프로세스별 페이지 집합 크기를 변화시키는 기법
  • 워킹 세트를 직접 계산하지 않고 PFF를 이용해 워킹 세트 크기를 추정해서 관리 

PFF

  • 얼마나 자주 페이지 교체가 발생하는지 나타내는 척도 
  • 페이지 폴트 발생 직후 부터 다음 페이지 폴트 발생할때까지 시간을 T 로 뒀을때 이의 역수(1/T)
    • T가 작으면 (폴트 금방 발생) → PFF 값이 커짐, 메모리 부족하다는 뜻 
    • T가 크면(폴트 없이 오래 실행) → PFF 값이 작아짐, 여유롭게 실행되고 있다는 뜻 
  • 상한과 하한 기준 설정
    • PFF > 상한 (잦은 페이지 폴트) →  페이지 프레임 1개 추가
    • PFF < 하한 (페이지 폴트가 너무 적음) → 참조되지 않은 페이지 제거
  • PFF 알고리즘을 통해 동적으로 페이지 집합 크기를 조정하여, 시스템 메모리 사용을 최적화하고 쓰래싱을 방지함
저작자표시