8장 가상 메모리(virtual memory)

미정·2022년 10월 23일

Demand Paging : 요청이 있으면 -> page를 메모리에 올린다

실제로 필요할 때 page를 메모리에 올리는 것
- I/O 양의 감소 (거의 사용되지 않는 방어적인 코드는 메모리에 올리지 않게됨)
- Memory 사용량 감소
- 빠른 응답 시간 (system-wide 관점)
- 더 많은 사용자 수용 (더 많은 프로그램이 동시에 메모리에 올라갈 수 있음)
Valid/Invalid bit의 사용
- Invalid의 의미 : 사용되지 않는 주소 영역인 경우 , 페이지가 물리적 메모리에 없는 경우
- 처음에는 모든 page entry가 invalid로 초기화
- address translation 시에 invalid bit이 set되어 있으면 => page fault 현상 발생

Page Fault

invalid page를 접근하면 MMU가 trap 을 발생시킴 (page fault trap)
kernel mode로 들어가서 page fault handler가 invoke됨
다음과 같은 순서로 page fault를 처리한다.

Invalid reference? (eg. bad address, protection violation) => abort process
Get an empty page frame (if no empty page frame -> replace)
해당 페이지를 disk에서 memory로 읽어온다.
1) disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당함 (block)
2) Disk read가 끝나면 page tables entry 기록, valid/invalid bit = "valid"
3) ready queue에 process를 insert -> dispatch later
이 프로세스가 CPU를 잡고 다시 running
아까 중단되었던 instruction을 재개

그림으로 살펴보자!

1. 주소변환을 하려고 page table을 봤더니, invalid로 표시되어 있다. 즉, 해당 페이지가 메모리에 올라와있지 않음
2. trap 발생하여 CPU가 운영체제에게 자동으로 넘어감
3. 해당 page는 현재 backing store에 있음 
4. 운영체제가 해당 page를 물리적인 메모리로 올려놓음
5. 물리적인 메모리의 frame number를 엔트리에 적어넣고, invalid -> valid로 바꿈
6. 이후 CPU를 다시 얻어서 주소 변환을 하면 valid로 되어 있기 때문에 주소 변환이 정상적으로 이루어져 물리적인 메모리의 page frame에 접근할 수 있다.

page fault가 났을 때, 디스크에 접근하는 것은 오래 걸리는 작업이기 때문에 page fault가 얼마나 나느냐 에 따라서 메모리 접근 시간이 크게 달라진다.

Page Fault Rate 0 ≤ p ≤ 1.0
- if p = 0 no page faults
- if p = 1l, every reference is a fault

Effective Access Time

= (1 - p) x memory access 
+ p(OS & HW page fault over head  // os로 CPU가 넘어가서 하드웨어적으로 page fault처리
	+ [swap page out if needed] // 메모리에 빈 공간이 없으면 페이지 쫓아내야함
    + swap page in				// 디스크에서 읽어온 페이지 올려놓기
    + OS & HW restart overhead)

Free frame이 없는 경우

Page replacement

어떤 frame을 빼앗아올지 결정해야 함
곧바로 사용되지 않을 page를 쫓아내느 것이 좋음
동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시들어올 수 있음

Replacement Algorithm

page-fault rate을 최소화 하는 것이 목표
알고리즘의 평가
- 주어진 page reference string에 대해 page fault를 얼마나 내는지 조사
* reference string : page들이 참조된 순서대로 나열해 놓은 것
reference string의 예
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Optimal Algorithm

(미래에 참조되는 page들을 미리 다 안다고 가정)

Belady's optimal algorithm, MIN, OPT 등으로 불림
MIN(OPT) : 가장 먼 미래에 참조되는 page를 replace
- 의미 : 실제 사용은 불가능하지만, 다른 알고리즘의 성능에 대한 upper bound 제공

FIFO(First In First Out) Algorithm

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

