[운영체제] 9. Virtual Memory

물리적인 메모리 변화는 OS가 관여하지 않지만 Virtual Memory 변화는 OS가 관여한다!

 

* 대부분 paging 기법을 사용한다고 가정

Demand Paging

요청이 있으면 그 때 page를 메모리에 올리는 것

- I/O 양의 감소 (한정된 메모리 공간을 더 의미있는 정보로 채울 수 있음)

- Memory 사용량 감소

- 빠른 응답 시간

- 더 많은 사용자 수용

 

invalid한 page는 disk(backing store)에 올라가 있는다

 

Valid / Invalid bit의 사용

* invalid란?

- 사용되지 않는 주소 영역인 경우

- 페이지가 물리적 메모리에 없는 경우

 

- 처음에는 모든 page가 invalid bit로 초기화

- address translation 시에 invalid bit이 set되어 있으면 page fault 

-> [trap] CPU가 OS로 넘어감

-> [page handler] OS가 fault난 page를 physical memory에 올림

 

Page Fault

1) invalid page 접근 > MMU가 trap 발생(page fault trap)

2) kernel mode 진입 > page fault handler 작동

3) page fault 처리

(1) invalid reference 체크 (bad address, protection violation)

-> invalid하면 process abort

(2) empty page frame 할당하기 > 만약 빈 곳 없으면 쫓아냄(replace)

(3) 해당 page를 disk -> memory로 읽어옴

- disk I/O 끝날 때까지 CPU preempt(block)

- page table entry 기록 / valid bit 표시

- ready queue에 process 넣기 -> 나중에 dispatch

(4) 해당 process가 CPU를 잡고 running

(5) 중단되었던 instruction 재개

 

 

Performance of Demand Paging

 

Page replacement

3-2)에서 비어있는 frame이 없는 경우 어떤 frame을 빼앗아 올 지 결정해야 함

- 곧바로 사용되지 않을 page를 쫓아내는 것이 좋음

- 동일한 page가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있음

 

Replacement Algorithm

- page-fault rate를 최소화하는 것이 목표 > 주어진 page reference string에 대해 page fault를 얼마나 내는지 조사

 

 

Offline - Optimal Algorithm

* 미래의 참조를 알고 있다는 가정 하에 진행(offline algo) -> 실제로는 사용 X

MIN(OPT) : 가장 먼 미래에 참조되는 page를 replace

 

* 다른 알고리즘의 성능에 대한 upper bound 제공(Belady's optimal algorithm, MIN, OPT 등으로 불림)

 

FIFO Algorithm

FIFO anomaly(belady's anomaly) : more frames != less page faults

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

 

LRU (Least Recently Used) Algorithm

가장 오래 전에 참조된 것을 지움

 

LFU (Least Frequently Used) Algorithm

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

여러 개 있을 경우 1) 랜덤 2) 가장 오래전에 참조된 page 지운다

 

* 장점- LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영

 

* 단점- 참조 시점의 최근성을 반영하지 못함

- LRU 보다 구현이 복잡함

 

다양한 Caching 환경

한정된 빠른 공간(cache)에 요청된 데이터를 저장해 두었다가 후속 요청 시 cache로부터 직접 서비스하는 방식

- paging system, cache memory, buffer caching, web caching 등 다양한 분야에서 사용

 

* replacement algorithm의 시간 제약

- buffer / web caching : O(1) ~ O(logn)까지 허용

- paging system

1) page hit : 주소 변환 과정에서 OS가 관여하지 않음 (OS가 접근 시간 알 수 없음 -> LRU, LFU 사용 불가능)

2) page fault : I/O 발생하기 때문에 OS에게로 CPU 제어권 넘어옴

 

Clock Algorithm

LRU의 근사 알고리즘 (Second change algorithm / NUR not used recently / NRU not recently used

1) reference bit을 사용해서 교체 대상 페이지 선정(circular list)

