페이지 교체 알고리즘과 프레임 할당

 

 

페이지 교체 알고리즘에 가상 메모리와 페이징 기법에 대해 학습하시는 것을 추천드립니다.

가상메모리(Virtual Memory)와 페이징 기법(Paging)

 

 

요구 페이징

가상 메모리를 통해 물리 메모리보다 큰 프로세스도 실행할 수 있게 됐습니다. 그렇지만 여전히 물리 메모리의 크기는 한정되어 있고 운영체제는 프로세스들이 한정된 메모리를 효율적으로 이용할 수 있도록 페이지를 교체해야 합니다. 여기서 페이지 교체는 페이지 인/아웃에 해당하는 것으로 실행에 필요한 페이지를 보조기억장치에서 꺼내오고, 당장 실행에 필요 없는 페이지는 메모리에서 보조기억장치로 내보내는 것을 뜻합니다.

프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법을 요구 페이징(Demand Paging)이라고 합니다. 그리고 요구 페이징 시스템이 안정적으로 작동하려면 페이지 교체와 프레임 할당 문제를 해결해야 합니다. 요구 페이징 기법으로 페이지들을 적재하다 보면 메모리가 가득 차게 되고, 메모리에 적재된 많은 페이지 중 어떤 페이지를 내보내는 것이 적절한지 판단해야 합니다. 이를 페이지 교체 알고리즘이라고 합니다.

 

 

페이지 교체 알고리즘

페이지 교체 알고리즘에서 가장 중점을 두어야 할 것은, 페이지 폴트(Page fault)입니다. 페이지 폴트를 가장 적게 일으키는 알고리즘이 좋은 알고리즘으로 평가됩니다. 페이지 폴트가 자주 발생했다는 말은 "보조기억장치로 내쫓을 페이지를 잘못 골랐다"는 뜻으로, 컴퓨터 성능을 저하시킵니다.

그렇기 때문에 페이지 교체 알고리즘을 이해하려면 페이지 폴트 횟수를 알고 있어야 하며, 페이지 폴트 횟수는 페이지 참조열(Page reference string)을 통해 알 수 있습니다. 페이지 참조열은 PU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지 열을 의미합니다.

// CPU가 참조하는 페이지
2 2 2 3 5 5 3 3 7

// 페이지 참조열
2 3 5 3 7

연속된 페이지를 생략하는 이유는 연속된 페이지에서는 더 이상 페이지 폴트가 생기지 않기 때문입니다.

 

FIFO 페이지 교체 알고리즘

FIFO는 First In First Out으로 가장 단순한 방식입니다. 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식입니다. 

프로세스가 사용할 수 있는 프레임은 3개로 가정하겠습니다. 처음 페이지는 2번이고 프레임에 2번이 적재됩니다. 이후 3번 1번 순차대로 적재가 됩니다. 그리고 다시 3번을 참조했을 때는 이미 프레임에 3번이 있으므로 페이지 폴트는 없습니다. 그리고 5번을 참조해야 하기 때문에 보조기억장치에서 가져와야 합니다. 현재 프레임에 2,3,1 페이지들이 있으므로 그중 어떤 페이지를 내쫓아야 합니다. FIFO에서는 오래 머물렀던 페이지를 내쫓기 때문에 2번을 내쫓습니다. 

FIFO는 프로그램 실행 내내 사용될 내용을 포함하고 있는 경우에는 페이지 폴트가 많이 납니다. 오래 머물렀지만 계속해서 실행되어야 하는 페이지들은 페이지 아웃되면 안되니까요. 결국 FIFO는 그다지 좋은 페이지 교체 알고리즘은 아닙니다.

 

최적 페이지 교체 알고리즘

이론적으로 가장 이상적인 페이지 교체 알고리즘으로, 미래에 사용되지 않을 페이지를 미리 예측하여 교체합니다. 결국 CPU가 자주 참조하는 페이지는 오래 남고, 자주 참조되지 않은 페이지는 내쫓는 방식입니다. 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘입니다.

위 예제에서 5번 페이지를 적재할 때 이미 프레임 안에 있는 2,3,1번 페이지 중 가장 오랫동안 사용하지 않을 페이지는 1번 페이지입니다. 따라서 1번을 내쫓습니다. 그리고 4번 페이지를 적재할 때 현재 페이지의 2,3,5번 페이지 중 가장 오랫동안 사용하지 않을 페이지는 5번 페이지입니다. 따라서 5번을 내쫓고 4번을 적재합니다.

앞서 FIFO알고리즘의 4번 페이지 폴트에 비해 최적 페이지 교체 알고리즘은 2번 페이지 폴트를 발생시킵니다. 이처럼 최적 페이지 교체 알고리즘은 가장 낮은 페이지 폴트율을 보장합니다. 그러나 앞으로 오랫동안 사용되지 않을 페이지인지를 예측하기 쉽지 않기 때문에 구현이 어려운 단점이 있습니다. 따라서 최적 페이지 교체 알고리즘도 다른 알고리즘의 성능을 평가하기 위한 비교군으로 간주되는 이론적 알고리즘입니다.

 

LRU 페이지 교체 알고리즘

