왜 필요한가

• Program이 실행되려면 메모리에 올라와야 한다. 하지만, 일부만 사용된다.
• 그러니까 다 안 올려도 된다.

physical 메모리로부터 사용자가 보는 logical(virtual, 가상) memory를 분리하자!

가상 메모리

큰 크기의 가상 메모리는 작은 physical memory를 사용할 때 좋다.
사용자가 보는 공간은 아주아주 큰 전체이지만, 이게 전부 다 메모리에 올라와 있는 게 아니다.
실제로 메모리에 올라와 있는 것도 있고, disk에 있는 것들도 있다.

우리가 아는 pross가 어떻게 메모리에 저장되는지, PCB의 구조는 사실 가상적인 관점이다.
연속적인 주소는 user view이며, 실은 phyical memory에 비연속적으로 할당되어 있을 것이다.
이 data들은 page단위로 잘려, MMU가 logical page를 physcial frame에 mapping해준다.

동적할당을 요청하면, 이는 추가적인 frame을 얻는 것이 아니다. 가상 주소 공간을 사용할 권리를 얻는 것이다.

Copy-on-Write

fork()는 부모 process의 복사본인 자식 process를 생성했었다.
fork()후, exec()을 호출하여 replace하는 경우, copy overhead가 발생한다.

Copy-on-Write(COW)는 부모와 자식 process가 메모리의 같은 페이지를 공유하도록 한다.(page sharing)
즉 초기에는 같은 page table을 가리킨다. write가 일어날 때, 그 부분만 page table의 주소를 바꾸어, physical memory의 다른 공간을 가리키도록 만든다.

1. Demand Paging

가상메모리는 demand paging을 사용한다.
이는 program 수행 중에 필요한 page만 메모리에 할당하는 방법이다.

극단적인 경우, 아무런 page가 메모리에 할당되지 않은 채로 시작할 수도 있다. (pure demand paging)

Demand paging은 swapping paging system과 유사하다.
Demand paging을 사용하면,

• 초기 initial time에 I/O를 적게 사용한다. (하지만 중간중간에 I/O는 많다.)
• 적은 메모리가 요구된다.
• response가 빠르다.
• 더 많은 사용자를 수용할 수 있다.

어떤 page는 메모리에 있지만, 어떤 애들은 disk, 즉 secondary storage에 있을 것이다.
따라서 지금 현재 메모리에 있는 애들과, 없는 애들을 구분하는 HW가 필요하다.

Valid-Invalid Bit

각 page table에는 valid-invalid bit가 포함되어 있다.

• valid(1)는 메모리에 있다는 뜻
• invalid(0)는 메모리에 없다는 뜻이다.
  초기에는 모두 0으로 setting되어 있다. 메모리에 page가 올라올 경우, 1로 변경된다.

만약 process가 메모리를 접근하려고 하였을 경우,
logical address를 따라 page table에 간다.

page table의 valid-invalid bit가 1이라면, 메모리에 있다는 뜻이므로 바로 메모리에 접근해 가져오면 된다.
하지만 valid-invalid bit가 0이라면, 현재 메모리에 없고 disk에 있다는 뜻이므로, page fault라는 trap을 발생시켜 OS에게 알린다. disk에서 가져오도록 해야 한다.

어떻게?

page fault steps

자, 찬찬히 다시 한 번 살펴보자.

어떤 명령어에 의해 data를 가져오려고 어디있나~ 정확한 주소(physical address)가 어딘가~ 싶어서 pagetable을 확인한다. invalid다! 메모리에 없다!
disk에 있다는 뜻이므로 trap(page fault)을 발생시켜 OS에게 알린다.
OS의 trap handler의 page fault handler는 이 접근이 과연 정상인시 check한다. segment fault이냐, 단순히 메모리에 없는 것이냐. 잘못된 접근이라면 abort 중단한다.
정상적인 접근인데, 단순히 메모리에 없는 것이라면 disk에서 찾아온다.
읏챠- 메모리의 빈 공간에 데리고 온다. 넣은 공간의 frame number를 page table에 정리하고, invalid를 valid로 바꾸어준다.
그런 다음, instruction을 다시 실행할 수 있게끔 한다.

Problem in Restart Instruction

만약 source와 destination block이 겹쳐져 있다면, source block이 변경되었을 때 instruction을 시작할 수 없다.
...?
어쨌든 page fault로 해결하기 어려운 문제가 발생하며, 이를 해결하기 위해서도 overhead가 어쨌거나 발생하게 된다.

Performance of Demand Paging

Demand paging은 성능에 영향을 준다.

page fault가 발생할 확률을 p라고 하자.
p가 0이면, page fault가 하나도 발생하지 않는다. 메인 메모리 접근으로도 충분하다는 뜻
p가 1이면, page fault가 계속 발생한다. 계속해서 disk에 접근해야 한다는 뜻

Effective access time (EAT)

EAT = (1 - p) X memeory access time + p X (page fault time)

page fulat time은, trap + (trap handler)check + disk에 찾기 + free frame 찾기 를 모두 포함하는 시간이다. (그리고 만약 free frame이 없다면, 기존에 있는 것 중 밀어낼 것은 없애고 새로 가져와야 한다.)

• page fault overhead
• time for swapping page in
• time for swapping page out, if necessary
• restart overhead

Ex.1

memory access time = 1 micro sec (10^-6)
50% 페이지가 free frame이 없어서 replace 된다. (swap out & swap in)

swap page time = 10 ms (milli 10^-3) = 10 000 us

page fault = no modification(0.5 X 10000 us) + modified(0.5 X 20000 us) = 5000 + 10000 = 15000 us
EAT = (1 - p) X 1 us + p X (15000 us) ~~ 1 + 15000 us

Ex.2

memory access time = 200 nano sec(10^-9)
Average page-fault tiem = 8 milli sec(10^-3)

EAT = (1 - p) X 200 ns + p X 8 ms
= (1 - p) X 200 ns + p X 8 000 000 ns
= 200 + p X 7,999,800 ns

IF one access out of 1000 causes a page fault, (1/1000)
EAT = 8.2 us (= 8 200 ns)
page fault 가 발생함으로 인해 기존 memory access time보다 40 배 느려짐