요구 페이징

요구 페이징 기법
스왑 기법을 사용하는 페이징 시스템과 비슷함.
프로그램을 실행하기 위해 프로그램의 일부만을 메인 메모리에 적재.
순차적으로 작성되어 있는 프로그램의 일부(모듈)을처리할 때 다른 부분은 실행되지 않는다는 사실을 이용함.

오류 처리 루틴의 실행 과정, 과도한 공간 확보, 모듈의 일부 처리 시 발생.
- 오류 처리 루틴의 실행 과정 : 일부 오류 발생 시 해당 오류 처리 루틴만이 필요하고, 나머지 루틴은  디스크에 저장.
- 과도한 공간 확보 : 배열 선언.

프로세스는 디스크에 저장되었다가 수행될 때, 직접 적재하지 않고 지연 교환기(Lazy Swapper)를 사용해 메인 메모리에 적재함.
- 페이지 요구가 있을 때 요구 페이지를 메모리에 교체, 동시에 모든 페이지를 교체하지 않음.
- 사용되지 않는 페이지를 메모리에 읽어 들이는 것을 예방, 교체시간, 기억 공간 감소 및 다중  프로그래밍 정도를 증가시킴.

요구 페이징의 기본 개념
타당-비타당을 나타내는 bit를 페이지 테이블의 각 항목에 추가함.
[그림 8-12] 타당/비타당 비트가 추가된 페이지 테이블.
- 타당 비트(v)로 설정된 경우 해당 페이지가 물리적 메모리에 있음을 의미함.
- 비타당 비트(i)로 설정된 경우 페이지는 보조기억장치(디스크)에 있음을 의미함.
- 저장되지 않은 페이지 사용 시 페이지 부재(Page Fault) 발생하며, 이때 액세스 방지를 위해  타당/비타당 비트를 이용하여 처리함.

비타당 비트.
프로그램이 비타당 비트로 표시된 페이지에 액세스 하지 않는 경우 실행에 영향을 주지 않음.
프로그램이 액세스하는 경우 페이지 부재로 운영체제에 트랩 발생.
- 무효 주소에 의한 오류.
페이지 부재.
[그림 8-13] 페이징 시스템의 페이지 부재.
- 프로세서에 의해 생성되니 가상(논리) 주소 V=(p, d)에서 페이지 번호(p)는 주소번역(페이지 테이블 레지스터)과정을 통해 페이지 테이블에서 해당 페이지 테이블 항목에 접속.
- 메모리에 지정된 프레임의 저장 여부 확인.
- 지정된 프레임 페이지가 저장되어 있지 않는 경우 프레임 번호와 변위 결합, 물리주소 생성.
- 페이지 부재로 해당 페이지(프레임)가 디스크에 저장되어 있음을 의미하므로 명령 재시작.

[그림 8-14] 페이지 부재 처리 과정.
① 프로세스 제어 블록에 있는 내부 테이블 검사, 프로세스 참조가 메모리 액세스에 타당한지 부당한지  결정함.
② 프로세스 참조가 무효화될 경우 프로세스는 중단. 프로세스가 유효한 참조이나 페이지를 가져오지  않은 경우 페이지를 가져옴.
③ 비어있는 프레임 리스트 중 하나를 선택.
④ 할당된 프레임에 요구된 페이지를 읽어 들이기 위해 디스크 동작을 스케줄함.
⑤ 요구된 페이지가 메모리에 있다는 것을 알리기 위해 페이지 테이블을 수정.
⑥ 주요 트랩에 의해 인터럽트된 명령어들을 다시 시작.

순수 요구 페이징.
요구가 계속될 때까지 페이지를 메모리에 들여놓지 않는 방법.
- 메모리에 실행할 프로세스의 페이지가 없어도 프로세스는 수행을 시작할 수 있음.
- 프로세스는 최소의 명령으로 페이지 부재를 일으킴.
- 페이지가 메모리로 들어온 후, 프로세스는 수행을 계속하면서 수행에 필요한 모든 페이지가 메모리에  적재될 대까지 필요할 때마다 페이지 부재를 발생시킴.
- 수행에 필요한 모든 페이지가 메모리에 적재되면 프로세스는 더 이상 페이지 부재를 발생시키지 않고  수행을 계속함.

