第三章_处理机调度与锁.ppt

《第三章_处理机调度与锁.ppt》由会员分享，可在线阅读，更多相关《第三章_处理机调度与锁.ppt（59页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 操作系统 第三章 处理机调度与死锁第三章 处理机调度与死锁3.1 处理机的分级调度3.2 作业调度3.3 进程调度3.4 死锁1 1 操作系统 第三章 处理机调度与死锁3.1 处理机的分级调度 处理机资源是计算机系统中最重要的资源，它的调度处理机资源是计算机系统中最重要的资源，它的调度策略，常常表示操作系统的某种特征，其算法的优劣直接策略，常常表示操作系统的某种特征，其算法的优劣直接影响整个系统的性能。影响整个系统的性能。处理机调度需要解决三个问题：处理机调度需要解决三个问题：(1)(1)处理机分配的策略，即需要确定处理机的调度算法；处理机分配的策略，即需要确定处理机的调度算法；(2)(2)

2、什么时候分配处理机，即需要确定处理机的调度时机；什么时候分配处理机，即需要确定处理机的调度时机；(3)(3)如何分配处理机，即需要给出处理机的调度过程。如何分配处理机，即需要给出处理机的调度过程。2 2 操作系统 第三章 处理机调度与死锁2 2）交换调度（中级调度）（均衡调度）：）交换调度（中级调度）（均衡调度）：按照给定的原则实现按照给定的原则实现进程进程在主存和外存交换区之间的在主存和外存交换区之间的换换进换出进换出，以解决内存紧张问题，特别是具有虚拟存储器的系，以解决内存紧张问题，特别是具有虚拟存储器的系统中。统中。3 3）进程调度（低级调度）：）进程调度（低级调度）：按按照照某某种种策

3、策略略从从进进程程就就绪绪队队列列中中选选择择一一个个就就绪绪进进程程，使其使其占有处理机占有处理机运行。运行。4 4）线程调度线程调度 处理机调度可以分为处理机调度可以分为4 4级：级：1 1）作业调度（高级调度）：）作业调度（高级调度）：按一定原则选择按一定原则选择若干个后备作业若干个后备作业调入主存调入主存，分配资源，分配资源，并建立相应的进程，投入运行。当该作业执行完毕时，还负并建立相应的进程，投入运行。当该作业执行完毕时，还负责回收资源。责回收资源。3 3 操作系统 第三章 处理机调度与死锁3.2 作业调度一、作业、作业步、作业流(1)(1)作业：作业：是用户一次请求计算机系统为它完

4、成任务所进是用户一次请求计算机系统为它完成任务所进 行的工作总和。行的工作总和。(2)(2)作业步：作业步：作业加工工作中的一个相对独立的步骤称为作作业加工工作中的一个相对独立的步骤称为作业步。业步。对作业的处理一般有这样几个作业步：对作业的处理一般有这样几个作业步：编辑（修改）、编译、连接、运行编辑（修改）、编译、连接、运行。(3)(3)作业流：作业流：是按一定顺序组织好的一批作业。是按一定顺序组织好的一批作业。4 4 操作系统 第三章 处理机调度与死锁作业步之间的关系：作业步之间的关系：每个作业步运行的结果产生下一个作业步所需要的文件。每个作业步运行的结果产生下一个作业步所需要的文件。一个

5、作业步能否正确地执行，依赖于前一个作业步是否一个作业步能否正确地执行，依赖于前一个作业步是否成功的完成。成功的完成。例如：例如：user.c user.obj user.exe 编辑编辑 编译编译 连接连接 运行运行 作业步之间的关系作业步之间的关系二、作业的类型根据计算机系统的作业处理方式不同，可以把作业分成两类：根据计算机系统的作业处理方式不同，可以把作业分成两类：脱机作业（批处理作业）脱机作业（批处理作业）联机作业（交互式作业或终端型作业）联机作业（交互式作业或终端型作业）。5 5 操作系统 第三章 处理机调度与死锁三、作业的组织 程序程序 作业由三部分组成作业由三部分组成 数据数据 作

6、业说明书作业说明书（说明用户的控制意图）（说明用户的控制意图）作业控制块作业控制块（JCBJCB）：为了管理和调度已进入系统的各个作业为了管理和调度已进入系统的各个作业，系统设置的用于记录作业的基本情况的数据结构系统设置的用于记录作业的基本情况的数据结构。作业控制块作业控制块（JCBJCB）的主要内容的主要内容：(1)(1)作业的基本情况作业的基本情况 用户名、作业名、作业的状态和使用的语言用户名、作业名、作业的状态和使用的语言等。等。(2)(2)作业的控制要求作业的控制要求 控制方式控制方式、类型、优先数、操作顺序和出错处理等。、类型、优先数、操作顺序和出错处理等。(3)(3)作业的资源要求

