[운영체제] 요구 페이징과 페이지 교체 알고리즘, 프레임 할당 정리

요구 페이징과 페이지 교체 알고리즘

물리 메모리의 크기는 한정되어 있다.

가상 메모리를 사용하면 물리 메모리보다 큰 프로세스도 실행할 수 있지만, 그렇다고 모든 페이지를 메모리에 올릴 수 있는 것은 아니다.

 

운영체제는 한정된 메모리를 효율적으로 사용하기 위해 두 가지를 결정해야 한다.

첫째, 기존에 메모리에 올라와 있는 페이지 중 어떤 페이지를 보조기억장치로 내보낼지 결정해야 한다.

둘째, 각 프로세스에게 몇 개의 프레임을 할당할지 결정해야 한다.

 

첫 번째 문제와 관련된 것이 페이지 교체이고, 두 번째 문제와 관련된 것이 프레임 할당이다.

 

요구 페이징

요구 페이징(demand paging)은 처음부터 모든 페이지를 메모리에 적재하지 않고, 실행에 필요한 페이지만 메모리에 적재하는 기법이다. 프로세스 전체를 메모리에 올리는 대신, CPU가 실제로 요구하는 페이지만 그때그때 메모리에 가져온다.

 

요구 페이징의 동작 과정은 다음과 같다.

 

1. CPU가 특정 페이지에 접근하는 명령어를 실행한다.
2. 해당 페이지가 메모리에 있다면, CPU는 그 페이지가 적재된 프레임에 접근한다.
3. 해당 페이지가 메모리에 없다면, 페이지 폴트가 발생한다.
4. 운영체제의 페이지 폴트 처리 루틴이 해당 페이지를 보조기억장치에서 메모리로 가져온다.
5. 페이지 테이블의 유효 비트를 1로 바꾼다.
6. 중단되었던 명령어를 다시 실행한다.

 

요구 페이징은 필요한 페이지만 메모리에 올리기 때문에 메모리를 효율적으로 사용할 수 있다.

 

하지만 페이지 폴트가 자주 발생하면 성능이 떨어질 수 있다. 페이지 폴트가 발생할 때마다 보조기억장치에 접근해야 하기 때문이다.

 

요구 페이징 시스템이 안정적으로 동작하려면 두 가지 문제가 해결되어야 한다.

페이지 교체
프레임 할당

 

 

페이지 교체 알고리즘

요구 페이징을 사용하면 필요한 페이지들이 계속 메모리에 적재된다.

그러다 보면 언젠가 메모리가 가득 차게 된다.
이때 새로운 페이지를 메모리에 올리려면 기존에 있던 페이지 중 하나를 보조기억장치로 내보내야 한다.

 

어떤 페이지를 내보낼지 결정하는 방법이 페이지 교체 알고리즘이다.

좋은 페이지 교체 알고리즘은 페이지 폴트 횟수를 줄이는 알고리즘이다.

 

페이지 폴트가 적게 발생한다는 것은 메모리에 필요한 페이지들이 잘 남아 있다는 뜻이다.
반대로 페이지 폴트가 자주 발생한다는 것은 내보내면 안 되는 페이지를 잘못 내보냈을 가능성이 크다.

페이지 참조열

페이지 교체 알고리즘의 성능을 비교할 때는 페이지 참조열(page reference string)을 사용한다.

페이지 참조열은 CPU가 참조하는 페이지 번호의 나열이다.

 

이때 연속해서 같은 페이지를 참조하는 경우는 보통 한 번만 적는다.

이미 메모리에 있는 같은 페이지를 연속해서 참조하면 페이지 폴트가 새로 발생하지 않기 때문이다.

 

예를 들어 다음과 같은 페이지 참조열이 있다고 하자.

2 3 1 3 5 2 3 4 2 3

 

프레임 수는 3개라고 가정하자.

이제 이 참조열을 기준으로 여러 페이지 교체 알고리즘을 살펴보자.

