Chapter 6: CPU Scheduling CPU调度

Chapter 6: CPU Scheduling CPU调度
6.1 Basic Concepts 基本概念 6.2 Scheduling Criteria 调度准则 6.3 Scheduling Algorithms 调度算法 6.4 Multiple-Processor Scheduling 多处理器调度 6.5 Real-Time Scheduling 实时调度 6.6 Algorithm Evaluation 算法评估 6.7 Process Scheduling Models 进程调度模型 Operating System Concepts

6.1 Basic Concepts Maximum CPU utilization obtained with multiprogramming 通过多道程序设计得到CPU的最高利用率处理机管理的工作是对CPU资源进行合理的分配和使用，以提高处理机利用率，并使各用户公平地得到处理机资源。这里的主要问题是处理机调度算法和调度算法特征分析 CPU–I/O Burst Cycle – Process execution consists of a cycle of CPU execution and I/O wait. CPU-I/O脉冲周期 - 进程的执行包括进程在CPU上执行和等待I/O CPU burst distribution CPU脉冲的分布 I/O burst Operating System Concepts

Fig 6.1 Alternating Sequence of CPU And I/O Bursts
Operating System Concepts

Histogram of CPU-burst Times

1. 按照调度的层次 6.1.1 调度的类型(scheduling)
从处理机调度的对象、时间、功能等不同角度，我们可把处理机调度分成不同类型。 1. 按照调度的层次作业调度：又称为"宏观调度"、"高级调度"。从用户工作流程的角度，一次提交的若干个流程，其中每个程序按照进程调度。时间上通常是分钟、小时或天。内外存交换：又称为"中级调度"。从存储器资源的角度。将进程的部分或全部换出到外存上，将当前所需部分换入到内存。指令和数据必须在内存里才能被CPU直接访问。进程或线程调度：又称为"微观调度"、"低级调度"。从CPU资源的角度，执行的单位。时间上通常是毫秒。因为执行频繁，要求在实现时达到高效率。 Operating System Concepts

处理机调度的层次 Operating System Concepts

2. 按照调度的时间周期长期(long-term)：将进程投入"允许执行"进程缓冲池中，或送到"退出"进程缓冲池中。进程状态：New－>Ready suspend, Running －>Exit 中期(medium-term)：将进程的部分或全部加载到内存中。进程状态：Ready <－>Ready suspend, Blocked <－>Blocked suspend 短期(short-term)：选择哪个进程在处理机上执行。进程状态：Ready <－>Running I/O调度：选择哪个I/O等待进程，使其请求可以被空闲的I/O设备进行处理。 Operating System Concepts

3. 按照OS的分类批处理调度－－应用场合：大中型主机集中计算，如工程计算、理论计算（流体力学）
分时调度、实时调度：通常没有专门的作业调度多处理机调度 Operating System Concepts

6.1.2 CPU Scheduler CPU调度 (short-term scheduler)
Selects from among the processes in memory that are ready to execute, and allocates the CPU to one of them.选择内存中的就绪进程，并分配CPU给其中之一 CPU scheduling decisions may take place when a process: CPU调度可能发生在当一个进程: 1.Switches from running to waiting state.从运行转到等待 2. Switches from running to ready state.从运行转到就绪 3.Switches from waiting to ready.从等待转到就绪 4.Terminates.终止运行 Operating System Concepts

6.1.3 Preemptive Scheduling
Scheduling under 1 and 4 is nonpreemptive. 发生在1、4两种情况下的调度称为非抢占式调度：分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程。 All other scheduling is preemptive. 其他情况下发生的调度称为抢占式调度：当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。剥夺原则有：优先权原则、短进程优先原则、时间片原则。 Operating System Concepts

6.1.4 Dispatcher Dispatcher module gives control of the CPU to the process selected by the short-term scheduler; this involves:进程调度模块负责将对CPU的控制权转交给由CPU调度程序，包括 : 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. 调度时间 – 调度程序终止一个进程的运行并启动另一个进程运行所花的时间. Operating System Concepts

6.2 Scheduling Criteria 调度准则
CPU utilization – keep the CPU as busy as possible CPU利用率 – 使CPU尽可能的忙碌 Throughput – # of processes that complete their execution per time unit 吞吐量 – 单位时间内运行完的进程数 Turnaround time – amount of time to execute a particular process 周转时间 – 进程从提交到运行结束的全部时间包括：在收容队列中等待，CPU上执行，就绪队列和阻塞队列中等待，结果输出等待－－批处理系统周转时间 T=完成时间-提交时间平均周转时间=∑周转时间/进程数带权周转时间W= T(周转时间)/t(CPU执行时间) 平均带权周转时间=∑W/进程数 Operating System Concepts

Scheduling Criteria (Cont.)
Waiting time – 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, not output (for time-sharing environment) 响应时间 – 从进程提出请求到首次被响应（而不是输出结果）的时间段（在分时系统环境下） Optimization Criteria：最优准则： Max CPU utilization　最大的CPU利用率 Max throughput　　　最大的吞吐量 Min turnaround time 最短的周转时间 Min waiting time 最短的等待时间 Min response time 最短的响应时间 Operating System Concepts

6.3 Scheduling Algorithms 调度算法
6.3.1 First-Come, First-Served (FCFS) Scheduling 先来先服务调度 6.3.2 Shortest-Job-First (SJR) Scheduling 短作业优先调度 6.3.3 Priority Scheduling 优先权调度 6.3.4 Round Robin (RR) 时间片轮转调度 6.3.5 Multilevel Queue Scheduling 多级队列调度 6.3.6 Multilevel Feedback Queue Scheduling 多级反馈队列调度 Operating System Concepts

