22. 페이지 교체 알고리즘: Chapter 10. Virtual Memory (Part 2)

10.4 페이지 교체

• 메모리 과할당over allocating
  • 다중 프로그래밍 정도를 올렸을 때 발생할 수 있는 문제
  • ex) 40개의 프레임과 10개의 페이지 중 5개만을 사용하는 6개의 프로세스가 있다고 가정
  • 이 경우 10개의 프레임은 남겨 놓고도 높은 CPU 활용률과 처리율을 얻을 수 있음
  • 그러나 특정 데이터 조합에 대해 이 프로세스들이 10페이지 모두를 사용해야 하는 상황이 발생할 수 있음
  • 또한 40프레임만이 존재하는 상황에서 60프레임을 필요로 하게 됨
• 메모리 과할당의 발생 순서(위 그림 참조)
  • 프로세스가 실행하는 동안 페이지 폴트 발생
  • 운영체제가 필요로 하는 페이지가 보조저장장치에 저장된 위치를 알아냄
  • 그러나 가용한 프레임 목록에 가용한 프레임이 없음을 발견함 (즉, 모든 메모리가 사용중임)
• 이 경우 페이지 교체page replacement가 수행되어야 함

 

 

기본적인 페이지 교체

• 페이지 교체 작업 순서
  1. 보조저장장치에서 필요한 페이지의 위치를 알아냄
  2. 빈 페이지 프레임을 찾음
     1. 비어 있는 프레임이 있다면 그것을 사용함
     2. 비어 있는 프레임이 없다면 희생될victim 프레임을 선정하기 위하여 페이지 교체 알고리즘을 가동 시킴
     3. victim 페이지를 보조저장장치에 기록하고, 관련 테이블을 수정함
  3. 빼앗은 프레임에 새 페이지를 읽어오고 테이블을 수정함
  4. 페이지 폴트가 발생한 지점에서부터 프로세스를 계속함
• 페이지 교체는 demand paging의 기본임
• demand paging이 해결 해야 할 두 가지 중요한 문제 
  • 프레임 할당frame-allocation 알고리즘
    • 여러 프로세스가 존재하는 경우 각 프로세스에 얼마나 많은 프레임을 할당해야 할지 결정하는 문제
  • 페이지 교체page-replacement 알고리즘
    • 페이지 교체가 필요할 때 마다 어떤 페이지를 교체해야 할지 결정하는 문제
• 보조저장장치 I/O가 매우 비용이 많이 든다는 것을 고려할 때, 이러한 문제를 해결할 수 있는 적절한 알고리즘을 설계하는 것은 매우 중요한 문제이며, 요구 페이징 방법은 조금만 개선해도 시스템의 전체 성능이 크게 해결될 수 있음

• 일반적으로 프레임의 수와 페이지 폴트 횟수는 위 그림과 같은 상관 관계를 가지며, 서로 반비례함

 

 

FIFO(first-in first-out) 페이지 교체

• 가장 간단한 페이지 교체 알고리즘
• 어떤 페이지를 교체해야 할 때 메모리에 올라온지 가장 오래된 페이지를 교체함
• 위 그림과 같은 예시 참조열reference string은 3개의 프레임으로 모두 15번의 페이지 폴트가 발생함

• Blelady의 모순Belady's anomaly
  • 프로세스에 프레임을 더 주었는데 오히려 페이지 폴트율을 더 증가하는 현상
  • 위 그림에서 4개의 프레임을 할당 했을 때는 페이지 폴트 10번이 일어났는데, 3개의 프레임을 할당 했을 때는 페이지 폴트 9번이 일어난 것을 알 수 있음

 

 

최적 페이지 교체Optimal Page Replacement

• 최적 페이지 교체 알고리즘은 최적 교체 정책을 따르는 알고리즘임
  • 최적 교체 정책: 모든 알고리즘보다 낮은 페이지 폴트율을 보이며 Belady의 모순이 발생하지 않는 것
• 어떤 페이지를 교체해야 할 때 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체함
• 위 그림과 같은 예시 참조열reference string은 3개의 프레임으로 모두 9번의 페이지 폴트가 발생함
• 어떤 교체 알고리즘도 9회 보다 더 적은 페이지 폴트를 일으킬 수 는 없음
• 그러나 프로세스가 앞으로 메모리를 어떻게 참조할 것인지를 미리 알아야 하므로 실제 구현은 어려움

 

 

LRU 페이지 교체least-recently-used Page Replacement

• 어떤 페이지를 교체해야 할 때 최근의 과거를 가까운 미래의 근사치로 보아 가장 오랜 기간동안 사용되지 않은 페이지를 교체함
• 페이지마다 마지막 사용시간을 유지함
• 위 그림과 같은 예시 참조열reference string은 3개의 프레임으로 모두 12번의 페이지 폴트가 발생함
• LRU 알고리즘은 페이지 교체 알고리즘으로 자주 사용되며 좋은 알고리즘으로 인정받고 있음
• LRU 알고리즘은 하드웨어의 지원이 필요함
• LRU 알고리즘의 2가지 구현 방법
  • 계수기Counter
    • 각 페이지 항목마다 사용 시간 필드를 넣고 CPU에 논리적인 시계나 계수기를 추가함
    • 메모리가 접근될 때마다 시간은 증가함
    • 페이지에 대한 참조가 일어날 때마다 페이지의 사용 시간 필드에 시간 레지스터의 내용이 복사됨
    • 이렇게 각 페이지의 마지막 참조 시간을 유지할 수 있음
  • 스택Stack
    • 페이지가 참조될 때 마다 페이지 번호는 스택의 중간에서 제거되어 스택 꼭대기에 놓임
    • 스택의 꼭대기는 항상 가장 최근에 사용된 페이지임
    • 스택의 밑바닥은 항상 가장 오랫동안 이용되지 않은 페이지임
    • 스택의 중간에서 항목을 제거할 필요가 있으므로 doubly linked list로 구현됨

 

 

