CPU 스케줄링

CPU 버스트 시간에 따른 프로세스의 종류

기계어 명령은 다음 세 가지 명령으로 구분된다.

• CPU 내에서 수행되는 명령: CPU 내에서만 수행되므로 명령 수행 속도가 매우 빠르다. (ex, add 명령: 레지스터에 있는 두 값을 더해 레지스터에 저장)
• 메모리 접근을 필요로 하는 명령: CPU 내에서 수행되는 명령에 비해 오래 소요되지만 비교적 짧은 시간에 수행할 수 있는 명령에 해당된다. (ex, load 명령: 메모리의 데이터를 CPU로 읽어 들임, store 명령: CPU에서 계산된 결과값을 메모리에 저장)
• 입출력을 동반하는 명령: CPU나 메모리 접근 명령에 비해 아주 오랜 시간이 소요된다.

CPU 내에서 수행되는 명령과 메모리 접근을 필요로 하는 명령은 사용자 프로그램이 직접 수행할 수 있는 일반명령이다. 그러나 모든 입출력 명령은 운영체제를 통해서만 수행할 수 있는 특권명령이다.

그리고 CPU 내에서 수행되는 명령과 메모리 접근을 필요로 하는 명령은 사용자 프로그램이 직접 CPU를 가지고 수행할 수 있는 비교적 빠른 명령이다. 반면 입출력 명령은 CPU 제어권이 운영체제 커널로 넘어가며 상대적으로 매우 느리게 수행된다. 이와 같이 프로그램의 수행은 서로 다른 두 단계의 조합으로 이뤄진다. 

• CPU 버스트: 사용자 프로그램이 직접 CPU를 가지고 빠른 명령을 수행하는 단계 
• I/O 버스트: I/O 요청이 발생해 커널에 의해 입출력 작업을 진행하는 비교적 느린 단계

이를 기반으로 프로세스를 크게 CPU 바운드 프로세스와 I/O 바운드 프로세스로 나눌 수 있다.

• CPU 바운드 프로세스
  • I/O 작업을 거의 수행하지 않아 CPU 버스트가 길게 나타나는 프로세스이다.
  • 프로세스 수행의 상당 시간을 입출력 작업 없이 CPU 작업에 소모하는 계산 위주의 프로그램이 해당된다.
• I/O 바운드 프로세스
  • I/O 요청이 빈번해 CPU 버스트가 짧게 나타나는 프로세스이다.
  • 주로 사용자로부터 인터랙션을 계속 받아가며 프로그램을 수행하는 대화형 프로그램(interactive program)이 해당된다.

이와 같이 CPU를 사용하는 패턴이 상이한 여러 프로그램이 동일 시스템 내부에서 함께 실행되기 때문에 CPU 스케줄링이 필요한 것이다. 그리고 이때 CPU 스케줄링의 핵심은 I/O 바운드 프로세스에게 CPU 우선권을 부여해야 한다는 것이다.

• I/O 바운드 프로세스는 대화형 작업이므로 사용자에 대한 빠른 응답이 중요하기 때문이다. (빠른 응답)
• 만약 CPU 바운드 프로세스에게 먼저 CPU를 할당한다면, 그동안 I/O 바운드 프로세스는 CPU를 대기하며 사용자 응답 시간이 길어지고 해당 I/O 장치도 작업을 수행하지 않는 상태가 되기 때문에 비효율적이다. 반면, I/O 바운드 프로세스에게 CPU를 우선적으로 할당하면 CPU를 짧게 잠깐 사용한 후 바로 I/O 작업을 수행하기 때문에 I/O 장치의 이용률이 높아지며 그동안 CPU 바운드 프로세스가 CPU를 사용하므로 매우 효율적이다. (효율성)

CPU 스케줄링의 필요성

정리하자면  CPU 스케줄링의 필요성은 다음과 같다.

• (단일 코어라고 가정했을 때) CPU는 동시에 하나의 일만 수행할 수 있기 때문에 효율적으로 CPU를 사용하기 위한 CPU 스케줄링이 필요하다.
• CPU를 사용하는 패턴이 상이한 여러 프로그램(CPU 바운드 프로세스, I/O 바운드 프로세스)이 함께 실행되기 때문에 효율적으로 CPU를 사용하기 위한 CPU 스케줄링이 필요하다.