6.3.1 First-Come, First-Served (FCFS) Scheduling先来先服务调度
这是最简单的调度算法，按先后顺序进行调度。 FCFS算法按照进程或作业提交变为就绪状态的先后次序，分派CPU；当前进程或作业占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。在进程或作业唤醒后（如I/O完成），并不立即恢复执行，通常等到当前作业或进程出让CPU。最简单的算法。 FCFS的特点比较有利于长作业，而不利于短作业。有利于CPU繁忙的作业，而不利于I/O繁忙的作业。 Operating System Concepts

6.3.1 First-Come, First-Served (FCFS) Scheduling先来先服务调度
Process Burst Time P1 24 P2 3 P3 3 Suppose that the processes arrive in the order: P1 , P2 , P 假定进程到达顺序如下: P1 , P2 , P3 The Gantt Chart for the schedule is:该调度的Gantt图为 Waiting time（等待时间） for P1 = 0; P2 = 24; P3 = 27 Average waiting time（平均等待时间）: ( )/3 = 17 P1 P2 P3 24 27 30 Operating System Concepts

FCFS Scheduling (Cont.)
Suppose that the processes arrive in the order （假定进程到达顺序如下） P2 , P3 , P1 . The Gantt chart for the schedule is:该调度的Gantt图为 Waiting time （等待时间） for P1 = 6; P2 = 0; P3 = 3 Average waiting time （平均等待时间） : ( )/3 = 3 Much better than previous case.比前例好得多 Convoy effect short process behind long process 此种结果产生是由于长进程先于短进程到达 P1 P3 P2 6 3 30 Operating System Concepts

6.3.2 Shortest-Job-First (SJF) Scheduling 短作业优先调度
又称为“短进程优先”SPF (Shortest Process First)；这是对FCFS算法的改进，其目标是减少平均周转时间。 1.SJF算法: 对预计执行时间短的作业（进程）优先分派处理机。通常后来的短作业不抢占正在执行的作业。 Operating System Concepts

2. SJF的特点优点：比FCFS改善平均周转时间和平均带权周转时间，缩短作业的等待时间；提高系统的吞吐量；缺点：
对长作业非常不利，可能长时间得不到执行；未能依据作业的紧迫程度来划分执行的优先级；难以准确估计作业（进程）的执行时间，从而影响调度性能。 Operating System Concepts

3. SJF的变型 "最短剩余时间优先"SRT(Shortest Remaining Time) 允许比当前进程剩余时间更短的进程来抢占
"最高响应比优先"HRRN(Highest Response Ratio Next) 响应比R = (等待时间 + 要求执行时间) / 要求执行时间是FCFS和SJF的折衷 Operating System Concepts

4. Two Schemes Associate with each process the length of its next CPU burst. Use these lengths to schedule the process with the shortest time. 关联到每个进程下次运行的CPU脉冲长度，调度最短的进程 Two schemes: nonpreemptive – once CPU given to the process it cannot be preempted until completes its CPU burst. 非抢占式调度 – 一旦进程拥有CPU，它的使用权限只能在该CPU 脉冲结束后让出. Operating System Concepts

抢占式调度 – 发生在有比当前进程剩余时间片更短的进程到达时，也称为最短剩余时间优先调度(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). 抢占式调度 – 发生在有比当前进程剩余时间片更短的进程到达时，也称为最短剩余时间优先调度(SRTF). SJF is optimal – gives minimum average waiting time for a given set of processes. SJF是最优的 ---- 对一组指定的进程而言，它给出了最短的平均等待时间 Operating System Concepts

5. Example of Non-Preemptive SJF
Process Arrival Time Burst Time P P P P SJF (non-preemptive) Average waiting time = ( )/4 = 4 P1 P3 P2 7 3 16 P4 8 12 Operating System Concepts

6. Example of Preemptive SJF
Process Arrival Time Burst Time P P P P SJF (preemptive) Average waiting time = ( )/4 = 3 P1 P3 P2 4 2 11 P4 5 7 16 Operating System Concepts

Determining Length of Next CPU Burst
Can only estimate the length.其长度只能估计 Can be done by using the length of previous CPU bursts, using exponential average（指数均值）. 可以通过先前的CPU脉冲长度及计算指数均值进行. : Define 4. 1 , 3. burst CPU next the for value predicted 2. of lenght actual 1. = + a t n th （a --常数加权因子） Operating System Concepts

Fig 6.3 Prediction of the Length of the Next CPU Burst

Examples 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 tn 0 Since both  and (1 - ) are less than or equal to 1, each successive term has less weight than its predecessor. Operating System Concepts

6.3.3 Priority Scheduling 优先权调度
该算法总是把处理机分配给就绪队列中具有最高优先权的进程。常用以下两种方法来确定进程的优先权：静态优先权静态优先权是在创建进程时确定的，在整个运行期间不再改变。依据有：进程类型、进程对资源的要求、用户要求的优先权。动态优先权动态优先权是基于某种原则，使进程的优先权随时间改变而改变。 A priority number (integer) is associated with each process 每个进程都有自己的优先数[整数] The CPU is allocated to the process with the highest priority (smallest integer  highest priority). CPU分配给最高优先级的进程（假定最小的整数  最高的优先级）. Preemptive　　　　抢占式 Nonpreemptive　　非抢占式 Operating System Concepts

Priority Scheduling (Cont.)
SJF is a priority scheduling where priority is the predicted next CPU burst time. 　SJF是以下一次CPU脉冲长度为优先数的优先级调度 Problem  Starvation – low priority processes may never execute. (infinite blocking) 　问题  饥饿 – 低优先级的可能永远得不到运行 Solution  Aging – as time progresses increase the priority of the process. 　解决方法  老化 – 视进程等待时间的延长提高其优先数 Operating System Concepts

6.3.4 Round Robin (RR) 时间片轮转调度
前几种算法主要用于宏观调度，说明怎样选择一个进程或作业开始运行，开始运行后的作法都相同，即运行到结束或阻塞，阻塞结束时等待当前进程放弃CPU 。本算法主要用于微观调度，说明怎样并发运行，即切换的方式；设计目标是提高资源利用率。其基本思路是通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率 Operating System Concepts