7、作业的资源要求 作业建立的时间、要求运行的时间、最迟完成的时间、需作业建立的时间、要求运行的时间、最迟完成的时间、需要的主存容量、外设的种类及数量和资源使用情况。要的主存容量、外设的种类及数量和资源使用情况。6 6 操作系统 第三章 处理机调度与死锁 作业的输入作业的输入作业的建立包括两个子过程作业的建立包括两个子过程 作业控制块作业控制块（JCBJCB）的建立的建立作业的输入方式作业的输入方式:1.1.联机输入方式联机输入方式 2.2.脱机输入方式脱机输入方式(预输入方式预输入方式)3.3.直接耦合方式直接耦合方式 4.SPOOLING4.SPOOLING系统系统 5.5.网络输入方式网络输

8、入方式 JCBJCB（作业控制块）的建立作业控制块）的建立:系统在作业输入到系统在作业输入到外存外存，进入，进入后备状态后备状态时为作业建立时为作业建立 JCB JCB，它是作业存在的惟一标志它是作业存在的惟一标志.四、作业的建立7 7 操作系统 第三章 处理机调度与死锁 一个作业从提交给计算机系统到执行结束退出系统，一一个作业从提交给计算机系统到执行结束退出系统，一般都要经历般都要经历4 4个状态：个状态：提交、后备（收容）、执行和完成。提交、后备（收容）、执行和完成。1 1）提交状态：提交状态：通过终端设备向计算机的磁盘输入作业信息通过终端设备向计算机的磁盘输入作业信息时所处的状态。时所处

9、的状态。2 2）后备状态：后备状态：作业的全部信息已输入到磁盘的一个专用区作业的全部信息已输入到磁盘的一个专用区(输入井输入井)中等待作业调度时所处的状态。中等待作业调度时所处的状态。3 3）执行状态：执行状态：在后备作业队列中的作业一旦被作业调度程在后备作业队列中的作业一旦被作业调度程序选中，为它分配了必要的资源，并且建立了进程序选中，为它分配了必要的资源，并且建立了进程,开始开始处理时所处的状态。处理时所处的状态。4 4）完成状态：完成状态：作业完成其全部任务后，进程撤消作业完成其全部任务后，进程撤消,做善后做善后处理时的作业状态称为完成状态。处理时的作业状态称为完成状态。五、作业的状态8

10、 8 操作系统 第三章 处理机调度与死锁一、作业的状态及其转换 作业的状态及其转换作业的状态及其转换 执执行行 进程调度进程调度 内存内存 线程调度线程调度运运行行等等待待就就绪绪外存外存 就就绪绪等等待待提提交交后后备备完完成成作业输入作业输入 作业调度作业调度 交换调度交换调度 作业调度作业调度 执执行行9 9 操作系统 第三章 处理机调度与死锁二、作业调度的功能 作业调度的主要任务：作业调度的主要任务：完成作业从后备状态到运行状态和完成作业从后备状态到运行状态和从运行状态到完成状态的转变。从运行状态到完成状态的转变。1 1）记录系统中各作业的状况）记录系统中各作业的状况。作业调度程序应包

11、括以下功能：作业调度程序应包括以下功能：作业调度程序为了挑选一个作业投入运行，并且在运作业调度程序为了挑选一个作业投入运行，并且在运行中对它实施管理，它必须掌握该作业进入系统时的有关行中对它实施管理，它必须掌握该作业进入系统时的有关情况并随时记录该作业在各运行阶段的变化。为此，系统情况并随时记录该作业在各运行阶段的变化。为此，系统为每一个已进入系统的作业分配一个为每一个已进入系统的作业分配一个作业控制块作业控制块JCBJCB(Job(Job ContrlContrl block)block)。每个作业的每个作业的JCBJCB在该作业进入后备状态时在该作业进入后备状态时由系统建立在该作业退出系统

12、时由系统撤消。每个作业由系统建立在该作业退出系统时由系统撤消。每个作业在各阶段的情况在各阶段的情况(包括分配的资源和作业状态等包括分配的资源和作业状态等)都记录在都记录在它的它的JCBJCB中。中。1010 操作系统 第三章 处理机调度与死锁2)2)按一定的调度算法，从后备作业中挑选出一个或几个作按一定的调度算法，从后备作业中挑选出一个或几个作业运行。业运行。系统中处于后备状态的作业较多，几十个甚至几百个，系统中处于后备状态的作业较多，几十个甚至几百个，处于运行状态的作业只是有限的几个如最多不超过处于运行状态的作业只是有限的几个如最多不超过4 4个或个或8 8个。个。作业调度程序的一个重要职能

