[운영체제] Chapter 10. Virtual Memory

경희대학교 허선영 교수님의 운영체제 수업을 기반으로 정리한 글입니다.

 

Chapter Objectives

• Virtual Memory에 대해 정의하고, 이점을 알아본다.
• demand paging을 이용하여 어떻게 pages가 memory 내에 load되는지 설명
• FIFO, Optimal, and LRU page replacement algorithms 적용
• process의 working set과 이것이 program locality와 무슨 연관성이 있는지 설명
• Linux, Windows 10, Solaris가 어떤 방식으로 virtual memory를 관리하는지 설명

 

Background

• code는 실행되기 위해 memory에 위치해야 함 -> 그러나, 전체 프로그램은 거의 쓰이지 않음
  • error code, unusual routines, large data structures
• Entire program의 code를 memory에 load할 필요는 없다!

- Virtual Memory

• physical memory에서의 user logical memory separation을 포함
• 프로그램의 일부가 execution을 위해 memory에 위치
• 이 개념을 통해서 logical address space -> physical memory보다 훨씬 커질 수 있음 -> program의 크기가 더이상 physical memory에 의해 제한되지 않음

- Benefits

• Address space -> several processes에 의해 공유될 수 있음 
  
  • system libraries
  • shared memory를 process의 virtual memory로 취급하여, 해당 region을 공유
• 더 많은 프로그램을 동시에(concurrently) 실행할 수 있음
  • 각 program이 실행되는 동안, 더 적은 메모리 공간을 차지
  • CPU uilization(활용도)와 throughput(처리율) 상승
• 더 효율적인 process 생성
• Less I/O needed to load or swap processes

 

- Virtual Address Space 

• Virtual Address Space: process가 memory에 저장되는 방식의 logical view
  
  • address 0부터 시작해서, 공간의 끝까지 연속적으로 이어진 주소
  • MMU -> logical을 physical로 mapping해야 함
• Virtual memory 구현 방안
  • Demand Paging
  • Demand Segmentation

 

Demand Paging

1. Basic Concepts

• page가 필요할 때만, memory로 bring -> page가 필요할 때: CPU 접근
  • invalid refernce -> abort
  • not-in-memory(page fault) -> bring to memory
•  Swapping과 유사한 방식
  • Lazy Swapper: page가 필요하지 않으면, 해당 페이지를 절대로 memory로 swap하지 않음
  • page를 다루는 swapper -> pager
  • swapping - process 단위
  • demand paging - page 단위

 

- Demand Paging with Valid-Invalid Bit

• page table의 각 entry에 valid-invalid bit 추가
  • v - in memory(memory resident)
  • i - not in memory
  • address translation 과정에서, valid-invalid bit i -> page fault

- Handling Page Fault

1. page table에 page가 존재 X(page로의 첫 번째 접근은 반드시 page fault) 
   • 가장 처음 접근할 때 
2. os에 page fault trap 바생
   • 동작하던 process의 PCB를 memory에 저장
3. 다른 page table 확인
   • invalid reference -> abort (프로세스 중지)
   • 단순히 memory에 위치하지 않는 경우
4. page를 찾아서, 해당 page를 저장할 Free Frame을 찾음
5. page를 frame으로 swap - via scheduled disk operation
6. page table 수정 -> 해당 page가 이제 memory에 위치한다는 것을 알림
   • validation bit = v
7. page fault를 발생 시킨 instruction으로 복구

 

- Pure Demand Paging

• 필요한 것들만 가지고 오는 것
• 프로그램이 처음 시작할 때, 지금 필요한 게 아니면 아무것도 가져오지 않음 -> 처음 시작할 때부터 page fault 발생
• 속도는 느리지만, 메모리 절약

 

2. Free-Frame List

• Free-Frame List: a pool of free frames -> secondary storage로부터 main memory에 필요한 page를 불러오기 위해 필요한 free frames의 목록(page fault 상황)
  • request의 조건을 만족하는 free frames의 목록
• os는 보통 zero-fill-on-demand 방식으로 free frame을 할당함
  • 할당 이전에 frame 내부를 0으로 초기화 -> for security