1. 时间片轮转算法将系统中所有的就绪进程按照FCFS原则，排成一个队列。
每次调度时将CPU分派给队首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。在一个时间片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，并通过上下文切换执行当前的队首进程。进程可以未使用完一个时间片，就出让CPU（如阻塞）。 Operating System Concepts

2. 时间片长度的确定 Each process gets a small unit of CPU time (time quantum), usually milliseconds. After this time has elapsed, the process is preempted and added to the end of the ready queue. 每个进程将得到小单位的CPU时间（时间片），通常为10-100毫秒。时间片用完后，该进程将被抢占并插入就绪队列末尾. 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. 　假定就绪队列中有n个进程、时间量为q, 则每个进程每次得到1/n的、不超过q单位的成块CPU时间，没有任何一个进程的等待时间会超过(n-1) q单位 Operating System Concepts

q过长 large－>退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。
时间片长度变化的影响 q过长 large－>退化为FCFS算法，进程在一个时间片内都执行完，响应时间长。 q过短 small－>用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，响应时间长。对响应时间的要求： T(响应时间)=N(进程数目)*q(时间片) 时间片长度的影响因素：就绪进程的数目：数目越多，时间片越小（当响应时间一定时）系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使响应时间、平均周转时间和平均带权周转时间延长。 Operating System Concepts

Example of RR with Time Quantum = 20
Process Burst Time P1 53 P2 17 P3 68 P4 24 The Gantt chart is: Typically, higher average turnaround than SJF, but better response.　典型的说，RR的平均周转时间比SJF长，但响应时间要短一些　。 P1 P2 P3 P4 20 37 57 77 97 117 121 134 154 162 Operating System Concepts

Fig 6.4 Time Quantum and Context Switch Time

Fig 6.5 Turnaround Time Varies With The Time Quantum
See book p.165 to compute turnaround time Operating System Concepts

To comupte turnaround time
Quantum=1 |------| p3=3 | | p2=9 | | p1=15 | | p4=17 So average turnaround time=( )/4 = 11.0 Operating System Concepts

6.3.5 Multilevel Queue Scheduling 多级队列调度
本算法引入多个就绪队列，通过各队列的区别对待，达到一个综合的调度目标根据作业或进程的性质或类型的不同，将就绪队列再分为若干个子队列。每个进程固定归入一个队列。各队列的不同处理：不同队列可有不同的优先级、时间片长度、调度策略等。如：系统进程、用户交互进程、批处理进程等。 Operating System Concepts

Multilevel Queue Scheduling (Cont.)
Ready queue is partitioned into separate queues: foreground (interactive) 前台（交互式） background (batch) 　　后台（批处理） Each queue has its own scheduling algorithm, 　每个队列有自己的调度算法　 foreground – RR　　　前台– RR 　background – FCFS　　后台– FCFS Operating System Concepts

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 。　给定时间片调度，即每个队列得到一定的CPU时间，进程在给定时间内执行；如，80%的时间执行前台的RR调度，20%的时间执行后台的FCFS调度 Operating System Concepts

Example Multilevel Queue
例:对于能同时支持批处理作业和交互式作业的通用操作系统，试设计一种较合理的进程调度算法。要求能保证交互式作业有合理的响应时间。解答： l、设置两个进程就绪队列Q1 ，Q2； Q1专供交互式作业所产生的进程使用； Q2专供批处理作业所产生的进程使用。 2、进程调度时优先在Q1中选择，Q1为空时再在Q2中选择； 3、对Q1中各进程实施时间片轮转法调度；对Q2中各进程可实施先来先服务调度。 Operating System Concepts

6.3.6 Multilevel Feedback Queue Scheduling 多级反馈队列调度
多级反馈队列算法是时间片轮转算法和优先级算法的综合和发展。优点：为提高系统吞吐量和缩短平均周转时间而照顾短进程为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程不必估计进程的执行时间，动态调节 Operating System Concepts

1. 多级反馈队列算法设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如逐级加倍新进程进入内存后，先投入队列1的末尾，按FCFS算法调度；若按队列1一个时间片未能执行完，则降低投入到队列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的队列，则按"时间片轮转"算法调度直到完成。仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢占执行新进程，并把被抢占的进程投入原队列的末尾。 Operating System Concepts

2. 几点说明 I/O型进程：让其进入最高优先级队列，以及时响应I/O交互。通常执行一个小时间片，要求可处理完一次I/O请求的数据，然后转入到阻塞队列。计算型进程：每次都执行完时间片，进入更低级队列。最终采用最大时间片来执行，减少调度次数。 I/O次数不多，而主要是CPU处理的进程：在I/O完成后，放回优先I/O请求时离开的队列，以免每次都回到最高优先级队列后再逐次下降。为适应一个进程在不同时间段的运行特点，I/O完成时，提高优先级；时间片用完时，降低优先级； Operating System Concepts

scheduling algorithms for each queue
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 　决定需要服务的进程将进入哪个队列的方法 Operating System Concepts

Multilevel Feedback Queue Scheduling (Cont.)
Example of Multilevel Feedback Queue Three queues: 三个队列 Q0 – time quantum 8 milliseconds Q1 – time quantum 16 milliseconds Q2 – FCFS Operating System Concepts

Example of Multilevel Feedback Queue
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. 　新的作业进入FCFS的Q0队列，它得到CPU时能使用8毫毫秒，如果它不能在8毫秒内完成，将移动到队列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. 　作业在Q1仍将作为FCFS调度，能使用附加的16毫秒，如果它还不能完成，将被抢占，移至队列Q2 。在队列Q2,采用FCFS调度算法。注意：仅当Q0 和Q1的队列均为空时，才会调度到Q2的作业 Operating System Concepts

Fig 6.7 Multilevel Feedback Queues