13、就是在适当的时候按一定的调作业调度程序的一个重要职能就是在适当的时候按一定的调度原则从后备作业中挑选出若干个作业投入运行。度原则从后备作业中挑选出若干个作业投入运行。3)3)为被选中的作业做好执行前的准备工作。为被选中的作业做好执行前的准备工作。为该作业建立相应的进程，并且为这些进程提供所需的为该作业建立相应的进程，并且为这些进程提供所需的资源，如内存和外部设备等。资源，如内存和外部设备等。4)4)在作业执行结束时做善后处理工作。在作业执行结束时做善后处理工作。输出如运行时间、作业执行情况等必要信息，回收该作输出如运行时间、作业执行情况等必要信息，回收该作业所占用的全部资源，撤消与该作业有关的

14、全部进程和该作业所占用的全部资源，撤消与该作业有关的全部进程和该作业的作业控制块。业的作业控制块。1111 操作系统 第三章 处理机调度与死锁注：注：1 1）处理机的分配工作由进程调度程序完成。内存的分配处理机的分配工作由进程调度程序完成。内存的分配和释放工作由存贮管理程序完成。外部设备的分配和释放和释放工作由存贮管理程序完成。外部设备的分配和释放工作由设备管理程序完成。工作由设备管理程序完成。三、作业控制块2 2）作业调度程序只保证被选中的作业获得使用处理机的作业调度程序只保证被选中的作业获得使用处理机的资格，把一个作业的内存、外设要求转给相应的管理程序。资格，把一个作业的内存、外设要求转给

15、相应的管理程序。作业控制块作业控制块JCBJCB是作业存在的标志，记录与该作业有关是作业存在的标志，记录与该作业有关的信息。的信息。1212 操作系统 第三章 处理机调度与死锁作业名作业名资源要求资源要求估计执行时间估计执行时间最迟完成时间最迟完成时间要求的主存量要求的主存量要求外设的类型及台数要求外设的类型及台数要求文件量和输出量要求文件量和输出量资源使用情况资源使用情况进入系统时间进入系统时间开始执行时间开始执行时间已已执行时间执行时间主存地址主存地址外设台号外设台号类型类型控制方式控制方式作业类型作业类型优先级优先级状态状态作业控制块作业控制块联机和脱机联机和脱机1313 操作系统 第三

16、章 处理机调度与死锁四、作业调度目标与性能衡量（1 1）公平性）公平性（2 2）均衡使用资源）均衡使用资源（3 3）较高的吞吐量）较高的吞吐量（4 4）较快的响应时间）较快的响应时间1.1.调度目标调度目标1414 操作系统 第三章 处理机调度与死锁（1 1）周转时间）周转时间T Ti i=完成时刻完成时刻TcTci i 提交时刻提交时刻TsTsi i =等待时间等待时间TwTwi i+运行时间运行时间 TrTri i对于进入系统的对于进入系统的n n个作业而言，个作业而言，平均周转时间平均周转时间T T为为i i1 1用于衡量不同调度算法对同一作业流的调度性能用于衡量不同调度算法对同一作业流

17、的调度性能:平均周转时间越小，该作业调度算法的性能越好。平均周转时间越小，该作业调度算法的性能越好。2.2.调度性能衡量指标调度性能衡量指标1515 操作系统 第三章 处理机调度与死锁(2)(2)带权周转时间带权周转时间WiWi=Ti=TiTriTri它能说明作业它能说明作业i i的相对等待时间。的相对等待时间。n n 平均带权周转时间平均带权周转时间W=W=（WiWi）n n i=1i=1用于衡量同一调度算法对不同作业流的调度性能：用于衡量同一调度算法对不同作业流的调度性能：平平均均带带权权周周转转时时间间越越小小，作作业业调调度度算算法法对对该该作作业业流流的的调调度度性能越好。性能越好。

18、对对于于批批处处理理系系统统，主主要要依依据据平平均均周周转转时时间间和和平平均均带带权权周周转转时时间间来来作作为为衡衡量量调调度度算算法法性性能能的的指指标标；而而对对于于分分时时系系统统和和实实时时系系统统，外外加加平平均均响响应应时时间间作作为为衡衡量量调调度度算算法性能的指标。法性能的指标。1616 操作系统 第三章 处理机调度与死锁五、作业调度算法 按作业来到的先后次序进行调度。这种算法优先考虑按作业来到的先后次序进行调度。这种算法优先考虑在系统中等待时间最长的作业，而不管它要求运行时间的在系统中等待时间最长的作业，而不管它要求运行时间的长短。长短。优点：优点：容易实现；容易实现；

19、缺点：缺点：没有考虑各个作业运行特征和资源要求的差异，系没有考虑各个作业运行特征和资源要求的差异，系统效率较低。统效率较低。1.1.先来先服务调度算法（先来先服务调度算法（FCFSFCFS）1717 操作系统 第三章 处理机调度与死锁例：先来先服务调度算法（单位：小时，并以十进制计）例：先来先服务调度算法（单位：小时，并以十进制计）作业作业提交时间提交时间运行时间运行时间开始时间开始时间完成时间完成时间周转时间周转时间带权带权周转时间周转时间 1 8.00 2.00 8.0010.00 2.00 1 2 8.50 0.5010.0010.50 2.00 4 3 9.00 0.1010.5010

