[운영체제] 8. 가상 메모리의 관리

OS? Oh Yes! 책을 바탕으로 학습한 내용입니다.

적재 정책(Fetch Strategy) - 언제 적재할 것인가?

• 요구 정책(Demand Fetch)
  적재해야 할 요구가 있을 때 적재
• 예측 적재(Anticipatory Fetch)
  참조될 가능성이 높다고 판단되는 페이지를 미리 적재
  • 디스크 입출력시 인접한 몇 개의 페이지들을 한 번에 적재
  • 프로그램 시작 시점에 당장 참조될 것으로 보이는 몇 개의 페이지 적재

배치 정책(Placement Strategy) - 어디에 적재할 것인가?

• 페이징 시스템에서는 발견되는 빈 프레임에 적재
• 세그먼테이션 시스템에서는 First-Fit, Best-Fit, Worst-Fit을 이용

할당 정책(Allocation Strategy) - 메모리를 얼마나 할당할 것인가?

• 고정 할당(Fixed Allocation)
  프로세스들에게 같거나 다른 메모리 크기의 할당을 변동 없이 고정한다.
• 가변 할당(Variable Allocation)
  실행 도중 프로세스에 부여된 메모리 크기에 변동이 있다.

교체 정책(Replacement Strategy) - 어떤 페이지와 교체할 것인가?

• 지역 교체(Local Replacement)
  해당 프로세스에게 할당된 프레임 중에서 교체될 페이지를 선택하게 함
• 전역 교체(Global Replacement)
  메모리의 모든 프레임들이 교체의 대상이 되는 경우, 고정 할당의 경우 메모리의 크기가 고정되어 있기 때문에 전역 교체가 불가하다.

교체 기법

• 최적 기법(Optimal, MIN)
  페이지 부재를 최소화하는 방법, 미래에 참조할 페이지를 미리 알 수 없으므로 현실적으로는 구현이 불가하다. 다른 기법들의 성능 비교를 위한 잣대
• FIFO(First In First Out) 기법
  적재된지 가장 오래된 페이지를 교체하는 기법, 시간 기록(Time Stamping)을 활용하거나 큐(Queue)를 활용하여 구현한다. 좋은 성능을 보여주지는 못한다.
  • FIFO 모순(FIFO Anomaly)
    일반적으로 프레임 할당이 더 커지면 페이지 부재율이 줄어들지만 FIFO의 경우에 반대로 부재율이 올라가는 경우가 있다.
• LRU(Least Recently Used) 기법
  참조된지 가장 오래된 페이지를 교체하는 기법, 시간 기록을 활용하거나 LRU 스택(Stack)을 활용하여 구현한다. 가장 바닥에 있는 페이지를 교체하는데 스택안에 존재하는 페이지에 대한 재참조가 발생하는 경우 스택 내부에서 가장 위로 이동이 필요하다. 대부분의 시스템에서 LRU 또는 그의 개량형이 쓰인다.
• Second-chance (Clock) 기법
  FIFO의 개량형으로 적재 후 한 번이라도 더 참조된 페이지는 바로 교체하지않고 한 번 더 기회를 주는 기법이다. 참조 비트를 두어 참조 비트가 1인 경우 참조 비트를 0으로 만들면서 큐의 가장 뒤로 보낸다. 순환 큐를 사용하여 페이지를 이동하지 않고 포인터만 이동시키는 구현법(Clock)도 있다.
• NUR(Not Used Recently), 개선된 Second-chance 기법
  Clock 기법에 갱신 비트를 추가하여 데이터가 갱신된 경우 교체를 미루어 디스크에 대한 쓰기 작업을 줄인 기법, 참조 비트와 갱신 비트의 조합으로 4가지 경우를 만들어낸다. (0, 0), (0, 1), (1, 0), (1, 1) 순으로 교체된다.
• LFU(Least Frequently Used)와 MFU(Most Frequently Used) 기법
  • LFU는 참조된 횟수가 가장 적은 페이지를 교체하는 기법
  • MFU는 참조된 횟수가 가장 많은 페이지를 교체하는 기법
• Page Buffering 기법
  부재 발생시 적재할 페이지는 가용 프레임 풀(Pool)로 바로 가져오고 교체 대상으로 선택된 페이지는 변경된 경우(갱신 비트 1) 디스크에 쓰기를 수행한 후 가용 풀로 보내진다. 일반적인 순서(디스크 쓰기 -> 적재)를 지키지 않아도 되기 때문에 응답 속도가 빠르다.

Working set과 PFF(Page Fault Frequency)

• 지역성
  현재 실행되는 명령어나 접근되는 데이터는 당분간 다시 실행되거나 접근될 확률이 높으며 이들과 인접한 명령어나 데이터가 실행되거나 접근될 확률 또한 높다.
• 스레싱(Thrashing)
  다중 프로그래밍 정도(degree of multiprogramming)가 계속 늘어나다 보면 어느 순간부터 페이지 부재(page fault)가 과도하게 늘어나 실제 CPU 사용 시간보다 페이지를 교체(page replacement) 하는 시간이 늘어나게 되는 현상

Working set 이론

지역성을 기반으로 스레싱을 해결하기 위한 방법, 프로세스가 특정 시점에 집중적으로 참조하는 페이지들의 집합을 Working set이라고 한다. 이를 유지함으로써 페이지 부재를 줄인다.

• working set의 구성은 현재로부터 과거 윈도우 크기만큼 개수의 페이지 참조 내에 포함되는 페이지 집합이다.

PFF(Page Fault Frequency)

Working set을 페이지 부재의 간격에 근거하여 결정하는 방법, 시스템에서 정한 적정 부재 간격의 크기를 초과하면 프레임을 줄이고 더 짧은 시간 안에 부재가 나면 프레임을 늘려준다.

• 부재가 없을 경우 Working set을 조정하지 않음으로써 조정의 횟수를 감소시켜 Working set 기법에 비해 오버헤드가 적다.

클리닝 정책(Cleaning Strategy)과 부하 조절(Load Control)

• 클리닝 정책(Cleaning Strategy)
  적재 중 내용이 변경된 페이지를 언제 디스크에 기록시킬 것인가
  • 요구 클리닝(Demand Cleaning)
    교체 대상으로 선택되었을 때 기록, 대부분의 시스템에서 활용
  • 예측 클리닝 또는 선클리닝(Precleaning)
    교체 전이라도 디스크의 부하가 적을 때 미리 기록
• 부하 조절(Load Control)
  다중 프로그래밍의 정도를 결정하는 것, 정도가 너무 낮으면 메모리를 비롯한 시스템의 자원을 활용하지 못해 성능이 떨어질 것이고, 너무 높으면 자원에 대한 경쟁 특히, 부족한 메모리로 인한 스레싱 때문에 성능이 떨어진다.
  • L = S 법칙
    부재 간격의 평균 값과 부재의 처리에 걸리는 시간의 평균 값을 같도록 하는 것이 CPU의 활용도를 최대로 할 수 있다는 연구