练习：进程调度实例假定在一个处理机上执行以下五个作业：(15分) 作业号到达时间运行时间(分) 优先数
作业号到达时间运行时间(分) 优先数 : : : : : 分别采用FCFS、SJF和非抢占优先数三种调度算法时，试： ①画出调度示图； ②计算每个作业的周转时间； ③计算平均周转时间。解答 Operating System Concepts

6.4 Multiple-Processor Scheduling 多处理器调度
CPU scheduling more complex when multiple CPUs are available. 多个CPU可用时，CPU调度将更为复杂 Homogeneous processors within a multiprocessor. 多处理器内的同类处理器 Load sharing 负载共享 Symmetric Multiprocessing (SMP) – each processor makes its own scheduling decisions 对称多处理器 – 每个处理器决定自己的调度方案 Operating System Concepts

Multiple-Processor Scheduling (Cont.)
Asymmetric multiprocessing – only one processor accesses the system data structures, alleviating the need for data sharing. 非对称多处理器 – 仅一个处理器能处理系统数据结构，这就减轻了对数据的共享需求 Operating System Concepts

6.5 Real-Time Scheduling 实时调度
Hard real-time systems – required to complete a critical task within a guaranteed amount of time. 硬件实现的实时系统 – 用于实现要求在给定的时间内执行完临界进程的场合 Soft real-time computing – requires that critical processes receive priority over less fortunate ones. 软件实现的实时计算 – 当要求临界进程得到比其他进程更高的优先级时 Conflict phase of dispatch latency has two components :调度等待的冲突状态有二部分： Preemption of any process running in the kernel 运行在内核任何进程的抢占 Release by low-priority processes resources needed by the high-priority process . 由低优先级进程释放高优先级进程所需的资源 Operating System Concepts

Fig 6.8 Dispatch Latency调度等待

6.6 Algorithm Evaluation 算法评估
define the criteria to be used in selecting an algorithm. 标准，例如： Maximize CPU utilization Maximize thoughput Describe the different evaluation methods in Section – 6.6.4: 不同的算法评估方法: Deterministic modeling (确定模型法) Queueing models (排队模型) Simulations (仿真) Implementation Operating System Concepts

6.6.1 Deterministic modeling 确定模型法
Deterministic modeling – One type of analytic evaluation, It takes a particular predetermined workload and defines the performance of each algorithm for that workload. 　确定模型法 – 分析评估之一。它精确预定作业量，并定义该作业量在每个算法上执行的情况。例如：p.173所提供的实例。 Too specific, and require too much exact knowledge, to be useful Operating System Concepts

6.6.2 Queuing models排队模型 The distribution of CPU and I/O bursts may be measured and then approximated or simply estimated. The result is a mathematical formula describing the probability of a particular CPU burst. CPU 和 I/O 字符组区分可以被度量，然后接近地或简单地评估。结果是一个数学公式描述一个特别CPU运行时间。 Queuing-network analysis : Each server has a queue of waiting processes. The CPU is a server with its ready queue, as is the I/O system with its device queues. Knowing arrival rates and service rates, we can compute utilization, average queue length, average wait time, and so on. 排队网分析：每个服务器有一个等待进程的队列。CPU 是一个带有就绪队列的服务器, 并包含有设备队列的 I/O 系统。确定的到达率和服务率, 我们就能计算利用率、平均的队列长度, 平均等待时间等等。 Operating System Concepts

6.6.3 Simulations 仿真通过仿真，可以对调度算法进行更为精确的评估可以通过随机数发生器产生仿真的驱动数据
6.6.4 Implementation 实现要得到更为精确的缺乏评估数据，唯一的办法只能是：code it。通过编程，把算法写出来，进行实地运行困难：实现成本算法的运行环境 Operating System Concepts

Fig 6.9 Evaluation of CPU Schedulers by Simulation

6.7 Process Scheduling Models 进程调度模型
Process Local Scheduling – How the threads library decides which thread to put onto an available LWP.进程局部调度– 线程库如何来决定将哪一个(用户级)线程与一个能够获得的轻量级线程(LWP)相对应 System Global Scheduling – How the kernel decides which kernel thread to run next 系统全局调度 – 内核怎样决定下一个运行的内核线程线程调度主要有软件库来完成，而非操作系统所决定 6.7.1 An Example : Solaris 6.7.2 An Example : Windows 2000 6.7.3 An Example : Linux Operating System Concepts

6.7.1 An Example : Solaris Priority-based process scheduling
Four class of scheduling Real time [highest priority] System [ to run kernel process] Time sharing [default] Interactive Each class includes different priority and scheduling algorithms Reverse relationship between priorities and time slices： the higher the priority, the smaller the time slice The selected thread runs on the CPU until It blocks It uses its time slice It is preempted by a higher-priority thread Operating System Concepts

Fig 6.10 Solaris 2 Scheduling

6.7.2 An Example : Windows 2000 Threads are scheduled using a priority-based, preemptive scheduling algorithms The selected thread runs on the CPU until It terminates It uses its time slice It is preempted by a higher-priority thread It calls a blocking system call, such as for I/O Dispatcher use a 32-level priority scheme Two classes of priorities: Variable class, 1-15 Real-time class, 16-31 6.7.3 An Example : Linux Operating System Concepts

Fig 6.11 Windows 2000 Priorities
Priority classes Relative priority Operating System Concepts

6.7.3 An Example : Linux Two separate process-scheduling algorithms:
Prioritized, credit-based algorithm (基于信用的算法) Time-sharing For fairness (公正性) credits = credit /2 +priority FCFS +RR, Absolute priority for real-time tasks Soft real-time Operating System Concepts

下列内容为自学资料（*） 1、传统UNIX的进程调度 2、 Windows 2000调度 Operating System Concepts