20、.60 1.60 16 4 9.50 0.2010.6010.80 1.30 6.5平均周转时间平均周转时间T T1.7251.725平均带权周转时间平均带权周转时间W W6.8756.8751818 操作系统 第三章 处理机调度与死锁2.2.短作业优先调度算法（短作业优先调度算法（SJFSJF）此算法总是优先调度要求运行时间最短的作业。此算法总是优先调度要求运行时间最短的作业。优点：优点：易于实现，效率比较高。易于实现，效率比较高。缺点：缺点：只照顾短作业而不考虑长作业的利益。只照顾短作业而不考虑长作业的利益。如果系统不断地接受新的短作业。则有可能较长作业如果系统不断地接受新的短作业。则有可

21、能较长作业长时间等待而不能运行。长时间等待而不能运行。1919 操作系统 第三章 处理机调度与死锁例：短作业优先调度算法（单位：小时，并以十进制计）例：短作业优先调度算法（单位：小时，并以十进制计）作业作业提交时间提交时间运行时间运行时间开始时间开始时间完成时间完成时间周转时间周转时间带权带权周转时间周转时间 1 8.00 2.00 8.0010.00 2.00 1 2 8.50 0.5010.3010.80 2.30 4.6 3 9.00 0.1010.0010.10 1.10 11 4 9.50 0.2010.1010.30 0.80 4平均周转时间平均周转时间T T1.551.55平均带

22、权周转时间平均带权周转时间W W5.155.152020 操作系统 第三章 处理机调度与死锁3.3.响应比高者优先调度算法响应比高者优先调度算法 响应比是指作业的响应时间与作业估计运行时间的比响应比是指作业的响应时间与作业估计运行时间的比值。值。选择原则是优先选取响应比值最大的作业。即兼顾等选择原则是优先选取响应比值最大的作业。即兼顾等待时间长和运行时间短的作业，它是待时间长和运行时间短的作业，它是FCFSFCFS和和SJFSJF算法的结合。算法的结合。响应比响应比1 1作业等待时间作业等待时间/执行时间执行时间2121 操作系统 第三章 处理机调度与死锁 作业作业提交时间提交时间运行时间运行

23、时间开始时间开始时间完成时间完成时间周转时间周转时间带权带权周转时间周转时间 1 8.00 2.00 8.0010.00 2.00 1 2 8.50 0.5010.1010.60 2.10 4.2 3 9.00 0.1010.0010.10 1.10 11 4 9.50 0.2010.6010.80 1.30 6.5例：响应比高者优先调度算法（单位：小时，并以十进制计例：响应比高者优先调度算法（单位：小时，并以十进制计)平均周转时间平均周转时间T T1.6251.625，平均带权周转时间平均带权周转时间W W5.6755.675 响应比响应比1 1作业等待时间作业等待时间/执行时间执行时间例如

24、：当作业例如：当作业3 3结束时，结束时，Rp2=1Rp2=1作业等待时间作业等待时间/可执行时间可执行时间=1+(10.10-8.50)/0.5=1+3.2=1+(10.10-8.50)/0.5=1+3.2Rp4=1Rp4=1作业等待时间作业等待时间/可执行时间可执行时间=1+(10.10-9.50)/0.2=1+3=1+(10.10-9.50)/0.2=1+32222 操作系统 第三章 处理机调度与死锁 这种算法是根据确定的优先数来选取作业，每次总是选这种算法是根据确定的优先数来选取作业，每次总是选择优先级最高的作业。择优先级最高的作业。4.4.最高优先级优先调度算法最高优先级优先调度算法

25、规定用户作业优先数的方法规定用户作业优先数的方法:1 1）由用户自己提出作业的优先数。）由用户自己提出作业的优先数。有的用户为了自己的作业有的用户为了自己的作业尽快被系统选中就设法提高自己作业的优先数，这时系统可以尽快被系统选中就设法提高自己作业的优先数，这时系统可以规定优先数越高则需付出的计算机使用费就越多，以作限制。规定优先数越高则需付出的计算机使用费就越多，以作限制。2 2）由系统综合有关因素来确定用户作业的优先数。）由系统综合有关因素来确定用户作业的优先数。例如，根据作业的缓急程度、作业计算时间的长短、等待例如，根据作业的缓急程度、作业计算时间的长短、等待时间的多少、资源申请情况等来确

