Transcript P 1 - Universidade de Coimbra

Operating
Systems
5. CPU Scheduling
2006/2007
5.1 Algorithms
Paulo Marques
Departamento de Eng. Informática
Universidade de Coimbra
[email protected]
Disclaimer

This slides and notes are heavily based on the companion material of
[Silberschatz05].The original material can be found at:


In some cases, material from [Stallings04] may also be used. The
original material can be found at:


http://codex.cs.yale.edu/avi/os-book/os7/slide-dir/index.html
http://williamstallings.com/OS/OS5e.html
The respective copyrights belong to their owners.
2
What’s the Best Scheduler?
What’s the Best Plane?
Capacity
(Passengers)
Autonomy
(Km)
Velocity
(Km/h)
Throughput
Boeing 777
375
7,408
976
366,000
Boeing 747
470
6,640
976
458,720
Concorde
132
6,400
2,160
285,120
Douglas DC8
146
13,952
870
127,020
Plane
(Passengers x
Km/h)
It all depends on what you are optimizing for!
3
Process Scheduling
Let’s see how to choose which
process/thread should the CPU
be allocated to!
4
System Queues
5
Preemptive vs. Non-Preemptive

Non-Preemptive Scheduling
Once the CPU is allocated to a process, the process keeps
the CPU until it terminates or it blocks in a I/O operations
and switches to the waiting state (e.g. in Windows 98).

Preemptive Scheduling
The operating system may decide (and is able to) take the
CPU away from a running process (e.g. in WindowsXP,
Linux)
6
Scheduling Criteria

CPU utilization


Throughput


Amount of time to complete a particular process
Waiting time


Number of processes that complete their execution per time unit
Turnaround time


Keep the CPU as busy as possible
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
7
Optimization Criteria…


As seen before, it all depends on what type of system we
are aiming at…
But, we would like:





Maximum CPU utilization
Maximum throughput
Minimum turnaround time
Minimum waiting time
Minimum response time
That’s a multi-objective function, not
really possible…
8
Why can we optimize?
CPU-IO Cycle
CPU-burst Times
9
Algorithm 1: First-Come First-Served (FCFS)
Process
P1
P2
P3

Burst Time
24
3
3
Suppose that the processes arrive in the order: P1 , P2 , P3
The Gantt Chart for the schedule is:
P1
0



P2
24
P3
27
30
Waiting time for P1 = 0; P2 = 24; P3 = 27
Average waiting time: (0 + 24 + 27)/3 = 17
This is a non-preemptive algorithm
10
First-Come First-Served (FCFS) – Cont.


Suppose that the processes arrive in the order: P2 , P3 , P1
The Gantt chart for the schedule is:
P2
0
P3
3
P1
6

Waiting time for P1 = 6; P2 = 0; P3 = 3
Average waiting time: (6 + 0 + 3)/3 = 3
Much better than previous case.

Convoy effect




30
Short process behind long process
I/O bound vs. CPU bound problem
11
Algorithm 2: Shortest-Job-First (SJF)

Associate with each process the length of its next CPU
burst. Use these lengths to schedule the process with the
shortest time.



How do you determine that? Can you guess the future?
Also known as Shortest-Job-Next (SJN), which is more correct.
Two schemes:

SJF (non-premptive): once CPU given to the process it cannot be
preempted until completes its CPU burst.

SRTF (preemptive): if a new process arrives with CPU burst
length less than remaining time of current executing process,
preempt. This scheme is know as the Shortest-Remaining-Time
First (SRTF).
12
(Non-Preemptive) Shortest-Job-First (SJF)
Process
P1
P2
P3
P4

Arrival Time
0.0
2.0
4.0
5.0
SJF (non-preemptive)
P1
0



Burst Time
7
4
1
4
3
P3
7
P2
8
P4
12
16
Average waiting time = (0 + 6 + 3 + 7)/4 = 4
Can be proved optimal (minimizes waiting time) for a set
of processes
Used frequently in long-term scheduling
13
(Preemptive) Shortest-Remaining-Time-First (SRTF)

Process
Arrival Time
Burst Time
P1
0.0
7
P2
2.0
4
P3
4.0
1
P4
5.0
4
SRTF (preemptive)
P1
0

P2
2
P3
4
P2
5
P4
7
P1
11
16
Average waiting time = (9 + 1 + 0 +2)/4 = 3
14
Predicting the next CPU burst time

Based on an exponential moving average based on the
past.
 n1    n  (1   )  tn
15
Priority Scheduling


A priority number is associated with each process
The CPU is allocated to the process with the highest
priority (smallest integer  highest priority)


Preemptive
Non-preemptive

SJF is a priority scheduling where priority is the predicted
next CPU burst time

Problem  Starvation


Low priority processes may never execute
Solution  Aging

As time progresses increase the priority of the process
16
Starvation @MIT
When the system managers shutdown
the IBM 7094 at MIT in 1973, they found
a low-priority process that had been
submitted in 1967 and had not yet run…
IBM 7094
17
Priority-Based Scheduler
18
Algorithm 3: Round-Robin (RR)

