第3章 处理机调度与死锁

1第3章处理机调度与死锁本章介绍调度与死锁的概念及解决方法。主要介绍分级调度、作业调度、进程调度的过程、概念及算法。介绍了死锁问题的概念及产生死锁的必要条件、死锁的预防、避免和检测方法。第3章处理机调度与死锁121世纪高等院校规划教材王红主编侯刚张凤云杨德芳张淑玉副主编中国水电水利出版社3.1基本知识结构图第3章处理机调度与死锁221世纪高等院校规划教材操作系统原理与应用(Linux)王红主编侯刚张凤云杨德芳张淑玉副主编中国水电水利出版社第3章处理机调度与死锁3调度与死锁分级调度作业调度进程调度进程上下文的切换死锁作业调度进程调度对换作业调度的概念及功能进程调度的时机Linux系统的进程调度先来先服务高响应比优先短作业（进程）优先优先级轮转法系列调度算法的评价准则Linux系统的进程调度算法调度算法进程调度的功能和时机死锁的概念死锁的原因及必要条件解决死锁问题的方法预防死锁的方法利用银行家算法避免死锁死锁的检测死锁的预防与避免死锁的检测与解除死锁的解除图3-1调度与死锁基本知识结构图21世纪高等院校规划教材操作系统原理与应用(Linux)王红主编侯刚张凤云杨德芳张淑玉副主编中国水电水利出版社1．三级调度作业调度、对换和进程调度。作业调度用于选择把外存上处于后备队列中的哪些作业调入内存，并为它们创建进程、分配必要的资源。然后，再将新创建的进程排在就绪队列上，准备执行。对换又称交换调度或中级调度，它是一种内存管理技术。当有作业或进程申请内存空间时，先将内存中暂时不用的信息写在磁盘上，再将外存中需要的信息加载内存。进程调度又称为低级调度或微观调度。其主要任务是按照某种策略和算法，将处理机分配给一个处于就绪状态的进程。第3章处理机调度与死锁43.2知识点3.2.1分级调度21世纪高等院校规划教材操作系统原理与应用(Linux)王红主编侯刚张凤云杨德芳张淑玉副主编中国水电水利出版社2．作业和进程的关系作业是用户向计算机提交任务的任务实体。进程则是计算机为了完成用户任务实体而设置的执行实体，是系统分配资源的基本单位。一个作业总是由一个或多个进程组成的。第3章处理机调度与死锁521世纪高等院校规划教材操作系统原理与应用(Linux)王红主编侯刚张凤云杨德芳张淑玉副主编中国水电水利出版社3.2.2作业调度1．作业调度的功能作业调度程序要从后备态队列中选择一个作业使它执行.第3章处理机调度与死锁61．进程调度的功能进程调度的功能大致有：记录系统中所有进程的执行情况、从就绪态队列中选择一个进程、进行进程上下文的切换。2．进程调度的时机引起进程调度的事件有：完成任务、进程等待资源、运行时间到、进入睡眠状态、发现核心态执行完成的标志以及优先级变化。3.2.3进程调度7第3章处理机调度与死锁3．进程上下文的切换进程上下文的切换主要包括以下四个方面：决定是否要做及是否允许做上下文切换、保存当前执行进程的上下文、选择一个处于就绪态的进程、使被选中的进程执行。4．Linux系统中进程调度发生的时机Linux系统中进程调度发生的时机有：创建一个新的进程时、正在执行的进程申请外部资源得不到满足时、运行的进程时间片用完、进程从核心态返回到用户态时。第3章处理机调度与死锁83.2.4调度算法1．先来先服务（FCFS）调度算法2．短作业调度算法（SJF）或短进程调度算法（SPF）3．高响应比优先调度算法4．优先级调度算法5．轮转调度算法第3章处理机调度与死锁9第3章处理机调度与死锁103.2.5Linux系统的调度算法Linux系统提供了三种进程调度算法，即：普通进程的分时算法、实时进程的先进先出调度算法、基于优先级的轮转算法（动态优先级调度）。这三种算法可由用户通过宏定义来选择。113.2.6死锁问题1．死锁的概念2．产生死锁的原因及必要条件3．解决死锁问题的基本方法11第3章处理机调度与死锁3.2.8利用银行家算法避免死锁1．银行家算法中的数据结构在银行家算法中用到的数据结构有：可利用资源向量Available、最大需求矩阵Max、分配矩阵Allocation、需求矩阵Need等。其中，Need=Max-Allocation2．银行家算法的实现第3章处理机调度与死锁12第3章处理机调度与死锁133.2.9死锁的检测与解除1．死锁检测的时机2．死锁的检测方法3．死锁的解除3.3.1单项选择题：【例1】进程调度是指根据一定的调度算法，从_____队列中挑选出一个的进程，分配给它CPU。A．阻塞B．就绪C．运行D．等待【解答】B【例2】作业调度程序从处于________状态的队列中先取适当的作业调入主存运行。A．运行B．提交C．完成D．后备【解答】D第3章处理机调度与死锁14第3章处理机调度与死锁15【例3】以下关于资源分配图与死锁关系说法中错误的是________。A．如果资源分配图中无环路，则系统中没有死锁发生。B．如果资源分配图中有环路，且每个资源类中只有一个资源，则处于环路中的进程一定处于死锁状态。C．如果资源分配图中有环路，同时资源类中有多个资源，则未必出现死锁。D．如果资源分配图是不可化简的，且有环路，则系统中是否发生死锁，需进一步分析。【解答】D【例4】银行家算法在解决死锁问题中是用于________的。A．预防死锁B．避免死锁C．检测死锁D．解除死锁【解答】B【例5】死锁的产生有四个必要条件，在死锁的预防策略中，资源的有序分配策略可以破坏________条件。A.互斥使用B.占有且等待C.不可抢占条件D.环路等待条件【解答】D第3章处理机调度与死锁16【例7】在多进程的并发系统中，肯定不会因竞争________而产生死锁。A．打印机B．CPUC．磁盘D．磁带机【解答】B【例8】在分时操作系统中，进程调度经常采用_______算法。A．先来先服务B．最高优先权C．时间片轮转D．随机【解答】C第3章处理机调度与死锁17【例9】为多道程序提供的可共享资源不足时，可能出现死锁；不适当的________也可能产生死锁。A．进程优先权B．时间片大小C．进程的推进顺序D．分配队列优先权【解答】C第3章处理机调度与死锁183.3.2填空题【例1】作业从进入系统并驻留在外存的后备队列上开始，直至作业运行完毕，可能要经历三级调度，其中的中级调度指的是对换。【解答】内外存对换【例2】不让死锁发生的策略可以分为静态和动态两种，死锁避免属于动态，死锁的预防属于静态。【解答】动态，静态【例3】进程调度在采用优先级调度算法时，一个高优先级的进程占用处理机时可以采用抢占式或非抢占式两种处理方式。【解答】非抢占式，可抢占式第3章处理机调度与死锁19【例5】若要求当前运行进程总是优先级最高的进程，应选择（抢占式）进程调度算法。【解答】可剥夺最高优先级算法。该算法总是将处理机分配给优先级最高的进程。【例7】作业调度从后备队列中选择一道作业，为它分配资源，并为它创建进程。【解答】后备队列，进程第3章处理机调度与死锁20【例8】在并发执行的一些进程中，如果能够找到一个进程推进的顺序，各进程按照这个顺序执行，能够保证所有的进程在有限时间内得到需要的全部资源，则称系统处于安全状态。【解答】安全状态【例9】解决死锁的方法分为死锁预防、死锁避免、死锁检测和死锁解除。【解答】死锁预防，死锁避免，死锁检测，死锁解除第3章处理机调度与死锁213.3.3综合题【例1】判断正误：（1）作业一旦被作业调度选中，系统就给它分配CPU。【解答】错误（2）分时系统中，时间片越小越好。【解答】错误。（3）银行家算法是预防死锁发生的方法之一。【解答】错误。（4）交互式作业不存在作业调度问题。【解答】正确。第3章处理机调度与死锁22（5）优先权调度算法中，在考虑静态优先权时，一般计算进程的优先权高于磁盘I/O进程的优先权。【解答】错误。（6）进程的调度算法有很多,如果选择不当,就会造成死锁。【解答】错误。（7）系统调用就是原语。【解答】错误。（8）所谓多道程序设计,即指每一刻可以有若干个程序在执行。【解答】错误。第3章处理机调度与死锁23第3章处理机调度与死锁24