26、定优先数。确定优先数时，时间的多少、资源申请情况等来确定优先数。确定优先数时，各因素的比例应根据系统设计目标来分析这些因素在系统中的各因素的比例应根据系统设计目标来分析这些因素在系统中的地位而决定。地位而决定。2323 操作系统 第三章 处理机调度与死锁3.3 进程调度进程调度：进程调度：就是系统按照某种算法把就是系统按照某种算法把CPUCPU动态地分配给某一就动态地分配给某一就绪进程。进程调度工作是通过进程调度程序来完成的。绪进程。进程调度工作是通过进程调度程序来完成的。一、调度/分派结构调度程序：调度程序：将进程插入就绪队列，按一定原则保持队列结构；将进程插入就绪队列，按一定原则保持队列结

27、构；分派程序：分派程序：将进程从就绪队列中移出，建立它执行的机器状态。将进程从就绪队列中移出，建立它执行的机器状态。进程切换进程切换：把一个进程让出处理机，由另一个进程占用处理机把一个进程让出处理机，由另一个进程占用处理机的调度过程称为的调度过程称为“进程切换进程切换”。分派程序首先将正在执行的进程的分派程序首先将正在执行的进程的CPUCPU现场信息保存在该进现场信息保存在该进程程PCBPCB的现场保护区中，再从被调度选中的进程的现场保护区中，再从被调度选中的进程PCBPCB的现场保护的现场保护区中取出它的区中取出它的CPUCPU现场信息恢复。现场信息恢复。CPUCPU现场信息由程序状态寄存现

28、场信息由程序状态寄存器、程序计数器以及若干通用寄存器的内容组成。器、程序计数器以及若干通用寄存器的内容组成。2424 操作系统 第三章 处理机调度与死锁1.1.记录系统中所有进程的执行情况。记录系统中所有进程的执行情况。二、进程调度功能 记录系统中所有进程的有关情况，对进程控制块记录系统中所有进程的有关情况，对进程控制块PCBPCB的内的内容作相应的登记、修改，记录进程的状态特征。容作相应的登记、修改，记录进程的状态特征。2.2.按照一定调度策略选择一个占有处理机的就绪进程。按照一定调度策略选择一个占有处理机的就绪进程。在处理机空闲时根据一定的原则选择一个进程去运行，在处理机空闲时根据一定的原

29、则选择一个进程去运行，同时确定获得处理机的时间。同时确定获得处理机的时间。3.3.实施处理机的分配和回收实施处理机的分配和回收(进行进程上下文切换进行进程上下文切换)。回收回收:正在运行的进程由于某种原因让出处理机，该进程的状正在运行的进程由于某种原因让出处理机，该进程的状态改为态改为“阻塞阻塞”，插入到相应队列中，保留该进程的，插入到相应队列中，保留该进程的CPUCPU现场。现场。分配分配:根据调度原则选择进程去运行，把选中进程从就绪队列中根据调度原则选择进程去运行，把选中进程从就绪队列中移出移出,改状态为改状态为“运行运行”，把，把CPUCPU控制权交给被选中的进程，将控制权交给被选中的进

30、程，将选中进程的有关选中进程的有关PCBPCB现场信息，分别送到相应的寄存器中。现场信息，分别送到相应的寄存器中。2525 操作系统 第三章 处理机调度与死锁三、进程调度时机 1 1）正在执行的进程完成其任务而正在执行的进程完成其任务而运行完毕运行完毕。2 2）执行中的进程由于执行中的进程由于请求某个事件的发生请求某个事件的发生，比如，比如I/OI/O请求，请求，等待所需要的信号、信件的到来等而自己调用等待所需要的信号、信件的到来等而自己调用阻塞阻塞原语将自原语将自己阻塞起来，进入相应的等待队列。己阻塞起来，进入相应的等待队列。3 3）在分时系统中，当进程使在分时系统中，当进程使用完规定的时间

31、片用完规定的时间片。4 4）在在采用可抢占采用可抢占调度方式的系统中，当具有更高优先级的调度方式的系统中，当具有更高优先级的进程要求使用处理机。进程要求使用处理机。2626 操作系统 第三章 处理机调度与死锁四、进程调度方式 1.1.非抢先调度方式非抢先调度方式 这种方式是当有重要或紧迫的进程进入就绪队列时，仍这种方式是当有重要或紧迫的进程进入就绪队列时，仍然让正在执行的进程继续执行，直到该进程完成任务终止运然让正在执行的进程继续执行，直到该进程完成任务终止运行或发生某种等待事件而进入阻塞状态时，才主动放弃占有行或发生某种等待事件而进入阻塞状态时，才主动放弃占有的处理机，把处理机分配给重要或紧

32、迫的就绪进程，以使其的处理机，把处理机分配给重要或紧迫的就绪进程，以使其运行。运行。2.2.可抢先调度方式可抢先调度方式 这这种种方方式式则则是是重重要要或或紧紧迫迫的的进进程程一一到到，便便把把正正在在执执行行的的进进程程占占有有的的处处理理机机强强行行剥剥夺夺下下来来，并并转转给给这这个个优优先先级级比比它它更更高的重要或紧迫的就绪进程，使其运行。高的重要或紧迫的就绪进程，使其运行。2727 操作系统 第三章 处理机调度与死锁五、进程调度算法 采用最高优先级优先调度算法时，系统对每个进程确采用最高优先级优先调度算法时，系统对每个进程确定一个优先数，进程的优先数用于表示进程的重要性及运定一个

