[운영체제] CPU 스케줄링

패스트캠퍼스 운영체제 강의와 쉽게 배우는 운영체제 교재에 대한 TIL입니다.

 

CPU 스케줄링

CPU 스케줄링이란 어떤 작업에 CPU를 배정할지 결정하는 것이다. 컴퓨터 시스템의 효율은 어떤 프로세스에 CPU를 먼저 배정하느냐에 따라 달라지므로 CPU 스케줄링은 작업의 형평성과 효율성을 결정하는 중요한 일이다.

 

CPU 스케줄링은 규모에 따라 고수준 스케줄링, 중간 수준 스케줄링, 저수준 스케줄링으로 구분된다.

 

고수준 스케줄링

시스템 내의 전체 작업 수를 조절하는 것이다. 즉, 고수준 스케줄링 단계에서는 어떤 작업을 시스템이 받아들일지 또는 거부할지를 결정한다. 또한, 고수준 스케줄링에 따라 시스템 내에서 동시에 실행 가능한 프로세스의 총 개수가 정해진다.

 

중간 수준 스케줄링

고수준 스케줄링과 저수준 스케줄링 사이에 일어나는 스케줄링이다. 고수준 스케줄링은 프로세스를 활성화할지 말지 결정하여 전체 프로세스 수를 조절하는 방식인데, 프로세스가 활성화된 후에도 여러 가지 사정으로 시스템에 과부하가 걸릴 수 있다. 따라서 중간 수준 스케줄링은 중지(suspend)와 활성화(active)로 전체 시스템의 활성화된 프로세스 수를 조정하여 과부하를 막는다. 이때, 이미 활성화된 프로세스 중 일부를 보류 상태로 보낸다.

 

저수준 스케줄링

저수준 스케줄링은 활성화된 프로세스를 준비 상태로 보낼지, 실행 상태로 보낼지, 대기 상태로 보낼지 결정하는 것이다. 사실상 실제로 작업이 이루어지는 스케줄링이라고 볼 수 있다.

 

CPU 스케줄링의 목적

공평성
모든 프로세스가 자원을 공평하게 배정받아야 한다.

효율성
시스템 자원이 유휴 시간 없이 사용되도록 스케줄링해야 하고 유휴 자원을 사용하려는 프로세스에는 우선권을 주어야 한다.

안정성
중요 프로세스의 우선순위를 높여 먼저 작동하도록 배정함으로써 시스템 자원을 점유하거나 파괴하려는 프로세스로부터 자원을 보호해야 한다.

확장성
프로세스가 증가해도 시스템이 안정적으로 작동하도록 조치해야 한다.

반응 시간 보장
시스템은 적절한 시간 안에 프로세스의 요구에 반응해야 한다.

무한 연기 방지
특정 프로세스의 작업이 무한히 연기되어서는 안 된다.

 

프로세스 우선순위

프로세스의 우선순위가 높다는 것은 해당 프로세스가 더 빨리 자주 실행된다는 의미이다.

 

커널 프로세스와 일반 프로세스

프로세스는 크게 커널 프로세스와 일반 프로세스로 나뉜다. 이때, 커널 프로세스는 중요한 작업을 많이 하므로 일반 프로세스보다 우선순위가 높다.

 

CPU 집중 프로세스와 입출력 집중 프로세스

CPU 집중 프로세스는 CPU 버스트(CPU Burst)가 많은 프로세스이고 입출력 집중 프로세스는 저장장치에서 데이터를 복사하는 일과 같이 입출력 버스트(I/O Burst)가 많은 프로세스이다. 이때, CPU를 할당받아 실행하는 작업을 CPU 버스트, 입출력 작업을 입출력 버스트라고 한다. 입출력 집중 프로세스가 우선순위가 높아 먼저 실행 상태로 가면 입출력 요구에 의해 대기 상태로 옮겨지기 때문에 다른 프로세스가 CPU를 사용할 수 있으므로 시스템 효율이 향상된다. 따라서, CPU 집중 프로세스보다 입출력 집중 프로세스의 우선순위가 높고 이러한 경우를 사이클 훔치기라고 한다.

 

전면 프로세스와 후면 프로세스