6.7.1 传统UNIX的进程调度未设置作业调度，进程调度采用基于时间片的多级反馈队列算法，进程优先级分为核心优先级和用户优先级。 1. 调度时机调度由0号进程完成（始终在核心态执行，与其他进程并不完全一样）。时机：进程由核心态转入用户态时：在每次执行核心代码之后返回用户态之前，检查各就绪进程的优先级并进行调度。如中断――进程回到就绪队列进程主动放弃处理机时：进程申请系统资源而未得到满足（如read），或进行进程间同步而暂停（如wait或pause），进程退出（如exit）――进程进入阻塞队列或exit状态。 Operating System Concepts

2. 用户优先级进程在用户态和核心态的优先级是不同的，这里说的是用户态进程的优先级。它是基于执行时间的动态优先级，进程优先级可为0~127之间的任一整数。优先数越大，优先级越低。 0~49之间的优先级为系统内核保留用户态下的进程优先级为50~127之间 Operating System Concepts

在UNIX System V中，进程优先数： P_pri = P_CPU / 2 + PUSER + P_nice + NZERO
系统设置部分：PUSER和NZERO是基本用户优先数的阈值，分别为25和20 CPU使用时间部分：P_CPU表示该进程最近一次CPU使用时间。每次时钟中断则该值加1（最多可达80）。如果时钟中断的周期为16.6ms，则每秒钟过后将该值为60。新创建进程的P_CPU值为0，因而具有较高的优先级。不同系统对P_CPU的计算方法有所不同。有的固定一个因子，有的会考虑系统负荷。用户设置部分：P_nice是用户可以通过系统调用设置的一个优先级偏移值。默认为20。超级用户可以设置其在0到39之间，而普通用户只能增大该值（即降低优先级）。 Operating System Concepts

3. 核心优先级内核把进程阻塞事件与一个睡眠优先级（0~49）联系起来；当进程从阻塞中醒来时，可及时进行处理。如：
磁盘I/O操作对应的睡眠优先级为20 终端输入操作对应的睡眠优先级为29。核心优先级分为可中断和不可中断两类优先级。当一个软中断信号到达时，若进程正在可中断优先级上阻塞，则进程立即被唤醒；若正在不可中断优先级上，则继续阻塞。其中：不可中断优先级：对换，等待磁盘I/O，等待缓冲区，等待文件索引结点－－关键操作，应该很快完成可中断优先级：等待tty（虚终端）I/O，等待子进程退出 Operating System Concepts

4. 调度的实现：分三个阶段检查是否作上下文切换（runrun标志）和核心是否允许作上下文切换（对核心的各种数据结构的操作都已经完成，核心处于正确的状态）。如果允许作上下文切换，则保存当前进程的上下文。恢复0号进程的上下文，然后执行0号进程，寻找最高优先级的就绪进程，如果没有这样的进程存在，则执行idle过程。如果有这样的进程存在，则该进程作为当前进程分派处理机，保存0号进程的上下文。恢复当前进程的上下文，执行该进程。 Operating System Concepts

6.7.2 Windows 2000/XP的线程调度 Windows 2000/XP的处理机调度的调度对象是线程。Windows 2000/XP的线程调度并不是单纯使用某一种调度算法，而是多种算法的综合体，针对实际系统的需要进行针对性的优化和改进。返回 Operating System Concepts

6.7.2.1 Windows 2000/XP线程状态 6.7.2.2 Windows 2000/XP的线程调度特征
线程优先级线程时间配额调度数据结构调度策略线程优先级提升对称多处理机系统上的线程调度空闲线程 Operating System Concepts

Windows 2000/XP线程状态 Windows 2000/XP的线程是内核线程，系统的处理机调度对象为线程。Windows 2000/XP把线程状态分成下面七种状态，与单挂起进程模型很相似，它们的主要区别在于从就绪状态到运行状态的转换中间多上一个备用状态，以优化线程的抢占特征。返回 Operating System Concepts

Operating System Concepts

就绪状态(Ready)：线程已获得除处理机外的所需资源，正等待调度执行。
备用状态(Standby)：已选择好线程的执行处理机，正等待描述表切换，以进入运行状态。系统中每个处理机上只能有一个处于备用状态的线程。运行状态(Running)：已完成描述表切换，线程进入运行状态。线程会一直处于运行状态，直到被抢占、时间片用完、线程终止或进入等待状态。等待状态(Waiting)：线程正等待某对象，以同步线程的执行。当等待事件出现时，等待结束，并根据优先级进入运行或就绪状态。转换状态(Transition)：转换状态与就绪状态类似，但线程的内核堆栈位于外存。当线程等待事件出现而它的内核堆栈处于外存时，线程进入转换状态；当线程内核堆栈被调回内存时，线程进入就绪状态。终止状态(Terminated)：线程执行完就进入终止状态；如执行体有一指向线程对象的指针，可将处于终止状态的线程对象重新初始化，并再次使用。初始化状态(Initialized)：线程创建过程中的线程状态； Operating System Concepts

Windows 2000/XP的线程控制 CreateThread完成线程创建，在调用进程的地址空间上创建一个线程，以执行指定的函数；它的返回值为所创建线程的句柄。 ExitThread用于结束当前线程。 SuspendThread可挂起指定的线程。 ResumeThread可激活指定线程，它的对应操作是递减指定线程的挂起计数，当挂起计数减为0时，线程恢复执行。 Operating System Concepts

调度单位是线程而不是进程，采用严格的抢占式动态优先级调度，依据优先级和分配时间配额来调度。
Windows 2000/XP的线程调度特征调度单位是线程而不是进程，采用严格的抢占式动态优先级调度，依据优先级和分配时间配额来调度。每个优先级的就绪线程排成一个先进先出队列；当一个线程状态变成就绪时，它可能立即运行或排到相应优先级队列的尾部。总运行优先级最高的就绪线程；返回 Operating System Concepts

