计算机学科专业基础综合计算机操作系统-9

1、计算机学科专业基础综合计算机操作系统-9（总分：99.97，做题时间：90分钟）一、综合应用题（总题数：25,分数：100.00）1. 某分时系统中的进程可能出现如图所示的状态变化，回答下列问题:（1）根据图示，该系统采用的是什么进程调度策略？把图示中的每一个状态变化的原因填在下表相应的栏中变化原因123456（分数：4.00） 正确答案：（）解析：题目中没有文字的框应该是就绪队列。（1）系统采用的是时间片轮转法（或者剥夺调度）策略。（2）1是调度程序选择了一个进程可以占用CPU 2是时间片到时；3、4是发出I/O请求；5、6是I/O完成。假设一个计算机系统具有如下性能特征：处理一次中断，平均

2、需要1ms 一次进程调度，平均需要 2ms；将CPU分配给选中的进程，平均需要1ms再假设其定时器芯片每秒产生100次中断。请同答：（分数：4.00）（1）.操作系统将百分之几的 CPU时间用于处理时钟中断？（分数：2.00）正确答案：（）解析：系统每秒100次时钟中断，时间周期是 10ms,因此10%勺CPU时间用于时钟中断处理；（2）.如果操作系统采用轮转法调度，10个时钟中断为1个时间片，那么，操作系统将百分之几的CPU时间用于进程调度（包括调度、分配 CPU和引起调度的时钟中断处理时间 ）?（分数：2.00 ） 正确答案：（）解析：10次时钟中断一个时间片，则一个时间片是100ms,因

3、此进程调度占用 CPU的时间是4%。有以下进程需要调度执行见下表。进程名到达时间/ms运行时间/msP10.09P20.44P31.01P45.54P572（分数：3.99 ）（1）.如果采用非抢占的短进程优先调度算法， 请问这5个进程的平均周转时间和平均响应时间分别是多少（分数:1.33）正确答案：（）解析：10.6ms 6.6ms（2）.如果采用抢占的短进程优先调度算法，请问这5个进程的平均周转时间和平均响应时间分别是多少（分数:1.33） 正确答案：（）解析：6.8ms 2.8ms（3）.采用非抢占的短进程优先调度算法存在平均周转时间较大的问题。为了降低平均周转时间，有这样一 种解决方案

4、：依旧采用非抢占的短进程优先调度算法，但当就绪队列中只有一个进程等待运行时，不马上 运行这个进程，而是让这个进程等待1个单位的时间，然后再选择一个运行时间短的进程投入运行。请问采用这种方法上述 5个进程的平均周转时间和平均响应时间分别是多少？（分数：1.33）正确答案：（）解析：7.48ms 3.48ms2. 设某计算机系统有一块 CPU 一台输入设备、一台打印机。现有两个进程同时进入就绪状态，且进程A先得到CPU运行，进程B后运行。进程A的运行轨迹为：计算 50ms,打印信息100ms,再计算50ms,打印 信息100ms,结束。进程B的运行轨迹为：计算 50ms,输入数据80ms,再计算1

5、00ms,结束。试画出它们 的时序关系图，并说明：（1）开始运行后，CPU有无空闲等待？若有，在哪段时间内等待 ？计算CPU的利用率。（2）进程A运行时有无等待现象？若有，在什么时候出现等待现象 ？（3）进程B运行时有无等待现象？若有，在什么时候出现等待现象 ？（分数：4.00） 正确答案：（） 解析：如图所示。（1）存在CPU空闲（在进程A运行后100150ms,进程A正打印，进程B正输入）。CPU利用率为（300- 50）-300=83.3%（2）进程A运行后无等待现象。 进程B运行后有等待现象（在A开始180200ms；或进程B在运行后130 150ms）。3. 桌子上有一只盘子，每次只

6、能放入或取出一个水果。现有许多苹果和橘子。一家4 口人各行其职。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。请用P操作、V操作来实现4人之间的同步算法。（分数：4.00 ） 正确答案：（）解析：盘子为互斥资源，只能放入一个水果，设信号量empty初值为1;爸爸放苹果前先看看有无空间，若有则抢盘子，放入苹果后向女儿发信号；妈妈放橘子前先看看有无空间，若有则抢盘子，放入橘子后向 儿子发信号；女儿先看有无苹果，若有则抢盘子，取走苹果后发岀盘子置空的信号；儿子看有无橘子，若 有则抢盘子，取走橘子后发岀盘子置空的信号；置空信号应是爸爸和妈妈都可以接收的。该