전면 프로세스는 입력과 출력을 사용하여 사용자와 상호작용이 가능한 프로세스이고 후면 프로세스는 사용자와 상호작용이 없는 프로세스이고 일괄 작업 프로세스라고도 한다. 전면 프로세스는 사용자의 요구에 즉각 반응해야 하기 때문에 전면 프로세스의 우선순위가 후면 프로세스보다 높다.

 

 

프로세스 상태의 다중 큐

프로세스의 우선순위는 프로세스 제어 블록에 표시된다. CPU 스케줄러는 모든 프로세스 제어 블록을 뒤져서 우선순위가 가장 높은 프로세스에 CPU를 할당한다. 그러나 매번 모든 프로세스 제어 블록을 검색하려면 상당히 번거롭기 때문에 다중 큐(Multiple Queue)라는 것이 등장했다.

 

준비 상태의 다중 큐

 

 

왼쪽 그림과 같이 프로세스의 우선순위 별로 정리되어 있지 않으면 매번 우선순위가 높은 프로세스 제어 블록을 찾아야 해서 불편하다. 반면 오른쪽 그림과 같이 우선순위에 따라 여러 개의 큐를 만들면 일일이 찾지 않아도 돼 편하다.

 

이때, 준비 큐를 몇 개를 나눌지, 여러 개의 준비 큐에 있는 프로세스 중 어떤 프로세스에 CPU를 할당할지 결정하는 일은 스케줄링 알고리즘에 따라 달라진다. 또한, 프로세스의 우선순위를 배정하는 방식에는 고정 우선순위 방식과 변동 우선순위 방식이 있다. 고정 우선순위 방식은 운영체제가 프로세스에 우선순위를 부여하면 프로세스가 끝날 때까지 바뀌지 않는 방식이다. 변동 우선순위 방식은 프로세스 생성 시 부여받은 우선순위가 프로세스 작업 중간에 변하는 방식이다.

 

대기 상태의 다중 큐

 

위 그림은 같은 입출력을 기다리는 프로세스끼리 모여 있는 대기 큐를 나타낸다. 준비 상태의 다중 큐와 대기 상태의 다중 큐간에는 차이가 있다. 준비 큐는 한 번에 하나의 프로세스를 꺼내어 CPU를 할당하는 반면, 대기 큐는 여러 개의 PCB를 동시에 꺼내어 준비 상태로 옮긴다. 시스템에는 많은 입출력장치가 있기 때문에 입출력이 동시에 끝날 경우 여러 개의 인터럽트가 한꺼번에 처리되어야 하는데 이를 위해 인터럽트 벡터라는 자료구조가 사용된다.

 

대기 큐에 있는 PCB는 큐에 삽입된 순서대로 처리되지만, 작업 속도를 높이기 위해 작업 순서를 뒤바꾸는 경우가 있어 나중에 들어온 PCB가 먼저 준비 상태로 옮겨 가기도 한다.

 

 

다음은 프로세스 상태에 따른 다중 큐를 합쳐서 정리한 것이다.

 

 

 

선점형 스케줄링과 비선점형 스케줄링

운영체제에서 선점은 '빼앗을 수 있음'을 뜻하고 비선점은 '빼앗을 수 없음'을 뜻한다. 따라서, 선점형 스케줄링(Preemptive Scheduling)은 어떤 프로세스가 CPU를 할당받아 실행 중이더라도 운영체제가 CPU를 강제로 빼앗을 수 있는 스케줄링 방식이고 비선점형 스케줄링(Non-preemptive Scheduling)은 어떤 프로세스가 CPU를 점유하면 다른 프로세스가 이를 빼앗을 수 없는 스케줄링 방식이다.

 

선점형 스케줄링 방식은 인터럽트 처리 같이 현재 실행 중인 작업을 중단하고 다른 프로세스가 CPU를 사용할 수 있는 방식이고, 비선점형 스케줄링 방식은 프로세스가 종료되거나 자발적으로 대기 상태에 들어가기 전까지는 계속 CPU를 사용할 수 있는 방식이다. 이를 통해, 과거의 일괄 작업 시스템에서 사용하던 방식이 비선점형 스케줄링 방식이고, 현대의 시분할 시스템에서 사용하는 방식이 선점형 스케줄링 방식임을 유추해 볼 수 있다.

 

