[OS] 프레임 할당

1. Global vs Local Replacement

• Global Replacement : 메모리 상의 모든 프로세스 페이지에 대한 교체 작업을 수행한다.
• Local Replacement : 메모리 상의 자기 자신의 프로세스 페이지에 대해서만 교체 작업을 수행한다.

메모리 사용 효율은 일반적으로 Global Replacement가 좋다.

2. 프레임 할당(Allocation of Frames)

쓰레싱(Thrashing)

일반적으로 메모리에 올라가는 프로세스 개수가 증가할수록 CPU의 이용률은 올라갈 것이라 예상한다. 왜냐면 프로세스가 많을 수록 CPU의 할일 역시 증가하기 때문이다. 이는 일정 범위까지는 맞는 예상이나 그 범위를 넘어서면 오히려 CPU 이용률이 감소하는 현상이 발생한다.

위 그림은 그러한 현상을 그래프로 나타낸 것이다. 위와 같은 현상이 발생하는 이유는 프로세스가 증가할 수록 메인 메모리의 비어있는 프레임 개수는 줄어들게 되고 결국 모든 프레임이 가득차게 된다. 그 후에도 계속 프로세스가 증가한다면 메모리와 backing store 사이에 page in/out 작업이 발생하는데, 프로세스가 많아질수록 이 작업 역시 증가한다. page in/out은 디스크 I/O 작업으로 CPU를 사용하지 않는 작업이다. 그러므로 이 작업이 많아질수록 CPU는 그동안 아무것도 하지 않게 된다.

 

위 그래프에서도 나와있듯이, I/O 작업이 증가하여 CPU 이용률이 떨어지는 현상을 쓰레싱(Thrashing) 이라 한다.

 

쓰레싱을 해결하는 방법은 크게 두 가지가 있다.

• Global Replacement보다 Local Replacement를 사용하는 것이다. 하지만 이 경우에는 메모리 사용 효율이 떨어지는 단점이 있다.
• 프로세스당 충분한/적잘한 수의 프레임(메모리)를 할당한다.

적절한 프레임 수를 조절하기 위해 크게 정적할당, 동적할당을 사용한다.

 

정적할당(Static Allocation)

• 동일 할당(Equal Allocation) : 모든 프로세스에게 똑같은 수의 프레임을 할당한다. 이 방식은 프로세스의 크기에 따라 매우 비효율적이다.
• 비례 할당(Proportional Allocation) : 프로세스의 크기에 따라 프레임을 할당한다. 이 방식 역시 단점이 있다. 프로세스 크기가 크더라도 모든 기능을 사용하지 않기 때문에 이 방식 또한 비효율적이다.

이처럼 정적할당은 한계가 뚜렷하다. 이를 해결하기 위한 방법은 실행 중에 프레임을 할당하는 동적 할당이다.

동적 할당(Dynamic Allocation)

Working Set Model

프로세스가 실행중일 때 어느 페이지를 사용하는지 실험한 결과에서 Locality 성질이 성립한다는 것을 발견할 수 있었다.

위 그래프는 프로세스가 실행 중에 어느 프로세스를 사용하는지 표시한 것으로 특정 시간에는 일정 범위의 페이지를 주로 참조하는 것을 알 수 있다. 이러한 성질은 캐시에서도 볼 수 있다. 이를 통해 특정 시간에 따라 사용하는 페이지의 개수만큼 프레임을 할당해줄 수 있다.

 

하지만 이는 프로세스를 미리 수행해봐야 할 수 있다는 치명적 단점이 있다. 그리고 프로세스를 수행할 때마다 사용하는 기능이 달라질 수 있어 Locality를 사용하는 방법은 비현실 적이다. 

 

이를 해결하기 위해 나온 것이 working set이다. working set은 위의 locality의 방식과 유사한데 미래가 아닌 과거를 보는 것이다.

 

위 그림은 working set을 사용하는 모습이다. working set은 현재 시간에서 일정시간 이전동안 사용되었던 페이지의 집합이다. 델타는 운영체제 내부에서 정하는 기준에 따라 다르며 이를 working set window라 한다. 마지막으로 working set의 개수만큼 프레임을 할당한다.

만약 현재 시간이 t1이라면 working set = {1, 2, 5, 6, 7}이다. 이때 working set의 개수는 총 5개이므로 프레임 역시 5개를 할당하면 된다.

페이지 부재 빈도(Page Fault Frequency)

페이지 부재의 비율은 프로세스에 할당된 프레임 수에 반비례한다. 즉 할당된 프레임 수가 적을 수록 부재 비율은 늘어난다.

 

위 그림은 이와 같은 현상을 그래프로 나타낸 것이다. 세로축은 페이지 부재 비율이고 가로축은 할당된 프레임 수이다. 여기서 운영체제 내부에서 해당 프로세스의 페이지 부재 횟수를 계속 검사한다. 그러면 위와 같은 그래프처럼 나오는데, 여기서 상한선과 하한선을 설정한다.

만약 상한선보다 많은 페이지 부재가 발생하면 프레임을 더 많이 할당해주고 하한선보다 적게 발생하면 프레임 개수를 줄여준다.

3. 페이지 크기

현재 페이지의 일반적 크기는 4KB ~ 4MB이다. 이는 예전부터 점점 크기가 증가해왔고, 현재에도 메모리 크기가 증가하면서 커지고 있다.

페이지 크기에 따라 성능에는 어떤 영향을 미치는지 알아보자.

• 내부단편화 : 내부단편화를 줄이려면 페이지 크기는 작은 것이 좋다.
• Page in, Page out 시간 : 페이지 in/out 시간을 결정하는 가장 큰 요인은 하드디스크 기준으로 하드디스크의 헤더가 움직이는 시간이다. (seek time) 페이지 크기가 클수록 한번의 seek time 마다 큰 페이지를 읽을 수 있으므로, 페이지 부재 빈도가 줄어든다. (데이터를 읽는 시간은 크기에 따라 차이가 매우 적다.)
• 페이지 테이블 크기 : 페이지 크기가 클수록 페이지 개수가 줄어들기 때문에 그만큼 페이지 테이블 크기도 줄일 수 있다.
• Memory resolution(해상도) : Memory resolution은 해당 메모리에 필요한 데이터가 있는 확률이다. 이는 페이지 크기가 작을수록 resolution을 높일 수 있다. 만약 페이지 크기가 크면 다른 필요없는 부분이 있을 확률이 크기 때문이다.
• Page fault 발생 확률 : Page fault 발생 확률을 줄이려면 페이지 크기가 큰 것이 좋다. 이는 Locality 성질과도 관련이 있는데 대부분 프로세스는 필요한 부분이 일정 범위 이내인 경우가 많으므로 페이지 크기가 클수록 필요한 부분이 있을 확률이 크다.