다음 내용은 아주대학교 김상훈 교수님 운영체제 강의 및 강의 자료와 Operating Systems: Three Easy Pieces(https://pages.cs.wisc.edu/~remzi/OSTEP/)을 참고하여 작성한 글입니다.
So far: Program Loading
- All von Neumann architecture processors require that the data to access should be loaded on the main memory
- However, we install programs on stroage devices
- OS should load everything into the main memory to start a program
Swapping
내 main memory가 꽉 찼는데 process를 더 띄우고 싶을 때 main memory에 바로 그 process를 load 할 수 없을 것이다. 이럴 때, main memory에서 임의의 process를 하나 골라 그 process의 모든 내용을 전부 disk에 쓰고, 빈 memory 공간에 다른 걸 올리는 걸 swapping이라고 한다.
- swap out a process temporarily to a backing store
- bring the process back into memory later for continued execution
Advanage
- process memory can be larger than the physical memory
Disadvantage
- Usually take long, determined by the process size and data transfer rate of the backing store
- 2GB process 하나를 swap in 하기 위해선 3초가 걸린다.
Solution
- Allow to swap in/out only a part of processes in the memory
Demand Paging
- A paging system with page-level swapping
- Bring a page into memory only when it is needed
- process 전체를 load 하는 게 아니라 필요한 부분만 page 단위로 넣고 빼고 하겠다
- less I/O needed
- less memory needed
- Faster response
- More processes
- Move out rarely used/unused pages to the backing store
- 일반적으로 "swapping 한다" 이렇게 더 말하긴 하지만 swapping은 paging unit, segmentation unit 용어가 나오기 이전에 쓰이던 용어이다. 정확하게는 paging이 맞다.
Page fault
page table이 비어있을 경우, 혹은 지금 실행하고자 하는 process의 page(보통 CODE, STACK pages)와 mapping 된 PPN이 없을 경우, MMU는 address translation을 할 수 없다. 이렇게 physical memory에는 없는 page에 접근하는 걸 page fault라고 한다.
MMU가 page fault exception을 날리면 OS는 이 fault를 해결할 수 있는 page-fault handler를 호출한다. 그러면 handler는 PTE에 기록된 PFN을 확인한다. 이때 두 가지 경우가 있을 수 있다.
-
Valid bit가 꺼져 있고, PFN에 Disk 위치가 기록돼 있음
- Valid bit가 꺼져 있고, PFN에 해당 page의 disk 상 address가 적혀 있을 경우, OS는 disk로 I/O 요청을 보내 해당 page를 memory로 load한다. disk I/O가 끝난 다음에는, OS가 PTE의 valid bit을 켜고, PFN field를 새롭게 fetch 해 온 page와 mapping 되는 PFN으로 바꾼다. 그런 다음에, 다시 address translation instruction을 실행한다.
-
Valid bit가 꺼져 있고, PFN에는 다 0이 쓰여 있음
- process가 접근 권한이 없는 메모리 주소에 접근하려고 한 것일 수 있다. 이 경우에는 OS가 process에 segmentation fault와 같은 오류를 발생시키고, 일반적으로 이 process는 강제 종료된다.
- 아직 한 번도 사용되지 않은 메모리 영역에 접근한 경우일 수 있다. 이럴 경우에도 OS는 page-fault handler를 호출한다. OS는 main memory에서 사용 가능한 빈 frame을 찾아 새 page를 할당한다. 그런 다음, PTE의 valid bit를 켜고, PFN을 수정한다. 다시 process를 실행하면, 이전에 실패했던 access가 이제는 성공적으로 처리된다.
그러면 valid bit이 꺼져 있고, PFN에 다 0이 쓰여 있을 때, 접근하면 안 되는 곳에 접근을 한 것인지 아직 한 번도 안 쓰인 영역에 접근한 것인지 어떻게 구분할 수 있을까?
보통 프로그램이 실행되기 전에 OS는 executable file을 참조한다. 이 executable file에는 program의 code range, data range 등의 정보가 기록되어 있다. OS는 이를 기반으로 "page table의 이 부분은 코드 영역", "이 부분은 데이터 영역", "이 부분은 사용되지 않는 영역" 이런 식으로 다른 자료 구조에 기록한다. 아직 실제로 페이지를 할당하지 않고, 프로그램의 주소 공간에 대한 정보만 다른 자료 구조에 저장하는 단계이다.
이후, program이 code나 data page에 접근하려 할 때, page fault가 발생할 것이다. 그러면 OS는 page table을 참고하여, 해당 page가 code 영역의 page인지, data 영역의 page인지, 아니면 사용되지 않는 영역을 접근하려고 하는지를 판단한다. 만약, 이 page가 아까 기록해 둔 valid한 영역에 속한다면 그때 disk에서 읽어서 채워 둔다. (이게 lazy loading이다. 즉 미리미리 load 한 게 아니라 필요한 시점에 load 해 두는 걸 의미한다.)
What if memory is full?
만약에, memory에 빈 공간이 없어서 page를 할당할 수 없다면 어떻게 될까? 이 경우 OS는 page replacement policy에 의해 victim page를 뽑는다. 그런 다음, 이 victim page의 내용을 전부 disk의 paging files에 기록하고, 이 page가 page out 되었다고 PTE에 기록한다(이 과정을 Fix up PTE라고 함. valid bit을 끄고 PFN에 해당 page의 disk 상 위치를 기록함). 그리고 나서 빈 공간이 없어 할당하지 못했던 page를 allocate 시킨다.
일반적으로 OS는 eviction이 불가피하게 발생하는 것을 막기 위해 빈 page를 계속 만들어 main memory의 빈 공간을 확보한다. 이 역할은 Pagers가 담당한다.
locality
Demand Paging은 locality(temporal locality/spatial locality)를 통해 최대의 효율을 달성할 수 있다. 즉 locality로 인해 paging 횟수가 적어질 수 있다. 그러나 locality를 확보하기 위해서는 application의 memory reference pattern, page replacement policy, amount of physical memory 등 아주 많다.
Hardware support
- Page table with valid/invalid bit
- Secondary memory (swap/paging device with swap space)
- Instruction restart
- MMU가 fault가 발생했다고 해서 다음 instr으로 넘어가선 안 된다. OS가 해결한 다음, fault 난 instr를 retry 할 줄 알아야 한다.
