第4章调度和死锁new

1、内容内容调度的类型和模型调度的类型和模型调度算法调度算法实时系统中的调度实时系统中的调度多处理机调度多处理机调度调度算法举例调度算法举例死锁的基本概念死锁的基本概念死锁的预防和避免死锁的预防和避免死锁的检测和解除死锁的检测和解除第四章第四章调度和死锁调度和死锁目的及要求目的及要求了解进程调度的类型，领会调度队列模型，领会并理解了解进程调度的类型，领会调度队列模型，领会并理解选择调度方式和算法的准则；选择调度方式和算法的准则；掌握先来先服务、短作业（进程）优先、时间片轮转和掌握先来先服务、短作业（进程）优先、时间片轮转和优先权调度算法，领会和理解高响应比优先、多级队列优先权调度算法，领会和理解高

2、响应比优先、多级队列调度和多级反馈队列调度算法；调度和多级反馈队列调度算法；了解实时系统中调度要求和调度算法；了解实时系统中调度要求和调度算法；了解多处理机系统中的进程调度算法；了解多处理机系统中的进程调度算法；领会并掌握死锁的基本概念，理解产生死锁的原因、产领会并掌握死锁的基本概念，理解产生死锁的原因、产生死锁的必要条件；生死锁的必要条件；领会和理解死锁的预防的各种方法；领会和理解死锁的预防的各种方法；领会系统的安全状态，理解并掌握掌握银行家算法；领会系统的安全状态，理解并掌握掌握银行家算法；了解和领会死锁检测的算法和死锁解除的方法。了解和领会死锁检测的算法和死锁解除的方法。第四章第四章调度

3、和死锁调度和死锁重点重点先来先服务、短作业（进程）优先、时间片轮转调度算先来先服务、短作业（进程）优先、时间片轮转调度算法；法；死锁的基本概念，产生死锁的必要条件；死锁的基本概念，产生死锁的必要条件；预防死锁的方法；预防死锁的方法；银行家算法。银行家算法。难点难点调度队列模型；调度队列模型；银行家算法；银行家算法；死锁的检测算法。死锁的检测算法。 第四章第四章调度和死锁调度和死锁4.1.1 4.1.1 调度类型调度类型4.1.2 4.1.2 调度队列模型调度队列模型4.1.3 4.1.3 选择调度方式和算法的若干准则选择调度方式和算法的若干准则4.14.1 调度的类型与模型调度的类型与模型高级

4、调度高级调度(High Level Scheduling)(High Level Scheduling)又称作业调度、宏观调度、长程调度又称作业调度、宏观调度、长程调度(Long-Term (Long-Term Scheduling)Scheduling)或接纳调度或接纳调度(Admission Scheduling)(Admission Scheduling)。作业调度用于决定把外存上处于作业后备队列上的哪些作业调度用于决定把外存上处于作业后备队列上的哪些作业调入内存，并为它们创建进程、分配必要的资源，然后再作业调入内存，并为它们创建进程、分配必要的资源，然后再将新创建的进程排在就绪队列上，

5、准备执行。在批处理系统中将新创建的进程排在就绪队列上，准备执行。在批处理系统中，作业是先驻留在外存上的，因此需要有作业调度。然而在分，作业是先驻留在外存上的，因此需要有作业调度。然而在分时系统中，通过键盘输入的命令和数据直接进入内存，无需作时系统中，通过键盘输入的命令和数据直接进入内存，无需作业调度。业调度。接纳多少个作业（多道程序度）接纳多少个作业（多道程序度）接纳哪些作业接纳哪些作业4.1.1 4.1.1 调度类型调度类型s低级调度低级调度(Low Level Scheduling)(Low Level Scheduling) 又称进程调度、微观调度或短程调度又称进程调度、微观调度或短程调

6、度(Short-Term (Short-Term Scheduling)Scheduling)。进程调度决定就绪队列中哪个进程将获得处理机，然后进程调度决定就绪队列中哪个进程将获得处理机，然后由分派程序执行把处理机分配给该进程的操作。进程调度是最由分派程序执行把处理机分配给该进程的操作。进程调度是最基本的调度，任何操作系统都有进程调度。基本的调度，任何操作系统都有进程调度。4.1.1 4.1.1 调度类型调度类型（ 非抢占方式非抢占方式(Non-Preemptive Mode)(Non-Preemptive Mode) 采用这种调度方式时，一旦把处理机分配给某进程后采用这种调度方式时，一旦把处

7、理机分配给某进程后，便让进程一直执行，直到该进程完成或发生某事件而被，便让进程一直执行，直到该进程完成或发生某事件而被阻塞时，才把处理机分配给其它进程，决不允许某进程抢阻塞时，才把处理机分配给其它进程，决不允许某进程抢占已经分配出去的处理机。占已经分配出去的处理机。 这种调度方式的优点是实现简单、系统开销小，适用这种调度方式的优点是实现简单、系统开销小，适用于大多数批处理系统环境。缺点是难以满足紧急任务的要于大多数批处理系统环境。缺点是难以满足紧急任务的要求，不适用于实时、分时系统要求。求，不适用于实时、分时系统要求。4.1.1 4.1.1 调度类型调度类型（ 抢占方式抢占方式(Preempt

8、ive Mode)(Preemptive Mode)这种调度方式，允许进程调度程序根据某个原则，去停止某个正这种调度方式，允许进程调度程序根据某个原则，去停止某个正在执行的进程，将已分配给进程的处理机，重新分配给另一个进程。在执行的进程，将已分配给进程的处理机，重新分配给另一个进程。抢占的原则有：抢占的原则有：l时间片原则。各进程按时间片运行，当一个时间片用完后，便时间片原则。各进程按时间片运行，当一个时间片用完后，便停止进程的执行而重新进行调度。这个原则适用于分时系统、大停止进程的执行而重新进行调度。这个原则适用于分时系统、大多数实时系统以及要求较高的批处理系统。多数实时系统以及要求较高的批

