프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지는 않습니다. 필요한 페이지 만을 메모리에 적재하는 기법을 요구 페이징이라고 합니다.
아무런 페이지도 메모리에 적재되지 않은 채 무작정 실행하는 경우도 있습니다. 메모리에 페이지 정보가 없기 때문에 페이지 폴트가 발생하게 되고, 페이지를 적재합니다. 한 동안 페이지 폴트가 계속 발생하게 되고 실행에 필요한 페이지가 어느 정도 적재 된 이후부터는 페이지 폴트 발생 빈도가 떨어지게 됩니다.
이를 순수 요구 페이징 기법이라고 합니다.
요구 페이징 시스템이 안정적으로 동작하려면 페이지 교체와 프레임 할당이라는 문제를 해결해야 합니다. 요구 페이징 기법은 지금 당장의 실행에 필요한 페이지를 메모리에 적재하는 기법이라 했습니다. 즉 실행에 필요하지 않은 페이지는 보조기억장치로 내보내야 하는 것이죠. 메모리에 적재된 많은 페이지 중에 어떤 페이지를 내보낼 것인지 결정하는 알고리즘이 페이지 교체 알고리즘이라고 합니다.
페이지 교체 알고리즘
좋은 페이지 교체 알고리즘은 페이지 폴트를 가장 적게 일으키는 알고리즘입니다. 어떤 알고리즘이 페이지를 스왑 아웃시켰을 때 페이지 폴트가 자주 발생하면 이는 좋은 알고리즘이 아닌 것이죠.
페이지 교체 알고리즘을 제대로 이해하려면 페이지 폴트 횟수를 알 수 있어야 합니다. 이러한 페이지 폴트 횟수는 페이지 참조열을 통해 알 수 있습니다.
페이지 참조열은 위 그림 처럼, CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지 열을 의미합니다. 연속된 페이지를 생략하는 이유는 중복된 페이지를 참조하는 행위 자체는 페이지 폴트를 발생시키지 않기 때문입니다.
예를 들어 위와 같이 CPU가 2번 페이지를 여러번 참조한 경우를 가정해보겠습니다. 페이지를 최대 적재할 수 있는 공간은 3개일 경우 동일한 2를 여러번 참조했다고 해서 적재 가능한 페이지가 모잘라 페이지 폴트가 발생하지는 않습니다.
페이지 교체 알고리즘이 관심있어 하는 부분은 페이지 폴트의 발생 횟수 이기 때문에 페이지 폴트에 영향을 주지 않는 연속된 페이지에 대한 참조는 고려하지 않는 것입니다.
페이지 교체 알고리즘으로 대표적인 3가지에 대해서 지금부터 살펴보도록 하겠습니다.
1. FIFO 페이지 교체 알고리즘
FIFO(First In First Out) 알고리즘은 이름 그대로 메모리에 가장 먼저 올라온 페이지를 보조기억장치로 스왑아웃 하는 방식을 뜻합니다.
참조열이 다음과 같이 2 3 1 3 ... 순서로 있을 때 프레임이 가득 차 있기 때문에 5를 수용할 수 있는 공간이 없으므로 페이지 폴트가 발생하게 됩니다. 가장 오래 있었던 페이지는 '2' 이므로 2를 스왑아웃하고 5를 스왑인을 해줍니다.
그런데 바로 다음 페이지가 2 라서 페이지 폴트가 한번더 발생하게 됩니다. 이 때 가장 오래 있던 페이지는 3이므로 3을 스왑 아웃하고 2를 다시 스왑 인을 해줍니다.
FIFO 알고리즘 자체의 구현은 간단하지만, 보시는 바와 같이 오래 있었던 페이지가 자주 사용되는 페이지면 페이지 폴트가 많이 발생하는 것을 볼 수 있습니다. 이를 보완하기 위해 나온 페이지 교체 알고리즘이 최적 페이지 교체 알고리즘입니다.
2. 최적 페이지 교체 알고리즘
최적 페이지 교체 알고리즘은 CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘입니다. 메모리에 오래 남아 있어야 할 페이지는 자주 사용될 페이지 이고, 메모리에 업어도 될 페이지는 오랫동안 사용되지 않을 페이지입니다.
즉 최적 페이지 교체 알고리즘은 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘을 뜻합니다.
FIFO의 예제와 똑같은 경우 최적 페이지 교체 알고리즘은 페이지 폴트 횟수가 훨씬 낮아진 것을 확인 할 수 있습니다.
전체 페이지 참조열을 보면 '1'은 1번 / '2'는 3번 / '3' 은 4번 / '4'는 1번 / '5'는 1번 사용되어 질 것을 예상할 수 있습니다.
만약 2 - 3 -1 -3 이후 5가 들어선다면 스왑 아웃되는 페이지는 가장 자주 사용되지 않을 페이지인 '1'이 스왑 아웃 되는 것이죠.
최적 페이지 교체 알고리즘은 상당히 이상적인 알고리즘입니다. 다른 모든 알고리즘 통틀어 봐도 페이지 폴트 횟수가 가장 낮음을 보장해줍니다. 하지만 현실적으로 이를 구현하는 것은 어렵습니다. 앞으로 오랫동안 사용되지 않을 페이지를 예측해야 하는데, 프로세스가 어느 부분을 참조할지 미리 알기 어렵기 때문입니다.
따라서 최적 페이지 교체 알고리즘은 운영체제에서 사용하기 보다는 다른 페이지 교체 알고리즘의 이론상 성능을 평가하기 위한 목적으로 사용된다고 합니다.
3. LRU 페이지 교체 알고리즘 (Least Recently Used)
LRU 페이지 교체 알고리즘은 최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것이라는 아이디어를 토대로 만들어진 알고리즘입니다. 페이지 마다 마지막으로 사용한 시간을 토대로 최근에 가장 사용이 적었던 페이지를 교체합니다.
위의 예시를 예로 들자면, 2 - 3 - 1 - 3 이후 '5'가 들어설 떄 페이지 폴트가 발생하게 되는데, 이 때 기준으로 가장 오랫동안 사용되지 않은 페이지는 '2'가 되게 됩니다. '1' 번 페이지도 1번 사용되었지만 '2'번 페이지 보다 오래되지 않았기 때문에 최종적으로 페이지 '2'가 스왑 아웃되는 것이죠.
최적 페이지 교체 알고리즘은 가장 많이 사용 되는 페이지를 미래까지 예상하여 판단하는 반면에 LRU 페이지 교체 알고리즘은 현재 기준까지의 사용된 현황을 바탕으로 판단하는 점에 있어서 차이를 보입니다.
스레싱과 프레임 할당
페이지 폴트가 자주 발생하는데에는 페이지 교체 알고리즘 뿐만 아니라 프레임 수도 영향을 끼칩니다. 프로세스가 사용할 수 있는 프레임 수가 적어도 페이지 폴트는 자주 발생하게 됩니다. 프레임 수가 늘어나면 페이지 폴트는 감소하게 됩니다. 프레임 수가 많으면 굳이 페이즈들을 보조기억장치로 스왑아웃할 필요가 없기 때문이죠.
반대로 프레임 수가 너무 적어서 지속적인 스왑 아웃과 스왑 인을 해야 된다면, 프로세스가 실제 실행되는 시간 보다 페이징에 더 많은 시간을 쏟게 됩니다. 이처럼 실제 실행되는 시간보다 페이징에 더많은 시간을 소요하여 성능이 저해 되는 문제를 스레싱이라고 합니다.
스레싱을 그래프로 표현하면 위와 같습니다. 세로축인 CPU이용률을 통해 CPU가 얼마나 일하는지를 파악할 수 있습니다. 가로축은 메모리에 올라와있는 프로세스의 수를 나타냅니다. 메모리에서 동시에 실행되는 프로세스의 수를 멀티프로그래밍 정도라고 합니다.
위의 그래프를 통해서 동시에 실행되는 프로세스의 수를 늘린다고 CPU이용률이 그에 비례하여 증가하는 것은 아님을 알 수 있습니다. 동시에 실행되는 프로세스가 증가하면 어느 정도 CPU 이용률이 높아지지만, 필요 이상으로 늘리게 된다면 프로세스 들이 사용할 수 있는 프레임 수가 적어지게 때문에 페이지 폴트가 빈번하게 발생하게 되고, 스레싱이 생기게 됩니다.
스레싱을 예방하려면, 프로세스 마다 필요한 최소한의 프레임 수가 보장되어야 합니다. 따라서 각각의 프로세스에 프레임을 할당하는 방식이 중요합니다. 지금부터 다양한 프레임 할당 방식에 대해 살펴보겠습니다.
1. 균등 할당과 비례 할당
균등 할당은 300개의 프레임을 3개의 프로세스에 100개씩 균등하게 할당하는 방식입니다. 실행되는 포로세스의 크기가 각기 다른데 동일하게 프레임 갯수를 할당하는 것은 비합리적입니다.
따라서 나온 방식이 프로세스의 크기가 크면 프레임을 많이 할당하고 프로세스의 크기가 작으면 프레임을 작게 할당하는 비례 할당 방식입니다.
하지만 비례 할당 방식 또한 문제점을 지니고 있습니다. 프로세스의 크기가 커서 프레임을 많이 할당했는데, 실제로는 많은 프레임이 필요하지 않는 경우도 있기 때문입니다. 프로세스가 실제로 얼마나 많은 프레임을 필요로 하는지는 실제로 실행해봐야 아는 경우가 많습니다.
이를 보완하기 위해 나온 방식이 작업 집합 모델과 페이지 폴트 빈도입니다.
2. 작업 집합 모델
실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합을 작업 집합 이라고 합니다. 운영체제가 작업 집합의 크기 만큼만 프레임을 할당하는 방식이 작업 집합 모델이라고 부릅니다.
예를 들자면, CPU가 프로세스를 실행하는 동안 3초에 10개의 페이지를 집중적으로 참조했다면 해당 프로세스에는 그 순간 만큼은 10개의 프레임을 할당하는 것입니다.
3. 페이지 폴트 빈도
페이지 폴트 빈도를 바탕으로 한 프레임 할당 방식은 다음 두 개의 가정하에 생겨난 아이디어 입니다.
1. 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있다.
2. 페이지 폴트율이 너무 낮으면 그 프로세스는 너무 많은 프레임을 갖고 있다.
페이지 폴트 기반의 프레임 할당 방식을 그래프로 표현하면 위와 같습니다. 보시는 바와 같이 페이지 폴트율과 프레임 수는 반비례 관계를 보이고 있습니다.
그래프에 일정한 상한선과 하한선을 표시한다음, 페이지 폴트율이 상한선 보다 높아지면 해당 프로세스는 너무 적은 프레임을 갖고 있다고 보고 추가적인 프레임을 할당해줍니다.
반대로 페이지 폴트율이 하한선보다 떨어지면 너무 많은 프레임을 지니고 있는 것을 의미하기에 프레임을 회수합니다.
이처럼 페이지 폴트 빈도 방식은 페이지 폴트율에 상한선가 하한선을 정하고 이 범위 안에서만 프레임을 할당하는 방식이라고 이해하시면 됩니다.
이상으로 페이지 교체 알고리즘과 프레임 할당 방식에 대해 살펴보았습니다.
긴 글 읽어주셔서 감사합니다!
자료 출처
https://www.youtube.com/watch?v=nF26uioM6zU&list=PLYH7OjNUOWLUz15j4Q9M6INxK5J3-59GC&index=42
'CS > 운영체제' 카테고리의 다른 글
| 동기/비동기 블로킹/논블로킹에 대하여 (0) | 2023.08.31 |
|---|---|
| 가상 메모리란? (4) | 2023.05.07 |
| 연속 메모리 할당의 문제점은? (0) | 2023.05.03 |
| 교착 상태 (0) | 2023.04.07 |
| 프로세스 동기화란 (0) | 2023.03.15 |