6-5. 페이지 프레임 할당

1. 페이지 프레임 할당 정책의 중요성

가상 메모리 시스템에서 핵심적인 역할 중 하나는 프로세스에게 필요한 메모리 공간을 제공하는 것입니다. 이 메모리 공간은 페이지 단위로 나뉘어 관리되며, 실제 물리 메모리에 해당하는 페이지 프레임에 매핑됩니다. 페이지 프레임 할당은 이러한 페이지 프레임을 각 프로세스에 어떻게 할당할 것인가에 대한 정책을 의미합니다. 올바른 페이지 프레임 할당은 시스템의 효율성을 극대화하고, 성능 저하의 주요 원인인 스래싱(Thrashing)을 방지하는 데 필수적입니다.

페이지 프레임 할당 정책은 단순히 메모리 사용량을 조절하는 것 이상입니다. 이는 프로세스 간의 자원 경쟁을 관리하고, 시스템 전체의 처리량(throughput)과 응답 시간(response time)에 직접적인 영향을 미칩니다. 각 프로세스에 충분한 페이지 프레임을 할당하지 않으면, 프로세스는 필요한 페이지를 디스크에서 지속적으로 가져와야 하며, 이는 디스크 I/O 작업의 증가로 이어져 시스템 성능을 급격히 저하시킵니다. 반대로, 과도한 페이지 프레임을 할당하면 메모리 낭비가 발생하고, 다른 프로세스가 사용할 수 있는 메모리 공간이 줄어들어 시스템 전체의 효율성이 감소할 수 있습니다.

2. 페이지 프레임 할당 정책의 종류

페이지 프레임 할당 정책은 크게 세 가지로 분류할 수 있습니다. 각 정책은 프로세스의 특성과 시스템의 자원 상황에 따라 장단점을 가지며, 시스템 설계자는 이를 고려하여 적절한 정책을 선택해야 합니다.

1) 균등 할당 (Equal Allocation)

균등 할당은 모든 프로세스에게 동일한 수의 페이지 프레임을 할당하는 가장 간단한 방식입니다. 프로세스의 크기나 요구사항에 관계없이 각 프로세스는 동일한 양의 메모리를 할당받습니다.

• 장점: 구현이 간단하고, 프로세스 간의 공정성을 보장합니다.
• 단점: 프로세스의 크기가 서로 크게 다르거나, 메모리 요구량이 다를 경우 효율성이 떨어집니다. 메모리 요구량이 큰 프로세스가 페이지 부재(page fault)로 인해 성능 저하를 겪을 수 있으며, 작은 프로세스는 할당된 메모리를 충분히 활용하지 못할 수 있습니다.

2) 비례 할당 (Proportional Allocation)

비례 할당은 각 프로세스의 크기에 비례하여 페이지 프레임을 할당하는 방식입니다. 프로세스의 크기가 클수록 더 많은 페이지 프레임을 할당받습니다. 이는 프로세스의 메모리 사용량을 고려하여 할당량을 조정하므로, 균등 할당보다 효율적일 수 있습니다.

프로세스 $P_i$에 할당되는 페이지 프레임의 수 $A_i$는 다음과 같이 계산됩니다.

$$A_i = \frac{S_i}{\sum_{j=1}^{n} S_j} \times m$$

여기서,

• $S_i$는 프로세스 $P_i$의 크기 (예: 프로세스가 사용하는 총 페이지 수)
• $n$은 시스템 내의 총 프로세스 수
• $m$은 시스템에서 사용 가능한 총 페이지 프레임 수

• 장점: 프로세스 크기에 비례하여 할당되므로, 균등 할당보다 합리적입니다.
• 단점: 프로세스의 메모리 사용 패턴을 고려하지 않으므로, 페이지 부재율이 높은 프로세스에 충분한 페이지 프레임을 할당하지 못할 수 있습니다.

3) 우선순위 할당 (Priority Allocation)

우선순위 할당은 각 프로세스에 우선순위를 부여하고, 우선순위에 따라 페이지 프레임을 할당하는 방식입니다. 우선순위가 높은 프로세스에 더 많은 페이지 프레임을 할당하여, 해당 프로세스의 성능을 향상시키는 것을 목표로 합니다.

