Home [운영 체제] 10강 - 페이지 교체 알고리즘
Post
Cancel

[운영 체제] 10강 - 페이지 교체 알고리즘

Posted May 2, 2025
By mxxikr
read 14 min

💡해당 게시글은 방송통신대학교 김진욱 교수님의 '운영 체제' 강의를 개인 공부 목적으로 메모하였습니다.



학습 개요

  • 새로운 페이지를 메모리에 적재하려는데 빈 페이지 프레임이 없을 경우 페이지 프레임 중 한 칸을 선택하여 거기에 든 페이지 대신 새로운 페이지를 넣어야 함
  • 어떤 페이지를 교체 대상으로 선택 하느냐에 따라 컴퓨터 시스템의 성능에 영향을 주게 됨
  • 다중 프로그래밍 환경에서는 각 프로세스가 사용할 수 있는 페이지 프레임의 개수를 제한할 필요가 있는데, 이 개수 또한 컴퓨터 시스템의 성능에 영향을 줌
  • 여러 가지 페이지 교체 알고리즘에 대해 학습함
  • 프로세스 별 페이지 집합을 관리하는 기법도 살펴봄



학습 목표

  • 다양한 페이지 교체 알고리즘을 설명할 수 있음
  • 프로세스 별 페이지 집합 관리를 설명할 수 있음



강의록

페이지 교체 알고리즘

페이징 기법

  • 모든 페이지 프레임이 사용되고 있을 때 새로 적재되어야 할 페이지를 위해 적절한 교체 대상을 결정

    image.png

교체 대상 선택

  • 최적화의 원칙
    • 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체 대상으로 선택
    • 이론적으로 최적이나 미래를 예측할 수 없어 실현 불가능
  • 선택을 위한 기본 정책
    • 대체로 좋은 결론은 내리면서 선택을 위한 시간 및 공간 오버 헤드가 적은 방법
  • 교체 제외 페이지
    • 페이징을 위한 커널 코드 영역
    • 보조 기억 장치 드라이버 영역
    • 시간을 맞춰 동작해야 하는 코드 영역
    • 입출력 장치를 위한 데이터 버퍼 영역 등

페이지 교체 알고리즘

  • FIFO 페이지 교체
  • LRU 페이지 교체
  • LFU 페이지 교체
  • 2차 기회 페이지 교체

FIFO 페이지 교체

  • FIFO (First-In First-Out)
    • 메모리 내에 가장 오래 있었던 페이지를 선택하여 교체
  • 구현
    • FIFO 큐 이용

    image.png

    1. 교체 대상 페이지 선택 (FIFO 큐의 선두)
    2. 가상 메모리에 보관
    3. 새로운 페이지 적재 (FIFO 큐의 끝에 추가)
  • 단점
    • 가장 많이 쓰이는 페이지를 교체 시킬 가능성 있음
    • Belady의 이상 현상
      • 프로세스에 더 많은 수의 페이지 프레임을 할당하면 오히려 페이지 부재가 더 많이 발생할 수 있는 현상

  • Belady의 이상 현상 예

    image.png

LRU 페이지 교체

  • LPU(Least Recently Used)
  • 메모리 내에서 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체
  • 국부성(locality) 휴리스틱에 기반
    • 최근의 상황이 가까운 미래에 대한 좋은 척도
    • 시간 국부성, 공간 국부성
  • 구현
    • 참조 시각 또는 리스트 이용
  • 참조 시각을 이용한 구현
    • 각 페이지가 참조될 때마다 그때의 시각을 테이블에 기록
    • 교체가 필요한 경우 참조 시각이 가장 오래된 페이지를 선택하여 교체

    image.png

    • 교체가 필요할 때 참조 시각이 가장 오래된 C를 B와 교체
  • 리스트를 이용한 구현
    • 각 페이지가 참조될 때마다 리스트의 선두로 옮김
    • 교체가 필요한 경우 리스트의 끝에 있는 페이지를 선택하여 교체

    image.png

  • 장점
    • Belady의 이상 현상 발생하지 않음
    • 많은 경우 최적화 원칙에 근사한 선택 가능
  • 단점
    • 국부성이 맞지 않는 상황도 존재
    • 막대한 오버 헤드

LFU 페이지 교체

  • LFU(Least Frequently Used)
  • 메모리 내에서 참조 된 횟수가 가장 적은 페이지를 선택하여 교체
  • 구현
    • 참조 횟수 이용
      • 각 페이지가 참조될 때마다 참조 횟수를 기록
      • 교체가 필요한 경우 참조 횟수가 가장 적은 페이지를 선택하여 교체

    image.png

  • 단점
    • 가장 최근에 메모리로 옮겨진 페이지가 교체될 가능성 높음
    • 초기에 매우 많이 사용된 후 더 이상 사용되지 않는 페이지는 교체 가능성 낮음
    • 막대한 오버 헤드

