《《操作系统实训（Linux）——习题解答、例题解析、实验指导》-王红-电子教案 第3章 处理机调度与死锁》由会员分享，可在线阅读，更多相关《《操作系统实训（Linux）——习题解答、例题解析、实验指导》-王红-电子教案 第3章 处理机调度与死锁（29页珍藏版）》请在金锄头文库上搜索。
1、1,第3章 处理机调度与死锁,本章介绍调度与死锁的概念及解决方法。主要介绍分级调度、作业调度、进程调度的过程、概念及算法。介绍了死锁问题的概念及产生死锁的必要条件、死锁的预防、避免和检测方法。,第 3章 处理机调度与死锁,1,21世纪高等院校规划教材,王 红 主 编 侯 刚 张凤云 杨德芳 张淑玉 副主编,中国水电水利出版社,3.1 基本知识结构图,第 3章 处理机调度与死锁,2,21世纪高等院校规划教材,操作系统原理与应用 (Linux),王 红 主 编 侯 刚 张凤云 杨德芳 张淑玉 副主编,中国水电水利出版社,第 3章 处理机调度与死锁,3,21世纪高等院校规划教材,操作系统原理与应用
2、(Linux),王 红 主 编 侯 刚 张凤云 杨德芳 张淑玉 副主编,中国水电水利出版社,1三级调度 一个批处理型作业，从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，可能要经历以下三级调度：即作业调度、对换和进程调度。 作业调度又称为高级调度或长调度，用于选择把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源。然后，再将新创建的进程排在就绪队列上，准备执行。一个作业从提交给计算机系统到执行结束退出系统，一般都要经历提交、后备、执行和完成等4个状态。 对换又称交换调度或中级调度，它是一种内存管理技术。当有作业或进程申请内存空间时，先将内存中暂时不用的信息写在
3、磁盘上，再将外存中需要的信息加载内存。该问题主要在第四章介绍。 进程调度又称为低级调度或微观调度。其主要任务是按照某种策略和算法，将处理机分配给一个处于就绪状态的进程。,第 3章 处理机调度与死锁,4,3.2 知识点 3.2.1 分级调度,21世纪高等院校规划教材,操作系统原理与应用 (Linux),王 红 主 编 侯 刚 张凤云 杨德芳 张淑玉 副主编,中国水电水利出版社,2作业和进程的关系 作业是用户向计算机提交任务的任务实体。进程则是计算机为了完成用户任务实体而设置的执行实体，是系统分配资源的基本单位。一个作业总是由一个或多个进程组成的。,第 3章 处理机调度与死锁,5,21世纪高等院校
4、规划教材,操作系统原理与应用 (Linux),王 红 主 编 侯 刚 张凤云 杨德芳 张淑玉 副主编,中国水电水利出版社,3.2.2 作业调度,1作业调度的功能 作业调度程序要从后备态队列中选择一个作业使它执行，并且在执行过程中对其进行管理。作业调度主要是完成作业从后备状态到执行状态的转换，以及从执行状态到完成状态的转换。 系统为每个作业建立一个作业控制表或作业控制块JCB，用以记录作业的有关信息。作业控制块中主要包括：作业类型、资源要求、作业的当前状态、资源使用情况、作业的优先级等。系统通过JCB而感知作业的存在。,第 3章 处理机调度与死锁,6,21世纪高等院校规划教材,王 红 主 编 侯
5、 刚 张凤云 杨德芳 张淑玉 副主编,中国水电水利出版社,第 3章 处理机调度与死锁,2调度算法的评价准则 面向用户的准则：周转时间短、响应时间快、截止时间有保证、优先权准则等。,1 进程调度的功能 进程调度的功能大致有：记录系统中所有进程的执行情况、从就绪态队列中选择一个进程、进行进程上下文的切换。 2进程调度的时机 引起进程调度的事件有：完成任务、进程等待资源、运行时间到、进入睡眠状态、发现核心态执行完成的标志以及优先级变化。,3.2.3 进程调度,8,第 3章 处理机调度与死锁,3进程上下文的切换 进程的上下文由正文段、数据段、硬件寄存器的内容以及有关的数据结构组成。进程上下文的切换主要
6、包括以下四个方面：决定是否要做及是否允许做上下文切换、保存当前执行进程的上下文、选择一个处于就绪态的进程、使被选中的进程执行。 4 Linux系统中进程调度发生的时机 Linux系统中进程调度发生的时机有：创建一个新的进程时、正在执行的进程申请外部资源得不到满足时、运行的进程时间片用完、进程从核心态返回到用户态时。,第 3章 处理机调度与死锁,9,3.2.4 调度算法,1先来先服务（FCFS）调度算法 2短作业调度算法（SJF）或短进程调度算法（SPF） 3高响应比优先调度算法 4优先级调度算法 5 轮转调度算法,第 3章 处理机调度与死锁,10,第 3章 处理机调度与死锁,11,3.2.5
7、Linux系统的调度算法 Linux系统提供了三种进程调度算法，即：普通进程的分时算法、实时进程的先进先出调度算法、基于优先级的轮转算法（动态优先级调度）。这三种算法可由用户通过宏定义来选择。,12,3.2.6 死锁问题 1 死锁的概念 2 产生死锁的原因及必要条件 3 解决死锁问题的基本方法,12,第 3章 处理机调度与死锁,3.2.8 利用银行家算法避免死锁 1 银行家算法中的数据结构 在银行家算法中用到的数据结构有：可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need等。其中，Need=Max-Allocation 2 银行家算法的实现,第
8、 3章 处理机调度与死锁,13,第 3章 处理机调度与死锁,14,3.2.9 死锁的检测与解除 1 死锁检测的时机 2 死锁的检测方法 3 死锁的解除,3.3 例题解析,3.3.1 单项选择题： 【例1】进程调度是指根据一定的调度算法，从_队列中挑选出一个的进程，分配给它CPU。 A阻塞 B就绪 C运行 D等待 【解答】B 【例2】作业调度程序从处于_状态的队列中先取适当的作业调入主存运行。 A运行 B提交 C完成 D后备 【解答】D,第 3章 处理机调度与死锁,15,第 3章 处理机调度与死锁,16,【例3】以下关于资源分配图与死锁关系说法中错误的是_。 A如果资源分配图中无环路，则系统中没
9、有死锁发生。 B如果资源分配图中有环路，且每个资源类中只有一个资源，则处于环路中的进程一定处于死锁状态。 C如果资源分配图中有环路，同时资源类中有多个资源，则未必出现死锁。 D如果资源分配图是不可化简的，且有环路，则系统中是否发生死锁，需进一步分析。 【解答】D 【例4】银行家算法在解决死锁问题中是用于_的。 A预防死锁 B避免死锁 C检测死锁 D解除死锁 【解答】B,【例5】死锁的产生有四个必要条件，在死锁的预防策略中，资源的有序分配策略可以破坏_条件。 A.互斥使用 B.占有且等待 C.不可抢占条件 D.环路等待条件 【解答】D 【例6】下列作业调度算法中， 具有最短的作业平均周转时间的是
10、_。 A先来先服务法 B短作业优先法 C优先数法 D时间片轮转法 【解答】B,第 3章 处理机调度与死锁,17,【例7】在多进程的并发系统中，肯定不会因竞争_而产生死锁。 A打印机 BCPU C磁盘 D 磁带机 【解答】B 【例8】在分时操作系统中，进程调度经常采用_算法。 A先来先服务 B最高优先权 C时间片轮转 D随机 【解答】C,第 3章 处理机调度与死锁,18,【例9】为多道程序提供的可共享资源不足时，可能出现死锁；不适当的_也可能产生死锁。 A进程优先权 B时间片大小 C进程的推进顺序 D分配队列优先权 【解答】C 【例10】为了系统中各部分资源得到均衡使用，以提高系统的效率，就必须
11、选择对资源需求不同的作业进行合理搭配。这项工作是由_完成的。 A作业调度 B中级调度 C进程调度 D内存调度 【解答】A,第 3章 处理机调度与死锁,19,3.3.2 填空题,【例1】作业从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，可能要经历三级调度，其中的中级调度指的是 。 【解答】内外存对换 【例2】不让死锁发生的策略可以分为静态和动态两种，死锁避免属于 ，死锁的预防属于 。 【解答】动态，静态 【例3】进程调度在采用优先级调度算法时，一个高优先级的进程占用处理机时可以采用 或 两种处理方式。 【解答】非抢占式，可抢占式 【例4】用户要求计算机处理的一个任务称为一个 。 【解
12、答】作业,第 3章 处理机调度与死锁,20,【例5】若要求当前运行进程总是优先级最高的进程，应选择（ ）进程调度算法。 【解答】可剥夺最高优先级算法。该算法总是将处理机分配给优先级最高的进程。 【例6】多级队列算法：允许对不同类型的作业使用不同的算法，最常用的是对前台队列使用 ，对后台成批队列采用 进行调度。 调度算法允许一个作业从一个队列移到另一个队列。 【解答】轮转法，先来先服务，多级反馈队列 【例7】作业调度从 中选择一道作业，为它分配资源，并为它创建 。 【解答】后备队列，进程,第 3章 处理机调度与死锁,21,【例8】在并发执行的一些进程中，如果能够找到一个进程推进的顺序，各进程按照
13、这个顺序执行，能够保证所有的进程在有限时间内得到需要的全部资源，则称系统处于 。 【解答】安全状态 【例9】解决死锁的方法分为 、 、 和 。 【解答】死锁预防，死锁避免，死锁检测，死锁解除,第 3章 处理机调度与死锁,22,3.3.3 综合题,【例1】判断正误： （1）作业一旦被作业调度选中，系统就给它分配CPU。 【解答】错误 （2）分时系统中，时间片越小越好。 【解答】错误。（3）银行家算法是预防死锁发生的方法之一。 【解答】错误。（4）交互式作业不存在作业调度问题。 【解答】正确。,第 3章 处理机调度与死锁,23,（5）优先权调度算法中，在考虑静态优先权时，一般计算进程的优先权高于磁
14、盘I/O进程的优先权。 【解答】错误。 （6）进程的调度算法有很多,如果选择不当,就会造成死锁。 【解答】错误。 （7）系统调用就是原语。 【解答】错误。 （8）所谓多道程序设计,即指每一刻可以有若干个程序在执行。 【解答】错误。,第 3章 处理机调度与死锁,24,【例2】何谓JCB，其作用是什么？它由谁在什么时候创建？它在什么时候撤消？JCB至少应包括哪些内容？ 【解答】略,第 3章 处理机调度与死锁,25,【例3】比较进程调度与作业调度的不同点。 【解答】略,第 3章 处理机调度与死锁,26,【例4】有5个批处理的作业（A、B、C、D和E）按先后顺序到达一个计算中心，但前后时差忽略不计。估计需运行时间分别为2、4、6、8、10分钟，它们的优先数分别为1、2、3、4、5（假设优先数越大，优先级越高）。对下面的各种调度算法，分别计算作业的平均周转时间。 （1）优先级调度算法； （2）时间片轮转（时间片为2分钟）； （3）FCFS（设作业到达顺序为C、D、B、E、A）； （4）短作业优先。,第 3章 处理机调度与死锁,27,第 3章 处理机调度与死锁,28,THE END,29,