• 장점: 중요한 프로세스의 성능을 보장할 수 있습니다. 시스템의 응답성을 향상시키고, 특정 프로세스의 작업을 우선 처리할 수 있습니다.
• 단점: 우선순위가 낮은 프로세스는 메모리 부족으로 인해 성능 저하를 겪을 수 있으며, 기아(starvation) 현상이 발생할 수 있습니다. 또한, 우선순위 결정 방식에 따라 시스템의 공정성이 저해될 수 있습니다.

3. 스래싱 (Thrashing) 문제

스래싱은 시스템 성능 저하의 심각한 문제 중 하나입니다. 이는 프로세스에 할당된 페이지 프레임이 부족하여, 프로세스가 작업을 수행하는 데 필요한 페이지를 지속적으로 디스크에서 가져와야 하는 상황을 의미합니다. 그 결과, CPU는 거의 유휴 상태로 시간을 보내고, 디스크 I/O 작업량은 급증하며, 시스템 전체의 처리량은 급격히 감소합니다.

1) 스래싱 발생 원인

스래싱은 주로 다음과 같은 원인으로 발생합니다.

• 과도한 멀티프로그래밍: 시스템에 너무 많은 프로세스가 동시에 실행될 경우, 각 프로세스에 충분한 페이지 프레임을 할당하기 어려워집니다.
• 부적절한 페이지 프레임 할당 정책: 프로세스의 메모리 요구량을 제대로 반영하지 못하는 할당 정책은 특정 프로세스에 메모리 부족을 초래할 수 있습니다.
• 로컬리티 부족: 프로세스가 페이지를 참조하는 지역성(locality)이 부족할 경우, 페이지 부재율이 높아져 스래싱을 유발할 수 있습니다.

2) 스래싱 발생 시 증상

스래싱이 발생하면 다음과 같은 증상이 나타납니다.

• CPU 활용률 급감: CPU는 페이지를 디스크에서 가져오는 데 시간을 소모하므로, 실제 작업 수행 시간은 줄어듭니다.
• 디스크 I/O 작업량 급증: 페이지 부재로 인해 디스크 접근이 빈번하게 발생합니다.
• 응답 시간 증가: 사용자 요청에 대한 응답 시간이 현저히 느려집니다.
• 시스템 처리량 감소: 시스템이 처리할 수 있는 작업의 양이 줄어듭니다.

3) 스래싱 해결 방법

스래싱을 해결하기 위한 다양한 방법이 있습니다.

• 작업 부하 감소: 멀티프로그래밍 정도를 조절하여, 시스템에 실행되는 프로세스 수를 줄입니다.
• 메모리 증가: 물리 메모리의 용량을 늘려, 각 프로세스에 더 많은 페이지 프레임을 할당할 수 있도록 합니다.
• 페이지 프레임 할당 정책 개선: 페이지 부재율을 모니터링하여, 프로세스에 적절한 페이지 프레임을 할당합니다. 예를 들어, 작업 집합 모델(Working Set Model)이나 페이지 부재 빈도(Page Fault Frequency) 알고리즘을 사용하여 동적으로 할당량을 조절합니다.
• 로컬리티 향상: 프로세스의 코드와 데이터를 메모리 내에서 가깝게 위치하도록 설계합니다.

4. 작업 집합 모델 (Working Set Model)

작업 집합 모델은 스래싱 문제를 해결하기 위한 효과적인 방법 중 하나입니다. 이 모델은 각 프로세스가 일정 시간 동안 참조하는 페이지들의 집합인 작업 집합(working set) 개념을 사용합니다. 시스템은 각 프로세스에 작업 집합 크기만큼의 페이지 프레임을 할당하여, 페이지 부재율을 최소화하고 스래싱을 방지합니다.

1) 작업 집합의 정의

작업 집합은 특정 시간 윈도우 $\Delta$ 동안 프로세스가 참조하는 페이지들의 집합을 의미합니다. 즉, 시간 $t$ 시점에서 작업 집합 $WSS(t, \Delta)$는 다음과 같이 정의됩니다.

$$WSS(t, \Delta) = \{페이지 \ p \ | \ t - \Delta \le \text{페이지 \ p \ 마지막 \ 참조 \ 시간} \le t \}$$

