[OS] 페이지 교체 알고리즘

🎇가상 메모리 관리를 위해 요구되는 정책과 기법

• 적재 정책(Fetch Strategy)
  실행에 필요한 페이지를 언제 적재할 것인가
  
  - 요구 적재(Demand Fetch)
    페이지가 참조될 때 적재
    필요한 페이지만 메모리를 사용해 오버헤드가 없으나,
    페이지가 부재일 경우 적재될 때까지 해당 프로세스를 대기 상태로 만드는 문맥교환, 디스크 입출력 부담
  
  - 예측 적재(Anticpactory Fetch)
    예측을 통해 확률적으로 참조될 가능성이 높다고 판단되는 페이지 적재
    예측이 잘 되지 않을 경우 예측을 위한 오버헤드와 메모리 낭비 발생
  
  
  
• 배치 정책(Placement Strategy)
  디스크로부터 가져온 페이지를 메모리의 어디에 적재할 것인가 결정하는 정책
  메모리가 페이지의 크기와 같은 프레임으로 이루어져 있으므로,
  빈 프레임 어디에 적재하든 문제가 없음 -> 신경 안써도 됨
  세그멘테이션-> 다양한 크기의 세그먼트 수용 -> 배치 정책 요구
  
  
  
• 할당 정책(Allocation Strategy)
  프로세스들에게 메모리를 얼마큼씩 줄 것인지 결정하는 정책
  각 프로세스에게 메모리 프레임을 몇 개 사용할 수 있도록 해줄 것인지 결정
  
  - 고정 할당 (Fixed Allocation)
    프로세스에게 시스템에서 정해놓은 개수의 프레임만 사용하도록 하고 개수의 변동이 없도록
  
  - 가변 할당 (Variable Allocation)
    실행 도중 부여된 프레임의 수에 변동이 있도록 함
  
  
  
• 교체 정책(Replacement Strategy)
  메모리에 빈 프레임이 없을 때 적재될 페이지를 위해
  이미 적재된 페이지 중 교체대상을 결정하는 정책
  
  - 지역 교체 (Local Replacement)
    해당 프로세스에 할당된 프레임 중에서 교체될 페이지를 선택하도록
  
  - 전역 교체 (Global Replacement)
    메모리의 모든 프레임들이 대상이 됨  
    전역교체에서 프레임이 하나 줄어야 하는 프로세스가 생기면
    다른 어떤 프로세스에게는 프레임이 하나 증가하는 것을 의미함 => 고정 할당 불가능
    할당된 프레임의 수는 변경할 수 있어도 교체의 대상은 자신의 프레임 내에서 교체 => Working Set 이론, PFF
  
  
  
• 클리닝 정책
  적재 중 내용이 변경된 페이지를 언제 디스크에 기록시킬 것인가
  
  
  
• 부하조절
  다중 프로그래밍 정도 결정
  메모리의 효율적 관리와 밀접한 관계

 

📃페이지 교체 알고리즘

고정할당 기반

• OPT(최적, Optimal, Min) 알고리즘
  현 시점에서 앞으로 가장 오랫동안 참조되지 않을 페이지 선택, 교체 알고리즘
  프로세스들이 앞으로 어떤 페이지를 참조할지 알 수 없어 현실적으로 불가능하지만,
  구현이 가능한 다른 성능들과의 비교에 사용됨
  페이지 부재일 경우 빈 프레임에 넣거나 가장 참조가 먼 페이지를 교체한다.

8번

• FIFO(First In First Out) 기법
  적재된 지 가장 오래된 페이지를 교체하는 방법
  - 시간 기록을 사용하기
    가장 오래된 페이지를 찾는데 오버헤드가 발생함
  - 큐를 사용하기
  페이지 부재가 많이 발생하므로 좋은 교체 정책이라고는 할 수 없음

12번

• LRU(Least Recently Used) 기법
  참조된지 가장 오래된 페이지가 교체 대상
  - 시간 기록 사용하기
    역시 오버헤드 발생
  - LRU 스택 사용하기
    이미 적재되어있는 페이지의 위치를 바꿀 때 오버헤드 발생
    스택의 가장 밑에 있는 페이지가 교체 대상이 되도록 스택의 위치가 상대적인 참조 순서를 나타내도록 함
  최적보다는 못해도 FIFO보다 나은 성능, 현재의 대부분의 시스템이 LRU나 LRU를 변형시킨 기법 사용

10번

• Second-chance(Clock) 기법
  FIFO의 변형이면서 LRU에 근접하는 기법
  한번이라도 더 참조된 페이지를 바로 교체시키지 않고 한번 더 메모리에 머무를 수 있는 기회를 줌
  순환 큐를 사용하기도 한다 -> Clock
  
  
• LFU (Least Frequently Used)와 MFU(Most Frequently Used)
  적재되어있는동안 참조된 횟수를 누적하여 기록함
  LFU - 많이 참조된 페이지는 앞으로도 참조될 확률 높을 것 같아 선택
  MFU - 많이 참조된 페이지는 앞으로 더 이상 참조될 확률이 낮을 것 같아 참조되지 않은 페이지 선택
  모두 너무 편향되어서 사용하지 않음

출처 : 김주균, 「OS? Oh Yes!」, 휴먼싸이언스