CS/운영체제

[공룡책🦖] ch10 Virtual Memory

설기똥꼬 2023. 7. 27. 12:25

본 포스팅은 공룡책으로 불리는 Abraham Silberschatz, Peter B. Galvin, Greg Gagne의 『Operating System Concept 10th』 기반으로 정리한 글입니다.

Background

가상메모리

  • 어떤 프로세스의 실행을 실제 메모리에 다 올리지 않아도, 물리 메모리보다 프로세스의 메모리가 더 커도 실행 가능하도록 할 수 있도록 하는 기술
  • 가상의 메모리로 생각하면 물리 메모리에서 논리 메모리 분리 가능
  • 매우 효율적인 메커니즘
  • 사용하지 않는 메모리는 서브 메모리(SSD, HDD)에 업로드 

 

가상 주소 공간

  • 논리 프로세스 메모리 구조
  • 연속적인 메모리에 존재

 

Page Sharing

  • 두 개 이상 프로세스에서 파일과 메모리 공유 쉬움
  • 공유하는 파일과 메모리를 shared page에 두고 사용 

 

 

Demand Paging

보조기억장치에서 메인메모리로 프로세스를 실행하면서 로딩하는 과정이 필요한데, 사용하지 않는 것까지 모두 올리는 것은 비효율적이다. 

그래서 모든 메모리를 올리는 대신 페이지 단위로 잘라서 올린다.

Demand paging을 통해 각각의 페이지를 올리는 시점을 정해 요청할 때마다 올리도록한다.

 

 

Demand-page 이슈

Demand paging은 유용하지만 많은 것을 고려해야한다. Demand될 때 어떻게 관리할 것인가?

  • 어떤 프로세스가 실행 중일 때는 필요한 자원이 메인 메모리나 보조기억장치에 있어야함
  • Demand paging에서의 유효성 확인 (메인에 있는지 보조기억장치에 있는지)
    • Vaild : 해당 페이지가 유효하고 메모리에 존재함
    • Invalid : 해당 페이지가 유효하지 않거나 보조기억장치에 있음

 

 

Page Fault

아직 메모리에 로딩이 안된 페이지에 접근 요청

  • 내부 테이블 체크하여 유효한 페이지인지 확인
  • 만약 Valid라면 페이지 제공
  • 만약 Invalid라면 페이지 메모리에 로드
    • 비어있는 프레임(free frame) 발견하여 HDD에 있는 페이지를 로드해야함
    • 내부 테이블이나 페이지 테이블에 해당 페이지가 메모리에 있다고 표시 후 명령 재시작

 

 

Pure demanding page

요청하지 않으면 페이지를 메모리에 올리지 않음

  • 메모리에 페이지 없는 채로 프로세스 실행
  • 처음 메인 메모리에 아무것도 없으므로 첫번째 요청은 무조건 page fault 발생

 

참조 국부성 (Locality of Reference)

  • 어떤 프로세스의 각 명령어가 여러 개의 페이지를 접근한다면 multiple page faults 일으킬 수 있음
  • 다행히 통계적으로 이런 경우가 드물며, 특히 메모리 관점으로 봤을 때 국부성(지역성)이 있음

 

 

Hardware Support to Demand Paging

  • Page table
    • 페이지 테이블을 사용하기 위해 해당 페이지가 저장된 실제 물리 메모리 주소를 알아야함
    • valid or invalid인지 마크할 수 있는 능력 보유 (dirty bit 사용해서 확인)
  • Secondary memory (swap space)
    • 별도의 장치 사용해서 페이징 스왑을 위해 세컨더리 메모리 활용

 

 

Free Frame List

Page Fault가 발생할 때, OS는 보조기억 장치에서 메모리로 요구되는 페이지를 가져온다.

Page Fault를 해결하기 위해 OS는 Free Frame list를 유지한다.

Free Frame list는 이러한 요청을 만족하는 Frame list의 pool이다.

 

 

Demand Paging Performance

page fault가 발생하면 실행 중인 프로세스를 대기큐에 보내서 페이지 스왑 완료시 프로세스를 재시작하도록 한다.

페이징 아웃, 인 과정에서 위치가 정확해야하고, 프로세스별로 페이징 테이블을 관리해야 한다.

  • Demand-paging memory에 효율적으로 접근하는 시간을 실행하는 방법?
  • ma : memory access time
  • p : probability of a page fault
    • EAT = (1 − 𝑝) × 𝑚𝑎 + 𝑝 ∗ 𝑝𝑎𝑔𝑒 𝑓𝑎𝑢𝑙𝑡 𝑡𝑖𝑚𝑒 
  • page fault를 서비스하는데 필요한 시간? (3가지 주요 Activities) 
    • Service the page-fault interrupt
    • Read in the page
    • Restart the process
  •  

 

 

Copy-on-Write

  • Read만 할 때 페이지의 변경 작업이 이뤄지지 않으므로 CRUD 과정 중 R할 때만 Copy
  • shared page로 활용하고 CUD 할 때만 Copy 진행 → fork

 

 

 