• system이 시작되면, all available memory -> free-frame list에 위치ㅏ

 

3. Performance of Demand Paging

• Page Fault Rate(0 <= p <= 1)
  
  • p = 0 -> no page faults
  • p = 1 -> 모든 접근이 fault
• Effective Access Time (EAT)
  • EAT = (1 - p) x memory access + p x page fault time 
    • page fault time: (page fault overhead + swap page out + swap page in)

 

Copy-on-Write

• 과거에는 child processes를 생성할 때, parent process의 address space를 복사함 -> 공간 낭비라 판단
• 이때 사용할 수 있는 기술이 copy-on-write
• copy-on-write: parent & child processes가 처음에 same pages를 공유할 수 있게 함
• 공유하는 process 중 하나가 특정 page에 modify 시도 -> 해당 page의 copy version에 수정 적용 -> 이후 나머지 processes 연결

 

Page Replacement

• Page Replacement: memory에 위치한 page 중 실제로 쓰이지 않는 page를 page out
  
  • Algorithm 
  • Performance - minimum number of page faults
• overhead를 줄이기 위해 modify or dirty bit 사용
• same page may be brought into memory several times

1. Basic Page Replacement

1. 필요한 page의 위치를 disk에서 탐색
2. Free frame을 탐색
   • free frame이 있다면 -> 해당 frame 사용
   • free frame이 없다면 -> page replacement algorithm을 기준으로 victim frame을 선정
   • dirty bit가 true인 경우(수정된 경우) -> victim frame을 disk에 저장해줘야 함
     • 이전에 수정된 전적이 있기 때문에, disk에는 해당 변경 사항이 아직 적용되지 않음 -> 교체되기 전에 수정된 사항 저장!!
3. 필요한 page를 새로 비운 free frame에 올림, 이에 따라 page, frame table 수정
4. trap을 발생시킨 instruction으로 복귀

• page fault가 발생하고, free frame에 존재하지 않는 경우 -> 두 번의 page transfer(page in & page out)가 발생 -> page fault 해결 시간을 증가시킴, 접근 시간도 증가

- Page Replacement Algorithms

• Frame-allocation algorithm: 각 process에 얼마나 많은 frame을 줄 것인지 결정
• Page-replacement algorithm: 어떤 frame이 교체될 것인지 결정 
  • lowest page-fault rate -> 첫 접근과 재접근의 경우 모두
• algorithm의 평가 -> reference string에서의 실행 -> 해당 string에서의 page faults number를 계산 
  • reference string: memory 접근의 특정 string

 

2. FIFO Page Replacement

• page가 교체되어야 할 때, 가장 오래된 page가 교체
  • FIFO queue를 사용하여 age를 tracking
• 3개의 frame이 존재하는 예시
• 7, 0, 1, 2, 0, 3 -> page number

• 1, 2, 3, 4, 5, 1, 2, 3, 4, 5
  • 3개의 frame일 때보다, 4개의 page일 때 page fault가 더 많이 발생 -> Belady's Anomaly(변칙)
  • 더 많은 memory size를 부여할 때, 성능이 오를 것이라 예상하지만, 그렇지 않은 경우도 존재한다.

 

3. Optimal Page Replacement

• 가장 오랜 시간 동안 쓰이지 않을 page를 교체
• 미래를 알 수는 없기 때문 -> algorithm 성능 비교용

 

4. LRU Page Replacement

• Least Recently Used
• 가장 오랜 시간 동안 쓰이지 않은 page를 교체
  
  • Use past knowledge

• Better than FIFO, worse than OPT

- Counter implementation

• 모든 page table entry counter를 가짐 
• page reference -> CPU의 clock을 counter로 copy -> 가장 작은 value의 counter를 가진 page가 교체됨
• counter value를 entry마다 모두 저장 -> stroage 측면에서 별로

- Stack implementation

• double linked stack에 page numbers 저장
  • page reference -> 해당 page number를 top으로 이동
  • 6개의 pointer change
• stack이 가득 찼을 때, 가장 아래에 위치한 item을 제거 -> No search for replacement

 

4. LRU Approximation Algorithms