9、处理系统。l优先权原则。通常是对一些重要的和紧急的进程赋予较高的优优先权原则。通常是对一些重要的和紧急的进程赋予较高的优先权。当这种进程进入就绪队列时，如果其优先权比正在执行的先权。当这种进程进入就绪队列时，如果其优先权比正在执行的进程优先权高，便停止正在执行的进程，将处理机分配给优先权进程优先权高，便停止正在执行的进程，将处理机分配给优先权高的进程，使之执行。高的进程，使之执行。l短作业（进程）优先原则。当新到达的作业（进程）比正在执短作业（进程）优先原则。当新到达的作业（进程）比正在执行的作业（进程）明显地短时，将剥夺长作业（进程）的执行，行的作业（进程）明显地短时，将剥夺长作业（进程）的

10、执行，将处理机分配给短作业（进程），使之优先执行。将处理机分配给短作业（进程），使之优先执行。4.1.1 4.1.1 调度类型调度类型s中级调度中级调度(Intermediate Level Scheduling)(Intermediate Level Scheduling) 又称中程调度又称中程调度 (Medium-Term Scheduling)(Medium-Term Scheduling)。引入中级调度的目的是为了提高主存利用率和系统吞吐引入中级调度的目的是为了提高主存利用率和系统吞吐量。由于在进程并发执行过程中，为了充分发挥内存的效能，量。由于在进程并发执行过程中，为了充分发挥内存的

11、效能，需将那些暂时不能运行的进程从内存调到外存去等待（就绪挂需将那些暂时不能运行的进程从内存调到外存去等待（就绪挂起），而当内存空闲时，进行中级调度，将那些在外存的等待起），而当内存空闲时，进行中级调度，将那些在外存的等待的进程调入内存，插入就绪队列（激活、解挂）的进程调入内存，插入就绪队列（激活、解挂） ，等待进程，等待进程调度。调度。中级调度就是存储管理中的对换，采用虚拟存储技术的中级调度就是存储管理中的对换，采用虚拟存储技术的分时系统往往设立中级调度。分时系统往往设立中级调度。4.1.1 4.1.1 调度类型调度类型s处理机三级调度：处理机三级调度：4.1.1 4.1.1 调度类型调度类

12、型 外存外存作 业作 业后 备后 备状态状态作 业作 业提 交提 交状态状态就绪就绪态态阻塞阻塞态态主存主存进程调度进程调度运行运行态态就绪就绪态态阻塞阻塞态态中级调度中级调度作作业业调调度度作 业作 业完 成完 成状态状态外存外存4.1.1 4.1.1 调度类型调度类型AdmitRunningReadySuspendExitReadyBlockedDispatchTimeoutEventWaitEventOccursReleaseBlockedSuspendSuspendNewEventOccursActivateSuspendActivateAdmitSuspend宏观调度微观调度中级调度

13、一一仅有进程调度的调度队列模型仅有进程调度的调度队列模型在分时系统中通常仅设置了进程调度。此时系统有一个在分时系统中通常仅设置了进程调度。此时系统有一个就绪队列，每个进程运行一个时间片，进程运行一个时间片后就绪队列，每个进程运行一个时间片，进程运行一个时间片后如未完成，则被放在就绪队列末尾。如进程运行中因等待某事如未完成，则被放在就绪队列末尾。如进程运行中因等待某事件（例如申请件（例如申请I/OI/O而等待而等待I/OI/O完成），则需排入阻塞队列，系统完成），则需排入阻塞队列，系统因阻塞的原因不同可设几个阻塞队列。因阻塞的原因不同可设几个阻塞队列。4.1.2 4.1.2 调度队列模型调度队列

14、模型事事件件出出现现CPUCPU交互用户交互用户时间片完时间片完进程完成进程完成 就绪队列就绪队列等待事件等待事件 阻塞队列阻塞队列进程调度进程调度s具有高级调度和低级调度的调度队列模型具有高级调度和低级调度的调度队列模型在多道批处理系统中，一般处理机管理设置作业和进程在多道批处理系统中，一般处理机管理设置作业和进程两级调度。它比第一个模型增加了高级调度。模型增加了在磁两级调度。它比第一个模型增加了高级调度。模型增加了在磁盘的作业后备队列，作业调度的任务是从作业后备队列中选一盘的作业后备队列，作业调度的任务是从作业后备队列中选一个作业为它创建至少一个进程，并分配资源，将它排入内存进个作业为它创

15、建至少一个进程，并分配资源，将它排入内存进程就绪队列末尾。程就绪队列末尾。s4.1.2 4.1.2 调度队列模型调度队列模型CPUCPU时间片完时间片完进程完成进程完成 就绪队列就绪队列等待事件等待事件1 1 阻塞队列阻塞队列1 1作业调度作业调度后备作业队列后备作业队列等待事件等待事件n n 阻塞队列阻塞队列n n进程调度进程调度事件出现事件出现1 1事件出现事件出现n ns同时具有三级调度的调度队列模型同时具有三级调度的调度队列模型 s在通用系统的多模式在通用系统的多模式OSOS中，一般采用具有三级调度的调中，一般采用具有三级调度的调s度队列模型，由于多模式度队列模型，由于多模式OSOS同

