[OS] CPU Scheduling

[ Basic Concept ]

OS는 CPU의 사용 효율을 늘리기 위해 여러 개의 프로세스를 한 번에 실행시키는 멀티프로그래밍을 한다. 하나의 CPU 코어에서 여러 개의 프로세스를 동시에 실행시키기 위해서는 time sharing(시분할)을 해야하는데, 이때 언제 어떤 프로세스에게 CPU를 할당할 것인지 정해야 한다. OS가 어떤 프로세스를 CPU에 할당할 것인지 정하는 과정을 CPU Scheduling(CPU 스케줄링) 이라고 한다.

 

프로세스가 CPU를 점유하고 있는 시간(running state)을 CPU burst라고 하며, I/O event를 대기하고 있는 시간(waiting or ready state)을 I/O burst라고 한다. CPU burst가 많은 프로세스를 CPU-bounded process라고 하며 I/O burst가 많은 프로세스를 I/O-bounded process라고 하는데, 아래 그래프를 보면 burst 지속기간이 긴 CPU-bounded process보다 burst 지속기간이 짧지만 자주 바뀌는 I/O-bounded process가 많은 것을 확인할 수 있다. 이를 통해 CPU 스케줄링을 하여 시분할을 할 경우 CPU 사용 효율이 좋아진다는 것을 알 수 있다.

 

CPU Scheduler & Dispatcher

• CPU Scheduler
  : selects a process from the processes in memory that are ready to execute
• Dispatcher
  : a module that gives control of the CPU's core to the process selected by the CPU scheduler
• dispatch latency
  : the time to stop one process and start another running

ready queue에 있는 프로세스 중 CPU를 할당할 프로세스를 고르는 것을 CPU 스케줄링이라고 하며, 이러한 역할을 하는 것을 scheduler(스케줄러)라고 한다. 스케줄러의 의해 선택된 프로세스에게 CPU 코어를 넘겨주는 즉, context switching을 해주는 것을 dispatch(디스페치)라고 하며, 이를 dispatcher 모듈이 담당한다. context switching을 하면 즉, 실행 중이던 프로세스의 PCB를 저장하고 실행시킬 프로세스의 PCB를 가져오는 과정에서 일정 시간이 소요된다. 그 시간을 dispatch latency라고 한다. 

 

Preemptive vs Non-Preemptive

• preemptive scheduling(선점형 스케줄링)
  : a process can be preempted by the scheduler
• non-preemptive scheduling(비선점형 스케줄링)
  : a process keeps the CPU until it releases it, either by terminating or by switching to the waiting state

스케줄링 방식에는 두 가지가 있다. 선점형 스케줄링의 경우 스케줄러가 CPU의 통제권을 갖는다. 즉 CPU에 프로세스가 할당되어 있더라도 이를 강제로 중단시키고 다른 프로세스에게 CPU를 할당할 수 있다. 반면 비선점형 스케줄링의 경우 프로세스가 스스로 다음 프로세스에게 CPU를 넘겨주는 방식이다. 프로세스가 종료하거나 I/O 이번트 발생 등으로 프로세스가 스스로 CPU 점유를 끝낼 때까지 해당 프로세스가 CPU를 점유하며 스케줄러가 개입할 수 없다/

---

[ Scheduling Criteria ]

• CPU utilization ↑
  : how busy the CPU is
• Throughput ↑
  : the number of processes completed per time unit
• Turnaround time ↓
  : how long it takes to execute a process, from the time of submission to the rime if completion
• Waiting time ↓
  : the sum of periods that a process spends waiting in ready queue
• Response time ↓
  : the time it takes to start responding

스케줄링의 목표는 CPU의 사용효율을 가능한 높이는 것이다. 또한 단위 시간 내에 일을 끝내는 프로세스의 수(throughput)을 높이는 것 역시 중요하다. 이를 위해서는 프로세스가 레디 큐에서 대기한 시간부터 작업을 마칠 때까지 걸리는 시간(turnaround time)을 줄여야 한다. turnaround time을 줄이기 위해서는 레디 큐에서 대기하고 있는 시간(waiting time)을 줄여야 한다. (waiting time을 줄여 turnaround time을 줄이면 자연스럽게 CPU utilization과 thoughput을 높일 수 있다.) 추가적으로 UI와 같은 경우 프로세스가 처음 CPU를 할당받기까지의 시간(response time)을 중요하게 보기도 한다. (클릭했을 때 바로 반응이 나와줘야 함)

정리하면 스케줄링의 목표는 위 5가지이며, CPU utilization, throughput, turnaround time, waiting time, response time을 기준으로 스케줄링 알고리즘을 평가한다.

 

---

[Scheduling Algorithms ]

스케줄링 알고리즘에는 대표적으로 FCFS, SJF, SRTF, RR 4 가지가 있다.

