[OS-10] 주기억장치 관리 전략

1. 반입 전략(Fetch)

• 보조기억장치에 보관 중인 프로그램이나 데이터를 언제 주기억장치로 적재할 것인지를 결정하는 전략
• 요구 반입 : 실행 프로그램이 요구할 때 비로소 적재하는 방법
• 예상 반입 : 앞으로 요구될 가능성이 큰 데이터 또는 프로그램을 예상하여 주기억장치로 미리 옮기는 방법

2. 배치(Placement) 전략

• 새로 반입되는 프로그램이나 데이터를 주기억장치의 어디에 위치시킬 것인지를 결정하는 전략
• 최초 적합(First Fit) : 적재 가능한 공간 중 첫 번째 공간에 배치
• 최적 적합(Best Fit) : 적재 가능한 공간 중 단편화(남는 기억공간)가 가장 적은 공간에 배치
• 최악 적합(Worst Fit) : 적재 가능한 공간 중 가장 큰 공간에 배치

3. 교체(Replacement) 전략

- 최적 교체 (OPT , Optimal replacement)

• 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법
  
• Belady가 제안한 것으로 페이지 부재 횟수가 가장 적게 발생하는 가장 효율적인 알고리즘
  
• 각 페이지의 호출 순서와 참조 상황을 미리 예측해야 하므로 실현 불가
  
• OPT 기법 예 - 3개의 페이지 프레임을 가진 기억장치에서 페이지 부재 수는 4회

---

- FIFO(First In First Out)

• 주기억장치에 가장 먼저 들어와서 가장 오래 있었던 페이지를 교체하는 기법
• 이해하기 쉽고 프로그래밍 및 설계가 간단 
• 프로세스에 할당된 페이지 프레임 수가 증가하면 페이지 부재의 수가 감소하는 것이 당연하지만 페이지 프레임 수가 증가할 때, 현실적으로 페이지 부재가 더 증가하는 모순(anomaly) 현상이 발생
• FIFO 기법 예 - 3개의 페이지 프레임을 가진 기억장치에서 페이지 부재 수는 6회

---

- LRU(Least Recently Used)

• 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법
• 각 페이지마다 계수기나 스택을 두어 현시점에서 가장 오랫동안 사용하지 않은 페이지를 교체
• LRU 기법 예 - 3개의 페이지 프레임을 가진 기억장치에서 페이지 부재 수는 5회

---

- LFU(Least Frequently Used)

• 사용 빈도가 가장 낮은 페이지를 교체하는 기법
• LFU 기법 예 - 4개의 페이지 프레임을 가진 기억장치에서 페이지 부재 수는 5회

---

- NUR(Not Used Recently)

• LRU와 비슷한 알고리즘으로 최근에 사용하지 않은 페이지를 교체하는 기법
• 최근의 사용 여부를 확인하기 위해 각 페이지마다 2개의 비트를 사용, 참조 비트(Reference Bit)와 변형 비트(Modified Bit)를 사용
• 참조 비트와 변형 비트의 값에 따라 순서가 결정되고 페이지 교체 

NUR 교체 순서 (0 : 참조 안됨, 1 : 참조됨)

---

- SCR(Second Chance Replacement)

• 가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 것으로, FIFO 기법의 단점을 보안한 기법
• 교체 대상이 되기 전에 참조 비트를 검사하여 1일 경우 한 번의 기회를 더 부여
• 각 페이지에 프레임을 FIFO 순으로 유지시키면서 LRU 근사 알고리즘처럼 참조 비트를 가짐