FIFO 페이지 교체 알고리즘

FIFO(First In First Out) 페이지 교체 알고리즘은 메모리에 가장 먼저 올라온 페이지를 가장 먼저 내보내는 방식이다.

가장 단순한 페이지 교체 알고리즘이다.

 

프레임이 3개이고 페이지 참조열이 다음과 같다고 하자.

2 3 1 3 5 2 3 4 2 3

 

처음에는 메모리가 비어 있다.

참조 2: 메모리에 없으므로 적재
[2]

참조 3: 메모리에 없으므로 적재
[2, 3]

참조 1: 메모리에 없으므로 적재
[2, 3, 1]

참조 3: 이미 메모리에 있으므로 그대로 사용
[2, 3, 1]

 

이제 5를 참조해야 한다.
하지만 프레임이 모두 차 있으므로 기존 페이지 하나를 내보내야 한다.

 

FIFO에서는 가장 먼저 들어온 2를 내보낸다.

참조 5: 2 제거, 5 적재
[3, 1, 5]

 

다음으로 2를 참조한다.
2는 이미 내보냈으므로 페이지 폴트가 발생한다. 가장 오래된 3을 내보낸다.

참조 2: 3 제거, 2 적재
[1, 5, 2]

 

이런 방식으로 가장 오래 머문 페이지를 계속 내보낸다.

 

FIFO는 구현이 쉽지만 단점이 있다.

 

메모리에 오래 있었다고 해서 앞으로 필요 없는 페이지라는 보장은 없다.
프로그램 실행 초기에 잠깐 쓰고 안 쓰는 페이지도 있지만, 프로그램 실행 내내 자주 사용되는 페이지도 있다.

자주 사용되는 페이지가 단지 먼저 들어왔다는 이유만으로 쫓겨날 수 있다.

 

 

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

FIFO의 단점을 보완한 방식이 2차 기회(second-chance) 페이지 교체 알고리즘이다.

 

기본적으로는 FIFO처럼 오래된 페이지부터 확인한다.
하지만 바로 내보내지 않고 참조 비트를 확인한다.

 

참조 비트가 1이면 CPU가 최근에 한 번이라도 참조한 적이 있는 페이지이다.
이런 페이지는 바로 내보내지 않고 한 번 더 기회를 준다.

 

참조 비트 1
최근에 참조된 적 있음
바로 내보내지 않음
참조 비트를 0으로 바꾸고 뒤로 보냄

 

참조 비트가 0이면 오래 메모리에 있었지만 최근에 참조되지 않은 페이지이다.
이런 페이지는 내보내도 괜찮다고 판단한다.

참조 비트 0
최근에 참조된 적 없음
페이지 교체 대상

 

2차 기회 알고리즘은 단순히 오래된 페이지를 내보내는 FIFO보다 조금 더 합리적이다.
최근에 사용된 페이지는 한 번 더 살려두기 때문이다.

 

 

 

 

최적 페이지 교체 알고리즘

최적 페이지 교체 알고리즘(Optimal Page Replacement)은 앞으로 가장 오랫동안 사용되지 않을 페이지를 내보내는 방식이다.

 

메모리에 오래 남아 있어야 하는 페이지는 앞으로 자주 사용될 페이지이다.
반대로 내보내도 되는 페이지는 앞으로 오랫동안 사용되지 않을 페이지이다.

 

예를 들어 페이지 참조열이 다음과 같다고 하자.

2 3 1 3 5 2 3 4 2 3

 

프레임에 [2, 3, 1]이 들어 있는 상태에서 5를 적재해야 한다고 하자.

 

이때 2, 3, 1 중 앞으로 가장 늦게 사용되거나 아예 사용되지 않는 페이지를 찾는다.

 

앞으로의 참조열은 다음과 같다.

2 3 4 2 3

 

2와 3은 다시 사용된다.
1은 앞으로 사용되지 않는다.

 

