CPU 스케쥴링은 멀티프로그램잉 운영체제의 기반이다. CPU의 프로세스들을 빈번히 switch하면서, 운영체제는 더 생산적이게 된다. 앞서 현대 운영체제들은 프로세스가 아닌 kernel-level단계의 스레드들을 스케쥴링의 단위로 하고 있다. 하지만, "process scheduling"이라는 단어와 "thread scheduling"은 서로 혼동되어 사용된다. 이 챕터에선 "process scheduling"을 일반적인 스케쥴링 개념으로 하며, "thread scheduling"은 스레드 특화된 개념으로 지칭한다.

Chapter Objectives

• 다양한 CPU scheduling 알고리즘의 소개
• CPU scheduling을 scheduling criteria에 따른 접근
• 멀티 프로세서, 멀티 코어 스케쥴링의 issues소개
• real-time 스케쥴링 알고리즘들의 소개

5.1 Basic concepts

기존의 단일 CPU 코어시스템에서는, CPU는 한번에 1개의 프로세스를 실행한다. 다른 프로세스는 CPU가 빈 상태가 될때가지 기다려야 했다. 하지만 multiprogramming이 등장함에 따라, CPU 사용을 극대화하기 위해서, 프로세스들을 항상 실행시키려 하였다. 특히, 시간 생산적인 방법을 사용하였다. 여러 프로세스들을 메모리(ready-queue)에 존재하고, 1개의 프로세스가 wait상태가 되면, OS는 이것을 CPU에서 꺼내고 다른 프로세스를 CPU에게 준다. 멀티코어 시스템에서도, CPU를 바쁘게 하려는 개념이 적용된다. 스케쥴링은 따라서 OS에 있어서 필수적인 기능이라 할 수 있다.

5.1.1 CPU-I/O Burst Cycle

CPU 스케쥴링은 프로세스의 특성을 관찰한다. 프로세스 실행은 위와 같이 CPU실행과 I/O wait의 연속인 cycle이다. 프로세스는 이 2개의 상태를 번갈아간다. 프로세스는 CPU burst로 시작하여, I/O burst가 뒤에 오며, 이것을 번갈아간다. 마지막 CPU burst가 종료됨과 동시에 실행이 종료된다.

CPU burst의 일반적인 측정결과는 위와 같으며, 대게 short CPU burst가 많으며, large CPU burst는 적은 경향을 보인다. 특히 I/O bounded program은 short cpu burst를 가지고, CPU bounded pprogramd는 약간의 long cpu burst를 가진다.이러한 분포들은 CPU 스케쥴링 알고리즘 구현에 매우 중요하다.

5.1.2 CPU Scheduler

Scheduler는 크게 long-term scheduler와 short-term scheduler로 나뉜다. Long-term scheduler는 ready 큐에 어떤 프로세스를 정할지 고르며, short-term scheduler(CPU scheduler)는 ready queue에서 어떠한 프로세스를 CPU에 할당할지 선택한다. CPU가 idle한 상태가 되면, OS는 CPU 스케쥴러를 통해, 같은 메모리(ready queue) 상에 있는 프로세스중 다음 실행할 프로세스를 선택한다.

5.1.3 Preemptive and Nonpreemptive scheduling

CPU scheduling은 다음고 같은 4가지 상황에서 발생할 수 있다.

• 프로세스가 running 상태서 waiting 상태로 전환되는 경우(wait() by I/O request)
• 프로세스가 running 상태서 ready 상태로 전환되는 경우(interrput)
• 프로세스가 waiting 상태서 ready 상태로 전환하는 경우(I/O가 종료)
• 프로세스가 종료될때

위의 경우, 1,4에서는 새로운 프로세스가 실행을 위해서 반드시 선택되어야 한다. 하지만 2,3은 반드시는 아니다. 2의 경우 ready상태로 넘긴 것을 스케쥴링에 의한 디스패치 없이 다시 CPU로 줄 수 있다는 말.

