[운영체제/OS] 프레임 할당(Frame allocation)과 Page fault 관련 기타 이슈들

📒 1. 프레임의 할당

이전의 많은 포스팅에서 가상 메모리의 관리는 애초에 물리적 메모리가 가상 메모리보다 훨씬 작기 때문에 필요한 개념이라고 말씀드렸는데요.

 

따라서 각 프로세스는 자신이 필요로 하는 "최소한의" 페이지만 사용하는 것이 합리적이라고 볼 수 있습니다.

 

그렇다면 각 프로세스는 얼마만큼의 프레임을 할당받아야 감당할만큼(?)의 페이지 폴트를 일으키면서 전체 프로세스가 원활하게 돌아갈 수 있을까요? 이 역시 명확한 기준은 없지만 크게 두 가지 방법이 존재합니다.

 

✅ 1) Local Replacement

이 방법은 프레임을 어떤 프로세스에게 고정 할당(Fixed Allocation)하는 개념에서 시작합니다. 애초에 프로세스 별로 할당된 프레임의 크기가 고정되어 있기 때문에, 페이지 폴트가 발생하면 프로세스 안에서 페이지 교체 정책을 통해 자체적으로 메모리를 확보해야 합니다.

 

예를 들어 100개의 프레임이 있고, 5개의 프로세스가 존재한다면 한 프로세스마다 20개의 페이지 공간(프레임)을 할당해주는 방식입니다.

 

✅ 2) Global Replacement

이 방법은 프로세스의 우선 순위를 따져 각 프로세스에게 '동적으로' 우선 순위 할당(Priority Allocation)을 합니다. 

 

만약 페이지 폴트가 발생한다면, 다른 프로세스이 가지고 있던 프레임을 뺐어와서 사용할 수 있죠. 

 

예를 들어, 전체 프레임의 수가 64개이고 프로세스 1, 2의 사이즈가 각각 s1, s2라면, 프로세스1에게 64 * (s1 / (s1+s2)) 만큼의 프레임을 할당합니다. 물론 다른 방식으로 우선순위 할당을 할 수도 있겠죠?

 

---

자, 이제 프레임 할당에 대한 간단한 설명을 마치고 페이지 폴트와 관련된 몇 가지 이슈에 대해 정리해보겠습니다.

 

📖 2. 쓰레싱(Thrashing)

만약 한 프로세스가 사용할 수 있는 물리 메모리의 공간이 부족하다고 해보겠습니다. 그러면 당연히 페이지 폴트의 가능성이 높아지고, 이를 처리하는 데 드는 오버헤드가 존재합니다.

 

쓰레싱은 이처럼 프로세스들이 자신의 작업을 처리하지 못하고 페이지 폴트로 인한 페이지 교체, 혹은 프레임의 재할당 등을 하는 데 시간을 계속 투자하는 상황을 말하는데요.

 

예를 들어서, 현재 CPU의 Utilization이 낮은 상황이라고 해봅시다. 그러면 우리의 OS는 CPU의 Utilization을 높이기 위해 멀티프로그래밍 수준을 높이고자 더 많은 프로세스를 메모리에 불러들일 수 있습니다. 하지만, 지금 CPU의 Utilization이 낮은 이유가 적은 수의 프로세스 때문이 아닌 프레임은 부족하고 프로세스는 많았기 때문이면 어떻게 될까요? 더 상황이 악화될 수밖에 없습니다.

 

다시 말해, 각 프로세스는 Locality에 대한 페이지를 프레임에 매핑해놔야 잘 돌아가게 되는데 이러한 페이지들을 올릴 프레임이 부족하면 잘 돌아가지 않아서 CPU의 활용률이 낮아진다는 뜻입니다.

 

그리고 이런 상황을 쓰레싱(Thrashing)이라고 합니다.

 

Thrashing

아래 그림은 프레임 할당 수에 따른 페이지 폴트의 빈도 수를 나타낸 그림인데요. 허용하는 페이지 폴트의 상한선과 하한선이 표시되어 있습니다.

 

만약 페이지 폴트가 상한선 위로 나타나면 프레임을 더 할당하고, 하한선 아래로 내려가면 프레임의 수를 줄여도 문제가 없습니다.

프레임 할당과 페이지 폴트의 빈도 관계

 

📊 3. 워킹 셋 모델 (Working-Set Model)

워킹 셋(Working-set)이란 "현재 사용되고 있는 페이지들의 집합"을 의미합니다. 그리고 워킹 셋 윈도우(Working-set Window)란 페이지를 참조(Reference)하는 횟수를 의미하는데, 예를 들어 10,000번의 명령어 수행을 Working-set Window로 정한다는 말은 현재 시점 T로부터 이전의 10,000개의 명령어에 속하는 녀석들이 Working-Set이 된다는 뜻입니다.

 

Working set, Working set window

위 그림을 보면 동일한 프로세스가 진행되는 중에도 시간에 따라 참조되는 페이지가 다르다는 것을 알 수 있는데요. 

 

워킹 셋 관점에서 워킹 셋 윈도우의 크기가 10임에도 불구하고 이 시점에 프로세스에게 프레임을 100개 할당해주면 90개 이상은 의미없는 할당이 된다는 뜻입니다.

 

