Virtual Memory - hochan222/Everything-in-JavaScript GitHub Wiki

바로가기
바로가기

물리적인 주소변환은 운영체제가 관여하지 않는다.
하지만, Virtual Memory는 운영체제가 관여한다.

Demand Paging

• 실제로 필요할 때 page를 메모리에 올리는 것
  • I/O 양의 감소
  • 메모리 사용량 감소
  • 빠른 응답 시간
  • 더 많은 사용자 수용
• Valid / Invalid bit의 사용
  • Invalid의 의미
    • 사용되지 않는 주소 영역인 경우
    • 페이지가 물리적 메모리에 없는 경우
  • 처음에는 모든 page entry가 invalid로 초기화
  • address translation 시에 invalid bit가 set되어있으면 page fault

Memory에 없는 Page의 Page Table

Page Fault

• invalid page를 접근하면 MMU가 trap을 발생 시킴 (page fault trap)
• Kernel mode로 들어가서 page fault handler가 invoke됨
• 다음과 같은 순서로 page fault를 처리한다.

대부분의 경우는 페이지 폴트는 나지 않는다 0.9xxxx

Free frame이 없는 경우

OS가 하는 역할, 빈페이지가 없을 경우 어떤 페이지를 쫓아내고 대체할지

• Page replacement
  • 어떤 frame을 빼앗아올지 결정해야 함
  • 곧바로 사용되지 않을 page를 쫓아내는 것이 좋음
  • 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있음
• Replacement Algorithm
  • page-fault rate을 최소화하는 것이 목표
  • 알고리즘의 평가
    • 주어진 page reference string에 대해 page fault를 얼마나 내는지 조사

Optimal Algorithm

• Min(OPT): 가장 먼 미래에 참조되는 page를 replace
• Page Fault를 가장 적게 하는 알고리즘
• Offline algorithm

FIFO (First In First Out) Algorithm

• 먼저 들어온 것을 먼저 내쫓음

• FIFO Anomaly (Belady's Anomaly)
  • more frames => more page faults

LRU (Least Recently Used) Algorithm

• LRU: 가장 오래 전에 참조된 것을 지움.

LFU (Least Frequently Used) Algorithm

• LFU: 참조 횟수가 가장 적은 페이지를 지움

다양한 캐쉬 환경

• 캐슁 기법
  • 한정된 빠른 공간(=캐쉬)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐쉬로부터 직접 서비스 하는 방식
  • paging system 외에도 cache memory, buffer caching, Web caching등 다양한 분야에서 사용

Pageing System에서 LRU, LFU 가능한가?

이미 메모리에 있는 경우는 운영체제는 가장 최근, 자주 참조된것을 모르기 때문에 불가능하다.
trap(page fault)이 발생할 때만 CPU 점유권이 운영체제에게 넘어온다.

Clock Algorithm

• NRU (Not Recently Used)

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에 따라 다르게 할당

Global vs Local Replacement

• Global replacement
  • replace 시 다른 process에 할당된 frame을 빼앗아 올 수 이싿
• Local replacement
  • 자신에게 할당된 frame 내에서만 replacement

Trashing

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

Working-Set Model

• Locality of reference

  • 프로세스는 특정 시간 동안 일정 자소만을 집중적으로 참조한다
  • 집중적으로 참조되는 해당 page들의 집합을 locality set이라 함

• Working-set Model

  • Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합을 Working Set이라 정의함
  • Working Set 모델에서는 process의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 frame을 반납한 후 swap out
  • Thrashing을 방지함
  • Multiprogramming degree를 결정함

PFF (Page-Fault Frequency) Scheme

Page Size의 결정

• Page size를 감소시키면

  • 페이지 수 증가
  • 페이지 테이블 크기 증가
  • Internal fragmentation 감소
  • Disk transfer의 효율성 감소
  • 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
    • Locality의 활용 측면에서는 좋지 않음

• Trend

  • Larger page size