完全的事件驱动机制，在被抢占前没有保证的运行时间；没有形式的调度循环；进入就绪事件；时间配额用完事件；优先级改变事件；
亲合处理机集合改变事件；在同一优先级的各线程按时间片轮转算法进行调度；在多处理机系统中多个线程并行运行； Operating System Concepts

6.7.2.3 Win32中与线程调度相关的API 返回 Suspend/ResumeThread Get/SetPriorityClass
Get/SetThreadPriority Get/SetProcessPriorityBoost Get/SetThreadPriorityBoost Get/SetProcessAffinityMask SetThreadAffinityMask SetThreadIdealProcessor SwitchToThread Sleep SleepEx 返回 Operating System Concepts

线程优先级 Operating System Concepts

Operating System Concepts

Fig . Windows 2000 Priorities

1. 实时优先级在应用程序中，要把线程的优先级提升到实时优先级，用户必须有升高线程优先级的权限。
如果用户进程在实时优先级运行时间过多，它将可能阻塞关键系统功能的执行，阻塞系统线程的运行；但不会阻塞硬件中断处理。在被其他线程抢占时，具有实时优先级线程与具有可变优先级线程的行为是不同的。 Windows 2000/XP并不是通常意义上的实时，并不提供实时操作系统服务。 Operating System Concepts

2. 中断优先级与线程优先级的关系 Operating System Concepts

线程时间配额时间配额是一个线程从进入运行状态到Windows 2000/XP检查是否有其他优先级相同的线程需要开始运行之间的时间总和。一个线程用完了自己的时间配额时，如果没有其它相同优先级线程，Windows 2000/XP将重新给该线程分配一个新的时间配额，并继续运行。时间配额不是一个时间长度值，而一个称为配额单位(quantum unit)的整数。返回 Operating System Concepts

1. 时间配额的计算缺省时，在Windows 2000专业版中线程时间配额为6；而在Windows 2000服务器中线程时间配额为36。
每次时钟中断，时钟中断服务例程从线程的时间配额中减少一个固定值(3)。如果没有剩余的时间配额，系统将触发时间配额用完处理，选择另外一个线程进入运行状态。在Windows 2000专业版中，由于每个时钟中断时减少的时间配额为3，一个线程的缺省运行时间为2个时钟中断间隔；在Windows 2000服务器中，一个线程的缺省运行时间为12个时钟中断间隔。 Operating System Concepts

不同硬件平台的时钟中断间隔是不同的，时钟中断的频率是由硬件抽象层确定的，而不是内核确定的。
如果时钟中断出现时系统正在处在DPC/线程调度层次以上(如系统正在执行一个延迟过程调用或一个中断服务例程)，当前线程的时间配额仍然要减少。甚至在整个时钟中断间隔期间，当前线程一条指令也没有执行，它的时间配额在时钟中断中也会被减少。不同硬件平台的时钟中断间隔是不同的，时钟中断的频率是由硬件抽象层确定的，而不是内核确定的。例如，大多数x86单处理机系统的时钟中断间隔为10毫秒，大多数x86多处理机系统的时钟中断间隔为15毫秒。 Operating System Concepts

这种部分减少时间配额的做法可解决线程在时钟中断触发前进入等待状态所产生的问题。
在等待完成时允许减少部分时间配额。当优先级小于14的线程执行一个等待函数(如WaitForSingleObject或WaitForMultipleObjects)时，它的时间配额被减少1个时间配额单位。当优先级大于等于14的线程在执行完等待函数后，它的时间配额被重置。这种部分减少时间配额的做法可解决线程在时钟中断触发前进入等待状态所产生的问题。如果不进行这种部分减少时间配额操作，一个线程可能永远不减少它的时间配额。例如，一个线程运行一段时间后进入等待状态，再运行一段时间后又进入等待状态，但在时钟中断出现时它都不是当前线程，则它的时间配额永远也不会因为运行而减少。 Operating System Concepts

提高前台线程优先级的问题假设用户首先启动了一个运行时间很长的电子表格计算程序，然后切换到一个计算密集型的应用(如一个需要复杂图形显示的游戏)。如果前台的游戏进程提高它的优先级，后台的电子表格将会几乎得不到CPU时间。但增加游戏进程的时间配额，则不会停止电子表格计算的执行，只是给游戏进程的CPU时间多一些。如果用户希望运行一个交互式应用程序时的优先级比其他交互进程的优先级高，可利用任务管理器来修改进程的优先级类型为中上或高级，也可利用命令行在启动应用时使用命令“start /abovenormal”或“start /high”来设置进程优先级类型。 Operating System Concepts

调度数据结构返回 Operating System Concepts

就绪位图(KiReadySummary)
为了提高调度速度，Windows 2000维护了一个称为就绪位图(KiReadySummary)的32位量。就绪位图中的每一位指示一个调度优先级的就绪队列中是否有线程等待运行。B0与调度优先级0相对应，B1与调度优先级1相对应，等待。空闲位图(KiIdleSummary) Windows 2000还维护一个称为空闲位图(KiIdleSummary)的32位量。空闲位图中的每一位指示一个处理机是否处于空闲状态。调度器自旋锁(KiDispatcherLock) 为了防止调度器代码与线程在访问调度器数据结构时发生冲突，处理机调度仅出现在DPC/调度层次。但在多处理机系统中，修改调度器数据结构需要额外的步骤来得到内核调度器自旋锁(KiDispatcherLock)，以协调各处理机对调度器数据结构的访问。 Operating System Concepts

调度策略 Windows 2000/XP严格基于线程的优先级来确定哪一个线程将占用处理机并进入运行状态。Windows 2000/XP在单处理机系统和多处理机系统中的线程调度是不同的。我们首先介绍单处理机系统中线程调度。返回 Operating System Concepts

1. 主动切换 Operating System Concepts

