19. Virtual Memory

• 가상 메모리
  • 핵심
  • 장점
  • HW, Control 구조
    • Page Table Base Register
    • Page Table Entry
      • 구성요소
        • Present Bit
        • Modified Bit
        • Reference Bit
        • Frame
      • 종류
        • Paging Only
        • Segmentation Only
        • Combined Segmentation and Paging
  • TLB
    • Effective Memory Access Time
      • 고려할 것
      • 시간 계산
    • 과정
  • Fetch 정책
    • Demanding Paging
    • PrePaging
  • Replace 정책
    • 목표 : 가장 호출이 적을만한 Page를 골라서 빼는 것
    • 기준 : Page Fault의 수가 적을 수록, Overhead가 적을 수록 좋은 것
    • 교환
  • Reference String
  • Initial Page Faults
  • Replace Algorithm
    • Optimal Page Replacement
    • FIFO
      • 장점
      • 단점
      • Belady’s Anomaly
    • LRU
      • 단점
    • Clock (Second Chance)
    • Enhanced Second Chance
      • 우선 순위
  • Resident Set Policy
    • 방법
      • Fixed Allocation Policy
      • Variable Allocation Policy
  • Thrashing
  • Working Set
  • Working Set Model
    • 단점
    • Page Fault Frequency
  • 고려할 점
    • Page Size
      • 작을 때
      • 클 때
    • Fast Translation
      • TLB Context Switch
      • 해결
        • Flush
        • ASID
    • Page Table Size
• Page Table Size
  • 해결
    • Combined Paging and Segmentation
      • 장점
      • 단점
    • Hierarchical Paging (Page Table을 Page화)
      • 장점
      • 단점
    • Inverse Page Table
      • 장점
      • 단점

가상 메모리

• 핵심

  • 부분 적재가 가능해야 함
  • Virtual Memory Address로 Physical Address에 접근할 수 있어야 함

• 장점

  • 더 많은 Process를 Main Memory에 올릴 수 있음
  • 물리적인 Memory보다 더 큰 Process들을 수행 가능
  • Protection과 Sharing, Isolation이 유용 (다른 Process의 Table에 접근 불가능)
  • I/O 유발 감소

• HW, Control 구조

  • Page Table Base Register

    Page Table의 크기가 크기 때문에, Page Table 자체는 Memory에서 관리, Page Table의 주소를 Register에 저장

  • Page Table Entry

    • 구성요소

      • Present Bit

        Page가 Memory에 있는지 Disk에 있는지

      • Modified Bit

        Page가 수정된 적 있는지 없는지

      • Reference Bit

        Page가 참조된 적 있는지 없는지

      • Frame

        메모리에서 어디에 저장되어 있는지

    • 종류

      • Paging Only

      • Segmentation Only

      • Combined Segmentation and Paging

        기능에 따라 (코드블럭, 힙, 스택 등등) Segment를 나누고, Segment 들을 Page로 나눔

  • TLB

    Translation Lookaside Buffer MMU에서 Table로의 접근(Memory로 접근)을 최소화 하기 위해 Page Table Entry들을 저장하는 작은 HW Cache

    • Effective Memory Access Time

      TLB가 Miss,Hit 나는 비율을 계산해서 CPU가 요청했을 때 걸리는 평균적인 Memory 접근 시간

      • 고려할 것

        + Memory Access Time + TLB Search Time + TLB Hit Ratio

        • 시간 계산

          (Memory Access Time + TLB Search Time) * TLB Hit Ratio + (Memory Access Time + TLB Search Time + Memory Access Time) * (1 - TLB Hit Ratio (==Failure Ratio))

    • 과정

      1. TLB에서 체크
      2. 있으면 바로 계산해서 접근, 없으면 Table에 접근해서 계산, 만약 Present Bit이 1이면 TLB 업데이트 후 접근
      3. 접근했을 때 Present Bit가 0이면 Page Fault 실행
      4. Memory 공간이 없으면 Replace 알고리즘으로 적재 시킨 뒤 Update

• Fetch 정책

  • Demanding Paging

    보편적인 방법

    해당 Page가 요청될 때 Load하는 방식

    없으면 Page Fault Handler에서 페이지 Load

  • PrePaging

    • 요구하는 Page 뿐만 아니라 그 다음 Page까지 I/O에서 읽는 것

    앞으로 미래에 어떻게 될 지를 아는게 아니고서야 효율적으로 하기가 어려움

• Replace 정책

  Memory가 가득 차거나, OS에서 Multi Programming을 위해 미리미리 준비하기 위해

  • 목표 : 가장 호출이 적을만한 Page를 골라서 빼는 것

  • 기준 : Page Fault의 수가 적을 수록, Overhead가 적을 수록 좋은 것

  • 교환

    더 복잡하고 정교한 교환 법칙일 수록, HW와 SW의 OverHead 증가

• Reference String

  Page가 참조되는 순서 (호출되는 Page 번호 순서)

• Initial Page Faults

  초기에 메모리가 비워져 있어서 날 수 밖에 없는 PageFault

  => 이건 Page Fault로 치지 않음

