处理机调度与死锁ppt课件

《处理机调度与死锁ppt课件》由会员分享，可在线阅读，更多相关《处理机调度与死锁ppt课件（150页珍藏版）》请在金锄头文库上搜索。

1、2018/9/14,第三章 处理机调度与死锁,1,第三章 处理机调度与死锁,在多道程序环境下，进程的数目往往多于处理器的数目，多个进程共享处理机资源就必然引起对处理机的竞争，这就要求操作系统采取一定的策略（调度算法），动态地将处理机分配给各个进程使之能够执行。 处理机调度算法对整个计算机系统的综合性能指标有重要影响,2018/9/14,第三章 处理机调度与死锁,2,调度策略考虑： 周转时间 吞吐率 响应时间 设备利用率 研究的内容有： 作业与进程的关系 作业调度策略与算法 进程调度策略与算法,处理机调度,2018/9/14,第三章 处理机调度与死锁,3,第三章 处理机调度与死锁,3.1 处理机

2、调度的层次 3.2 调度队列模型和调度准则 3.3 调度算法 3.4 实时调度 3.5 产生死锁的原因和必要条件 3.6 预防死锁的方法 3.7 死锁的检测与解除,2018/9/14,第三章 处理机调度与死锁,4,可把处理机调度分成三个层次：高级调度中级调度低级调度,3.1 处理机调度的层次,2018/9/14,第三章 处理机调度与死锁,5,作业的定义,2018/9/14,第三章 处理机调度与死锁,6,作业的定义,作业：是指在一次应用业务处理过程中，从输入开始到输出结束，用户要求计算机所做的有关该次业务处理的全部工作。 用户的观点：在一次业务处理过程中，从输入程序和数据到输出结果的全过程。 系

3、统的观点（针对作业进行资源分配）：作业由程序及数据（作业体）和作业说明书（作业控制语言）组成。批处理系统以作业为单位把程序和数据输入内存以便执行。作业由不同的顺序相连的作业步组成。作业步：是在一个作业的处理过程中，计算机所做的相对独立的工作。,2018/9/14,第三章 处理机调度与死锁,7,每个作业步运行的结果产生下一个作业步所需要的文件。一个作业步能否正确地执行，依赖于前一个作业步是否成功地完成。,作业步之间的关系,2018/9/14,第三章 处理机调度与死锁,8,作业组织,作业由程序、数据和作业说明书三部分组成。程序和数据完成用户所要求的业务处理工作。作业说明书则体现用户的控制意图。用批

4、处理控制方式组织的作业，在作业进入系统之前，程序员除了要准备好源程序和初始数据外，还必须用作业控制语言来书写一份作业控制说明书，系统通过作业说明书控制文件形式的程序和数据，使之执行和操作。在批处理系统中，把一批作业依次放置在相应的输入设备上，在操作系统的控制下，依次将它们输入辅助存储器中，这样就形成了一个作业流，也称输入流。,2018/9/14,第三章 处理机调度与死锁,9,作业说明书,作业说明书包括作业基本情况、作业控制、作业资源要求的描述；它体现用户的控制意图。如：预计运行时间、要求的资源情况、执行优先级等。 作业基本情况描述：用户名、作业名、编程语言、最大处理时间等； 作业控制描述：作业

5、控制方式、作业步的操作顺序、作业执行出错处理等； 作业资源要求描述：处理时间、优先级、内存空间、外设类型和数量、库函数或实用程序等；,2018/9/14,第三章 处理机调度与死锁,10,作业的建立,建立一个作业必须把该作业所包含的程序和数据输入到计算机的外部辅助存储设备上，而且还要由作业注册程序在系统中为该作业申请建立起一个相应的作业控制块。 即作业的建立过程包括两个子过程：作业的输入；作业控制块的建立。,2018/9/14,第三章 处理机调度与死锁,11,JCB 的建立,在系统把作业信息输入到外存输入井之后，还需要根据作业说明书中的说明及其它信息建立作业控制块(JCB)。只有在获得JCB表项

