[CS] 요구 페이징, 페이지 교체 알고리즘, 프레임 할당

Sundae·2023년 12월 11일

운영체제

목록 보기

14/15

요구 페이징, 페이지 교체 알고리즘, 프레임 할당

가상 메모리를 사용하면 남아있는 메모리보다 큰 프로세스도 실행할 수 있다. 하지만, 물리 메모리의 크기는 한정되어있기 때문에 이를 효율적으로 사용하려면 불필요한 페이지를 골라내고, 프로세스들에게 적절한 수의 프레임과 페이지를 할당할 수 있어야한다.

요구 페이징

프로세스를 메모리에 적재할 때 필요한 페이지만을 메모리에 적재하는 기법을 요구 페이징(demand paging)이라고 한다.

요구 페이징의 기본적인 단계는 다음과 같다.

CPU가 특정 페이지에 접근하는 명령어를 실행한다.
해당 페이지의 유효 비트가 1일 경우 CPU는 페이지가 적재된 프레임에 접근한다.
해당 페이지의 유효 비트가 0일 경우 페이지 폴트가 발생한다.
페이지 폴트 처리 루틴을 실행해 해당 페이지를 메모리에 적재하고 유효 비트를 1로 설정한다.
다시 1번을 수행한다.

순수 요구 페이징(pure demand paging)

만약 메모리에 아무런 페이지도 적재되지 않았다면 프로세스의 첫 명령어가 실행되는 순간부터 페이지 폴트가 발생한다. 이때, 필요한 페이지만을 메모리에 적재하는 것을
순수 요구 페이징(pure demand paging)기법이라고한다. 순수 요구 페이징은 필요한 페이지를 디스크에서 읽어와야 하기 때문에 초기 로딩 시간이 느릴 수 있지만, 필요한 페이지만 메모리에 적재하므로 메모리 사용이 효율적이다.

페이지 교체 알고리즘

페이지를 메모리에 적재하다보면, 언젠가 메모리는 가득차게 되어있다. 그렇다면 당장 실행에 필요한 페이지가 발생하면 메모리에 적재되어있던 페이지와 스와핑을 해주어야한다.
메모리에 적재되어 있던 많은 페이지 중 내보낼 페이지를 결정하는 방법을 페이지 교체 알고리즘이라고 한다.

일반적으로 페이지 폴트를 적게 일으키는 알고리즘을 좋은 알고리즘이라고 말한다. 따라서, 교체 알고리즘을 평가하기 위해선 페이지 폴트 횟수를 알아야한다.

페이지 교체 알고리즘에 대해서 알아보자.

FIFO 페이지 교체 알고리즘

FIFO 페이지 교체 알고리즘(First-In First_out Page Replacement Algorithm)은 이름 그대로 수행하는 알고리즘이다.

메모리에 가장 먼저 올라온 페이지부터 스와핑하는 방식을 사용한다.

예를 들어, CPU가 참조한 페이지들의 나열이 다음과 같다.

2 3 1 3 5 2 3 4 2 3

그리고 프로세스가 사용할 수 있는 프레임이 세 개가 있다고 가정해보자. 페이지가 세 개의 프레임에 차례대로 적재된다면 2.. 3.. 1.. 순으로 적재될 것이다. 하지만 5가 들어오는 순간부터 페이지 폴트가 발생한다. 아래의 이미지로 이해해보자.

이미지를 보면 페이지 5가 들어올 때부터 페이지 폴트가 발생한다. 이때, 스와핑이 필요한데, FIFO 페이지 교체 알고리즘은 메모리에 가장 먼저 올라온 페이지부터 스와핑 하는 방식을 사용한다고 하였다. 따라서, 2, 3, 1, 5 순으로 보조메모리로 스왑아웃되는 것을 볼 수 있다.

FIFO 페이지 교체 알고리즘은 구현이 간단하지만, 프로세스 실행 내내 사용될 내용을 포함하는 페이지가 있다면 비효율적일 수 있다. 계속 실행되어야할 페이지를 메모리에 먼저 적재되었다고 해서 내보내니말이다.

2차 기회 페이지 교체 알고리즘

2차 기회 페이지 교체 알고리즘(second chance page replacement algorithm)은 FIFO 페이지 교체 알고리즘의 부작용을 어느정도 해소한다.

기본적으로 FIFO 페이지 교체 알고리즘과 같이 가장 오래 메모리에 적재되어있던 페이지를 내보낼 페이지로 선택한다. 이때, 중요한 점은 만약 선택한 페이지의 참조 비트가 1이라면 당장 스왑아웃하지 않고 참조 비트를 0으로 만든 뒤 페이지의 적재 시간을 현재 시간으로 설정한다. 참조 비트가 1이라는 말은 CPU가 접근한 적이 있다는 뜻이므로 한 번의 기회를 더 주는 것이다.

당연히 참조 비트가 0이라면 오래 머무른 것과 동시에 사용하지 않는 페이지라고 볼 수 있으므로 스왑아웃 한다.