7、题是生产者/消费者问题的变形，有两对生产者和消费者。生产者需要指明是给哪个消费者的产品，但消费者取走产品 后无须特别通知某个生产者，因为空岀的缓冲区可由两个生产者随意争夺。此处无须设置信号量控制对盘子的互斥访问，因为盘子只能放一个产品；apple表示盘中有苹果，orange表示盘中有橘子，初值均为0=1 then y:=y+1;ifxv=1 then t:=t+2;z:=y; u:=t;end end(分数： 4.00 ) 正确答案： ()解析：遍历 x 是两个进程的共享资源，在进程同时申请访问时很容易出错。若采用顺序执行的方法，结构为y=1 , z=1 , t=2 , u=2；若采用并发的方

8、式，并按顺序执行，则结果为y=0, z=0,出错改正的方法是为临界资源 x设置信号量S,初值为1。程序如下：ParbeginVar x:integer;Process P1 Process P2Vat y,z:integer; Var t,u:integer;Begin BeginP(S); P(S);x:=1; x:=0;y:=0; t:=0;if x =1 then y:=y+1; if x （答案不定）。如果系统中可用资源为（0，6，2），则只可满足P 3的要求，P 3归还后，可满足P 4的要求，P 4归还后， 可满足P 0的要求，P 0归还后，无法满足P 1和P 2的要求，即找不到安全

9、序列，因此系统处在不安全 状态。一个系统中存在某类资源 m个，被n（n n（k-1）+1则一定不会发生死锁（见下表）。序号mnk是否会死锁1633可能会2933 :不会31363不会有3个进程P 1、P 2和P 3并发工作。进程P 1需用资源S 3和S 1 ；进程P 2需用资源S 1和S 2 进程P 3需用资源S 2和S 3。问：（分数：4.00 ）（1）.若对资源分配不加限制，会发生什么情况？为什么？（分数：2.00 ） 正确答案：（）解析：可能会发生死锁。（2）.为保证进程正确工作，应采用怎样的资源分配策略？列举出所有可能的方法。（分数：2.00 ） 正确答案：（）解析：可有几种答案：A.

10、 采用静态分配：由于执行前已获得所需的全部资源，故不会出现占有资源又等待别的资源的现象（或不 会岀现循环等待资源现象）oB. 采用按序分配：不会岀现循环等待资源现象。C. 采用银行家算法：在分配时保证系统处于安全状态。有一阅览室，读者进入时必须先在一张表上进行登记。该表为每一个座位列出一个表目（包括座位号、姓名、阅览时间），读者离开时要撤销登记信息。阅览室有100个座位。（分数：4.00 ）（1）.为描述读者的动作，应编写几个程序，应设置几个进程？程序和进程之间的对应关系如何？（分数:2.00 ）正确答案：（）解析：在本题中，每个读者都可视为一个进程，有多少读者就有多少进程。这些进程称为读者进

11、程，设为 P i （i=0 , 1,）。读者进程P i执行的程序包括：登记、阅览和撤销。每个读者进程的活动都相同，所 以其程序也相同。进程和程序的关系是各读者进程共用同一程序。（2）.试用P，V操作描述这些进程间的同步关系。（分数：2.00 ） 正确答案：（）解析：在读者进程所执行的程序中，对登记和撤销都需互斥执行，其信号量的初值为1,而对进入阅览室也需互斥执行，其信号量为100o现用P, V操作描述如下：读进程 P i （i=0,1,.）P（S1）P(S2)登记V(S2)阅览P(S2)撤销V(S2)V(S1)其中信号量 S1 的初值为 100，信号量 S2 的初值为 1。13. 有一只铁笼子

12、，每次只能放入一只动物。猎手向笼中放入老虎，农民向笼中放入猪，动物园等待取笼中 的老虎，饭店等待取笼中的猪，试用 P，V 操作写出能同步执行的程序。(分数： 4.00 )正确答案： () 解析：这个问题实际上可看作是两个生产者和两个消费者共享了一个仅能存放一件产品的缓冲器。生产者 各自生产不同的产品，消费者各自取自己需要的产品。利用P，V 操作编程为：beginsemaphore:S,S1,S2;ParbeginProcess hunterbeginL1:have a tiger;P(S);put a tiger;V(S1);go to L1;end;Process peasantbeginL

