Transcript CPU Scheduling

Computer Studies (AL)
Process Management
CPU Scheduling
Reference


Silberschatz, Galvin, Gagne “Operating
System Concepts 6th edition”, 2003, Wiley
Stallings, “Operating Systems Internals and
Design Principles”, 2001, Prentice Hall
Content


Basic concepts
Scheduling Criteria


Decision making (preemptive and non-preemptive
Scheduling Algorithm




FCFS
SJF
PS
RRS
Basic concept


The objective of multiprogramming is to
have some process running at all times, in
order to maximize CPU utilization.
Scheduling is a fundamental operating
system function.
CPU-I/O burst Cycle

The success of CPU scheduling depends on the
following observed property of processes:



Process execution consists of a cycle of CPU
execution and I/O wait.
Processes alternate between these two states.
Process execution begins with a CPU burst,
followed by an I/O burst, and so on
CPU scheduler


OS must select one of the processes in the
ready queue to be executed.
The selection process is carried out by the
short-term scheduler.




FIFO queue
Priority queue
Tree
Unordered linked list
Scheduling decision take place...

CPU scheduling decisions may take place
under the following 4 circumstances:




1. When a process switches from running stat
to the waiting state
2. When a process switches from running
state to the waiting state
3. When a process switches from the waiting
state to the ready state
4. When a process terminates
Non Preemptive CPU Scheduler





When scheduling takes place only under circumstances 1
and 4
= Nonpreemptive scheduling scheme.
(since it’s no choice in terms of scheduling)
Under nonpreemptive scheduling, once the CPU has been
allocated to a process, the process keeps the CPU until it
releases the CPU either by terminating or by switching to
the waiting state.
In order word, CPU scheduler is said to be nonpreemptive if it reassigns the CPU only when a process
gives up the use of the CPU.
E.g. Windows 3.1
Preemptive Scheduling


When scheduling takes place at 2 and 3
= preemptive scheduling scheme.
In order word, a CPU scheduler is said to
be preemptive if it immediately assigns the
CPU to a higher-priority process when the
process requires CPU service.
Discussion

Any disadvantage of preemptive?

Incur greater overhead than nonpreemptive.
Discussion

Any disadvantages of using nonpreemptive CPU scheduler?

Keep the job too long for processor.
Discussion

Why preemptive?


Better service to the total population processes
because they prevent any one process from
monopolizing the processor for very long.
The cost of preemption may be kept relatively low by
using efficient process-switching mechanisms
(hardware design) or providing large main memory
to keep a high percentage of programs in main
memory.
Scheduling Criteria


Different CPU-scheduling algorithm have different properties.
The criteria suggested include:

CPU utilization
 Keep CPU busy

Throughput
 The number of processes completed per time unit

Turnaround time
 How long it takes to execute that process
 (Waiting to get into memory + ready queue + execute + I/O)

Waiting time
 Spends time on waiting in the reading queue

Response time
 The time from the submission of a request until the first response is
produced.
Scheduling Algorithm




First-Come-First-Served (FCFS)
Shortest-Job-First (SJF)
Priority Scheduling (PS)
Round-Robin Scheduling (RRS)
First-Come-First-Served (FCFS)

The process that requests the CPU first is
allocated the CPU first
Process Burst
time
P1
24
P2
3
P3
3
P1
P2
P3
24
27 30
0
Average waiting time = (0+24+27)/3 =
17ms
First-Come-First-Served (FCFS)

If the order is P2, P3 and P1
P2 P3
0
3
P1
6
Average waiting time is now (6+0+3)/3 = 3ms
30
Shortest-Job-First Scheduling
(SJF)

When CPU is available, it is assigned to the
process that has the smallest next CPU
burst.
Process Burst
time
P1
6
P2
8
P3
7
P4
3
P4 P1
0
3
P3
9
P2
16
24
Average waiting time is (3+16+9+0)/4 = 7ms
Shortest-Job-First Scheduling
(SJF)


SJF is provably optimal, in that it gives the
minimum average waiting time.
The read difficulty is knowing the length of
the next CPU request.(that’s why SJF is
used frequently in long-term scheduling)
Shortest-Job-First Scheduling
(SJF)


Preemptive SJF will preempt the currently
executing process
Nonpreemptive SJF will allow the
currently running process to finish its
CPPU burst.
Shortest-Job-First Scheduling
Process P1 is started at time 0,
(SJF)
since it’s the only process in the queue.
Process
Avvival
time
Burst time Process P2 arrives at time 1. The remaining
P1
0
8
P2
1
4
P3
2
9
P4
3
5
time for P1 (7ms) is larger than the time required
by process P2, so process P1 is preempted and
process P2 is scheduled.
Preemptive
P1 P2
P4
P1
P3
0 1 5
10
Nonpreemptive
P1
0
P2
8
P4
12
17
26
P3
17
26
Average waiting time (preemptive) is
((10-1)+(1-1)+(17-2)+(5-3))/4
= 26/4 = 6.5ms
Average waiting time (Nonpreemptive)is
((0-0)+(8-1)+(12-3)+(17-2)/4
= 31/4 =7.75ms
Priority Scheduling (PS)



A priority is associated with each process
The CPU is allocated to the process with
the highest priority.
Equal-priority processes are scheduled in
FCFS order.
Priority Scheduling (PS)
Process
Burst
time
priority
P1
10
3
P2
1
1
P3
2
4
P4
1
5
P5
5
2
P2
0
P5
P1
1
6
Average waiting time = 8.2ms
Major problem of PS is indefinite blocking
(starvation) A low-priority process
ever getting the CPU.
Solution: Aging
It’s a technique of gradually increasing the
priority of processes that wait in the
system for a long time.
P3
16
P4
18 19
Round-Robin Scheduling (RRS)




Design for time-sharing system
Similar FCFS, with preemption
Small unit of time: time quantum/time slice
The CPU scheduler goes around the ready queue,
allocating the CPU to each process for a time
interval of up to 1 time quantum


Process less than 1 time quantum: release CPU
voluntarily, then next process
Process more than 1 time quantum: time slice expired,
context switch will be executed, process will be put
at the tail of the ready queue, then next process.
Round-Robin Scheduling

Average waiting time is quite long.
Process
P1
P2
P3
P1
P2
Suppose time quantum: 4ms
P1 gets the first 4ms, since it requires
another 20ms, it’s preempted after the
first quantum, and CPU is given to next
process P2. P2 doesn’t need 4ms, then
quits before time quantum expires. Then
next process P3 got the time quantum.
Burst time
24
3
3
P3
P1
P1
P1
P1
0
4
7
10
14
18
22
Average waiting time: 17/3 = 5.66
P1
26
30