[운영체제] 프레임 개수

• 페이지 부재율은 일반적으로 프로세스에 할당된 프레임의 개수와 역비례 관계이다. 즉, 할당된 프레임이 많을 수록 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 정도가 보편화되어 있다.