[운영체제] Day10. Virtual Memory

Demand Paging

• 요청이 있을 때 page를 메모리에 올리는 것
  • I/O 양의 감소 (방어적 코드 작성. 대부분의 경우 사용하지 않는 코드들.)
  • memory 사용량의 감소
  • 빠른 응답 시간
  • 더 많은 사용자 수용
• valid / invalid bit
  당장 필요한 부분은 Demading Paging 에 의해 메모리 상에 존재할 것.
  그렇지 않은 부분은 Backing Store (Swap Area, Disk) 상에 존재

  invalid의 의미

  사용되지 않는 주소 영역. 혹은 페이지가 물리적 메모리에 없는 경우.
  처음에는 모든 page entry가 invalid로 초기화
  address translation 시에 Invalid bit이 set 되어 있으면 page fault
  page fault trap 발생 시 CPU는 OS에게 넘어감 (일종의 interrupt)

Page Fault

invalid page 접근 시 page fault 발생.
Kernel mode 로 진입해서 page fault handler invoke
1. 요청의 유효성 확인 (invalid address, protection violaition => abort)
2. 정상적 메모리 요청이라면 메모리 상에서 empty page frame 확보 (없으면 뺏는다. replace)
3. Disk에서 memory로 page 옮겨옴 (disk I/O 통해서)
Disk I/O는 몹시 느리므로 이 프로세스는 block 당함 (disk I/O 완료까지)
4. 이 프로세스가 다시 CPU 획득 후 주소 변환
5. 정상적 instruction 시행

Replacement

Page Replacement

free frame이 없는 경우 어떤 frame을 빼앗아올지 결정해야 함
곧바로 사용되지 않을 page를 쫓아내자 (Replacement Algorithm)
같은 페이지가 여러 번 쫓겨나서 다시 불러와질 수 있음. (Bad Case)
OS의 역할 : page table의 valid bit toggle / put frame #

Replacement Algorithm

page-fault rate 최소화하는 것이 목표.
알고리즘의 평가 : 주어진 page reference string에 대해 page fault 얼마나 내는지 (Bad!)

Optimal Algorithm

page-fault rate 최소화하는 알고리즘
미래에 참조되는 Page를 알고 있다고 가정하는 알고리즘 (offline algorithm)

• Belady's Algorithm(MIN, OPT) : 가장 먼 미래에 참조되는 page를 replace
  다른 알고리즘의 성능에 대한 Upper Bound

FIFO Algorithm

FIFO (First In First Out) : 선입 선출 방식