최적 페이지 교체 알고리즘

최적 페이지 교체 알고리즘은 앞으로 사용 빈도가 가장 낮은 페이지를 선택하여 스와핑하는 알고리즘이다.

이름 그대로 가장 낮은 페이지 폴트율을 보장하는알고리즘이다. 하지만 앞으로의 사용 빈도가 제일 낮을 페이지를 예측하기는 불가능에 가까워서 실제 구현이 어렵다. 그래서 주로 다른 페이지 교체 알고리즘의 성능을 평가하기 위해 사용된다.

LRU 페이지 교체 알고리즘

사용 빈도가 가장 '낮을' 페이지를 예측하는 것은 어렵지만, 사용 빈도가 가장 '낮은' 페이지를 교체하는 알고리즘 구현은 가능하다.

이 알고리즘을 LRU 페이지 교체 알고리즘(LRU;Least Recently Used Page Replacement Alogorithm)이라고 한다.

위 이미지를 보면 가장 적게 된 페이지 순서대로 스왑 아웃 되는 것을 볼 수 있다. 2 -> 1 -> 5 순으로 말이다.

이외에도 페이지 교체 알고리즘의 종류는 매우 다양하다.

단순 암기보다는 왜 페이지 교체 알고리즘을 사용하는지, 무엇이 좋고 대표적인 알고리즘의 아이디어는 무엇인지를 알고 있어야한다.

스레싱

잦은 페이지 폴트의 원인은 나쁜 페이지 교체 알고리즘을 사용하는 것과 더불어 프로세스가 사용할 수 있는 프레임 수에도 있다.

프레임 수가 적다면 프로세스의 페이지를 수용할 공간이 부족하기 때문에 페이지 폴트가 자주 발생한다. 반대로 프레임 수가 넉넉하다면 거의 모든 페이지를 적재할 수 있기 때문에 페이지 폴트 발생 빈도가 적다.

페이지 폴트 발생 빈도가 많다면 CPU의 이용률이 떨어져 성능 악화를 초래한다. 이를 스래싱(thrashing)이라고 한다.

멀티프로그래밍의 정도(degree of multiprogramming)

메모리에서 동시 실행되는 프로세스의 수를 멀티프로그래밍의 정도(degree of multiprogramming)라고 한다.

위 그래프에서 가로축은 동시에 실행되는 프로세스 수(멀티프로그래밍의 정도)이다. 그래프를 보다시피 멀티프로그래밍의 정도가 높다고 CPU 이용률이 비례해서 증가하진 않는다. 물론 프로세스 수가 어느 정도 증가하면 CPU 이용률이 높아지지만 일정 이상으로 늘리면 각 프로세스가 사용할 수 있는 프레임 수가 적어져 페이지 폴트가 자주 발생한다. 이는 곧 성능 악화로 이어진다.

따라서 운영체제는 각 프로세스에게 무리없이 실행하기 위한 적절한 프레임 수를 할당할 수 있어야한다.

프레임 할당

프레임 할당 방식에는 크게 정적 할당 방식과 동적 할당 방식이 있다.

정적 할당 방식에는 균등 할당(equal allocation)과 비례 할당(proportional allocation)등이 있다.

균등 할당
모든 프로세스에게 균등하게 프레임을 제공하는 방식이다. 예를 들어, 다섯개의 프로세스에게 500개의 프레임을 제공할 수 있다면 100개씩 나누어서 할당하는 방식이다.
비례 할당
크기가 상대적으로 큰 프로세스에게 프레임을 더 많이 할당하는 방식이다.

이 두 개의 프레임 할당 방식은 완벽한 방법이 아니다. 균등 할당같은 경우에는 프로세스들마다 크기가 각기 다르기 때문에 동일한 프레임을 할당할 시 비효율적일 것이다. 비례 할당은 프로세스의 크기가 클지라도 실행 시에 많은 프레임을 필요로 하지 않은 경우도 있다.

동적 할당 방식에는 크게 작업 집합 모델(working set model)을 사용하는 방식과 페이지 폴트 빈도(PFF;Page-Fault Frequency)를 사용하는 방식이 있다.

작업 집합 모델
프로세스가 일정 기간 동안 참조한 페이지 집합(작업 집합)을 기억해서 빈번한 페이지 교체를 방지한다. CPU는 참조 지역성의 원리에 의해 특정 시간 동안 몇몇 페이지에 집중적으로 참조하게 된다. 이때, 집중적으로 참조한 페이지 수만큼의 프레임을 할당하는 방식이다. 예를 들어, 5초동안 30개의 페이지를 집중적으로 참조했다면 운영체제는 그 시간동안 최소 30개의 프레임을 할당한다.
페이지 폴트 빈도
아래의 그래프를 보면 가로축은 한 프로세스에 할당된 프레임 수, 세로축은 페이지 폴트율을 나타낸다.