Page Replacement

  • No free frame의 경우 어떤 일이? ( == 페이지를 메인 메모리에 로드할 공간이 X)
    • 멀티프로그래밍의 차수를 늘려나가면 over-allocating memory 상태 
    • 페이지를 in 시키기 위해서는 메인 메모리에 올라간 페이지를 제거해서 공간을 만들어야함

 

 

Page Replacement

  1. Page Fault 과정에서 free frame이 없다면, 희생자를 선정하는 알고리즘에 의해 제거할 페이지를 선정
  2. 새로운 페이지를 메모리에 올리고 페이지와 프레임 테이블을 변경
  3. page fault + page replacement 가 끝나면 프로세스는 작업을 재개함

 

 

Page Replacement의 두 가지 문제

  • Frame-allocation algorithm : 희생자 선정하는 알고리즘  
  • Page-replacement algorithm : 프로세스마다 몇 개의 프레임을 할당 

보조 기억 장치에 I/O를 하는 비용은 비싸며, demand paging의 성능이 조금만 좋아져도 시스템 효율이 굉장이 높아진다. 

 

 

 

Page Replacement algorithm 평가기준

  • page fault의 비율을 낮춤
  • reference string (참조 문자열) : 메모리 레퍼런스
  • the number of page faults minimize
  • 프레임 많을수록 pf 줄어들것

 

 

FIFO Page Replacement

  • 가장 간단한 알고리즘
  • 가장 오래된 페이지를 대체
  • Belady’s Anomaly
    • 할당된 프레임 수가 증가함에 따라 Page Fault 비율 증가

 

 

Optimal Page Replacement

  • 가장 적은 Page Fault 비율 → Belady algorhtim으로 고통 X
  • 앞으로 사용 안할 거 같은, 오랫동안 사용안할 거 같은 페이지(OPT)를 내보냄
  • 최적화는 미래 knowledge가 필요 → 다른 연구와 비교용으로 사용

 

 

LRU Page Replacement (Least Recently Used)

  • 최근에 젤 안사용된 페이지를 사용
  • 각 페이지 마지막으로 사용한 기록을 바탕으로 젤 오래된 페이지 찾기
  • LRU Policy : 효율 좋고 자주 사용
    • 프레임이 언제 마지막으로 사용되었는지 알아야함 (알려면 복잡 ..)
    • 하드웨어 지원받으면 좋은데 쉽지 않음
    • Belady anomaly 겪을 수 없음
  • LRU 구현
    • Counter Implementation (페이지 쓸떄마다 카운트 갔다오거나 clock을 복사)
    • Stack Implemenation (페이지 넘버를 스택에 넣고 없어질때까지)
  • LPU Approximation
    • HW 지원 필요, 많은 OS가 reference bit 제공
    • reference bit : 페이지 reference할 때마다 reference bit 0으로 치환 (원래 1)

 

Second-Chance Alogorithm

  • LRU 컨셉의 알고리즘 중 하나
  • FIFO 알고리즘 + reference bit 
    • r bit 0이면 페이지 교체
    • r bit 1이면 second chance 줌 (FIFO에 의해 다음 페이지 선택)
    • r bit을 가지고 reset 가능

 

 

Allocation of Frames 

N개의 프로세스가 있을 때 M개의 프레임이 있다면, 각 페이지에 얼마만큼 배정해야할까?

 

분배 (Equal vs Proportional)

  • Equal allocation : 모든 프로세스에게 동일한 프레임을 할당
  • Proprtional allocation : 프로세스 사이즈가 큰 경우에게 더 많이 할당

 

교체 범위 (Global vs Local)

  • Global replacement : 프로세스에게 할당된 프레임 중 희생자를 정해서 교체
  • Local replacement : 프로세스들이 사용하고 있는 모든 프레임 중 희생자를 선정하여 교체

 

 

Thrashing

Demand paging으로 가상 메모리를 사용하면 HW 메모리에 큰 프로그램을 만들 수 있다. 그러나  어떤 프로세스가 페이지 스와핑(page in and out) 작업으로 본 일을 해야하는 프로세스가 멈춰있을 수 있다.

충분한 페이지가 없다면 page-fault 비율이 매우 높아질 것이다. 이에 따라 degree of multiprogramming 또한 높아지며 CPU 사용량이 올라가는데, 어느 순간 Thrashing이 발생하면서 CPU 활용이 떨어지게 된다. 

이 현상이 발생한 경우 방안으로 Working-Set Model이 있다.

 

Working-Set Model

  • based on the assumption of locality
  • working-set window를 델타 크기만큼 지정하고 해당 working set 안으로 들어오는 page 대신, 그 밖에 있는 page를 victim으로 삼으면 page fault가 줄 것
    • working-set : 최근 페이지 레퍼런스
  • 페이지가 active use라면 working set에 있음 
  • 더이상 사용 안하면 working set에 drop