Non-preemptive scheduling
CPU가 프로세스에 할당되면, 프로세스는 CPU를 실행이 종료되거나 ready waiting 상태가 되기 전까지 계속된다. OS가 프로세스를 중간에 뺏는것이 불가하다.

• 장점: 적은 Context-swtich 부담
• 단점: longer response time

Preemptive Scheduling
CPU에서 작동되는 프로세스를 중단시킬 수 있으며, ready state로 보내질 수 있다. Real-time OS에 적합.

• 장점: 낮은 response time, 효율적이다
• 단점: 많은 Context-switching overhead, race conditions(실행되는 순서에 의해 결과가 달라짐)

5.1.4 Dispatcher

Dispatcher는 CPU 스케쥴러에 의해 선택된 프로세스를 CPU에 부착하는 역할을 한다. Dispatcher의 역할은 다음과 같다.

• context switching
• switching to user mode
• 프로그램 연산 재개를 위한, PCB의 Program Counter에 있는 메모리 주소로 jumping시켜준다.

5.2 Scheduling Criteria

Scheduling Criteria는 CPU 스케쥴링 알고리즘을 선택하기 위한 기준으로 사용된다.

• CPU utilization : CPU를 얼마나 계속 바쁘게 하는가?
• Throughput : 수행한 일 / 단위 시간
• Turnaround time : 프로세스를 실행하는데 걸린 총 시간(레디큐 대기시간, CPU실행시간, I/O 등에 걸린 시간 포함)
• Waiting time : 레디큐에서 대기하고 있는 시간
• Response time : 프로세스가 처음으로 CPU할당 받을때까지 걸리는 시간

Max CPU-utilization, throughput // Min turnaround, waiting-time, response-time

이 챕터서는 평균 waiting-time을 기준으로 알고리즘들을 비교설명

5.3 Scheduling Algorithms

CPU 스케쥴링은 레디큐의 어떤 프로세스를 선택하여 CPU에 할당할지 결정한다. 이 섹션에서는 단일 코어 시스템(cpu1개당 1개의 프로세스 수행)을 가정하여 설명.

5.3.1 First-come, First-served Scheduling

FIFO 큐를 사용하여, 선착순으로 프로세스를 실행하는 것이다. 알고리짐이 이해하고 작성하기 쉽다는 장점이 있으나, 평균 대기 시간이 꽤 길다는 단점이 있다. 또한 아래와 같이 들어온 순서에 따라 평균 대기 시간이 달라진다.

평균 대기 시간 : (0+24+27) / 3 = 17
평균 대기 시간 : (6+0+3) / 3 = 3

FCFS는 non-preemptive한 알고리즘이다. 따라서 CPU에 프로세스가 할당되면, 그 프로세스는 동료되거나 I/O연산을 요청하기 전까지 CPU를 사용한다. 따라서 realtime OS나 interactive system에서는 문제가 발생한다. 또한 convoy effect가 발생할 수 있는데, 다른 모든 프로세스들이 하나의 거대한 프로세스가 CPU서 나오는 것을 기다리는 문제가 발생할 수 있다.

5.3.2 Shortest-Job-First Scheduling

SJF는 process의 CPU burst가 가장 작은 것부터 실행하는 알고리즘이다. 짧은 프로세스를 긴 프로세스보다 앞으로 가져옴으로써, 평균 대기 시간은 감소한다.

CPU burst prediction
CPU Scheduling에 필요한 CPU burst는 어떻게 계산하는 것인가? 이는 통계적 수치를 기반으로 한 예측값을 사용한다. 아래와 같이 exponential moving average값을 이용하여서, CPU burst length를 예측할 수 있다. The value of tn contains our most recent information, while τn stores the past history. The parameter α controls the relative weight of recent and past history in our prediction. If α = 0, then τn+1 = τn, and recent history has no effect (current conditions are assumed to be transient). If α = 1, then τn+1 = tn, and only the most recent CPU burst matters (history is assumed to be old and irrelevant). More commonly, α = 1/2, so recent history and past history are equally weighted. 주로 α를 1/2로 사용한다.

SJF는 preemptive, non-preemptive방식으로 나뉜다. 새로운 프로세스가 레디큐에 도달했을때, 선택을 해주면 된다.

