《2022年操作系统》由会员分享,可在线阅读,更多相关《2022年操作系统(20页珍藏版)》请在金锄头文库上搜索。
1、4.2 例题解析63 第4章调度与死锁4.2 例题解析例 4.2.1 当前运行的进程() ,将引发系统进行进程调度。A.执行了一条转移指令B.要求增加主存空间,经系统调用银行家算法进行测算认为是安全的C.执行了一条I/O 指令D.执行程序期间发生了I/O 完成中断解 本题考核进程调度的时机,相关的概念有:(1) 进程执行转移指令表示CPU将转到一个新程序段去,并不是转到一个新进程,因而不会重新分配CPU。(2) 当前进程提出主存请求时,若系统认为分配是安全的,则可以立即使进程的请求得到满足,不会因而造成进程阻塞。因此不会分配CPU。(3) 当前进程执行了I/O 指令,提出了输入输出请求。由于I
2、/O 是低速的,因此不能让CPU 等待 I/O 完成。因此需要阻塞当前进程,重新分配 CPU。(4) 当前进程运行程序期间发生了I/O 完成中断,说明有一个处于阻塞队列上的进程,正等待此I/O 事件的出现。因此可在中断处理程序中查出等待的进程,将它唤醒。然后再返回到当前进程来执行。只要恢复当前进程的现场信息就可以了,不会重新分配CPU。正确答案应为C。例 4.2.2分时系统中的当前运行进程连续获得了两个时间片,原因可能是() 。A该进程的优先级最高B就绪队列为空C该进程最早进入就绪队列D该进程是一个短进程解(1) 在分时系统中,诸多进程以轮流方式分享CPU,一般不考虑进程的优先级。(2) 当前
3、进程运行完一个时间片后回到就绪队列,如果此刻就绪队列名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 20 页 - - - - - - - - - 第 4 章调度与死锁64 为空队列,那么下一个时间片仍然由该进程使用CPU。(3) 在分时系统中,诸多进程轮流地使用CPU,并不考虑进程进入就绪队列的时间,也不登记进程进入就绪队列的时间。(4) 分时系统中诸多进程轮流使用CPU 不考虑进程的长短,也不登记进程预估将运行多长时间。正确答案应为B。例 4.2.3有三个作业A(到达时
4、间8:50 ,执行时间1.5小时) 、B(到达时间9:00 ,执行时间0.4 小时)、C(到达时间9:30 ,执行时间1小时)。当作业全部到达后,单道批处理系统按照响应比高者优先算法进行调度,则作业被选中的次序是() 。A (ABC )B (BAC )C (BCA )D (CBA )E (CAB )F (ACB )解 本题考核进程调度问题。作业运行情况见下表:进程到达时间运行长度开始时间结束时间A 8:50 1.5 9:30 11:00 B 9:00 0.4 11:00 11:24 C 9:30 1 11:24 12:24 当作业全部到达后,也就是9:30,系统开始调度。此刻各作业的等待时间是
5、, A 为 40 分钟( 0.67 小时)、B 为 0.5 小时、 C 为 0 小时。其响应比分别为:A=1+0.67/1.5=1.4 B=1+0.5/0.4=1.25 C=1+0/1=1 系统首先选A 运行,至 11:00 运行结束。各作业的等待时间是,B 为2 小时, C 为 1.5 小时。其响应比分别修改为:B=1+2/0.4=6 C=1+1.5/1=2.5 系统再选B 运行,至11:24 运行结束。最后选择C 运行至12:24 结束。因此,本题的正确答案应当是A。例 4.2.4 有三个进程P1、P2 和 P3 并发工作。进程P1 需要资源S3和 S1;进程 P2 需用资源S1 和 S2
6、;进程 P3 需用资源S2 和 S3,回答:(1)若对资源分配不加限制,会发生什么情况?为什么?( 2)为保证进程正确地工作,应采用怎样的资源分配策略?为什么?解名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 20 页 - - - - - - - - - 4.2 例题解析65 (1) 若对进程间的资源分配不加限制,可能会发生死锁,因为这样的分配可能导致进程间的“循环等待”,并且这种状态将永远持续下去。进程 P1、P2 和 P3 分别获得资源S3、S1 和 S2,后再继续申
7、请资源时都要等待。进程和资源会形成如下环路:图 4.3 进程资源分配图(2) 为保证系统处于安全状态,应采用下面列举3 种资源分配策略:1)采用静态分配: 由于执行前已获得所需的全部资源,故不会出现占有资源又等待的资源的现象(或不会出现循环等待资源现象)。2)采用资源按序分配,避免出现循环等待资源的现象。3)采用银行家算法进行分配资源前的检测。例 4.2.5进程调度又称为低级调度,其主要功能是( )。A.选择一个作业调入内存B.选择一个主存中的进程调出到外存C.选择一个外存中的进程调入到主存D.将一个就绪的进程投入运行解 本题考核进程调度的基本功能,相关概念有:(1) 选择一个作业调入内存是批
8、处理系统的作业调度所实现的功能。(2) 选择一个主存中的进程调出到外存是进程换出的功能。(3) 选择一个外存中的进程调入到主存是进程的换入功能,是中级调度的组成部分。(4) 将进程投入运行是进程调度的功能。本题的正确答案应为D。例4.2.6若 进程P 一旦 被唤醒就能够投入运行 ,系统可能为( )。A.在分时系统中,进程P的优先级最高B.抢占调度方式,就绪队列上的所有进程的优先级皆比P的低C.就绪队列为空队列D.抢占调度方式,P的优先级高于当前运行的进程解 本题考核一个进程被调度的条件,相关概念有:(1) 在分时系统中,进程调度是按照轮转方式进行的。系统并不登记名师资料总结 - - -精品资料
9、欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 20 页 - - - - - - - - - 第 4 章调度与死锁66 进程的优先级,也就是说与P 的优先级高低无关。(2) 在抢占调度方式中,P 的优先级高于就绪队列上的所有进程,但不一定高于当前的运行进程,所以也不一定能立即运行。(3) 无论哪种调度方式,若就绪队列为空队列,P 被唤醒并插入后都会成为该队列的唯一进程。但这并不能说P 可以立即获得处理机。只有当前运行的进程释放了CPU,且就绪队列无其他进程时,P 才可以立即使用 CPU。(4) 在抢占式
10、调度中,一个的进程P 到来,若P 的优先级高于当前进程时,可以抢占CPU,立即投入运行。本题的正确答案应为D。例 4.2.7 有 5 个任务 A,B,C,D,E,它们几乎同时到达,预计它们的运行时间为10,6,2,4,8min。其优先级分别为3,5,2,1 和 4,这里 5 为最高优先级。对于下列每一种调度算法,计算其平均进程周转时间(进程切换开销可不考虑)。(1) 先来先服务(按A,B,C , D,E)算法。(2) 优先级调度算法。(3) 时间片轮转算法。解(1) 采用先来先服务(FCFS)调度算法时,5 个任务在系统中的执行顺序、完成时间及周转时间如下表所示:执行次序运行时间优先数等待时间
11、周转时间A 10 3 0 10 B 6 5 10 16 C 2 2 16 18 D 4 1 18 22 E 8 4 22 30 根据表中的计算结果,5 个进程的平均周转时间T 为:T=(10+16+18+22+30 )/5=19.2min (2) 采用最高优先级调度(HPF)算法时,5 个任务在系统中的执行顺序、完成时间及周转时间如下表所示:执行次序运行时间优先数等待时间周转时间B 6 5 0 6 E 8 4 6 14 A 10 3 14 24 C 2 2 24 26 D 1 1 26 27 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -
12、- - - 名师精心整理 - - - - - - - 第 4 页,共 20 页 - - - - - - - - - 4.2 例题解析67 它们的平均周转时间为:T=(6+14+24+26+27 )/5= 19.4min (3) 如果系统采用时间片轮转(RR)算法,令时间片为2 分钟, 5 个任务轮流执行的情况为:第 1 轮: (A,B,C,D,E)第 2 轮: (A,B,D,E)第 3 轮: (A,B,E)第 4 轮: (A,E)第 5 轮: (A)显然, 5 个进程的周转时间为:T1=30min 、 T2=22min 、 T3=6min 、T4=16min 、T5=28min 。它们的平均周
13、转时间T 为:T=( 30+22+6+16+28)/5=20.4min 例 4.2.8 现有两道作业同时执行,一道以计算为主,另一道以输入输出为主,你将怎样赋予作业进程占有处理器的优先级?为什么?解 本题考核要点是,如何提高系统效率的问题。我们知道,以计算为主的进程运行期间,将主要集中在CPU 的计算上,较少使用外部设备。而以输入输出为主的进程则主要集中在外部设备的I/O 上,较少使用CPU。因此让两个进程并发运行是可以提高系统效率的。不过它们的优先级应当设定合理。(1) 如果计算进程的优先级高于或者等于输入输出进程的优先级,系统效率也不会提高。因为计算进程一旦占用了CPU 便忙于计算,使输入
14、输出进程得不到运行机会,同样会使设备空闲,不能提高系统效率。(2) 如果输入输出进程的优先级高于计算进程的优先级,系统效率就能够得到提高。因为输入输出操作是一种速度极慢的操作。若该项操作的优先级高,那么,当它完成一项输入输出操作后,便能立即获得CPU,为下一次输入输出作准备工作,并启动外部设备。当设备被启动起来后,它便主动让出CPU,由系统将CPU 交给计算机进程使用。从而获得较好的运行效率。例 4.2.9 设某系统进程的状态除了最基本的三种状态外,还增加了创建状态、延迟状态和完成状态。试画出系统的进程状态变迁图,并说明状态变迁可能的原因。解 一般的多道程序运行环境中,进程最基本的状态有3 个
15、:就绪、运行、阻塞。本题又增加了创建、延迟、完成3 种状态,使进程状态增至6 个。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页,共 20 页 - - - - - - - - - 第 4 章调度与死锁68 图 4.3 进程状态转换配图(1) 就绪运行:进程具备运行条件,当进程调度程序选择了进程后,便将其转入运行状态。(2) 运行阻塞:进程需要等待某种事件的发生,如执行了输入输出指令,或者请求资源得不到满足时,进程转阻塞状态。(3) 阻塞就绪:进程等待的I/O 已完成,或者请求
16、的资源得到满足,进程转为就绪状态。(4) 创建就绪:进程尚不具备运行条件,所需的资源尚未得到满足。当进程创建完成后,进程可转入就绪状态。(5) 运行延迟:进程运行过程中,因某种原因需要延迟运算,则设定好延迟时间后被转入延迟状态。(6) 运行完成:进程运行时遇到结束指令后,被转入完成状态。例 4.2.10 考虑由 n 个进程共享的具有m个同类资源的系统,证明:如果对i=1 ,2,, , n 进程,有Need0 而且所有最大需求量之和小于m+n,那么该系统是死锁无关的。解 本题的考核要点是资源共享系统。令每个进程请求共享资源的最大量相等,且为x, (0n)号资源。(系统也可以规定由大到小的请求次序
17、。)(2) 按序分配可以破坏环路等待条件。因为在进程发生死锁时,必然存在一个“进程-资源”的环形链。令Pi 表示第i 个进程, Ri 表示第 i 个资源,则, n 个和 n 个资源的进程-资源形链如图所示:名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页,共 20 页 - - - - - - - - - 4.2 例题解析71 图 4.5 进程资源分配图在有环路存在,必然存在一个进程Pi,该进程已经占有了一个较大编号的资源,并再请求一个较小编号的资源,否则循环无法存在。要排除循环
18、的产生,让Pi 先请求较小编号的资源,如果不能满足就不准请求较大编号的。这样一来,较小编号的资源如用于其他进程,Pi 进程申请不到,也就不能申请高号资源,因此形成不了循环,也就不会产生死锁。例 4.2.14 什么叫作业调度和进程调度?下面给出的算法中,哪些适合于前者,哪些适合于后者?(1) FCFS (2) LJF(Longest Job First)(3)SJF (4) RR (5) Priority 解(1) 作业调度是处理机调度中的高级调度,该调度将按照某种算法从后备作业中选择一个作业,将其装入内存创建为进程。(2) 进程调度是处理机调度中的低级调度,该调度将按照某种算法从就绪队列中中选
19、择一个进程,让该进程使用CPU 运行程序。(3) 适合于作业调度的算法有:( 1) 、 (2) 、 (3)和( 5) 。(4) 适合于 CPU 调度的算法有: (1) 、 (4)和( 5) 。例 4.2.15 单处理机分时系统收到了3 个作业,作业提交情况见下表:Job 作业提交时间运行长度其中I/O 时间CPU 时间A 10.0 0.36 小时0.18 小时0.18 小时B 10.2 0.32 小时0.16 小时0.16 小时C 10.4 0.36 小时0.18 小时0.18 小时名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - -
20、 名师精心整理 - - - - - - - 第 9 页,共 20 页 - - - - - - - - - 第 4 章调度与死锁72 现假设:(1) 单 CPU上分时运行两道作业,若每道作业的I /O等待时间皆占各自总运行时间的50% ,则 CPU将有 20% 的时间空闲;(2) 系统有相当充足的可用资源(CPU除外)供用户使用。请写出各个作业的结束时间。解 在分时系统中,进程轮流使用CPU。每个进程使用完一个时间片后就将处理机转给另一个进程。已知,每个进程单道运行时的I /O 等待时间皆占各自总运行时间的50%,若两个进程分时运行时则CPU 将有20%的时间空闲,即,CPU 为各进程分别运行4
21、0%。这样一来,可列出下表所示的运行情况。时间事件道数CPU 等待各占 CPU 经过时间作业进度还需10.0-10.2 A 提交1 50% 50% 0.2 A 0.1 0.08 10.2-10.4 B 提交2 20% 40% 0.2 A B 0.08 0.08 0 0.08 10.4-10.6 C 提交2 20% 40% 0.2 B C 0.08 0.08 0 0.1 10.6-10.8 1 50% 50% 0.2 C 0.1 0 因此, 3 个作业的完成时间为:(1) A :10.4 小时;(2) B:10.6 小时;(3) C:10.8 小时;例 4.2.6 一个计算机系统中拥有6 台打印
22、机,现有N 个进程竞争使用,每个进程要求两台,试问,N 的值如何选取时系统中绝对不会出现死锁?解 本题的考核要点是资源竞争与死锁问题。已知系统中的每个进程需要两台打印机,那么在最坏的情况下,各进程都占用了其中的一台,而且都在请求自己所需的另一台。如果此时系统尚有多余的一台,那么就可以满足其中一个进程运行完毕。因此说,如果让6-1 台打印机分给N 个进程,满足它们每人一台的话,进程数量N 必然小于等于5。当该进程运行完毕释放出它所占有的打印机后,又可以进一步满足其他进程。系统就不会出现死锁。4.3习题4.3.1 选择最合适的答案1某系统采用了银行家算法,则下列叙述正确的是() 。名师资料总结 -
23、 - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页,共 20 页 - - - - - - - - - 4.2 例题解析73 A. 系统处于不安全状态时一定会发生死锁B. 系统处于不安全状态时可能会发生死锁C.系统处于安全状态时可能会发生死锁D.系统处于安全状态时一定会发生死锁2银行家算法中的数据结构包括有可利用资源向量Available 、最大需求矩阵Max、分配矩阵Allocation 、需求矩阵Need,下列选项正确的是() 。A.Maxi,j=Allocationi,j+Needi,j
24、B.Needi,j= Allocationi,j+ Maxi,j C.Maxi,j= Availablei,j+Needi,j D.Needi,j= Availablei,j+ Maxi,j 3下列进程调度算法中,()可能会出现进程长期得不到调度的情况。A. 非抢占式静态优先权法B. 抢占式静态优先权法C.时间片轮转调度算法D.非抢占式动态优先权法4在下列选项中,属于预防死锁的方法是() 。A.剥夺资源法B.资源分配图简化法C.资源随意分配D.银行家算法5在下列选项中,属于检测死锁的方法是() 。A.银行家算法B.消进程法C.资源静态分配法D.资源分配图简化法6在下列选项中,属于解除死锁的方法
25、是() 。A剥夺资源法B.资源分配图简化法C银行家算法D.资源静态分配法7为了照顾紧迫型作业,应采用() 。A.先来服务调度算法B.短作业优先调度算法C.时间片轮转调度算法D.优先权调度算法8在采用动态优先权的优先权调度算法中,如果所有进程都具有相同优先权初值,则此时的优先权调度算法实际上和()相同。A.先来先服务调度算法B.短作业优先调度算法C.时间片轮转调度算法 D.长作业优先调度算法9作业从后备作业到被调度程序选中的时间称为() 。A.周转时间B.响应时间C.等待调度时间D.运行时间10资源静态分配法可以预防死锁的发生,它们使死锁四个条件中的()不成立。A.互斥条件B.请求和保持条件名师
26、资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页,共 20 页 - - - - - - - - - 第 4 章调度与死锁74 C.不可剥夺条件D. 环路等待条件4.3.2 选择所有正确答案1下列选项中, ()可能是非抢占方式进程调度中引起调度的原因。A.当前的运行进程调用阻塞原语而进入阻塞状态B.当前的运行进程提出申请I/O 而阻塞C.有更高优先级的进程到达而从执行状态变为就绪状态D.正在执行的进程执行了P原语操作,由于资源不足而阻塞2选择排队作业中等待时间最长的作业被优先调度,
27、该调度算法不可能是() 。A.先来先服务调度算法B.高响应比优先调度算法C.优先权调度算法D.短作业优先调度算法3作业控制块JCB 连成一串而形成的一个排队队列,该队列称为() 。A挂起队列B.阻塞队列C.就绪队列D.后备队列4下列哪个选项描述的时间属于响应时间的一部分() 。A.处理机对请求信息进行处理的时间B.从键盘输入的请求信息传送到处理机的时间C.所形成的响应回送到终端显示器的时间D.用户查看响应回送到的信息5下列四个选项描述的时间组成了周转时间,其中可能发生多次的是() 。A.等待 I/O 操作完成的时间B.作业在外存后备队列上等待作业调度的时间C.进程在 CPU上的执行时间D.进程
28、在就绪队列上等待进程调度的时间6下面列出的是选择调度方式和算法的4 个面向用户的准则。其中,不完全适用于实时系统的准则是() 。A.优先权准则B.响应时间快C.截止时间的保证 D.周转时间短7下面列出了选择调度方式和算法的4 个准则。其中,对批处理、分时、实时系统都可以采用的是() 。A.周转时间短 B.响应时间快C.截止时间的保证 D. 优先权准则8下列选项中, ()是分时系统中确定时间片大小需要考虑的因素。A.各类资源的平衡利用B.就绪队列中进程的数目名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - -
29、- - - - 第 12 页,共 20 页 - - - - - - - - - 4.2 例题解析75 C.系统的处理能力D.系统对响应时间的要求9下面列出的选项中,属于可剥夺性资源的有() 。A.CPU B.内存C.磁盘D.磁带机10在多级队列调度和多级反馈队列调度的叙述中,正确的是() 。A.多级反馈队列调度中就绪队列的设置不是象多级队列调度一样按作业性质划分,而是按时间片的大小划分B.多级队列调度用到优先权,而多级反馈队列调度中没有用到优先权C.多级队列调度中的进程固定在某一个队列中,而多级反馈队列调度中的进程不固定D.多级队列调度中每个队列按作业性质不同而采用不同的调度算法,而多级反馈队
30、列调度中除了个别队列外,均采用相同的调度算法4.3.3 判断正误,简要说明理由1作业调度能够使作业获得CPU。2在多道程序系统中,系统的现有空闲可用资源能否满足一个后备作业 J的资源要求,是选择作业J 进入内存的必要条件。3短作业(进程)优先调度算法具有最短的平均周转时间,因此这种算法是最好的算法。4在优先权调度算法中确定静态优先权时,一般说,计算进程的优先权要高于磁盘I/O 进程的优先权。5摒弃不可剥夺条件的方法可用于预防多个打印进程死锁的发生。6操作系统处理死锁,只要采用预防、解除、检测、避免之中的一种就足够了。7如果系统在所有进程运行前,一次性地将其在整个运行过程所需的全部资源分配给进程
31、,即所谓“静态分配”法,是可以预防死锁发生的。8多个进程竞争比进程数目少的资源时就可能产生死锁,而当资源数目大于进程数目时就一定不会发生死锁。9在银行家算法中,对某时刻的资源分配情况进行安全分析,如果该时刻状态是安全的,则存在一个安全序列,且这个安全序列是唯一的。10进程调度算法各种各样,但是如果选择不当,就会造成死锁。4.3.4 简答题1高级调度和低级调度的主要任务是什么?为什么要引入中级调度?名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页,共 20 页 - - - -
32、- - - - - 第 4 章调度与死锁76 2在作业调度中需作出哪些决定?3在剥夺调度中,有哪些剥夺原则?4在 OS 中引起进程调度的主要因素有哪些?5在选择调度方式和调度算法时,应遵循的原则是什么?6在批处理系统、分时系统和实时系统中,各采用哪几个进程(作业)调度算法?7为什么说多级反馈队列能较好地满足各种用户的需要?8在多用户分时系统中,时间片轮转调度的算法在确定时间片的大小时,应考虑哪些因素?9为实现实时调度,对实时系统提出了哪些要求?10目前常用的调度方式和算法,能否应用到实时系统中?11在多处理机系统中,比较有代表性的线程调度方式有哪几种?12试比较自调度和成组调度?13在 OS/
33、2 中采用哪种调度方式和调度算法?14何为死锁?产生死锁的原因和必要条件是什么?15在解决死锁问题的几个方法中,哪种方法最容易实现?哪种方法使资源的利用率最高?16请详细说明可通过哪些途径预防死锁?17 在 银 行 家 算 法 的 例 子 中 , 如 果P0 发 出 的 请 求 向 量 由Request0(0,2,0)改为 Request0(0,1,0),问系统可否将资源分配给它?4.4 习题解答要点4.4.1 选择最合适的答案1.B 2.B 3.B 4.D 5.D 6.A 7.D 8.A 9.C 10.B 4.4.2 选择所有正确答案1.ABD 2.BCD 3.D 4.ABC 5.ACD 6
34、.AD 7.D 8.BCD 9.ABC 10.ACD 4.4.4 简答题1 错误作业调度是高级调度。它只能使某作业获得使用CPU 的资格。而只有进程调度或线程调度才能使作业真正获得CPU。2 错误多道系统中的资源分配有两种方法:名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页,共 20 页 - - - - - - - - - 4.4 习题解答要点77 (1) 静态分配:作业调度的功能之一是审查系统能否满足用户作业的资源要求;之二是按照一定的算法选取作业。(2) 动态分配:进程
35、所需的资源是在运行中分配的,作业调度并不考虑当前空闲的资源量,只是按照一定的算法选取作业。3 错误前半句话讲的正确,但由此说短作业(进程)优先调度算法是最好的,就不正确了。因为一个算法的好坏要看其是否适于系统的需要而判定。4 错误因为磁盘I/O 进程属于系统进程。而系统在确定进程的静态优先权时遵循的原则是:系统进程的优先权高于一般用户进程的优先权(除非用户的进程特别紧迫或重要)5 错误因为摒弃不剥夺条件的方法可预防死锁的发生。6 错误因为,操作系统要兼顾资源的使用效率和安全性两个方面,常见的是,将预防、解除、检测、避免四种处理混合起来使用。举例来说,只有检测死锁而无解除死锁,检测出死锁又有什么
36、用呢?7 正确因为资源的“静态分配”方法,可以摒弃“请求和保持”条件,是可以预防死锁的。8 错误进程是否发生死锁,需要考虑每个进程申请资源的数目、所申请资源的种类、进程推进情况等因素。不能简单地比较进程数目和资源数目就来确定是否死锁。9 错误系统在调用银行家算法进行安全检查时,只要找到一个安全序列就可断定系统是安全的。但安全序列可能不止一个,有的情况下可能是只有一个,有的情况下可能有2 个或者更多。10错误如果进程调度算法选择不当,会造成某些进程的长期等待。我们将这种进程称为“饥饿”进程(长期“饥饿”的极端情况是“饿死”) 。 “饿死”和“死锁”具有完全不同的含义。4.3.4 简答题1高级调度
37、和低级调度的主要任务以及引入中级调度原因如下:(1) 高级调度又称为作业调度。它是批处理系统中使用的一种调度。其主要任务是,按照某种算法从外存的后备队列上选择一个或多个作业调入内存,并为它们创建进程、分配必要的资源,然后再将创建的进程控制名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页,共 20 页 - - - - - - - - - 第 4 章调度与死锁78 块挂入就绪队列上。(2) 低级调度又称进程调度。它是距离硬件最近的一级调度。其主要任务是,按照某种算法从就绪队列上选
38、择一个(或多个)进程,使其获得CPU。(3) 引入中级调度的目的是为了提高内存利用率和系统吞吐量。其功能是,让那些暂时不能运行的进程不再占用宝贵的内存资源,而是调出到外存上等待。此时的进程状态为挂起状态。当这些进程重新具备运行条件且内存空闲时,由中级调度选择一部分挂起状态的进程调入内存,将其状态变为内存就绪状态。2在作业调度中需作出的决定如下:(1) 作业调度需要按照多道程序度(即,最大道数)决定一次接纳多少作业进入内存。如果太少将导致系统资源利用率低,且系统吞吐量低;太多将导致内存空间紧张,系统服务质量下降,使作业运行周期过长。(2) 作业调度需要决定接纳哪些作业进入内存。常用的算法是,先来
39、先服务,短作业优先,最高优先级调度、响应比高者优先等。3在剥夺进程调度中,剥夺原则如下:(1) 时间片原则。在轮转算法中,CPU 轮流为诸多进程服务,每个进程运行完自己的时间片后,系统就将它的CPU 剥夺过来,交给下一个进程使用。(2) 优先级原则。为紧迫的作业赋予较高的优先级,这种作业到达系统,或者由阻塞状态被唤醒后,若其优先级高于当前运行的进程的优先级,可以剥夺其CPU。(3) 短作业(进程)优先原则。若一个作业(进程)到达系统,其运行长度比当前运行的进程长度明显的短,则剥夺它的CPU。4引起进程调度的主要因素主要有:(1) 一个进程运行完毕;(2) 一个正在运行的进程被阻塞;(3) 在抢
40、占式调度中,一个高优先级的进程被创建;(4) 在抢占式调度中,一个高优先级进程由阻塞被唤醒;(5) 在轮转式调度中,正在运行的进程运行完一个时间片。5在选择调度方式和调度算法时,应遵循的原则如下:(1) 面向用户准则。首先,对于用户的紧迫性作业,系统能够及时地处理,不至于运行延误。其次,对于批处理系统,还应追求作业的周转时间短;分时系统中作业的响应时间块;实时系统中作业的截止时间有保证。(2) 面向系统准则。系统的吞吐量高,处理机的利用率高,各类系统资源能够得到平衡利用。6批处理系统、分时系统和实时系统中的主要调度算法如下:(1) 批处理系统中的作业调度算法有先来先服务(FCFS) 、短作名师
41、资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页,共 20 页 - - - - - - - - - 4.4 习题解答要点79 业优先( SJF) 、优先级调度(HPF)和高响应比优先(RF) 。批处理系统的进程调度算法有:先进先出(FIFO) 、短进程优先(SPF) 、优先级调度( PRI)和高响应比优先(RF) 。(2) 分时系统中只设有进程调度(不设作业调度),其进程调度算法只有轮转法(RR)一种。(3) 实时系统中只设有进程调度(不设作业调度),其进程调度算法有:轮转法、优
42、先级调度算法。前者适用于时间要求不严格的实时系统;后者用于时间要求不严格的实时系统。后者又可细分为:非抢占式优先级调度、抢占式优先级调度、基于时钟中断的抢占式优先级调度。注意,一个纯粹的实时系统是针对特定应用领域设计的专用系统。作业提交的数量不会超过系统规定的多道程序度,因而可全部进入内存。若将实时系统与批处理系统结合的话,就可以让作业量超过多道程序度,使优先级低的作业呆在外存的后备队列上。7多级反馈队列能较好地满足各种用户的需要的原因:(1) 终端用户的作业一般比较短小精悍,大多数在进入多级队列的第一级队列中后运行一个时间片就可以完成,因而感到满意。(2) 批处理作业用户,其作业进入多级队列
43、的第一级队列中后,若作业较短,运行一个时间片就可以完成。对于稍长一些的作业,只需在第二或第三队列上各执行一个时间片就可完成,因而感到满意。对于长作业来说,它将依次在第1,2,, , n 个队列上运行,不会因作业太长而长期得不到处理。8在多用户分时时间片长度的选择上,既要保证交互性,又要保证系统的效率。(1) 系统对响应时间T 的要求(一般应小于等于23 秒钟) ;(2) 就绪队列中的进程数目N(N 与终端上的用户数目有关);(3) 系统的处理能力,一个时间片的长度q 应能保证用户的大部分常用命令可处理完;(4) 进程的转换时间p;(5) 三者的关系可表示为:T=N(q+p) 。9对实时系统提出
44、了要求如下:(1) 任务要提供必要的调度信息:主要包括:开工的最后期限或完工的最后期限、处理时间长度、优先级、就绪时间,以及资源需求。(2) 采用适当的调度方式:如果实时任务的运行长度较长且时间要求严格,那么实时系统应采用抢占式调度;如果所有的实时任务都比较小,且预知任务的开工最后期限,也可以采用非剥夺式调度。(3) 能够快速响应外部中断:这要求,硬件上要有较高的中断机制,软件上要使“封中”的时间间隔尽量短,以免贻误时机。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页,共
45、20 页 - - - - - - - - - 第 4 章调度与死锁80 (4) 快速的任务分派能力:尽量减少任务切换时间开销,使得一个任务完成后可以较快地切换到下一个任务去。10抢占方式和非抢占方式都可以用于实时系统中。能够使用的算法有:轮转算法(RR)和优先级调度算法(HPF) ;不可以使用的算法有:先进先出( FIFO)和短进程优先算法(SPF) 。11在多处理机系统中,有代表性的线程调度方式有:(1) 自调度方式:诸多CPU 可以共享同一就绪队列,从中获取就绪线程运行。(2) 成组调度方式:由系统将若干相关的线程同时分配到多台CPU上运行。线程与CPU 一一对应。(3) 专用处理机分配方
46、式:将若干同属于一个应用程序的线程分配到一组 CPU 上。让这组CPU 专门处理它们。12调度方式的比较如下:(1) 自调度方式中,就绪队列与单机的相同,调度算法也与之相同。系统没有集中调度机制,任何CPU 都可调用系统的调度例程去选择一个线程。只要就绪队列不空,就不会有空闲的CPU。它存在的问题是,多CPU 共享一个就绪队列将产生瓶颈;各线程在其生命周期中可能要换好几台CPU,每次更换都要将CPU 中的高速缓存(Cache)重新拷入现场数据,造成效率低下;由于合作的一组线程很难同时获得CPU,一些运行的线程只好阻塞等待未获得CPU 的线程,所以线程切换频繁。(2) 成组调度中,合作的各线程可
47、以同时获得CPU,减少因同步造成的阻塞,减少了切换次数。同时,也可减少调度的频率。13多优先级的抢占式调度,调度的基本单位是线程。优先级分为3类:每一类共细分32 级,以31 级为最高级。其中:时间紧迫类为最高类,对应的是实时线程及通信管理等;常规类为中档优先类,对应的是一般线程;空闲时间类为较低类,对应的是紧迫度低的线程。调度算法:在同一类的同一优先级中采用轮转算法。每当运行完一个时间片就检查是否有更高优先级线程到来,若有便抢占CPU。14(1) 死锁是指多个进程因竞争资源而造成的一种僵持状态。若无外力作用,这些进程都将永远处于阻塞状态,不能再运行下去。(2) 产生死锁的原因有:资源不足资源
48、、进程推进次序不当。(3) 产生死锁的必要条件有:互斥条件、请求和保持条件、不可剥夺条件、环路等待条件。15(1) 预防死锁方法,主要是破坏产生死锁的必要条件。该方法是最容易实现的,但系统资源利用率较低。(2) 避免死锁方法,比较实用的有银行家算法(Banker Algorithm ) 。该算法需要较多的数据结构,实现起来比较困难,但资源利用率最高。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页,共 20 页 - - - - - - - - - 4.4 习题解答要点81 (
49、3)检测死锁方法是基于死锁定理设计的,定期运行该算法对系统的状态进行检测,发现死锁便予以解除。其中,需要比较一下各种死锁解除方案的代价,找到代价最小的方案。该方法最难实现,资源利用率较高。16预防死锁方法是破坏产生死锁的必要条件,主要有:(1) 摈弃请求和保持条件。采用静态分配方案,一次性地分配给进程所请求的全部资源。进程运行过程中不可再请求新资源。(2) 摈弃不剥夺条件。采用动态分配方案,进程运行中可以请求新资源。若进程请求资源不能满足时,就应使其释放已占有的资源。(3) 摈弃环路等待条件。采用动态分配方案,要求进程请求资源时,按资源序号递增(或递减)顺序提出。17系统的资源数量为: ( 1
50、0,5, 7) 。经过一段时间的分配后,资源分配与占用情况见下表所示。进程MAX A B C Allocation A B C Need A B C Available A B C P0 7 5 3 0 1 0 7 4 3 3 3 2 P1 3 2 2 2 0 0 1 2 2 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 (1)Request1(1,0,2): P1请求满足后的占用情况如下。进程MAX A B C Allocation A B C Need A B C Available A B C P0 7 5
51、3 0 1 0 7 4 3 2 3 0 P1 3 2 2 3 0 2 0 2 0 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 (2)检测系统此刻存在一条安全序列P1 ,P3,P4,P0, P2。检测过程为:1)资源可用量( 230) ,不能满足P0,可满足 P1。2)资源可用量( 532) ,不能满足P2,可满足 P3。3)资源可用量( 743) ,可满足P4。4)资源可用量( 745) ,可满足P0。5)资源可用量( 755) ,可满足P2。待其完成后使系统的资源可用量达到初始值(10,5,7) 。名师资料总结
52、 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页,共 20 页 - - - - - - - - - 第 4 章调度与死锁82 (3)Request4(3,3,0): P4 的请求超过系统当前的可用量(2,3,0) ,应推迟分配。(4)Request0(0,1,0): P0 请求满足后的占用情况如下:进程MAX A B C Allocation A B C Need A B C Available A B C P0 7 5 3 0 2 0 7 3 3 2 2 0 P1 3 2 2 3 0
53、2 0 2 0 P2 9 0 2 3 0 2 6 0 0 P3 2 2 2 2 1 1 0 1 1 P4 4 3 3 0 0 2 4 3 1 检测系统此刻存在安全序列P1,P3,P4,P0,P2。1)资源可用量(220) ,不能满足P0,可满足P1。2)资源可用量(522) ,不能满足P2,可满足P3。3)资源可用量(733) ,可满足 P4。4)资源可用量(735) ,可满足 P0。5)资源可用量(755) ,可满足P2。待其完成后使系统的资源可用量达到初始值(10,5, 7) 。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页,共 20 页 - - - - - - - - -