LRU 근사 페이지 교체LRU Approximation Page Replacement 

• LRU 알고리즘 지원을 충분히 할 수 있는 하드웨어는 많지 않음
• 그러나 많은 시스템은 참조 비트reference bit의 형태로 어느 정도의 지원을 하고 있음
• 페이지 참조가 있을 때마다 하드웨어가 그 페이지에 대한 참조 비트를 설정함
• 처음에는 운영체제의 의해 참조비트가 0으로 채워지고, 프로세스가 실행 되면서 페이지의 비트는 하드웨어가 1로 세팅함
• 따라서 참조비트가 0인 페이지를 타깃으로 하여 선택하는 방식으로 LRU를 구현할 수 있음

 

 

2차 기회 알고리즘Second-Chance Algorithm

• 2차 기회 알고리즘의 기본은 FIFO 알고리즘임
• 그러나 페이지가 선택할 때마다 참조 비트를 확인함
• 참조 비트가 0이면 페이지를 교체하고, 1이면 다시 한번 기회를 주고 다음 페이지로 넘어감
• 어떤 프레임을 빼앗아야 할 일이 필요해지면 포인터는 0값의 참조 비트를 가진 페이지를 발견할 때 까지 큐를 뒤지고 참조 비트 값들이 1인 것은 0으로 바꿈
• 0을 가지고 있는 victim 페이지를 발견하면 그 페이지는 교체되고 새로운 페이지는 큐의 해당 위치에 삽입됨

 

 

10.5 프레임의 할당

• n개의 프로세스에 m개의 프레임을 분할하는 방법
  • 할당 비율을 다르게 하는 방법
    1. 균등 할당
       • 모두에 같은 몫 m/n 프레임씩 나눠주는 방법
       • ex) 93개의 프레임과 5개의 프레임이 있다고 할 때 각 프로세스는 18개의 프레임을 받음
    2. 비례 할당
       • 각 프로세스의 크기 비율에 맞추어 나눠주는 방법
  • 프레임 할당을 위해 경쟁하는 환경을 다르게 하는 방법
    1. 지역 교체local replacement
       • 각 프로세스가 자기에게 할당된 프레임 중에서만 교체될 희생자를 선택할 수 있는 경우
    2. 전역 교체global replacement
       • 프로세스가 교체할 프레임을 다른 프로세스에 속한 프레임을 포함한 모든 프레임을 대상으로 찾는 경우

 

 

10.6 스레싱Trashing

• 스레싱: 프로세스에 충분한 프레임이 없어 과도한 페이징 작업을 하게 되어 실제 실행보다 더 많은 시간을 페이징에 사용하고 있는 현상

 

 

스레싱의 원인

• 다중 프로그래밍의 정도degree of multiprogramming을 과도하게 높인 경우
  • 초기의 페이징 시스템에서 실제로 있었던 경우의 예시
    • CPU 이용률이 낮아져 새로운 프로세스를 시스템에 더 추가함
    • 이때 전역 페이지 교체 알고리즘을 사용하여 어떤 프로세스의 페이지인지 고려 없이 교체 수행
    • 교체된 페이지들이 해당 프로세스에서 필요로 하는 것들인 경우 또 다들 프로세스에서 프레임을 가져옴
    • 프로세스들이 페이징 장치를 기다리는 동안 CPU 이용률이 떨어짐
    • CPU 이용률이 낮아져 새로운 프로세스를 시스템에 더 추가함
    • ...
    • 결국 실제 메모리 접근 시간은 증가하고 프로세스들은 페이징하는 데 시간을 다 소비하게 되어 아무런 일도 할 수 없게 됨
  • 따라서 이러한 경우 CPU 이용률을 높이고 스래싱을 중지시키기 위해 다중 프로그래밍 정도를 낮춰야 함

• 지역 교체 알고리즘을 사용하여 스래싱의 영향을 제한할 수 있음
• 위 그림은 지역성을 나타냄
  
  • 지역성: 프로세스가 실행될 때 항상 어떤 특정한 지역에서만 메모리를 집중적으로 참조함을 말함
  • 지역: 집중적으로 함께 참조되는 페이지들의 집합을 의미함

 

 

작업 집합 모델Working-Set Model

• 지역성을 토대로 하며, 창(작업 집합 window)을 가지고 있음
• 한 프로세스가 최근 Δ번의 페이지를 참조했다면 그 안에 들어있는 서로 다른 페이지들의 집합을 작업 집합이라고 부름
• 페이지가 활발하게 사용되었다면 작업 집합에 포함됨
• 페이지가 더 사용되지 않게 되면 마지막 참조로부터 Δ만큼의 페이지 후에는 작업 집합에서 제외됨