• FIFO Anomaly(Belady's Algorithm)
  통상 frame이 많아지면 PF 감소해야 하는데 오히려 늘어날 수 있음.

LRU Algorithm

LRU (Least Recently Used) : 가장 오래 전에 참조된 것을 지운다.

• 구현 : 이중 연결 리스트 Queue 사용.
  최근 참조 Node를 후순위에 매달고, 맨 앞 Node제거. O(1) complexity

LFU Algorithm

LFU (Least Frequently Used) : 가장 덜 참조된 것을 지운다.

• 최저 참조 횟수 Page가 여럿 있는 경우 LRU를 섞을 수도
• LRU보다 page의 인기도를 더 정확하게 파악 가능
• 참조 시점의 최근성을 반영하지 못함. (과거에 자주 쓰이다가 최근에 안쓰이면)
• LRU 보다 구현이 복잡함.
• 구현 : heap 이용 구현, 참조횟수 기준 오름차순 정렬. O(log n) complexity

  Caching

  한정된 빠른 공간에 요청된 데이터를 저장해 두었다가 후속 요청 시 캐쉬에서 로드.
  캐쉬는 보통 제한된 공간을 사용. 때문에 무언가를 교체 과정이 발생.
  이때 교체 알고리즘에서 삭제 항목을 결정하는 일에 많은 시간이 걸리면 실제 사용이 불가능하다.

  • Paging System
    • page fault가 나는 상황을 제외하고는 OS에게 CPU가 넘어오지 않으므로
      어떤 page가 많이 참조되는지 알 수 없음. (LRU, LFU 사용 불가)

Clock Algorithm

LRU의 근사 알고리즘
여러 명칭으로 불림 - Second Chance Algorithm, NUR / NRU (Not Recently Used)

• 구현 :
  reference bit 이용 (Memory에 올라온 page 참조 시 reference bit toggle to 1)
  Page fault 나서 한 Page를 쫓아내야 하는 상황이 온다면,
  clock에서 reference = 0 인 Page를 쫓아낸다.
  이때, 0 to 1 toggle은 hardware가, 1 to 0은 clock을 도는 OS가 진행한다.
  한 바퀴 되돌아와서도 (second chance) 0이면 그때는 replace.
  자주 사용하는 page라면 second chance 때 1.
• 개선 :
  modified bit 활용. 최근에 변경된 page 표시
  modified bit = 1이면 memory에서 삭제 시 Disk의 값을 update 하고 삭제해야 함.

Page Frame Allocation

Allocation Problem : 각 Process에 얼마만큼의 page frame 할당할 것인가?
반복문의 경우, page frame을 모두 할당하지 않으면 무수히 많은 page fault 발생 가능

Allocation Scheme

Equal Allocation

모든 프로세스에 똑같은 개수 할당

Proportional Allocation

프로세스 크기에 비례하여 할당

Priority Allocation

프로세스 우선순위 따라 할당

Global vs. Local Replacement

Global Replacement

Process 마다 나눠서 frame을 할당해두지 않음.
LRU, LFU 등의 Replacement 마다 다른 Process의 frame을 뺏기 가능.
어차피 자주 사용되는 Process가 많은 memory를 자연스레 차지할 것.

Local Replacement

Process 마다 나눠서 frame 할당.
할당된 frame 내부에서 Process 각각이 Replacement 진행.
LRU, LFU 등의 알고리즘을 Process 별 운영.

Thrashing

Thrasing

프로세스 원활한 수행에 필요한 최소한의 page frame을 할당받지 못한 경우.
replacement가 발생. page fault rate 상승. CPU 사용률 증가.
x축, 프로세스 차수. 멀티 프로그래밍 차수 증가 시 CPU 사용률 증가 (Good)
하지만 어느 지점 (Thrasing) 발생 지점을 기준으로 CPU 사용률 급감

• 각 프로세스에 할당된 메모리가 너무 작다 : 무수히 많은 Page Fault 발생.
• 사용률 적네? -> 프로세스 추가 -> 더 적네 -> 다시 추가 ...

Working-Set Model

프로세스는 특정 시간동안 일정 장소만을 집중적으로 참조한다.
해당 page들의 집합을 Locality Set 이라고 부른다.

• Locality 기반하여 프로세스가 일정 시간동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page 집합을 Working Set 이라고 부른다.
• working set 전체가 메모리에 올라오는 것이 보장이 안되면 자원(frame)을 반납 => thrasing 방지
• Working-Set의 결정
  • Working-Set의 window로 알아냄.
  • window size = delta인 경우
  • 시점 t에서 t-delta 까지의 참조된 서로 다른 페이지 집합.
  • 즉, 참조 후 delta만큼 유지하는 것과 같음.

PFF (Page-Fault Frequency) Scheme

Page-fault rate의 상한과 하한을 둔다.

• 상한을 넘으면 frame 추가 할당.
• 하한 이하면 frame 수 줄임.
• 빈 frame 없으면 일부 프로세스 swap out

Page Size 결정

• Page Size 감소시키면
  • Page 수 증가
  • Page Table 크기 증가 (메모리 사용 증가)
  • Internal Fragment 감소
  • 필요한 정보만 메모리 올라와 메모리 이용이 효율적
  • Disk transfer 효율성 감소
    • 한 번 읽을 때 많이 읽는 게 좋다 (Seek/Rotation 증가는 비효율 초래)
  • Locality 활용 측면에서는 좋지 않음.
• Trend : Larger Page Size