Transcript Module 6: CPU Scheduling

Chapter 5: CPU Scheduling
(Continuation)
Determining Length of Next CPU Burst
 Can only estimate the length
 Can be done by using the length of previous CPU bursts, using
exponential averaging
1. tn  actual length of nth CPU burst
2.  n stores the past history
3.  n 1  predicted value for the next CPU burst
4.  , 0    1
5. Define:

tn
n 1
  tn  1    n
contains the most recent information,
n
contains the past history
α is the relative weight of recent and past history; more commonly it is
taken α=1/2, so recent history and past history are equally weighted
Operating System Concepts – 7th Edition, Feb 2, 2005
5.2
Silberschatz, Galvin and Gagne ©2005
Philosophy of Exponential Averaging
  =0
n+1 = n
 Recent history does not count
  =1
 n+1 =  tn
 Only the actual last CPU burst counts
 If we expand the formula, we get:
n+1 =  tn+(1 - ) tn -1 + …
+(1 -  )j  tn -j + …
+(1 -  )n +1 0

 Since both  and (1 - ) are less than or equal to 1, each
successive term has less weight than its predecessor
Operating System Concepts – 7th Edition, Feb 2, 2005
5.3
Silberschatz, Galvin and Gagne ©2005
Prediction of the Length of the Next CPU
Burst
 n1   tn  1    n
 0  10;   1/2; t0  6
Operating System Concepts – 7th Edition, Feb 2, 2005
5.4
Silberschatz, Galvin and Gagne ©2005
Priority Scheduling
 A priority number (integer) is associated with each process
 Smaller number  higher priority, larger number  lower
priority
 The CPU is allocated to the process with the highest priority
(smallest integer  highest priority)

Preemptive (preempt the CPU if the priority of newly
arrived process is higher than the priority of the currently
running process)

Nonpreemptive (put the new process at the head of the
ready queue if its priority is higher than the priority of
other processes in the ready queue )
 Equal-priority processes are scheduled in FCFS order.
Operating System Concepts – 7th Edition, Feb 2, 2005
5.5
Silberschatz, Galvin and Gagne ©2005
Priority Scheduling
 SJF is a special case of the general priority scheduling. In
this case the priority is the inverse of the predicted next CPU
burst time: the larger the CPU burst, the lower the priority,
and vice versa.
 Problem  Starvation – low priority processes may never
execute
 Solution  Aging – as time progresses increase the priority
of the process that wait in the system for a long time
Operating System Concepts – 7th Edition, Feb 2, 2005
5.6
Silberschatz, Galvin and Gagne ©2005
Round Robin (RR) Scheduling
 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
the time frames of at most q time units at once. No process
waits more than (n-1)q time units.
 Performance

q large  FCFS

q too small (about 1 millisecond)  processor sharing 
q must be larger, with respect to context switch, otherwise
overhead is too high
Operating System Concepts – 7th Edition, Feb 2, 2005
5.7
Silberschatz, Galvin and Gagne ©2005
Time Quantum and Context Switch Time
Operating System Concepts – 7th Edition, Feb 2, 2005
5.8
Silberschatz, Galvin and Gagne ©2005
Example of RR with Time Quantum = 20
Process
P1
P2
P3
P4
 The Gantt chart is:
P1
0
P2
20
P3
37
Burst Time
53
17
68
24
P4
57
P1
77
P3
97 117
P4
P1
P3
P3
121 134 154 162
 Typically, higher average turnaround than SJF, but better response
Operating System Concepts – 7th Edition, Feb 2, 2005
5.9
Silberschatz, Galvin and Gagne ©2005
Turnaround Time Varies With The Time Quantum
•If the time quantum is too large, RR scheduling degenerates to FCFS policy
•About 80% of the CPU bursts should be shorter than the time quantum
Operating System Concepts – 7th Edition, Feb 2, 2005
5.10
Silberschatz, Galvin and Gagne ©2005
Multilevel Queue
 Ready queue is partitioned into separate queues:
foreground (interactive)
background (batch)
 Each queue has its own scheduling algorithm

foreground – Round Robin (RR)

background – First come, first served (FCFS)
 Scheduling must be done between the queues

