요구 페이징은 시스템 메모리를 보다 효율적, 응답 속도 향상을 높이기 위해 컴퓨터 운영 체제에서 사용되는 방법이다. 전체 프로세스를 한 번에 메모리에 로드하는 대신 요구 페이징은 프로세스에서 필요할 때(또는 "요구할 때") 페이지(메모리 블록)만 로드한다.
페이지 테이블은 가상 메모리를 관리하기 위해 컴퓨터 운영 체제에서 사용되는 데이터 구조이다. 가상 주소와 물리적 주소 간의 매핑을 저장한다. 가상 주소는 실행 중인 프로그램에서 사용하는 반면 물리적 주소는 실제 하드웨어 메모리를 나타낸다.
아래 그림은 페이지 테이블의 한 행을 의미하는 페이지 테이블(PTE)의 구성을 나타낸다.
페이지 폴트(page fault) 는 프로그램이 현재 물리 메모리에 없는 페이지에 액세스하려고 할 때 컴퓨터 시스템에서 발생하는 인터럽트 또는 예외이다. 그런 다음 운영 체제는 필요한 페이지를 보조 저장소(일반적으로 디스크)에서 물리 메모리로 로드하고, 프로그램은 실행을 계속할 수 있다. 페이지가 전혀 존재하지 않으면 운영 체제는 일반적으로 오류와 함께 프로그램을 종료한다.
페이지 교체 알고리즘은 스왑 영역으로 보낼 페이지를 결정하는 알고리즘이다.
페이지 교체 알고리즘은 다음과 같이 다양한 종류가 있다:
랜덤 페이지 교체 알고리즘: 이 알고리즘은 메모리에서 무작위로 페이지를 선택하여 교체한다. 특별한 규칙 없이 수행되기 때문에 구현은 간단하지만 성능은 일반적으로 최상이 아니다.
FIFO (First In First Out) 알고리즘: 이 알고리즘은 가장 오래된 페이지부터 교체한다. 페이지는 큐에 저장되고, 가장 먼저 들어온 페이지가 가장 먼저 교체된다.
최적 페이지 교체 알고리즘: 이 알고리즘은 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체한다. 이 알고리즘은 가장 낮은 페이지 결함률을 제공하지만, 미래의 페이지 요청을 알아야 하므로 실제 시스템에서는 구현이 불가능하다.
LRU (Least Recently Used) 알고리즘: 이 알고리즘은 가장 최근에 사용되지 않은 페이지부터 교체한다. LRU 페이지 교체 알고리즘은 페이지 접근 시간에 기반한 구현, 카운터에 기반한 구현, 참조 비트 시프트 방식으로 구현할 수 있으며 접근 시간이나 참조 비트를 유지하기 위한 메모리가 추가로 필요하기 때문에 낭비되는 메모리 공간이 많다는 단점이 있다.
LFU (Least Frequently Used) 알고리즘: 이 알고리즘은 가장 적게 사용된 페이지부터 교체한다. 각 페이지의 참조 횟수를 추적하고, 가장 적게 참조된 페이지를 교체한다. LFU 알고리즘도 LRU 알고리즘과 동일하게 낭비되는 메모리 공간이 많다는 단점이 있다.
NUR (Not Used Recently) 페이지 교체 알고리즘: 이 알고리즘은 최근에 사용되지 않은 페이지를 선택하여 교체하는 방법이다. 이 알고리즘은 두 가지 비트, 즉 참조 비트(Reference bit)와 변경 비트(Modified bit)를 사용하여 작동한다.
NUR 알고리즘은 이 두 비트를 이용하여 교체할 페이지를 선택한다. 알고리즘이 이 두 비트를 검사하고 다음 순서대로 페이지를 교체한다:
이 방식으로, NUR 알고리즘은 최근에 사용되지 않은 페이지를 우선적으로 교체하며, 동일한 조건의 페이지가 여러 개 있는 경우에는 수정되지 않은 페이지를 먼저 교체하려고 한다.
FIFO (First In First Out) 변형 알고리즘: FIFO 변형 알고리은 페이지 교체 알고리즘의 단점을 개선하기 위해 개발된 알고리즘이다. 대표적으로 두 가지 변형 알고리즘이 있다:
2차 기회 페이지 교체 알고리즘 (Second Chance Page Replacement Algorithm): 이 알고리즘은 FIFO 알고리즘에 참조 비트를 추가한 변형이다. 페이지가 메모리에 처음 로드되면 참조 비트는 0으로 설정된다. 페이지가 참조되면 참조 비트는 1로 설정된다. 페이지를 교체해야 할 때, 알고리즘은 FIFO 순서로 페이지를 확인하지만, 참조 비트가 1로 설정된 페이지는 교체하지 않고, 대신 참조 비트를 0으로 재설정하고 페이지를 큐의 뒤로 이동시킨다. 참조 비트가 0인 페이지를 찾을 때까지 이 과정을 반복한다.
시계 알고리즘 (Clock Algorithm): 이 알고리즘은 2차 기회 알고리즘의 변형으로, 큐 대신 시계 형태(원형 큐)의 자료구조를 사용하여 페이지를 관리한다. 페이지가 메모리에 로드되면 참조 비트는 0으로 설정되며, 페이지가 참조될 때마다 참조 비트는 1로 설정된다. 페이지 교체가 필요하면, 알고리즘은 "시계 바늘(포인터)"가 가리키는 페이지부터 확인을 시작한다. 만약 참조 비트가 1인 페이지를 만나면, 참조 비트를 0으로 재설정하고 "시계 바늘"을 다음 페이지로 이동시킨다. 참조 비트가 0인 페이지를 만나면 그 페이지를 교체한다. 이 알고리즘은 두 번째 기회 알고리즘보다 페이지 교체를 더 효율적으로 수행할 수 있다.
스레싱(threshing): 하드디스크의 입출력이 너무 많아져서 잦은 페이지 부재(페이지 폴트)로 작업이 멈춘 것 같은 상태를 말한다.
프로그램의 수가 적을 때는 CPU 사용률이 계속 증가하다가 메모리가 꽉 차면 CPU가 작업하는 시간보다 스왑영역으로 페이지를 보내고 새로운 페이지를 메모리로 가져오는 작업이 빈번해져서 CPU가 작업할 수 없는 상태에 이르게 된다. 이러한 시점을 스레싱 발생 시점(threshing point)이라고 한다.
동시에 실행하는 프로그램의 수를 멀티프로그래밍 정도(degree of multiprogramming)이라고 한다.
물리 메모리의 크기를 늘리면 스레싱 발생 지점이 늦쳐진다. 하지만 물리메모리가 작업하는 데 충분한 크기가 되면 그 이후에는 물리 메모리 크기를 늘려도 작업 속도에 영향을 미치지 않는다.
실행 중인 여러 프로세스에 프레임을 얼마나 나누어 주느냐에 따라 시스템의 성능이 달라진다.
정적 할당 방식은 프로세스를 실행하는 초기에 프레임을 할당하기 때문에 프로세스를 실행하는 동안 메모리 요구를 반영하지 못한다는 단점이 있다.
페이지 부재 횟수를 기록하여 페이지 부재(페이지 폴트) 비율을 계산하는 방식