Transcript P 3

Chapter 5: CPU Scheduling
Chapter 5: CPU Scheduling
 Basic Concepts
 Scheduling Criteria
 Scheduling Algorithms
 Operating Systems Examples
5.2/42
Basic Concepts
 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. That is
followed by an I/O burst, which is followed by another
CPU burst, then another I/O burst, and so on.
Eventually, the final CPU burst ends with a system
request to terminate execution
CPU burst概念：一个进程在CPU上的一次连续执行过
程称为该进程的一个CPU周期。
一个CPU周期由进程自我终止。当进程需等待某个事
件而进入等待状态时，便终止了它的当前CPU周期。
P153
5.3/42
Alternating Sequence of CPU And I/O Bursts
5.4/42
CPU Burst
5.5/42
CPU Burst
 with a large number of short CPU bursts and a
small number of long CPU bursts.
 An I/O-bound program typically has many short
CPU bursts.
 A CPU-bound program might have a few long
CPU bursts.
 This distribution can be important in the selection
of an appropriate CPU-scheduling algorithm.
P154
5.6/42
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 under 1 and 4 is non-preemptive
 All other scheduling is preemptive
P156
5.7/42
调度方式
 非占先式调度（non preemptive）

一个进程一旦获得CPU便一直执行下去，直到完成它
的当前CPU Burst ，系统才被重新调度，换言之，OS
无权分割进程的任一CPU Burst 。
 占先式调度（preemptive）

当现行进程正在执行它的一个CPU周期期间，OS有权
强行分割该进程的当前CPU Burst，即强行剥夺现行进
程正占用的CPU，并把CPU分配给另一进程，换言之
，一个进程的一个CPU Burst可能被分割成两个或更多
个CPU Burst。
Which is better？
P156
5.8/42
调度方式
 非占先式调度（non preemptive）

如果一个进程陷入死循环，怎么办？
 占先式调度（preemptive）

避免了上述问题

Unfortunately, preemptive scheduling incurs a cost
associated with access to shared data.----inconsistent
state.

Preemption also affects the design of the operatingsystem kernel.
ensures
that the kernel structure is simple, since the
kernel will not preempt a process while the kernel
data structures are in an inconsistent state.
5.9/42
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
 Dispatch latency – time it takes for the dispatcher to
stop one process and start another running
 The dispatcher should be as fast as possible, since
it is invoked during every process switch.
P157
5.10/42
Scheduling Criteria
 CPU utilization – keep the CPU as busy as possible
 Throughput – # of processes that complete their execution
per time unit
 Turnaround time

The interval from the time of submission of a process to
the time of completion.

Turnaround time is the sum of the periods spent waiting
to get into memory, waiting in the ready queue,
executing on the CPU, and doing I/O.
 Waiting time – amount of time a process has been waiting
in the ready queue
P157
调度算法不影响进程的总的执行时间和I/O操作时间。
只影响进程在就绪队列等待被调度的时间。
5.11/42
Scheduling Criteria
 Response time – amount of time it takes from when a
request was submitted until the first response is
produced, not output (for time-sharing environment)
--------------------------------- Max CPU utilization
 Max throughput
 Min turnaround time
 Min waiting time
 Min response time
5.12/42
Optimization Criteria
 each being a sequence of several hundred CPU
bursts and I/O bursts.
 For simplicity, though, we consider only one CPU
burst per process in our examples.
 Our measure of comparison is the average waiting
time.
5.13/42
First-Come, First-Served (FCFS) Scheduling
Process
P1
P2
Burst Time
24
3
P3
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
P158
5.14/42
FCFS Scheduling (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
30
 Waiting time for P1 = 6; P2 = 0; P3 = 3
 Average waiting time: (6 + 0 + 3)/3 = 3
 Much better than previous case
 Convoy effect :all the other processes wait for the one
big process to get off the CPU.
5.15/42
FCFS Scheduling 特点
 实现简单，自然；
 属于非占先调度；
 平均等待时间一般比较长；
 有利于长（CPU burst）进程，不利于短（CPU
burst）进程。
5.16/42
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
 Two schemes:

nonpreemptive – once CPU given to the process it cannot
be preempted until completes its CPU burst

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)
P160
5.17/42
Shortest-Job-First (SJF) Scheduling
 SJF is optimal – gives minimum average waiting time for a
given set of processes
 The real difficulty with the SJF algorithm is knowing the
length of the next CPU request.
5.18/42
Example of Non-Preemptive SJF
Process Arrival Time
Burst Time
P1
0.0
7
P2
2.0
4
P3
4.0
1
P4
5.0
4
 SJF (non-preemptive)
P1
0
3
P3
7
P2
8
P4
12
16
 Average waiting time = (0 + 6 + 3 + 7)/4 = 4
5.19/42
Example of Preemptive SJF
Process Arrival Time
Burst Time
P1
0.0
7
P2
2.0
4
P3
4.0
1
P4
5.0
4
 SJF (preemptive)
P1
0
P2
2
P3
4
P2
5
P4
P1
11
7
16
 Average waiting time = (9 + 1 + 0 +2)/4 = 3
5.20/42
SJF Scheduling特点
 有效地降低作业的平均等待时间，提高了系统的吞吐量；
 对长作业十分不利。饿死现象。
 未完全考虑作业的紧迫程度；
 估算作业（进程）的执行时间非常困难。
5.21/42
Priority Scheduling
 A priority number (integer) is associated with each