• page reference는 매우 빈번하게 발생 -> counter와 stack을 이용해서 매번 기록하기엔 성능적 비용이 너무 큼
• 작은 시스템에서는 hardware를 추가하여 hardware support 이용, but 일반적인 경우에는 가성비가 떨어짐
• 따라서, LRU에 근사한 LRU approximation algorithm 사용

- Reference bit

• page table의 각 entry에 reference bit 추가
  • 초기값 0
  • page reference -> set to 1
  • 교체는 reference bit가 0인 page 중에서 결정 
• starvation 발생 가능성 

- Second-chance algorithm

• FIFO + hardware-provided reference bit
  • FIFO 순서에 따라 page 검색
  • reference bit = 0 -> page replacement
  • reference bit = 1 
    • reference bit을 0으로 clear
    • give one more chance
    • 다음 검사 때는 교체의 대상이 될 수 있음

 

Allocation of Frames

1. Gloval vs. Local Allocation

- Global Replacement

• 메모리 상의 모든 frames에서 replacement frame 선택
• 다른 process로부터 frame을 뺏어올 수 있음 -> preemption
  • process execution time이 매우 커질 수 있음
  • 메모리 사용 효율은 일반적으로 global replcement가 더 좋음

- Local Replacement

• 메모리 상의 process 자신에게 할당된 frame 중에서만 선택
  • 일관된 프로세스 당 성능
  • 그러나, memory 사용 효율이 좋지 않을 수 있음

Thrashing

1. Cause of Thrashing

• proess가 충분한 수의 page를 memory에 적재하지 못하면, page-fault rate가 매우 높아짐
• 낮은 CPU utilization(이용률) -> os는 multiprogramming의 정도(MPD; multi-programming degree)를 높여야 한다고 판단  -> 또다른 process가 system에 추가
• process가 증가할수록 free frame의 개수는 감소 -> 결국 모든 frame이 가득 차게 됨 -> busy swapping
• swapping -> page in/out는 disk I/O 작업으로 CPU를 사용하지 않는 작업 -> 해당 작업이 많아질수록 CPU utilization은 떨어짐
• 이렇게 busy swapping으로 인해 cpu 성능이 떨어지는 현상 -> Thrashing

- Locality Model

• process가 실행될 때, locality에서 다른 locality로 migration(이주)
• localities may overlap
• reason why does thrashing occur -> Σ size of locality > total memory size
  • 접근하는 memory size -> demand paging(?)
• Local or Priority page replacement -> thrashing 효과 감축

2. Solution

- Working-Set Model

• WSS_i(Working Set Size of Process P_i) = 가장 최근 Δ에서 접근된 page의 총 개수
  • Δ가 너무 작으면 -> locality를 충분히 나타내지 못함
  • Δ가 너무 크면 -> 다른 locality까지 overlap해버림
  • Δ = infinite -> 전체 프로그램을 포함

-> D: demand frame의 개수

-> locality의 근사치

 

• if D > m(available frame) -> thrashing

- Page-Fault Frequency

• Page-Fault Frequency(PFF): 허용 가능한 PFF & local replacement policy 설정
  
  • actual rate too low -> process에서 frame 할당 해제
  • actual rate too high -> process에 frames 할당

 

 

Allocating Kernel Memory

• 보통 free-memory pool로부터 할당됨 
  • kernel은 다양한 size를 가진 data structure의 memory를 요청
  • 몇몇 kernel은 contiguous해야 함- ex) device I/O (DMA; Direct Memory Access)

Memory Pool?
- fixed size block을 할당 
- malloc & new -> Memory Fragmentatiotn 유발 -> performance 문제로 실시간 시스템에서 사용 불가능
- memory pool 방식은 동일한 사이즈의 memory blocks를 미리 할당해 놓는 방법으로 이를 해결
- 응용 프로그램은 핸들에 의해서 표현되는 blocks를 할당하고, 접근하고, 해제할 수 있음

고정 메모리 풀 vs 가변 메모리 풀
- 고정 메모리 풀: 같은 크기를 할당하기 때문에 internal fragmentation 발생 X, 미리 할당받은 공간에 있는 메모리를 할당 및 해제하기 때문에 external fragmenation 발생 X

