[10-1] Virtual Memory : Demand Paging

[ Virtual Memory ]

메모리에 완전히 적재되지 않은채로 실행될 수 있게 하는 기술.

→  프로그램의 크기가 물리적인 메모리보다 더 커도 실행이 가능함.

logical memory와 physical memory를 분리하여 main memory를 극도로 큰 저장장치로 추상화한다.

 

파일, 라이브러리 공유와 process 생성시에 매우 효율적인 방식이다.

physical memory보다 큰 virtual memory의 개념도

 

아래 그림을 보면, Virtual Memory를 사용함으로써 우리가 알고 있던 메모리의 형태가 되기 시작한다.

0번부터 시작하는 logical 형식이면서 contiguous하게 존재한다.

 

 

또한 프로세스들간에 파일, 라이브러리 등 page 단위로 공유가 가능해진다.

→ Page Sharing

 

 

 

 

프로그램을 실행하면, 보조기억장치(SSD, HDD)에서 Memory로 적재한다.

이제, Physical memory에 프로그램을 전체로 올리지 않고 Page 단위로 올린다는 것은 알게 되었다.

그러면 Page 단위로 언제 올릴 것인지도 중요해진다.

 

필요할 때만 page를 적재하자.

→ demand-paged virtual memory

 

[ Damand Paging ]

 

프로세스가 실행 중일 때, 어떤 page는 메모리에 있고 반대로 secondary storage(SSD, HDD같은 보조기억장치)에 있을 수도 있다.

이 두가지 경우를 구분하기 위해, Memory Protection with Paging에서 사용했었던 valid-invalid bit가 사용될 수 있다.

valid : legal and in memory

invalid : illegal or in secondary storage

또는 추가적인 dirty bit를 통해 illegal, secondary storage 까지 구분할 수도 있다.

 

Ex) logical memory에서 G라는 page가 필요 해서 로드하려고 하자.

Page Table에서 해당하는 frame을 보니 invalid bit

→ 현재 메모리가 아닌 secondary storage에 있다는 뜻이므로 swap in(Page in)이 필요하다.

 

[ Page Fault ]

필요한 page가 현재 메모리에 없을 때

1) OS가 들고있는 Free-frame list로부터 free frame을 찾는다.

2) 새로운 frame에 필요한 page를 읽어서 할당

3) internal table과 page table에 현재 메모리에 존재한다고 알리기 위해 invalid bit를 valid bit로 변경.

4) trap에 의해 interrupt된 instruction 재실행

Steps in handling a page fault

 

[ Pure Demand Paging ]

요청할 때만 page를 가져오는 것. (요청되지 않으면 memory에 page가 아예 없는 상태)

→ first instruction부터 page fault가 발생할 것이다.

 

[ Locality of Reference ]

만약 하나의 instruction이 수 많은 page에 접근을 필요로 한다면, 그러니까 instruction에 대한 하나의 page가 접근하는 data 에 대해 많은 page를 요구한다면

Multiple page faults per instruction이 발생할 수도 있다.

 

다행히, 프로세스들을 분석해보면 이런 동작이 과도하게 일어나진 않는다.

프로그램은 the locality of reference를 가지려는 경향이 있어, Demand Paging은 이상적인 성능을 낸다.

→ 컴퓨터구조의 Cache memory와 지향하는 바가 거의 동일하다.

ex) i-j를 서로 바꾼 for-loop의 경우

 

→ 프로그래머가 자료구조 또는 프로그래밍 코드 구조를 잘 선택하고, 배치한다면 data와 code의 locality를 올릴 수 있어 page-fault rate를 줄이고 performance를 향상시킬 수 있다.

 

[ Hardware Support to Demand Paging ]

Page table : valid-invalid bit

Secondary memory (= swap space) : SSD, NVME SSD 사용 (page in-out 속도에 직접적인 관여때문)

 

[ Instruction Restart ]

Trap이 걸리면 wait queue에 보냄, page in이 끝나면 signal을 줘서 재진입

이 때, page fault시 registers, condition code, instruction 등이 저장됨.

그러므로 Context-Switching시 다시 가져와서 정확히 같은 place와 state에서 restart 해야 하는데, 이 때 page table은 다를 수 있어 process별로 page table 관리 필요

 

만약 instruction을 fetch 할 때, page fault가 발생한다면, instruction을 다시 fetch해야할 것이다.

만약 operand를 fetch할 때, page fault가 발생한다면, instruction을 다시 fetch, decode하고 operand를 다시 fetch해야할 것이다.

 

[ Worst-case example ]

ADD A, B, C : three address instruction, adding A and B into C.

1) Fetch and decode the instruction (ADD)

2) Fetch A

3) Fetch B

4) ADD A and B

5) Store the sum in C

 

1)에서 instruction을 fetch할 때 page fault가 일어날 가능성

2), 3), 5)에서 A, B, C를 fetch할 때 page fault가 일어날 가능성

→ page fault가 일어날 때 마다 처음부터 다시 fetch해야 한다.

 

[ Free Frame List ]

page fault가 발생했을 때, OS는 secondary storage로부터 memory로 필요한 page를 swap-in 해야 한다.

→ OS가 free frame list pool을 들고 있으면 해결된다.

 

[ Performance of Demand Paging ]

Page fault를 처리하는데 가장 많은 시간이 소모되는 작업 3가지

1) Page fault interrupt

2) Read in the page

3) Restart the process

 

이 중 가장 큰 것은 2) page를 읽어들이는 시간

 

[ Copy on Write ]

fork() 사용시, shared page를 write할 때만 해당 page를 copy하고, 이외에 read할 때는 굳이 복사할 필요가 없으므로 공유하면 된다.