페이지 부재율은 일반적으로 프로세스에 할당된 프레임의 개수와 역비례 관계이다. 즉, 할당된 프레임이 많을 수록 page fault rate가 줄어든다.
물론 페이지 대치 알고리즘에 따라서 일시적으로 이 역비례관계가 깨지는 '벨러디 변이'가 일어날 수는 있다.
이런 성질에 따라 각 프로세스에 적절한 프레임 개수를 할당해주어야만 할 것이다.
프레임 할당
모든 프로세스가 할당 받을 최소의 프레임 개수는 CPU 명령어의 구조에 의해 결정된다. 하나의 명령어가 참조하는 모든 페이지가 동시에 메모리에 올라와야 명령어 수행 완료가 가능하기 때문이다.
예를 들어 어떤 명령어가 간접주소를 사용한다고 하면 '명령어 페이지', '오퍼랜드 주소 페이지', '주소 내용이 가리키는 페이지' 총 3개의 페이지가 담길 프레임이 필요하다.
PDP-11의 move 명령은 6개의 페이지가 필요하다. 한 명령어가 2바이트를 차지할 수 있어 최대 2페이지이 필요되었다. 또 from과 to 각각에 대해 간접주소를 사용해 또 각각 2페이지씩 필요하여 총 6개의 페이지이 있어야 프로세스 수행이 원활하다.
균등할당 방법 : 모든 프로세스에 똑같은 프레임을 할당. 예를 들어 93개의 프레임과 5개의 프로세스가 있다할 때 각 프로세스에 18개씩 프레임을 할당해주고 나머지 3개의 프레임은 프리 프레임 버퍼 풀(free frame buffer pool)로 사용한다.
비례할당 방법 : 프로그램의 크기에 비례하여 프레임을 할당. 가용 프레임이 m개, 프로세스 pi의 크기를 si라 하고, si들의 합을 S라하면 프로세스 pi에 할당되는 프레임 개수 ai = (si / S) * m 이 된다. 단 ai는 최소할당 수보다는 큰 정수로 한다.
두 방법 모두 높은 우선순위의 프로세스와 낮은 우선순위의 프로세스를 동등하게 취급한다. 하지만 우선 순위가 낮은 프로세스에게 손실을 주더라도 우선순위가 높은 프로세스에게 더 많은 프레임을 할당 할 수도 있다.
Copy-on-Write
일전에 배운 fork와 exec를 떠올려보자. fork를 하면 부모 프로세스의 사용자 문맥을 복제해 자식 프로세스의 사용자 문맥으로 사용한다. 여기서 '사용자 문맥'은 결국 메모리 상의 프레임들이다. 그렇다면 fork를 할 때 자식 프로세스를 위해 부모 프로세스의 프레임을 복제해주어야 하는 것이다.
실제로는 복사하지 않는다. fork->exec의 순서로 코드가 구성된다면 복제된 프레임 내용이 금방 쓸모없어지기 때문이다.
페이지를 공유하도록 하고 해당 페이지를 copy-on-wirte 페이지로 표시만 해놓는다. 그리고 해당 페이지에 값을 기록하게 되면 그 때부터는 공유를 하지 않고 새로운 프레임을 할당, 복제한다.
해당 과정에서 페이지 복사본을 만들 때 빈 프레임을 어떻게 할당해주는가도 중요하다. 이러한 처리를 위해 free page pool을 마련한다. 일반적으로 빈 프레임이 프로세스에 할당되는 경우는 copy-on-write를 할때 혹은 스택이나 힙공간을 확장할 때 등이다. 이러한 과정에서 zero-fill-ondemand 방법(페이지 할당 시 그 내용을 0으로 채워 이전 내용을 지워주는 방법)을 채택하고 있다.
프로그램 구조
int i, j;
int data[128][128];
for(j=0; j <128; j++)
for(i=0; i < 128; i++)
data[i][j]=0;
int i, j;
int data[128][128];
for(i=0; i <128; i++)
for(j=0; j < 128; j++)
data[i][j]=0;
개발자 혹은 컴파일러가 demand paging의 특성을 이해, 반영하고 있다면 프로그램의 성능을 크게 개선시킬 수 있다. 루프가 대표적으로 이에 해당한다. 루프 내의 페이지들은 한번에 메인 메모리에 적재되는 것이 유리하다. 그렇지 않으면 매 loop 마다 page fault가 발생할 위험이 있다.
한 페이지가 128개의 워드 크기이고, 128 x 128의 워드 배열 data을 0으로 초기화하는 프로그램을 생각해보자. 배열이 메모리에 행 중심으로 저장된다고 하면 data[0],[0],data[0][1],...,data[0][127],data[1][0],...,data[128][128] 순서로 저장되어 있을 것이다. 페이지가 128 워드 크기이므로 한 행이 한 페이지를 차지한다.
그럼 위의 프로그램은 루프를 열 중심으로 수행하게 되므로 각 페이지에서 한 워드씩 0으로 만들고, 다시 다음 워드를 0으로 만드는 작업을 반복하게 된다. 이렇게되면 각 루프를 돌때마다 128 * 128회의 page fault를 초래한다.
아래의 프로그램은 행을 중심으로 루프를 수행한다. 페이지의 모든 워드를 0으로 한 후 다음 페이지로 넘어가기 때문에 페이지 부재 수를 128회로 감소시킬 수 있다.
이렇듯 프로그래밍 구조나 자료구조를 잘 선택하면 지역성을 향상시킬 수 있고, page fault rate, 작업 페이지 수를 줄일 수 있다.
예를 들어 스택의 경우 한쪽 끝만 참조하기 때문에 지역성이 높다. 반면 해시 테이블은 접근 또는 참조를 분산시키므로 지역성이 좋지 않다. 물론 지역성은 자료구조의 효율을 측정하는 한 요소일 뿐이며, 그 외 탐색속도나 총 메모리 참조횟수, 페이지 접근 횟수 등을 종합적으로 고려해 효율성을 높여야 한다.
컴파일러와 로더는 페이징에 상당한 영향을 미칠 수 있다. 코드와 데이터를 분리하므로써 수정이 이뤄져선 안되는 코드 페이지는 교체 시 페이지 아웃(write back)을 하지 않도록 한다. 또한 로더는 하나의 루틴 혹은 함수를 페이지 경계에 걸치지 않도록 할당, 각 루틴이 한 페이지 내에 완전히 들어가도록 하여 page fault를 줄일 수 있다.
서로 호출하는 빈도가 높은 함수들끼리 서로 같은 페이지에 위치시킬 수도 있다. 이러한 묶음 작업은 'bin-packing' 문제의 일종으로 볼 수 있다. (cf. bin-packing problem : n개의 아이템을 m개의 빈에 채워넣는 문제. n개의 아이템은 용량을 가지며 m개의 빈은 최대 용량이 제한되어 있다.)
가변 크기의 세그먼트들을 균일한 크기의 페이지들로 묶으면 페이지 간 참조가 최소화가 되도록 할 수도 있다. 이러한 방법은 큰 페이지를 크기를 갖는 경우일수록 유용하다.
페이지 크기
페에지 크기도 페이지의 부재율에 영향을 미친다.
페이지 크기가 작아지면 필요 페이지 수는 많아지지만, 시간이 지나면서 지역성에 의해 인접부분을 모두 포함하게 되어 page fault의 발생은 줄어든다.
페이지 크기가 커지면 개별 페이지들이 최근의 참조로부터 멀어져 지역성 효과가 약화, page fault가 증가한다. 극단적으로 보면 페이지 크기가 프로그램 크기에 근접하면 page fault는 발생하지 않게 될 수는 있다.
페이지 크기가 작으면 페이지 부재률이 매우 낮다가 커질수록 높아진다. 하지만 그러다 페이지 크기가 충분할 정도로 커지면 부재률은 다시 떨어진다. 그리고 페이지 크기가 프로그램 크기와 같아지면 페이지 부재률은 제로가 된다.
물론 그렇다고 페이지 크기를 크게 설정하는 것은 의미가 없다.
페이지 크기에 정답은 없으나, 현재는 페이지 크기가 꽤 커져 4KB~8KB 정도가 보편화되어 있다.