CPU 스케줄러 & 디스패처

• CPU 스케줄러: 준비 상태에 있는 프로세스들 중 어떤 프로세스에게 CPU를 할당할지를 결정하는 운영체제 커널의 코드이다. 
• 디스패처(dispatcher): 디스패처는 프로세스 스케줄링을 담당하는 운영체제의 코드이다. 즉, CPU 스케줄러를 통해 어떤 프로세스에게 CPU를 할당할지 결정되면, 해당프로세스에게 실제로 CPU를 이양하는 작업이 필요한데 이때 디스패처의 코드대로 수행된다. 즉 프로세스 간 문맥 교환시 디스패처의 코드가 호출된다.
  1. 디스패처는 현재 수행 중이던 프로세스의 문맥을 그 프로세스의 PCB에 저장하고
  2. 새로 선택된 프로세스의 문맥을 그 프로세스의 PCB로부터 복원한 후
  3. 그 프로세스에게 CPU를 넘기는 과정을 수행한다. 
  4. 새로운 프로세스의 문맥을 복원시킨 후에는 시스템 상태를 사용자 모드로 전환하고 사용자 프로그램에게 CPU 제어권을 넘긴다. 
  5. 그러면 사용자 프로그램은 복원된 문맥 중 프로그램 카운터로부터 현재 수행할 코드의 주소를 찾아 수행한다.
• 디스패처 지연시간(dispatcher latency): 디스패처가 하나의 프로세스를 정지시키고 다른 프로세스에게 CPU를 전달하기까지 걸리는 시간을 디스패처 지연시간라고 하며, 디스패처 지연시간의 대부분은 문맥교환 오버헤드에 해당된다.

CPU 스케줄링 방식

CPU 스케줄링 방식은 CPU를 강제로 빼앗느냐 아니냐에 따라 다음과 같이 나뉜다.

• 비선점형 방식(nonpreemptive): CPU를 획득한 프로세스가 스스로 CPU를 반납하기 전까지 CPU를 빼앗지 않는 방식이다.
• 선점형 방식(preemptive): 프로세스가 CPU를 계속 사용하기를 원하더라도 강제로 빼앗을 수 있는 방식이다. 이때 CPU를 빼앗는 방법으로는 할당시간을 부여한 후 타이머 인터럽트를 발생시키는 방법이 대표적이다. 

다음은 CPU 스케줄링에 따라 프로세스의 상태 변화와 스케줄링 방식이다.

• 실행 상태 ➡️ 봉쇄 상태 (ex, I/O 작업을 요청하는 시스템 콜) = 비선점형 방식
• 실행 상태 ➡️ 준비 상태 (ex, 타이머 인터럽트) = 선점형 방식
• 봉쇄 상태 ➡️ 준비 상태 (ex, I/O 작업 완료 후 인터럽트) = 선점형 방식
• 종료 (ex, 프로세스 종료) = 비선점형 방식

CPU 스케줄링의 성능 평가

다양한 CPU 스케줄링 기법을 평가하기 위해 여러 지표들이 사용되는데, CPU 이용률과 처리량 같은 시스템 관점의 지표와 소요시간, 대기시간, 응답시간과 같은 사용자 관점의 지표가 있다.

• CPU 이용률: 전체 시간 중 CPU가 일을 한 시간의 비율
• 처리량: 주어진 시간 동안 준비 큐에서 기다리고 있는 프로세스 중 몇 개를 마쳤는지, 즉 CPU 버스트를 완료한 프로세스의 개수
• 소요시간: 프로세스가 CPU를 요청한 시점부터 CPU 버스트가 끝날 때까지 걸린 시간, 즉 준비 큐에서 기다린 시간 + 실제로 CPU를 사용한 시간 
• 대기시간: CPU 버스트 기간 중 프로세스가 준비 큐에서 CPU를 얻기 위해 기다린 시간의 합, 즉 CPU 버스트가 끝나기까지 준비 큐에서 기다린 시간의 합
• 응답시간: 프로세스가 준비 큐에 들어온 후 첫 번째 CPU를 획득하기까지 기다린 시간

CPU 스케줄링 알고리즘

선입선출 스케줄링(First-Come First-Served:FCFS)

준비 큐에 도착한 순서대로 CPU를 할당하는 방식이다.

 