许多Win32等待函数调用(如WaitForSingleObject或WaitForMultipleObjects等)都使线程等待某个对象，等待的对象可能有事件、互斥信号量、资源信号量、I/O操作、进程、线程、窗口消息等。通常进入等待状态线程的时间配额不会被重置，而是在等待事件出现时，线程的时间配额被减1，相当于1/3个时钟间隔；如果线程的优先级大于等于14，在等待事件出现时，线程的时间配额被重置。 Operating System Concepts

2. 抢占当一个高优先级线程进入就绪状态时，正在处于运行状态的低优先级线程被抢占。 Operating System Concepts

高优先级线程的等待完成，即一个线程等待的事件出现。一个线程的优先级被增加或减少。用户态下运行的线程可以抢占内核态下运行的线程。
可能在以下两种情况下出现抢占：高优先级线程的等待完成，即一个线程等待的事件出现。一个线程的优先级被增加或减少。用户态下运行的线程可以抢占内核态下运行的线程。在判断一个线程是否被抢占时，并不考虑线程处于用户态还是内核态，调度器只是依据线程优先级进行判断。当线程被抢占时，它被放回相应优先级的就绪队列的队首。处于实时优先级的线程在被抢占时，时间配额被重置为一个完整的时间配额；处于动态优先级的线程在被抢占时，时间配额不变，重新得到处理机使用权后将运行到剩余的时间配额用完。 Operating System Concepts

3. 时间配额用完线程完整用完一个规定的时间片值时，重新赋予新时间片值，优先级降一级（不低于基本优先级），放在相应优先级就绪队列的尾部；

如果刚用完时间配额的线程优先级降低了，Windows 2000将寻找一个优先级高于刚用完时间配额线程的新设置值的就绪线程。
如果没有优先级相同的就绪线程可运行，刚用完时间配额的线程将得到一个新的时间配额并继续运行。 Operating System Concepts

4. 线程结束当线程完成运行时，它的状态从运行状态转到终止状态。线程完成运行的原因可能是通过调用ExitThread而从主函数中返回
通过被其他线程通过调用TerminateThread来终止。如果处于终止状态的线程对象上没有未关闭的句柄，则该线程将被从进程的线程列表中删除，相关数据结构将被释放。 Operating System Concepts

线程优先级提升线程由于调用等待函数而阻塞时，减少一个时间片，并依据等待事件类型提高优先级；如等待键盘事件比等待磁盘事件的提高幅度大。返回 Operating System Concepts

在下列5种情况下，Windows 2000会提升线程的当前优先级： I/O操作完成信号量或事件等待结束前台进程中的线程完成一个等待操作
由于窗口活动而唤醒图形用户接口线程线程处于就绪状态超过一定时间，但没能进入运行状态(处理机饥饿) 线程优先级提升的目的是改进系统吞吐量、响应时间等整体特征，解决线程调度策略中潜在的不公正性。但它也不是完美的，它并不会使所有应用都受益。 Windows 2000永远不会提升实时优先级范围内(16至31)的线程优先级。 Operating System Concepts

1. I/O操作完成后的线程优先级提升在完成I/O操作后，Windows 2000将临时提升等待该操作线程的优先级，以保证等待I/O操作的线程能有更多的机会立即开始处理得到的结果。为了避免I/O操作导致对某些线程的不公平偏好，在I/O操作完成后唤醒等待线程时将把该线程的时间配额减1。线程优先级的实际提升值是由设备驱动程序决定的。与I/O操作相关的线程优先级提升建议值在文件“Wdm.h”或“Ntddk.h”中。设备驱动程序在完成I/O请求时通过内核函数IoCompleteRequest来指定优先级提升的幅度。线程优先级的提升幅度与I/O请求的响应时间要求是一致的，响应时间要求越高，优先级提升幅度越大。 Operating System Concepts

线程优先级提升的建议值线程优先级提升是以线程的基本优先级为基点的，不是以线程的当前优先级为基点。
当用完它的一个时间配额后，线程会降低一个优先级，并运行另一个时间配额。这个降低过程会一直进行下去，直到线程的优先级降低至原来的基本优先级。优先级提升策略仅适用于可变优先级范围(0到15)内的线程。不管线程的优先级提升幅度有多大，提升后的优先级都不会超过15而进入实时优先级。 Operating System Concepts

2. 等待事件和信号量后的线程优先级提升当一个等待执行事件对象或信号量对象的线程完成等待后，它的优先级将提升一个优先级。
阻塞于事件或信号量的线程得到的处理机时间比处理机繁忙型线程要少，这种提升可减少这种不平衡带来的影响。 SetEvent、PulseEvent或ReleaseSemaphore函数调用可导致事件对象或信号量对象等待的结束。提升是以线程的基本优先级为基点的，而不是线程的当前优先级。提升后的优先级永远不会超过15。在等待结束时，线程的时间配额被减1，并在提升后的优先级上执行完剩余的时间配额；随后降低1个优先级，运行一个新的时间配额，直到优先级降低到初始的基本优先级。 Operating System Concepts

3. 前台线程在等待结束后的优先级提升对于前台进程中的线程，一个内核对象上的等待操作完成时，内核函数KiUnwaitThread会提升线程的当前优先级(不是线程的基本优先级)，提升幅度为变量PsPrioritySeparation的值。在前台应用完成它的等待操作时小幅提升它的优先级，以使它更有可能马上进入运行状态，有效改进前台应用的响应时间特征。用户不能禁止这种优先级提升，甚至是在用户已利用Win32的函数SetThreadPriorityBoost禁止了其他的优先级提升策略时，也是如此。 Operating System Concepts

4. 图形用户接口线程被唤醒后的优先级提升拥有窗口的线程在被窗口活动唤醒(如收到窗口消息)时将得到一个幅度为2的额外优先级提升。
窗口系统(Win32k.sys)在调用函数KeSetEvent时实施这种优先级提升，KeSetEvent函数调用设置一个事件，用于唤醒一个图形用户接口线程。这种优先级提升的原因是改进交互应用的响应时间。 Operating System Concepts