FCFS

• First-Come, First-Served
  먼저 들어온 프로세스가 먼저 실행되는 방식이다. 가장 간단한 방식의 알고리즘으로 FIFO queue를 이용해 쉽게 구현할 수 있다.
• non-preemptive
• The average waiting time under FCFS is generally not minimal and vary substantially if the processes' CPU-burst vary greatly.
  프로세스 처리 순서 즉, 레디 큐에 들어오는 순서에 따라 성능이 크게 달라질 수 있다.
• Convoy Effect(콘보이 효과, 똥차 효과)
  CPU-burst 시간이 긴 프로세스가 먼저 올 경우, 그 뒤에 오는 프로세스는 불필요하게 긴 시간을 대기해야 하며, 이로 인해 average waiting time이 증가한다. 즉 성능이 떨어지게 된다. 이를 콘보이 효과라고 한다.

ex 1) 

+------------------------------+------+------+
|              p1              |  p2  |  p3  |
+------------------------------+------+------+
0                             15     18      21

process	burst time	waiting time	turnaround time	response time
p1	15	0	15	0
p2	3	15	18	15
p3	3	18	21	18
total	21	33	54	33

  → average waiting time: 11

 

ex 2)

+------+------+------------------------------+
|  p1  |  p2  |             p3               |
+------+------+------------------------------+
0      3      6                              21

process	burst time	waiting time	turnaround time	response time
p1	3	0	3	0
p2	3	3	6	3
p3	15	6	21	6
total	21	9	30	9

 

  → average waiting time: 3

 

SJF

• Shortest-Job-First
  프로세스 수행시간이 짧은 순서에 따라 처리된다. 레디 큐에 있는 프로세스 중 burst time이 가장 작은 프로세스가 다음에 실행된다.
  만약 burst time이 동일한 프로세스가 있을 경우 FCFS로 먼저 들어온 프로세스부터 실행된다.
• provably optimal, but there is no way to know the length of next CPU burst.
  주어진 프로세스에 대해 가장 짧은 waiting time을 보여주기 때문에 최적 알고리즘이라고 할 수 있지만, 레디 큐에 있는 프로세스의 CPU-burst 시간을 정확히 알 수 없다.
  → 해당 프로세스의 이전 CPU burst 기록을 바탕으로 다음 CPU burst 시간을 예측한다.
      이때, 이전 CPU burst 길이의 지수적 평균을 이용하는데 이는 가장 최근의 burst time을 더 중요하게 보기 위함이다.
• non-preemptive

ex)

+------+------------+--------------+----------------+
|  p4  |     p1     |       p3     |       p2       |
+------+------------+--------------+----------------+
0      3            9              16               24

process	burst time	waiting time	turnaround time	response time
p1	6	3	9	3
p2	8	16	24	16
p3	7	9	16	9
p4	3	0	3	0
total	24	28	52	24

  → average waiting time: 7

 

SRTF

• Shortest-Remaining-Time-First
  프로세스의 남은 수행시간이 짧은 순서대로 처리된다. 즉 preemptive SJF라고 할 수 있다.
• preemptive
  선점형 스케줄링 방식이기 때문에 SJF보다 비교적 효율적이다.

ex)

+--+--------+----------+--------------+------------------+
|p1|   p2   |    p4    |      p1      |        p3        |
+--+--------+----------+--------------+------------------+
0  1        5          10             17                 26

process	arrival time	burst time	waiting time	turnaround time	response time
p1	0	8	10 - 1 = 9	17	0
p2	1	4	1 - 1 = 0	5 - 1 = 4	1 - 1 = 0
p3	2	9	17 - 2 = 15	26 - 2 = 24	17 - 2 = 15
p4	3	5	5 - 3 = 2	10 - 3 = 7	5 - 3 = 2
total		26	26	52	17

  → average waiting time: 6.5

 

comparing with SJF....

+----------------+--------+----------+------------------+
|       p1       |   p2   |    p4    |        p3        |
+----------------+--------+----------+------------------+
0                8        12         17                 26

process	arrival time	burst time	waiting time	turnaround time	response time
p1	0	8	0	8	0
p2	1	4	8 - 1 = 7	12 - 1 = 11	7
p3	2	9	17 - 2 = 15	26 - 2 = 24	15
p4	3	5	12 - 3 = 9	17 - 3 = 14	9
total		26	31	57	31

  → average waiting time: 7.75

 

RR

• Round-Robin
  일정 시간 할당량 time quantum을 단위로 여러 프로세스를 번갈아가면서 실행한다. 만약 CPU burst가 time quantum보다 짧으면 프로세스가 스스로 다음 프로세스에게 CPU를 넘긴다. CPU burst가 time quantum보다 길면 OS가 강제로 context switching을 한다. 레디 큐는 circular queue 형태로, 레디 큐에 들어왔던 순서로 로테이션이 돌기 때문에 preemptive FCFS라고도 볼 수 있다.
