操作系统习题解析.pptx

习题选讲与解析一、选择题1.在计算机系统中配置操作系统的主要目的是（A）。操作系统的主要功能是管理 计算机系统中的（B），其中包括（C）、（D），以及文件和设备。这里的（C）管 理主要是对进程进行管理。A：（1）增强计算机系统的功能；（2）提高系统资源的利用率；（3）提高系统的运行速度；（4）合理组织系统的工作流程，以提高吞吐量。B：（1）程序和数据；（2）进程；（3）资源；（4）作业；（5）软件；（6）硬件。C，D：（1）存储器；（2）虚拟存储器；（3）运算器；（4）处理机；（5）控制器。2.操作系统有多种类型：允许多个用户以交互方式使用计算机的操作系统称为（A）；允许多个用户将若干个作业提交给计算机系统集中处理的操作系统称为（B）；在（C）的控制下，计算机系统能及时处理由过程控制反馈的数据，并做出响应；在IBMPC机上的操作系统称为（D）。A，B，C，D：（1）批处理操作系统；（2）分时操作系统；（3）实时操作系统；（4）微机操作系统；（5）多处理机操作系统。A:2 B:3 C:4 D:1A:2 B:1 C:3 D:43.在设计分时操作系统时，首先要考虑的是（A）；在设计批处理操作系统时，先要考虑的是（B）；在设计实时操作系统时，首先要考虑的是（C）。A，B，C：（1）灵活性和可适应性；（2）交互性和响应时间；（3）周转时间和系统吞吐量；（4）实时性和可靠性。4.分时系统的响应时间（及时性）主要是根据(A)确定的，而试试系统的响应时间则是由（B）确定的。A，B：（1）时间片大小；（2）用户数目；（3）计算机运行速度；（4）用户所能接受的等待时间；（5）控制对象所能接受的时延；（6）实时调度。5.采用（A）结构时，将OS分成用于实现OS最基本功能的内核和提供各种服务的服务器两个部分。通常，下列模块中必须包含在操作系统内核中的是（B）模块。A：（1）整体式；（2）模块化；（3）层次式；（4）微内核。B：（1）内存分配；（2）中断处理；（3）文件处理；（4）命令处理。A:4 B:2A:4 B:5A:2 B:3 C:46.6.在在3.X3.X版本以前的版本以前的MSMSDOSDOS是（是（A A）操作系统，）操作系统，Windows95Windows95是（是（B B）操作系统，）操作系统，WindowsXPWindowsXP是（是（C C）操作系统，它们都是由（操作系统，它们都是由（D D）开发的。）开发的。A A，B B，C C：（：（1 1）单用户单任务；（）单用户单任务；（2 2）单用户多任务；（）单用户多任务；（3 3）多用户单任务；（）多用户单任务；（4 4）多用户多任务。）多用户多任务。D D：（：（1 1）IBMIBM公司；（公司；（2 2）MicrosoftMicrosoft公司；（公司；（3 3）MicrosoftMicrosoft和和IBMIBM联合；（联合；（4 4）BellBell实验室；实验室；7 7.下面下面8 8个系统中，必须是实时操作系统的有（个系统中，必须是实时操作系统的有（）A A计计算算机机辅辅助助设设计计系系统统；B B 航航空空定定票票系系统统；C C 过过程程控控制制系系统统；D D 机机器器翻翻译译系系统统；E E 办办公公自自动动化化系统；系统；F F 计算机激光照排系统；计算机激光照排系统；G G情报检索系统；情报检索系统；H H导弹的制导系统导弹的制导系统l二、二、简答题简答题在操作系统中实现虚拟的关键技术是什么？并加以说明。在操作系统中实现虚拟的关键技术是什么？并加以说明。操作系统中所谓的操作系统中所谓的”虚拟虚拟“，是指通过某种技术把一个物理实体变为若干个逻辑上，是指通过某种技术把一个物理实体变为若干个逻辑上的对应物，相应的用于实现虚拟的技术称为虚拟技术。在操作系统中利用了多种虚拟技的对应物，相应的用于实现虚拟的技术称为虚拟技术。在操作系统中利用了多种虚拟技术分别用来实现虚拟处理机、虚拟内存、虚拟外设和虚拟信道等。虚拟的实现主要是通术分别用来实现虚拟处理机、虚拟内存、虚拟外设和虚拟信道等。虚拟的实现主要是通过分时技术，例如，多道程序系统中，通过过分时技术，例如，多道程序系统中，通过分时技术分时技术来实现虚拟处理机来实现虚拟处理机；将一台物理处；将一台物理处理机虚拟为多台逻辑上的处理机，是靠多道程序分时地使用同一台物理处理机来实现的。理机虚拟为多台逻辑上的处理机，是靠多道程序分时地使用同一台物理处理机来实现的。微观上，该处理机在每一时刻只运行一道程序，它们分时地运行；然而在宏观上，系统微观上，该处理机在每一时刻只运行一道程序，它们分时地运行；然而在宏观上，系统中确有几道程序在同时运行，从而给用户的感觉是系统中同时同时有多台处理机在为其中确有几道程序在同时运行，从而给用户的感觉是系统中同时同时有多台处理机在为其中的每一道程序服务，显然用户所感觉到的处理机并不实际存在。中的每一道程序服务，显然用户所感觉到的处理机并不实际存在。A:1 B:2 C:4 D:2ABCGH试从交互性、及时性以及可靠性三个方面，比较分时系统与实时系统。P11 已知一个求值公式（已知一个求值公式（A2+3B）/(B+5A),若若A,B已赋值，试画出已赋值，试画出该公式求值过程的前趋图，并用信号量解决公式的求解过程。该公式求值过程的前趋图，并用信号量解决公式的求解过程。S1:x1=A*AS2:x2=3*BS3:x3=5*AS4:x4=x1+x2S5:x5=B+x3S6:x6=x4/x5开始开始结束结束S1S4S6S5S3S2S1S4S6S5S3S2struct semaphore a,b,c,d,e,=0,0,0,0,0;cobegin S1;V(a);S2;V(b);S3;V(c);P(a);P(b);S4;V(d)P(c);S5;V(e);P(d);P(e);S6);coend acbde吃水果问题吃水果问题问题描述：桌上有一只盘子，每次只能放一个水果，爸爸专向盘中放苹果，妈妈专向盘中问题描述：桌上有一只盘子，每次只能放一个水果，爸爸专向盘中放苹果，妈妈专向盘中放桔子，儿子专等吃盘里的桔子，女儿专等吃盘里的苹果。只要盘子空，则爸爸或妈妈可放桔子，儿子专等吃盘里的桔子，女儿专等吃盘里的苹果。只要盘子空，则爸爸或妈妈可向盘中放水果，仅当盘中有自己需要的水果时，儿子或女儿可从中取出，请给出四人之间向盘中放水果，仅当盘中有自己需要的水果时，儿子或女儿可从中取出，请给出四人之间的同步关系，并用的同步关系，并用P、V操作实现四人正确活动的程序。操作实现四人正确活动的程序。void son(void)while(TRUE)P(so);get an orange;V(s);eat an orange;void daught(void)while(TRUE)P(sp);get an apple;V(s);eat an apple;coendstruct semaphore s,sp,so=1,0,0;cobegin void father(void)while(TRUE)have an apple;P(s);put an apple;V(sp);void mother(void)while(TRUE)have an orange;P(s);put an orange;V(so);Plate 1爸私爸私 applempty 盘中无苹果盘中无苹果 1女私女私applefull盘中有苹果盘中有苹果0妈私妈私orangempty无桔子无桔子1儿私儿私orangefull有桔子有桔子0爸爸p(plate);P(applempty);放苹果；放苹果；V(applefull);V(plate);女女p(applefull);P(plate);取苹果；取苹果；V(applempty);儿儿p(orangefull);P(plate);取桔子；取桔子；V(plate);V(orangempty);母母p(plate);P(orangempty);放桔子；放桔子；V(orangefull);V(plate);mutex 盘子盘子a表示爸爸是否在盘中放入苹果表示爸爸是否在盘中放入苹果b 女儿是否可吃苹果女儿是否可吃苹果c表示妈妈是否在盘中放桔子表示妈妈是否在盘中放桔子d为儿子是否可吃桔子为儿子是否可吃桔子p(a);p(mutex);放入苹果；放入苹果；v(b);p(b);取走苹果；取走苹果；v(a);v(mutex);p(c);p(mutex);放入桔子；放入桔子；v(d);p(d);取走桔子取走桔子;v(c);v(mutex)初值？初值？mutex 盘子盘子1appfull苹果个数苹果个数0avail 盘中空位个数初值为盘中空位个数初值为norgfull 桔子的个数桔子的个数0 dadP(avail);P(mutex);put an apple;V(appfull);V(mutex);momP(avail);P(mutex);put an orange;V(orgfull);V(mutex);sonP(orgfull);P(mutex);get an apple;V(avail);V(mutex);dauP(appfull);P(mutex);get an apple;V(avail);V(mutex);注意初值注意初值avail的设置，的设置，n不正确不正确BeginP(apple);P(pan)V(apple);V(pan);P(orange);P(pan);V(orange);V(pan);P(pan);P(apple);V(apple);V(apple);V(pan);P(pan);P(orange);V(orange);V(pan);四人动作未分开，四人动作未分开，apple和和orange变量的含义不明确变量的含义不明确lempty=1;apple=0;orange=0;S1：parbegin P(empty);count:=count+1;V(apple);do sth elseparendS2：parbegin P(empty);count:=count+1;V(orange);do sth elseparendS3：parbegin P(orange);count:=count-1;If(count=0)V(empty);do sth elseparendS4：parbegin P(apple);count:=count-1;If(count=0)V(empty);do sth elseparend父父子子女女母母lcount=0;struct semphore plate,platempty,orange,apple=1,1,0,0;cobeginmother(void)beginP(platempty);P(plate);桔子放入盘中；桔子放入盘中；V(orange)；V(plate)；end son(void)beginP(orange);P(plate);吃桔子；吃桔子；V(platempty)；V(plate)；end mother(void)beginP(apple);P(plate);吃苹果；吃苹果；V(platempty)；V(plate)；endcoend father(void)beginP(platempty);P(plate);放苹果；放苹果；V(apple)；V(plate)；end设公共汽车上，司机和售票员的活动分别是：设公共汽车上，司机和售票员的活动分别是：司机：司机：售票员：售票员：启动车辆启动车辆 上下乘客上下乘客 正常行车正常行车 关车门关车门 到站停车到站停车 售票售票 开车门开车门 上下乘客上下乘客 在汽车不断到站，停车，行驶过程中，这两个活动的同步关系。在汽车不断到站，停车，行驶过程中，这两个活动的同步关系。struct semaphore s1,s2=0,0;cobegin void driver(void)while(TRUE)p(s2);启动车辆启动车辆;正常行车正常行车;到站停车到站停车;V(s1);void conductor(void)while(TRUE)上、下乘客；关车门；上、下乘客；关车门；V(s2);售票；售票；P(s1);开车门开车门;上、下乘客上、下乘客;coendS1是否可以开车门是否可以开车门S2是否可以发动车辆是否可以发动车辆struct semaphore s1,s2=1,0;cobegin void driver(void)while(TRUE)P(s2);启动车辆启动车辆;正常行车正常行车;到站停车到站停车;V(s1);void conductor(void)while(TRUE)P(s1);开车门开车门;上、下乘客上、下乘客;关车门关车门;V(s2);售票；售票；coend司机司机-售票员问题另解：售票员问题另解：S1是否可以开车门1S2是否可以发动车辆01.在某系统中，三个进程共享四台设备资源，这些资源一次只能一台地为进程服务和释放，每个进程最多需要二台设备资源，试问在系统中是否会产生死锁？l答：不会。若所有的资源都被占用，而占用者又都不满足必须的全部资源，此时就有一个或几个进程无限期地等待更多的资源，系统就会出现死锁。本题中若4 台设备资源都被占用，则其中一定有一个进程获得2台设备资源(满足其最大的需求量)，这个进程必然会在有限的时间内完成其工作，并释放其所占用的2台资源，这样也就能满足其它二进程对设备资源的要求，继续完成它们各自的工作。某寺庙，有小和尚和老和尚若干，有一个水缸，由小和尚某寺庙，有小和尚和老和尚若干，有一个水缸，由小和尚提水入缸供老和尚饮用。水缸可以容纳提水入缸供老和尚饮用。水缸可以容纳1010桶水，水取自同一口桶水，水取自同一口井中，由于水井口窄，每次只能容纳一个水桶取水。水桶总数井中，由于水井口窄，每次只能容纳一个水桶取水。水桶总数为为3 3个。每次入水、取水仅为一桶，且不可同时进行。试给出有个。每次入水、取水仅为一桶，且不可同时进行。试给出有关取水、入水的算法描述。关取水、入水的算法描述。l 应首先考虑清楚本题需要几个进程。从井中取水后向缸中倒应首先考虑清楚本题需要几个进程。从井中取水后向缸中倒水此为连续动作，可算同一进程，从缸中取水为另一进程。在考水此为连续动作，可算同一进程，从缸中取水为另一进程。在考虑信号量，有关互斥的资源有水井（一次仅一个水桶进出），水虑信号量，有关互斥的资源有水井（一次仅一个水桶进出），水缸（一次如水取水时均为一桶），分别为之设置信号量缸（一次如水取水时均为一桶），分别为之设置信号量mutex1,mutex2控制互斥；另有同步问题存在：三个水桶无论控制互斥；另有同步问题存在：三个水桶无论从井中取水还是入出水缸都是一次一个，应为之设信号量从井中取水还是入出水缸都是一次一个，应为之设信号量count，抢不到水桶的进程只好等待；还有水缸满时，不可入水，设信，抢不到水桶的进程只好等待；还有水缸满时，不可入水，设信号量号量empty,控制入水量，水缸空时不可出水，设信号量控制入水量，水缸空时不可出水，设信号量full,控制控制出水量。出水量。mutex1:=1;mutex2:=1;empty:=10;full:=0;count:=3;cobegin 小和尚打水:beginL1:P(empty);P(count);P(mutex1);从井中取水；V(mutex1);P(mutex2);送入水缸；V(mutex2);V(count);V(full);Goto L1:end;老和尚取水：begin L2:P(full);P(count);P(mutex2);从缸中取水；V(mutex2);V(empty);V(count);Goto L2 end;coend.n在南开大学和天津大学之间有一条弯曲的小路，在南开大学和天津大学之间有一条弯曲的小路，其中从其中从S S到到T T一段路每次只允许一辆自行车通过，一段路每次只允许一辆自行车通过，但中间有一个小的但中间有一个小的“安全岛安全岛”M M（同时允许两辆自（同时允许两辆自行车停留），可供两辆自行车已从两端进入小路行车停留），可供两辆自行车已从两端进入小路情况下错车使用，如图所示。试设计一个算法来情况下错车使用，如图所示。试设计一个算法来使来往的自行车均可顺利通过。使来往的自行车均可顺利通过。MKSTL南开大学南开大学天津大学天津大学MKSTL南开大学南开大学天津大学天津大学 本本题题是是一一个个利利用用P、V操操作作控控制制一一个个任任务务流流程程的的问问题题。这这类类问问题题较较常常见见。分分析析的的时时候候主主要要是是列列出出所所需需控控制制的的对对象象，以以及及其其控控制制关关系系，对对于于本本题题来来说说，所所需需控控制制对对象象，以以及及其其控控制制关关系系。对对于于本本题题来来说说，所所需需控控制制的的对对象象是是由由T到到L这这一一段段路路的的使使用用，由由S到到K这这一一段段路路的的使使用用以以及及M这这个个“安安全全岛岛”的的使使用用。路路段段T至至L及及路路段段S至至K同同时时只只允允许许一一个个进进程程（一一辆辆自自行行车车）使使用用，对对于于它它们们，我我们们可可以以分分别别用用3个个信信号号量量来来管管理理。最最后后，由由于于同同时时最最多多只只能能由由一一个个方方向向的的一一辆辆自自行行车车通通过过（两两个个方方向向共共两两辆辆自自行行车车），因因此此，对对每每个个方方向向上上的的自自行行车车还应用一个信号量来控制对临界资源的访问。还应用一个信号量来控制对临界资源的访问。解解答答：对对于于两两个个方方向向的的自自行行车车，我我们们用用两两个个进进程程bikeT2N和和bikeN2T来来表表示示。BikeT2N为为从从天天津津大大学学向向南南开开大大学学行行驶驶的的自自行行车车，bikeN2T为为从从南南开开大大学学向向天天津大学行驶的自行车。其控制流程如下：津大学行驶的自行车。其控制流程如下：BEGIN Integer T2N,N2T，L，M，K；T2N：1；N2T：1；L：1；K：1；M：2;BEGINPROCEDURE bikeT2N()P(T2N)；P（L）；）；go through T to L;P(M);Go into M;V(L);P(K);go through K to S;V(M);V(K);V(T2N);MKSTL南开大学南开大学天津大学天津大学PROCEDURE bikeN2T()P(N2T);P(K);go through S to K;P(M);go into M;V(K);P(L);go through L to T;V(M);V(L);V(N2T);END某工厂有两个生产车间，两个生产车间分别生产某工厂有两个生产车间，两个生产车间分别生产A，B两种零件，装配车间的任务是把两种零件，装配车间的任务是把A，B两种零件组装成两种零件组装成产品。两个生产车间每生产一个零件后都要分别把它产品。两个生产车间每生产一个零件后都要分别把它们送到装配车间的货架们送到装配车间的货架F1，F2上，上，F1存放零件存放零件A，F2存放零件存放零件B，F1和和F2的容量均为可以存放的容量均为可以存放10个零件。个零件。装配工人每次从货架上取一个装配工人每次从货架上取一个A零件和一个零件和一个B零件然后零件然后组装成产品。请用组装成产品。请用PV操作进行正确管理。操作进行正确管理。l该题是生产者消费者的变形，可以认为一个消费该题是生产者消费者的变形，可以认为一个消费者（装配工人）同两个生产者（者（装配工人）同两个生产者（A，B车间）互车间）互斥试用两个缓冲区（斥试用两个缓冲区（F1，F2），可设），可设mutex1，mutex2（初值为（初值为1）控制进程对）控制进程对F1，F2的互斥操的互斥操作，另设作，另设empty1，empty2（初值均为（初值均为10），），full1，full2（初值均为（初值均为0）。过程如下：）。过程如下：Cobegin A车间：车间：Begin生产一个产品；生产一个产品；P（empty1）；）；P（mutex1）；）；放入放入F1；V（mutex1）；）；V（full）；）；EndB车间车间Begin生产一个产品；生产一个产品；P(empty2);P(mutex2);放入放入F2；V(mutex2);V(full2);End装配工人：装配工人：BeginP(full1);P(full2);P(mutex1);P(mutex2);取取A和和B；V(mutex1);V(mutex2);V(empty1);V(empty2);End 假定系统中有五个进程P0、P1、P2、P3、P4和三种类型的资源A，B，C，每一种资源的数量分别为10、5、7，在T0时刻的资源分配情况如图请找出该表中T0时刻以后存在的安全序列（至少2种）资源情况资源情况进程进程AllocationA B CMaxA B CNeedA B CAvailableA B CP0P1P2P3P40 1 03 2 29 0 22 2 24 3 32 0 03 0 22 1 10 0 27 4 31 2 26 0 00 1 14 3 13 3 27 5 3（中国科学院计算技术研究所1999年试题）一系统具有150个存储单元，在T0时刻下表所示分配给3个进程。进程进程 Maximum demand Current allocation Maximum demand Current allocation P1 70 25 P1 70 25 P2 60 40 P2 60 40 P3 60 45 P3 60 45对下列请求应用银行家算法分别分析判定是否安全？（1）第4个进程P4到达，最大需求60个存储单元，当前请求分配25个单元；（2）第4个进程P4到达，最大需求50个存储单元，当前请求分配35个单元；如果是安全的，情给出一个可能的安全执行序列；如果是不安全的，请说明原因。l该题的两个问题都是问当P4当前的需求是否可以满足。对于P4来说关键不在其最大的需求量是多少，而是其当前需求量是多少；系统在此时剩余资源数是40个；l（1）P4的最大需求量为60，当前请求分配25个，计算是否安全，应在假设分配之后看是否找到安全序列。结果是至少可以找到一个安全序列，答案不唯一。l（2）P4得到35个单元后，系统剩余资源数为5，此时4个进程的剩余量需求量均无法满足，为不安全状态，因为找不到安全序列。设系统中有3种类型的资源（A，B，C)和5个进程（P1,P2,P3,P4,P5)，A资源的数量为17，B资源的数量为5，C资源的数量为20，在T0时刻系统状态见下表。进程 最大资源数量 已分配资源数量 剩余资源数量 A B C A B C A B C P1 5 5 9 2 1 2 2 3 3 P2 5 3 6 4 0 2 P3 4 0 11 4 0 5 P4 4 2 5 2 0 4 P5 4 2 4 3 1 4系统采用银行家算法实施死锁避免策略。（1）T0时刻是否为安全状态？若是，请给出安全序列（2）在T0时刻若进程P4请求（0，3，4），是否能实施资源分配？为什么？（3）在（2）的基础上，若进程P4请求资源（2，0，1）是否能实施资源分配？为什么？（4）在（3）的基础上，若进程P1请求资源（0，2，0），是否能实施分配？为什么？判断是否为安全状态，关键在于能否找到一个安全序列。这与进程剩余需求量判断是否为安全状态，关键在于能否找到一个安全序列。这与进程剩余需求量有关，列表如下有关，列表如下资源情况资源情况进程进程NeedA B CworkA B CWorkAllocationA B CAllocationA B CP4P2P3P5P1finish 2 3 3 2 2 1 2 0 4 4 3 7 true 4 3 7 1 3 4 4 0 2 8 3 9 true 8 3 9 0 0 6 4 0 5 12 3 14 true12 3 14 1 1 0 3 1 4 15 4 18 true15 4 18 3 4 7 2 1 2 17 5 20 true 进程进程 最大资源数量最大资源数量 已分配资源数量已分配资源数量 还需要资源数量还需要资源数量 剩余资源数量剩余资源数量 A B C A B C A B C A B C P1 5 5 9 2 1 2 3 4 7 2 3 3 P2 5 3 6 4 0 2 1 3 4 P3 4 0 11 4 0 5 0 0 6 P4 4 2 5 2 0 4 2 2 1 P5 4 2 4 3 1 4 1 1 0（2）Request4（0，3，4）Available（2，3，3），系统不能给予满足。），系统不能给予满足。（3）a：Request4（2，0，1）Need4（2，2，1）b：Request4（2，0，1）Available（2，3，3）c：系统试探将：系统试探将Request4（2，0，1）分配出去并修改数据结构的值）分配出去并修改数据结构的值进程进程 最大资源数量最大资源数量 已分配资源数量已分配资源数量 还需要资源数量还需要资源数量 剩余资源数量剩余资源数量 A B C A B C A B C A B C P1 5 5 9 2 1 2 3 4 7 0 3 2 P2 5 3 6 4 0 2 1 3 4 P3 4 0 11 4 0 5 0 0 6 P4 4 2 5 4 0 5 0 2 0 P5 4 2 4 3 1 4 1 1 0此时可以寻找到安全序列此时可以寻找到安全序列,此次请求可以分配此次请求可以分配（4）a：Request1（0，2，0）Available(0,3,2)b:Request1(0,2,0)0 430 段号段号 位移量位移量W649段号段号 基址基址 段长段长物理地址物理地址01234219230090132719526001410058096段号段号基址基址长度长度01234219230090132719526001410058096已知段表如下所示已知段表如下所示 下述逻辑地址的物理地址是什么？并画出基本分段的地下述逻辑地址的物理地址是什么？并画出基本分段的地址变换过程址变换过程（0，430）、（）、（1，10）、（）、（1，11），（），（2，500），），（3，400），（），（4，112）（0，430）的物理地址是）的物理地址是649（1，10）的物理地址是）的物理地址是2310（1，11）的物理地址是）的物理地址是2311（2，500）地址非法，产生越界中断）地址非法，产生越界中断（3，400）的物理地址是）的物理地址是1727（4，112）地址非法，产生越界中断）地址非法，产生越界中断5.进程资源的使用情况和可用情况如下表所示，请画出资源分配图，并判断该状态进程资源的使用情况和可用情况如下表所示，请画出资源分配图，并判断该状态是否会产生死锁？是否会产生死锁？进程进程 当前分配数当前分配数 待分配的请求待分配的请求 可用资源可用资源 R1 R2 R3 R1 R2 R3 R1 R2 R3 P1 2 0 0 1 1 0 0 0 0 P2 3 1 0 0 0 0 P3 1 3 0 0 0 1 P4 0 1 1 0 1 0 P1P2P3P4R1R2R3P1P2P3P4R1R2R3P1P2P3P4R1R2R3P1P2P3P4R1R2R3P1P2P3P4R1R2R3根据死锁定理，资源分配图可完全化简系统中不存在死锁根据死锁定理，资源分配图可完全化简系统中不存在死锁6.吸烟者问题：三个吸烟者在一个房间内，还有一个香烟供应者。为了制造吸烟者问题：三个吸烟者在一个房间内，还有一个香烟供应者。为了制造并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴、供应者有丰富货并抽掉香烟，每个吸烟者需要三样东西：烟草、纸和火柴、供应者有丰富货物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸和第三个物提供。三个吸烟者中，第一个有自己的烟草，第二个有自己的纸和第三个有自己的火柴。供应者随机地将两样东西放在桌子上，允许一个吸烟者进行有自己的火柴。供应者随机地将两样东西放在桌子上，允许一个吸烟者进行对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再把另外两样对健康不利的吸烟。当吸烟者完成吸烟后唤醒供应者，供应者再把另外两样东西放在桌子上，唤醒另一个吸烟者。试采用信号量和东西放在桌子上，唤醒另一个吸烟者。试采用信号量和P、V操作编写他们同操作编写他们同步工作的程序。步工作的程序。烟烟草草纸纸 火火柴柴123烟草、纸、火柴烟草、纸、火柴香烟提供者香烟提供者a b c abca代表烟草、代表烟草、b代表纸，代表纸，c代表火柴；我们设初始状态为老板先出售代表火柴；我们设初始状态为老板先出售b，c（即（即a的初值为的初值为0；b，c初值为初值为1）设）设mutex1，mutex2，mutex3（初值均为（初值均为1）作为互斥信号量，用来）作为互斥信号量，用来控制对三组变量（控制对三组变量（b，c），（），（a，c），（），（a，b）的访问；再设信号量）的访问；再设信号量buy1，buy2，buy3，sale用来吸烟者同老板之间的同步控制，其中用来吸烟者同老板之间的同步控制，其中buy1初值为初值为1，其它初值为，其它初值为0；因；因此我们设置的初始状态为老板可向第一个对列出售他们需要的两种物品此我们设置的初始状态为老板可向第一个对列出售他们需要的两种物品lstruct semaphore mutex1，mutex2，mutex3，buy1，buy2，buy3，sale1，1，1，1，0，0，0；lint a，b，c0，1，1；P1：Begin P(buy1);P(mutex1);b:=b-1;c:=c-1;V(mutex1);吸烟；V（sale）；End P2：BeginP(buy2);P(mutex2);a:=a-1;c:=c-1;V(mutex2);吸烟；V（sale）；End P3：BeginP(buy3);P(mutex3);a:=a-1;b:=b-1;V(mutex3);吸烟；V（sale）；End P4：Cobegin begin P(sale);P(mutex1);b:=b+1;c:=c+1;V(mutex1);V（buy1）；）；End begin P（sale）；）；P(mutex2)a:=a+1;c:=c+1;V(mutex2);V(buy2);end beginP(sale);P(mutex3);a:=a+1;b:=b+1;V(mutex3);V(buy3);End;Cobegin 7.某多道程序设计系统供用户使用的主存为某多道程序设计系统供用户使用的主存为100KB，磁带机，磁带机2台，打印机台，打印机1台。采用可变分区内存管理，采用静态分配外围设备，忽略用户作台。采用可变分区内存管理，采用静态分配外围设备，忽略用户作用用I/O时间，现有作业序列如下：时间，现有作业序列如下：作业调度采用作业调度采用FCFS策略，优先分配主存低地址区且不准移动已在主策略，优先分配主存低地址区且不准移动已在主存的作业，在主存中的各作业平分存的作业，在主存中的各作业平分CPU时间。现求（时间。现求（1）作业被调度）作业被调度的先后次序？（的先后次序？（2）全部作业运行结束的时间？（）全部作业运行结束的时间？（3）作业平均周转时）作业平均周转时间为多少？间为多少？作业号 进入输入井时间 运行时间 主存需求量 磁带需求 打印机需求 1 8 1 8：00 2500 25分钟分钟 15KB 1 115KB 1 1 2 8 2 8：20 1020 10分钟分钟 30KB 0 130KB 0 1 3 8 3 8：20 2020 20分钟分钟 60KB 1 060KB 1 0 4 8 4 8：30 2030 20分钟分钟 20KB 1 020KB 1 0 5 8 5 8：35 1535 15分钟分钟 10KB 1 110KB 1 1作业号作业号 进入输入井时间进入输入井时间 运行时间运行时间 主存需求量主存需求量 磁带需求磁带需求 打印机需求打印机需求 1 8 1 8：00 2500 25分钟分钟 15KB 1 115KB 1 1 2 8 2 8：20 1020 10分钟分钟 30KB 0 130KB 0 1 3 8 3 8：20 2020 20分钟分钟 60KB 1 060KB 1 0 4 8 4 8：30 2030 20分钟分钟 20KB 1 020KB 1 0 5 8 5 8：35 1535 15分钟分钟 10KB 1 110KB 1 1 0 15K 75K100K-1剩余磁带剩余磁带 打印机打印机 完成完成8：20作业作业2到达但因缺少打印机无法装入内存；到达但因缺少打印机无法装入内存；等待等待1 0 (1)8：30 8：00作业作业1进入内存占用进入内存占用15K内存内存8：20作业作业3到达满足资源要求装入内存到达满足资源要求装入内存 0 0占用占用60K和磁带机和磁带机1个个 作业作业1已经运行了已经运行了20分钟作业分钟作业1剩余剩余5分钟，和作业分钟，和作业3共享共享CPU时间，因此作业时间，因此作业1还需还需10分钟（作分钟（作业业3运行运行5分钟）结束分钟）结束8：30作业作业1完成，释放内存及资源完成，释放内存及资源 1 18:30作业作业4到达资源满足装入内存到达资源满足装入内存 0 1作业作业2因系统剩余内存不足仍无法装入内存因系统剩余内存不足仍无法装入内存因此是作业因此是作业3和和4同时在内存作业同时在内存作业3需还有需还有15分钟，但与作业分钟，但与作业4平分平分cpu时间因此需要时间因此需要30分钟可完成分钟可完成(其中作业其中作业4占占15分钟）分钟）因此因此作业作业3完成时间是完成时间是9：00 (3)9：008:35作业作业5到达因磁带机无法满足到达因磁带机无法满足等待等待9:00作业作业3释放释放60K和磁带机和磁带机1 剩余资源为剩余资源为 1 1 0 15K 75K100K-1作业号作业号 进入输入井时间进入输入井时间 运行时间运行时间 主存需求量主存需求量 磁带需求磁带需求 打印机需求打印机需求 1 81 8：00 2500 25分钟分钟 15KB 1 115KB 1 1 2 8 2 8：20 1020 10分钟分钟 30KB 0 130KB 0 1 3 83 8：20 2020 20分钟分钟 60KB 1 060KB 1 0 4 8 4 8：30 2030 20分钟分钟 20KB 1 020KB 1 0 5 8 5 8：35 1535 15分钟分钟 10KB 1 110KB 1 1 0 15K 75K100K-1剩余磁带剩余磁带 打印机打印机 完成完成9:00作业作业3释放释放60K和磁带机和磁带机1 剩余资源为剩余资源为 1 1作业作业2先于作业先于作业5到达，系统满足作业到达，系统满足作业2需求需求讲作业讲作业2装入内存装入内存 1 0作业作业5因打印机资源不足无法装入内存因打印机资源不足无法装入内存作业作业4（还剩（还剩5分钟）和作业分钟）和作业2共享内存共享内存作业作业4还需还需10分钟结束此时作业分钟结束此时作业2运行了（运行了（5分钟）分钟）(4)9:10 0 75K100K-130K作业作业4释放释放20K内存和磁带机资源内存和磁带机资源 2 0作业作业5仍因缺打印机无法装入内存仍因缺打印机无法装入内存内存只有作业内存只有作业2（剩余（剩余5分钟）在运行分钟）在运行5分钟以后分钟以后2结束结束 (2)9:15作业作业2释放所有资源内存释放所有资源内存30k和和 2 19:15作业作业5装入内存占用装入内存占用10K和和磁带机打印机各磁带机打印机各1个个 1 0 作业作业5独自在内存中运行独自在内存中运行15分钟后结束分钟后结束 (5)9:30释放资源释放资源10K 2 1 l作业调度的次序是1、3、4、2、5l作业1的周转时间30分钟l作业2的周转时间55分钟l作业3的周转时间40分钟l作业4的