13、2:have a pig;P(S);put a pig;V(S2);go to L2;end;Process hotelbeginL3:P(S1);get a pig;V(S);eat a pig;go to L3;end;Process zoobeginL4:P(S2);get a tiger;V(S);eat a tiger; goto L4;end;parend14. 有三个进程 P A ，P B 和 P C 合作解决文件打印问题： P A 将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录； P B 将缓冲区 1 的内容复制到缓冲区 2，每执行一次复制一个记录； P C 将缓冲区

14、 2 的内容打印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录大小。请用P，V 操作来保证文件的正确打印。(分数： 4.00 ) 正确答案： ()解析：在本题中，进程 PA PB, PC之间的关系为：PA与PB共用一个单缓冲区，而 PB又与PC共用一个单 缓冲区。当缓冲区1为空时，进程PA可将一个记录读入其中；若缓冲区1中有数据且缓冲区2为空，则进程PB可将记录从缓冲区1复制到缓冲区2中；若缓冲区2中有数据，则进程 PC可以打印记录。在其他条 件下，相应进程必须等待。事实上，这是一个生产者消费者问题。为遵循这一同步规则，应设置四个信号量 empty1 ， empty2 ， full1

15、， full2 ，信号量 empty1 及 empty2 分别 表示缓冲区 1 及缓冲区 2 是否为空，其初值为 1 ；信号量 full1 及 full2 分别表示缓冲区 1 及缓冲区 2 是 否有记录可供处理，其初值为 0。其同步描述如下：int empty1=1;int empty2=1;int full1=0;int full2=0;main() cobeginPA();PB();PC();coendPA() while(1) 从磁盘读一个记录 :P(empty1);将记录存入缓冲 1;V(full1);PB() while(1) 从缓冲区 1 中取出记录 :V(empty1);P(em

16、pty1);将记录存入缓冲 2;V(full2);PC() while(1) P(full2);从缓冲区 2 中取出记录 ;V(empty2);打印记录 ;本题也是一个典型的生产者一消费者问题。其中的难点在于PB既是一个生产者又是一个消费者。15. 某数据库有一个写进程，多个读进程，它们之间读、写操作的互斥要求是：写进程正在写该数据库时不 能有其他进程读该数据库，也不能有其他进程写该数据库；读进程之间不互斥，可以同时读该数据库。请 用信号量及P、V操作描述这一组进程的工作过程。(分数： 4.00 ) 正确答案： () 解析：在本题中，允许读进程同时读数据库，但写进程正在写数据库时不允许其他进程

17、读数据库，也不允 许其他进程写该数据库。为了解决读、写进程之间的同步，应设置两个信号量和一个共享变量：读互斥信号量rmutex，用于使读进程互斥地访问共享变量count，其初值为1写互斥信号量 wmutex用于实现写进程与读进程的互斥及写进程与写进程的互斥，其初值为1；共享变量 count 用于记录当前正在读数据库的读进程数目，初值为 0。其工作过程如下：int rmutex=1;int wmutex=1;int count=0;main() cobeginReader();Writer();coendReader() while(1) P(rmutex):if(count=0)P(wmute

18、x);/ 当第一个读进程读数据库时 , 阻止写进程写 ;count+;V(rmutex):读数据库 ;P(rmutex);count-;if(count=0)V(wmutex);/ 当最后一个读进程读完数据库时 , 允许写进程写 ;V(rmutex);Writer() while(i) P(wmutex);写数据库 ;V(wmutex);在本题中，要注意对信号量 rmutex意义的理解。rmutex是一个互斥信号量，用于使读进程互斥地访问共 享变量count。该信号量并不表示读进程的数目，表示读进程数目的是共享变量count。当一个读进程要读数据库时，应将读进程计数count增加1。如果此前（

19、count加1以前）数据库中无读进程， 还应对写互斥信 号量wmutex做P操作，这样若数据库中无写进程，则通过P操作组织写进程写；若数据库中有写进程，则通过P操作让读进程等待。同理，当一个读进程完成读数据库操作时，应将读进程计数count减少1 ；如果此时（count减1以后）数据库中已无读进程，还应对写互斥信号wmutex作V操作，以允许写进程写。16.抽烟问题：有一个烟草代理和三个抽烟者。抽烟者若要抽烟，必须具有烟草、烟纸和火柴。三个抽烟者 中，一个缺烟叶、一个缺烟纸、一个缺火柴。烟草代理会源源不断地分别供应烟叶、烟纸和火柴，并将它 们放在桌上。如果他放的是烟叶，则缺烟叶的抽烟者会拾起烟