비선점형 방식으로, CPU를 먼저 요청한 프로세스에게 CPU를 먼저 할당하고, 그 프로세스가 자발적으로 CPU를 반납할 때까지 빼앗지 않는다. 

문제점

CPU 버스트가 긴 프로세스가 먼저 도착하면 CPU 버스트가 짧은 프로세스보다 먼저 도착하면, CPU 버스트가 짧은 프로세스들이 오래 기다려야 하는 콘보이 현상(Convoy effect)이 발생한다. 따라서 프로세스들의 평균 대기시간이 매우 길어진다.

• 만약 CPU 버스트가 긴 프로세스가 CPU 버스트가 짧은 프로세스 여러 개보다 먼저 준비 큐에 도착했다고 가정하자.
• 이 경우 CPU를 잠깐만 사용하고 I/O 작업을 수행할 다수의 프로세스들이 앞의 긴 작업 하나 때문에 계속 기다려야 하는 상황이 발생하여 평균 대기시간이 길어진다. 
• 또한 CPU 버스트가 짧은 여러 프로세스들이 CPU를 할당받기 위해 오랜 시간 기다리기 때문에 그 동안 I/O 장치의 이용률도 낮아지게 된다.

최단작업 우선 스케줄링(Shortest-Job First: SJF)

CPU 버스트가 가장 짧은 프로세스에게 제일 먼저 CPU를 할당하는 방식이다. CPU 버스트가 짧은 프로세스가 CPU를 먼저 사용하고 준비 큐를 빠져나가게 되면, 프로세스들이 준비 큐에서 대기하는 전체적인 시간이 줄어들게 된다. 따라서 SFJ 스케줄링 알고리즘은 평균 대기시간을 가장 짧게 하는 최적 알고리즘으로 알려져 있다.

 

SJF 알고리즘은 비선점형 방식과 선점형 방식 두 가지로 구현될 수 있다.

• 비선점형 방식: 일단 CPU를 획득하면 그 프로세스가 CPU를 자진 반납하기 전까지 CPU를 빼앗지 않는다.
• 선점형 방식: CPU 버스트가 더 짧은 프로세스가 도착하면 CPU를 빼앗아 더 짧은 프로세스에게 부여한다. 이러한 SJF의 선점형 방식을 SRTF(Shortest Remaining Time First)라고 부른다. 비선점형 방식보다 적은 평균 대기 시간을 가져, 더 최적의 방법이다.

문제점

CPU 버스트가 긴 프로세스는 준비 큐에 줄 서서 무한정 기다려야 하는 문제가 발생할 수도 있다. 이를 기아 현상(starvation)이라고 한다. 즉, SFJ 스케줄링 방법은 평균 대기시간이 가장 짧아 효율성은 좋지만, 형평성 문제가 있다.

 

또한 누가 CPU를 짧게 쓰는지 알 수 없다. 즉, 준비 큐에 들어온 프로세스의 CPU 버스트 시간을 알 수 없다. 따라서 CPU 버스트를 예측할 뿐이다. 이때 예측하는 방법은 과거의 CPU 버스트를 보고 예측한다.

우선순위 스케줄링

우선순위 스케줄링이란 준비 큐에서 기다리는 프로세스들 중 우선순위가 가장 높은 프로세스에게 제일 먼저 CPU를 할당하는 방식이다. 이때 우선순위는 우선순위 값을 통해 표시하며 우선순위 값이 작을수록 높은 우선순위를 갖는다.

 

우선순위 스케줄링도 비선점형 방식과 선점형 방식 두 가지로 구현될 수 있다.

• 비선점형 방식: 일단 CPU를 획득하면 그 프로세스가 CPU를 자진 반납하기 전까지 CPU를 빼앗지 않는다.
• 선점형 방식: 우선순위가 더 높은 프로세스가 도착하면 CPU를 빼앗아 해당 프로세스에게 부여한다. 

우선순위의 기준은 여러가지가 될 수 있다. CPU 버스트 시간을 우선순위 값으로 정의하면, 우선순위 스케줄링은 SJF 알고리즘과 동일한 의미를 가지게 된다. 반면, 시스템과 관련된 중요한 작업을 수행하는 프로세스의 우선순위를 높게 부여할 수도 있다.

문제점