33、优先数，进程的优先数用于表示进程的重要性及运行的优先性。调度时，系统把处理机分配给优先级最高的行的优先性。调度时，系统把处理机分配给优先级最高的就绪进程。如果就绪进程具有相同的优先数，则再按先来就绪进程。如果就绪进程具有相同的优先数，则再按先来先服务的次序分配处理机。先服务的次序分配处理机。先先来来先先服服务务调调度度算算法法是是按按照照进进程程进进入入就就绪绪队队列列的的先先后后次序来选择进程分配处理机。次序来选择进程分配处理机。（一）最高优先级优先调度算法2828 操作系统 第三章 处理机调度与死锁系统确定优先数的方法：1.1.静静态态优优先先数数法法：静静态态优优先先数数是是在在创创建建

34、进进程程时时系系统统为为其其确确定的，并且在进程的生命期内不再改变。定的，并且在进程的生命期内不再改变。确定静态优先数的原则：确定静态优先数的原则：1 1）按进程类型。）按进程类型。系统进程的优先级高于用户进程的优先级。系统进程的优先级高于用户进程的优先级。2 2）按按进进程程使使用用的的资资源源。进进程程所所使使用用的的资资源源越越多多，进进程程的的优优先级越低；反之，则进程的优先级越高。先级越低；反之，则进程的优先级越高。3 3）按按进进程程的的估估计计运运行行时时间间。进进程程的的估估计计运运行行时时间间越越长长，进进程的优先级越低；反之，则进程的优先级越高。程的优先级越低；反之，则进程

35、的优先级越高。4 4）由用户指定。）由用户指定。有些系统可以按收费标准不同，设置不同的有些系统可以按收费标准不同，设置不同的优先级别，可以由用户指定。优先级别，可以由用户指定。静态优先级法实现起来比较简单，但不能反映系统以及进程静态优先级法实现起来比较简单，但不能反映系统以及进程在运行过程中的动态变化情况，系统管理效果显然不佳。在运行过程中的动态变化情况，系统管理效果显然不佳。2929 操作系统 第三章 处理机调度与死锁2.2.动态优先数法。动态优先数法。动态优先数是指在系统创建进程时，根动态优先数是指在系统创建进程时，根据系统资源的使用情况和进程的当前特点确定一个优先数，据系统资源的使用情况

36、和进程的当前特点确定一个优先数，然后，在进程运行过程中再根据情况的变化动态调整进程的然后，在进程运行过程中再根据情况的变化动态调整进程的优先数。优先数。调整进程优先数的原调整进程优先数的原则：则：1 1）进程占有处理机的时间越长，则进程的优先级越低；进程）进程占有处理机的时间越长，则进程的优先级越低；进程的等待时间越长，则进程的优先级越高。的等待时间越长，则进程的优先级越高。2 2）根据进程所执行的程序的轻重缓急程度，调整进程的优先）根据进程所执行的程序的轻重缓急程度，调整进程的优先数。数。3030 操作系统 第三章 处理机调度与死锁（二）时间片轮转调度算法 在分时系统中，为了满足系统对响应时

37、间的要求，通在分时系统中，为了满足系统对响应时间的要求，通常采用时间片轮转调度算法。常采用时间片轮转调度算法。1.简单轮转法(固定时间片轮转法）在这种调度算法中，系统把所有就绪进程按到达的先在这种调度算法中，系统把所有就绪进程按到达的先后顺序形成一个就绪队列，就绪队列中的所有进程按时间后顺序形成一个就绪队列，就绪队列中的所有进程按时间片依次轮流获得处理机。片依次轮流获得处理机。3131 操作系统 第三章 处理机调度与死锁 时间片的大小应根据进程要求系统给出应答的时间和进时间片的大小应根据进程要求系统给出应答的时间和进入系统的进程数来决定。可以表示为：入系统的进程数来决定。可以表示为：其其中中，

38、q q是是时时间间片片的的大大小小，T T是是系系统统的的响响应应时时间间，N N是是进进入入系系统统的进程数。的进程数。简简单单轮轮转转法法的的优优点点是是简简单单、方方便便，但但由由于于采采用用固固定定时时间间片片的的方方式式，调调度度欠欠灵灵活活，服服务务质质量量不不够够理理想想。可可以以通通过过以以下下两个方面加以改进：两个方面加以改进：1 1）将固定时间片方式改为可变时间片方式；）将固定时间片方式改为可变时间片方式；2 2）将单就绪队列改为多就绪队列。）将单就绪队列改为多就绪队列。3232 操作系统 第三章 处理机调度与死锁2.可变时间片轮转法 时时间间片片可可变变会会给给系系统统带

39、带来来好好处处。如如果果要要求求系系统统快快速速应应答答，则则时时间间片片小小一一些些，这这样样可可使使轮轮转转一一遍遍的的总总时时间间减减少少而而可可对对进进程程尽尽快快应应答答。如如果果进进程程数数少少，则则时时间间片片可可以以大大一一些些，这样可减少进程调度的次数，提高系统效率。这样可减少进程调度的次数，提高系统效率。3333 操作系统 第三章 处理机调度与死锁可变时间片轮转法中，可采取如下措施调整时间片：可变时间片轮转法中，可采取如下措施调整时间片：1)1)固定周期轮转法。固定周期轮转法。在在这这种种方方法法中中，每每一一轮轮调调度度中中所所得得的的时时间间片片q q值值的的大大小小仅