• Non-preemptive SJF
  CPU가 프로세스에게 주어지면, 이것은 실행되고 있는 프로세스가 끝날때까지 허용한다.
• Preemptive SJF
  새로운 프로세스가 주어질때, remaining time이 작은 것부터 선택한다. 이 방법은 Shortest-remaining-time-first(SRJF)라고 알려져있다.

  1) Non-preemptive
  
  2) preemptive
  

장단점

• 장점 : minimum average waiting time, 레디큐의 크기도 줄어들며, 전반적인 공간 사용량도 줄어든다. Fast response time
• 단점 : Starvation. Long process는 짧은 녀석들이 없어질 때까지 CPU할당을 받지 못한다. aging으로 해결 가능하다.

5.3.3 Round-Robin Scheduling

Round-Robin 알고리즘은 FCFS와 유사하나, preemption이 프로세스 교환할때 사용되는 것이 큰 차이점이다. time-quantum 또는 time-slice라 불리는 시간단위가 정의되어야 한다. 레디큐를 FIFO 큐로 취급하면서, CPU 스케쥴러는 이 레디큐를 time quantum만큼 각 프로세스를 할당해준다. 새로운 프로세스는 레디큐 tail에 붙게 된다.

프로세스가 time quantum내에 종료되면 CPU를 다시 반납하겠지만, time quantum내에 끝나지 않으면 interupt가 발생하여, Cotext switching이 실행되고 프로세스를 레디큐에 보낼것이다. CPU 스케쥴러는 다음 프로세스를 레디큐서 불러올 것이다.

time-quantum이 4일때의 Ghantt chart는 위와 같다.

장단점

• Average turnaround time(수행시간)이 높다.
• response time이 짧아서, Interactive/time-sharing한 시스템에 적합하다
• context swtich로 인하여 CPU독점을 막는다. 하지만 너무 빈번이 일어나면, overhead가 커진다.

RR알고리즘의 성능은 time-quantum에 매우 의존적이다. 만약 너무 크면, FCFS와 다를 것이 없어질 것이다. 반면에 너무 작으면, context-switch가 매우 많아져서 overhead가 증가하여 오히려 시간이 더 걸릴수도 있다. 아래의 경우가 그 예이다.

따라서 time quantum은 context-switch를 고려하여 결정되어야 한다. 만약 context-swtich time이 time quantum의 10프로정도 되면, CPU사용시간의 10프로가 context switching에 사용된다. 현대 운영체제들에서는 copntext swtich가 대략 10 mircosecond도 안되기 떄문에, time qunatum의 매우 작은 부분이 된다. Rule-of-thumb은 보통 CPU burst의 80프로보다 time quantum이 작아야 한다.

5.3.4 Priority Scheduling

SJF알고리즘도 결국 priority-scheduling 알고리즘의 일종이다. 이 방법에서는 우선순위가 높은 프로세스부터 CPU에 할당한다.

우선순위는 내/외부적으로 정해질 수 있다. 내부적인 요인은 측정 가능한 값을 기준으로 하며, 외부적인 것은 OS외부로부터, 프로세스의 중요성에 따라 정해질 수 있다.

Piroiry Scheduling은 또한 preemptive, non-preemptive할 수 있다. 프로세스가 레디큐에 새로오면, 현재 진행중인 프로세스와의 우선순위를 비교할 수 있다. preemptive priority면, 만약 새 프로세스의 우선순위가 높다면, 진행중인 프로세스를 중단하고 새 프로세스를 CPU에 전달할 것이다. Non-preemptive의 경우 새로운 프로세스를 레디큐에 그냥 넣을 것이다.

문제점
우선순위 방식의 가장 큰 문제점은 starvation이다. 즉, 우선순위가 매우 낮은 프로세스들은 CPU할당을 받기 매우 어렵다. 이를 해결하기 위해서는 aging이라는 방법이 있으며, 기다릴수록 우선순위를 높여주는 방식이다.