장단점.
장점.
- 다중 프로그래밍의 정도를 증가시키고 액세스되지 않은 페이지를 로드 하지 않아 메모리가 절약됨.
- 프로그램을 시작할 때 적재(로딩) 지연이 적음.
- 적은 수의 페이지를 읽으므로 초기 디스크 오버헤드가 적음.
- 보호 오류를 페이지 오류로 사용 가능하므로 페이징에 필요한 별도의 하드웨어 지원 불필요함.
- 적재된 페이지들 중 하나가 수정될 때까지 페이지들은 여러 프로그램에 의해 공유되므로 공유 페이지 (코드 공유) 기술은 보다 많은 자원 절약 가능.
- 프로그램을 실행할 충분한 메모리가 없는 시스템에서도 대용량 프로그램을 실행 가능하며,  프로그래머는 이전 중첩(오버레이) 기법보다 쉽게 구현 가능함.

단점.
- 개별 프로그램들은 페이지에 처음 액세스할 때 약간의 지연이 발생함.
- 프리 페이징은 마지막으로 수행한 몇 개의 페이지를 미리 불러오는 방법으로 성능을 향상시킴.
- 낮은 비용, 낮은 성능의 시스템에 실행되는 프로그램은 페이지 대체를 지원하는 메모리 관리 장치가  없음.
- 메모리 관리(페이지 교체)가 복잡함.

페이지 성능
요구 페이지된 메모리의 유효액세스시간.
메모리 액세스시간(Ma)은 대부분 10~ 200ns(Nano Second).
페이지 부재가 발생하지 않는 경우 유효액세스시간은 메모리액세스시간과 동일함.
페이지 부재 발생 시 보조기억장치에서 관련 페이지를 읽은 후 요구된 단어에 액세스하여 더 많은 시간이 소요됨.
페이지 부재의 확률이 p라고 가정함(0 ≤ p ≤ 1).
- p는 0에 매우 가까운, 약간의 페이지 부재율이 있다고 가정함.

페이지 부재 시간 계산.
유효액세스시간 계산을 위해 페이지 부재시간을 계산하여야 함.
페이지 부재 시에 처리하는 인터럽트 처리시간과 페이지 교체시간, 프로세스 재시작 과정이 필요함.
- 인터럽트 처리 및 프로세스 재시작 과정은 수백 개의 명령어로 구성, 짧은 시간 (약 1~1000microsecond 범위)에 처리 가능.
- 페이지 교체시간은 디스크의 헤드 이동에 따른 탐색시간(5millisecond-ms)과 지연시간(3ms),  전송시간(0.05ms) 등으로 대략 8ms로 예상됨.
- 소프트웨어와 하드웨어 시간을 포함한 총 페이지부재시간 처리는 약 8ms임.
평균 페이지부재 처리시간이 8ms이며, 메모리 액세스시간이 200ns일 경우.

유효액세스 시간 감속.
유효액세스시간은 페이지 부재율에 비례함.
1,000개 중 한 개의 액세스에 페이지 부재 발생 시 유효액세스시간은 8.2(8199.8ns)microsecond.
요구 페이징으로 인해 유효액세스시간은 40배(메모리 액세스시간은 200ns) 감속됨.
유효액세스시간을 10% 미만으로 감속, 메모리 액세스시간을 220ns보다 적게 유지하기 위한 조건.

페이징으로 인한 감속을 적당한 수준에서 유지하기 위해 399,990(=1/0.00000250006250)번 중 한 번의 메모리 액세스가 페이지 부재 발생율 보다 더 낮은 비율로 발생해야 함.

※ 페이지 부재율이 높을 경우 유효액세스시간이 증가하며, 프로세스 수행시간이 늦어짐.
※ 대부분의 페이지가 처음 참조될 때 부재가 발생하고 이후에는 메모리에 저장되어 있어 페이지 부재율이 발생하지 않을 수 있음.

페이지 대치
페이지 대치의 필요성.
[그림 8-15] 페이지 대치의 필요성.
- 프로그램 카운터(PC)에 의해 사용자 1의 페이지 M을 적재하면 물리적 메모리에 비어있는 프레임이  없음을 발견.
- 사용자 2의 페이지 B는 물리적 메모리에 적재할 수 없음.

페이지 대치 기법.
페이지 방식을 취하는 가상 메모리에서 페이지 부재 발생 시 메인 메모리에 있으면서 사용되지 않는 페이지를 없애고 새로운 페이지로 변경.
아래와 같은 방식으로 액세스 됨.
① 비어 있는 프레임이 없다면 현재 사용하지 않는 프레임(희생자)을 찾음. 사용하지 않는 프레임이  있는 경우 발견한 프레임을 비우기 위해 프레임의 내용을 보조기억장치(디스크)에 저장.
② 페이지가 메모리에 더 이상 존재하지 않는다는 것을 알려주기 위해 페이지 테이블을 변화(비타당  비트로 전환)시킴으로써 프레임이 비게 됨.
③ 원하는 페이지(f)를 디스크로부터 읽어 프레임에 저장.
④ 새로운 페이지(f)를 위하여 페이지 테이블을 수정함.