第三章 处理机调度与死锁

操作系统第三章处理机调度与死锁1第三章处理机调度与死锁3.1处理机的分级调度3.2作业调度3.3进程调度3.4死锁操作系统第三章处理机调度与死锁23.1处理机的分级调度处理机资源是计算机系统中最重要的资源，它的调度策略，常常表示操作系统的某种特征，其算法的优劣直接影响整个系统的性能。处理机调度需要解决三个问题：(1)处理机分配的策略，即需要确定处理机的调度算法；(2)什么时候分配处理机，即需要确定处理机的调度时机；(3)如何分配处理机，即需要给出处理机的调度过程。操作系统第三章处理机调度与死锁32）交换调度（中级调度）（均衡调度）：按照给定的原则实现进程在主存和外存交换区之间的换进换出，以解决内存紧张问题，特别是具有虚拟存储器的系统中。3）进程调度（低级调度）：按照某种策略从进程就绪队列中选择一个就绪进程，使其占有处理机运行。4）线程调度处理机调度可以分为4级：1）作业调度（高级调度）：按一定原则选择若干个后备作业调入主存，分配资源，并建立相应的进程，投入运行。当该作业执行完毕时，还负责回收资源。操作系统第三章处理机调度与死锁4§3.2作业调度一、作业、作业步、作业流(1)作业：是用户一次请求计算机系统为它完成任务所进行的工作总和。(2)作业步：作业加工工作中的一个相对独立的步骤称为作业步。对作业的处理一般有这样几个作业步：编辑（修改）、编译、连接、运行。(3)作业流：是按一定顺序组织好的一批作业。操作系统第三章处理机调度与死锁5作业步之间的关系：·每个作业步运行的结果产生下一个作业步所需要的文件。·一个作业步能否正确地执行，依赖于前一个作业步是否成功的完成。例如：user.cuser.objuser.exe编辑编译连接运行作业步之间的关系二、作业的类型根据计算机系统的作业处理方式不同，可以把作业分成两类：脱机作业（批处理作业）联机作业（交互式作业或终端型作业）。操作系统第三章处理机调度与死锁6三、作业的组织程序作业由三部分组成数据作业说明书（说明用户的控制意图）作业控制块（JCB）：为了管理和调度已进入系统的各个作业，系统设置的用于记录作业的基本情况的数据结构。作业控制块（JCB）的主要内容：(1)作业的基本情况用户名、作业名、作业的状态和使用的语言等。(2)作业的控制要求控制方式、类型、优先数、操作顺序和出错处理等。(3)作业的资源要求作业建立的时间、要求运行的时间、最迟完成的时间、需要的主存容量、外设的种类及数量和资源使用情况。操作系统第三章处理机调度与死锁7作业的输入作业的建立包括两个子过程作业控制块（JCB）的建立作业的输入方式:1.联机输入方式2.脱机输入方式(预输入方式)3.直接耦合方式4.SPOOLING系统5.网络输入方式JCB（作业控制块）的建立:系统在作业输入到外存，进入后备状态时为作业建立JCB，它是作业存在的惟一标志.四、作业的建立操作系统第三章处理机调度与死锁8一个作业从提交给计算机系统到执行结束退出系统，一般都要经历4个状态：提交、后备（收容）、执行和完成。1）提交状态：通过终端设备向计算机的磁盘输入作业信息时所处的状态。2）后备状态：作业的全部信息已输入到磁盘的一个专用区(输入井)中等待作业调度时所处的状态。3）执行状态：在后备作业队列中的作业一旦被作业调度程序选中，为它分配了必要的资源，并且建立了进程,开始处理时所处的状态。4）完成状态：作业完成其全部任务后，进程撤消,做善后处理时的作业状态称为完成状态。五、作业的状态操作系统第三章处理机调度与死锁9一、作业的状态及其转换作业的状态及其转换执行进程调度内存线程调度运行等待就绪外存就绪等待提交后备完成作业输入作业调度交换调度作业调度执行操作系统第三章处理机调度与死锁10二、作业调度的功能作业调度的主要任务：完成作业从后备状态到运行状态和从运行状态到完成状态的转变。1）记录系统中各作业的状况。作业调度程序应包括以下功能：作业调度程序为了挑选一个作业投入运行，并且在运行中对它实施管理，它必须掌握该作业进入系统时的有关情况并随时记录该作业在各运行阶段的变化。为此，系统为每一个已进入系统的作业分配一个作业控制块JCB(JobContrlblock)。每个作业的JCB在该作业进入后备状态时由系统建立．在该作业退出系统时由系统撤消。每个作业在各阶段的情况(包括分配的资源和作业状态等)都记录在它的JCB中。操作系统第三章处理机调度与死锁112)按一定的调度算法，从后备作业中挑选出一个或几个作业运行。系统中处于后备状态的作业较多，几十个甚至几百个，处于运行状态的作业只是有限的几个如最多不超过4个或8个。作业调度程序的一个重要职能就是在适当的时候按一定的调度原则从后备作业中挑选出若干个作业投入运行。3)为被选中的作业做好执行前的准备工作。为该作业建立相应的进程，并且为这些进程提供所需的资源，如内存和外部设备等。4)在作业执行结束时做善后处理工作。输出如运行时间、作业执行情况等必要信息，回收该作业所占用的全部资源，撤消与该作业有关的全部进程和该作业的作业控制块。操作系统第三章处理机调度与死锁12注：1）处理机的分配工作由进程调度程序完成。内存的分配和释放工作由存贮管理程序完成。外部设备的分配和释放工作由设备管理程序完成。三、作业控制块2）作业调度程序只保证被选中的作业获得使用处理机的资格，把一个作业的内存、外设要求转给相应的管理程序。作业控制块JCB是作业存在的标志，记录与该作业有关的信息。操作系统第三章处理机调度与死锁13作业名资源要求估计执行时间最迟完成时间要求的主存量要求外设的类型及台数要求文件量和输出量资源使用情况进入系统时间开始执行时间已执行时间主存地址外设台号类型控制方式作业类型优先级状态作业控制块联机和脱机操作系统第三章处理机调度与死锁14四、作业调度目标与性能衡量（1）公平性（2）均衡使用资源（3）较高的吞吐量（4）较快的响应时间1.调度目标操作系统第三章处理机调度与死锁15（1）周转时间Ti=完成时刻Tci－提交时刻Tsi=等待时间Twi+运行时间Tri对于进入系统的n个作业而言，平均周转时间T为i＝1用于衡量不同调度算法对同一作业流的调度性能:平均周转时间越小，该作业调度算法的性能越好。2.调度性能衡量指标操作系统第三章处理机调度与死锁16(2)带权周转时间Wi=Ti／Tri它能说明作业i的相对等待时间。n平均带权周转时间W=（ΣWi）／ni=1用于衡量同一调度算法对不同作业流的调度性能：平均带权周转时间越小，作业调度算法对该作业流的调度性能越好。对于批处理系统，主要依据平均周转时间和平均带权周转时间来作为衡量调度算法性能的指标；而对于分时系统和实时系统，外加平均响应时间作为衡量调度算法性能的指标。操作系统第三章处理机调度与死锁17五、作业调度算法按作业来到的先后次序进行调度。这种算法优先考虑在系统中等待时间最长的作业，而不管它要求运行时间的长短。优点：容易实现；缺点：没有考虑各个作业运行特征和资源要求的差异，系统效率较低。1.先来先服务调度算法（FCFS）操作系统第三章处理机调度与死锁18例：先来先服务调度算法（单位：小时，并以十进制计）作业提交时间运行时间开始时间完成时间周转时间带权周转时间18.002.008.0010.002.00128.500.5010.0010.502.00439.000.1010.5010.601.601649.500.2010.6010.801.306.5平均周转时间T＝1.725平均带权周转时间W＝6.875操作系统第三章处理机调度与死锁192.短作业优先调度算法（SJF）此算法总是优先调度要求运行时间最短的作业。优点：易于实现，效率比较高。缺点：只照顾短作业而不考虑长作业的利益。如果系统不断地接受新的短作业。则有可能较长作业长时间等待而不能运行。操作系统第三章处理机调度与死锁20例：短作业优先调度算法（单位：小时，并以十进制计）作业提交时间运行时间开始时间完成时间周转时间带权周转时间18.002.008.0010.002.00128.500.5010.3010.802.304.639.000.1010.0010.101.101149.500.2010.1010.300.804平均周转时间T＝1.55平均带权周转时间W＝5.15操作系统第三章处理机调度与死锁213.响应比高者优先调度算法响应比是指作业的响应时间与作业估计运行时间的比值。执行时间响应时间响应比＝选择原则是优先选取响应比值最大的作业。即兼顾等待时间长和运行时间短的作业，它是FCFS和SJF算法的结合。响应比＝1＋作业等待时间/执行时间操作系统第三章处理机调度与死锁22作业提交时间运行时间开始时间完成时间周转时间带权周转时间18.002.008.0010.002.00128.500.5010.1010.602.104.239.000.1010.0010.101.101149.500.2010.6010.801.306.5例：响应比高者优先调度算法（单位：小时，并以十进制计)平均周转时间T＝1.625，平均带权周转时间W＝5.675响应比＝1＋作业等待时间/执行时间例如：当作业3结束时，Rp2=1＋作业等待时间/可执行时间=1+(10.10-8.50)/0.5=1+3.2Rp4=1＋作业等待时间/可执行时间=1+(10.10-9.50)/0.2=1+3操作系统第三章处理机调度与死锁23这种算法是根据确定的优先数来选取作业，每次总是选择优先级最高的作业。4.最高优先级优先调度算法规定用户作业优先数的方法:1）由用户自己提出作业的优先数。有的用户为了自己的作业尽快被系统选中就设法提高自己作业的优先数，这时系统可以规定优先数越高则需付出的计算机使用费就越多，以作限制。2）由系统综合有关因素来确定用户作业的优先数。例如，根据作业的缓急程度、作业计算时间的长短、等待时间的多少、资源申请情况等来确定优先数。确定优先数时，各因素的比例应根据系统设计目标来分析这些因素在系统中的地位而决定。操作系统第三章处理机调度与死锁243.3进程调度进程调度：就是系统按照某种算法把CPU动态地分配给某一就绪进程。进程调度工作是通过进程调度程序来完成的。一、调度/分派结构调度程序：将进程插入就绪队列，按一定原则保持队列结构；分派程序：将进程从就绪队列中移出，建立它执行的机器状态。进程切换：把一个进程让出处理机，由另一个进程占用处理机的调度过程称为“进程切换”。分派程序首先将正在执行的进程的CPU现场信息保存在该进程PCB的现场保护区中，再从被调度选中的进程PCB的现场保护区中取出它的CPU现场信息恢复。CPU现场信息由程序状态寄存器、程序计数器以及若干通用寄存器的内容组成。操作系统第三章处理机调度与死锁251.记录系统中所有进程的执行情况。二、进程调度功能记录系统中所有进程的有关情况，对进程控制块PCB的内容作相应的登记、修改，记录进程的状态特征。2.按照一定调度策略选择一个占有处理机的就绪进程。在处理机空闲时根据一定的原则选择一个进程去运行，同时确定获得处理机的时间。3.实施处理机的分配和回收(进行进程上下文切换)。回收:正在运行的进程由于某种原因让出处理机，该进程的状态改为“阻塞”，插入到相应队列中，保留该进程的CPU现场。分配:根据调度原则选择进程去运行，把选中进程从就绪队列中移出,改状态为“运行”，把CPU控制权交给被选中的进程，将选中进程的有关PCB现场信息，分别送到相应的寄存器中。操作系统第三章处理机调度与死锁26三、进程调度时机1）正在执行的进程完成其任务而运行完毕。2）执行中的进程由于请求某个事件的发生，比如I/O请求，等待所需要的信号、信件的到来等而自己调用阻塞原语将自己阻塞起来，进入相应的等待队列。3）在分时系统中，当进程使用完规定的时间片。4）在采用可抢占调度方式的系统中，当具有更高优先级的进程要求使用处理机。操作系统第三章处理机调度与死锁27四、进程调度方式1.非抢先调度方式这种方式是当有重要或紧迫的进程进入就绪队列时，仍然让正在执行的进程继续