6、和足够的输入井空间之后，一个作业才可能创建成功。JCB是作业存在的唯一标志。作业进入系统时，则为之建立JCB，当作业退出系统时，则其JCB也被撤消。,2018/9/14,第三章 处理机调度与死锁,12,作业控制块,内容：作业名、作业类型、资源要求、当前状态、资源使用情况以及该作业的优先级等。作业类型：计算型（要求CPU时间多）、管理型（要求输入/输出量大）和图形设计型（要求高速图形显示）等。资源要求：该作业估计执行时间、要求最迟完成时间、要求的内存量和外存量、要求的外设类型及台数以及要求的软件支持工具库函数等。,2018/9/14,第三章 处理机调度与死锁,13,资源使用情况：作业进入系统时间

7、、开始执行时间、已执行时间、内存地址、外设台数等。 作业进入系统时间：指作业的全部信息进入输入井，作业的状态成为后备状态的时间。 开始执行时间：指该作业被调度程序选中，其状态由后备状态变为执行状态的时间。 内存地址：指分配给该作业的内存区起始地址。 外设台数：指分配给该作业的外设实际台数。优先级：用来决定该作业的调度次序。可以由用户给定，也可以由系统动态计算产生,作业控制块,2018/9/14,第三章 处理机调度与死锁,14,作业的状态,作业从提交给系统直到它完成后离开系统前的整个活动过程，要经历四种不同状态： 提交状态：一个作业在其处于从输入设备进入外部存储设备的过程称为提交状态 后备状态（

8、收容状态）：输入管理系统不断地将作业输入到外存对应部分（或称输入井），如果一个作业的全部信息已全部输入到输入井，在它还没有被调度去执行前，该作业处于后备状态。 运行状态：作业一旦被作业调度程序选中而被送入主存中投入运行，作业就处于执行状态。 完成状态：作业运行完毕，但它所占用的资源尚未被系统全部回收时，该作业处于完成状态,2018/9/14,第三章 处理机调度与死锁,15,作业状态及其转换,2018/9/14,第三章 处理机调度与死锁,16,作业是用户向计算机提交任务的任务实体。 进程是计算机为了完成用户任务实体而设置的执行实体。 计算机要完成一个任务实体，必须要有一个以上的执行实体，因此一个

9、作业总是由一个以上的多个进程组成。,作业与进程的关系,2018/9/14,第三章 处理机调度与死锁,17,作业、作业步、进程的关系,2018/9/14,第三章 处理机调度与死锁,18,也称为作业调度、长程调度（Long-Term Scheduling）或宏观调度。 根据某种算法对外存输入井上的大量后备作业进行选择调入内存，并为它们创建进程、分配必要的资源，再将新创建的进程排在就绪队列上，准备执行。一般在批处理系统中有作业调度。而在分时系统中，为了及时响应，用户通过键盘输入的命令或数据都是直接送入内存，因此无需配置作业调度机制，实时系统亦然。,高级调度,2018/9/14,第三章 处理机调度与死

10、锁,19,高级调度 执行作业调度时应决定： 接纳多少个作业？ 接纳哪些作业？,取决于多道程序度。取决于所采用的调度算法，如先来先服务调度算法、短作业优先调度算法、最高响应比法等。,2018/9/14,第三章 处理机调度与死锁,20,作业调度功能,1: 记录系统中各作业的状况2：按某种算法从后备队列中挑选一个或一批作业调入内存，让它们投入执行。3：为被选中作业做好执行前的准备工作。4：在作业执行结束时做善后处理工作,2018/9/14,第三章 处理机调度与死锁,21, 按照某种调度算法从后备作业队列中选取作业。 为被选取的作业分配内存和外设资源（当系统为动态分配外设时，作业所申请的外设只作为调度

11、的参考因素）。因此要用到内存分配程序和外设分配程序。 为选中的作业建立相应的进程。 为作业开始运行做好一切准备工作。如构造和读写作业运行时所需要的有关表格及建立负责其运行控制的作业运行控制程序。 在作业运行完毕或运行过程中因某种原因需要撤离时，作业调度程序还要完成作业的善后处理工作，如输出作业管理信息（执行时间），收回分配给该作业的全部资源，撤销与该作业有关的全部进程和该作业的作业控制块等,作业调度应完成如下几方面的工作,2018/9/14,第三章 处理机调度与死锁,22,作业从后备状态到执行状态,2018/9/14,第三章 处理机调度与死锁,23,作业从执行状态到完成状态,2018/9/14

