OS_07_CPU Scheduling

1. Basic Concepts

1) CPU Scheduler

• ready process들 중에서 선택을 하는 것.
  • 그리고 그 중 하나에게 CPU를 할당하는 것이다.
• Schduling 결정은 process가 해당 상황에 있을 때 일어난다.
  • Switches from running to waiting state (e.g., I/O request) → CPU가 더이상 필요하지 않은 상황
    
  • Switches from running to ready state (e.g., interrupt) → 할게 더 있는데 CPU를 빼앗기는 것
    
  • Switches from waiting to ready (e.g., completion of I/O) → 할게 더 있는데 CPU를 빼앗기는 것
    
  • Terminates → CPU가 더이상 필요하지 않은 상황
    
• 1번과 4번에 의해 schduling이 되는 것을 nonpreemptive라고 한다.
• 그렇지 않다면 preemptive라고 한다.
  • 선제적으로 OS가 CPU를 뺏어오는 것이다.
  • 이론적으로 성능이 더 좋은 방식

2. Scheduling Criteria

1) Scheduling Criteria

• CPU utilization - CPU를 최대한 바쁘게 유지하는 것이 좋다.
• Throughput - 시간 단위 당 각자의 execution을 완료하는 process의 개수이다.
• Turnaround time - 특정 Process를 실행시키는데에 걸리는 시간이다.
  • process의 submission time부터 completion time까지
• Waiting time - process가 ready queue에서 기다리는 시간이다.
• Response time - request가 제출되고 처음 response(start)가 발생한 시간이다. (for time-sharing environment)

2) Optimization Criteria

• Max CPU utilization
• Max throughput
• Min turnaround time
• Min waiting time
• Min response time

3. Scheduling Algorithms

1) First-Cone, First-Served (FCFS) Scheduling

a) 1st example

Process	Burst Time(Execution Time)
P1	24
P2	3
P3	3

• Process가 도착하는 순서를 P1, P2, P3라고 가정

The Gantt Chart

• Waiting time for P1 = 0; P2 = 24; P3 = 27
• Average waiting time : (0 + 24 + 27)/3 = 17

b) 2nd example

• Process가 도착하는 순서를 P2, P3, P1이라고 가정

The Gantt Chart

• Waiting time for P1 = 6; P2 = 0; P3 = 3
• Average waiting time : (6 + 0 + 3)/3 = 3
• 이전의 예시보다 훨씬 좋은 결과를 보여준다.

2) Shortest-Job-First (SJF) Scheduling

• 가장 job을 하는데 걸리는 time이 짧은 것 부터 scheduling하는 방식이다.
• 2가지의 틀
  • nonpreemptive - 일단 process에게 CPU가 주어지면 완료 할 때 까지 CPU를 내려놓지 않는다.
  • preemptive - 만약 새로운 process가 도착했는데, 현재 진행중인 process의 남은 시간보다 burst time이 짧다면 해당 프로세스를 scheduling → Shortest-Remaining-Time-First (SRTF)
    

a) 1st example

Process	Arrival Time	Burst Time(Execution Time)
P1	0.0	7
P2	2.0	4
P3	4.0	1
P4	5.0	4

• SJF (non-preemptive)

The Gantt Chart

• Average waiting time = (0 + 6 + 3 + 7)/4 = 4

b) 2nd example

• SJF (preemptive)

The Gantt Chart

• Average wating time = (9 + 1 + 0 + 2)/4 = 3

c) Optimality and Feasibility of SJF

• SJF는 최적의 방식이다.
  • SJF는 주어진 process들의 집합에서 최소한의 average waiting time을 제공한다.
• SJF는 실제로는 실현이 불가능하다.
  • Burst time은 대부분의 경우에 미리 알기 어렵다.

증명

• Execution time을 예측해서 어느정도 유추를 할 수 있지만, 실질적으로 guess는 후행으로 이루어지기에 큰 의미가 없다.

