OS #4. CPU 스케줄링 (CPU Scheduling)

오랜만에 운영체제 공부를 다시 시작하게 되었다. 이번에는 CPU 스케줄링에 대해 정리해 보려고 한다.

CPU 스케줄링이란?

CPU 스케줄링은 프로세스가 작업을 수행할 때, 언제 어떤 프로세스에 CPU를 할당할지를 결정하는 작업이다. 기본적으로 멀티프로그래밍과 시분할에 기반한다. 메모리 내에 실행 준비된 프로세스 중 하나를 선택하여 CPU를 할당한다. 한정된 CPU 및 I/O장치 등의 시스템 자원을 가지고 최고의 성능을 내야 하고, 따라서 자원을 언제 어떻게 할당할지를 결정하는 문제는 정말 중요하다. CPU 스케줄링의 목표는 CPU를 최대로 활용하는 것, 즉 idle을 최소화 하는 것이다. 참고로 이 때 time quantum은 커널이 CPU를 쓰는 시간에 포함하지 않는다. 

CPU 스케줄링의 결정은 다음 두 가지 상태변화에서 이루어진다. 첫 번째는 'Running'에서 'Ready'로 상태가 바뀌는 경우이며, timer interrupt를 하는 경우를 말한다. 두 번째는 'Running'에서 'Waiting'으로 상태가 바뀌는 경우이며, I/O를 할 때가 여기에 해당된다. 스케줄링은 OS가 강제적으로 CPU 사용을 중단시키는지 여부에 따라서 크게 두 가지로 나뉘는데, 강제할 경우를 선점형 스케줄링(preemptive scheduling), 강제하지 않는 경우 비선점형 스케줄링(non-preemptive scheduling)이라고 한다. 선점형 스케줄링은 time quantum을 가지고 해당 타임 퀀텀이 지나가면, 프로세스가 아직 남아 있더라도 OS가 강제적으로 바꾸어주는 스케줄링 방식이며, 비선점형 스케줄링은 프로세스가 I/O를 하는 상황에서만 수행되는 스케줄링이다. 즉 커널이 자발적으로 I/O를 할 때 까지 기다리는 것이다. 

 

---

Scheduling Criteria

스케줄링 기준에는 여러가지가 있다. 그 중에 중요하게 여겨지는 대표적인 기준들은 아래와 같다.

1. CPU 활용률(CPU utilization) : 전체 시스템 시간 중 CPU가 작업을 처리하는 시간의 비율

2. 처리량(Throughput) : CPU가 단위 시간(1초)당 처리하는 프로세스의 갯수

3. 응답 시간(Response Time) : 프로세스가 입출력을 시작해서 첫 결과가 나오는데 걸리는 시간

4. 대기 시간(Waiting Time) : 프로세스가 Ready Queue에서 대기하는 시간의 총합

5. Turnaround Time : 프로세스가 시작해서 끝날 때 까지 걸리는 시간

스케줄러를 디자인 할 때 이상적인 스케줄러는 아마 최대의 CPU 사용률을 가지고 있으며, 최대의 처리량을 보이고, 응답시간은 최소이며, 대기시간 역시 최소인 스케줄러일 것이다. 하지만 이러한 이상적인 스케줄러는 지구상에 존재하지 않는다. 따라서 시스템의 용도에 따라서 요구사항이 달라지고, 그 요구사항에 맞는 스케줄러를 찾아야 한다. 예를 들어 슈퍼컴퓨터의 경우는 CPU 사용률이 아마 중요한 기준이 될 것이며, 개인용 컴퓨터는 응답시간이 중요한 기준이 될 수 있다.

---

Process Cycle

프로세스 수행 사이클은 일반적으로 CPU Burst와 I/O Burst가 번갈아 가면서 이루어진다.

출처 : Operating System Concept 9th ed.

CPU burst가 긴 경우는 CPU-bound 프로세스라고 하고, CPU burst가 짧은 경우는 I/O-bound 프로세스라고 한다. 어떤 종류의 프로세스가 많은지에 따라 스케줄링 기법의 효율성이 달라진다. 아래는 CPU-burst time의 빈도수를 나타낸 그래프인데, 이러한 데이터를 바탕으로 time quantum은 10ms로 설정이 되었다. 

출처 : Operating System Concept 9th ed.

 

---

Scheduling Algorithms

스케줄링 알고리즘에는 다양한 종류가 있고, 실제 OS에서는 이러한 알고리즘을 튜닝해서 성능을 개선한 후에 사용하는 경우가 많다. 그 중에 대표적인 몇 가지만 살펴보고자 한다.

FSFS(First Come First Served) Scheduling

선착순 방식의 스케줄링으로 비선점형 스케줄링이다. Ready Queue에 있는 순서대로 CPU를 할당한다. 작업의 순서에 따라서 대기 시간이 변할 수 있다.

 

SJFS(Shortest Job First Scheduling) Scheduling

가장 CPU Burst 시간이 짧은 프로세스부터 CPU에 할당하는 스케줄링 방식이다. 최소의 평균 대기 시간을 제공한다는 특징을 가지고 있다. 비선점형, 선점형 방식이 모두 가능하다.