Each process gets a small unit of CPU time (time
quantum), usually 10-100 milliseconds. After this time
has elapsed, the process is preempted and added to the
end of the ready queue.


If there are n processes in the ready queue and the time
quantum is q, then each process gets 1/n of the CPU time
in chunks of at most q time units at once.


New processes are added to the tail of the ready queue
No process waits more than (n-1)q time units.
Performance


q large  FCFS
q small  q must be large with respect to context switch,
otherwise overhead is too high. If so, having N processes is like
having a machine running at 1/N of the speed.
19
RR with a quantum of 20

Process
P1
Burst Time
53
P2
P3
P4
17
68
24
The Gantt chart is:
P1
0

P2
20
37
P3
P4
57
P1
77
P3
97 117
P4
P1
P3
P3
121 134 154 162
Typically, higher average turnaround than SJF, but better
response time
20
Timeline charts are relevant!
21
Time Quantum and Context Switches
22
Turnaround Time vs. Time Quantum


Turnaround time depends on time quantum but the
relation is not direct.
In general, turnaround time can be improved if most
processes finish on a time quantum
23
Multilevel Queue Scheduling
24
Multilevel Queue Scheduling (2)

Ready queue is partitioned into separate queues. E.g.



Each queue has its own scheduling algorithm:



Foreground (interactive)
Background (batch)
Foreground – RR
Background – FCFS
Scheduling must be done between the queues.


Fixed priority scheduling (i.e., serve all processes from foreground;
then from background). Possibility of starvation.
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
25
Multilevel Feedback Queue Scheduling

Processes can move among 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
26
Example of a scheduler with three queues
Note that queue serving is priority-based!
27
Example of a scheduler with three queues (2)

Three queues:




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.
Gives high-priority to any process with CPU bursts of 8ms or less.


Q0 – time quantum 8 milliseconds
Q1 – time quantum 16 milliseconds
Q2 – FCFS
Grabs CPU, do processing, move along to next IO cycle…
Process with bursts of >8ms and <16ms are served quickly but with
less priority
Long running processes since to Q2 and are served on any CPU cycles
remaining.
28
Characteristics of Scheduling Algorithms
from [Stallings05]
29
Operating
Systems
5. CPU Scheduling
2006/2007
5.2 Example from Stallings
Paulo Marques
Departamento de Eng. Informática
Universidade de Coimbra
[email protected]
Example

This example is taken from [Stallings04]

Homework


Calculate Finish-Time, Waiting-Time, Turnaround Time for each
process
Calculate Average Waiting Time and Average Turnaround Time
31
FCFS



Short process may have to wait a very long time before it can execute
Favors CPU-bound processes
I/O processes have to wait until CPU-bound process completes
32
Round-Robin (q=1)




Uses preemption based on a clock
When an interrupt occurs, the running process is placed in the ready
queue
Next ready job is selected
Known as time slicing
33
SPN / SJF



Non-preemptive policy
Process with shortest expected processing
time is selected next
Short process jumps ahead of longer processes
34
SRTF


Preemptive version
Must estimate processing time
35
Multilevel Feedback

Penalize jobs that are longer
36
Comparison of Scheduling Algorithms
37
Comparison of Scheduling Algorithms (2)
38
Operating
Systems
5. CPU Scheduling
2006/2007
5.3 Operating Systems
Paulo Marques
Departamento de Eng. Informática
Universidade de Coimbra
[email protected]
Traditional UNIX Scheduling

Multilevel feedback using
Round-Robin within each of the
priority queues

If a process does not block or
complete within a second, it is
preempted

Priorities are recomputed once
per second

Base priority divides all
processes into fixed bands of
priority levels
40
Windows XP Scheduling

Priority-based Preemptive Scheduling


The highest priority queue is always served first
32 levels of priorities, two classes of threads:






Real-time, having a priority from 16 to 31
Variable, having a priority from 1 to 15
The priorities from all threads vary except if they are in a
REAL_TIME_PRIORITY_CLASS
Within each class, there are relative priorities
“Normal” preempted threads have their priority lowered; “Normal”
threads released from a wait() have their priority boosted.
Time quantum is different for “foreground” and “background” threads.
41
Linux 2.6 Scheduling


Preemptive Priority-Based Scheduler
Two separate priority ranges:



Scheduling (Time-Sharing Algorithm  Fair preemptive):





Real-time (0-99) and Nice (100-140)
Two algorithms: time-sharing and real-time
Active Array and Expired Array
Scheduling is done from the active array. The scheduler chooses the task
from the active array for execution. It runs until its time slice is gone, or it is
blocked.
Whenever a task has used all its time slice, it’s moved to the expired array.
Recalculation of its priority is done at that time.
Execution goes on until the active array is empty. When the active array is
empty, it’s switched with the expired array.
Real-time tasks (Soft Real time) are POSIX.1b compliant and are
assigned fixed priorities.

Two scheduling algorithms are used: FCFS and RR.
42
Linux 2.6 Scheduling (2)

Higher priority tasks are
assigned a longer time
quantum

Two arrays are used for
scheduling
43
Reference

Chapter 5: CPU Scheduling

5.1, 5.2, 5.3, 5.6, 5.8
44