그래서 1을 내보내는 것이 가장 좋다.

1 제거, 5 적재

 

 

 

최적 페이지 교체 알고리즘은 가장 낮은 페이지 폴트율을 보장한다.

 

하지만 실제 운영체제에서 구현하기는 어렵다.
미래에 어떤 페이지가 언제 참조될지 미리 알 수 없기 때문이다.

 

그래서 최적 페이지 교체 알고리즘은 실제 구현용이라기보다, 다른 페이지 교체 알고리즘의 성능을 평가하는 기준으로 사용된다.

 

LRU 페이지 교체 알고리즘

LRU(Least Recently Used) 페이지 교체 알고리즘은 가장 오랫동안 사용되지 않은 페이지를 내보내는 방식이다.

최적 페이지 교체 알고리즘은 앞으로 가장 오랫동안 사용되지 않을 페이지를 내보낸다.

 

LRU는 과거를 기준으로 판단한다.

 

이런 가정에 기반한 방식이다.

예를 들어 프레임에 [2, 3, 1]이 들어 있고, 최근 사용 기록을 봤을 때 1이 가장 오랫동안 사용되지 않았다면 1을 내보낸다.

 

LRU는 FIFO보다 실제 사용 패턴을 더 잘 반영할 수 있다.
단순히 먼저 들어온 페이지를 내보내는 것이 아니라, 최근에 사용되었는지를 보기 때문이다.

다만 정확한 LRU를 구현하려면 각 페이지가 언제 사용되었는지 기록해야 한다.
이 기록을 관리하는 데 비용이 들 수 있다.

 

LFU 페이지 교체 알고리즘

LFU(Least Frequently Used) 페이지 교체 알고리즘은 사용 빈도가 가장 낮은 페이지를 내보내는 방식이다.

LRU가 “최근에 사용되었는가”를 기준으로 한다면, LFU는 “얼마나 자주 사용되었는가”를 기준으로 한다.

 

LRU
최근에 가장 오래 사용되지 않은 페이지를 교체

LFU
참조 횟수가 가장 적은 페이지를 교체

 

예를 들어 프레임에 다음 페이지들이 있다고 하자.

페이지 2: 참조 횟수 5회
페이지 3: 참조 횟수 1회
페이지 1: 참조 횟수 3회

 

새 페이지를 적재해야 한다면 LFU는 참조 횟수가 가장 적은 3번 페이지를 내보낸다.

 

LFU의 장점은 자주 사용되는 페이지를 메모리에 오래 남길 수 있다는 점이다.

프로그램 실행 중 반복적으로 사용되는 핵심 페이지가 있다면, LFU는 이런 페이지를 잘 보존할 수 있다.

 

하지만 단점도 있다.

과거에 많이 사용되었지만 이제는 더 이상 사용되지 않는 페이지가 계속 메모리에 남을 수 있다.

 

예를 들어 어떤 페이지가 프로그램 초기에 100번 사용되었지만 이후에는 거의 사용되지 않는다고 하자.
LFU는 이 페이지의 참조 횟수가 높다는 이유로 계속 남겨둘 수 있다.

 

반대로 최근에 새로 들어온 페이지는 참조 횟수가 낮기 때문에, 앞으로 많이 사용될 가능성이 있어도 금방 쫓겨날 수 있다.

 

이 문제를 줄이기 위해 실제 구현에서는 참조 횟수를 시간이 지나며 감소시키거나, 일정 주기마다 초기화하는 방식이 함께 사용될 수 있다.

 

 

페이지 교체 알고리즘 정리

대표적인 페이지 교체 알고리즘을 정리하면 다음과 같다.

FIFO
가장 먼저 메모리에 들어온 페이지를 교체한다.
구현은 쉽지만 자주 쓰는 페이지도 오래 있었다는 이유로 내보낼 수 있다.

2차 기회
FIFO를 기반으로 하되, 참조 비트가 1인 페이지는 한 번 더 기회를 준다.

