OS-03中断与处理机调度

1、 处理器调度的类型处理器调度的类型 调度算法调度算法 Linux进程调度进程调度 Windows 2000/xp线程调度线程调度 中断：中断：在进程运行过程中出现某种紧急情况，必在进程运行过程中出现某种紧急情况，必须中止当前正在运行的程序，转去处理其它事件，须中止当前正在运行的程序，转去处理其它事件，处理完毕后恢复原来程序的运行。处理完毕后恢复原来程序的运行。 中断系统：中断系统：中断装置中断装置+中断处理程序中断处理程序 中断分类：中断分类：内中断和外中断；硬中断和软中断；内中断和外中断；硬中断和软中断；可屏蔽中断和不可屏蔽中断；强迫性中断和自愿可屏蔽中断和不可屏蔽中断；强迫性中断和自愿性中

2、断性中断 P49-59 ：选择性自学：选择性自学 操作系统必须为多个进程可能有竞争的请求分配计算机资操作系统必须为多个进程可能有竞争的请求分配计算机资源。对处理器而言，可分配的资源是在处理器上的执行时源。对处理器而言，可分配的资源是在处理器上的执行时间，分配途径是调度间，分配途径是调度 处理器调度处理器调度：指采用合理的策略和方法在多个可运行实体：指采用合理的策略和方法在多个可运行实体间分配间分配CPU资源。资源。 处理器调度算法处理器调度算法：按照什么原则和方法分配处理器资源：按照什么原则和方法分配处理器资源 处理机调度必须设计成可以满足多个目标，例如公平、任处理机调度必须设计成可以满足多个

3、目标，例如公平、任何进程都不会饿死、有效地使用处理器时间和低开销等何进程都不会饿死、有效地使用处理器时间和低开销等 面向用户准则所关心的性能指标面向用户准则所关心的性能指标 周转时间周转时间 T :指一个进程从提交到完成之间的时间间隔，指一个进程从提交到完成之间的时间间隔，包括实际执行时间加上等待时间（等待包括实际执行时间加上等待时间（等待+就绪）。就绪）。 带权的周转时间带权的周转时间 W：周转时间与执行时间的比值周转时间与执行时间的比值 响应时间响应时间 从提交一个请求到开始处理的时间间隔。从提交一个请求到开始处理的时间间隔。 最后期限最后期限 当可以指定进程完成的最后期限时，调度当可以指

4、定进程完成的最后期限时，调度原则将服从于其他目标，使得距最后期限最近原则将服从于其他目标，使得距最后期限最近 平均周转时间：平均周转时间： p61 平均带权周转时间平均带权周转时间： p61 面向面向系统准则所关心的性能指标系统准则所关心的性能指标 吞吐量吞吐量 单位时间内完成的任务数。调度策略将试图单位时间内完成的任务数。调度策略将试图使得每个时间单位完成的进程数目最大。使得每个时间单位完成的进程数目最大。 处理器使用率处理器使用率 处理器忙的时间百分比。尽量是处理器忙的时间百分比。尽量是CPU处于繁忙状态。处于繁忙状态。 公平公平 进程应该被平等对待，没有一个进程会被饿死进程应该被平等对待