RR방식과의 혼용
위와 같이 우선순위대로 실행하되, 같은 우선순위를 가진 프로세스들은 RR을 이용하여 실행하면, aging과 더불어 Starvation을 어느정도 해결할 수 있다.

5.3.5 Multilevel Queue Scheduling

Priority, RR방식 모두 단일 큐를 사용한다. 하지만 실제로는, 우선순위 기준이 다른 분리된 큐들을 두어서, 그 우선순위에 맞게 스케쥴링을 하는 것이 훨씬 쉬울 것이다. 이러한 접근방법을 multilevel queue라 한다.

multilevel queue 알고리즘은 프로세스들을 프로세스 타입에 따라 다른 큐들에 분리할 수 있다. Foreground(interactive), Background(batch)프로세스로 분리할 수 있으며, 다른 스케쥴링 방식을 필요로한다. 각각의 큐들은 다른 스케쥴링 알고리즘을 사용할 수 있다.**

5.5 Multi-Processor scheduling

지금까지는 단일 코어 시스템을 기준으로 설명하였는데, 다중 코어를 사용하게 되면, load-sharing을 사용할 수 있어, multiple threads이 병렬적으로 수행될 수 있다. 하지만 스케쥴링 문제가 더 복잡해진다.

5.5.1 Approaches to Multiple-Processor Scheduling

멀티프로세서를 지원하는 가장 표준적인 방법은 symmetric multiprocessing(SMP)며, 각 프로세서마다 self-scheduling이 되는 것이다. 각 프로세서마다 스케쥴러를 가져서, 레디큐에서 실행할 스레드를 가져오는 것이다

SMP의 스레드 스케쥴링의 2가지 전략
1. All threads may be in a common ready queue.
2. Each processor may have its own private queue of threads.

5.5.2 Multicore Processors

현대 컴퓨터는 다중 코어를 사용하여, 각

5.5.3 Load Balancing

Load balancing은 workload를 모든 프로세서에게 공정히 배분하려는 노력을 한다. Load balancing은 특히, 각 프로세마다 레디큐를 가지고 있는 경우에 중요하다. Load balancing에는 크게 2가지 전략이 있다. Push migration은 각 프로세서의 로드량을 체크한 이후에, 만약 불균형을 찾으면, 스레드를 idle or 덜 바쁜 CPU에 옮겨서 공평히 분배한다. Pull migration은 idle 프로세서가 wating processor에서 task를 가져오는 것을 말한다. 이 둘을 반대되는 개념이 아니라, 상호보완적으로 서로 병렬적으로 실행될 수 있다.

5.5.4 Processor Affinity

프로세서에서 최근에 실행되던 데이터들은 프로세서 캐시에 남아있다. 따라서 스레드에 의한 연속적인 메모리 접근은 캐시 메모리에 존재한다.('warm cache') 많은 현대 운영체제들은 스레드를 기존 실행되던 프로세서에서 다른 프로세서로 옮기려 하지 않는다. 대신에 warm cache를 이용하여 같은 프로세스 위에서 스레드를 실행하려 한다. 이를 processor affinit이라 하며, 즉, 프로세스는 계속 실행되고 있는 프로세서에 남으려고 한다.

멀티코어 프로세서는 스케쥴링 문제를 복잡하게 할 수 있다. 프로세서가 메모리에 접근할 때, 데이터를 기다리며 엄청난 시간이 걸린다. 이를 memory stall이라 하며, 최근 프로세서들은 메모리보다 훨씬 빠르기 때문에 발생한다.

Memory stall을 해결하기 위해서, 최근 프로세서에서는 코어에 멀티 스레드를 가질 수 있게 한다. 만약 하나의 하드웨어 스레드가 메모리를 기다리면, 코어는 다른 스레드로 switch한다. 아래 그림은 dual-threaded processing core를 나타낸 것이다.

인텔 프로세서는 hyper-threading이라는 용어를 사용하는데, 여러 스레드를 단일 프로세서 코어에 할당하는 것을 의미한다. i7은 보통 코어당 2개의 스레드를 할당한다.

5.6 Real-time CPU scheduling