• preemptive
• average waiting time이 항상 minimum은 아니며, 보통 priority-base 스케줄링과 결합해 사용된다.
  
• time quantum은 보통 10-100 milliseconds이며, time-quantum의 크기에 따라 성능이 달라질 수 있다.
  time quantum이 너무 크면 FCFS와 다를 게 없다, 반면에 time quantum이 너무 작으면 context switchng이 빈번하게 발생되는데, context switching을 할 때마다 dispatch latency가 발생하기 때문에 비효율적이다.

ex)

+--------+------+------+--------+--------+------+
|   p1   |  p2  |  p3  |   p1   |   p1   |  p1  |
+--------+------+------+--------+--------+------+
0        4      7      10       14       18     21

process	burst time	waiting time	turnaround time	response time
p1	15	10 - 4 = 6	21	0
p2	3	4	7	4
p3	3	7	10	7
total	21	17	38	17

  → average waiting time: 5.66

 

Priority Scheduling

• highest priority first
  특정 기준으로 우선순위가 높은 프로세스를 먼저 실행시킨다.
  만약 모든 프로세스의 우선순위가 동일하다면 FCFS와 동일하다.
  SJFsms 수행 시간을, SRTF는 남은 수행시간을 우선순위의 기준으로 한 priority-based 스케줄링이다. 
• either preemptive of non-preemptive
• the problem of starvation (indefinite blocking)
  우선순위가 높은 프로세스가 계속 들어올 경우, 우선순위가 낮은 프로세스는 계속 blocking되어 무한대기하는 경우가 생길 수 있다. 이러한 현상을 기아 현상이라고 한다. aging으로 해결할 수 있다.
• aging, solution to the starvation problem
  기다리는 시간이 길어질 수록 우선순위를 높이는 방법이다. 처음에는 우선순위가 낮아 실행이 안될 수 있지만 시간이 지남에 따라 점점 우선순위가 높아지므로 우선순위가 낮아 무한대기하는 경우를 방지할 수 있다.

ex) combine RR and Priority scheduling

우선순위가 높은 순서대로 실행하되, 우선순위가 같을 경우 RR을 사용한다.

+--------------+----+----+----+----+--+--------+----+----+----+--+
|      p4      | p2 | p3 | p2 | p3 |p2|   p3   | p1 | p5 | p1 |p5|
+--------------+----+----+----+----+--+--------+----+----+----+--+
0              7    9    11   13   15 16       20   22  24    26 27

process	priority	burst time	waiting time	turnaround time	response time
p1	3	4	22	26	20
p2	2	5	11	16	7
p3	2	8	12	20	9
p4	1	7	0	7	0
p5	3	3	24	27	22
total		27	69	96	58

  → average waiting time: 13.8

 

MLQ Scheduling

• priority에 따라 레디 큐를 여러 개 두어 각 레벨마다 다른 스케줄링을 적용시킬 수 있다.
• 모든 레디 큐에 대기 중인 프로세스가 있다면 우선순위가 높은, 즉 레벨이 높은 레디 큐에 있는 프로세스부터 실행한다.
• preemptive
  실행 중인 프로세스보다 우선순위가 높은 프로세스가 레디큐에 들어오면 context switching일 발생하여 우선순위가 높은 프로세스부터 실행한다.
• time slicing
  각각의 큐는 CPU의 일정시간을 할당받는데, 우선순위가 높을 수록 많은 시간(time quantum)을 할당받는 방식이다.
• stravation and aging
  low level/priority의 경우 무한대기를 할 수 있기 때문에 기아 문제가 발생할 수 있다. aging과 비슷하게 time quantum을 조금씩 늘리는 방법으로 해결할 수 있다.

 

---

[ Thread  Scheduling ]

최근 OS는 프로세스가 아니라 커널 스레드를 스케줄링한다. (유저 스레드는 스레드 라이브러리에 의해 관리되기 때문에 OS 입장에서는 유저 스레드와 커널 스레드를 맵핑만 해주면 되기 때문에 커널 스레만 스케줄링 해주면 된다)

 

---

[ Real-Time CPU Scheduling ]

실시간 OS의 경우 주어진 시간 내에 작업을 완료해야 한다.

soft real-time 시스템의 경우 모든 작업이 주어진 deadline에 맞춰 실행될 것이라고 보장되지 않는다. 하지만 critical 프로세스가 noncritical 프로세스보다 선행할 것은 보장한다. 예를 들어 유선 전화의 경우 중간에 한 두개 놓쳐 말이 끊길 수는 있지만 순서대로 처리된다.

hard real-time 시스템의 경우 반드시 deadline에 맞춰 작업을 끝내주는 시스템이다.