OS-0613 : Demand Paging

*Page fault 처리

#Address Translation, Revisited

가정: 32bit 시스템

- 페이지 사이즈가 1KB라면(2^10), 페이지 테이블에는 2^22(400만)개의 엔트리 존재, 각각 최소 몇바이트씩 차지

- 문제: 메인 메모리가 16MB라면, 문제가 됨

- 해결: 페이지 테이블을 가상 메모리에 저장하고, 필요한 부분을 필요할 때마다 가져옴

- 새로운 문제: 메모리 액세스 시간이 두배로 증가, 페이지 테이블이 페이징의 영향을 받음

    > 페이지 테이블에서 정보 가져오는 액세스, 메모리에서 데이터 가져오는 액세스

- 해결: TLB 사용하여 페이지 테이블 엔트리를 캐시

*TLB는 하드웨어 캐시에 저장됨

 

#Translation Lookaside Buffer(TLB)

- TLB는 page table을 캐싱하는 개념

- TLB는 CPU에 직접 저장되는 하드웨어 캐시고, page table은 main memory에 저장된다

 

#Paging and Segementation

* 2단계 매핑

- 프로세스는 가변 크기의 세그먼트로 분할

- 세그먼트는 많은 작은 고정크기 페이지로 분할

    > 페이지는 OS가 관리하기 용이

    > 외부 단편화 해소

- 가상 주소 = 세그먼트, 페이지, 오프셋

- 각 프로세스당 하나의 세그먼트 테이블, 세그먼트당 하나의 페이지 테이블

 

* 2단계 공유

- 두 페이지 테이블에서 동일한 프레임을 가리킴으로써 프레임 공유

- 두 세그먼트 테이블에서 동일한 베이스를 가리킴으로써 세그먼트 공유

- 여전히 보호 비트 필요

 

#Memory Management So Far

- 애플리케이션의 메모리는 가상 주소 공간

    > OS는 물리 주소 공간

    > MMU를 사용하여 세그멘테이션, 페이징 또는 두 가지 조합을 구현하여 주소 변환 제공

- 지금까지의 제한: 프로세스의 모든 세그먼트/페이지는 메인 메모리에 있어야 실행 가능

    > 프로세스가 실행되지 않으면 전체 프로세스를 디스크로 스왑 아웃 가능

- 인사이트: 특정 시간에는 프로세스의 가상 메모리의 작은 일부분만 접근해야 할 가능성이 높음

    > 요구에 따라 페이지/세그먼트 로드

 

#Demand Paging(Virtual memory)

- 특정 시간에 가상 메모리 페이지는 다음중 하나에 저장

    > 물리 메모리의 프레임

    > 디스크(백업 또는 스왑 공간)에 저장

- 프로세스는 가상 주소 공간의 일부만 메인 메모리에 올라와도 실행 가능

    > 거의 무한한 메모리처럼 보이게 함

즉 프로세스의 모든 페이지를 가져오지 않고 일부만 가져와서 프로세스를 실행한다

(page fault, 가져오기 반복)

 

#Starting a New Process

- 프로세스는 가상 페이지 중 일부가 물리메모리에 있고 나머지는 디스크에 저장된 채로 시작

- 페이지 선택 - 새로운 페이지는 언제 물리 메모리로 가져와지나

    > pre paging - 시작에 필요한 만큼 미리 로드: 코드, static dat, stack page 하나 

        > 단점: memory polution

    > Demad paging - 0 페이지로 시작, 각 페이지는 필요할 때마다 로드(page fault 발생시)(가장 일반적)

        > 단점: 프로그램 실행 시 많은 페이지 폴트 발생

-> 참조 공간, 시간적 지역성 기반으로 작동(통계적으로 분석해 보니 메모리에서 근처에 있는 것들을 자주 참조하는 경향을 보임 + 최근에 참조한 것을 또 참조하는 경향도 보임)

- demand paging은 참조의 지역성 원리에 따라 작동

    >★ Knuth는 프로그램 시간의 90%가 코드의 10%에서 발생한다고 주장

 

#Page fault

- 물리 메모리에 없는 페이지에 접근 시도는 page fault 발생

    > 페이지 테이블은 각 페이지마다 유효 비트(present bit) 포함

    > 유효 비트가 설정되지 않은 페이지에 접근 시도는 페이지 폴트 발생, OS 트랩 유발

    > 폴트 발생시: 

        > OS는 페이지를 페이지 인 하여 디스크에서 물리 메모리의 빈 프레임으로 가져옴

-> 해당 작업은 pid2번 pager가 실

        > 페이지 테이블, 유효 비트 업데이트

        > 프로세스 실행 계속

- 인터럽트와 달리 페이지 폴트는 메모리 참조가 있는 모든 시점에 발생 가능

    > 심지어 명령어의 중간에도 가능

    > 그러나 페이지 폴트 처리는 발생한 프로세스가 모르게 진행

 

#Handling Page Faults

- 페이지 폴트 핸들러는 프로그램의 실행을 계속하기 위해 페이지 폴트가 발생한 시점의 머신 상태를 복구할 수 있어야 함

- PC(program counter)는 명령어 주기의 시작에서 증가

    > OS/HW가 특별히 처리하지 않으면, 페이지 폴트 발생한 프로세스는 다음 명령어를 실행(폴트 발생 명령어 건너뜀)

- 하드웨어 지원:

1. 명령어 실행 전에 폴트 테스트(IBM)

2. 명령어 완료 이전 위치에서 계속(intel)

3. 명령어 다시 시작하고, 필요한 경우 이미 수행한 적읍을 취소(pdp, mips, dec 등)

 

#Performance of Demand Paging★

 

#Page Replacement

- 프레임이 꽉 차서 페이지 교체가 필요한 상황

- 이를 결정하는 알고리즘

    > FIFO, Random, LRU, Optimal 등