20、叶，制作香烟，然后抽烟；其他类推。试用 信号量同步烟草代理和三个抽烟者。（分数：4.00） 正确答案：()解析：semaphore smoker3; 初始0,三个抽烟者semaphore material3; 初始 0,三种原料semaphore agent;/ 初始 1,供应商int turn;/ 初始0,轮到谁agent:while(1) wait(agent);signal(smokerturn);signal(material(turn+1)%3);signal(material(turn+2)%3);turn=(turn+1)%3smoker i:while(1) wait(smok

21、eri);wait(material(i+1)%3);Wait(material(i+2)%3);signal(agent);今有三个批处理作业。第一个作业10:00到达，需要执行2小时。第二个作业10:10到达，需要执行1小时。第三个作业10:25到达，需要执行25分钟。分别采取如下(见表(a)，表(b)，表(c)三种作业调度算 法：(a)算法一作业号到达时间开始执行时间执行结束时间110:0010:0012:00210:1012:0013:00310:2513:0013:25(b)算法二作业号到达时间开始执行时间执行结束时间1110:0011:5012:00210:1010:5013:00

22、310:2510:2513:25(c)算法三作业号到达时间开始执行时间执行结束时间110:0010:0012:00210:1012:2513:25310:2512:0012:25(分数:4.00 )(1).计算各调度算法下的作业平均周转时间。(分数：2.00 )正确答案：()解析：采用调度算法1时：作业1的周转时间为2h ；作业2的周转时间为2.83h ；作业3的周转时间为3h ；平均周转时间为：(2+2.83+3)/3=2.61(h)。采用调度算法2时：作业1的周转时间为3.83h ；作业2的周转时间为1.67h ；作业3的周转时间为0.42h ；平均周转时间为：(3.83+1.67+0.4

23、2)/3=1.97(h)。采用调度算法3时：作业1的周转时间为2h ；作业2的周转时间为3.25h ；作业3的周转时间为2h ；平均周转时间为：(2+3.25+2)/3=2.42(h)。(2).调度算法一、三分别是什么作业调度算法？(分数：2.00)正确答案：()解析：调度算法1是按照作业到达的先后次序执行的，所以它是先来先服务调度算法。调度算法3是按照作业执行时间从短到长的次序执行的，所以它是短作业优先调度算法。17.在单CPU和两台输入/输出设备(I 1，I 2)的多道程序设计环境下，同时投入三个作业Job 1，Job 2，Job 3运行。这三个作业对 CPU和输入/输出设备的使用顺序和时

24、间如下所示：Job 1 :1 2 (30ms);CPU(10ms);l1 (30ms) ； CPU(10ms)； I 2 (20ms)Job 2 :I 1 (20ms) ； CPU(20ms)； I 2 (40ms)Job 3 :CPU(30ms) ； I 1 (20ms) ； CPU(10ms); I 1 (10ms)假定CPU I 1，I 2都能并行工作，Job 1优先级最高，Job 2次之，Job 3优先级最低，优先级高的作业 可以抢占优先级低的作业的CPU但不抢占I 1和I 2。试求：(1)三个作业从投入到完成分别需要的时间。从投入到完成的CPU利用率。I/O设备利用率。(分数：4.0

25、0) 正确答案：()解析：三个作业并发执行时的工作情况如下：Job i 的执行顺序为：I2 (30ms) ； CPU(10ms);I 1 (30ms) ； CPU(10ms);等待I 2 (10ms) ；I 2 (20ms)。Job 2 的执行顺序为：I1 (20ms) ； CPU(10ms);等待 CPU(10ms); CPU(10ms);I 2 (40ms)；Job 3 的执行顺序为：CPU(20ms);等待 CPU(30ms); CPU(10ms);等待 I 1 (10ms) ; I 1 (20ms); CPU(10ms); I 1 (10ms)。(1) Job 1从投入到运行完成需要 110ms, Job 2从投入到运行完成需要 90ms, Job 3从投入到运行完成需 要 110ms。(2) CPU在时间段6070ms, 8090ms, 100110ms期间空闲，所以CPU的利用率为：(110-30)/110=72.7%。 设备I 1在时间段2040ms, 90100ms期间空闲，所以设备 I 1的利用率为：(110-30)/110=