$\Delta$는 시간 윈도우의 크기를 나타내는 파라미터로, 시스템의 성능과 메모리 사용량에 영향을 미칩니다. $\Delta$가 크면 작업 집합의 크기가 커지고, $\Delta$가 작으면 작업 집합의 크기가 작아집니다.

2) 작업 집합 기반 메모리 관리

작업 집합 모델을 기반으로 한 메모리 관리는 다음과 같은 방식으로 이루어집니다.

1. 각 프로세스의 작업 집합 크기 추정: 시스템은 각 프로세스의 페이지 참조 패턴을 분석하여, 현재 작업 집합의 크기를 추정합니다.
2. 메모리 할당: 각 프로세스에 추정된 작업 집합 크기만큼의 페이지 프레임을 할당합니다. 프로세스의 작업 집합 크기보다 적은 수의 페이지 프레임이 할당될 경우, 해당 프로세스는 메모리 부족으로 인해 활성화되지 않습니다.
3. 스래싱 방지: 작업 집합 크기보다 많은 페이지 프레임을 할당함으로써, 페이지 부재율을 낮추고 스래싱을 방지합니다.

3) 작업 집합 모델의 장단점

• 장점:

  • 스래싱을 효과적으로 방지합니다.
  • 프로세스의 실제 메모리 사용량을 기반으로 메모리를 할당하므로, 효율적인 메모리 관리가 가능합니다.
  • 단점:
  • $\Delta$ 값을 적절하게 설정해야 합니다. $\Delta$ 값에 따라 시스템 성능이 크게 달라질 수 있습니다.
  • 작업 집합 크기를 추정하기 위한 추가적인 오버헤드가 발생합니다.
  • 작업 집합을 유지하기 위한 추가적인 메모리가 필요합니다.

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

페이지 부재 빈도 (PFF) 알고리즘은 페이지 부재율을 모니터링하여, 페이지 프레임 할당량을 동적으로 조절하는 방식입니다. 페이지 부재율이 높으면 더 많은 페이지 프레임을 할당하고, 페이지 부재율이 낮으면 할당량을 줄여 메모리 사용량을 최적화합니다.

1) 페이지 부재 빈도 모니터링

PFF 알고리즘은 일정 시간 간격으로 각 프로세스의 페이지 부재율을 측정합니다. 페이지 부재율은 단위 시간당 발생하는 페이지 부재의 횟수로 정의됩니다.

2) 페이지 프레임 할당량 조절

페이지 부재율을 기반으로 페이지 프레임 할당량을 조절하는 규칙은 다음과 같습니다.

• 페이지 부재율이 높을 경우: 프로세스에 더 많은 페이지 프레임을 할당합니다. (예: 페이지 프레임 할당량 증가)
• 페이지 부재율이 낮을 경우: 프로세스에 할당된 페이지 프레임을 회수합니다. (예: 페이지 프레임 할당량 감소)
• 페이지 부재율이 적정 범위 내에 있을 경우: 할당량을 유지합니다.

3) PFF 알고리즘의 장단점

• 장점:

  • 페이지 부재율을 기반으로 메모리 할당량을 동적으로 조절하여, 스래싱을 방지하고 메모리 사용 효율을 높입니다.
  • 작업 집합 모델보다 구현이 간단합니다.
  • 단점:
  • 페이지 부재율의 적절한 임계값을 설정해야 합니다. 임계값 설정에 따라 시스템 성능이 달라질 수 있습니다.
  • 페이지 부재율 측정 및 조절을 위한 오버헤드가 발생합니다.

6. 결론

페이지 프레임 할당 정책은 가상 메모리 시스템의 성능에 매우 중요한 영향을 미칩니다. 균등 할당, 비례 할당, 우선순위 할당과 같은 다양한 정책이 존재하며, 각 정책은 시스템의 특성과 요구 사항에 따라 장단점을 가집니다. 스래싱은 페이지 프레임 할당 부족으로 발생하는 심각한 성능 저하 문제이며, 작업 집합 모델과 PFF 알고리즘과 같은 다양한 해결 방법을 통해 예방하고 해결할 수 있습니다. 시스템 설계자는 이러한 개념들을 충분히 이해하고, 시스템의 요구 사항에 맞는 적절한 페이지 프레임 할당 정책을 선택하여 시스템의 성능을 최적화해야 합니다.