5.6.2 Priority-Based Scheduling

real-time OS의 가장 중요한 특징으로는 즉각 반응하여 real time 처리가 가능하도록 하는 것이다. 이로인해 real-time OS는 보통 preemption이 있는 Priority 스케쥴링 알고리즘을 많이 사용한다.

진행하기에 앞서, 모든 프로세스들은 periodic하다고 가정된다. 고정된 프로세스 시간 t, deadline d, period p가 있으며, 이들의 관계는 0 ≤ t ≤ d ≤ p을 만족해야 한다. rate은 1/p(주기의 역수)로 정의된다.

5.6.3 Rate-Monotonic Scheduling

Rate-Monotonic Scheduling알고리즘은 periodic task를 priority with preemption을 이용한다. Prioriy는 period에 기반하는데, period가 짧을수록 rate이 커지며, priority가 증가한다. 반대로, period가 짧을수록, rate이 작아져서, priority가 줄어든다. 또한 각 프로세스당 진행되는 CPU burst는 같다고 가정한다.

위의 그림처럼 deadline을 맞추는 경우에는 아무런 문제가 발생하지 않는다.

하지만 위의 경우처럼 deadline을 맞추지 못하는 경우도 발생한다.

rate-monotonic 스케쥴링은 결국에 그들의 deadline을 맞추며 schedule 되는것을 보장하지 못한다.

5.6.4 Earliest-Deadline-First Scheduling

Earliest-deadline-firs(EDF)는 deadline이 급한것부터 우선순위를 높게 주어서, 스케쥴링을 한다. 프로세스는 시스템에게 deadline을 반드시 알려야 한다. rate-monotonic 방법과의 차이점으로는 고정된 priority를 갖는다는 것과, 프로세스의 cpu burst duration이 같지 않다는 점이 있다. 장점으로는 이론상 최적화된 스케쥴링을 할 수있으며, 각 프로세는 deadline을 맞추고 CPU 사용량을 100프로까지 할 수 있다는 점이다. 하지만 이것은 context switching(프로세스와 인터럽트 핸들링 사이)에 의해 현실적으로는 불가능하다.

Summary

• CPU scheduling is the task of selecting a waiting process from the ready queue and allocating the CPU to it. The CPU is allocated to the selected
process by the dispatcher.

• Scheduling algorithms may be either preemptive (where the CPU can be taken away from a process) or nonpreemptive (where a process must voluntarily relinquish control of the CPU). Almost all modern operating systems are preemptive.

• Scheduling algorithms can be evaluated according to the following five
criteria: (1) CPU utilization, (2) throughput, (3) turnaround time, (4) waiting
time, and (5) response time.

• First-come, first-served (FCFS) scheduling is the simplest scheduling algorithm, but it can cause short processes to wait for very long processes.

• Shortest-job-first (SJF) scheduling is provably optimal, providing the shortest average waiting time. Implementing SJF scheduling is difficult, however, because predicting the length of the next CPU burst is difficult.

• Round-robin (RR) scheduling allocates the CPU to each process for a time
quantum. If the process does not relinquish the CPU before its time quantum expires, the process is preempted, and another process is scheduled
to run for a time quantum.

• Priority scheduling assigns each process a priority, and the CPU is allocated
to the process with the highest priority. Processes with the same priority
can be scheduled in FCFS order or using RR scheduling.

• Multilevel queue scheduling partitions processes into several separate
queues arranged by priority, and the scheduler executes the processes in
the highest-priority queue. Different scheduling algorithms may be used
in each queue.

• Multilevel feedback queues are similar to multilevel queues, except that a
process may migrate between different queues.

• Multicore processors place one or more CPUs on the same physical chip,
and each CPU may have more than one hardware thread. From the perspective of the operating system, each hardware thread appears to be a
logical CPU.

• Load balancing on multicore systems equalizes loads between CPU cores, although migrating threads between cores to balance loads may invalidate cache contents and therefore may increase memory access times.

• Rate-monotonic real-time scheduling schedules periodic tasks using a
static priority policy with preemption