2) reference bit이 0인 것을 찾을 때까지 포인터 앞으로 이동

3) 이동 중 reference bit 1은 모두 0으로 변경

4) 한 바퀴 되돌아와서도(second chance) 0이면 그때는 replace

5) 자주 사용되는 page라면 second chance 시 1일 것 (HW)

 

* 개선

modified bit이 0인 것을 우선해서 쫓아냄

- reference bit와 modified bit(dirty bit)을 함께 사용

- reference bit = 1 : 최근에 참조된 페이지

- modified bit = 1 : 최근에 변경된 페이지(I/O 동반) -> 쫓아내기 전에 backing store에 반영해야 함

 

Page frame allocation

각 process에 얼마만큼의 page frame을 할당할 것인가?

1) 메모리 참조 명령어 수행 시 최소한 할당되어야 하는 frame의 수가 있음 (명령어, 데이터 등 여러 페이지 동시 참조)

2) loop를 구성하는 page들은 한꺼번에 allocate되는 것이 유리함

 

Allocation scheme

1) Equal allocation : 모든 프로세스에 똑같은 개수 할당

2) Proportional allocation : 프로세스 크기에 비례하여 할당

3) Priority allocation : 프로세스의 priority에 따라 다르게 할당

 

Global vs Local replacement

1) Global replacement

- 다른 process에 할당된 frame을 빼앗아 올 수 있음

- FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용 시 해당

- Working set, PFF 알고리즘 사용 시 알아서 할당

 

2) Local replacement

- 자신에게 할당된 frame 내에서만 replacement

- FIFO, LRU, LFU 등의 알고리즘을 process 별로 운영시

 

Thrashing

프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당받지 못한 경우

1) page fault가 매우 빈번하게 발생

2) low CPU utilization

3) OS는 MPD(multiprogramming degree)를 높여야 한다고 판단

4) 또 다른 프로세스가 시스템에 추가됨 (higher MPD)

5) 프로세스 당 할당된 frame의 수가 더욱 감소

6) 프로세스는 page의 swap in / swap out으로 매우 바쁨

7) 대부분의 시간에 CPU는 한가함

8) low throughput

Thrashing Diagram

 

Working-Set Algorithm

* Locality of reference

- 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다

- 집중적으로 참조되는 해당 page들의 집합을 locality set이라 함

 

* Working-set model

locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합

- process의 working set 전체가 메모리에 올라와 있어야 수행되고, 그렇지 않을 경우 모든 frame을 반납한 후 swap out(suspend)

- thrashing을 방지

- multiprogramming degree를 결정

 

* Working-set의 결정

time interval 사이에 참조된 서로 다른 페이지들의 집합

- working set window를 통해 알아냄 (과거 delta 시간 동안 참조된 page = working set window)

-> working set에 모두 속한 page는 메모리에 유지해주고, 속하지 않은 애들은 모든 frame 반납 후 suspend

(참조된 page를 delta 시간만큼만 유지하고 버림)

 

* algorithm

1) process의 working set size 합 > page frame의 수

- 일부 process를 swap out 시켜(MPD 줄임) 남은 process의 working set을 우선적으로 충족시켜준다

2) working set을 다 할당하고도 page frame이 남는 경우

- swap out되었던 프로세스에게 working set을 할당(MPD 키움)

 

PFF(Page-Fault Frequency) Scheme

직접 page-fault rate를 보고 frame 할당

빈 frame이 없으면 일부 프로세스를 swap out

 

Page Size의 결정

larger page size가 요즘의 추세 (low page fault -> seek 시간 감소)

page size를 감소시키려면

- page 수 증가

- page table 크기 증가

- internal fragmentation 감소

- disk transfer의 효율성 감소(seek/rotation vs transfer)

- 필요한 정보만 메모리에 올라와 메모리 이용이 효율적 -> locality의 활용 측면에서는 좋지 않음