[운영체제] 9. Virtual Memory (2)

kocw 반효경 교수님의 운영체제 강의를 수강 후 작성한 글입니다.

1. Page Frame의 Allocation

• Allocation Problem: 각 process에 얼마만큼의 page frame을 할당할 것인가?
• Allocation의 필요성
  • 메모리 참조 명령어 수행 시 명령어, 데이터 등 여러 페이지를 동시 참조함. 따라서 명령어 수행을 위해 최소한 할당되어야 하는 frame 수가 있음
  • Loop를 구성하는 page들은 한꺼번에 allocate되는 것이 유리함. 최소한의 allocation이 없으면 매 loop 마다 page fault가 발생할 것임
• Allocation Scheme
  • Equal allocation: 모든 프로세스에 똑같은 갯수 할당
  • Proportional allocation: 프로세스 크기에 비례하여 할당
  • Priority allocation: 프로세스의 priority에 따라 다르게 할당 (eg. system app > user app)

Global vs. Local Replacement

• Global replacement
  • 메모리 전체를 대상으로 함 
  • Replace 시 다른 process에 할당된 frame을 빼앗아 올 수 있음
  • Process 별 할당량을 조절하는 또 다른 방법임
  • FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용시에 해당
  • Working Set, PFF 알고리즘 사용
• Local Replacement
  • 자신에게 할당된 frame 내에서만 replacement
  • FIFO, LRU, LFU 등의 알고리즘을 process 별로 운영시 사용

Thrashing

• 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당 받지 못한 경우 발생
• page fault rate이 매우 높아짐
• CPU utilization이 낮아짐
• OS는 MPD(Multiprogramming degree)를 높여야 한다고 판단
• 또 다른 프로세스가 시스템에 추가됨 (higher MPD)
• 프로세스 당 할당된 frame 수가 더욱 감소
• 프로세스는 page의 swap in/out 으로 매우 바쁨 -> CPU utilization은 더욱 감소 (CPU는 한가함)
• Low throughput

Working-Set Model

• Locality of reference
  • 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조함. 집중적으로 참조되는 해당 page들의 집합을 locality set이라 한다.
• Working-set Model
  • Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합을 Working Set이라 정의함
  • Working Set 모델에서는 process의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 frame을 반납한 후 swap out(suspend)
  • Thrashing을 방지함 (page fault 발생을 방지)
  • Multiprogamming degree를 결정함 (working set이 올라와있지 않으면 degree 감소)
• Working-set의 결정
  • working set window를 통해 알아냄
  • window size가 △인 경우
    • 시각 ti에서의 working set WS(ti): Time interval [ti-△, ti] 사이에 참조된 서로 다른 페이지들의 집합
    • Working set에 속한 page는 메모리에 유지, 속하지 않은 것은 버림 (즉, 참조된 후 △시간 동안 해당 page를 메모리에 유지한 후 버림)
• Working-set algorithm
  • process들의 working set size의 합이 page frame의 수보다 큰 경우
    • 일부 process를 swap out시켜 남은 process의 working set을 우선적으로 충족시켜 준다. (MPD 줄임)
  • Working set을 다 할당하고도 page frame이 남는 경우
    • Swap out되었던 프로세스에게 working set을 할당 (MPD를 키움)
• Window size △
  • Working set을 제대로 탐지하기 위해서는 window size를 잘 결정해야 함
  • △ 값이 너무 작으면 locality set을 모두 수용하지 못할 우려 (page fault 발생)
  • △ 값이 너무 크면 여러 규모의 locality set 수용
  • △ 값이 ∞ 이면 전체 프로그램을 구성하는 page를 working set으로 간주

PFF (Page-Fault Frequency) Scheme

• page-fault rate의 상한값과 하한값을 둔다.
  • page-fault rate이 상한값을 넘으면 frame을 더 할당한다.
  • page-fault rate이 하한값 이하이면 할당 frame 수를 줄인다.
• 빈 frame이 없으면 일부 프로세스를 swap out (MPD를 줄여서 thrashing 방지)

Page Size의 결정

• Page size를 감소시키면
  • 페이지 수 증가 -> 페이지 테이블 크기 증가
  • Internal fragmentation 감소
  • Disk transfer 효율성 감소
    • page size가 작아지면 seek/rotation time이 증가하고, page size가 커지면 transfer time이 증가한다.
    • seek/rotation time이 커지는 것이 transfer보다 더 큰 영향을 미치기 때문에 page size가 감소해서 page 수가 증가하면 disk transfer의 효율성이 감소한다.
  • 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
    • Locality 활용 측면에서는 좋지 않음
• Trend: Larger page size