5. 对处理机饥饿线程的优先级提升系统线程“平衡集管理器(balance set manager)” 会每秒钟检查一次就绪队列，是否存在一直在就绪队列中排队超过300个时钟中断间隔的线程。如果找到这样的线程，平衡集管理器将把该线程的优先级提升到15，并分配给它一个长度为正常值两倍的时间配额；当被提升线程用完它的时间配额后，该线程的优先级立即衰减到它原来的基本优先级。 Operating System Concepts

如果在该线程结束前出现其他高优先级的就绪线程，该线程会被放回就绪队列，并在就绪队列中超过另外300个时钟中断间隔后再次被提升优先级。
平衡集管理器只扫描16个就绪线程。如果就绪队列中有更多的线程，它将记住暂停时的位置，并在下一次开始时从当前位置开始扫描。平衡集管理器在每次扫描时最多提升10个线程的优先级。如果在一次扫描中已提升了10个线程的优先级，平衡集管理器会停止本次扫描，并在下一次开始时从当前位置开始扫描。这种算法并不能解决所有优先级倒置的问题，但它很有效。 Operating System Concepts

对称多处理机系统上的线程调度当Windows 2000试图调度优先级最高的可执行线程时，有几个因素会影响到处理机的选择。Windows 2000只保证一个优先级最高的线程处于运行状态。返回 Operating System Concepts

1. 亲合关系(Affinity) 描述该线程可在哪些处理机上运行。线程的亲合掩码是从进程的亲合掩码继承得到的。
缺省时，所有进程(即所有线程)的亲合掩码为系统中所有可用处理机的集合。应用程序通过调用SetProcessAffinityMask或SetThreadAffinityMask函数来指定亲合掩码； Operating System Concepts

2. 线程的首选处理机和第二处理机首选处理机(ideal processor)：线程运行时的偏好处理机；
线程创建后，Windows 2000系统不会修改线程的首选处理机设置；应用程序可通过SetThreadIdealProcessor函数来修改线程的首选处理机。第二处理机(last processor)：线程第二个选择的运行处理机； Operating System Concepts

3. 就绪线程的运行处理机选择当线程进入运行状态时，Windows 2000首先试图调度该线程到一个空闲处理机上运行。如果有多个空闲处理机，线程调度器的调度顺序为：线程的首选处理机线程的第二处理机当前执行处理机(即正在执行调度器代码的处理机)。如果这些处理机都不是空闲的，Windows 2000将依据处理机标识从高到低扫描系统中的空闲处理机状态，选择找到的第一个空闲处理机。 Operating System Concepts

如果这两个处理机都不在线程的亲合掩码中，Windows 2000将依据活动处理机掩码选择该线程可运行的编号最大的处理机。
线程的首选处理机线程的第二处理机如果这两个处理机都不在线程的亲合掩码中，Windows 2000将依据活动处理机掩码选择该线程可运行的编号最大的处理机。 Windows 2000并不检查所有处理机上的运行线程和备用线程的优先级，而仅仅检查一个被选中处理机上的运行线程和备用线程的优先级。如果在被选中的处理机上没有线程可被抢占，则新线程放入相应优先级的就绪队列，并等待调度执行。 Operating System Concepts

如果被选中的处理机已有一个线程处于备用状态(即下一个在该处理机上运行的线程)，并且该线程的优先级低于正在检查的线程，则正在检查的线程取代原处于备用状态的线程，成为该处理机的下一个运行线程。
如果已有一个线程正在被选中的处理机上运行，Windows 2000将检查当前运行线程的优先级是否低于正在检查的线程；如果正在检查的线程优先级高，则标记当前运行线程为被抢占，系统会发出一个处理机间中断，以抢占正在运行的线程，让新线程在该处理机上运行。 Operating System Concepts

4. 为特定的处理机调度线程在多处理机系统，Windows 2000不能简单地从就绪队列中取第一个线程，它要在亲合掩码限制下寻找一个满足下列条件之一的线程。线程的上一次运行是在该处理机上；线程的首选处理机是该处理机；处于就绪状态的时间超过2个时间配额；优先级大于等于24；如果Windows 2000不能找到满足要求的线程，它将从就绪队列的队首取第一个线程进入运行状态。 Operating System Concepts

5. 最高优先级就绪线程可能不处于运行状态有可能出现这种情况，一个比当前正在运行线程优先级更高的线程处于就绪状态，但不能立即抢占当前线程，进入运行状态。例如：假设0号处理机上正运行着一个可在任何处理机上运行的优先级为8的线程，1号处理机上正运行着一个可在任何处理机上运行的优先级为4的线程；这时一个只能在0号处理机上运行的优先级为6的线程进入就绪状态。在这种情况下，优先级为6的线程只能等待0号处理机上优先级为8的线程结束。因为Windows 2000不会为了让优先级为6的线程在0号处理机上运行，而把优先级为8的线程从0号处理机移到1号处理机。即0号处理机上的优先级为8的线程不会抢占1号处理机上优先级为4的线程。 Operating System Concepts

6.7.2.10 空闲线程如果在一个处理机上没有可运行的线程，Windows 2000/XP会调度相应处理机对应的空闲线程。
由于在多处理机系统中可能两个处理机同时运行空闲线程，所以系统中的每个处理机都有一个对应的空闲线程。 Windows 2000/XP给空闲线程指定的线程优先级为0，该空闲线程只在没有其他线程要运行时才运行。返回 Operating System Concepts

Chapter 6: CPU Scheduling CPU调度

Similar presentations

Presentation on theme: "Chapter 6: CPU Scheduling CPU调度"— Presentation transcript:

Similar presentations

About project

反馈

请登录

Auth with social network:

Chapter 6: CPU Scheduling CPU调度

Similar presentations

Presentation on theme: "Chapter 6: CPU Scheduling CPU调度"— Presentation transcript:

Similar presentations

About project

反馈