[메모리 관리] 요구 페이징의 페이지, 프레임 관리 기법 (+ 페이지 교체, 프레임 할당)

 

 

 

---

 

요구 페이징은 무엇이며, 페이지와 프레임은 어떻게 관리할까?

 

 

---

 

 

 

 

요구 페이징 (Demand Paging)

 

--

요구 페이징은

프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하는 것이 아니라

필요한 페이지만을 메모리에 적재하는 기법이다.

즉, 실행 요구에 필요한 페이지만 적재하는 기법이다.

 

가상 메모리를 통해 작은 물리 메모리보다 큰 프로세스도 실행할 수 있지만,
그래도 여전히 물리 메모리의 크기는 한정되어 있다.
(결국 실행에 필요한 페이지들은 물리 메모리에 적재되어야 하기 때문)

운영체제는 프로세스들이 한정된 메모리를 효율적으로 이용하기 위해서
기존에 메모리에 적재된 불필요한 페이지를 선별하여 보조기억장치로 내보낼 수 있어야 하고,
프로세스들에 적절한 만큼의 프레임을 할당하여 페이지를 할당할 수 있게 해야 한다.

 

 

요구 페이징의 기본적인 흐름

1. CPU가 특정 페이지에 접근 (명령어 실행)
2. 해당 페이지가 메모리에 있는 경우(유효 비트 = 1)
   CPU는 해당 페이지가 적재된 프레임으로 접근
3. 해당 페이지가 메모리에 없는 경우(유효 비트 = 0)
   "페이지 폴트" 발생
4. 만약 "페이지 폴트"발생 시 처리 루틴 수행 (해당 페이지를 메모리에 적재하고 유효 비트를 1로 지정)
5. 다시 1번부터 반복

 

어떠한 페이지도 메모리에 적재하지 않은 상태로 무작정 실행부터 한 경우
프로세스의 첫 명령어를 실행하는 순간부터 "페이지 폴트"가 계속 발생되며,
"페이지 폴트" 처리 루틴으로 인해 어느 정도 적재된 이후부터는 "페이지 폴트"발생 빈도가 낮아진다.

이러한 경우를 "순수 요구 페이징 (Pure Demand Paging)" 기법이라고 부른다.

 

 

안정적인 요구 페이징 시스템을 위해 해결해야 하는 2가지 문제

• 페이지 교체  :  메모리 공간이 부족할 때 발생하는 문제 (메모리에 페이지들로 꽉 참)
• 프레임 할당  :  각 프로세스에게 얼마나 많은 프레임을 할당할지 결정하는 문제

--

 

 

 

 

페이지 교체 알고리즘

 

--

요구 페이징 기법으로 페이지들을 적재하다 보면 메모리가 가득 차게 된다.
만약 당장 실행에 필요한 페이지를 적재해야 한다면
메모리에 이미 적재된 페이지를 보조기억장치로 내보내서 새로 적재할 공간을 만들어 줘야 한다.

이때 적재된 페이지들 중에서 어떤 페이지를 내보내는지 결정하는 방법이
"페이지 교체 알고리즘"이다.

 

일반적으로 "페이지 폴트"를 가장 적게 발생시키는 알고리즘이 가장 좋은 알고리즘이다.
"페이지 폴트"가 발생하면 보조기억장치로부터 필요한 페이지를 가져와야 하는 하기 때문에
메모리에 적재된 페이지를 바로 가져오는 것보다 느려지기 때문이다.

"페이지 참조열 (Page Reference String)"을 통해
"페이지 폴트"의 발생 횟수를 파악하면 해당 알고리즘이 좋은지 판단할 수 있다.

"페이지 참조열"은
CPU가 참조하는 페이지들 중에서 연속된 페이지를 생략한 페이지열을 의미한다.

만약 CPU가 2, 2, 3, 6, 6, 2, 7, 7번 페이지를 순서대로 접근했다면
2, 3, 6, 2, 7번 순서열이 "페이지 참조열"이 된다.