LRU(Least Recently Used) 페이지 교체 알고리즘은 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘입니다. 각 페이지에 접근할 때마다 해당 페이지의 사용 시간을 업데이트하고, 교체할 때는 사용 시간이 가장 오래 전인 페이지를 선택합니다. 구현이 복잡할 수 있지만, 교체 성능이 좋습니다. 앞선 최적 페이지 교체 알고리즘은 가장 오래 사용되지 않을 페이지를 교체하는 것이며 LRU 페이지 교체 알고리즘은 가장 오래 사용되지 않은 페이지를 교체하는 것입니다.

5번 페이지를 적재할 때 2,3,1번 페이지 중 가장 오랫동안 사용하지 않은 페이지는 2번 페이지입니다(2번은 처음 말고는 쓰인적이 없습니다). 따라서 2번을 내쫓습니다. 그리고 2번 페이지를 적재할 때 5,3,1번 페이지 중 가장 오랫동안 사용하지 않은 페이지는 1번 페이지입니다. 따라서 1번을 내쫓습니다.

대표적인 페이지 교체 알고리즘을 알아봤습니다. 이외에도 수 많은 페이지 교체 알고리즘이 있습니다. 우리는 페이지 교체 알고리즘이 무엇이며 왜 해야 하는지, 어떤 알고리즘이 좋은 페이지 교체 알고리즘인지에 대해 중점을 두면 됩니다.

 

 

스래싱과 프레임 할당

페이지 폴트가 자주 발생하는 이유는 나쁜 페이지 교체 알고리즘을 사용해서 발생할 수도 있지만 프로세스가 사용할 수 있는 프레임 자체가 적어서 발생하기도 합니다. 오히려 후자가 더 많은 빈도를 보입니다. 만약 프레임이 무한한 컴퓨터라면 적재될 페이지도 무한하기 때문에 페이지 교체가 필요 없고, 페이지 폴트도 발생하지 않습니다. 반대로 페이지가 하나인 컴퓨터는 페이지를 교체할 때마다 페이지 폴트가 발생하게 됩니다.

 

 프레임 자체가 부족한 컴퓨터는 잦은 페이지 폴트로 인해 실행 흐름이 자주 끊기고 성능이 저하됩니다. 그렇기 때문에 메모리가 작은 컴퓨터에 비해 메모리가 큰 컴퓨터가 성능이 좋다고 하는 것입니다. CPU가 작업을 하느라 바쁜 게 아니라 페이지 교체를 하느라 바쁜 경우를 스래싱이라고 합니다. 다시 말하면 스래싱은 프로세스가 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저하되는 문제를 일컫습니다.

스레싱을 그래프로 표현하면 위와 같습니다. 가로축의 멀티프로그래밍의 정도는 메모리에 올라와 있는 프로세스의 수에 비례합니다. 즉 메모리에 올라와 있는 프로세스와 CPU이용률이 비례해서 증가하는 것이 아님을 나타내고 있습니다. 프로세스를 필요 이상으로 늘리면 각 프로세스들이 사용할 수 있는 프레임 수가 적어지기 때문에 페이지 폴트가 빈번히 발생해서 CPU이용률이 떨어집니다. 이 지점이 스래싱이 발생하는 지점입니다.

그렇기 때문에 운영체제는 각 프로세스들이 원활히 실행할 수 있을 정도의 프레임 수를 파악하고 할당해줘야 합니다.

정적 프레임 할당

균등 할당
프레임 할당 방식 중 균등 할당 방식을 알아보면, 모든 프로세스들에게 균등하게 프레임을 할당하는 방식입니다. 총 300개 프레임 할당 가능한 메모리라면 세 개의 프로세스들에게 100개씩 프로세스를 할당하는 방식입니다.

비례 할당
비례 할당 방식은 프로세스의 크기별로 할당하는 방식입니다. 크기가 큰 프로세스들에게는 더 많은 프레임을, 크기가 작은 프로세스들에게는 더 적은 프레임을 할당합니다. 만약 크기가 큰 프로세스인데 실행해 보니 많은 프레임을 필요로 하지 않는 다면 어떻게 될까요? 정적 프레임 할당 방식은 프로세스의 실행과 무관한 방식입니다. 프로세스의 실행 중 요구되는 프레임 사항을 알기 위해선 동적 할당 방식을 택해야 합니다.

동적 프레임 할당

작업 집합 모델
CPU가 특정 시간 동안 주로 참조한 페이지 개수만큼만 프레임을 할당하는 방식입니다. 프레임이 100개인 메모리 중 CPU가 페이지를 골고루 참조하는 것이 아닌 특정 시간 동안 집중적으로 몇몇개의 페이지만 참조하게 됩니다. 그렇게 되면 페이지 교체가 많이 일어나지 않습니다. CPU가 메모리를 참조할 때 그 주변 메모리를 자주 참조하는 것을 기반한 아이디어입니다.

페이지 폴트 빈도
페이지 폴트 빈도는 두 개의 가정에서 생겨난 아이디어입니다. 첫 번째는 "페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있다." 두 번째는 "페이지 폴트율이 너무 낮으면 그 프로세스가 너무 많은 프레임을 갖고 있다."입니다. 즉, 프로세스가 실행하는 과정에서 페이지 폴트율을 보고 프레임을 더 많이, 더 적게 할당하는 방식입니다. 

 

 

---

 

 

참조: 혼자공부하는 컴퓨터구조+운영체제