12、,第三章 处理机调度与死锁,24,作业调度目标与性能衡量,1)调度目标 对所有作业应该是公平合理 应使设备有高的利用率 执行尽可能多的作业 有快的响应时间,2018/9/14,第三章 处理机调度与死锁,25,2）在批处理系统中衡量作业调度算法优劣的性能量度 周转时间其中某一作业进入“输入井”的时间为Tsi ，它被选中执行，运行结束时的时间为Tein 个作业平均周转时间为：,作业调度目标与性能衡量,2018/9/14,第三章 处理机调度与死锁,26,作业调度目标与性能衡量,一个作业的周转时间说明了该作业在系统内停留的时间，包含两部分：一是等待时间；二为执行时间，即带权周转时间平均带权周转时间：,

13、2018/9/14,第三章 处理机调度与死锁,27,又称中程调度(Medium-Term Scheduling)、交换调度。 引入中级调度的目的是为了提高内存的利用率和系统吞吐量。 将目前不在运行态的进程，包括其数据，从内存交换到外存（此时进程的状态为挂起状态），将新进程的代码、数据、栈等交换入内存。,中级调度,2018/9/14,第三章 处理机调度与死锁,28,也称微观调度、进程调度或短程调度（Short-Term Scheduling）。 用来决定就绪队列中的哪个进程应获得处理机，再由分派程序执行把处理机分配给该进程的具体操作。 从处理机资源分配的角度来看，处理机需要经常选择就绪进程或线程

14、进入运行状态。由于低级调度算法的频繁使用，要求在实现时做到高效（算法不宜复杂） 任何OS都必须配置进程调度。,低级调度,2018/9/14,第三章 处理机调度与死锁,29,进程调度的两种方式,非抢占式(Non-preemptive Mode)：分派程序一旦把处理机分配给某进程后便让它一直运行下去，直到进程完成或发生某事件而阻塞时，才把处理机分配给另一个进程。 抢占方式(Preemptive Mode)：当一个进程正在运行时，系统可以基于某种原则，剥夺已分配给它的处理机，将之分配给其它进程。 抢占原则：优先权原则、短作业（进程）优先原则、时间片原则。,2018/9/14,第三章 处理机调度与死锁

15、,30,WHAT：按什么原则分配CPU调度算法 WHEN：何时分配CPU调度的时机 HOW： 如何分配CPUCPU调度过程（进程的上下文切换）,进程调度要解决的问题,2018/9/14,第三章 处理机调度与死锁,31,进程调度的功能,1、记录系统中所有进程的执行情况作为进程调度的准备，进程管理模块必须将系统中各进程的执行情况和状态特征记录在各进程的PCB表中。并且将各进程的PCB表排成相应的队列并进行动态队列转接。 2、选择占有处理机的进程进程调度的主要功能是按照一定的策略选择一个处于就绪状态的进程，使其获得处理机执行。 3、进行进程上下文切换一个进程的执行是在其上下文中执行的。当正在执行的进

16、程由于某种原因要让出处理机时，系统要做进程上下文切换，以使另一个进程得以执行。,2018/9/14,第三章 处理机调度与死锁,32,一个进程运行完毕，或因某种错误而终止运行当一个进程在运行时变为等待状态（等待I/O）分时系统中时间片到在进程通信中，执行中的进程执行了某种原语操作（P操作，阻塞原语）在执行完系统调用，系统程序返回用户进程时，可认为系统进程执行完毕，从而可调度选择一新的用户进程执行。当有一个优先级更高的进程就绪（可抢占式）例：新创建一个进程；一个等待进程变成就绪,进程调度的时机,2018/9/14,第三章 处理机调度与死锁,33,处理机调度的层次,2018/9/14,第三章 处理机调度与死锁,34,调度队列模型,仅有进程调度的调度队列模型,主要适用于分时系统。,FIFO 队列,2018/9/14,第三章 处理机调度与死锁,35,具有高级和低级调度的调度队列模型适用于批处理操作系统,调度队列模型,优先权队列,多个阻塞队列,2018/9/14,第三章 处理机调度与死锁,36,调度队列模型,同时具有三级调度的调度队列模型,