스케줄링 알고리즘

스케줄링 알고리즘의 종류는 여러 가지이므로 선택 기준은 당연히 얼마나 효율적으로 스케줄링을 하느냐일 것이다. 스케줄링 알고리즘의 성능을 비교할 때는 주로 평균 대기 시간을 본다. 아래는 CPU 알고리즘을 평가 기준들이다.

 

대기 시간: 프로세스가 준비 큐에 도착 후 실행되기 전까지 대기하는 시간
응답 시간: 프로세스가 첫 작업을 시작한 후 첫 번째 출력(반응)이 나오기까지 걸리는 시간
실행 시간: 프로세스 작업이 시작된 후 종료되기까지 걸리는 시간
반환 시간: 대기 시간을 포함하여 실행이 종료될 때까지 걸리는 시간, 즉 프로세스의 준비 큐 도착부터 종료까지 걸리는 시간

 

다음은 여러 종류의 스케줄링 알고리즘을 보자. 각 스케줄링 알고리즘은 아래 표처럼 크게 선점형인지 비선점형인지로 나뉠 수 있다.

 

 

FCFS 스케줄링(First Come First Served)

준비 큐에 도착한 순서대로 CPU를 할당하는 비선점형 방식으로, 선입선출 스케줄링이라고도 한다. 초기 일괄 작업 시스템에서 사용되던 스케줄링 알고리즘이다. 준비 큐가 하나라 모든 프로세스의 우선순위가 동일하다. 이 스케줄링 알고리즘은 처리 시간이 긴 프로세스가 CPU를 차지하면 다른 프로세스들은 하염없이 기다리느라 시스템의 효율성이 떨어지는데, 이를 콘보이 효과라고 한다. 결국, CPU 이용 시간이 긴 프로세스가 문제이므로 CPU 이용 시간이 짧은 작업부터 스케줄링하는 SJF 스케줄링이 등장하게 된다.

 

SJF 스케줄링(Shortest Job First)

준비 큐에 있는 프로세스 중에서 실행 시간이 가장 짧은 작업부터 CPU를 할당하는 비선점형 방식으로, 최단 작업 우선 스케줄링이라고도 한다. 작은 작업을 먼저 실행하기 때문에 시스템의 효율성은 좋아진다. 하지만, 현대의 프로세스는 사용자와 빈번하게 상호 작용하기 때문에 프로그램 실행 시간을 파악하기 어렵기 때문에 이 알고리즘을 사용하기 힘들다. 또한, SJF 알고리즘은 공평성에 위배된다. SJF 알고리즘을 사용하면 어떤 프로세스는 CPU 할당이 계속 연기될 수 있는데 이를 기아 상태(Starvation)라고 한다.

 

이때, 기아 상태는 에이징(Aging)으로 완화할 수 있다. 에이징은 프로세스가 양보할 수 있는 상한선을 정하는 방식이다. 프로세스가 자신의 순서를 양보할 때마다 나이를 한 살씩 먹어 최대 몇 살까지만 양보하도록 규정하는 방식이다. 하지만, 에이징 값을 어떤 기준으로 정할 것인지가 문제라 이 방법에는 한계가 있다.

 

HRN 스케줄링(Highest Response Ratio Next)

SJF 스케줄링에서 발생할 수 있는 기아 상태를 해결하기 위해 만들어진 비선점형 알고리즘으로, 최고 응답률 우선 스케줄링이라고도 한다. SJF의 스케줄링의 우선순위 판단 기준이 프로세스의 실행 시간이었다면, HRN은 대기 시간과 CPU 사용 시간, 즉 실행 시간을 고려하여 스케줄링하는 방식이다. 다음은 HRN 스케줄링에서 우선순위를 정하는 기준이다.

 

 

HRN 스케줄링은 SJF 스케줄링의 기아 상태는 완화하였지만, 여전히 공평성이 위배되어 많이 사용되지는 않는다.

 

 

라운드 로빈 스케줄링(Round Robin)

한 프로세스가 할당받은 시간(타임 슬라이스) 동안 작업을 하다가 완료하지 못하면 준비 큐의 맨 뒤로 가서 자기 차례를 기다리는 방식이다. 선점형 알고리즘 중 우선순위가 적용되지 않은 가장 단순한 방식으로, 프로세스들이 작업을 완료할 때까지 계속 순환하면서 실행된다.

 

 

