가상 메모리 관리의 목적 !

• 가상 메모리 시스템 성능 최적화
  • Cost model을 최소화하는 다양한 최적 화 기법

Cost model(Paging가정)

• Page fault frequency(발생 빈도)
  • CPU가 참조하려는데 메모리에 없는 경우
  • running ➡ asleep ➡ ready의 과정
• Page fault rate(발생률)
• Page fault rate를 최소화 할 수 있도록 전략들을 설계해야함
  • Context switch 및 kernel 개입을 최소화
  • 시스템 성능 향상

용어

• Page(segment) reference string (d, 페이지 참조 문자열)
  • 프로세스의 수행 중 참조한 페이지 번호와 순서
  • ω : r1,r2 ~~ rT (번호와 순서),
    • r:페이지 번호, N:프로세스의 페이지 수
    • 정보가 있어야 효율적으로 사용 되고 있는 지 기록을 저장 및 기준을 정함
• Page fault rate = F(ω) (발생률)
  • page fault 수 / |ω|(참조한 페이지 길이)

Hardware Components

• Address translation device (주소 사상(변환) 장치)
  • 주소 사상을 효율적으로 수행하기 위해 (TLB, Cache)

• Bit Vectors (bit 배열들)

  • Page 사용 상황에 대한 정보를 기록하는 비트들 (기준)
  • Reference bits(used bit) - 참조 비트
    • 메모리에 적재된 각각의 page가 최근에 참조되었는 지 표시
    • 1. 프로세스에 의해 참조가 되면 해당 page의 ref.bit를 1로 설정
      2. 주기적으로 모든 ref.bit를 0으로 초기화
    • Locality(지역성)
  • Update bits(modified, wirte, dirty) - 갱신 비트
    • Page가 메모리에 적재된 후, 프로세스에 의해 수정되었는 지 표시
    • 주기적인 초기화 없음, 메모리에서 나올 때 초기화
    • Update bit = 1
      • 해당 page의 Memory data와 swap device의data가 다를 경우
        write-back(to swap device)이 필요
  • 

📌Software Components

성능향상을 위하 관리 기법들

• Allocation strategies

  • 각 프로세스에게 메모리를 얼마 만큼 줄 것인가?
    • Fiexed allocation (고정 할당) : page freme 수를 고정
    • Variable allocation (가변 할당) : 메모리 크기 유동적(할당 받은 page frame 수가 유동적임)
  • 고려사항
    • 프로세스 실행에 필요한 메모리 양을 예측해야함
    • 너무 큰 메모리 할당인 경우 ➡ 메모리가 낭비 됨.
    • 나무 적은 메모리 할당할 경우 ➡ Page fault rate 높음(성능 저하)

• Fetch strategies

  • 특정 page를 메모리에 언제 적재할 것인가?
    • Demand fetch (요구할 때마다 적재) : 프로세스가 참조하는 페이지들만 적재, page fault overhead가 큼
    • Anticipatory fetch(pre-paging)
      • 참조될 가능성이 높은 page 예측
      • 가까운 밀에 참조될 가능성이 높은 page를 미리 적재
      • 예측 성공 시, page fault overghead가 없음
      • Prediction overhead (kernel의 개입, 예측할 때 overhead 증가), Hit ratio(예층 성공률)에 민감함
  • 대부분의 시스템은 Demand fetch 기법사용
    - 일반적으로 준수한 성능을 보여 줌!

    내가 만든 프로그램 하나는 일종의 하나의 OS -> 내가 원하는 가상 메모리를 만들 경우가 생김 이때는 Anticipatory fetch 사용할 수 있음

• Placement strategies

  • Page/segment를 어디에 적재할 것인가?
  • Paging system에는 불필요하다. (크기가 동일하기 때문에)
  • Segmentation system에서의 배치 기법(First-f, Best-f,Worst-f,Next-f)