연속된 페이지를 생략하는 이유는
중복으로 페이지를 참조하는 행위는 "페이지 폴트"를 발생시키지 않기 때문이다.
즉, "페이지 참조열"에 나열된 개수가 "페이지 폴트"의 발생 횟수라고 생각하면 된다.

 

 

대표적인 페이지 교체 알고리즘

• FIFO 페이지 교체 알고리즘  (First-In First-Out Page Replacement Algorithm)
• 최적 페이지 교체 알고리즘 (Optimal Page Replacement Algorithm)
• LRU 페이지 교체 알고리즘 (Least Recently Used Page Replacement Algorithm)

 

 

 

FIFO 페이지 교체 알고리즘

가장 간단한 알고리즘으로

가장 먼저 메모리(프레임)에 적재된 페이지부터 내보내는 방식이다.

즉, 가장 오래 머물러있던 페이지부터 보조기억장치로 내보낸다.

 

1. [2, 3, 1, 3]까지는 빈 공간이 있거나 이미 적재되어 있기 때문에 "페이지 폴트"가 발생하지 않는다.
2. [5]를 적재하기 위해 적재된 페이지 중에서 가장 오랫동안 메모리에 적재된 [2]를 내보내고 적재한다.
3. [2]를 적재하기 위해 적재된 페이지 중에서 가장 오랫동안 메모리에 적재된 [3]를 내보내고 적재한다.
4. ...

 

구현이 간단하지만 좋다고는 판단할 수 없다.
프레임(메모리)에 가장 오래 머물러 있는 페이지더라도
아직 사용하고 있는 페이지일 수 있기 때문이다.

 

 

 

최적 페이지 교체 알고리즘

CPU에 의해 참조되는 횟수를 고려하는 알고리즘이다.

자주 사용하는 페이지일수록 메모리에 자주 할당되고,

잘 사용하지 않는 페이지일수록 메모리에 덜 할당될 것이므로

애초에 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 알고리즘이다.

즉, 앞으로(미래에) 가장 덜 사용하는 페이지를 보조기억장치로 내보낸다.

 

 

1. [2, 3, 1, 3]까지는 빈 공간이 있거나 이미 적재되어 있기 때문에 "페이지 폴트"가 발생하지 않는다.
2. [5]를 적재하기 위해 앞으로 남은 "페이지 참조열" [2, 3, 4, 2, 3]를 참고하여 가장 덜 사용할 페이지인 [1]를 내보낸다.
3. ...

 

교체 알고리즘들에 비해 비교적 "페이지 폴트" 발생 빈도가 가장 낮으며 가장 이상적인 방법이지만,
앞으로 오랫동안 사용되지 않을 페이지를 예측하는 것이 어렵기 때문에 실제로 구현하기 어렵다.

 

 

 

LRU 페이지 교체 알고리즘

"최적 페이지 교체 알고리즘"과 반대로

앞으로(미래)가 아닌 지금까지(과거) 가장 오래 사용하지 않은 페이지를 교체하는 알고리즘이다.

즉, 여태까지 적재한 페이지들 중에서 가장 예전에 적재한 페이지를 보조기억장치로 내보낸다.

 

 

1. [2, 3, 1, 3]까지는 빈 공간이 있거나 이미 적재되어 있기 때문에 "페이지 폴트"가 발생하지 않는다.
2. [5]를 적재하기 위해 지금까지 적재한 "페이지 참조열" [2, 3, 1, 3]을 참고하여
   가장 예전에 적재한 페이지인 [2]를 내보낸다.
3. ...

 

페이지가 얼마나 자주 사용되는지를 고려하므로 FIFO보다 효율적이라고 볼 수 있지만
각 페이지의 사용 이력을 추적해야 하기 때문에 추가적인 메모리 및 계산 자원이 필요한다.

 

일반적으로 "LRU 페이지 교체 알고리즘"을 자주 사용하고
간단한 시스템에서는 "FIFO 페이지 교체 알고리즘"을 사용할 수 있으며,
다른 알고리즘의 비교대상으로는 "최적 페이지 교체 알고리즘"을 기준으로 비교한다.

--

 

 

 

 