process, the CPU is allocated to the process with the
highest priority, Equal-priority processes are
scheduled in FCFS order.
P162
5.22/42
Priority Scheduling
5.23/42
Priority Scheduling
 Equal-priority processes are scheduled in FCFS order.
 An SJF algorithm is simply a priority algorithm where the
priority is the inverse of the (predicted) next CPU burst.
 Priority scheduling can be either preemptive or non-
preemptive.
 A major problem with priority scheduling algorithms is
indefinite blocking, or starvation.

(Rumor has it that, when they shut down the IBM 7094
at MIT in 1973, they found a low-priority process that
had been submitted in 1967 and had not yet been run.)
 Aging: gradually increasing the priority of processes that
wait in the system for a long time.
P163
5.24/42
Priority Scheduling
 Priorities can be defined either internally or externally.
 Internally defined priorities use some measurable quantity
or quantities to compute the priority of a process. For
example, time limits, memory requirements, the number of
open files, and the ratio of average I/O burst to average
CPU burst have been used in computing priorities.
 External priorities are set by criteria outside the operating
system, such as the importance of the process, the type
and amount of funds being paid for computer use, the
department sponsoring the work, and other, often political,
factors.
5.25/42
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.
 The process may have a CPU burst of less than 1 time
quantum. In this case, the process itself will release the
CPU voluntarily. The scheduler will then proceed to the
next process in 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. No
process waits more than (n-1)q time units.
P164
5.26/42
Example of RR with Time Quantum = 20
Process
P1
P2
P3
Burst Time
53
17
68
P4
 The Gantt chart is:
P1
0
P2
20
37
P3
P4
57
24
P1
77
P3
97 117
P4
P1
P3
P3
121 134 154 162
 Typically, higher average turnaround than SJF,
but better response
5.27/42
Round Robin (RR)
 The performance of the RR algorithm depends heavily
on the size of the time quantum.

q large  FIFO

q small  q must be large with respect to context
switch, otherwise overhead is too high
 Although the time quantum should be large compared
with the context switch time, it should not be too large.
5.28/42
Time Quantum and Context Switch Time
5.29/42
Multilevel Queue
 Ready queue is partitioned into separate queues
 Each queue has its own scheduling algorithm
 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,20% to
background in FCFS
P166-167
5.30/42
Multilevel Queue Scheduling
5.31/42
Multilevel Feedback Queue
 设置多个就绪队列，并为各个队列赋予不同的优先权。第一
个队列的优先权最高，第二队列次之，其余队列的优先权逐
个降低。
 赋予各个队列中进程执行时间片的大小也各不相同，优先权
越高，时间片越小。
 当一个新进程进入内存后，首先将它放入第一队列的末尾，
按FCFS原则排队等待调度。当轮到该进程执行时，如能在该
时间片内完成，便可准备撤离系统；如果它在一个时间片结
束时尚未完成，调度程序便将该进程转入第二队列的末尾，
再同样地按FCFS原则等待调度执行；如果它在第二队列中运
行一个时间片后仍未完成，再依法将它转入第三队列。如此
下去，当一个长进程从第一队列降到第n队列后，在第n队列
中便采取按时间片轮转的方式运行。
P168
5.32/42
Multilevel Feedback Queue
 仅当第一队列空闲时，调度程序才调度第二队列中的进程运
行；仅当第1~（i-1）队列均空时，才会调度第i队列中的进程
运行。
 如果处理机正在第i队列中为某进程服务时，又有新进程进入
优先权较高的队列，则此时新进程将抢占正在运行进程的处
理机，由调度程序把正在运行进程放回第i队列末尾，重新把
处理机分配给新进程。
5.33/42
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.
5.34/42
Multilevel Feedback Queues
5.35/42
Multilevel Feedback Queue
 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
5.36/42
Windows XP Scheduling
 Windows XP schedules threads using a priority-based,
preemptive scheduling algorithm.
 The Windows XP scheduler ensures that the highest-
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 I/O.
 If a higher-priority real-time thread becomes ready while a
lower-priority thread is running, the lower-priority thread
will be preempted.
P177-179
5.37/42
Windows XP Scheduling
 The dispatcher uses a 32-level priority scheme to determine
the order of thread execution. Priorities are divided into two
classes.
 The variable class contains threads having priorities from 1 to
15,
 the real-time class contains threads with priorities ranging
from 16 to 31.
 (There is also a thread running at priority 0 that is used for
memory management.)
 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.
5.38/42
Windows XP Scheduling
 The Win32 API identifies several priority classes to which a
process can belong. These include 6 classes (see p177).
 Priorities in all classes except the REALTIME-PRIORITY-
CLASS are variable, meaning that the priority of a thread
belonging to one of these classes can change.
 Within each of the priority classes is a relative priority. The
values for relative priority include:

TIME-CRITICAL、HIGHEST、ABOVE-NORMAL、
NORMAL、BELOW-NORMAL、LOWEST、IDLE
5.39/42
Windows XP Priorities
5.40/42
Windows XP Scheduling
 When a thread's time quantum runs out, that thread is
interrupted; if the thread is in the variable-priority class, its
priority is lowered.
 The priority is never lowered below the base priority,
however. 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
the boost depends on what the thread was waiting for; for
example, a thread that was waiting for keyboard I/O would
get a large increase, whereas a thread waiting for a disk
operation would get a moderate one. This strategy tends to
give good response times to interactive threads that are
using the mouse and windows.
5.41/42
Homework：1、2、4、5、6、7、9、10
End of Chapter 5