16、时支持批处理、分时和实同时支持批处理、分时和实时处理时处理s，所以它必须具有以上模型，所以它必须具有以上模型4.1.2 4.1.2 调度队列模型调度队列模型中 级中 级调 度调 度调出调出CPUCPU交互型作业交互型作业时间片完时间片完等待事件等待事件完成完成 就绪队列就绪队列就绪，挂起队列就绪，挂起队列阻塞，挂起队列阻塞，挂起队列 阻塞队列阻塞队列事事件件出出现现作业调度作业调度后备作业队列后备作业队列批批量量作作业业中 级中 级调 度调 度调入调入中 级中 级调 度调 度调出调出事 件事 件出现出现一一面向用户的准则面向用户的准则 s为满足用户需求应遵循的一些准则：为满足用户需求应遵循的一

17、些准则：1.1. 周转时间短周转时间短（批处理系统批处理系统） 周转时间，是指从作业提交给系统开始，到作业完成为止的这段周转时间，是指从作业提交给系统开始，到作业完成为止的这段时间间隔（称为作业周转时间）它包括：时间间隔（称为作业周转时间）它包括：n作业在外存后备队列上等待（作业）调度的时间；作业在外存后备队列上等待（作业）调度的时间；n进程在就绪队列上等待进程调度的时间；进程在就绪队列上等待进程调度的时间；n进程在进程在CPUCPU上执行的时间；上执行的时间；n等待等待I/OI/O操作完成的时间。操作完成的时间。其中后三项在一个作业的处理过程中，可能发生多次。其中后三项在一个作业的处理过程中

18、，可能发生多次。4.1.34.1.3 选择调度方式和算法的若干准则选择调度方式和算法的若干准则提交作业后备队列就绪队列CPU作业调度进程调度周转时间等待I/O完成4.1.3 4.1.3 选择调度方式和算法的若干准则选择调度方式和算法的若干准则l对每个用户而言，都希望自己作业的周转时间最短。但作为计对每个用户而言，都希望自己作业的周转时间最短。但作为计算机系统的管理者，总是希望能使平均周转时间最短；这不仅会有算机系统的管理者，总是希望能使平均周转时间最短；这不仅会有效地提高资源利用率，而且还可使大多数用户感到满意效地提高资源利用率，而且还可使大多数用户感到满意l平均周转时间可描述为：平均周转时间

19、可描述为：l作业的周转时间作业的周转时间TiTi与系统为它提供的实际服务时间与系统为它提供的实际服务时间TsiTsi之比，之比，即即W=T/TsW=T/Ts称为带权周转时间称为带权周转时间, ,而平均带权周转时间可表示为：而平均带权周转时间可表示为：11niiTnT11nisiiTTnWl响应时间快响应时间快（分时系统分时系统）l响应时间常用于评价分时操作系统的性能，是选择分时系统中响应时间常用于评价分时操作系统的性能，是选择分时系统中进程调度算法的重要准则之一。进程调度算法的重要准则之一。l响应时间是从用户通过键盘提交一个请求开始，直至系统首次响应时间是从用户通过键盘提交一个请求开始，直至系

20、统首次产生响应为止的时间，或说直到在屛幕上显示出结果为止的一段时产生响应为止的时间，或说直到在屛幕上显示出结果为止的一段时间间隔。它包括：间间隔。它包括：n从键盘输入的请求信息传送到处理机的时间；从键盘输入的请求信息传送到处理机的时间；n处理机对请求信息进行处理的时间；处理机对请求信息进行处理的时间；n将所形成的响应回送到终端显示器的时间。将所形成的响应回送到终端显示器的时间。4.1.34.1.3 选择调度方式和算法的若干准则选择调度方式和算法的若干准则键入请求显示器显示请求响应响应时间CPU处理请求l截止时间的保证截止时间的保证（实时系统实时系统）l它是用来评价实时系统性能的重要指标，因而是

21、选择实时调度它是用来评价实时系统性能的重要指标，因而是选择实时调度算法的重要准则。算法的重要准则。l所谓截止时间，是指某任务必须开始执行的最迟时间，或必须所谓截止时间，是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。完成的最迟时间。l优先权准则优先权准则（批处理、分时和实时系统批处理、分时和实时系统）l在选择批处理、分时和实时系统的调度算法时，都可引用在选择批处理、分时和实时系统的调度算法时，都可引用优先权优先权l准则，以便让那些紧急的作业（或事件），得到及时的处理。在准则，以便让那些紧急的作业（或事件），得到及时的处理。在要求要求l较严格的场合，往往还需选择抢占调度方式，才能保证紧急

22、作业较严格的场合，往往还需选择抢占调度方式，才能保证紧急作业得到得到l及时的处理。及时的处理。4.1.34.1.3 选择调度方式和算法的若干准则选择调度方式和算法的若干准则s面向系统的准则面向系统的准则1.1.系统吞吐量高系统吞吐量高 这是用来评价批处理系统的重要指标。系统吞吐量是单位时间内这是用来评价批处理系统的重要指标。系统吞吐量是单位时间内完成的作业数，它与批处理作业的平均长度具有密切关系。完成的作业数，它与批处理作业的平均长度具有密切关系。l处理机利用率好处理机利用率好l对于大中型多用户系统，由于对于大中型多用户系统，由于CPUCPU价格十分昂贵，所以处理价格十分昂贵，所以处理机利机利