https://sypdevlog.tistory.com/333

 

• 이런 free memory를 관리하는 두 가지 방법 존재

1. Buddy System Allocator

• physically-contiguous한 pages -> 고정된 크기의 segment로 분할
• power-of-2 allocator에 의해 메모리 할당 -> 2의 제곱 단위로 memory block 관리
• 초기의 모든 memory block은 free 상태, 각각의 block은 binary tree 구조로 연결 - leaf node는 가장 작은 available block
• process request memory -> 해당 사이즈를 충족하는 가장 작은 available block 탐색 -> 찾은 block이 요청한 블록 사이즈보다 크면, block은 두 개의 buddy blocks로 나뉨

- Advantage

• release 이후에, buddy와 다시 합쳐 larget size chunkg로 복구하기 용이
• external fragmentation을 줄일 수 있음

- Disadvantage

• internal fragmentation -> 257 bytes가 필요한 경우 512 bytes를 할당해야 함

- Example

• 256chunk available, kernel requests 21KB

 

2. Slab Allocator

• Slab: 하나 이상의 연속적인 pages
• Cache: 하나 이상의 slabs를 포함
  • unique kernel data structure마다 single cache 존재 -> 각 cache는 objects로 채워짐 - slab의 크기에 맞는 수의 객체 생성
  • cache 생성 -> 객체는 초기에 free 상태로 초기화
  • kernel data structure가 필요하면, 객체에 저장 -> used 상태로 초기화

- State of Slab

• Full: slab의 모든 object가 used
• Empty: slabe의 모든 object가 free
• Partial: free, used 상태 object를 모두 포함
• partial에 먼저 할당 -> partial이 없음 -> empty에 할당 -> empty가 없음 -> 새로운 slab이 contiguous physical pages에서 할당되어 cache에 assign -> 해당 empty slab에서 할당

- Benefits

• no fragmentation
  
  • 자료구조에 맞춰서 설계 -> 딱 요청된 자료구조 만큼의 공간이 할당
• fast memory request
  • 할당/해제가 자주 이루어질 때 효과적 -> 특히 kernel에서 빈번함
  • 요청할 때 마다 memory 할당/해제하는 것이 X
  • 미리 cache에 할당해놨다가 필요시 제공
  • 메모리 할당 해제 X -> cache에 돌려놓음

- Slab Allocator in Linux

• Example: struct task_struct
• New task 생성 -> cache로부터 new struct 할당
  • 기존에 존재하던 free struct task_struct 사용

---

참고자료

• https://wpaud16.tistory.com/entry/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-Demand-paging-%EC%9A%94%EA%B5%AC-%ED%8E%98%EC%9D%B4%EC%A7%95-page-fault%EB%9E%80

운영체제 Demand paging ( 요구 페이징, page fault란? )

• https://velog.io/@zehye/%EA%B0%80%EC%83%81%EB%A9%94%EB%AA%A8%EB%A6%ACVirtual-Memory%EC%99%80-%EC%9A%94%EA%B5%AC%ED%8E%98%EC%9D%B4%EC%A7%80Demand-Paging

가상메모리(Virtual Memory)와 요구페이지(Demand Paging)

• https://4legs-study.tistory.com/53

[OS/운영체제] 페이지 교체 (Page Replacement) - (1)

• https://gofo-coding.tistory.com/entry/Page-Replacement

Page Replacement

• https://velog.io/@anjaekk/OS-Thrashing

[OS] 스레싱(Thrashing)과 해결방법

• https://velog.io/@youngeui_hong/%EC%BB%B4%ED%93%A8%ED%84%B0-%EC%8B%9C%EC%8A%A4%ED%85%9C-%EB%8F%99%EC%A0%81-%EB%A9%94%EB%AA%A8%EB%A6%AC-%ED%95%A0%EB%8B%B9-Buddy-System%EC%9D%98-%EA%B0%9C%EB%85%90%EA%B3%BC-%EA%B5%AC%ED%98%84

[컴퓨터 시스템] 동적 메모리 할당 - Buddy System의 개념

• https://velog.io/@dandb3/OS-Slab-Allocation

[OS] Slab Allocation