Fixed priority scheduling; (i.e., serve all 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 and 20% to background in
FCFS
Operating System Concepts – 7th Edition, Feb 2, 2005
5.11
Silberschatz, Galvin and Gagne ©2005
Multilevel Queue Scheduling
Operating System Concepts – 7th Edition, Feb 2, 2005
5.12
Silberschatz, Galvin and Gagne ©2005
Multilevel Feedback Queue
 A process can move between the various queues; aging can
be implemented this way
 Multilevel-feedback-queue scheduler is 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
Operating System Concepts – 7th Edition, Feb 2, 2005
5.13
Silberschatz, Galvin and Gagne ©2005
Example of Multilevel Feedback Queue
 Three queues:

Q0 – RR with time quantum 8 milliseconds

Q1 – RR time quantum 16 milliseconds

Q2 – FCFS, only when Q0 and Q1 are empty
 Scheduling

A new job enters queue Q0 . 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 receives 16 additional milliseconds. If it still does
not complete, it is preempted and moved to queue Q2.
Operating System Concepts – 7th Edition, Feb 2, 2005
5.14
Silberschatz, Galvin and Gagne ©2005
Multilevel Feedback Queues
Operating System Concepts – 7th Edition, Feb 2, 2005
5.15
Silberschatz, Galvin and Gagne ©2005
Thread Scheduling
 On operating systems that support user-level
and kernel-level threads the latter are being
scheduled by the operating system
 User-level threads are managed by a thread
library. To run on a CPU, user-level thread
must be mapped to an associate kernel-level
thread. This mapping may use a lightweight
process (LWP - a mean of achieving multitasking. In
contrast to a regular (full-blown) process, an LWP shares all
(or most of) its logical address space and system resources
with other process(es); in contrast to a thread, a lightweight
process has its own private process identifier and parenthood
relationships with other processes)
Operating System Concepts – 7th Edition, Feb 2, 2005
5.16
Silberschatz, Galvin and Gagne ©2005
Thread Scheduling
 Local Scheduling (Process-Contention Scope)
– how the threads library decides which thread
to put onto an available lightweight process
(LWP)
 Global Scheduling (System-Contention Scope)
– how the kernel decides which kernel thread
to run next
Operating System Concepts – 7th Edition, Feb 2, 2005
5.17
Silberschatz, Galvin and Gagne ©2005
Windows XP Scheduling
 Windows XP schedules threads using a priority-based,
preemptive scheduling algorithm.
 The Windows XP scheduler ensures that the higher priority
thread will always run.
 The portion of the Windows XP kernel that handles
scheduling is called the dispatcher.
 A thread selected to run by the dispatcher will run until it is
preempted by a higher priority thread, until it terminates, until
its time quantum ends, or until it calls a blocking system call
(such as for Input/Output operation)
 If a higher priority real-time thread becomes ready while a
lower priority thread is running, the lower-priority thread will
be preempted.
Operating System Concepts – 7th Edition, Feb 2, 2005
5.18
Silberschatz, Galvin and Gagne ©2005
Windows XP Scheduling
 There are two priority classes:

The variable class contains threads having priorities from 1
to 15

The real-time class contains threads with priorities from 16
to 31.

A single thread running at priority 0 is used for memory
management.
 Each scheduling priority has a separate queue of the
corresponding processes
 The dispatcher uses a queue for each scheduling priority and
traverses the set of queues from highest to lowest until it finds a
thread that is ready to run.
 If no ready thread is found, the dispatcher will execute a special
thread called the idle thread.
Operating System Concepts – 7th Edition, Feb 2, 2005
5.19
Silberschatz, Galvin and Gagne ©2005
Windows XP Priorities
The relative priorities
The priority
within a class
classes
By default, the base priority is the value of the Normal relative priority for the
specific class
Operating System Concepts – 7th Edition, Feb 2, 2005
5.20
Silberschatz, Galvin and Gagne ©2005
Windows XP Priorities: Some Rules
 Processes are typically members of the
NORMAL_PRIORITY_CLASS.

A process will belong to this class unless the parent of the
process was of the IDLE_PRIORITY_CLASS or unless another
class was specified when the process was created.
 The initial priority of a thread is typically the base priority of the
process the thread belongs to.
 When a thread’s time quantum runs out, the thread is
interrupted; if the thread is in the variable-priority class, its
priority is lowered. However, the priority is never lowered below
the base priority.
Operating System Concepts – 7th Edition, Feb 2, 2005
5.21
Silberschatz, Galvin and Gagne ©2005
Windows XP Priorities: Some Rules
 Lowering the thread’s priority tends to limit the CPU
consumption of compute-bound threads.
 When a variable-priority thread is released from a wait
operation, the dispatcher boosts the priority. The amount of
boost depends on what the thread is waiting for:

A thread that was waiting for keyboard I/O would get a large
increase

A threat that was waiting for a disk operation would get a
moderate increase
 Windows XP distinguishes between the foreground process that
is currently selected on the screen and the background
processes that are not currently selected. When a process
moves into the background, Windows XP increases the
scheduling quantum by some factor – typically by 3.
Operating System Concepts – 7th Edition, Feb 2, 2005
5.22
Silberschatz, Galvin and Gagne ©2005
End of Chapter 5