23、l用率成为衡量大、中型系统性能的十分重要指标，但对单用户微用率成为衡量大、中型系统性能的十分重要指标，但对单用户微机或机或l某些实时系统，该准则就不那么重要。某些实时系统，该准则就不那么重要。（各类资源的平衡利用各类资源的平衡利用（在大中型系统中，有效地利用各类资源（包括在大中型系统中，有效地利用各类资源（包括CPUCPU、外存、外存、I/OI/O设设（备等）也是一个重要指标，对于微型机和某些实时系统，该准则备等）也是一个重要指标，对于微型机和某些实时系统，该准则也不也不（重要。重要。4.1.34.1.3 选择调度方式和算法的若干准则选择调度方式和算法的若干准则4.2.1 4.2.1 先进先服

24、务调度算法先进先服务调度算法 4.2.2 4.2.2 短作业（进程）优先调度算法短作业（进程）优先调度算法 4.2.3 4.2.3 时间片轮转调度算法时间片轮转调度算法 4.2.4 4.2.4 优先权调度算法优先权调度算法 4.2.5 4.2.5 高响应比优先调度算法高响应比优先调度算法 4.2.6 4.2.6 多级队列调度算法多级队列调度算法 4.2.7 4.2.7 多级反馈队列调度算法多级反馈队列调度算法4.2 4.2 调度算法调度算法一一调度算法调度算法先进先服务先进先服务FCFSFCFS( (First-Come-First-Served)First-Come-First-Served

25、)调度算法是调度算法是一种最简单的调度算法。一种最简单的调度算法。当在作业调度中采用该算法时，每次调度是从后备作业队当在作业调度中采用该算法时，每次调度是从后备作业队列中，选择一个或多个最先进入该队列的作业，将它们调入内列中，选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放人就绪队列。存，为它们分配资源、创建进程，然后放人就绪队列。在进程调度中，采用在进程调度中，采用FCFSFCFS调度算法时，则每次调度是从就调度算法时，则每次调度是从就绪队列中，选择一个最先进入该队列的进程，把处理机分配给绪队列中，选择一个最先进入该队列的进程，把处理机分配给它，使之投入运

26、行。该进程一直运行到完成或发生某事件而阻它，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后，才放弃处理机。塞后，才放弃处理机。该算法比较有利于长作业（进程），不利于短作业（进程）。该算法比较有利于长作业（进程），不利于短作业（进程）。4.2.1 4.2.1 先进先服务调度算法先进先服务调度算法 4.2.1 4.2.1 先进先服务调度算法先进先服务调度算法 s实例实例据此可知：据此可知： FCFSFCFS调度算法有利于调度算法有利于 CPUCPU繁忙型的作业（进程）繁忙型的作业（进程） ，而不利，而不利于于I IO O繁忙型的作业（进程）。繁忙型的作业（进程）。 lCPUCPU繁忙型作业

27、，是指该类作业需要大量的繁忙型作业，是指该类作业需要大量的 CPUCPU时间进行计算，而很时间进行计算，而很少请求少请求 I I（通常的科学计算便属于（通常的科学计算便属于CPUCPU繁忙型作业繁忙型作业) )。lI IO O繁忙型作业，是指繁忙型作业，是指CPUCPU进行处理时，又需频繁地请求进行处理时，又需频繁地请求I IO O，而每，而每次次I IO O的操作时间却又很短。目前的大多数的事务处理，都属于的操作时间却又很短。目前的大多数的事务处理，都属于I/OI/O繁忙繁忙型作业。型作业。先进先出算法比较简单，但很少作为一个独立的调度算法被使用，一般先进先出算法比较简单，但很少作为一个独立