FCFS 스케줄링에 비해 당연히 콘보이 효과가 줄어들지만, 선점형 방식의 문맥 교환 오버헤드까지 추가되면 평균 대기 시간이 더 크게 나올 수 있다.

 

SRT 스케줄링(Shortest Remaining Time)

SJF 스케줄링과 라운드 로빈 스케줄링을 혼합한 방식으로 최소 잔류 시간 우선 스케줄링이라고도 한다. 이 방식은 SJF 스케줄링의 선점형 버전이라고 할 수 있다. SRT 스케줄링은 기본적으로 라운드 로빈 스케줄링을 사용하지만, CPU를 할당받을 프로세스를 선택할 때 남은 작업 시간이 가장 적은 프로세스를 선택한다. 이때, 먼저 CPU를 할당받아 실행되고 있는 프로세스가 있더라도 준비 큐에 작업 시간이 더 적은 프로세스가 오면 현재 실행되고 있는 프로세스를 대기 상태로 보내고 작업 시간이 더 적은 프로세스가 CPU를 할당받게 한다.

 

 

SJF 스케줄링과 평균 대기 시간을 비교해 보면 SRT 스케줄링의 평균 대기 시간이 짧다. 하지만, SJF 스케줄링과 마찬가지로 운영체제가 프로세스 종료 시간을 예측하기 어렵고 기아 상태가 일어나기 때문에 잘 사용하지 않는다.

 

 

다단계 큐 스케줄링(Multi-Level Queue)

우선순위에 따라 준비 큐를 여러 개 사용하는 방식이다. 프로세스는 운영체제로부터 부여받은 우선순위에 따라 해당 우선순위의 큐에 삽입된다. 각 우선순위 큐는 라운드 로빈 방식으로 운영되므로 프로세스가 큐에 삽입되는 것만으로도 우선순위 큐에서의 PCB 우선순위가 결정된다. 우선순위는 고정 우선순위를 사용하며, 상단 우선순위 큐에 있는 모든 프로세스의 작업이 끝나야 다음 우선순위 큐의 작업이 시작된다.

 

 

우선순위가 높은 상위 큐 프로세스의 작업이 끝나기 전에 하위 큐 프로세스의 작업을 할 수가 없고 하위 큐 프로세스가 실행되고 있을 때 상위 큐 프로세스가 도착하면 대기 상태로 보내고 상위 큐 프로세스를 실행한다. 이때, 우선순위가 높은 프로세스 때문에 우선순위가 낮은 프로세스의 작업이 연기되는데, 이러한 문제를 해결하기 위해 제안된 것이 다단계 피드백 큐 스케줄링이다. 다단계 큐 스케줄링에 에이징 기법이 적용된 스케줄링 기법이라고 생각하면 된다.

 

다단계 피드백 큐 스케줄링(Multi-Level Feedback Queue)

 

 

다단계 큐 스케줄링과의 차이점은 다단계 피드백 큐 스케줄링에서는 프로세스가 CPU를 사용한 후에는 프로세스의 우선순위가 낮아진다. 다시 말해, CPU를 사용한 후의 PCB는 원래의 큐로 되돌아가지 않고 우선순위가 하나 낮은 큐의 끝으로 들어간다. 물론 프로세스의 우선순위가 낮아진다고 할지라도 커널 프로세스가 일반 프로세스의 큐에 삽입되지는 않는다.

 

또 다른 특징은 우선순위에 따라 타임 슬라이스의 크기가 다르다는 것이다. 다단계 피드백 큐 스케줄링에서는 어렵게 얻은 CPU를 좀 더 오랫동안 사용할 수 있도록 우선순위가 낮아질수록 해당 큐의 타임 슬라이스가 커진다. 결국 다단계 피드백 큐 스케줄링의 마지막 큐, 즉 우선순위가 가장 낮은 프로세스는 FCFS 스케줄링 방식처럼 동작한다.

 

마지막으로, 다단계 피드백 큐 스케줄링의 우선순위는 변동 우선순위 방식을 사용하고, 오늘날 운영체제가 CPU 스케줄링을 할 때 일반적으로 사용하는 방식이다.