• Replace Algorithm

  • Optimal Page Replacement

    구현이 불가능함

    Reference String을 다 안다는 가정 하에 전략

    가장 좋은 성능으로 Page Fault가 가장 적음

    Page Fault 수의 하한을 제공하기 때문에 다른 알고리즘과 비교 가능

  • FIFO

    가장 오래된 Page를 내보내는 것

    • 장점

      • 구현이 쉬움

    • 단점

      • 오래된 Page가 빈번하게 호출되는 Page일 수도 있음
      • Belady’s Anomaly 현상

    • Belady’s Anomaly

      보통 Frame 크기 (Page를 담을 수 있는 크기)와 Page Fault는 반비례하는데 이상하게도 Frame 크기와 Page Fault가 비례해지는 현상

      => Reference 순서에 따라서 좀 순서가 안 맞아서 발생할 수 있음

      => ex: Reference String이 1,2,3,4,1,2,5,1,2,3,4,5일 때 Frame 크기가 4일 때와 3일 때를 비교하면 4일 때는 6개, 3일 때가 오히려 PageFault가 5개가 나옴

  • LRU

    가장 오랫동안 사용되지 않은 것을 내보냄

    과거를 봄으로써 Optimal Policy에 Approximate하고자 함

    • 단점

      • 구현이 힘듦 (메모리를 참조할 때마다 Page의 TimeStamp를 Update해야 함)

  • Clock (Second Chance)

    원형의 Frame과 각 Page마다 Reference Bit가 존재

    참조 했으면 1 아니면 0 으로 설정

    Page Fault 발생 시 Pointer가 돌아가면서 Frame의 Reference Bit를 확인하고 0이면 해당 Frame의 Page를 교체, 아니면 Refernece Bit를 0으로 설정한 뒤 다음 Frame으로 넘어감

  • Enhanced Second Chance

    Clock 알고리즘의 Reference Bit에 더해서 Modify Bit를 추가함

    우선순위가 가장 낮은 Page를 선택

    • 우선 순위

      1. 참조X, 수정 X
      2. 참조 X, 수정 O
      3. 참조 O, 수정 X
      4. 참조 O, 수정 O

• Resident Set Policy

  각 Process당 Frame을 얼마나 할당할 지

  • 방법

    • Fixed Allocation Policy

      Process마다 고정된 수의 Frame 제공

      Frame이 부족하면 Local Replacement 수행 (자기 자신의 일부를 버리고 채움)

    • Variable Allocation Policy

      Frame 수가 유동적으로 변함

      Frame이 부족하면 Global Replacement 수행 (다른 여유 있는 Process를 좀 줄이고 내가 사용)

• Thrashing

  Multi Programming Level이 올라가면서, 공간이 부족해져서 Swap in, out이 빈번해지고 Page Fault가 급격하게 올라가면서 오히려 CPU Util이 저하되는 것

• Working Set

  어느 시점에 Program이 접근하는 Page들의 Window 크기 만큼의 집합 #### Window 최근에 참조된 것을 저장하는 공간

• Working Set Model

  Resident Set(메모리에 거주 중인 집합들)을 Working Set과 일치시킴

  Resident Set에 존재하지만 Working Set에는 존재하지 않는 것을 LRU를 기반으로 제거함

  모든 Process들의 Working Set들이 Physical Memory보다 클 때 Thrashing 발생

  • 단점

    • Time Ordered Queue 이기 때문에 구현이 어려움
    • Optimal한 Window Size를 모름 (너무 작으면 Locality 반영 X, 너무 크면 불필요한 페이지도 가지고 있음)

  • Page Fault Frequency

    Page Fault 비율의 상한과 하한을 정해서, 상한을 넘기면 하한보다 밑인 프로세스에게서 Frame을 회수해서 넘겨 Page Fault를 조절

• 고려할 점

  • Page Size

    • 작을 때

      • Page Entry 및 Page Entry Table 증가 (크기가 커져서 좋지 않음)
      • 동일 크기의 데이터를 가져올 때 더 많은 Page를 필요로 해 입출력 횟수 증가

    • 클 때

      • Page Entry 및 Page Entry Table 감소
      • Internal Fragmentation이 커짐

  • Fast Translation

    • TLB Context Switch

      Process가 바뀌었지만, TLB에 잔여 값이 남아 지난 Process의 Page를 참조할 수가 있는 문제 존재

    • 해결

      • Flush

        Switch가 생기면 모든 VPN (Virtual Page Number)의 Valid를 0 으로 설정해 초기화

      • ASID

        Address Space Identifier

        각 VPN에 PID를 적어서 구분

  • Page Table Size

    Page Table Size는 Page 수 * Page별 PTE 크기가 되는데, 각 Process마다 Page Table이 존재해 너무 커짐

Page Table Size

Page Table Size는 Page 수 * Page별 PTE 크기가 되는데, 각 Process마다 Page Table이 존재해 너무 커짐

• 해결

  • Combined Paging and Segmentation

    각 용도 별로 주소를 Segment로 나누고 Segment를 고정된 Page로 나눔

    • 장점

      • Segment Table의 Base에는 해당 Segment의 Page Table만 유지할 수 있어 크기 감소

      • Page 단위로 할당되기 때문에 외부 단편화 X, 내부 단편화만 일부 발생 가능

    • 단점

      • 구현 복잡함 (MMU에서 지원)

  • Hierarchical Paging (Page Table을 Page화)

    Page Table을 더 작은 Page Table Chunks로 나눔

    사용되지 않는 PageTableEntry의 모든 Page들이 사용되지 않으면 그 부분은 할당하지 않음

    • 장점

      • Page뿐만 아니라 Page Table도 연속적으로 존재할 필요 X
      • 메모리 장비 줄임

    • 단점

      • Page Table에 접근하기 위해 Page Directory에 접근하는 추가적인 Load 과정이 필요

  • Inverse Page Table

    오직 System에서 한개의 Page Table만을 가지며, Frame Number를 Index로 PTE에 접근

    Page가 어떤 Process의 Page인지 알기 위해 PID가 추가됨

    => PID와 Page Number를 가지고 Page Table에서 찾으면 해당 Index가 곧 Frame Number가 됨

    • 장점

      • 각 Process 별 Page Table 만들 필요 없어 메모리 절약

    • 단점

      • 찾는데 시간 걸림(Hash Table 사용으로 개선하고자 함)