3) Priority-based Scheduling Algorithms

• priority number는 각기의 Process와 관련이 있다.
• CPU는 process의 우선순위에 따라 할당된다. (smallest integer == highest priority)
  • Preemptive
  • Nonpreemptive
• SJF도 일종의 priority scheduling으로 볼 수 있다. (CPU burst time에 따라 우선순위가 결정되기에..)
• Problem
  • Starvation - 낮은 우선순위의 Process는 한번도 scheduling이 안될 수도 있다.
• Solution
  • Aging - 시간이 지날수록 process의 우선순위를 높인다.

4) Earliest Deadline First (EDG)

• 가정 - process가 도착 할 때, deadline을 가지고 들어온다. → Deadline이 빠른 프로세스가 높은 priority를 가진다.
  
• Deadline을 충족시키는 관점에서 optimal하다.

5) Round Robin (RR)

• 각 process는 작은 CPU time의 단위를 가진다. (Non-priority)
  • time quantum : 보통 10-100 milisecond
  • 이 시간을 모두 소진하게 되면 process는 CPU를 양보하고 ready queue의 맨 마지막에 들어간다.
• 만약 n개의 process가 ready queue에 있고, time quantum이 q라고 한다면.
  • process의 wait time이 (n-1)q time units를 초과하는 process는 없다.

a) 1st example

Process	Burst Time(Execution Time)
P1	53
P2	17
P3	68
P4	24

The Gantt Chart

• 전형적으로 SJF 보다 높은 average turnaround time을 가지지만, response의 관점에서는 낫다.

6) Multilevel Queue

• Ready queue는 여러개의 queue로 나누어져 있다.
  • foreground (interactive) and background (batch)
• 각 queue는 각자의 scheduling algorithm을 가진다
  • foreground (RR) and background (FCFS)
• Scheduling은 반드시 queue들 중에서 일어나야한다.
  - 고정된 우선순위 스케줄링 - foreground에 있는 process부터 처리 한 후에 background를 처리한다.
  - Time slice - 각 queue는 특정 CPU time의 양을 가진다.
  - 80% to foreground in RR
  - 20% to background in FCFS
  

Multilevel Queue Scheduling (Starvation 가능)

7) Multilevel Feedback Queue

• process는 다양한 queue사이를 움직일 수 있다.
  • 만약 Process가 너무 많이 CPU를 사용한다면, 낮은 순위의 queue로 옮긴다.
  • Aging이 이 방식으로 구현된다.
• MLFQ scheduler는 다음의 parameter들로 정의된다.
  • number of queues
  • scheduling algorithms for each queue
  • method used to determine when to upgrade a process (승급)
  • method used to determine when to demote a process (강등)
  • method used to determine which queue a process will enter when that process needs service

a) 1st example

• 3개의 queues (preempted)
  • Q0 - time quantum 8 milliseconds (Round robin)
  • Q1 - time quantum 16 milliseconds (Round robin)
  • Q2 - FCFS
• Scheduling
  • 새로운 job은 Q0으로 들어온 후, FCFS에 따라 스케줄링이 된다.
    • CPU를 할당 받은 뒤 8 milliseconds만큼 수행하는데, 일을 끝마치지 못했다면 Q1 queue로 이동한다.
  • Q1에서도 FCFS에 따라 16 milliseconds만큼 수행한다.
    • 이번에도 일을 끝마치지 못했다면, Q2 queue로 이동한다.

• Process의 특징 (여담)
  • 사용자와 상호작용이 많은 것
    • 해당 작업이 더 중요해서 우선순위가 높은 곳에 할당하고 싶다.
    • CPU를 적게 사용하기에 금방 끝나는 작업이다.
  • CPU를 많이 쓰는 작업
• 해당 Process의 특징 때문에 후순위 queue로 갈 수록 time quantum이 더욱 커지는 구조가 만들어졌다.