Transcript CPU Scheduling(1)

CPU Scheduling
CPU Scheduling
 Assign processes to be executed by the processor(s)
CPU and I/O Burst Cycle
 The execution of a process
consists of a cycle of CPU
execution and I/O wait.
 A process begins with a CPU
burst, followed by an I/O
burst, followed by another
CPU burst and so on. The
last CPU burst will end will a
system request to terminate
the execution.
 The CPU burst durations
vary from process to
process and computer to
computer.
Histogram of CPU-burst Times
CPU and I/O Bound Process
 An I/O bound program has many very short CPU
bursts.
 A CPU bound program might have a few very long
CPU bursts.
Types of Scheduling
Queuing Diagram for scheduling
CPU Scheduler
 CPU scheduling decisions may take place when:
1.
2.
3.
4.
The running process changes from running to waiting state.
The running process terminates
A waiting process becomes ready
The current process switches from running to ready stat
 Scheduling under 1 and 2 is nonpreemptive.
 Once a process is in the running state, it will continue until it
terminates or blocks itself.
 Scheduling under 3 and 4 is preemptive.
 Currently running process may be interrupted and moved to the
Ready state by OS.
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
CPU Scheduler and Dispatcher
From
Other
States
Process
Descriptor
Ready Process
Enqueuer
Ready
List
Dispatcher
Context
Switcher
CPU
Running Process
What is a Good Scheduler? Criteria
 User oriented
 Turnaround time: time interval from submission of job
until its completion. spent waiting in ready queue.
 Waiting time: sum of periods spent waiting in ready
queue.
 Response time: time interval from submission of job to
first response.
 Service Time: The amount of time process needs to be in
running state (Acquired CPU) before it is completed.
What is a Good Scheduler? Criteria
 System oriented
 CPU utilization: percentage of time CPU is busy. CPU
utilization may range from 0 to 100%.
 Throughput: number of jobs completed per time unit.
This depends on the average length of the processes.
Goals of Scheduling Algorithms
for Different Systems
Scheduling Algorithms
 CPU scheduling deals with the problem of deciding
which of the processes in the ready queue is to be
allocated the CPU.
 There are many different CPU scheduling algorithms,
which we will discuss now.
First-Come First-Served (FCFS)
Scheduling
 The process that requests the
CPU first is allocated the CPU
first.
 It is nonpreemptive algorithm.
 Can easily be implemented with
a FIFO queue.
 When a process enters the ready
queue, its PCB is linked onto the
tail of the queue.
 When CPU is free, it is allocated
to the process at the head of the
queue.
FCSF - Example
FCFS – Advantages and
Disadvantages
 Advantages
 Very simple
 Disadvantages
 Long average and worst-case
waiting times
 Poor dynamic behavior
(convoy effect - short
process behind long process)
Shortest-Job First Scheduling (SJF)
 This algorithm associates
with each process the
length of its next CPU
burst.
 When the CPU is
available, it is assigned
the process that has the
smallest next CPU burst.
 It is a non-preemptive
policy.
Shortest Remaining Time First (Preemptive SJF)
 Preemptive version of SJF.
 If a new process arrives with CPU burst length less
than remaining time of current executing process,
preempt the currently executing process and allocate
the CPU to the new process.
Example:
Process Arrival Time
P1
0.0
P2
2.0
P3
4.0
P4
5.0
Burst Time
7
4
1
4
 SJF (non-preemptive)
P1
0
P3
3
7
P2
8
P4
12
16
 Average waiting time = (0 + 6 + 3 + 7)/4 = 4
 SRT (preemptive SJB)
P1
0
P2
2
P3
4
P2
5
P4
7
P1
11
16
Advantages and Problems with SJF/SRT
 Advantages:
 Minimizes average waiting times.
 Problems:
 How to determine length of next CPU burst?
If estimated time for process not correct, the
operating system may abort it
 Starvation of jobs with long CPU bursts.

Priority Scheduling
 A priority (an integer) is associated with each process.
 Priorities can be assigned either externally or
internally.
 The CPU is allocated to the process with the highest
priority (smallest integer means highest priority).
 Priority scheduling can be:
 Preemptive
 Nonpreemptive
Priority Scheduling Example
Example:
Process
P1
P2
P3
P4
P5
Arrival time
0
7
9
10
11
CPU Burst
10
1
2
1
5
Priority
3
1
3
4
2
Problem with Priority Scheduling
 Starvation or indefinite blocking – low priority
processes may never execute.
 Solution
 Aging – as time progresses increase the priority of the
process (Allow a process to change its priority based on
its age or execution history)
Round-Robin Scheduling
 Each process gets a small unit of CPU time (called time
quantum), usually 10-100 milliseconds.
 After this time has elapsed, the process is preempted
and added to the end of the ready queue.
 Ready queue is treated as a circular queue.
 CPU scheduler goes around the ready queue,
allocating the CPU to each process for a time interval
of 1 time quantum.
 Ready queue is a FIFO queue of processes.
RR Example
Process
P1
P2
P3
P4
Arrival Time Burst Time
0
53
22
17
35
68
45
24
Time Quantum: 20
RR With Context Switching
Overhead
•In RR, context switching overhead should be considered.
RR and Time Quantum
 The performance of the RR depends heavily on the size
of the time quantum.
 If the time quantum is very large, then RR policy is the
same as FCFS policy.
 If the time quantum is very small then most of the
CPU time will be spent on context switching.
 Turnaround time also depends on the time quantum
 A rule of thumb is that 80% of the CPU bursts should
be shorter than the time quantum.
RR and Time Quantum
Multilevel Queue Scheduling
Multilevel Queue Scheduling
Example
 An OS uses a multilevel queue scheduling algorithm that works as
follows. Each process when created is given a type (OS, Interactive and
Other). There are three queues Q0, Q1 and Q2 (where Q0 has the
highest priority and Q2 the lowest). OS processes are admitted in Q0,
interactive in Q1 and all other in Q2. Q0 uses a FCFS scheduling, Q1 RR
with time quantum of 5ms and Q2 shortest job first. The scheduler
selects the process from Q0. If Q0 if empty then it selects a process
from Q1. If both Q0 and Q1 are empty, then it selects a process from
Q2. If the CPU is executing a process from a low level queue and a
process arrives in a high-level queue, the running process is preemptive
and put back in the same queue. A process from Q1 that is preemptive
before its time quantum expires will get the priority next time a process
is selected from Q1 and will complete its time quantum and then
preemptive.
Multilevel Queue Scheduling
Example
 Show the Gantt chart for the following processes:
Process
P1
P2
P3
P4
P5
Arrival time
0
4
6
8
10
Type
Interactive
OS
Interactive
Other
Other
CPU burst
15
5
4
12
3
Multilevel Feedback Queue
Scheduling
 A process can move between the various queues; aging
can be implemented this way.
 Multilevel-feedback-queue scheduler defined by
the following parameters:
 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