[운영체제] 메모리 관리 정리 (2)

🎯  페이지 교체와 프레임 할당

 

요구 페이징이란? 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법입니다. 즉 요구되는 페이지만 적재하는 기법입니다.

 

이런 요구 페이징 시스템이 안정적으로 작동하려면 페이지 교체, 프레임 할당 이 잘 동작해야 합니다.

 

페이지 교체 알고리즘이란?

 

요구 페이징 기법으로 페이지들을 적재하다보면 언젠간 메모리가 가득찹니다. 당장 실행에 필요한 페이지를 적재하려면 적재된 페이지를 보조기억 장치로 내보내야 합니다. 이때 어떤 페이지를 내보낼지 결정하는 알고리즘이 바로 페이지 교체 알고리즘 입니다.

 

 

✅  FIFO  알고리즘

 

가장 단순한 방식의 페이지 교체 알고리즘입니다. FIFO 즉 선입 선출 방식을 이용해 메모리에 가장 먼저 올라온 페이지 부터 보조기억 장치로 내쫓는 방식입니다. 하지만 이런 방식은 성능적으로 효율적이지 않습니다. Belady`s Anomaly 가 발생할 위험성이 있습니다.

 

Belady`s Anomaly 란 페이지 프레임 수가 증가맣ㅁ에 따라 페이지 폴트(page fault) 의 수가 감소하지 않고 오히려 증가하는 경우를 ㅏ말합니다.

 

직관적으로 생각해봤을때 프레임의 개수가 많아지면 page-fault 가 줄어야 하는데 FIFO 를 사용하게 되면 그렇지 않을 위험이 있습니다.

 

 

✅  OPT(Optimal) 알고리즘

 

OPT 알고리즘은 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 알고리즘입니다. 모든 페이지 교체 알고리즘 중 page-fault 발생이 가장 적습니다. 하지만 이론상 가능할뿐 실제 구현이 거의 불가능한 알고리즘입니다. 앞으로 어떤 페이지가  사용되지 않을지 판단하는게 쉽지 않기 때문입니다.

 

이는 실제 상용화된 알고리즘이 아닌 연구 목적을 위해 사용됩니다.

 

✅  LRU (Lesat Recently User) 알고리즘

 

LRU 알고리즘은 가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘입니다. 참조된 시간을 기록하거나 스택을 이용해 구현합니다. 이는 성능이 좋아 많은 운영체제가 선택한 알고리즘입니다.

 

✅  MFU(Most Frequently User) 알고리즘

 

MFU 알고리즘은 LFU 와 반대로 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘입니다.

 

✅  CLOCK (Second Chance) 알고리즘

 

FIFO 와 LRU 의 절충안으로, 페이지마다 참조 비트를 두어 페이지가 교체되기 전에 한번의 "두 번째 기회" 를 줍니다. 참조비트가 1인 페이지는 비트를 0 으로 바꾸고 다음페이지로 넘어가며, 비트가 0 인 페이지는 교체 대상이됩니다.

 

---

 

 

실제 운영체제에서는 이러한 알고리즘들을 단독으로 사용하기 보다는 조합해 사용하는 경우가 많습니다. 예를 들어 현대의 많은 운영체제는 기본적으로 LRU 알고리즘에 기반해 구현되지만, 구현의 복잡성을 줄이기 위해 CLOCK 알고리즘과 같은 변형된 방식으로 구현하는 경우가 많습니다.

 

페이지 교체 알고리즘은 시스템의 직접적인 관련이 있기 때문에, 특정 상황에 맞는 최적의 알고리즘을 선탯하는 것이 중요합니다.

 

---

 

🎯  스레싱과 프레임 할당

페이지 폴트가 자주 발생하는 이유는 나쁜 페이지 교체 알고리즘을 사용해서 발생기도 하지만 좀 더 근본적인 이유는 프로세스가 사용할 수 있는 프레임 자체가 적어서 페이지 폴트가 발생합니다.

 

스레싱(Thrashing) 이란 컴퓨터 시스템에서 발생하는 성능 저하 현상으로, 주 기억장치 (메모리)의 페이지 교체가 너무 빈번하게 일어나면서 실제로 유용한 작업을 수행할 시간이 거의 없게되는 상황을 말합니다. 이러한 스레싱이 발생하는 이유는 다음과 같습니다.

 

(1) 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문
(2) 각 프로세스가 필요로 하는 최소한의 프레임 수를 파악하고, 프로세스들에게 적절한 프레임을 할당해 줘야합니다.

 

즉 운영체제는 각각의 프로세스들이 무리 없이 실행할 수 있을정도의 프레임 수를 파악하고 할당해줘야 합니다. 그렇다면 운영체제는 프레임을 어떻게 할당할까?

 

✅   균등 할당(equal allocation)

 

가장 단순한 할당 방식입니다. 모든 프로세스들에게 균등하게 프레임을 할당하는 방식입니다. 하지만 권장되는 방법은 아닙니다. 프로세스의 크기는 각기 다를텐데 모든 프로세스에게 동일한 프레임을 할당하면 결코 효율적으로 CPU 가 동작하지 않을겁니다.

 

✅   비례 할당 (proportional allocation)

 

프로세스의 크기를 고려해 프레임을 할당하는 방식입니다.

 

하지만 비례할당 역시 효율적인 할당 방식이 아닙니다. 만약 크기가 큰 프로세스 인데 막상 실행해보니 많은 프레임을 필요로 하지 않을 수 있고, 크기가 작은 프로세스인데 프레임을 많이 필요로 할 수 있기 때문입니다. 결국 프로세스가 필요로 하는 프레임 수 는 실행을 해봐야 정확히 파악할 수 있습니다.

 

그렇기 때문에 프로세스를 실행하는 과정에서 프레임을 결정하는 방식이 필요하게 됐는데 여기에는 크게 두가지 작업집합 모델을 활용하는 방식과 페이지 폴티 빈도를 사용하는 방식이 있습니다.

 

(균등 할당과 비례 할당은 정적 할당이라고도 부릅니다.)

✅   작업 집합 모델

 

프로세스가 실행하는 과정에서 배분할 프레임을 결정합니다. 스레싱이 발생하는 이유는 빈번한 페이지 교체 때문이기 때문에 CPU 가 특정 시간동안 주로 참조한 페이지 개수만큼만 프레임을 할당하면 됩니다.

 

작업 집합 모델(Working Set Model) 은 운영체제의 메모리 관리에서 사용되는 개념으로, 각 프로세스가 일정 기간 동안 자주 참조하는 페이지들의 집합을 정의하는 모델입니다. 이 모델은 스레싱을 방지하고 메모리 사용을 최적화하기 위해 고안됐습니다.

 

 

✅   페이지 폴트 빈도

 

프로세스가 실행하는 과정에서 배분할 프레임을 결정합니다. 

 

1. 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있다.

2. 페이지 폴트율이 너무 낮으면 그 프로세스는 너무 많은 프레임을 갖고 있다.