[운영체제] ep7) Virtual Memory

ㅁVirtual Memory(가상 메모리): m.m.에 프로그램의 일부만 남기고 나머지는 HDD에 적재

- 현대 시스템의 99%가 가상 메모리 시스템

 

※ 멀티 프로그래밍 레벨이 높을수록 좋은 시스템이다

멀티 프로그래밍 레벨: 메모리에서 동시에 실행되는 프로세스의 숫자

 

<VM기법의 프로그램 실행과정>

1. OS가 프로그램 조각(resident set)을 m.m.로 가져온다

- resident set: 프로그램 조각(Page들의 집합)

2. 필요한 프로그램이 m.m.에 없으면 interrupt 발생!

3. 필요한 프로그램을 가져오기 위해서 OS가 process를 blocked시킨다

4. OS가 HDD에 I/O 읽기 요청을 한다

5. HDD가 I/O 작업을 처리하는 동안 다른 프로세스가 디스패치된다

6. 아까 blocked된 프로세스를 다시 ready 상태로 바꾼다

 

 

ㅇThrashing(스레싱): 실행하는 시간보다 HDD Swap in-out 하는 시간이 더 걸리는 상황

- 개판으로 설계하지 않는 이상 실제로 잘 생기지는 않는다

ㅇPrinciple of Locality(지역성의 원리): 내가 필요한 함수들은 웬만하면 한 페이지 안에 다 있다

(ep6. 지역성의 원리 참고)

https://claremont.tistory.com/entry/%EC%BB%B4%ED%93%A8%ED%84%B0-%EA%B5%AC%EC%A1%B0-ep6-%EB%A9%94%EB%AA%A8%EB%A6%AC-%EC%BA%90%EC%8B%9C%EB%A9%94%EB%AA%A8%EB%A6%AC

[컴퓨터 구조] ep6) 메모리와 캐시메모리

 

 

 

VM에서도 똑같이 페이징과 세그멘테이션 기법을 사용한다

ㅇ페이징(Paging): 내용 상관없이 모두 동일한 크기로 짜름 - 관리 easy 

프로세스들은 각각의 Page Table을 가진다

 

virtual system에서는 logical address가 아닌 virtual address이다

vm에서의 page table entry

- presence bit: page가 m.m.에 있는지

- modify bit: page가 m.m.에 올라간 이후 변형이 됐는지

 

relocation

 

(프로그램 크기 big = page 크기 big = page table 크기 big)

 

 

[Two-Level Hierarchical Page Table]

k: 2^10 / M: 2^20 / G: 2^30

 

 

 

Address Translation for Hierarchical page table

 

 

 

 

역발상) presence bit = 1인 entry만으로 Page Table을 구성하자! -> 공간을 절약

ㅇInverted Page Table(역페이지 테이블): page table의 k번째 entry에는 k번째 page frame에 저장된 page에 대한 정보가 저장

- Page #을 hash function을 이용하여 변형시킨다

- 페이지 테이블의 크기가 항상 고정이다

 

 

[페이지 테이블에 들어있는 4가지]

➀ Page #

➁ PID

➂ Control bits: flag (e.g. valid, referenced)

➃ Chain pointer: hash function의 결괏값이 같은 entry들끼리 링크로 연결 (링크의 다음 위치에 대한 포인터)

 

 

<Inverted Page Table의 구조>

(Page Table의 시작주소가 그림에는 빠져있다)

e.g. 2350번 process의 33번 page가 12번 frame에 들어있다

 

 

 

 

m.m. 접근속도는 빠르지만, HDD의 접근속도는 느리다 그래서 나온 것이 바로 TLB 캐시

ㅇTLB(Translation Lookaside Buffer): Page Table Entry를 찾는데 위한 캐시

자주 사용하는 Page Table Entry를 TLB에 넣어둔다

 

Direct mapping과 Associative mapping과의 차이점 (TLB 캐시의 유무)

 

 

 

 

ㅇ세그멘테이션(Segmentation): 관련이 있는 함수를 고려해 짜름 - 관리 hard

Segment Table Entry

 

Address Translation in Segmentation

 

근데 너무 비효율적이다! 그래서 VM에서는 Segmentation 기법을 잘 안 쓰고 Paging과 Segmentation을 합친 기법을 사용한다

 

 

ㅇCombined Paging and Segmentation: 페이징과 세그멘테이션을 합친 기법

관련이 있는 함수를 고려해 짜름 + Paging 기법으로 관리를 한다 (각각의 Segment들을 Page로 나눈다)

- 페이징의 장점: external fragmentation x

- 세그멘테이션의 장점: 모듈화 ㅇ, sharing ㅇ, protection ㅇ

 

Length와 Segment Base의 의미가 다름을 유의하자

 

