CS지식/운영체제

[OS]가상메모리

초보개발자.. 2022. 5. 14. 14:24

가상메모리리란

물리적인 메모리는 크기에 제약이 발생한다. 그렇기 때문에 가상 메모리를 두어 메모리 크기에 대한 제한을 없애고, 더 많은 프로세스들을 실행시킬 수 있게 도와준다.

 

Demand Paging(요청이 있다면 페이지를 메모리에 올리겠다)

  • 필요할 때 page를 메모리에 올리는 것
    • I/O 양의 감소(빈번히 사용되는 부분은 제약적이라서)
    • Memory 사용량 감소
    • 빠른 응답 시간
    • 더 많은 사용자 수용
  • Valid/Invalid bit 사용
    • Invalid: 사용되지 않는 주소 영역, 페이지가 물리적 메모리에 없는 경우
    • 처음에는 page entry가 invalid, address translation 시에 invalid bit이 set되어 있으면 -> page fault

Page Fault(요청한 페이지가 메모리에 없는 경우 -> 운영체제에게 넘김[interrupt])

  1. invalid이면 MMU(주소변환 하드웨어)가 trap 발생
  2. kernel mode로 들어가서 page fault handler가 invoke
    1. invalid reference? abort process
    2. get empty page frame(자리가 없으면 뺏어오기)
    3. 해당 페이지를 disk에서 memory로
      1. disk I/O 끝나기까지 프로세스는 CPU를 preempt
      2. Disk read가 끝나면 page entry table 기록, bit = Valid
      3. ready queue에 process insert -> 이후 dispatch
    4. cpu잡고 다시 running
    5. 중단되었던 instruction을 재개

Steps in Handling a Page Fault

  1. 메모리 레퍼런스를 통해 페이지 테이블을 보게 되는데 Invalid로 표시가 되어 있는 것을 확인합니다.
  2. 이 페이지가 메모리에 올라와 있지 않다는 것임으로 trap을 걸어 운영체제에게 cpu 제어권을 넘기게 됩니다.
  3. 운영체제는 Backing store에 들어갑니다.
  4. 물리적인 메모리에 올려 놓습니다,
  5. 올려 놓는 작업이 끝난다면 pageTable에 프레임번호를 올려놓고 invalid를 valid로 바꾸고 시작합니다.

빈 페이지가 없을 경우 페이지를 쫓아내고 그 자리에 새로운 페이지를 올려 놓는 작업을 합니다.

이를 Page replacement입니다.

Replacement Algorithm

  • 어떤 frame을 빼앗아올지 결정해야함
  • page-fault rate을 최소화하는 것이 목표

Optimal Algorithm(가장 좋은 알고리즘 , 실제에선 불가능)

  • 미래의 요구되는 페이지를 모두 알고 있다고 가정
  • 가장 먼 미래에 참조되는 페이지를 replace
  • 다른 알고리즘의 성능에 대한 upper bound 제공

FIFO(First In First Out) Algorithm

  • 먼저 들어온 페이지를 내쫓음
  • FIFO anomaly: 메모리 프레임 늘려도 page fault가 더 발생할 수 있음

LRU(Least Recently Used) Algorithm

  • 가장 오래 전에 사용된 페이지를 내쫓음

LFU(Least Frequently Used) Algorithm

  • 참조 횟수가 가장 적은 페이지를 지움
  • 장기적인 시간 규모를 보기 때문에 LRU보다 page의 인기도를 좀 더 정확히 반영할 수 있음
  • 참조시점의 최근성을 반영하지 못함

LRU와 LFU 알고리즘의 예제 및 구현

  • LRU: linkedlist 형태(O(1))
    • 페이지가 참조되는 경우: list 맨 마지막으로 이동
    • page fault 발생시: list 처음 페이지를 삭제
  • LFU: heap 형태(O(log n))
    • 페이지 참조되는 경우: heap 재구성
    • page fault 발생시: heap 첫번째 삭제

다양한 캐슁 환경

  • 캐싱 기법
    • 한정된 빠른 공간(= 캐쉬)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐쉬로부터 직접 서비스하는 방식
  • 캐시 운영 시간 제약
    • 교체 알고리즘에서 작은 시간이 걸려야 함
    • Buffer/Web caching의 경우: O(1), O(log n)
    • Paging system인 경우: page fault인 경우에만 OS가 관여함. 페이지가 메모리에 존재하는 경우 참조시각등의 정보를 OS가 알 수 없음. O(1)인 LRU list 조작조차 불가능

Clock Algorithm

  • Clock Algorithm
    • LRU의 근사 알고리즘에서
    • NUR or NRU 로 불림
    • reference bit를 사용해서 교체 대상 페이지 선정
    • reference bit가 0인 것을 찾을 때까지 포인터를 앞으로 이동. bit가 1이었던 것은 0으로 바꾸면서 이동.
    • 한 바퀴 돌았는데 0이면 그때에는 replace
    • 자주 사용되는 페이지라면 second chance가 올 때 1
  • Clock Algorithm 개선
    • reference bit와 modified bit를 함께 사용
    • reference bit = 1 : 최근에 참조된 페이지(하드웨어가함)
    • modified bit = 1 : 최근에 변경된 페이지(I/O 동반하는 페이지)

Page Frame의 Allocation

  • Allocation problem: 각 프로세스에 얼마만큼의 page frame을 할당할 것인가?
  • Allocation 필요성: 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있음. Loop를 구성하는 page들은 한꺼번에 allocate되는 것이 유리(Loop를 구성하는 page가 3개인데 2개만 할당하면 지속적으로 page fault 발생)
  • Allocation scheme
    • Equal allocation: 모든 프로세스에 똑같은 갯수 할당
    • Proportional allocation: 프로세스 크기에 비례하여 할당
    • Priority allocation: 프로세스의 Priority에 따라 다르게 할당

Global vs. Local Replacement

  • Global Replacement(할당 하지않고 그때그때에 맞게 할당)
    • Replace시 다른 프로세스에 할당된 frame을 빼앗아 올 수 있다
    • FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용시에 해당
    • Working set, PFF 알고리즘 사용
  • Local replacement
    • 자신에게 할당된 frame 내에서만 replacement
    • FIFO, LRU, LFU 등의 알고리즘을 프로세스 별로 운영시

Thrashing

  • 프로세스 수행에 필요한 최소한의 page frame 수를 할당 받지 못한 경우 발생(너무 적은 페이지 할당)
  • Page fault rate 높아짐. CPU utilization이 낮아짐 ( 페이지 폴트로 인한 지속적인 IO발생)-> OS는 MPD(Multiprogramming degree를 높여야 한다고 판단 이유는 CPU가 놀고있어서) -> 다른 프로세스가 시스템에 추가됨 -> 프로세스 당 할당된 frame의 수가 감소 -> 프로세스는 page swap in/out으로 매우 바쁨 -> 대부분의 시간에 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
    • Thrashing을 방지. MPD를 결정

Working-Set Algorithm

  • Working-set 결정
    • Working set window를 통해 알아냄

PFF(Page-Fault Frequency) Scheme

  • page-fault rate의 상한값과 하한값을 둔다
  • page-fault rate이 상한값을 넘으면 frame을 더 할당
  • page-fault rate이 하한값 이하이면 할당 freme을 줄임

Page Size의 결정

  • Page size 감소시키면
    • 페이지 수 증가. 페이지 테이블 크기 증가
    • Internal fragmentation 감소. 필요한 정보만 메모리에 올라와 메모리 이용이 효율적