搜索
第三章处理机调度与死锁第三章处理机调度与死锁3.1处理机调度的层次3.2调度队列模型和调度算法的目标3.3调度算法3.4实时调度（不讲）3.5死锁概述3.6预防死锁3.7避免死锁3.8死锁的检测与解除第三章处理机调度与死锁（1）作业•作业是一个比程序更为广泛的概念，它不仅包含了通常的程序和数据，而且还应配有一份作业说明书，系统根据该说明书来对程序的运行进行控制。•在批处理系统中，是以作业为基本单位从外存调入内存的。批处理系统作业处理作业的基本概念第三章处理机调度与死锁（2）作业步在作业运行期间，每个作业都必须经过若干个相对独立，又相互关联的顺序加工步骤才能得到结果，把其中的每一个加工步骤称为一个作业步。典型的作业控制过程：“编译”、“链接装配”、“运行”批处理系统作业处理作业的基本概念第三章处理机调度与死锁典型的作业步编译连接装配运行目标程序段目标程序源程序输入数据子程序库函数动态库函数计算结果作业的基本概念第三章处理机调度与死锁（3）作业流•若干个作业进入系统后，被依次存放在外存上，这便形成了输入作业流；•在操作系统的控制下，逐个作业进行处理，于是便形成了处理作业流。批处理系统作业处理作业的基本概念第三章处理机调度与死锁（1）作业控制语言作业说明书是用户用于描述批处理作业处理过程控制意图的一种特殊程序。书写作业说明书的语言称为作业控制语言（JCL）（2）作业控制语言的类别包括：I/O命令、编译命令、操作命令以及条件命令等（3）作业说明书表达用户对作业的控制意图内容：作业的基本描述作业控制描述资源要求描述批处理作业控制语言与作业说明书第三章处理机调度与死锁（1）作业控制块（JCB：JobControlBlock）是批处理作业在系统中存在的标志，保存有系统对于作业进行管理和调度所需的全部信息，位于磁盘区域中。作业控制块JCB和作业：一一对应关系（2）作业控制块的内容作业控制块中所包含的信息数量及内容因系统而异作业控制块与作业表作业标识用户名称用户帐号调度信息资源需求作业状态作业类型输入井地址输出井地址进入系统时间开始处理时间作业完成时间作业退出时间资源使用情况第三章处理机调度与死锁（3）作业控制块的建立当作业开始由输入设备向磁盘的输入井传输时，作业注册程序为其建立一个作业控制块，进行初始化，初始化的大部分信息取自作业说明书。（4）作业控制块的使用需要访问作业控制块的程序：作业注册程序作业调度程序作业控制程序系统输出程序终止作业程序作业控制块与作业表第三章处理机调度与死锁（5）作业控制块的撤消作业执行完成后，其作业控制块由系统撤消作业控制块被撤消后其作业也不复存在（6）作业表•每个作业有个作业控制块•所有作业JCB构成一个作业表•作业表存放在外存固定区域中，长度是固定的•限制了系统所能同时容纳的作业数量JCB1JCB2……JCBi……JCBn作业表作业控制块与作业表第三章处理机调度与死锁•一个作业从进入系统到运行结束，需要经历三个阶段，处于三种状态：“收容”“后备”“运行”“运行”“完成”“完成”批处理作业的状态及转换第三章处理机调度与死锁作业和进程的状态转换图数据完成状态后备状态运行状态作业控制进程…输入设备数据源程序输出设备作业说明书输入井运行等待就绪输出井输入程序输出程序作业调度进程调度批处理作业的状态及转换第三章处理机调度与死锁分时系统中用户控制作业的执行大致有四个阶段：终端的连接用户登录控制作业执行用户退出分时系统的作业管理第三章处理机调度与死锁(1)终端的连接必须使终端设备与计算机系统在线路上接通近程终端是直接与计算机系统连接的，当终端设备加电后，终端就与计算机系统在线路上接通了远程终端通过租用专线或交换线接到计算机系统，在终端加电后用户还需通过电话拨号进行呼叫，直到接通分时系统的作业管理第三章处理机调度与死锁(2)用户登录用户必须向系统登录用户首先输入“登录”命令（LOGON）命令系统会向询问用户名、作业名、口令和资源需求等经过识别用户、核对口令，系统在终端上显示“已登录”和进入系统的时间等信息若口令不对或资源暂时不能满足时，则系统在终端上显示“登录不成功”并给出登录失败的原因用户的登录过程可看作是对终端作业的作业调度分时系统的作业管理第三章处理机调度与死锁(3)控制作业执行登录成功的终端用户可从终端上输入作业的程序和数据使用系统提供的命令语言或会话语句控制作业执行每输入一命令或一会话语句后，由系统解释执行且在终端上显示执行成功或问题由用户决定下一步命令或会话直到作业完成分时系统的作业管理第三章处理机调度与死锁(4)用户退出用户输入“退出”命令（LOGOFF命令）请求退出系统系统接收命令后就收回该用户所占的资源让其退出同时在终端上显示“退出时间”或“使用系统时间”分时系统的作业管理第三章处理机调度与死锁•处理机调度即对处理机进行分配。•批处理系统中，一个作业，从进入系统并驻留在外存的后备队列上开始，直到作业运行完成，可能要经历三级处理机调度：高级调度中级调度低级调度3.1处理机调度的层次第三章处理机调度与死锁1、高级调度(High-LevelScheduling)•又称为作业调度、长程调度、接纳调度。•任务：（1）根据作业控制块中的信息，审查系统中的资源能否满足用户作业对资源的需求。（2）按照一定的算法，从外存的后备队列中选取某些作业调入内存，并为它们创建进程、分配必要的资源。然后再将新创建的进程插入就绪队列，准备执行。•两个决定：（1）接纳多少个作业取决于多道程序度（2）接纳哪些作业取决于所采用的调度算法第三章处理机调度与死锁2、低级调度(Low-LevelScheduling)•又称为进程调度、短程调度。•主要功能：(1)保存当前进程的处理机的现场信息。(2)按某种算法从就绪队列中选取一个进程，把它的状态改为运行状态，并准备把处理机分配给它。(3)把处理器分配给进程。由分派程序把处理器分配给被选中的进程。为选中的进程恢复处理机现场，把处理器的控制权交给该进程。第三章处理机调度与死锁(1)排队器排队器把系统中的所有就绪进程按照一定策略排成一个或多个队列。(2)分派器(分派程序)。分派器把由进程调度程序所选定的进程，从就绪队列中取出，然后进行上下文切换，将处理机分配给它(3)上下文切换器第一对：当前进程上下文－＞分派程序上下文第二对：分派程序上下文－＞新选进程上下文进程调度中的三个基本机制第三章处理机调度与死锁进程调度方式1．非抢占方式（非剥夺式调度）•原理：一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞时，才再把处理机分配给其他进程，决不允许某进程抢占已经分配出去的处理机。•引起进程调度的原因：（1）正在执行的进程执行完毕或因发生某事件而无法再继续运行；（2）正在执行的进程提出I/O请求而暂停执行；（3）进程通信或同步过程中，执行了某种原语操作（Block）。•特点：实现简单，系统开销较小，但不能反映各个进程重要、紧急程度的差异，难以满足紧急任务的要求。第三章处理机调度与死锁进程调度方式2．抢占方式（剥夺式调度）•原理：允许调度程序根据某种原则，暂停某个正在执行的进程，将已分配给该进程的处理机重新分配给另一进程。•抢占原则：（1）优先权原则（2）短进程优先原则（3）时间片原则•特点：反映了进程的优先级特征，系统能及时处理紧急事件，但可能导致较大的系统开销，算法也相对复杂一些。第三章处理机调度与死锁3、中级调度(Intermediate-LevelScheduling)•又称为中程调度、内存调度。•引入了挂起状态的操作系统中有中级调度。•中级调度：用来决定把外存上的哪些又具备运行条件的静止就绪进程，重新调入内存，并修改其状态为活动就绪状态，挂在活动就绪队列上等待进程调度。第三章处理机调度与死锁3.2调度队列模型和调度算法的目标3.2.1调度队列模型三种类型的调度队列模型：一．仅有进程调度的调度队列模型二．具有高级调度和低级调度的调度队列模型三．同时具有三级调度的调度队列模型第三章处理机调度与死锁一．仅有进程调度的调度队列模型－－分时系统•在分时系统中，用户键入的命令和数据，都直接送入内存。对于命令，由OS为之建立的一个进程。•仅有进程调度的调度队列模型：就绪队列阻塞队列进程调度CPU进程完成等待事件交互用户事件出现时间片完第三章处理机调度与死锁二．具有高级调度和低级调度的调度队列模型－－批处理系统就绪队列进程调度CPU进程完成等待事件1作业调度事件1出现时间片完等待事件2事件2出现……等待事件n事件n出现后备队列……第三章处理机调度与死锁三．同时具有三级调度的调度队列模型就绪队列进程调度CPU就绪，挂起队列中级调度阻塞，挂起队列阻塞队列等待事件进程完成时间片完作业调度交互型作业后备队列批量作业挂起事件出现事件出现第三章处理机调度与死锁3.2.2处理机调度算法的目标一、共同目标•1．资源利用率•2．公平性•3．平衡性•4．策略强制执行第三章处理机调度与死锁3.2.2处理机调度算法的目标二．批处理系统的目标1．平均周转时间短•所谓周转时间，是指从作业提交给系统开始，到作业完成为止的这段时间间隔。它包括：（1）作业在外存后备队列上等待调度的时间；（2）进程在就绪队列上等待进程调度的时间；（3）进程在CPU上执行的时间；（4）进程等待I/O操作完成的时间。第三章处理机调度与死锁•平均周转时间可描述为：T=(∑Ti)/n;(i=1,2,......,n)•作业的周转时间T与系统为它提供的实际服务时间Ts之比，即W=T/Ts称为带权周转时间。•平均带权周转时间可表示为：W=(∑(Ti/Tsi))/n;(i=1,2,......,n)3.2.2处理机调度算法的目标二．批处理系统的目标第三章处理机调度与死锁3.2.2处理机调度算法的目标二．批处理系统的目标2．系统吞吐量高3．处理机利用率高第三章处理机调度与死锁3.2.2处理机调度算法的目标三．分时系统的目标1．响应时间快是从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间，或说直到在屏幕上显示出结果为止的一段时间间隔。它包括：(1）从键盘输入的请求信息传送到处理机的时间；(2）处理机对请求信息进行处理的时间；(3）将所形成的响应回送到终端显示器的时间。2．均衡性是指系统响应时间的快慢应与用户所请求服务的复杂性相适应。第三章处理机调度与死锁3.2.2处理机调度算法的目标四．实时系统的目标1.截止时间的保证所谓截止时间，是指某任务必须开始执行的最迟时间，或必须完成的最迟时间。2.可预测性第三章处理机调度与死锁3.3调度算法•作业调度的职责就是根据一定的算法，从多个在外存上处于后备队列中的作业中选择其中一些调入内存，并为它们创建进程、分配必要的资源，然后，再将新创建的进程排在就绪队列上，准备执行。•进程调度的职责就是根据一定的算法，从多个就绪进程中选择其中之一来占用CPU。从宏观上讲，进程调度把一个物理上的CPU变为多个逻辑上的CPU。第三章处理机调度与死锁3.3调度算法•先来先服务(FirstComeFirstServed,FCFS)•短作业(进程)优先(ShortestJobFirst,SJF或ShortestProcessFirst,SPF)•时间片轮转调度算法(RoundRobin,RR)•优先级调度算法(Priority-SchedulingAlgorithm,PSA)•高响应比优先调度算法(HighestResponseRatioNext,HRRF)•多队列调度算法•多级反馈队列调度算法第三章处理机调度与死锁先来先服务调度算法（FCFS）•FCFS调度算法最简单，既适合于作业调度，又适合于进程调度。•作业调度：每次调度是从后备作业队列中，选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放人就绪队列。•进程调度：每次调度是从就绪队列中，选择一个最先进入该队列的进程，把处理机分配给它，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后，才放弃处理机。第三章处理机调度与死锁先来先