요구 페이징(Demand Paging)
요구 페이징이란 프로그램 실행 시 프로세스를 구성하는 모든 페이지를 한꺼번에 메모리에 올리는 방식이 아니라, 당장에 사용될 페이지만 올리는 방식이다. 즉, 요구 페이징 기법에서는 특정 페이지에 대해 CPU의 요청이 들어온 뒤 해당 페이지를 메모리에 적재한다.
요구 페이징의 장점
- 필요한 페이지만 메모리에 적재하기 때문에 메모리 사용량이 감소한다.
- 프로세스 전체 메모리를 올리는 데 소요되는 임출력 오버헤드가 감소한다.
- 사용되지 않은 주소 영역에 대한 입출력이 줄어 응답시간이 감소한다.
- 시스템이 더 많은 프로세스를 수용할 수 있도록 한다.
- 물리적 메모리의 제약에서 벗어날 수 있도록한다.
페이지 부재(Page Fault)
가상 메모리 기법은 일부 페이지만 메모리에 적재되어 있고, 나머지는 디스크 스왑 영역에 존재하게 된다. 이러한 이유로 인해 메모리에 페이지가 존재하는지 구별하기 위해 유효-무효 비트를 두어 각 페이지가 존재하는지 표시한다.
이때, 페이지가 메모리에 적재되지 않아 유효-무효 비트에 무효로 세팅되어 있는 경우를 페이지의 부재가 발생했다라고 한다.
요구 페이징의 페이지 부재 처리
CPU가 무효 페이지에 접근하면 주소 변환을 담당하는 하드웨어인 MMU가 페이지 부재 트랩을 발생시킨다. 그 다음에 CPU의 제어권이 커널 모드롤 변경되고 운영체제의 페이지 부재 처리 루틴이 호출된다.
- 운영체제가 해당 페이지에 대한 접근을 위해 주소가 유효한지 확인
- 범위를 벗어나는 영역에 속한 페이지 접근이나 접근 권한 위반을 할 경우 프로세스를 종료
- 접근이 가능한 경우 물리적 메모리에 비어 있는 프레임을 할당
- 빈 프레임이 없다면 기존에 메모리에 올라와 있는 페이지 중 하나를 디스크로 보낸다. => 스왑 아웃
- 디스크로부터 메모리 적재는 오랜 시간이 걸리므로 페이지 부재가 발생한 프로세스는 CPU를 반납하고 PCB에 현재 상태를 저장한 후 봉쇄 상태가 된다.
- 디스크 입출력이 완료되어 인터럽트가 발생하면, 해당 페이지의 유효-무효 비트를 유효로 수정한다.
- 봉쇄되어있던 프로세스를 준비 큐로 이동
- CPU에 할당 받고 PCB로부터 저장한 값을 복원시켜 중단되었던 명령부터 실행시킨다.
희생 페이지(Victim Page)
메모리가 가득 차면 추가로 페이지를 가져오기 위해 어떤 페이지는 backing store로 몰아내고 그 빈 공간으로 페이지를 가져온다. backing store로 페이지를 몰아내는 것을 page-out이라고 하고 반대로 빈 공간으로 페이지를 가져오는 것을 page-in이라고 한다. 여기서 몰아내는 페이지를 victim page라고 한다. 말 그대로 희생 페이지라는 것을 의미한다.
페이지 교체 알고리즘
무작위 페이지 교체
무작위 페이지 교체 알고리즘은 스왑 영역으로 쫒아낼 대상 페이지를 특별한 로직 없이 무작위로 선정하여 내보내는 알고리즘이다. 하지만 이 알고리즘은 지역성을 고려하지 않은 알고리즘이기 때문에 성능이 좋지 못하다.
FIFO (First-in First Out)
메모리에 먼저 올라온 페이지를 먼저 내보내는 알고리즘이다. 따라서 victim page의 대상은 가장 먼저 메모리에 올라온 페이지가 되는 것이다. 이 방법은 가장 간단한 방법이다. 특히 초기화 코드에 대해서 적절한 방법이라고 할 수 있다. 초기화 코드는 처음에 프로세스가 실행될 때 최초 초기화를 시키는 역할만 진행하고 다른 역할은 수행하지 않기 때문에 메인 메모리에서 내려 보내도 괜찮다. 하지만 처음에 프로세스를 실행시키는 데에 무조건 필요하다. 따라서 FIFO의 방법을 사용하면 초기화 시켜준 후 가장 먼저 내려 보내지게 된다. FIFO 알고리즘은 프레임의 수가 적을수록 페이지 결함이 더 많이 일어나게 된다. 계속 교체를 해주어야 하기 때문이다. 하지만 프레임의 수가 많아질수록 페이지 결함의 횟수는 감소하게 된다. 이를 Belady's Anomaly라고 부른다.
OPT (Optimal Page Replacement) - 최적 페이지 교체
OPT 알고리즘은 앞으로 가장 사용하지 않을 페이지를 가장 우선적으로 내려 보내는 알고리즘이다. FIFO에 비해서 페이지 결함이 일어날 횟수가 더 적다. 하지만 OPT의 경우 앞으로도 사용이 잘 되지 않을 것이라는 보장이 없으므로 미래를 알 수 없기 때문에 실질적으로 수행하기에는 큰 어려움이 있다고 할 수 있다.
LRU (Least-Recently-Used)
LRU 알고리즘은 최근에 사용하지 않은 페이지를 가장 먼저 내려 보내는 알고리즘이다. 최근에 사용되지 않으면 나중에도 사용되지 않을 것이라는 아이디어로부터 온 것이다. OPT의 경우에는 미래에 대한 예측이지만 LRU의 경우에는 과거를 보고 판단하므로 실질적으로 사용 가능한 알고리즘이라고 할 수 있다. 실제로도 최근에 사용하지 않은 페이지는 앞으로도 사용하지 않을 확률이 높다고 할 수 있다. 비록 OPT보다는 페이지 결함이 더 일어날 수 있지만 실제로 사용할 수 있는 알고리즘 중에서는 좋은 방법 중 하나라고 할 수 있다.
LFU(Least Frequently Used) 알고리즘
LFU 알고리즘은 참조횟수가 가장 적은 페이지를 교체하는 알고리즘이다.교체 대상이 여러 개라면 가장 오랫동안 사용하지 않은 페이지를 교체한다.
MFU(Most Frequently User) 알고리즘
MFU 알고리즘은 LFU와 반대로 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘이다.
클럭 알고리즘 (NRU or NUR)
클럭 알고리즘은 하드웨어적인 자원을 통해 기존(LRU, LFU)알고리즘의 소프트웨어적인 운영 오버헤드를 줄인 방식이다. NRU(Not Used Recently) 또는 NUR(Not Recently Used) 알고리즘이라고도 부르기도 한다.
클럭 알고리즘은 LRU처럼 가장 최근에 참조되지 않은 페이지를 대상으로 선정한다는 점에서 LRU와 근사하지만 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 않는다.
클럭 알고리즘은 그림처럼 참조 비트(reference bit)를 순차적으로 조사하며 동작한다.
- 프레임 내의 페이지가 참조될 때 하드웨어에 의해 1로 자동 세팅
- 클럭 알고리즘은 한 바퀴 돌며 참조되지 않은 페이지의 참조 비트 값을 0으로 바꾼 후 지나간다.
- 참조 비트가 0인 페이지를 방문하면 해당 페이지를 교체한다.
즉, 페이지가 참조되어 1이 되고, 한 바퀴 도는 동안 사용되지 않으면 0이 되고 다시 한 바퀴를 도는 동안 사용되지 않는 페이지는 참조되지 않았으므로 교체 대상 페이지로 선정하는 알고리즘이다.
클럭 알고리즘은 시계 바늘이 한 바퀴 도는 동안 걸리는 시간만큼 페이지를 메모리에 유지시켜 페이지 부재율을 줄이도록 설계 되었다. 때문에 클럭 알고리즘을 2차 기회 알고리즘이라 부르기도 한다.
스레싱과 프레임 할당
스레싱(Thrashing)
여러 프로그램을 한 번에 실행하면 하드디스크와의 입출력이 계속되어 프로그램이 정지한 것 같은 현상이 발생할 수 있다.
메모리가 꽉 찬 이후 새로운 프로그램을 올리기 위해 기존 프로그램을 스왑 영역에 옮기는 횟수가 증가하기 때문이다.
이처럼 하드디스크의 입출력이 너무 많아져 잦은 페이지 부재로 CPU Utilization이 급격히 저하되는 현상을 스레싱이라고 한다.
물리메모리의 크기와 스레싱
스레싱은 메모리의 크기가 일정할 경우 멀티프로그램의 수와 밀접한 관계가 있다. 흔히 멀티 프로그래밍의 정도(동시에 실행하는 프로그램 수)가 증가하면 CPU Utilization이 증가한다고 생각할 것이다. 어느 지점까지는 이 말이 옳다. 프로그램의 수가 적을 때는 CPU Utilization이 계속 증가가하다가 메모리가 꽉 차면 CPU가 작업하는 시간보다 Paging in, out 작업이 빈번해져 CPU가 작업할 수 없는 상태에 이른다. 이 시점을 Thrashing Point라고 한다.
스레싱과 프레임 할당
- 남아 있는 프레임을 실행 중인 프로세스에 적정히 나눠주는 정책이 필요하게 되는데, 프로세스에 프레임을 할당하는 방식은 크게 정적 할당과 동적 할당으로 나누어 진다.
정적 할당
프로세스 실행 초기에 프레임을 나눠준 후 그 크기를 고정하는 방식이다. 프로세스 크기와 상관없이 사용가능한 프레임을 모든 프로세스에 동일하게 할당하는 균등 할당과 프로세스 크기에 비례하여 프레임을 할당하는 비례 할당 방식이 있다.
동적 할당
정적 할당과 달리 프로세스를 실행하는 동안 메모리 요구를 반영할 수 있는 방식이다.
