가상 메모리는 물리 메모리의 크기 한계를 극복하기 위해 등장한 개념이다. 예를 들어 100MB의 메인 메모리에서 200MB 크기의 프로세스를 실행하고자 한다면? 원래는 실행이 불가능하지만 가상 메모리를 사용하면 가능하다.
동적 할당 (Dynamic Allocation) 에서 보았듯이 프로세스를 실행할 때 필요한 부분만을 메모리에 적재하면서 메모리 낭비를 방지할 수 있다. 가상 메모리에서도 마찬가지이다. 프로세스 이미지를 모두 메모리에 올릴 필요가 없고 필요한 부분만을 메모리에 올릴 수 있다. 이처럼 지금 요구되는 페이지만 메모리에 올리는 방식을 요구 페이징 (Demand Paging) 이라고 한다.
프로세스 이미지는 기본적으로 Backing Store에 저장된다. 이 후 필요한 페이지만을 메모리에 할당한다.
요구 페이징의 페이지 테이블에는 Valid Bit가 추가된다. 현재 페이지가 메모리에 존재하면 1, 존재하지 않으면 0이 된다. CPU가 어떤 특정 페이지에 접근했을 때 Valid Bit를 확인한다. Valid Bit가 0이라면 인터럽트가 발생하고 운영체제의 ISR로 점프하여 Backing Store에 있는 프로세스 이미지에서 필요한 페이지를 메모리에 할당한다.
요구 페이징은 가상 메모리에서 제일 많이 사용되는 방법이기 때문에 가상 메모리라고 하면 일반적으로 요구 페이징과 동일한 개념으로 여기기도 한다.
페이지 부재는 페이지 결함이라고도 하며, CPU가 접근하려는 페이지가 메모리에 없는 경우를 말한다. 페이지 부재가 발생하면 Backing Store에서 필요한 페이지를 갖고 오며 순서는 다음과 같다.
Pure Demand Paging은 프로그램을 처음 시작할 때는 어떤 페이지가 필요한지 모르기 때문에 아무 페이지도 올리지 않는다. 따라서 처음 실행하면 무조건 Page Fault가 발생하고 필요한 페이지를 갖고 온다.
Page Fault가 무조건 발생하고 또 자주 발생하기 때문에 속도가 느리지만 진짜 필요한 페이지만을 갖고 올 수 있기 때문에 메모리가 절약된다.
지금 당장 필요하지 않더라도 필요할 것으로 예상되는 페이지를 미리 갖고 온다. 비록 메모리는 낭비될 수 있지만 Page Fault가 적게 일어나기 때문에 속도가 빠르다.
Swapping과 Demand Paging은 모두 Backing Store와 메모리 사이를 반복한다는 점은 비슷하다. 하지만 Swapping은 프로세스 단위로 이동하고, Demand Paging은 페이지 단위로 이동한다는 차이가 있다.
Page Fault가 발생하여 Backing Store에서 페이지를 가져오는 과정이 있으므로 페이지 테이블에 페이지가 있을 때와 없을 때의 시간 차이가 생긴다. 이러한 시간 차이를 고려해서 평균적으로 소요되는 시간이 어느 정도인지 계산하는 것이 바로 유효 접근 시간 (Effective Access Time)이다.
p : 페이지 부재 확률
Tm : 메모리를 읽는 시간
Tp : 페이지 부재 발생 시 소요되는 시간
Effective Access Time = (1 - p) * Tm + (p * Tp)
지역성의 원리는 메모리 접근은 시간적, 공간적 지역성을 가진다.는 의미이다. 지역성의 원리로 인해 실제 페이지 부재 확률은 매우 낮다.
CPU가 어느 메모리의 공간을 읽은 후, 시간이 지나도 똑같은 공간을 다시 읽을 확률이 높다. 보통 컴퓨터 프로그램은 반복문을 사용하는 경우가 많기 때문에 똑같은 공간을 반복할 경우가 많다.
CPU가 어느 메모리 공간을 읽을 때는 그 인접한 범위 내에서 읽는다는 특징이다. 보통 컴퓨터 프로그램은 대부분 1000, 1004, 1008, ... 식으로 순서대로 읽는 경우가 많다.
Backing Store는 보통 HDD로 사용하지만 HDD는 접근 시간이 너무 길다는 단점이 있으므로 Swap Device에는 부적합하다. 따라서 SSD (Solid State Disk) 또는 느린 저가 DRAM을 사용하기도 한다.
요구 페이징은 요구되어지는 페이지만 Backing Store에서 가져온다. 하지만 프로그램이 계속 실행되면 요구하는 페이지가 늘어나게 되고, 언젠가는 메모리가 가득 차게 된다. 메모리가 가득 차면 추가로 페이지를 가져오기 위해 어떤 페이지는 Backing Store로 몰아내고 (Page-Out), 그 빈 공간으로 페이지를 가져온다. (Page-In)
이 때, Page-Out된 페이지를 Victim Page라고 한다.
I/O 시간 절약을 위해서 기왕이면 Modified (수정)되지 않은 페이지를 Victim으로 선택하는 것이 효율적이다. Modified된 페이지는 Backing Store 즉, HDD로 보낼 때 변경된 내용을 반영해 줘야 한다. 이를 쓰기 (Write) 연산이라고 하는데 HDD는 읽기 속도도 느린데 쓰기 연산까지 추가된다면 속도가 더욱 느려질 것이다.
따라서 해당 페이지가 Modified 되었는지 여부를 판단해야 하는데, Bit를 하나 추가해서 확인할 수 있다. 이때 추가하는 Bit를 Dirty Bit 또는 Modified Bit라고 하며 수정되었으면 1로, 수정되지 않았으면 0으로 표시한다.
그렇다면 여러 페이지 중에서 무엇을 Victim으로 결정할 것인지를 정해야한다. 제일 쉽고 간단한 방법은 랜덤하게 선택하는 방법이지만 성능 보장이 안된다. 또는 First-In-First-Out (FIFO) 즉, 가장 먼저 메모리에 올라온 페이지를 Victim Page로 선택하는 방법도 있다.
그 외에도 많은 방법이 있는데 이처럼 Victim Page를 결정하는 교체 알고리즘이 몇 가지 있는데, 이를 Page Replacement Algorithms (페이지 교체 알고리즘)이라고 한다.