최적 페이지 교체
앞으로 가장 오랫동안 사용되지 않을 페이지를 교체한다.
페이지 폴트율이 가장 낮지만 미래를 알아야 하므로 실제 구현은 어렵다.

LRU
가장 오랫동안 사용되지 않은 페이지를 교체한다.
최근 사용 기록을 기준으로 판단한다.

LFU
참조 횟수가 가장 적은 페이지를 교체한다.
자주 사용되는 페이지를 보호할 수 있지만, 과거 기록이 지나치게 오래 영향을 줄 수 있다.

 

 

스래싱과 프레임 할당

페이지 폴트가 자주 발생하는 이유는 크게 두 가지로 볼 수 있다.

 

첫째, 페이지 교체 알고리즘이 좋지 않아서 필요한 페이지를 자꾸 내보내는 경우이다.

둘째, 프로세스에게 할당된 프레임 수가 너무 적은 경우이다.

 

특히 두 번째 경우에는 아무리 좋은 페이지 교체 알고리즘을 사용해도 페이지 폴트가 계속 발생할 수 있다.

 

프로세스가 실행되기 위해 필요한 최소한의 페이지들이 메모리에 있어야 하는데, 프레임이 너무 적으면 필요한 페이지들이 계속 쫓겨난다.

이렇게 프로세스가 실제 실행보다 페이지 교체에 더 많은 시간을 쓰는 상태를 스래싱(thrashing)이라고 한다.

 

 

스래싱이 발생하면 CPU 이용률이 떨어진다.

 

프로세스는 CPU에서 명령어를 실행해야 하는데, 계속 페이지 폴트가 발생하면 보조기억장치에서 페이지를 가져오는 데 시간을 쓰게 된다.

 

결국 CPU는 놀게 되고, 시스템 성능이 크게 떨어진다.

 

 

 

 

동시 실행 프로세스 수와 스래싱

동시에 실행되는 프로세스 수를 늘리면 CPU 이용률이 높아질 것처럼 보인다.

 

처음에는 실제로 그럴 수 있다.
프로세스가 많아지면 CPU가 처리할 작업도 많아지기 때문이다.

 

하지만 너무 많은 프로세스를 동시에 실행하면 각 프로세스에게 돌아가는 프레임 수가 줄어든다.

 

각 프로세스가 필요한 최소 프레임 수를 받지 못하면 페이지 폴트가 급격히 증가한다.
이 지점부터는 CPU 이용률이 오히려 떨어진다.

 

이 현상이 스래싱이다.

동시 실행 프로세스 수 증가
처음에는 CPU 이용률 증가
프로세스가 너무 많아짐
각 프로세스의 프레임 부족
페이지 폴트 급증
CPU 이용률 하락

 

스래싱을 막으려면 각 프로세스가 필요로 하는 최소한의 프레임 수를 보장해야 한다.

이를 위해 필요한 것이 프레임 할당이다.

프레임 할당

프레임 할당은 각 프로세스에게 몇 개의 프레임을 나누어줄지 결정하는 문제이다.

 

프레임을 너무 적게 주면 페이지 폴트가 자주 발생한다.
프레임을 너무 많이 주면 다른 프로세스에게 줄 프레임이 부족해진다.

 

따라서 운영체제는 프로세스의 특성과 실행 상황을 고려해 적절한 수의 프레임을 할당해야 한다.

 

프레임 할당 방식은 크게 정적 할당과 동적 할당으로 나눌 수 있다.

 

정적 할당은 프로세스 실행 전에 프레임 수를 어느 정도 정해두는 방식이다.
동적 할당은 프로세스 실행 중 페이지 폴트율이나 참조 패턴을 보고 프레임 수를 조정하는 방식이다.

 

균등 할당

균등 할당(equal allocation)은 모든 프로세스에게 같은 수의 프레임을 할당하는 방식이다.

 