우선순위 스케줄링 방식에서도 기아 현상이 발생할 수 있다. 우선순위가 높은 프로세스가 계속 도착하는 상황에서 우선 순위가 낮은 프로세스가 CPU를 얻지 못한 채 계속 기다려야 할 수 있기 때문이다.

➡️ 이러한 문제를 해결하기 위해 노화 기법(aging)을 사용할 수 있다. 노화 기법은 기다리는 시간이 길어지면 우선순위를 조금씩 높여, 언젠가는 가장 높은 우선순위가 되어 CPU를 할당받을 수 있게 해주는 방법이다.

라운드 로빈 스케줄링

라운드 로빈 스케줄링은 앞서 살펴본 스케줄링 방식들과 달리 시분할 시스템의 성질을 가장 잘 활용한 스케줄링 방식이다. 라운드 로빈 스케줄링에서는 타이머를 통해 각 프로세스가 CPU를 사용할 수 있는 시간을 제한한다. 그리고 이 시간이 경과하면 해당 프로세스로부터 CPU를 회수해 준비 큐에 줄 서 있는 다른 프로세스에게 CPU를 할당한다. 그리고 CPU를 빼앗긴 프로세스는 다시 준비 큐의 제일 뒤에 가서 줄을 선다. (선점형 방식)

• 이때 할당 시간이 너무 길면, FCFS와 같은 결과를 나타내게 된다. CPU 버스트 시간이 매우 긴 프로세스가 모든 작업을 수행할 만큼 할당 시간을 길게 설정하는 경우를 말한다.
• 반면 할당 시간이 너무 짧으면, CPU를 사용하는 프로세스가 빈번히 교체되어 문맥교환의 오버헤드가 커진다.
• 따라서 일반적으로 할당 시간을 수십 밀리초 정도의 규모로 설정한다.

이때 할당 시간이 만료되어 CPU를 회수하는 방법으로는 타이머 인터럽트를 사용하고, 만약 CPU 버스트 시간이 할당 시간보다 짧으면 CPU를 자신의 버스트 시간만큼 사용한 후 스스로 반납한다. 

장점

• 대화형 프로세스에서 빠른 응답시간을 보장(효율성)
  • 예를 들어 n개의 프로세스가 준비 큐에 있고 할당 시간이 q라고 할 때, 모든 프로세스는 (n - 1) * q 시간 이내에 적어도 한 번은 CPU를 할당받을 수 있게 된다. 즉, 스케줄링 성능 평가 기준 중 응답시간이 빠르다. 
  • 할당 시간을 수십 밀리초 규모로 설정하면 인간이 빠르다고 느낄 정도의 응답시간을 보장할 수 있기 때문이다.
• 공정한 스케줄링 방식(공정성)
  • 각 프로세스의 대기시간이 그 프로세스의 CPU 버스트 시간에 비례하기 때문에 CPU 버스트 시간이 긴 프로세스가 불이익을 당하지 않는다. 즉, CPU를 많이 쓰는 프로세스는 많이 쓰는 만큼 대기시간이 긴 것이다.  
• 여러 종류의 프로세스가 같이 실행되는 환경에서 효과적 
  • 라운드 로빈 스케줄링 방법과 FCFS 스케줄링 방법을 비교해보자.
    • FCFS에서는 CPU를 먼저 쓰고 나가는 프로세스의 경우에는 소요시간 및 대기시간이 짧아진다.
    • 반면, 라운드 로빈 스케줄링에서는 CPU를 조금씩 같이 쓰고 거의 동시에 끝나게 되어 소요시간 및 대기시간이 가장 오래 기다린 프로세스에 맞춰지게 된다.
    • 따라서 라운드 로빈 스케줄링의 응답시간은 FCFS보다 짧지만, 평균 대기시간과 소요시간은 FCFS보다 오래 걸린다.
  • 하지만 현실 상황에서 대부분의 시스템의 프로세스들은 CPU 버스트 시간이 균일하지 않고 각자 다른 CPU 버스트 및 I/O 버스트를 갖는다.
    • 따라서 이 경우 라운드 로빈 스케줄링을 적용하면 CPU 버스트 시간이 짧은 프로세스는 자신의 CPU 버스트를 빨리 끝낼 수 있고, 반대로 CPU 버스트 시간이 긴 프로세스는 상대적으로 오래 기다리며 오랜 시간 후에 CPU 버스트를 끝낼 수 있다. 즉, 프로세스의 CPU 사용량에 비례해 대기시간과 소요시간이 증가하므로 매우 합리적이다. 
    • 이에 비해 FCFS는 CPU 버스트가 긴 프로세스가 먼저 준비 큐에 도착하는 경우에는 소요시간과 대기시간이 오래 걸리며 불공정하다.