40、仅在在这这一一轮轮调调度度中中有有效效。系系统统的的响响应应时时间间T T固固定定，在在每每一一轮轮调调度度中中，根根据据当当前前就就绪绪队队列列中中的的进进程程数数n n计计算算这这一一轮轮调调度度的的时时间间片片：q qT/T/n n，然然后后进进行行轮轮转转，每每个个进进程程可可获获得得这这一一轮轮的的一一个个时时间间片片q q。在在此此期期间间所所到到达达的的进进程程暂暂不不进进入入就就绪绪队队列列，等等此此次次轮轮转转完完毕毕再再一一并并进进入入。系系统统根根据据此此时时就就绪绪队列的进程数重新计算时间片队列的进程数重新计算时间片q q，然后开始下一轮循环。然后开始下一轮循环。2)2

41、)时时间间片片的的大大小小取取决决于于优优先先级级的的高高低低，优优先先级级高高的的进进程程分分得的时间片较大，优先级低的进程分得的时间片较小。得的时间片较大，优先级低的进程分得的时间片较小。3)3)短作业的时间片较小，短作业的时间片较小，长作业的时间片较大。长作业的时间片较大。3434 操作系统 第三章 处理机调度与死锁3.多级反馈轮转法（多重时间片轮转调度算法）调度算法的实施过程如下：调度算法的实施过程如下：1.1.设设置置多多个个就就绪绪队队列列，并并为为各各个个就就绪绪队队列列赋赋予予不不同同的的优优先先级级。第第一一个个就就绪绪队队列列的的优优先先级级最最高高，第第二二个个就就绪绪队

42、队列列的的优优先先级次之，其余各个就绪队列的优先级逐个降低。级次之，其余各个就绪队列的优先级逐个降低。2.2.赋赋予予各各个个就就绪绪队队列列中中进进程程的的时时间间片片也也各各不不相相同同，优优先先级级越越高高的的就就绪绪队队列列中中的的进进程程的的时时间间片片越越小小，反反之之，优优先先级级越越低低的的就绪队列中的进程的时间片越大。就绪队列中的进程的时间片越大。3.3.当一个新被创建的进程当一个新被创建的进程进入就绪队列后，首先将它加入第进入就绪队列后，首先将它加入第一个就绪队列的队尾，按先来先服务的原则排队等待调度。一个就绪队列的队尾，按先来先服务的原则排队等待调度。3535 操作系统

43、第三章 处理机调度与死锁 当当轮轮到到该该进进程程执执行行时时，如如能能在在该该时时间间片片内内完完成成，则则该该进进程程将将被被撤撤消消；如如果果在在一一个个时时间间片片结结束束时时该该进进程程尚尚未未完完成成，调调度度程程序序则则将将该该进进程程转转入入第第二二个个就就绪绪队队列列的的队队尾尾，按按先先来来先先服服务务的的原原则则排排队队等等待待调调度度；如如果果它它在在第第二二个个就就绪绪队队列列中中运运行行一一个个时时间间片片后后仍仍未未完完成成，再再以以同同样样的的方方法法将将它它转转入入第第三三个个就就绪绪队列的队尾，队列的队尾，如此下去。如此下去。4.4.仅仅当当第第一一个个就就

44、绪绪队队列列空空闲闲时时，调调度度程程序序才才调调度度第第二二个个就就绪绪队队列列中中的的进进程程运运行行；仅仅当当第第1 1至至第第i i1 1个个就就绪绪队队列列均均为为空空时时，才才会会调调度度第第i i个个就就绪绪队队列列中中的的进进程程运运行行。如如果果处处理理机机正正在在第第i i个个就就绪绪队队列列中中为为某某进进程程服服务务时时，又又有有新新进进程程进进入入优优先先级级较较高高的的就就绪绪队队列列时时，则则此此时时新新进进程程将将抢抢占占正正在在运运行行进进程程的的处处理理机机，即即由由调调度度程程序序把把正正在在运运行行的的进进程程放放回回到到第第i i个个就就绪绪队队列列的

