OPERATING SYSTEMS
Scheduling
CPU SCHEDULER
Selects from among the processes in memory that are ready to
execute, and allocates the CPU to one of them
CPU scheduling decisions may take place when a process:
1. Switches from running to waiting state
2. Switches from running to ready state
3. Switches from waiting to ready
4. Terminates
SCHEDULING CRITERIA
CPU utilization – Usage of CPU
Throughput – # 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
FIRST-COME, FIRST-SERVED (FCFS) SCHEDULING
Process Burst Time
P1 24
P2 3
P3 3
Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:
P1 P2 P3
0 24 27 30
Waiting time for P1 = 0; P2 = 24; P3 = 27
Average waiting time: (0 + 24 + 27)/3 = 17
SFCS SCHEDULING (CONT)
Suppose that the processes arrive in the order
P2 , P3 , P1
The Gantt chart for the schedule 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
SHORTEST-JOB-FIRST (SJF) SCHEDULING
Associate with each process the length of its next CPU burst.
Use these lengths to schedule the process with the shortest
time
SJF is optimal – gives minimum average waiting time for a given
set of processes
The difficulty is knowing the length of the next CPU request
EXAMPLE OF SJF
Process Arrival Time Burst Time
P1 0.0 6
P2 2.0 8
P3 4.0 7
P4 5.0 3
SJF scheduling chart
P4 P1 P3 P2
0 3 9 16 24
Average waiting time = (3 + 16 + 9 + 0) / 4 = 7
PRIORITY SCHEDULING
• A priority number (integer) is associated with each process
• The CPU is allocated to the process with the highest priority
(smallest integer highest priority)
• Preemptive
• nonpreemptive
• SJF is a priority scheduling where priority is the predicted
next CPU burst time
• Problem Starvation – low priority processes may never
execute
• Solution ?
ROUND ROBIN (RR)
Each process gets a small unit of CPU time. After this
time has elapsed, the process is preempted and added
to the end of the ready queue.
EXAMPLE OF RR WITH TIME QUANTUM = 4
Process Burst Time
P1 24
P2 3
P3 3
The Gantt chart is:
P1 P2 P3 P1 P1 P1 P1 P1
0 4 7 10 14 18 22 26 30
MULTILEVEL QUEUE
• Ready queue is partitioned into separate queues:
foreground
background
• Each queue has its own scheduling algorithm
• foreground – RR
• background – FCFS
• Scheduling must be done between the queues
• Fixed priority scheduling; (i.e., serve all from foreground then from
background).
• Time slice – each queue gets a certain amount of CPU time which it
can schedule amongst its processes; i.e., 80% to foreground in RR
• 20% to background in FCFS
EXAMPLE OF MULTILEVEL FEEDBACK QUEUE
Three queues:
Q0 – RR with time quantum 8 milliseconds
Q1 – RR time quantum 16 milliseconds
Q2 – FCFS
Scheduling
A new job enters queue Q0 which is served FCFS. When it gains CPU, job
receives 8 milliseconds. If it does not finish in 8 milliseconds, job is
moved to queue Q1.
At Q1 job is again served FCFS and receives 16 additional milliseconds. If
it still does not complete, it is preempted and moved to queue Q2.
MULTILEVEL FEEDBACK QUEUES
END OF LECTURE