멀티레벨 큐

멀티레벨 큐는 준비 큐를 여러 개로 분할해 관리하는 방법이다. 즉 프로세스들이 CPU를 기다리기 위해 한 줄로 서는 것이 아니라 여러 줄로 서는 것이다. 멀티레벨 큐는 일반적으로 성격이 다른 프로세스들을 별도로 관리하고, 프로세스의 성격에 맞는 스케줄링을 적용하기 위해 준비 큐를 별도로 둔다.

• 일반적으로 대화형 작업을 담기 위한 전위 큐와 계산 위주의 작업을 담기 위한 후위 큐로 분할하여 운영된다.
• 전위 큐에서는 응답시간을 짧게 하기 위해 라운드 로빈 스케줄링을 사용하고, 계산 위주의 작업을 위한 후위 큐에서는 응답시간이 큰 의미를 갖지 않기 때문에 FCFS 스케줄링을 사용해 문맥교환의 오버헤드를 줄이도록 한다.

그리고 여러 개의 준비 큐에 대해서 어느 큐에 먼저 CPU를 할당할 것인지도 결정해야 한다. 큐에 대한 스케줄링으로 고정 우선순위 방식과 타임 슬라이스 방식이 있다.

• 고정 우선순위 방식
  • 전위 큐와 후위 큐를 사용하는 방식에서는 전위 큐에 있는 프로세스에게 우선적으로 CPU가 할당되고, 전위 큐가 비어있는 경우에만 후위 큐에 있는 프로세스에게 CPU가 할당된다.
  • 그러나 후위 큐에 대해서는 기아 현상이 발생할 수 있다.
• 타임 슬라이스 방식
  • 큐에 대한 기아 현상을 해소할 수 있는 방식으로, 각 큐에 CPU 시간을 적절한 비율로 할당한다.
  • 예를 들어 전체 CPU 시간 중 전위 큐에 80%, 후위 큐에 20%를 할당해 스케줄링하는 방식이다.

멀티레벨 피드백 큐

멀티레벨 피드백 큐는 CPU를 기다리는 프로세스를 여러 줄에 세운다는 측면에서 멀티레벨 큐와 동일하나, 프로세스가 하나의 큐에서 다른 큐로 이동이 가능하다는 점이 다르다. 

 

예를 들어 다음과 같은 방식이 있다.

1. 그림에서 상위에 있는 큐일수록 우선순위가 높다. 프로세스가 준비 큐에 도착하면 우선순위가 가장 높은 큐에 줄을 선다. 그러면 CPU 사용시간이 짧은 대화형 프로세스들은 우선순위가 가장 높은 큐에서 빨리 서비스받고 작업을 완료할 수 있다.
2. 그러나 CPU 버스트 시간이 긴 프로세스들은 5만큼의 시간 동안 CPU를 사용하고도 작업을 완료할 수 없기 때문에 할당시간이 10인 하위 큐로 내려가서 줄을 서게 된다.
3. 이후 하위 큐에서 본인 차례가 되어 할당 시간 10을 사용하고도 작업이 완료되지 않으면, 이 프로세스는 최하위 큐로 이동하게 되고 FCFS 스케줄링을 적용받게 된다.

이때 큐에 대한 스케줄링 방식으로는, 최상위 큐에 있는 프로세스들이 먼저 CPU를 할당받고 상위 큐가 비었을 때에만 그 하위 큐에 있는 프로세스들이 CPU를 할당받을 수 있다.

 

이 방식은 라운드 로빈 스케줄링을 한층 더 발전시켜, 프로세스의 CPU 작업시간을 다단계로 분류함으로써 작업시간이 짧은 프로세스일수록 빠른 서비스가 가능하도록 하고, 작업시간이 긴 프로세스에 대해서는 문맥교환 없이 CPU 작업에만 열중할 수 있는 FCFS 방식을 채택할 수 있게 한다.

---

Reference

• 이화여자대학교출판문화원, 운영체제와 정보기술의 원리, 반효경