45、的队队尾，然后将处理机重新分配给新进程。尾，然后将处理机重新分配给新进程。3636 操作系统 第三章 处理机调度与死锁3.4 死锁 一、死锁的概念死锁：死锁：各并发进程彼此互相等待对方所拥有的资源，且这各并发进程彼此互相等待对方所拥有的资源，且这些并发进程在得到对方的资源之前不会释放自己所拥有的些并发进程在得到对方的资源之前不会释放自己所拥有的资源。从而造成系统中一些进程处于无休止的等待状态，资源。从而造成系统中一些进程处于无休止的等待状态，在无外力作用的情况下，这些进程永远也不能继续前进。在无外力作用的情况下，这些进程永远也不能继续前进。我们称这种现象为我们称这种现象为死锁死锁。例：例：系统

46、中只有一台输入机系统中只有一台输入机R1R1和一台打印机和一台打印机R2R2可供进程可供进程P1P1和和P2P2共享。共享。3737 操作系统 第三章 处理机调度与死锁进程进程P1P1 进程进程P2P2 请求资源请求资源R1 R1 请求资源请求资源R2R2 请求资源请求资源R2 R2 请求资源请求资源R1R1 释放资源释放资源R1 R1 释放资源释放资源R2 R2 释放资源释放资源R2 R2 释放资源释放资源R1R1 R1R1R2R2 两个进程死锁的典型情况两个进程死锁的典型情况 3838 操作系统 第三章 处理机调度与死锁 进程在同步和通信的过程进程在同步和通信的过程当中也会产生死锁。当中也

47、会产生死锁。例如，在生产者例如，在生产者消费者消费者问题中，若把生产者进程中两问题中，若把生产者进程中两个个P P操作的顺序颠倒如下图所示：操作的顺序颠倒如下图所示：生产者进程生产者进程Pi Pi 生产一个产品生产一个产品 产品送入缓冲区产品送入缓冲区 P(avail)P(avail)P(mutexP(mutex)V(mutexV(mutex)V(full)V(full)在在这这种种情情况况下下，当当缓缓冲冲区区都都已已放放满满了了产产品品时时，生生产产者者仍仍可可执执行行P(mutexP(mutex)操操作作，于于是是该该生生产产者者掌掌握握了了对对缓缓冲冲区区的的存存取取控控 制制 权权，

48、当当 它它 继继 续续 执执 行行P(avail)P(avail)操操作作时时，由由于于没没有有空空缓冲区，该生产者被阻塞，并缓冲区，该生产者被阻塞，并3939 操作系统 第三章 处理机调度与死锁在在availavail上等待。若此时有一个消费者到达，尽管缓冲区中有上等待。若此时有一个消费者到达，尽管缓冲区中有产品，消费者在执行产品，消费者在执行P(full)P(full)操作时通过，但紧接着执行操作时通过，但紧接着执行P(mutexP(mutex)操作时，将因缓冲区已被阻塞的生产者所占有，而操作时，将因缓冲区已被阻塞的生产者所占有，而使消费者无法获得缓冲区的存取控制权而被阻塞。此时，出使消费

49、者无法获得缓冲区的存取控制权而被阻塞。此时，出现了生产者和消费者之间僵死的局面，亦即发生了死锁。现了生产者和消费者之间僵死的局面，亦即发生了死锁。二、产生死锁的原因 产生的产生的根本原因根本原因是系统能够提供的资源数少于需要该是系统能够提供的资源数少于需要该资源的进程数资源的进程数(系统资源不足系统资源不足)。1 1）对资源的分配策略（请求顺序）不当）对资源的分配策略（请求顺序）不当；2 2）进程推进顺序非法。）进程推进顺序非法。死锁起因是并发进程的资源竞争。但资源竞争并不一定死锁起因是并发进程的资源竞争。但资源竞争并不一定产生死锁。例如，在前一个例子中，进程产生死锁。例如，在前一个例子中，进

50、程P1P1和和P2P2的不同进展的不同进展情况将产生不同的结果。情况将产生不同的结果。4040 操作系统 第三章 处理机调度与死锁 P1P1和和P2P2都占用都占用R1R1 P1P1和和P2P2都占用都占用R2R2 P2P2的进展的进展 P1P1的进展的进展 占用占用R1 R1 占用占用R2 R2 释放释放R1 R1 释放释放R2 R2 请求请求R1 R1 请求请求R2 R2 请求请求R1R1 请求请求R2 R2 释放释放R1R1 释放释放R2R2 占用占用R1 R1 1 1 2 2 3 3 占用占用R2R2下面用图示来说明进程下面用图示来说明进程P1P1和和P2P2的三种可能的进展情况：的三