OS_11_Demand Paging
1. Memory Space Utilization
1) Obtaining Better Memory-Space Utilization
- 이전 접근들
- 프로세스의 전체 데이터와 프로그램이 physical memory에 있어야만 프로세스를 실행시킬 수 있었다.
- 즉 프로세스의 크기는 Physical memory의 크기로 제한되어 있었다.
- 더 나은 memory-space utilization을 위해서
- Dynamic loading → routine, A,B,C,D순서대로 올린다. (필요한 만큼만)
- Overlays → 임의의 프로그램 조각은 실행하는 것만 올리자
- Dynamic linking
- Swapping
2) Dynamic Loading
- 어떤 routine이 다른 routine에 의해 호출이 될 때에만 해당 routine을 메모리에 load하는 방식이다.
- 시작하기 위해서는 오직 main routine만 memory에 load된다.
- main routine이 다른 routine을 호출한다면 해당 routine이 메모리에 load된다.
- 이러한 방식은 꽤 중요한 이점을 가진다.
- 프로그램에서 특정 실행 경로가 모든 루틴을 사용하지 않을 수 있다.
- 즉, 메모리에 로드되지 않은 routine은 필요하지 않기에, 메모리 공간을 절약 할 수 있다.
- 하지만, memory에 load되어 있지 않은 프로그램을 로드해야 할 때에는 로딩에 시간이 소요될 수 있다.
3) Overlays
- 필요한 시점에만 메모리에 필요한 명령어와 데이터를 유지하는 방식
- Implemented by user
- 프로그래머는 핵심 기능 이외에도 overlay driver를 작성한다.
- overlay driver의 역할은 각 단계가 시작되기 전에 해당 단계의 관련 코드를 메모리에 로드하는 것이다.
- 이를 위해 OS에 특별한 지원은 필요하지 않다.
- 일부 microcomputer compiler는 프로그래머가 overlay 작업을 더 쉽게 할 수 있도록 지원해준다.
Overlays for a Two-Pass Assembler
4) Dynamic Linking
- Linking을 excution time까지 연기하는 방식
- 메모리에 있는 적절한 library routine을 찾기 위해서 작은 코드 조각인 stub이 사용된다.
- stub은 자신을 루틴의 주소로 대체하고 루틴을 실행시킨다.
- Dynamic linking은 일반적으로 OS의 도움이 필요하다.
- OS는 필요한 루틴이 다른 프로세스의 메모리 공간에 있는지 확인하거나 여러 프로세스가 동일한 메모리 주소에 접근할 수 있도록 허용하여야 한다.
- Dynamic Linking은 shared library에서 유용하다.
- 컴파일 할때, Linking하는 것이 아니라 필요할 때, linking한다.
5) Swapping
- 프로세스를 일시적으로 메모리에서 backing store로 이동시키는 것이다.
- 이후에 프로세스를 다시 메모리로 가져와서 실행을 계속할 수 있다.
- (e.g.) round-robin schduling에서 quntum이 만료 될 때, 메모리 관리자는 방금 완료된 프로세스를 swap out하고 다른 프로세스를 메모리로 swap in 한다.
- Backing Store
- 모든 사용자의 메모리 이미지 사본을 수용할 수 있는 충분히 큰 용량의 빠른 disk
- 이 memory image에 대한 직접적인 접근을 제공해야한다.
- backing store는 file system과 별개로 관리되는 디스크의 일부 영역이다.
- swap time의 중요한 부분은 transfer time이다.
- 전체 전송 시간은 스왑된 메모리의 양과 비례한다.
- swap 기능은 많은 시스템에서 수정된 버전으로 사양된다.
- UNIX, Linux, and Windows
- UNIX에서 swapping에서 일반적으로 비활성화
- 많은 프로세스가 실행 중일 때, 활성화된다.
2. Demand Paging
1) Demand Paging vs. Swapping
- Demand paging
- page가 main memory에 필요하기 전까지 load되지 않는다.
- memory에서 backing store에서 page가 스왑된다.
- memory에서 swap되어 필요할 때, 다시 메모리로 올려진다.
- Swapping
- 시스템이 물리적 메모리를 모두 사용할 때, 프로세스를 임시로 backing store로 swap하는 작업.
2) Page Fault
- Page fault
- 첫 번째 메모리 접근시에 발생하는 exception, page fault라고 부른다.
- 처음엔 page를 할당하지 않기 때문에
- 보통 exception은 process를 죽이는데, page fault는 처리해준다.
- Exception은 valid-invalid bit가 invalid인 것을 참조할 때 발생한다.
- Valid-invalid bit는 초기엔 모두 0으로 설정되어 있다.
- valid-invalid bit는 page table entry가 valid한지 아닌지를 나타낸다.
- 첫 번째 메모리 접근시에 발생하는 exception, page fault라고 부른다.
- Page falut handling
- 만약 invalid page에 대한 참조가 일어난다면, OS에게 trap을 보낸다.
- OS는 빈프레임을 확보하고, 페이지를 해당 프레임으로 가져와서 valid-invalid bit를 1로 설정한다.
- 그리고 trap으로 중단된 instruction을 수행한다.
Page Table When Some Pages Are Not in Memory
Steps in Handling a Page Fault
Swapping
Demand Paging
3) Performance of Demand Paging
- Page Fault Rate 0 ≤ p ≤ 1.0
- 만약 p =0이라면 page falut는 없다.
- 만약 p =1이라면, 모든 참조는 falut이다.
- Effective Access Time (EAT)
- EAT = (1-p)m + pf
- Memory access time (m)
- Page fault handling time (f)
- e.g.,
- m = 100 nanosec
- f = 25,000,000 nanosec → 하드디스크에 접근하기에 굉장히 느림
- EAT = (1-p)100 + 25,000,000 p = 100 + 24,999,900 p
- 이 때, EAT를 10% 이하로 유지하고자 한다면
- 110 > 100 + 24,999,900 * p
- 0.0000004 > p
- EAT = (1-p)m + pf