아래는 비선점형 스케줄링 방식의 SJFS이다.

아래는 선점형 스케줄링 방식은 SJFS이다.

Priority Scheduling

프로세스에 우선순위가 있어서, 그 우선순위에 따라 CPU에 순서대로 할당하는 스케줄링 방식이다. 이 방법 역시 비선점형, 선점형이 가능하다. 우선순위가 높은 프로세스를 빠르게 처리할 수 있다는 장점이 있는 반면에, 낮은 우선순위를 가진 프로세스는 매우 늦게 수행되거나 수행되지 않을 수도 있는 기아 문제(starvation)가 발생할 수 있다.

이러한 기아 문제를 해결하기 위한 방법이 Aging 기법으로 기다리는 시간이 늘어날 수록 프로세스의 우선순위를 증가시키는 방법이다. 우선순위의 경우 정적으로, 혹은 동적으로 부여할 수가 있는데, 동적으로 부여할 경우 시스템의 응답 속도를 증가시키는 장점이 있는 반면, 오버헤드가 늘어날 수 있다는 단점을 가지고 있다.

Round Robin Scheduling

라운드 로빈 스케줄링은 CPU를 시간 단위(time quantum)로 할당하는 선점형 스케줄링 방식이다. Ready 큐를 사용하여 먼저 대기한 작업이 먼저 CPU를 사용한다. 해당 작업은 시간 단위 동안 CPU를 사용한 후에 다시 대기 큐의 가장 끝으로 배치되어 다시 할당을 기다린다. 

RR의 장점은 response time이 짧다는 점이다. 이는 Interactive 프로세스에 필요하다. 성능적인 면에서 살펴보면 시간 단위가 클 경우 FCFS 스케줄링과 비슷해 지고, 시간 단위가 만약 문맥 전환(Context Switching)에 필요한 시간보다 작을 경우는 문맥 전환이 일어날 때 마다 오버헤드가 발생하여 효율이 매우 떨어질 수 있다.

Multilevel Queue Scheduling

다단계 큐 스케줄링은 ready 큐를 여러 개 만들어 각각에 대해 다른 우선순위와 스케줄링 알고리즘을 사용하는 기법을 말한다. 예시로 Foreground 큐와 Background 큐가 있다. Foreground 큐는 Interactive한 동작이 필요한 프로세스를 위한 큐이며 RR 스케줄링 방식을 사용한다. Background 큐는 CPU 연산 작업을 주로 수행하는 프로세스를 위한 큐로 FCFS 스케줄링 방식을 사용한다. 다단계 큐 스케줄링의 한계점이 있다면, 상위 큐에 프로세스가 계속 있으면 하위 큐에 기아 현상이 발생할 수 있다.

이러한 다단계 큐 스케줄링의 한계를 극복하기 위해 고안된 방식이 다단계 피드백 큐 스케줄링(Multilevel Feedback Queue Scheduling)이다. 이 방식은 다단계 큐에서 프로세스들이 다른 큐로 이동할 수 있게 한 스케줄링 기법이다. 이 방식에서 Design choices에는 다음과 같은 요소들이 있으며 어떤 요소들을 선택하는지에 따라 성능이 바뀌게 된다.

• 큐의 개수

• 각 큐마다 스케줄링 기법

• 언제 프로세스를 한 단계 높은 큐로 옮길 것인지

• 언제 프로세스를 한 단계 낮은 큐로 옮길 것인지

아래의 그림은 3 단계 피드백 큐 스케줄링이다. Q0는 시간 단위가 8ms이고, Q1은 시간 단위가 16ms이며 Q2는 FCFS 방식이다. 새로운 프로세스가 들어오면 Q0에서 8ms 동안 수행이 되며, Q0에서 끝나지 않은 프로세스는 Q1으로 이동한다. Q1에서는 16ms동안 수행이 되며, 여기서도 종료되지 않은 경우 많은 CPU 작업이 필요한 프로세스라고 판단, Q2로 이동하여 FCFS 방식으로 수행된다.

 

---

Multiple Core Scheduling

여러 개의 코어를 사용하는 시스템의 경우 스케줄링 방식은 더욱 복잡해진다. 최근에는 멀티프로세서보다 멀티코어 방식을 선호하는 경우가 많다. 가장 큰 이유는 Scalability(확장성) 때문. 예를 들어 GPU(Graphical Processing Unit)의 경우 많은 수의 코어(ex. 4096개)를 AI 연산에서 병렬적으로 처리하는데 이러한 경우는 멀티 코어 방식이 성능적으로 유리하다.

멀티코어 스케줄링 방식에는 Load Balancing과 Cache Affinity 등이 있다.

 

---

 

참고자료

1. 고려대학교 유혁 교수님 운영체제(COSE341) 수업 자료

2. <Operating System Concepts> 9th ed. by A. Silberschatz

3. https://preamtree.tistory.com/19

4. https://cornswrold.tistory.com/127