스래싱(Thrashing)과 프레임 할당

 

--

"페이지 폴트"가 자주 발생하는 이유에는

나쁜 페이지 교체 알고리즘을 사용하는 것도 있지만

조금 더 근본적인 이유는

프로세스가 사용할 수 있는 프레임 수가 적기 때문이다.

(적재할 메모리(프레임) 공간이 적다면 페이지 교체 알고리즘이 좋더라도 "페이지 폴트"가 자주 발생할 수밖에 없다.)

 

프레임이 부족하여 "페이지 폴트"가 자주 발생  ->  프로세스 실행이 계속 끊기게 되어 CPU의 이용률이 떨어짐

 

 

스래싱은

위 내용처럼 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저하되는 문제를 의미한다.

 

 

스래싱이 발생하는 근본적인 원인은

각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문이다.

 

만약 프로세스 A를 무리 없이 실행하기 위해서는 최소 10개의 프레임이 필요하지만

5개의 프레임만 할당할 수 있다면 해당 프로세스는 "페이지 폴트"가 자주 발생할 것이다.

즉, 스래싱 발생 위험이 높아진다.

 

그래서 운영체제는 각 프로세스들이 무리 없이 실행할 수 있는 최소한의 프레임 수를 파악하고

적절하게 프레임을 할당할 수 있어야 한다.

 

프레임 할당 방식 종류

• 정적 할당 방식
• 동적 할당 방식

 

정적 할당 방식 종류

• 균등 할당 (Equal Allocation)
• 비례 할당 (Proportional Allocation)

 

동적 할당 방식 종류

• 작업 집합 모델 (Working Set Model)
• 페이지 폴트 빈도 (PFF, Page-Fault Frequency)

 

 

균등 할당은

프로세스들에게 동일한 수의 프레임을 할당하는 방식이다.

예시로 3개의 프로세스와 300개의 프레임이 존재하면

각 프로세스는 100개의 프레임을 할당받는다.

실행되는 프로세스들의 크기는 각기 다르기 때문에
동일한 프레임의 개수로 할당하는 것은 비합리적이다.

 

 

비례 할당은

프로세스들의 크기에 비례하여 프레임을 할당하는 방식이다.

(크기가 크면 많은 프레임을, 작으면 적은 프레임을 할당받는다.)

프로세스의 크기가 커서 많은 프레임을 할당받았지만
막상 실행해 보니 사용하는 프레임의 수가 적은 경우가 존재하고,
반대로 프로세스 크기가 작지만 많은 프레임을 사용하는 경우도 존재하기 때문에
이 또한 완벽한 방식은 아니다.

 

 

균등 할당과 비례 할당처럼 프로세스를 실행하기 전에

정적으로 프레임을 할당하면 변수가 많이 생기게 된다.

(실행을 해봐야 얼마나 많은 프레임이 필요한지 알 수 있기 때문이다.)

 

그래서 프로세스를 실행하는 과정에서 배분할 프레임의 수를 결정하는 방식인

"동적 할당 방식"을 사용하는 방법도 있다.

 

 

작업 집합 모델은

프로세스가 주기적으로 사용하는 페이지들의 집합을 추적하여,

해당 집합을 메모리에 유지하는 방식으로 페이지 교체를 최소화하는 모델이다.

각 프로세스가 실제로 필요로 하는 페이지만 메모리에 유지하여 자원을 효율적으로 사용할 수 있으며,
동으로 프로세스의 메모리 요구량을 반영하는 장점이 있지만
작업 집합을 정확히 추적하는 것이 복잡할 수 있다.

 

 

페이지 폴트 빈도(PFF)는

페이지 폴트가 발생하는 빈도를 모니터링하여 프레임 할당을 조절하는 방법이다.

실시간으로 메모리 할당을 조절할 수 있어 효율적이고,
페이지 폴트가 자주 발생하는 프로세스에 더 많은 프레임을 할당하여 성능을 향상시키는 장점이 있지만
페이지 폴트 빈도를 정확하게 추적하고 적절한 상한값과 하한값을 설정하는 것이 어렵다.

--