9. Virtual memory

Demand Paging 

실제로 필요할 때 page를 메모리에 올리는 것

메모리 사용량 감소

빠른 응답 시간

더 많은 프로세스를 메모리에 올릴 수 있다

 

출처 : https://core.ewha.ac.kr/publicview/C0101020140509151648408460?vmode=f

위 그림에서 페이지 테이블은 사용가능한 가상주소영역의 크기만큼 만들어진다. (0번 ~ 7번 페이지)

프로그램을 구성하는 페이지는 0번 ~ 5번 페이지이지만 페이지 테이블은 0번 ~ 7번 페이지까지 만들어진다.

1번 3번 4번 페이지는 프로그램에서 사용되는 프로그램이지만 메모리에 올라가있지 않으므로 invalid

프로그램에서 사용되지 않는 6번 7번 페이지는 안쓰니까 invalid

 

주소 변환시 invalid page에 접근하게 되면 page fault가 발생 (요청한 페이지가 메모리에 없는 경우)

page fault가 발생하면 MMU가 trap(소프트웨어 인터럽트)를 발생시켜 cpu가 운영체제로 넘어가고 페이지를 올리는 작업을 수행함

 

Page fault 처리 과정

1. 적절한 주소인지 확인 -> 아닌경우 프로세스 abort() 

2. 메모리에 존재하는 비어있는 페이지 프레임을 찾는다. 

3. disk에서 memory로 페이지를 읽어온다. (disk I/O) 

4. disk I/O가 일어나므로 CPU를 뺏긴다. (block 상태)

5. disk 읽어서 memory로 읽어오면 페이지 테이블 새로운 엔트리에 페이지 프레임 번호 기록하고, valid로 세팅

6. ready queue에 프로세스를 넣기 (ready 상태)

 

비어있는 페이지 프레임이 없는경우

어떤 page frame을 쫓아낼 것인지 결정하는 replacement 알고리즘이 필요함

쫓아내는 과정

1. 쫓아내는 페이지 프레임을 swap area에 복사 (write 작업으로 페이지가 변경되어 swap area에 있는 데이터와 다를 수 있기 때문)

2. 해당 페이지 엔트리를 invalid로 세팅

3. 새로운 페이지를 swap에서 physical memory로 올림

4. 페이지 테이블에 새로운 엔트리에 대해 프레임 번호와 valid 세팅

 

Clock Algorithm (Second change algorithm)

Paging System에서 사용하는 replacement 알고리즘

LRU를 근사한 알고리즘

page fault가 나지 않으면 운영체제는 제어권을 얻을 수 없기 때문에 어떤 페이지가 최근에 참조되었는지(LRU) 어떤 페이지가 가장 자주 참조되었는지(LFU)를 알 수 없음

 

페이지 테이블 entry 마다 reference bit와 modified bit을 둔다. 

하드웨어는 메모리 참조가 일어날때 reference bit을 설정해두고

나중에 os가 빈페이지를 찾을 때 reference bit가 1로 되어있는거 0으로 바꾸면서 0을 찾는다.

페이지가 write으로 참조되는 경우 페이지의 modified bit을 1로 세팅

ㄴ 1로 세팅 되어있으면 나중에 이 페이지 쫓아낼 때에는 swap area에 복사가 필요

ㄴ 0이면 그냥 지워도 됨

페이지 프레임 할당 문제

얼마만큼의 페이지 프레임을 프로세스에 할당 해주어야 page fault가 덜 발생할 것인가?

local replacement - 미리 프로세스에 정해진 프레임 개수 할당하고 프로세스 별로 replace 알고리즘을 적용하는 방법

global replacement - 다른 프로세스에서 뺏을 수 있다.

Thrashing

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

Page fault rate가 높아짐

I/O 시간이 많아져 CPU 이용율이 낮아짐

swap in / swap out 하느라 시간을 다 씀

 

동시에 너무 많은 프로세스 안 올라오게 하는 global replacement 알고리즘

1. working set algorithm

ㄴ working set window를 사용하여 최근에 사용한 n개의 페이지 집합을 유지하고, 집합의 크기보다 비어있는 페이지 프레임 수가 작으면 워킹셋에 있는 페이지 전부 swap out 시키고 프로세스 suspend 상태로 전환

2. PFF(page-fault-frequency) algorithm

ㄴ page fault rate에 상한값가 하한값을 두어 프로그램마다 할당하는 frame의 수를 줄인다.

 

page size

가 작으면 

전체 페이지 수가 증가하므로

페이지 테이블 크기도 증가

disk tansfer 효율성 떨어짐 - seek/rotation 비용이 커짐

locality성이 떨어짐