FIFO Anomaly (Belady's Anomaly)
more frames =/=> less page faults (프레임 수의 증가가 page fault의 감소를 보장하지 않음)

LRU(Least Recently Used) Algorithm

가장 오래 전에 참조된 것을 지움
(= 최근에 참조된 page가 다시 참조되는 성향이 높다)

# LFU(Least Frequently Used) Algorithm

LFU : 참조 횟수(reference count)가 가장 적은 페이지를 지움

장점 : LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있음
단점 : 참조 시점의 최근성을 반영하지 못함. LRU보다 구현이 복잡함

LRU와 LFU 알고리즘의 구현

LRU
메모리 안에 있는 페이지들을 참조 시간 순서에 따라서 줄 세움(LinkedList 형태)
O(1) complexity
LFU
메모리 안에 있는 페이지들을 참조 횟수 순으로 줄 세움
LinkedList 형태로 구현한다면, LRU와 달리 특정 페이지의 참조 횟수가 바뀌었을 때 어느 위치에 줄 세울지 결정하기 위해 다른 페이지와의 1:1 비교 과정이 필요함
O(n) complexity
Heap으로 구현시, O(log n) complexity

다양한 캐슁 환경

caching 기법

한정된 빠른 공간(=캐쉬)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐쉬로부터 직접 서비스하는 방식
paging system 외에도 cache memory, buffer caching, Web caching(동일한 url에 대해 다시 요청을 할 경우, 내 컴퓨터에 이미 읽어온 웹 페이지를 저장해두었다가 화면에 보여줌) 등 다양한 분야에서 사용

캐쉬 운영의 시간 제약
교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 ㅣㄹ제 시스템에서 사용할 수 없음

Buffer caching이나 Web caching의 경우
- O(1)에서 O(log n) 정도까지 허용
Paging system인 경우
- page fault인 경우에만 OS가 관여함
- 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없음
- O(1)인 LRU의 list 조작조차 불가능

결론 : paging system에서는 LRU, LFU 사용할 수 없다.
(그럼 왜 배웠나..? pagign system 외에도 다양한 캐슁 환경이 있다니까~)

Clock Algorithm

LRU의 근사 알고리즘. Second chance algorithm, NUR(Not Used Recently), NRU(Not Recently Used) 이라고도 불림

Reference bit 을 사용해서 교체 대상 페이지 선정(circular list)
reference bit가 0인 것을 찾으면 그 페이지를 교체
한 바퀴 돌아와서도(=second chance) 0이면 그때에는 replace 당함
자주 사용되는 페이지라면 second chacne가 올 때 1

+ Clock algorithm의 개선
- reference bit와 `modified bit(dirty bit)을 함께 사용
- reference bit = 1 : 최근에 참조된 페이지
- modified bit = 1 : 최근에 변경된 페이지 (I/O를 동반하는 페이지)

Page Frame의 Allocation

Allocation problem : 각 process에 얼마만큼의 page frame을 할당할 것인가?
Allocation의 필요성
- 메모리 참조 명령어 수행시 명령어, 데이터 등 여러 페이지 동시 참조
명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있음
- Loop를 구성하는 page들은 allocate 되는 것이 유리함
(최소한의 allocation이 없으면 매 loop마다 page fault)
Allocation Scheme
- Equal allocation : 모든 프로세스에 똑같은 개수 할당
- Proportional allocation : 프로세스 크기 에 비례하여 할당
- Priority allocation : 프로세스의 priority 에 따라 다르게 할당

Global vs Local Replacement

Global replacement

Replace시 다른 process에 할당된 frame을 빼앗아 올 수 있다
Process별 할당량을 조절하는 또 다른 방법임
FIFO, LRU, LFU 등의 알고리즘을 glocal replacement로 사용시에 해당
Working set, PFF 알고리즘 사용

Local replacement

자신에게 할당된 frame 내에서만 replacement
FIFO, LRU, LFU 등의 알고리즘을 process별로 운영시

Thrashing

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

Page fault rate이 매우 높아짐
CPU utilization이 낮아짐
OS는 MPD(Multiprogramming degree)를 높여야 한다고 판단
(CPU가 놀고있다고 생각해서 프로그램을 더 메모리에 올려야겠다고 판단함)
또 다른 프로세스가 시스템에 추가됨(higher MPD)
프로세스 당 할당된 frame의 수가 더욱 감소
프로세스는 page의 swap in/swap out으로 매우 바쁨
대부분의 시간에 CPU는 한가함
low throughput

Thrashing을 막기 위해서는 동시에 메모리에 올라가 있는 프로세스의 개수(multiprogramming degree) 를 조절해주어야 한다. 각 프로세스가 어느 정도 메모리를 확보할 수 있도록!
-> 그것을 해주는 알고리즘 : Working-Set Algorithm, PFF(Page-Fault Frequency) Scheme

Working-Set Model

Locality of reference

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

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

Working-set Model

Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 page들의 집합을 Working Set이라 정의함
Working Set 모델에서는 process의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 frame을 반납한 후 swap out (suspend)
ex) 프로그램 A의 Working Set은 페이지 5개로 구성되는데 해당 프로그램에게 페이지를 3개밖에 줄 수 없는 상황 -> "3개 필요없고, 5개 줄 때까지 하나도 안받을게~"
Thrashing을 방지함
Multiprogramming degree를 결정함

Working-Set Algorithm

Working-Set의 결정

프로그램이 과거 Δ시간(window) 동안 참조한 페이지들을 Working-Set이라고 간주
window size가 Δ인 경우
- 시각 ti에서의 working set WS(ti)
Timeinterval[ti - Δ, ti] 사이에 참조된 서로 다른 페이지들의 집합
- Working-Set에 속한 page는 메모리에 유지, 속하지 않은 것은 버림
(즉, 참조된 후 Δ 시간 동안 해당 page를 메모리에 유지한 후 버림)

PFF(Page-Fault Frequency) Scheme

page-fault rate의 상한값과 하한값을 둔다

어떤 프로그램의 page-fault rate이 상한값보다 높음(지나치게 빈번)
-> Working-Set 보장이 안 된 상황으로 간주하여, 해당 프로그램에게 page 수를 더 늘려줌
어떤 프로그램의 page-fault rate이 하한값보다 낮음
-> 필요 이상으로 메모리를 가지고 있다고 간주하여, 해당 프로그램으로부터 메모리를 빼앗음
빈 frame이 없으면 일부 프로세스를 swap out

Page Size의 결정

Page size를 감소시키면

페이지 수 증가
페이지 테이블 크기 증가 (더 많은 수의 엔트리 필요)
Internal fragmentation 감소
Disk transfer의 효율성 감소
- Seek/rotation vs transfer
- Seek 시간 : 오래걸림
  따라서, 가능하면 한 번 디스크 head가 이동해서 많은 양의 데이터를 읽어서 메모리에 올리는 것이 좋다.(=페이지가 큰 것이 좋다.) 페이지 크기가 작으면 Disk head가 비교적 자주 이동해야함
필요한 정보만 메모리에 올라와 메모리 이용이 효율적
- Locality의 활용 측면에서는 좋지 않음

* page size를 키우는 것이 요즘의 추세이다.

미정

이전 포스트