Scheduling

Chapter 5: CPU Scheduling

Operating System Concepts – 8th Edition

Silberschatz, Galvin and Gagne ©2009

Chapter 5: CPU Scheduling
Basic Concepts Scheduling Criteria Scheduling Algorithms Thread Scheduling Multiple-Processor Scheduling Operating Systems Examples Algorithm Evaluation

Operating System Concepts – 8th Edition

5.2

Silberschatz, Galvin and Gagne ©2009

ObjectivesTo introduce CPU scheduling, which is the basis for multiprogrammed operating systems To describe various CPU-scheduling algorithms To discuss evaluation criteria for selecting a CPU-scheduling algorithm for a particular system

Operating System Concepts – 8th Edition

5.3

Silberschatz, Galvin and Gagne ©2009

Basic Concepts
Maximum CPU utilization obtained with multiprogramming CPU–I/OBurst Cycle – Process execution consists of a cycle of CPU execution and I/O wait CPU burst distribution

Operating System Concepts – 8th Edition

5.4

Silberschatz, Galvin and Gagne ©2009

Alternating Sequence of CPU and I/O Bursts

Operating System Concepts – 8th Edition

5.5

Silberschatz, Galvin and Gagne ©2009

Histogram of CPU-burst Times

Operating System Concepts – 8thEdition

5.6

Silberschatz, Galvin and Gagne ©2009

CPU Scheduler
Selects from among the processes in ready queue, and allocates the CPU to one of them Queue may be ordered in various ways CPU scheduling decisions may take place when a process: 1. 2. 3.
4.

Switches from running to waiting state Switches from running to ready state Switches from waiting to ready TerminatesScheduling under 1 and 4 is nonpreemptive All other scheduling is preemptive Consider access to shared data Consider preemption while in kernel mode Consider interrupts occurring during crucial OS activities

Operating System Concepts – 8th Edition

5.7

Silberschatz, Galvin and Gagne ©2009

Dispatcher
Dispatcher module gives control of the CPU to the process selected by the short-term scheduler;this involves: switching context switching to user mode jumping to the proper location in the user program to restart that program Dispatch latency – time it takes for the dispatcher to stop one process and start another running

Operating System Concepts – 8th Edition

5.8

Silberschatz, Galvin and Gagne ©2009

Scheduling Criteria
CPU utilization – keep the CPU as busy as possibleThroughput – # of processes that complete their execution per time unit Turnaround time – amount of time to execute a particular process Waiting time – amount of time a process has been waiting in the ready queue Response time – amount of time it takes from when a request was submitted until the first response is produced, not output (for time-sharing environment)

Operating System Concepts – 8thEdition

5.9

Silberschatz, Galvin and Gagne ©2009

Scheduling Algorithm Optimization Criteria
Max CPU utilization Max throughput Min turnaround time Min waiting time Min response time

Operating System Concepts – 8th Edition

5.10

Silberschatz, Galvin and Gagne ©2009

First-Come, First-Served (FCFS) Scheduling
Process P1 P2 P3 Suppose that the processes arrive in the order: P1 ,P2 , P3 The Gantt Chart for the schedule is: Burst Time 24 3 3

P1

P2

P3

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

24

27

30

Operating System Concepts – 8th Edition

5.11

Silberschatz, Galvin and Gagne ©2009

FCFS Scheduling (Cont.)
Suppose that the processes arrive in the order: P2 , P3 , P1 The Gantt chart for theschedule is:

P2

P3

P1

0

3

6

30

Waiting time for P1 = 6; P2 = 0; P3 = 3 Average waiting time: (6 + 0 + 3)/3 = 3 Much better than previous case Convoy effect - short process behind long process Consider one CPU-bound and many I/O-bound processes

Operating System Concepts – 8th Edition

5.12

Silberschatz, Galvin and Gagne ©2009

Shortest-Job-First (SJF) Scheduling...