정리해서 이야기하자면, 워킹 셋 모델이란 T시간동안 프로세스에게 할당해야 하는 적절한 프레임의 수에 대한 모델이라고 할 수 있죠.

 

한편 WSS(Working Set Size of Process P)는 가장 최근 워킹 셋 윈도우에서 사용되고 있는 페이지들의 수를 의미하는데요. 워킹 셋 윈도우의 크기가 클수록 더 많은 명령어들이 워킹셋에 포함되고, Locality의 개념이 커지게 됩니다. 반면 워킹 셋 윈도우의 크기가 작아지면 Locality를 인정하는 명령어들이 적어지게 되죠.

 

한편, D = 모든 프로세스의 WSS 합이라고 정의해보겠습니다. 그러면 위에서 이야기했던 Thrashing은 어떤 상황에서 발생할까요? 정답은 아래와 같습니다.

D > 물리 메모리에 존재하는 프레임의 총량일 때

당연히 모든 프로세스의 현재 워킹 셋 윈도우에서 사용하고 있는 페이지들의 수가 전체 프레임의 수보다 많으면 누군가는 프레임의 부족으로 인한 버벅임이 생깁니다. 그래서 위와 같은 상황이 발생하면 프로세스들 중에서 몇 개를 Swap-out하여 메모리를 확보해야 하는 것이죠.

 

그렇다면 매 시점마다 워킹 셋을 일일이 파악해서 쓰레싱을 막아야 할까요? 이로 인한 오버헤드가 너무 커질 것입니다.

 

따라서 이전에 페이지 교체 정책에서 다룬 Clock Algorithm처럼, 시간 간격과 Reference bit을 이용해서 워킹 셋을 정해줘야 합니다. 무슨말일까요?

 

예를 들어 윈도우의 크기가 10,000이라고 해봅시다. 그러면 인터벌 타이머를 통해 5,000 Time unit마다 인터럽트를 겁니다. 인터럽트를 걸 때, 페이지들의 Reference bit을 다른 메모리 장소에다가 복사해두고 Reference bit은 0으로 바꿉니다. 그러면 타임 인터벌이 5,000 유닛이기 때문에 10,000 Time unit이 지나면 각 페이지들은 두 번의 History Bit가 쌓이게 됩니다. 이 때, 두 번의 History Bit이 모두 0이라면, 그 시간동안 해당 명령어는 사용되지 않았기 때문에 워킹셋에 포함하지 않으면 됩니다. * 여기서 History bit은 간단하게 생각해서 해당 Time Interval 동안 기록된 Reference bit 이라고 할 수 있습니다.

 

다만, 이러한 방법도 100% 정답은 아닌데요. Time Interval을 작게 하면 그만큼 History Bit을 저장하기 위한 메모리가 소모되고 오버헤드가 커지는 단점이 있기 때문이죠. 그래서 적당한 윈도우 크기를 정하는 것이 쉬운 일은 아닙니다.

 

🗒 4. 페이지 사이즈는 어느정도가 적당한가?

이전까지의 포스팅을 보면, 메모리 관리의 기본 컨셉은 가상 메모리와 물리 메모리를 동일한 크기의 페이지와 프레임으로 쪼갠 뒤 이를 매핑하는 것이었습니다. 그렇다면 페이지와 프레임 크기(둘은 동일)는 도대체 어느 정도로 정해야 할까요?

 

우선 페이지 크기를 작게 설정한다고 해보겠습니다. 그러면 그만큼 Internal Fragmentation은 줄어들 수 있고 메모리 사용의 효율성을 높일 수 있습니다. 하지만 페이지 크기가 작으면 그만큼 개별 페이지에 대한 페이지 테이블을 들고 다니는 데 많은 메모리가 필요할 수 있고, 잦은 페이지 폴트에 의한 오버헤드가 커질 수 있습니다.

 

반면 페이지 크기를 크게 잡으면 어떨까요? 페이지 크기가 크다면 그만큼 전체적인 페이지 수는 적기 때문에 이에 필요한 페이지 테이블의 수는 적을 것입니다. 그리고 페이지 폴트를 핸들링 하는 데 드는 오버헤드도 적을 수 있겠죠. 하지만 페이지 크기가 크다는 것은 그만큼 Internal Fragmentation이 크기 때문에 단점이 존재합니다.

 

결국 두 상황은 서로 Trade-Off 관계에 있다고 볼 수 있기 때문에 정해진 정답은 없겠죠.

 

---

지금까지 정말 긴 시간동안 메모리 관리, 페이지 교체 정책, 페이지 폴트 대응과 관련된 이슈들에 대해 이야기했습니다. 

 

어렵고 헷갈릴만한 내용도 많이 있었던 것 같은데요. 제 생각에는 많은 부분의 내용이 딱 정답이 있는 것이 아니라 장점과 단점이 동시에 존재하고, 다른 부분과의 연관 때문에 독립적으로 떼놓고 볼 수 없었던 것 같습니다.

 

이제 거의 운영체제 정리의 막바지에 오다보니 운영체제는 "정답"보다 정답을 찾아가는 "과정"이 중요한 것 같습니다. 물론 저처럼 학부생의 입장에서겠지만요.

 

아무튼, 이상으로 프레임 할당과 페이지 폴트 관련 몇 가지 이슈에 대한 포스팅을 마치겠습니다!