운영체제 - 제 10장 페이지 교체 알고리즘

10.1 페이지 교체 알고리즘

• 최적화 원칙
  • 최적의 성과를 얻기 위해 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체 대상으로 선택함
  • 미래를 예측할 수 없으므로 실제로 실현 불가능
• 교체 제외 페이지
  • 효율적인 동작을 위해 교체가 일어나지 않도록 페이지 프레임에 고정함
  • 페이징을 위한 커널 코드 영역
  • 커넬에 속하지 못한 보조 기억장치 드라이버 영역
  • 시간을 맞춰 동작해야 하는 코드 영역
  • DMA 등에 의해 입출력로부터 직접 데이터가 교환되어야 하는 데이터 버퍼 영역 등

10.1.1 FIFO 페이지 교체

• FIFO(First In First Out) 페이지 교체 알고리즘
  • 메모리 내에 가장 오래 있었던 페이지 교체
  • FIFO 큐로 구현함
• 단점
  • 가장 많이 쓰이는 페이지를 교체시킬 가능성이 있음
  • Belady의 이상현상 : 프로세스에 더 많은 수의 페이지를 할당할 경우 오히려 페이지 부재가 더 많이 발생하는 현상

10.1.2 LRU 페이지 교체

• LRU(Least Recently Used) 페이지 교체 알고리즘
  • 메모리 내에서 가장 오랫동안 사용되지 않은 페이지 교체
  • 최근의 상황이 가까운 미래에 대한 좋은 척도라는 국부성 휴리스틱에 의존하는 것
• 국부성(locality)
  • 프로세스는 기억장치 내의 정보를 어느 한순간에 특정 부분을 집중적으로 참조한다는 것
  • 시간 국부성과 공간 국부성
• 참조시간을 이용한 LRU 구현
  • 각 페이지가 참조될 떄마다 그때의 시간을 테이블에 기록함
  • 교체가 필요한 경우 참조시간이 가장 오래된 페이지를 교체 대상으로 선택함
• 리스트를 이용한 LRU 구현
  • 메모리에 적재된 페이지 번호를 저장하는 리스트 이용
  • 페이지를 액세스하면 해당 페이지 번호를 리스트의 선두로 옮김
  • 교체가 필요한 경우 리스트의 끝에 있느 ㄴ페이지를 교체 대상으로 선택함
• 장점
  • Belady의 이상현상이 발생하지 않음
  • 최적화 원칙에 근사한 선택 가능
• 단점
  • 경험적 판단이 맞지 않는 상황 존재
    • 여러 페이지로 구성되는 커다란 루프
  • 막대한 오버헤드

10.1.3 LFU 페이지 교체

• LFU(Least Frequently Used) 페이지 교체 알고리즘
  • 메모리 내에서 참조된 횟수가 가장 적은 페이지 교체
• 단점
  • 가장 드물게 이용되는 페이지가 가장 최근에 메모리로 옮겨진 페이지일 가능성이 있음
  • 초기에 매우 많이 사용된 후 더 이상 사용되지 않는 페이지는 불필요하게 메모리를 점유할 가능성이 있음
  • 막대한 오버헤드

10.1.4 2차 기회 페이지 교체

• 2차 기회 페이지 교체 알고리즘
  • 참조 비트가 0이면서 메모리 내에 가장 오래 있었던 페이지 교체
  • FIFO 페이지 교체를 보완한 기법
  • 알고리즘 동작
    1. 참조할 페이지가 메모리에 존재하지 않을 경우
       • 페이지 프레임에 빈 자리가 있을 경우 : 해당 페이지를 페이지 프레임에 적재, 큐에 추가, 참조 비트는 0으로 설정
       • 페이지 프레임에 빈자리가 없을 경우
         • 1단계 : 큐의 선두 항목을 꺼내 참조 비트 조사
         • 2단계 : 참조 비트가 1이면, 그 페이지를 교체 대상으로 선택
         • 3단계 : 참조 비트가 0이면, 그 페이지를 교체 대상으로 선택
           • 교체 대상으로 선택된 페이지가 있던 페이지 프레임에 참조할 페이지 적재, 큐에 추가, 참조 비트는 0으로 설정
    2. 참조할 페이지가 메모리에 존재할 경우
       • 큐의 위치는 변화시키지 않고 해당 페이지의 참조 비트만 1로 설정
• 클럭 페이지 교체 알고리즘
  • 2차 기회 알고리즘에서 큐를 변형된 원형 큐로 관리
    • 원형 큐가 시곗바늘이 돌아가는 것처럼 관리됨
  • 원형 큐의 포인터는 마지막에 추가된 페이지의 다음 위치를 가리킴
    • 페이지 프레임이 꽉 차지 않은 경우 : 포인터는 빈칸을 가리킴
    • 페이지 프레임이 꽉 찬 경우 : 포인터는 큐의 선두를 가리킴

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

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

10.2.1 워킹 세트 알고리즘

• 워킹 세트(working set)
  • 페이지 부재비율을 감소시키기 위해 데닝(Denning)이 제안한 모델
• 프로세스의 워킹 세트 W(t,w)
  • 시각 t에 t를 포함한 직전 w시간 동안 참조한 페이지의 집합
    • w : 워킹 세트의 윈도 크기
  • 시각 t-w+1부터 시각 t까지 참조한 페이지의 집합
  • 프로세스가 수행됨에 따라 페이지가 삭제, 추가 또는 변함없이 유지
• 쓰레싱(thrashing)
  • 페이지 부재가 비정상적으로 많이 발생하여 프로세스 처리보다 페이지 교체처리에 너무 많은 시간을 소비함으로써 시스템의 처리량이 급격히 저하되는 현상
• 워킹 세트 알고리즘
  • 프로세스의 워킹 세트를 메모리에 유지시키는 것을 원칙으로 하는 기법
  • 각 프로세스의 워킹 세트 감시
  • 워킹 세트 크기에 해당하는 충분한 페이지 프레임 할당
  • 충분한 여분의 페이지 프레임이 존재하면 다른 프로세스를 들여옴
    • 실행 프로세스의 수를 늘림
      • 실행 중인 프로세스들의 워킹 세트 크기의 합이 증가하여 총페이지 프레임 수를 넘을 경우
    • 우선순위가 가장 낮은 프로세스를 일시적으로 중지시켜 여유 페이지 프레임 확보
    • 워킹 세트에 포함되지 않는 페이지를 담고 있는 프레임은 필요시 교체 대상으로 선택
• 문제점
  • 과거를 통해 미래를 예측하는 것이 정확하지 않음
  • 워킹 세트를 알아내고 업데이트하는 것이 현실적으로 어려움
  • 워킹 세트를 구하기 위한 윈도 크기 w의 최적값을 알기 어려움

10.2.2 PFF 알고리즘

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

참고 문헌 : 김진욱·이인복. 운영체제 워크북. 한국방송통신대학교출판문화원, 2023.