• Placement strategies (빈 페이지가 없는 경우)

  • 새로운 page를 어떤 page와 교체 할 것인가?
  • 📌Fiexed allocation을 위한 교체 기법
  • 📌Variable allocation을 위한 교체 기법

• Cleaning strategies (Update-bit, dirty-bit)

  • 변경된 page를 언제 wirte-back 할 것인가?
    • 변경된 내용을 swap device에 반영
    • Demand cleaning
      • 해당 page가 메모리에서 나올 때
    • Anticipatory cleaning (pre-cleaning)
      • 더이상 변경될 가능성이 없다고 판단 할 때, 미리 wirte-back
      • Page 교체시 발생하는 write-back 시간 절약 ↔ 이후 page 내용이 수정되면 Overhead!
    • 실제 대부분의 시스템은 Demand cleaning 기법사용
    • 일반적으로 준수한 성능, pre-cleaning으로 잘못된 예측 시 자원 낭비가 큼

• Load Control strategies (부하 제어 )

  • 시스템의 mulit-programming degeree 조절
    • Allocation strategies 와 연계 됨. 100개의 프로세스일 때와 1개일 때 Allocation strategies도 달라지기 때문에
  • 적정 수준의 multi-programming degree를 유지해야함
    • Plateau(고원) 영역으로 유지
    • 저부하 상태(Under-loaded) : 시스템 자원 낭비, 성능 저하
    • 고부하 상태(Over-loaded) : 자원에 대한 경쟁 심화, 성능 저하
      Thrashing(스레싱) 현상 발생 (과도한 page fault가 발생함)

Other Considerations

추가 고려사항

📌Page size

• 시스템 특성에 따라 다름
  • 최적의 정답은 없음. 적당히!
  • 현재 점점 커지는 경향 (CPU, MemorySize가 증가 I/O 시간을 최대한 줄임)
    • Disk(I/O)의 발전속도보다 CPU의 발전속도가 훨씬 빠르다.
      ➡ Disk에서 전달해주는 속도가 CPU 처리속도를 못 따라감(I/O 병목현상)
      즉 I/O시간을 줄이는게 좋기 때문에 page size가 큰게 좋다.
• 일반적인 page size
  • 128 bytes ~ 4M bytes
• Small page size
  • 페이지수가 많음, page table이 큼 ➡ Kernel이 관리하는 Overhead가 큼
  • 내부 단편화가 감소 되고, Locality는 향상 됨
  • I/O 시간이 증가(하나의 작업을 위해 page를 여러개 올려야 함)
  • Page fault 증가
• Large page size
  • 페이지수가 적음, page table이 작음 ➡ Kernel이 관리하는 Overhead가 작음
  • 내부 단편화 증가, Locality 저하(필요없는 것 까지 같이 올라가 있는 경우)
  • I/O 시간 감소, Page fault 감소
    

📌Program Restructuring

• 가상 메모리 시스템(OS)의 특성에 맞도록 프로그램을 재구성한다
• 사용자가 가상 메모리 관리 기법(예, paging system)에 대해 이해하고 있다면, 프로그램의 구조를 변경하여 성능을 높일 수 있음
• Example -> Notion

📌TLB Reach

• HW, 옆에 두고 보는 Buffer
• TLB를 통해 접근 할 수 있는 메모리의 양
  • entry 수(TLB 크기) * 2. page size = TLB Reach
• TLB의 hit ratio를 높이려면
  • TLB 크기 증가 ➡ 비쌈
  • Page 크기 증가 or 다양한 page size 지원
    ➡ OS의 지원이 필요, 최근 OS의 발전 경향임
• 사용자가 가상 메모리 관리 기법(예, paging system)에 대해 이해하고 있다면, 프로그램의 구조를 변경하여 성능을 높일 수 있음
• Example -> Notion

---

https://youtu.be/EdTtGv9w2sA [Course] Operating System (CPA310) - 운영체제 강의. HPC Lab. KOREATEC