5、，没有一个进程会被饿死 强制优先级强制优先级 当进程被指定了优先级，调度策略会先当进程被指定了优先级，调度策略会先选择高优先级的进程选择高优先级的进程 平衡资源平衡资源 保持系统中所有资源忙。这个准则也可用保持系统中所有资源忙。这个准则也可用于中程调度和长程调度于中程调度和长程调度多道程序的关键是调度。典型的调度类型有：多道程序的关键是调度。典型的调度类型有： 长程调度长程调度( (作业调度作业调度, ,高级调度）决定加入到待高级调度）决定加入到待执行的进程池中执行的进程池中 中程调度中程调度（交换调度（交换调度, ,中级调度）将进程调入内中级调度）将进程调入内存存, ,或者将进程交换到硬盘或

6、者将进程交换到硬盘 短程调度短程调度（进程调度，低级调度）决定哪一个（进程调度，低级调度）决定哪一个就绪进程将被处理器执行就绪进程将被处理器执行 线程调度线程调度：决定哪一个线程被处理器执行：决定哪一个线程被处理器执行下一次允许哪一个进程进入的下一次允许哪一个进程进入的决策决策可以基于简单可以基于简单的先来先服务原则，或者也可以基于管理系统性的先来先服务原则，或者也可以基于管理系统性能的工具能的工具使用的原则包括优先级、期待执行时间和使用的原则包括优先级、期待执行时间和I/O需求需求同样，可以根据请求哪个同样，可以根据请求哪个I/O资源和试图平衡资源和试图平衡I/O使用的目的进行决策使用的目的

7、进行决策中程调度的目标有中程调度的目标有2个：个：解决内存资源紧张的矛盾解决内存资源紧张的矛盾减小并发度以降低系统开销减小并发度以降低系统开销 中程调度算法将结合存储管理来设计。中程调度算法将结合存储管理来设计。从执行的频率看从执行的频率看 长程调度程序的执行频率相对低些，并且仅仅是长程调度程序的执行频率相对低些，并且仅仅是粗略地决定是否接受新进程以及接受哪一个粗略地决定是否接受新进程以及接受哪一个 为进行交换决策，中程调度程序执行得略微频繁为进行交换决策，中程调度程序执行得略微频繁一些一些 短程调度程序，即分派程序执行得最频繁，并且短程调度程序，即分派程序执行得最频繁，并且精确地决定下一次执

8、行哪一个进程精确地决定下一次执行哪一个进程根据已占有处理机的进程是否可被剥夺这一原则，根据已占有处理机的进程是否可被剥夺这一原则，调度方式（策略）可分为：调度方式（策略）可分为： 非剥夺方式：非剥夺方式：一旦某个就绪进程分得处理机之后，一旦某个就绪进程分得处理机之后，只要不是其自身的原因被阻塞只要不是其自身的原因被阻塞 ( (如要求如要求I/OI/O操作操作) ) 而不能继续运行时，就一直运行下去，直至运行而不能继续运行时，就一直运行下去，直至运行结束结束 缺点：紧急进程无法立即运行，实时性差；缺点：紧急进程无法立即运行，实时性差； 短进程周转时间长，公平性差。短进程周转时间长，公平性差。 剥

9、夺方式：剥夺方式：当一个正在运行的进程没有运行完时，当一个正在运行的进程没有运行完时，系统采取某种手段强行剥夺已分配给该进程的处理系统采取某种手段强行剥夺已分配给该进程的处理器资源。而被剥夺的进程重新回到就绪队列中等待器资源。而被剥夺的进程重新回到就绪队列中等待 在剥夺方式下，可以通过剥夺处理器所有权的方式，在剥夺方式下，可以通过剥夺处理器所有权的方式，暂停当前进程的运行，已满足更紧急进程的处理要暂停当前进程的运行，已满足更紧急进程的处理要求。求。v 有三个进程有三个进程p1，p2，p3到达时间为：到达时间为：0，3，4，优先级依，优先级依次增高，运行所需的时间分别为次增高，运行所需的时间分别

10、为20，4，2，假设现按优先，假设现按优先级策略调度执行，并且不采用时间片原则，请分别求出非级策略调度执行，并且不采用时间片原则，请分别求出非剥夺方式和剥夺方式下各个进程的周转时间。剥夺方式和剥夺方式下各个进程的周转时间。最短进程最短进程SPN（短进程优先调度算法）（短进程优先调度算法） 减少减少FCFSFCFS固有的对长进程的偏爱的另一种方法是固有的对长进程的偏爱的另一种方法是最短进程最短进程 (SPN) (SPN) 策略，策略，这是一种非剥夺的策略这是一种非剥夺的策略，其原则是下一次选择所需处理时间最短的进程，其原则是下一次选择所需处理时间最短的进程，因此，短进程将会越过长进程，得到优先运

11、行因此，短进程将会越过长进程，得到优先运行 SPNSPN策略的难点在于需要知道或至少需要估计每策略的难点在于需要知道或至少需要估计每个进程所需要的处理时间个进程所需要的处理时间 长进程可能被长进程可能被“饿死饿死”最短剩余时间优先调度算法最短剩余时间优先调度算法 (SRTN) 对对SPNSPN增加剥夺机制。当一个时钟中断周期到后，增加剥夺机制。当一个时钟中断周期到后，调度程序总是调度程序总是选择预期剩余时间最短选择预期剩余时间最短的进程的进程 当一个新进程加入就绪队列时，它可能比当前运当一个新进程加入就绪队列时，它可能比当前运行的进程具有更短的剩余时间，因此，调度程序行的进程具有更短的剩余时间

12、，因此，调度程序将剥夺当前程序，将处理器分配给新进程。将剥夺当前程序，将处理器分配给新进程。 和和SPNSPN一样，调度程序必须有关于处理时间的估一样，调度程序必须有关于处理时间的估计，并且存在长进程被饿死的危险计，并且存在长进程被饿死的危险最高响应比优先调度算法（最高响应比优先调度算法（HRRN） 响应比：响应比： R=(w+s)/s=1+w/sR=(w+s)/s=1+w/s w w表示等待时间；表示等待时间；s s表示执行所需时间表示执行所需时间 最高响应比也是对最短进程法的一种改进，当当最高响应比也是对最短进程法的一种改进，当当前进程完成或被阻塞时，前进程完成或被阻塞时，选择响应比最大的

13、进程选择响应比最大的进程先执行先执行，是一种，是一种非剥夺非剥夺的策略。的策略。 响应比响应比R R，代表了进程的年龄，算法在保证短进，代表了进程的年龄，算法在保证短进程优先的同时又兼顾了长进程程优先的同时又兼顾了长进程折中折中最高响应比优先调度算法（最高响应比优先调度算法（HRRN） R=(w+s)/s=1+w/sR=(w+s)/s=1+w/s 当一系列进程同时进入系统时，由于短作业当一系列进程同时进入系统时，由于短作业s s值值小，小，R R值就大，因此短作业得到了优先执行。值就大，因此短作业得到了优先执行。 但随着长作业等待的时间但随着长作业等待的时间(w)(w)增长，增长，R R值不断

14、增大，值不断增大，到达一定的等待时间，长进程最终将凭借年龄的到达一定的等待时间，长进程最终将凭借年龄的增长战胜短进程，从而获得处理器。增长战胜短进程，从而获得处理器。 可见，在可见，在HRRNHRRN算法中，长作业不会被饿死算法中，长作业不会被饿死 优先级调度算法：按进程的优先级调度，选择就绪优先级调度算法：按进程的优先级调度，选择就绪队列中优先级最高的进程到处理机上运行。队列中优先级最高的进程到处理机上运行。优先数确定方式：优先数确定方式： 静态优先级：每个进程创建时被赋予一个优先数，该优静态优先级：每个进程创建时被赋予一个优先数，该优先数在进程整个生命周期都是固定不变的。先数在进程整个生命

15、周期都是固定不变的。 动态优先级：每个进程被创建时被赋予一个优先数，该动态优先级：每个进程被创建时被赋予一个优先数，该优先数在进程的生命周期内是可以动态变化的优先数在进程的生命周期内是可以动态变化的 大多数动态优先级设计方案大多数动态优先级设计方案 把交互式和把交互式和I/OI/O频繁的进程移到优先级队列的顶端，而频繁的进程移到优先级队列的顶端，而让计算量大的进程移到较低的优先级上让计算量大的进程移到较低的优先级上 对与优先级相同的进程，按先来先服务或轮转法则分对与优先级相同的进程，按先来先服务或轮转法则分配处理机配处理机 对于一给定时间周期，一个正在运行的进程，每请求对于一给定时间周期，一个

16、正在运行的进程，每请求一次一次I/OI/O操作后其优先级就自动加操作后其优先级就自动加 1 1，直接反映出，直接反映出I/OI/O请求的频率，从而使请求的频率，从而使I/OI/O设备具有很高的利用率设备具有很高的利用率优先级调度算法分类：优先级调度算法分类： 非抢占的优先级调度法非抢占的优先级调度法：一旦一个高优先级的进程占有：一旦一个高优先级的进程占有了处理器，就一直运行下去，直到因等待某事被阻塞或了处理器，就一直运行下去，直到因等待某事被阻塞或执行结束，才选择就绪队列中优先级最高的进程来执行。执行结束，才选择就绪队列中优先级最高的进程来执行。 可抢占的优先级调度法可抢占的优先级调度法：任何

17、时刻都按照高优先级进程：任何时刻都按照高优先级进程在处理器上运行的原则进行进程调度。当一高优先级进在处理器上运行的原则进行进程调度。当一高优先级进程运行时，若有一更高优先级进程到达就绪队列，则当程运行时，若有一更高优先级进程到达就绪队列，则当前运行进程立刻将处理器让给更高优先级的进程（即使前运行进程立刻将处理器让给更高优先级的进程（即使未处理完，也无遇到阻塞情况）未处理完，也无遇到阻塞情况） 可抢占CPU Process Arrival time Priority Burst time P1 0 0 8 P2 2 1 5 P3 4 3 7 P4 0 2 3 P5 5 7 2 Gantt Cha

18、rt0 0 3 3 4 4 5 5 7 7 13 17 2513 17 25P1P4P2P2P3P3P50 0 3 3 4 4 5 5 7 7 13 17 2513 17 25P1P4P2P2P3P3P5轮转调度轮转调度 简单轮转法是以就绪队列中的所有进程均以相同的速简单轮转法是以就绪队列中的所有进程均以相同的速度往前推进为其特征。其时间片的长短，影响着进程度往前推进为其特征。其时间片的长短，影响着进程的进展速度的进展速度 当就绪进程很多时，如果时间片很长，就会影响一些当就绪进程很多时，如果时间片很长，就会影响一些需要需要“紧急紧急”运行的作业。同样这对短作业和要求运行的作业。同样这对短作业和

19、要求 I/O 操作多的作业显然是不利的操作多的作业显然是不利的 因而，在简单轮转法的基础上又提出了分级轮转法因而，在简单轮转法的基础上又提出了分级轮转法分级轮转法分级轮转法 将一个就绪队列根据进程的优先级不同，划分二将一个就绪队列根据进程的优先级不同，划分二个或二个以上的就绪队列，并赋给每个队列不同个或二个以上的就绪队列，并赋给每个队列不同的优先级，甚至可以分配不同的时间片的优先级，甚至可以分配不同的时间片 一般情况下，调度算法把相同的时间片分配给优一般情况下，调度算法把相同的时间片分配给优先级高的就绪队列中的队首进程先级高的就绪队列中的队首进程 只有当优先级高的就绪队列中的所有进程全部运只有

20、当优先级高的就绪队列中的所有进程全部运行完毕或等待行完毕或等待I/OI/O操作而没有进程运行时，才把操作而没有进程运行时，才把处理机分配给低优先级就绪队列中的进程处理机分配给低优先级就绪队列中的进程分级轮转法分级轮转法 为了公平性，低优先级就绪队列的进程如果获为了公平性，低优先级就绪队列的进程如果获得调度，将得到比高优先级就绪队列进程更多得调度，将得到比高优先级就绪队列进程更多的时间片，加以弥补的时间片，加以弥补 这样能大大降低长作业的交换频率，减少系统这样能大大降低长作业的交换频率，减少系统在交换作业时的时间消耗，又给了短作业较高在交换作业时的时间消耗，又给了短作业较高的优先级的优先级反馈反

21、馈FB（多级反馈队列调度算法）（多级反馈队列调度算法） 分级轮转调度和动态优先级算法的结合，分级轮转调度和动态优先级算法的结合，采用剥夺策略采用剥夺策略 划分多个就绪队列，优先级逐步降低。划分多个就绪队列，优先级逐步降低。 新建进程进入优先级最高的队列中，每当进程规定的时新建进程进入优先级最高的队列中，每当进程规定的时间片用完，被剥夺时，就送往低一级的就绪队列。间片用完，被剥夺时，就送往低一级的就绪队列。 进程调度时总是先执行高优先级队列中的进程。高优先进程调度时总是先执行高优先级队列中的进程。高优先级队列为空后，才转去处理低一级优先级队列中的进程。级队列为空后，才转去处理低一级优先级队列中的

22、进程。 同一优先级队列（除最低）的进程，按同一优先级队列（除最低）的进程，按FIFOFIFO机制调度。机制调度。最低优先级队列，按时间片轮转调度算法执行最低优先级队列，按时间片轮转调度算法执行反馈反馈FB 在反馈调度算法中，长进程也存在饿死的现象在反馈调度算法中，长进程也存在饿死的现象 当比运行进程更高优先级队列到来一个新进程时，则当比运行进程更高优先级队列到来一个新进程时，则应该处理高优先级队列的进程。有两种方案：应该处理高优先级队列的进程。有两种方案： 抢占方式：即当高优先级进程到来时，立即抢占处抢占方式：即当高优先级进程到来时，立即抢占处理进程的处理器，被抢占进程回到原来就绪队列的理进程

23、的处理器，被抢占进程回到原来就绪队列的末尾。（末尾。（没有特殊说明时，认为是抢占方式） 非抢占方式：当前进程用完规定的时间片后，再调非抢占方式：当前进程用完规定的时间片后，再调度高优先级的进程。度高优先级的进程。反馈反馈FB 对于被阻塞的进程，当阻塞取消后的处理方法：对于被阻塞的进程，当阻塞取消后的处理方法： 进入低一级的就绪队列进入低一级的就绪队列 回到原就绪队列回到原就绪队列 放入高一级的就绪队列中放入高一级的就绪队列中 进入最高级的就绪队列进入最高级的就绪队列 时间片的长短由如下四个因素决定：时间片的长短由如下四个因素决定： 系统的响应时间系统的响应时间 当进程数目一定时，时间片的长短直

24、当进程数目一定时，时间片的长短直接影响系统的响应时间接影响系统的响应时间 就绪队列中进程的数目就绪队列中进程的数目 当系统对响应时间要求一定时，当系统对响应时间要求一定时，就绪队列中进程数少则时间片长，反之亦然就绪队列中进程数少则时间片长，反之亦然 进程状态转换进程状态转换 (即进程由就绪态到运行，或反之即进程由就绪态到运行，或反之) 的时间的时间开销开销 计算机本身的处理能力计算机本身的处理能力 执行速度和可运行作业的道数执行速度和可运行作业的道数v现有现有5各进程，到达就绪队列的时间和所需的服各进程，到达就绪队列的时间和所需的服务时间如下表所示务时间如下表所示 求求 ：FCFS, RR (

25、q=1、4) , SPN, SRTN, HRRN, FB(q=1、2i )进程进程到达时间到达时间服务时间服务时间A03B26C44D65E82012345678910111213141516171819ABCDE进程进程到达时间到达时间服务时间服务时间A03B26C44D65E82012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213

26、141516171819ABCDE012345678910111213141516171819ABCDE进程进程到达时间到达时间服务时间服务时间A03B26C44D65E82012345678910111213141516171819ABCDE进程进程到达时间到达时间服务时间服务时间A03B26C44D65E82012345678910111213141516171819ABCDE进程进程到达时间到达时间服务时间服务时间A03B26C44D65E82012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012

27、345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE进程到达时间服务时间A03B26C44D65E82012345678910111213141516171819ABCDE进程进程到达时间到达时间服务时间服务时间A03B26C44D65E82012345678910111213141516171819ABCDE012345678910111213141516171819ABC

28、DE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE012345678910111213141516171819ABCDE进程进程到达时间到达时间服务时间服务时间A03B26C44D65E82012345678910111213141516171819ABCDE进程进程到达时间到达时间服务时间服务时间A03B26C44D65E82各种调度算法各有其特点，但分级轮转法和反馈各种调度算法各有其特点，但分级轮转法和反馈法较为理想法较为理想除

29、了从就绪进程中选取一合理的进程投入运行外，除了从就绪进程中选取一合理的进程投入运行外，进程调度程序还必须给该进程分配运行时间片进程调度程序还必须给该进程分配运行时间片为了保证终端用户提供服务请求之后，能及时得为了保证终端用户提供服务请求之后，能及时得到响应，一般规定的时间片在几十毫秒到几百毫到响应，一般规定的时间片在几十毫秒到几百毫秒之间不等秒之间不等调度算法分析：调度算法分析： 将就绪进程分成高和低优先级两个队列。如果进将就绪进程分成高和低优先级两个队列。如果进程运行中超过了规定的时间片就进入低优先级队程运行中超过了规定的时间片就进入低优先级队列，而列，而I/OI/O操作完成的进程，即由阻塞

30、状态进入操作完成的进程，即由阻塞状态进入高优先级就绪队列高优先级就绪队列 调度算法是调度算法是: : 首先从高优先就绪队列中选择一个首先从高优先就绪队列中选择一个进程来运行，如果在高优先级就绪队列中没有进进程来运行，如果在高优先级就绪队列中没有进程，则从低优先级就绪队列中选择一个进程运行程，则从低优先级就绪队列中选择一个进程运行 此算法此算法对于要求对于要求 I/O 量大的就绪进程有利量大的就绪进程有利 (高优先级高优先级) ，而对，而对于那些于那些计算量大的就绪进程不利计算量大的就绪进程不利 (未计算完毕就进入低优先未计算完毕就进入低优先级就绪队列级就绪队列) 由于外部设备的运行速度大大低于

31、主机的运行速度，所以为由于外部设备的运行速度大大低于主机的运行速度，所以为了保持了保持I/O通道和设备处于忙碌状态，受通道和设备处于忙碌状态，受I/O限制的进程优先限制的进程优先于受于受CPU限制的进程运行。只有当所有的受限制的进程运行。只有当所有的受I/O限制的进程限制的进程全部被阻塞，才选取某个受全部被阻塞，才选取某个受CPU限制的低优先级就绪进程在限制的低优先级就绪进程在处理机上运行处理机上运行 对交互式用户来说，对交互式用户来说，这个策略提供了良好的响应这个策略提供了良好的响应，也保持了，也保持了I/O和中央处理机之间的高度并行和中央处理机之间的高度并行 传统的UNIX调度的基本目标是

32、分时交互环境 调度算法设计成为交互用户提供好的响应时间，同时保证低优先级的后台作业不会饿死。是分时调度算法的代表 传统的UNIX调度程序在每个优先级队列中采用使用循环法的多级反馈。该系统使用1秒剥夺，也就是说，如果一个正在运行的进程在1秒内没有阻塞或完成，它将被剥夺。优先级基于进程类型和执行历史 每秒都重新计算每个进程的优先级，并进行一次新的调度决策 基本优先级的目的是把所有的进程划分成固定的优先级。这些区用于优化访问块设备 (如磁盘) 和允许操作系统迅速响应系统调用 按优先级的顺序，这些区如下 交换程序 块I/O设备控制 文件操作字符I/O设备控制用户进程当系统包含多个处理器时，在设计调度功

33、能时就当系统包含多个处理器时，在设计调度功能时就会产生一些新问题会产生一些新问题多处理器系统可以划分为以下几类多处理器系统可以划分为以下几类 松耦合、分布式多处理器、集群松耦合、分布式多处理器、集群：由一组相对自治的系：由一组相对自治的系统组成，每个处理器有自己的主存和统组成，每个处理器有自己的主存和I/OI/O通道通道 专门功能的处理器专门功能的处理器：例如：例如I/OI/O处理器。在这种情况下，处理器。在这种情况下，有一个通用的主处理器，专用处理器受主处理器的控制，有一个通用的主处理器，专用处理器受主处理器的控制，并给主处理器提供服务并给主处理器提供服务 紧耦合多处理器紧耦合多处理器：由一

34、组共享同一个主存并在操作系统：由一组共享同一个主存并在操作系统完全控制下的处理器组成完全控制下的处理器组成关注最后一类系统，特别是与调度有关的问题关注最后一类系统，特别是与调度有关的问题 粒度粒度 刻画多处理器的一种比较好的方法，是考虑系统中进程刻画多处理器的一种比较好的方法，是考虑系统中进程之间的同步粒度，或者说同步频率之间的同步粒度，或者说同步频率 可以根据粒度区分可以根据粒度区分5类并行度类并行度 独立独立：多个无关进程：多个无关进程 非常粗非常粗：在网络节点上进行分布处理，以形成一个计算：在网络节点上进行分布处理，以形成一个计算环境环境 粗粗：在多道程序环境中并发进程的多处理：在多道程

35、序环境中并发进程的多处理 中等中等：在一个应用程序中的并行处理或多任务处理：在一个应用程序中的并行处理或多任务处理(线程线程) 细细：指令流中固有的并行：指令流中固有的并行 独立并行度 进程间没有显式的同步。每个进程都代表各自独立的应用或作业。这类并行度的一个典型应用是分时系统。每个用户都执行一个特定的应用，如字处理或使用电子表格。多处理器和多道程序单处理器一样提供相同的服务。由于有多个处理器可用，因而用户的平均响应时间非常短 有可能达到这样的性能：每个用户都如同在使用个人计算机或工作站。如果任何一个文件或信息被共享，则单个系统必须连接在一个有网络支持的分布式系统中 在许多实例中，多处理器共享

36、系统比分布式系统的成本效益更合算，它允许节约使用磁盘和其他外围设备 粗粒度和非常粗粒度的并行度 是指进程之间在一个非常粗的级别上存在着同步。这种情况可以简单地处理成一组运行在多道程序单处理器上的并发进程，在多处理器上对用户软件进行很少的改动或者不进行改动就可以提供支持 一般来说，使用多处理器体系结构，对所有需要通信或同步的并发进程集合都有好处。当进程间存在非常频繁的交互时，分布式系统可以提供好的支持。但是，当交互更加频繁时，分布式系统中的网络通信开销会抵消一部分潜在的加速，在这种情况下，多处理器组织能提供最有效的支持 中等粒度的并行度 应用程序可以作为进程中的一组线程被有效地实现。在这种情况下

37、，可以由程序员显式地指定应用程序潜在的并行性。典型地，在应用程序的线程之间，需要更高程度的合作与交互，从而导致中等粒度级的同步 尽管多处理器和多道程序单处理器都支持独立、非常粗和粗粒度的并行度，并对调度功能产生少许影响或没有影响，但是在处理线程调度时，我们仍然需要重新分析调度。由于应用程序中各个线程间的交互是如此地频繁，关于线程调度的决策可能会影响整个应用的性能 细粒度的并行度 代表着比线程中的并行更加复杂的使用。尽管在高度并行的应用中已经完成了大量的工作，迄今为止，这仍然是一个特殊的、被分割的领域多处理器中的调度涉及到以下三个相关问题多处理器中的调度涉及到以下三个相关问题 把进程分配到处理器

38、把进程分配到处理器 在单个处理器上使用多道程序在单个处理器上使用多道程序 一个进程的实际分派一个进程的实际分派在讨论这三个问题时，必须记住所采用的方法通在讨论这三个问题时，必须记住所采用的方法通常取决于应用程序的粒度等级和可用的处理器的常取决于应用程序的粒度等级和可用的处理器的数目数目把进程分配到处理器把进程分配到处理器 假设多处理器结构中各个处理器在访问主存和假设多处理器结构中各个处理器在访问主存和I/O设备时没有特别优势，那么最简单的调度方设备时没有特别优势，那么最简单的调度方法是把处理器看作是一个资源池，并按照要求把法是把处理器看作是一个资源池，并按照要求把进程分配到相应的处理器。带来的

39、问题是：分配进程分配到相应的处理器。带来的问题是：分配应该是应该是静态静态的还是的还是动态动态的的 静态：静态：一个进程从被激活到完成，被永久地分配到一个进程从被激活到完成，被永久地分配到一个处理器，则需要为每个处理器维护一个专门的一个处理器，则需要为每个处理器维护一个专门的短程队列。短程队列。 其优点是调度的开销比较小，因为所有进程关于处其优点是调度的开销比较小，因为所有进程关于处理器的分配只进行一次理器的分配只进行一次 静态分配的缺点是某个处理器可能空闲，这时它的静态分配的缺点是某个处理器可能空闲，这时它的队列为空，而另一个处理器却积压了许多工作队列为空，而另一个处理器却积压了许多工作 动

40、态动态：为防止静态分配浪费：为防止静态分配浪费CPU资源的情况，需资源的情况，需要使用一个公共队列。所有进程都进入一个全局要使用一个公共队列。所有进程都进入一个全局队列，然后调度到任何一个可用的处理器中。这队列，然后调度到任何一个可用的处理器中。这样，在一个进程的生命周期中，它可以在不同的样，在一个进程的生命周期中，它可以在不同的时间在不同的处理器上执行时间在不同的处理器上执行把进程分配到处理器把进程分配到处理器处理器结构处理器结构 主从式结构主从式结构：操作系统的主要核心功能总是在某个特定的：操作系统的主要核心功能总是在某个特定的处理器上运行，其他处理器可能仅用于执行用户程序处理器上运行，其

41、他处理器可能仅用于执行用户程序 主处理器负责调度作业。当一个进程被激活时，如果从处主处理器负责调度作业。当一个进程被激活时，如果从处理器需要服务理器需要服务 (例如一次例如一次I/O调用调用) ，它必须给主处理器发，它必须给主处理器发送一个请求，然后等待服务的执行送一个请求，然后等待服务的执行 这种方法简单，由于处理器拥有对所有存储器和这种方法简单，由于处理器拥有对所有存储器和I/O资源资源的控制，因而可以简化冲突解决方案的控制，因而可以简化冲突解决方案 缺点是缺点是: 主处理器的失败导致整个系统失败主处理器的失败导致整个系统失败; 主处理器可能主处理器可能成为性能瓶颈成为性能瓶颈把进程分配到

42、处理器把进程分配到处理器处理器结构处理器结构 对等式结构对等式结构：操作系统可以在任何一个处理器中执行。：操作系统可以在任何一个处理器中执行。每个处理器从可用进程池中进行自调度。这种方法增加每个处理器从可用进程池中进行自调度。这种方法增加了操作系统的复杂性，必须确保两个处理器不会选择同了操作系统的复杂性，必须确保两个处理器不会选择同一个进程，进程也不会从队列中丢失一个进程，进程也不会从队列中丢失 也可以提供一个处理器子集专门用于内核处理，或者是也可以提供一个处理器子集专门用于内核处理，或者是基于优先级和执行历史来管理内核进程和其他进程之间基于优先级和执行历史来管理内核进程和其他进程之间的差别等

43、的差别等在单个处理器上使用多道程序在单个处理器上使用多道程序 传统的多处理器处理是粗粒度或独立同步粒度，显然单传统的多处理器处理是粗粒度或独立同步粒度，显然单个处理器能够在许多进程间切换，以达到较高的使用率个处理器能够在许多进程间切换，以达到较高的使用率和更好的性能。和更好的性能。 但是，对于运行在有许多处理器的多处理器系统中的中但是，对于运行在有许多处理器的多处理器系统中的中等粒度等粒度(线程线程)应用程序，当多个处理器可用时，要求每个应用程序，当多个处理器可用时，要求每个处理器尽可能地忙就不再那么重要了。相反，我们更加处理器尽可能地忙就不再那么重要了。相反，我们更加关注如何能为应用提供最好

44、的平均性能。关注如何能为应用提供最好的平均性能。进程分派进程分派 选择哪一个进程运行？选择哪一个进程运行？ 在多道程序单处理器上，与简单的先来先服务策略相比在多道程序单处理器上，与简单的先来先服务策略相比较，使用优先级或者基于过去的使用历史的高级调度算较，使用优先级或者基于过去的使用历史的高级调度算法可以提高性能法可以提高性能 当考虑多处理器时，这些复杂性是不必要的，不然可能当考虑多处理器时，这些复杂性是不必要的，不然可能反而达不到预期的目标，反而达不到预期的目标， 对于多处理器，相对比较简单的方法会更有效，而且开对于多处理器，相对比较简单的方法会更有效，而且开销也比较低。销也比较低。 在大多

45、数传统的多处理器系统中，进程并不是被指定到一个在大多数传统的多处理器系统中，进程并不是被指定到一个专门的处理器。不是所有处理器只有一个队列专门的处理器。不是所有处理器只有一个队列 而是有多条基于优先级的队列，并且都送进相同的处理器池而是有多条基于优先级的队列，并且都送进相同的处理器池中。在任何情况下，我们都可以把系统看作是多服务器排队中。在任何情况下，我们都可以把系统看作是多服务器排队结构结构 对各种情况进行分析，对于多处理器，调度原则的选择没有对各种情况进行分析，对于多处理器，调度原则的选择没有在单处理器中显得重要。因此，在多处理器系统中使用简单在单处理器中显得重要。因此，在多处理器系统中使

46、用简单的的FCFS (先来先服务先来先服务) 原则或者在静态化先级方案中使用原则或者在静态化先级方案中使用FCFS就足够了就足够了 在单处理器中在单处理器中，线程可以用作辅助构造程序，并，线程可以用作辅助构造程序，并在处理过程在处理过程中重叠执行中重叠执行I/O。由于在进行线程切换时的性能损失远远小。由于在进行线程切换时的性能损失远远小于进程切换的开销，因此可以用很少的代价实现这些优点于进程切换的开销，因此可以用很少的代价实现这些优点 在多处理器系统中在多处理器系统中，线程的全部能力得到了更好的展现，线，线程的全部能力得到了更好的展现，线程可以用于开发应用程序中真正的并行性。如果程可以用于开发

47、应用程序中真正的并行性。如果一个应用程一个应用程序的各个线程同时在各个独立的处理器中执行序的各个线程同时在各个独立的处理器中执行，其性能就会，其性能就会得到显著的提高。得到显著的提高。 在多处理器线程调度和处理器分配的各种方案中，比较突出在多处理器线程调度和处理器分配的各种方案中，比较突出的方法是：的方法是： 负载分配负载分配：进程不是分配到一个特定的处理器，而是维护一个就绪进程不是分配到一个特定的处理器，而是维护一个就绪进程的全局队列，每个处理器只要空闲就从队列中选择一个线程，进程的全局队列，每个处理器只要空闲就从队列中选择一个线程，负载平衡是基于一种比较永久的分配方案配工作的负载平衡是基于

48、一种比较永久的分配方案配工作的 成组调度成组调度：一组相关的线程基于一对一的原则，同时调度到一组处一组相关的线程基于一对一的原则，同时调度到一组处理器上运行理器上运行 专用处理器分配专用处理器分配：这种方法与负载分配的方法相反，它通过把线程这种方法与负载分配的方法相反，它通过把线程指定到处理器来定义隐式的调度。在程序执行过程中，每个程序被指定到处理器来定义隐式的调度。在程序执行过程中，每个程序被分配给一组处理器，处理器的数目与程序线程的数目相等。当程序分配给一组处理器，处理器的数目与程序线程的数目相等。当程序终止时，处理器返回到总的处理器池中，可供分配给另一个程序终止时，处理器返回到总的处理器

49、池中，可供分配给另一个程序 动态调度动态调度：在执行期间，进程中线程的数目可以改变：在执行期间，进程中线程的数目可以改变Windows 2000 的设计目标是在高度交互的环境中的设计目标是在高度交互的环境中或者作为服务器尽可能地响应单个用户的需求或者作为服务器尽可能地响应单个用户的需求Windows 2000 实现了剥夺式调度程序，它具有灵实现了剥夺式调度程序，它具有灵活的优先级系统，在每一级上都包括了循环调度活的优先级系统，在每一级上都包括了循环调度方法，在某些级上，优先级可以基于它们当前的方法，在某些级上，优先级可以基于它们当前的线程活动而动态变化线程活动而动态变化Windows 2000中的优先级被组织成两段中的优先级被组织成两段 (两类两类) ：实：实时和可变。每一段包括时和可变。每一段包括16种优先级。需要立即关注种优先级。需要立即关注的线程在实时类中，它包括诸如通信之类的功能和的线程在实时类中，它包括诸如通信之类的功能和实时任务实时任务Windows 2000使用一种优先级驱动的剥夺式调度程使用一种优先级驱动的剥夺式调度程序，具有实时优先级的线程优先于其他线程序，具有实时优先级的线程优先于其他线程在单处理器中，当一