Address Translation

 

 

 

ㅇFetch Policy: Page를 HDD에서 m.m.로 가져오는 정책

2가지 방법이 있다

1. 필요한 Page만 가져온다 - 거의 모든 시스템에서 대부분 사용되는 방식이다

2. 주변 Page까지 미리 다 가져온다 - Disk 스케줄링에서 주로 사용되는 방식이다

 

ㅇReplacement Policy: 캐시 or m.m.에서 데이터 블록을 교체하는 정책

OPT, LRU, FIFO, CLOCK 4가지 방법이 있고 대부분은 LRU나 CLOCK의 변형을 사용한다

 

상황)

 

 

1. OPT(Optimal Policy): 앞으로 가장 오랫동안 사용하지 않을 Page를 버린다

말 그대로 가장 이상적인 최적의 방식이다

Page fault 3개

 

하지만 어떤 Page를 언제 사용할지 알아낼 방법은 존재하지 않는다

따라서 구현은 불가능하고, 우리는 이것을 이상향의 기준점으로 삼자

 

 

2. LRU(Least Recently Used): 최근에 사용하지 않은 Page를 버린다

Page fault 4개

 

장점: Page fault 수 ↓

단점: 2가지 오버헤드 발생

- 공간적인 오버헤드: Page당 시간을 표시하는 정보가 필요(최소 4byte)

- 시간적인 오버헤드: Page 전부를 비교(탐색시간 多)

 

 

3. FIFO(First-In First-Out): 그냥 순서대로 RR 느낌

Page fault 6개

 

장점: 오버헤드 X

단점: 최악의 성능(Page fault 수 ↑)

 

※ FIFO Anomaly(a.k.a. Belady's Anomaly): Page frame이 늘어나면 Page fault 수가 줄어야 하지만, FIFO 방식은 오히려 Page fault 수가 늘어날 수 있다

(이 현상을 Belady가 발견)

 

 

4. CLOCK(Clock Policy): Page당 use bit 사용

use bit는 1bit이므로 공간적 오버헤드가 4byte에 비해 1/32만큼 작다

use bit 초기값을 0으로 설정하고, Page가 사용되면 use bit를 1로 바꾼다

Page fault 5개

 

 

 

성능은 LRU와 FIFO의 중간성능을 보인다

Comparison of Fixed-Allocation, Local Page Replacement Algorithms

 

 

 

 

 

 

ㅇResident Set Size(RSS): Page들의 집합 (프로그램 조각이라 생각하면 편하다)

1. Fixed-Allocation: 고정된 개수의 프레임 할당

- Local Scope: Page를 버릴 때 내 Page를 버린다 (적절한 기법: LRU)

 

2. Variable-Allocation: working set만큼만 할당

※ working set: 실행할 때 필요한 Page들의 집합

- Local Scope: Page를 버릴 때 내 Page를 버린다 (적절한 기법: LRU)

- Global Scope: Page를 버릴 때 다른 사람 Page를 working set에 맞춰 버릴 수 있다 (적절한 기법: CLOCK)

 

Typical Graph of Working Set Size

 

 

 

 

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

[UNIX와 Windows의 Virtual Memory 관리법]

ㅁUNIX: 2가지 메모리 관리 메커니즘이 있다

1. User process를 다루는 메커니즘: Page-Based Virtual Memory System

+ 페이지 테이블은 TLB를 사용한 Dynamic Address Translation에 기반한다

 

2. 커널을 다루는 메커니즘: Kernel Memory Allocator

커널의 경우 Dynamic Partitioning을 사용한다 (변형된 형태의 Buddy System)

 

 

Variable-Allocation의 Global Scope 시스템 - Two-Handed CLOCK 기법

ㅇTwo-Handed CLOCK Page Replacement Algorithm

use bit 대신에 reference bit 라는 이름을 사용한다

"Two-Handed" 2개의 바늘을 사용한다

- fronthand: reference bit를 0으로 reset한다

- backhand: 교체할 페이지들(reference bit = 0인 페이지들)을 Paged-Out list에 쌓아둔다

backhand는 fronthand 뒤를 따라가고 fronthand는 적당한 속도를 유지해야 한다

 

장점: Paged-Out lits로 Page를 교체하는데 시간 소요 x

 

 

 

ㅁWindows: Page-Based Virtual Memory System

Variable Allocation의 Local Scope 시스템을 사용 - LRU 기법

 

working-set Based Memory Management

- m.m.가 가득 차면, 활성 프로세스의 RSS가 성장한다

- m.m.가 거의 비면, 최근에 사용되지 않은 Page가 버려진다

 

 

 

 

 

 

 

 

 

 

참고 및 출처: Operating Systems: Internals and Design Principles(William Stalling), Operating System Concepts(Silberschatz, Abraham)