2차 기회 페이지 교체

  • 참조 비트가 0이면서 메모리 내에 가장 오래 있었던 페이지를 선택하여 교체
  • 구현
    • FIFO 큐와 참조 비트 이용
      • 각 페이지가 메모리에 적재될 때는 참조 비트 0
      • 적재된 상태에서 추가로 참조되면 참조 비트 1

    image.png

  • 참조할 페이지가 메모리에 없는 경우
    • 빈 페이지 프레임이 있으면
      • 페이지 적재, 큐에 추가, 참조 비트는 0으로 설정
    • 빈 페이지 프레임이 없으면
      1. 큐의 선두 항목을 꺼내 참조 비트 조사
      2. 참조 비트가 1이면 0으로 바꿔 큐의 뒤에 추가 후 1) 단계로 이동
      3. 참조 비트가 0이면 교체 대상으로 선택하여 교체
  • 참조할 페이지가 메모리에 있는 경우
    • 큐 위치 변화 없이 참조 비트만 1로 설정

  • 큐를 이용한 구현

    image.png

    image.png

    • B 페이지 참조
      • 큐에서 A의 참조 값 1 확인 후 참조 값 0으로 바꿔 큐의 맨 뒤로 이동
      • 큐에서 C의 참조 값 1 확인 후 참조 값 0으로 바꿔 큐의 맨 뒤로 이동
      • 큐에서 D의 참조 값 0 확인 후 참조 값 0이므로 B로 교체
  • 변형 된 원형 큐를 이용한 구현(클럭 페이지 교체 알고리즘)
    • 포인터는 마지막에 추가된 페이지의 다음 위치를 가리킴
      • 빈 페이지 프레임이 있는 경우: 빈칸
      • 페이지 프레임이 꽉 찬 경우: 큐의 선두

      image.png

      image.png

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

  • 프로세스마다 사용할 수 있는 페이지 프레임의 개수만큼 메모리에 유지 되는 페이지 집합
  • 집합의 크기가 작을수록 시스템 처리량 증대
    • 각 프로세스 별 페이지 부재는 자주 발생하여 성능 저하
  • 집합의 크기가 클수록 프로세스 별 페이지 부재는 감소
    • 메모리에 적재될 수 있는 프로세스 수는 줄어듦
  • 각 프로세스가 사용할 수 있는 페이지 프레임 개수 관리
    • 워킹 세트 알고리즘, PFF 알고리즘

워킹 세트 알고리즘

  • 워킹 세트(working set) 모델
    • 페이지 부재 비율을 감소 시키기 위해 Denning이 제안한 모델
  • 프로세스의 워킹 세트 W(t, ∂)
    • 시각 t에 t를 포함한 직전 ∂시간 동안 참조한 페이지의 집합

    image.png

워킹 세트 알고리즘

  • 프로세스가 수행 됨에 따라 그 프로세스의 워킹 세트는 변할 수 있으며 워킹 세트의 크기도 달라질 수 있음
  • 워킹 세트 알고리즘의 원칙
    • 프로세스의 워킹 세트를 메모리에 유지 시키는 것
  • 워킹 세트를 메모리에 유지하지 않으면 쓰래싱 유발 가능
    • 쓰래싱 (thrashing)
      • 페이지 부재가 비정상적으로 많이 발생하여 프로세스 처리보다 페이지 교체 처리에 너무 많은 시간을 소비하여 시스템의 처리량이 급감하는 현상
  • 프로세스마다 워킹 세트 크기에 맞게 페이지 프레임 개수 조절
  • 충분한 여분의 페이지 프레임이 존재
    • 실행 프로세스 수 늘림
  • 실행 중인 프로세스들의 워킹 세트 크기의 합이 총 페이지 프레임 수를 넘어섬
    • 우선 순위가 낮은 프로세스를 일시 중지
  • 문제점
    • 과거를 통해 미래를 예측하는 것이 정확하지 않음
    • 워킹 세트를 정확히 알아내고 계속 업데이트하는 것이 현실적으로 어려움
    • 워킹 세트 윈도 크기 ∂의 최적 값을 알기 어려우며 이 역시 변화할 수 있음

PFF 알고리즘

  • 페이지 부재 빈도(PFF)를 이용하여 프로세스 별 페이지 집합의 크기를 변화 시키는 기법
  • PFF(Page Fault Frequency)
    • 얼마나 자주 페이지 교체가 발생하는 지를 나타내는 척도
    • 페이지 부재가 발생하면 직전 페이지 부재 이후로 경과 된 시간의 역수
  • PFF의 상한과 하한을 정해 둠
  • PFF가 상한보다 높으면
    • 페이지 프레임 개수를 1 증가
  • PFF가 하한보다 낮으면
    • 그 사이에 참조되지 않았던 페이지를 모두 제거
  • 장점
    • 프로세스 별 페이지 집합이 워킹 세트 알고리즘처럼 자주 바뀌지 않음



정리 하기

  • 페이지 교체는 메모리가 완전히 사용되고 있을 때, 새로 적재되어야 할 페이지를 위해 어느 페이지가 교체되어야 하는 지를 다룸
  • 페이지 교체 알고리즘에는 FIFO, LRU, LFU, 2차 기회 페이지 교체 등이 있음
  • 최적의 페이지 교체 방법은 앞으로 가장 오랫동안 사용되지 않을 페이지를 선택하는 방법이지만 현실적으로 불가능함
  • 프로세스는 기억 장치 내의 정보를 균일하게 액세스하는 것이 아니라 어느 한순간에는 특정 부분을 집중적으로 참조하는 국부성을 보임
  • 워킹 세트는 한 프로세스가 최근에 참조한 페이지의 집합임
  • 프로세스가 효율적으로 수행되기 위해서는 워킹 세트가 메모리 내에 유지되어야 함
  • PFF 알고리즘의 기본 아이디어는 페이지 부재 빈도가 높으면 페이지 프레임을 해당 프로세스에 더 배정하고 낮으면 회수하는 것임
Knou, 운영 체제
knou os
Recently Updated
Contents

[데이터베이스 시스템] 10강 - 데이터 저장과 파일

[유비쿼터스 컴퓨팅 개론] 10강 - 상황 인식 처리 기술