예를 들어 사용 가능한 프레임이 100개이고 프로세스가 5개라면, 각 프로세스에게 20개씩 할당할 수 있다.

 

균등 할당은 단순하고 이해하기 쉽다.

하지만 프로세스의 크기나 특성을 고려하지 않는다.

 

작은 프로세스와 큰 프로세스가 같은 수의 프레임을 받으면, 어떤 프로세스는 프레임이 남고 어떤 프로세스는 부족할 수 있다.

 

비례 할당

비례 할당(proportional allocation)은 프로세스의 크기에 비례하여 프레임을 할당하는 방식이다.

크기가 큰 프로세스에는 더 많은 프레임을 주고, 크기가 작은 프로세스에는 더 적은 프레임을 준다.

 

예를 들어 프로세스 A의 크기가 100이고, 프로세스 B의 크기가 300이라면 B가 A보다 더 많은 프레임을 받는 식이다.

 

비례 할당은 균등 할당보다 합리적으로 보일 수 있다.
프로세스 크기를 고려하기 때문이다.

 

하지만 프로세스 크기만으로 실제 필요한 프레임 수를 정확히 알 수는 없다.

 

크기가 큰 프로세스라도 실행 중 실제로 참조하는 페이지가 적을 수 있다.
반대로 크기가 작은 프로세스라도 짧은 시간에 많은 페이지를 참조할 수 있다.

균등 할당과 비례 할당은 모두 실행 과정을 직접 고려하지 않는 정적 할당 방식이다.

 

작업 집합 모델

정적 할당의 한계를 보완하기 위해 프로세스 실행 중 참조 패턴을 고려하는 방식이 있다.

그중 하나가 작업 집합 모델(working set model)이다.

작업 집합은 실행 중인 프로세스가 일정 시간 동안 참조한 페이지들의 집합이다.

 

스래싱이 발생하는 이유는 프로세스가 자주 사용하는 페이지들을 메모리에 충분히 올려두지 못하기 때문이다.

 

작업 집합 모델은 최근 일정 시간 동안 자주 참조한 페이지들을 기억하고, 그만큼의 프레임을 프로세스에게 할당하려는 방식이다.

 

 

예를 들어 어떤 프로세스가 최근 일정 시간 동안 다음 페이지를 참조했다고 하자.

1, 2, 3, 2, 1, 4

 

이때 작업 집합은 다음과 같다.

{1, 2, 3, 4}

 

이 프로세스가 최근에 주로 사용한 페이지는 4개이므로, 최소한 4개의 프레임이 필요하다고 볼 수 있다.

 

작업 집합을 구하려면 두 가지 정보가 필요하다.

프로세스가 참조한 페이지
시간 간격

 

시간 간격을 너무 짧게 잡으면 필요한 페이지를 충분히 반영하지 못할 수 있다.
너무 길게 잡으면 이미 필요 없어진 페이지까지 포함될 수 있다.

페이지 폴트 빈도 방식

프레임을 동적으로 할당하는 또 다른 방법은 페이지 폴트 빈도(Page Fault Frequency, PFF)를 이용하는 방식이다.

이 방식은 두 가지 가정에서 출발한다.

페이지 폴트율이 너무 높으면 프레임이 부족한 것이다.
페이지 폴트율이 너무 낮으면 프레임을 너무 많이 가진 것이다.

 

운영체제는 페이지 폴트율에 상한선과 하한선을 정한다.

 

페이지 폴트율이 상한선보다 높으면 해당 프로세스에 프레임이 부족하다고 판단한다.
그래서 프레임을 더 할당한다.

 

페이지 폴트율이 하한선보다 낮으면 해당 프로세스가 프레임을 너무 많이 가지고 있다고 판단한다.
그래서 일부 프레임을 회수할 수 있다.

 

페이지 폴트 빈도 방식은 프로세스의 실제 실행 상태를 보고 프레임 수를 조정한다는 점에서 동적 할당 방식이다.