28、的调度算法被使用，一般总是作为其他算法的一种辅助手段，例如在优先级调度算法中，对拥有相同总是作为其他算法的一种辅助手段，例如在优先级调度算法中，对拥有相同的的优先级的进程进行调度时，可采用先进先出算法。优先级的进程进行调度时，可采用先进先出算法。短作业（进程）优先调度算法短作业（进程）优先调度算法SJFSJF（Shortest Job FirstShortest Job First）/ SPF(Shortest Process First/ SPF(Shortest Process First）是对短作业或短进程优先）是对短作业或短进程优先调度的算法。调度的算法。SJFSJF是从后备作业中选择

29、一个或多个估计运行时间最短的是从后备作业中选择一个或多个估计运行时间最短的作业，将它们调入内存运行。作业，将它们调入内存运行。SPFSPF是从就绪队列中选出一个估计运行时间最短的进程，是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并直到完成，或有事件发生将处理机分配给它，使它立即执行并直到完成，或有事件发生而被阻塞放弃处理机，而重新调度。而被阻塞放弃处理机，而重新调度。4.2.2 4.2.2 短作业（进程）优先调度算法短作业（进程）优先调度算法 4.2.2 4.2.2 短作业（进程）优先调度算法短作业（进程）优先调度算法 优点：优点：l比比FCFSFCFS改善平均

30、周转时间和平均带权周转时间，缩短作业的等改善平均周转时间和平均带权周转时间，缩短作业的等待时间；待时间；l提高系统的吞吐量；提高系统的吞吐量；缺点：缺点：l对长作业非常不利，可能长时间得不到执行；对长作业非常不利，可能长时间得不到执行；l未能依据作业的紧迫程度来划分执行的优先级；未能依据作业的紧迫程度来划分执行的优先级；l难以准确估计作业（进程）的执行时间，从而影响调度性能。难以准确估计作业（进程）的执行时间，从而影响调度性能。4.2.2 4.2.2 短作业（进程）优先调度算法短作业（进程）优先调度算法 一一基本原理基本原理时间片轮转时间片轮转Round-RobinRound-Robin（RR

31、RR）调度算法将系统中所有的调度算法将系统中所有的就绪进程按照就绪进程按照FCFSFCFS原则，排成一个队列。原则，排成一个队列。每次调度时将每次调度时将CPUCPU分派给队首进程，让其执行一个时间片分派给队首进程，让其执行一个时间片。时间片的长度从几个。时间片的长度从几个msms到几百到几百msms。在一个时间片结束时，发生时钟中断。调度程序据此暂停在一个时间片结束时，发生时钟中断。调度程序据此暂停当前进程的执行，将其送到就绪队列的末尾，等待分配下一时当前进程的执行，将其送到就绪队列的末尾，等待分配下一时间片再执行。间片再执行。然后把处理机分配给就绪队列中新的队首进程，同时也让然后把处理机分

32、配给就绪队列中新的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程，它执行一个时间片。这样就可以保证就绪队列中的所有进程，在一给定的时间内，均能获得一时间片处理机执行时间。在一给定的时间内，均能获得一时间片处理机执行时间。 在在RRRR算法中，时间片的大小对系统性能有很大的影响。算法中，时间片的大小对系统性能有很大的影响。4.2.3 4.2.3 时间片轮转调度算法时间片轮转调度算法 s时间片大小的确定时间片大小的确定1.1.时间片长度变化的影响时间片长度变化的影响l过长过长 退化为退化为FCFSFCFS算法，进程在一个时间片内都执行完，响算法，进程在一个时间片内都执行完，

33、响应时间长。应时间长。l过短过短 用户的一次请求需要多个时间片才能处理完，进程切用户的一次请求需要多个时间片才能处理完，进程切换次数增加，系统开销增大，响应时间长。换次数增加，系统开销增大，响应时间长。2.2.考虑因素考虑因素l对响应时间的要求对响应时间的要求T(T(响应时间响应时间)=N()=N(进程数目进程数目) )* *q(q(时间片时间片) )l就绪进程的数目就绪进程的数目数目越多，时间片越小（当响应时间一定时）数目越多，时间片越小（当响应时间一定时）l系统的处理能力系统的处理能力应当使用户输入的常用命令通常在一个时间片内能处理完，否应当使用户输入的常用命令通常在一个时间片内能处理完，

34、否则使响应时间，平均周转时间和平均带权周转时间延长。则使响应时间，平均周转时间和平均带权周转时间延长。4.2.3 4.2.3 时间片轮转调度算法时间片轮转调度算法 s优先权优先权(Priority(Priority) )调度算法的基本思想是系统为每个进调度算法的基本思想是系统为每个进程程s设置一个优先数（对应一个优先级），把所有的就绪进程设置一个优先数（对应一个优先级），把所有的就绪进程按优按优s先级从高到低排序，调度时从就绪队列中选择优先级最高先级从高到低排序，调度时从就绪队列中选择优先级最高的进的进s程投入运行。程投入运行。 一一优先权调度算法的类型优先权调度算法的类型1.1.非抢占式优先

35、权算法非抢占式优先权算法仅当占用仅当占用CPUCPU的进程运行结束或因某种原因不能继续运的进程运行结束或因某种原因不能继续运行时，系统才进行重新调度。行时，系统才进行重新调度。 进程切换次数少，系统开销小，但可能导致优先级低进程切换次数少，系统开销小，但可能导致优先级低的进程长期抢占不到的进程长期抢占不到CPUCPU。主要用于批处理、实时性不高的实时系统。主要用于批处理、实时性不高的实时系统。4.2.4 4.2.4 优先权调度算法优先权调度算法l抢占式优先权算法抢占式优先权算法当系统中有另一优先级更高的进程变成就绪状态时，当系统中有另一优先级更高的进程变成就绪状态时，系统应立即剥夺现运行进程占

36、用系统应立即剥夺现运行进程占用CPUCPU的权力，使该优先级更的权力，使该优先级更高的进程投入运行。高的进程投入运行。 系统能及时处理紧急事件，但系统开销较大。系统能及时处理紧急事件，但系统开销较大。主要用于实时性高的实时系统、性能高的批处理以及主要用于实时性高的实时系统、性能高的批处理以及分时系统。分时系统。4.2.4 4.2.4 优先权调度算法优先权调度算法s优先权的类型优先权的类型1.1.静态优先权静态优先权静态优先权是在创建进程时确定的，且规定它在进程静态优先权是在创建进程时确定的，且规定它在进程的整个运行期间保持不变。一般，优先权是利用某一范围的整个运行期间保持不变。一般，优先权是利

37、用某一范围内的一个整数来表示。例如，内的一个整数来表示。例如，0 07 7，或，或0 0255255中的某一整中的某一整数，又称该整数为优先数。只是具体用法各异：有的系统数，又称该整数为优先数。只是具体用法各异：有的系统用用“0”0”表示优先权最高，数值愈大其优先权愈低；而有的表示优先权最高，数值愈大其优先权愈低；而有的系统恰恰相反。系统恰恰相反。4.2.4 4.2.4 优先权调度算法优先权调度算法确定进程优先权的依据有：确定进程优先权的依据有：（1 1）进程类型。通常，系统进程（如接收进程、对换进）进程类型。通常，系统进程（如接收进程、对换进程、磁盘程、磁盘I/OI/O进程）的优先权高于一般

38、用户进程的优先权进程）的优先权高于一般用户进程的优先权。（2 2）进程对资源的需求。如进程的估计执行时间及内存）进程对资源的需求。如进程的估计执行时间及内存需要量少的进程，应赋予较高的优先权。需要量少的进程，应赋予较高的优先权。（3 3）根据用户要求。这是由用户进程的紧迫程度及用户）根据用户要求。这是由用户进程的紧迫程度及用户所付费用的多少来确定进程的优先权。所付费用的多少来确定进程的优先权。静态优先权法简单易行、系统开销小，但不够精确，很可静态优先权法简单易行、系统开销小，但不够精确，很可能出现优先权低的作业（进程），长期没有被调度的情况，因能出现优先权低的作业（进程），长期没有被调度的情况

39、，因此，仅在要求不太高的系统中，才使用静态优先权。此，仅在要求不太高的系统中，才使用静态优先权。4.2.4 4.2.4 优先权调度算法优先权调度算法s动态优先权动态优先权动态优先权是指在创建进程时所赋予的优先权，可以随动态优先权是指在创建进程时所赋予的优先权，可以随进程的推进而改变，以便获得更好的调度性能。进程的推进而改变，以便获得更好的调度性能。l在就绪队列中，等待时间延长则优先级提高，从而使优先级较低在就绪队列中，等待时间延长则优先级提高，从而使优先级较低的进程在等待足够的时间后，其优先级提高到可被调度执行；的进程在等待足够的时间后，其优先级提高到可被调度执行；l进程每执行一个时间片，就降

40、低其优先级，从而一个进程持续执进程每执行一个时间片，就降低其优先级，从而一个进程持续执行时，其优先级降低到出让行时，其优先级降低到出让CPUCPU。4.2.4 4.2.4 优先权调度算法优先权调度算法4.2.5 4.2.5 高响应比优先调度算法高响应比优先调度算法 s在批处理系统中，用以作业调度的短作业优先算法是一个在批处理系统中，用以作业调度的短作业优先算法是一个s比较好的算法。其主要缺点是比较好的算法。其主要缺点是长长作业的运行得不到保证。作业的运行得不到保证。如果我如果我s们能为每个作业引入前面所述的动态优先权机制，并使之们能为每个作业引入前面所述的动态优先权机制，并使之以速率以速率sa

41、 a增加，则长作业在等待一定的时间后，必然有机会分配到增加，则长作业在等待一定的时间后，必然有机会分配到处理处理s机，即机，即高响应比优先高响应比优先 Highest Response Ratio Next Highest Response Ratio Next s(HRRN)(HRRN)( (作业作业) )调度算法，调度算法，该优先权的变化可描述为：该优先权的变化可描述为：s由于等待时间加上要求服务时间，就是系统对该作业的响由于等待时间加上要求服务时间，就是系统对该作业的响s应时间，故该优先权又相当于响应比应时间，故该优先权又相当于响应比RpRp。据此，又可表示。据此，又可表示为为: :HR

42、RNHRRN算法实际上是算法实际上是FCFSFCFS算法和算法和STFSTF算法的折衷算法的折衷。4.2.5 4.2.5 高响应比优先调度算法高响应比优先调度算法 作业号ABCDE平均到达时间01234运行时间43524完成时间4 7 12 14 18 周转时间461011149FCFS带权周转时间1225.53.52.8完成时间4 9 186 13周转时间4816398SJF带权周转时间22.673.21.52.252.1完成时间1512189 17周转时4RR带权周转时间3.753.673.233.253.37完成时间4 7 149 18周转时间46126148.

43、4HRRN带权周转时间122.433.52.384.2.5 4.2.5 高响应比优先调度算法高响应比优先调度算法 高响应比优先高响应比优先( (HRRN)(HRRN)(作业作业) )调度算法计算：调度算法计算： T=0T=0：只有作业只有作业A A已到达，调度作业已到达，调度作业A A运行运行。 T=4T=4：作业作业A A完成，作业完成，作业B B、C C、D D、E E已到达，计算作业已到达，计算作业B B、C C、D D、E E响应比响应比R RP P分别为：分别为： 1+3/3 1+3/3、1+2/51+2/5、1+1/21+1/2、1+0/41+0/4，作业作业B B响应比最大调度运

44、行。响应比最大调度运行。 T=7T=7：作业作业B B完成，作业完成，作业C C、D D、E E已到达，计算作业已到达，计算作业C C、D D、E E响响应比应比R RP P分别为：分别为： 1+5/5 1+5/5、1+4/21+4/2、1+3/41+3/4，作业，作业D D响应比最响应比最大调度运行。大调度运行。 T=9T=9：作业作业D D完成，作业完成，作业C C、E E已到达，计算作业已到达，计算作业C C、E E响应比响应比R RP P分别为：分别为： 1+7/5 1+7/5、1+5/41+5/4，作业，作业C C响应比最大调度运行。响应比最大调度运行。 T=14T=14：作业作业C

45、 C完成，只有作业完成，只有作业E E未完成，调度作业未完成，调度作业E E运行运行。 4.2.6 4.2.6 多级队列调度算法多级队列调度算法 多队列调度是根据作业的性质和类型的不同，将就绪队列再分为若干多队列调度是根据作业的性质和类型的不同，将就绪队列再分为若干个子队列，所有的作业（或进程）按其性质排入相应的队列中，而不同的就个子队列，所有的作业（或进程）按其性质排入相应的队列中，而不同的就绪队列采用不同的调度算法。绪队列采用不同的调度算法。例如前后台系统可以建立两个就绪队列，批处理作业所建立进程进入例如前后台系统可以建立两个就绪队列，批处理作业所建立进程进入后台就绪队列；交互型作业所建立

46、的进程进入前台就绪队列。前台采用时间后台就绪队列；交互型作业所建立的进程进入前台就绪队列。前台采用时间片轮转算法，进程按片轮转算法，进程按FCFSFCFS等策略排序，后台采用优先权高优先的调度算法或等策略排序，后台采用优先权高优先的调度算法或者短作业优先的调度算法。者短作业优先的调度算法。对多级就绪队列调度策略有两种，一种是各就绪队列按进程性质赋予对多级就绪队列调度策略有两种，一种是各就绪队列按进程性质赋予不同的优先权，优先权高的就绪队列的进程优先被调度，例如上例中前台就不同的优先权，优先权高的就绪队列的进程优先被调度，例如上例中前台就绪队列的优先权比后台就绪队列的优先权高，所以前台队列中的进

47、程优先被绪队列的优先权比后台就绪队列的优先权高，所以前台队列中的进程优先被调度。而只有当优先权高的就绪队列空时，方才调度优先权其次的就绪队列调度。而只有当优先权高的就绪队列空时，方才调度优先权其次的就绪队列进程，在上例中只有前台队列空时，才调度后台就绪队列。这样，只有较高进程，在上例中只有前台队列空时，才调度后台就绪队列。这样，只有较高优先权的就绪队列都空时才调度最低优先权就绪队列的进程。优先权的就绪队列都空时才调度最低优先权就绪队列的进程。 另一种调度就绪队列的方式是为每个队列分配一定的占用另一种调度就绪队列的方式是为每个队列分配一定的占用CPUCPU时间的比例时间的比例。上例中为前台队列分

48、配。上例中为前台队列分配8080的的CPUCPU时间，给后台队列分配时间，给后台队列分配2020的的CPUCPU时间。时间。4.2.7 4.2.7 多级反馈队列调度算法多级反馈队列调度算法 前面介绍的各种用作进程调度的算法，都有在一定的局限前面介绍的各种用作进程调度的算法，都有在一定的局限性，如短进程优先算法仅照顾了短进程而怠慢了长进程。况且对性，如短进程优先算法仅照顾了短进程而怠慢了长进程。况且对进程运行的长短，往往难以正确估计，所以短进程优先的调度算进程运行的长短，往往难以正确估计，所以短进程优先的调度算法无法正确使用。法无法正确使用。而多级反馈而多级反馈( (FeedbackFeedba

49、ck) )队列调度算法，则不必事先知道各队列调度算法，则不必事先知道各种进程所需的执行时间，仍能基本满足短进程优先和种进程所需的执行时间，仍能基本满足短进程优先和I/OI/O频繁的频繁的进程优先的需要，因而是目前公认的较好的一种进程调度算法。进程优先的需要，因而是目前公认的较好的一种进程调度算法。在在UNIXUNIX系统、系统、WindowsNTWindowsNT、OS/2OS/2中都采用了类似的调度算法中都采用了类似的调度算法4.2.7 4.2.7 多级反馈队列调度算法多级反馈队列调度算法 一一调度算法调度算法1.1.设置多个就绪队列，分别赋予不同的优先级，如逐级降低，队列设置多个就绪队列，

50、分别赋予不同的优先级，如逐级降低，队列1 1的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则的优先级最高。每个队列执行时间片的长度也不同，规定优先级越低则时间片越长，如逐级加倍。时间片越长，如逐级加倍。l新进程进入内存后，先投入队列新进程进入内存后，先投入队列1 1的末尾，按的末尾，按FCFSFCFS算法调度；若按算法调度；若按队列队列1 1一个时间片未能执行完，则降低投入到队列一个时间片未能执行完，则降低投入到队列2 2的末尾，同样按的末尾，同样按FCFSFCFS算法调度；如此下去，降低到最后的队列，则按算法调度；如此下去，降低到最后的队列，则按“时间片轮转时间片轮转”算法调算

51、法调度直到完成。度直到完成。l仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执仅当较高优先级的队列为空，才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进行。如果进程执行时有新进程进入较高优先级的队列，则抢先执行新进程，并把被抢先的进程投入原队列的末尾。程，并把被抢先的进程投入原队列的末尾。4.2.7 4.2.7 多级反馈队列调度算法多级反馈队列调度算法 就绪队列就绪队列1 时间片时间片S1时间片完时间片完时间片完时间片完就绪队列就绪队列2 时间片时间片S2S1运行运行运行运行运行运行就绪队列就绪队列n 时间片时间片SnSn-1完成完成完成

52、完成完成完成时间片完时间片完阻塞队列阻塞队列i阻塞阻塞阻塞阻塞阻塞阻塞事事件件发发生生4.3 4.3 实时系统中的调度实时系统中的调度 实时系统是指那些时间因素非常关键的系统。通实时系统是指那些时间因素非常关键的系统。通常常可分为硬实时系统和软实时系统。可分为硬实时系统和软实时系统。前者是指系统必须满足时间的约束。前者是指系统必须满足时间的约束。后者则意味着偶尔超过时间限制也是可以容忍的后者则意味着偶尔超过时间限制也是可以容忍的。 4.3.1 4.3.1 对实时系统的要求对实时系统的要求4.3.2 4.3.2 实时调度算法实时调度算法4.3.1 4.3.1 对实时系统的要求对实时系统的要求提供

53、必要的调度信息提供必要的调度信息如，就绪时间、开始或完成截止时间、处理时间、资源要如，就绪时间、开始或完成截止时间、处理时间、资源要求、绝对或相对优先级（硬实时或软实时）。求、绝对或相对优先级（硬实时或软实时）。调度方式调度方式采用抢先式调度。采用抢先式调度。s快速中断响应快速中断响应在中断处理时（硬件）关中断的时间尽量短。在中断处理时（硬件）关中断的时间尽量短。s快速上下文切换快速上下文切换相应地采用较小的调度单位（如线程）。相应地采用较小的调度单位（如线程）。4.3.2 4.3.2 实时调度算法实时调度算法时间片轮转调度算法时间片轮转调度算法非抢占优先级调度算法非抢占优先级调度算法基于时钟

54、中断抢占的优先级调度算法基于时钟中断抢占的优先级调度算法立即抢占的优先级调度算法立即抢占的优先级调度算法4.4 4.4 多处理机调度多处理机调度 4.4.1 4.4.1 与单处理机调度的区别与单处理机调度的区别4.4.2 4.4.2 对称式多处理系统对称式多处理系统(SMP)(SMP)4.4.3 4.4.3 非对称式多处理系统非对称式多处理系统(ASMP)(ASMP)的处理机调的处理机调 度度4.4.4 4.4.4 成组调度成组调度(Gang Scheduling)(Gang Scheduling)4.4.5 4.4.5 专用处理机调度专用处理机调度(Dedicated Processor (

55、Dedicated Processor Assignment) Assignment)4.4.1 4.4.1 与单处理机调度的区别与单处理机调度的区别一一注重整体运行效率（而不是个别处理机的利用率）注重整体运行效率（而不是个别处理机的利用率）二二更多样的调度算法更多样的调度算法三三多处理机访问多处理机访问OSOS数据结构时的互斥（对于共享内存数据结构时的互斥（对于共享内存系统）系统）四四调度单位广泛采用线程调度单位广泛采用线程4.4.2 4.4.2 对称式多处理系统对称式多处理系统(SMP)(SMP)按控制方式，按控制方式，SMPSMP调度算法可分为集中控制和分散控制。调度算法可分为集中控制和

56、分散控制。下下面所述静态和动态调度都是集中控制，而自调度是分散控面所述静态和动态调度都是集中控制，而自调度是分散控制。制。一一 静态分配静态分配(static assignment)(static assignment)：每个：每个CPUCPU设立一个就绪队设立一个就绪队列，进程从开始执行到完成，都在同一个列，进程从开始执行到完成，都在同一个CPUCPU上。上。1.1.优点：调度算法开销小。优点：调度算法开销小。2.2.缺点：容易出现忙闲不均。缺点：容易出现忙闲不均。二二 动态分配动态分配(dynamic assignment)(dynamic assignment)：各个：各个CPUCPU采

57、用一个公共就采用一个公共就绪队列，队首进程每次分派到当前空闲的绪队列，队首进程每次分派到当前空闲的CPUCPU上执行。上执行。三三 分散控制分散控制自调度自调度(self-scheduling)(self-scheduling)：各个：各个CPUCPU采用一个公共就绪队采用一个公共就绪队列，每个处理机都可以从队列中选择适当进程来执行。需要对就列，每个处理机都可以从队列中选择适当进程来执行。需要对就绪队列的数据结构进行互斥访问控制。是最常用的算法，实现时绪队列的数据结构进行互斥访问控制。是最常用的算法，实现时易于移植采用单处理机的调度技术。易于移植采用单处理机的调度技术。4.4.3 4.4.3

58、非对称式多处理系统非对称式多处理系统(ASMP)(ASMP)主从处理机系统，由主处理机管理一个公共就绪队列，主从处理机系统，由主处理机管理一个公共就绪队列，并分派进程给从处理机执行。并分派进程给从处理机执行。s各个处理机有固定分工，如执行各个处理机有固定分工，如执行OSOS的系统功能，的系统功能，I/OI/O处理，处理，应用程序。应用程序。4.4.4 4.4.4 成组调度成组调度(gang scheduling)(gang scheduling)将一个进程中的一组线程，每次分派时同时到一组处理机将一个进程中的一组线程，每次分派时同时到一组处理机上执行，在剥夺处理机时也同时对这一组线程进行。上执

59、行，在剥夺处理机时也同时对这一组线程进行。优点优点: :1.1.通常这样的一组线程在应用逻辑上相互合作，成组调度通常这样的一组线程在应用逻辑上相互合作，成组调度提高了这些线程的执行并行度，有利于减少阻塞和加快提高了这些线程的执行并行度，有利于减少阻塞和加快推进速度，最终提高系统吞吐量。推进速度，最终提高系统吞吐量。2.2.每次调度可以完成多个线程的分派，在系统内线程总数每次调度可以完成多个线程的分派，在系统内线程总数相同时能够减少调度次数，从而减少调度算法的开销相同时能够减少调度次数，从而减少调度算法的开销4.4.54.4.5 专用处理机调度专用处理机调度(dedicated processo

60、r assignment)(dedicated processor assignment)为进程中的每个线程都固定分配一个为进程中的每个线程都固定分配一个CPUCPU，直到该线程执，直到该线程执行行完成。完成。缺点：线程阻塞时，造成缺点：线程阻塞时，造成CPUCPU的闲置。优点：线程执行时不需切的闲置。优点：线程执行时不需切换，相应的开销可以大大减小，推进速度更快。换，相应的开销可以大大减小，推进速度更快。适用场合：适用场合：CPUCPU数量众多的高度并行系统，单个数量众多的高度并行系统，单个CPUCPU利用率已不太利用率已不太重要。重要。4.5 4.5 调度算法举例调度算法举例4.5.1 4