1、计算机学科专业基础综合计算机操作系统-9 及答案解析(总分：99.97，做题时间：90 分钟)一、综合应用题(总题数：25，分数：100.00)1.某分时系统中的进程可能出现如图所示的状态变化，回答下列问题： （分数：4.00）_假设一个计算机系统具有如下性能特征：处理一次中断，平均需要 1ms；一次进程调度，平均需要 2ms；将 CPU 分配给选中的进程，平均需要 1ms。再假设其定时器芯片每秒产生 100 次中断。请同答：（分数：4.00）(1).操作系统将百分之几的 CPU 时间用于处理时钟中断?（分数：2.00）_(2).如果操作系统采用轮转法调度，10 个时钟中断为 1 个时间片，那
2、么，操作系统将百分之几的 CPU 时间用于进程调度(包括调度、分配 CPU 和引起调度的时钟中断处理时间)?（分数：2.00）_有以下进程需要调度执行见下表。 进程名 到达时间/ms 运行时间/ms P1 0.0 9 P2 0.4 4 P3 1.0 1 P4 5.5 4 P5 7 2 （分数：3.99）(1).如果采用非抢占的短进程优先调度算法，请问这 5 个进程的平均周转时间和平均响应时间分别是多少?（分数：1.33）_(2).如果采用抢占的短进程优先调度算法，请问这 5 个进程的平均周转时间和平均响应时间分别是多少?（分数：1.33）_(3).采用非抢占的短进程优先调度算法存在平均周转时间
3、较大的问题。为了降低平均周转时间，有这样一种解决方案：依旧采用非抢占的短进程优先调度算法，但当就绪队列中只有一个进程等待运行时，不马上运行这个进程，而是让这个进程等待 1 个单位的时间，然后再选择一个运行时间短的进程投入运行。请问采用这种方法上述 5 个进程的平均周转时间和平均响应时间分别是多少?（分数：1.33）_2.设某计算机系统有一块 CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态，且进程 A先得到 CPU 运行，进程 B 后运行。进程 A 的运行轨迹为：计算 50ms，打印信息 100ms，再计算 50ms，打印信息 100ms，结束。进程 B 的运行轨迹为：计算 50
4、ms，输入数据 80ms，再计算 100ms，结束。试画出它们的时序关系图，并说明： (1)开始运行后，CPU 有无空闲等待?若有，在哪段时间内等待?计算 CPU 的利用率。 (2)进程 A 运行时有无等待现象?若有，在什么时候出现等待现象? (3)进程 B 运行时有无等待现象?若有，在什么时候出现等待现象? （分数：4.00）_3.桌子上有一只盘子，每次只能放入或取出一个水果。现有许多苹果和橘子。一家 4 口人各行其职。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。请用P 操作、V 操作来实现 4 人之间的同步算法。 （分数：4.00）_4.8
5、位哲学家围坐一方桌，桌子每边坐 2 位，每位哲学家面前放一盘面条，桌子四角和每一边(中间)各放着一把叉子。哲学家只进行两种活动：吃饭和思考问题。当一位哲学家感到饥饿时，先取自己边上的叉子，拿到之后，再取自己角上的叉子，两把叉子到手才能用餐，吃完后把两把叉子放回原处。写一段程序描述哲学家的行为，并讨论这种安排是否可能导致死锁。 （分数：4.00）_5.下面是两个并发执行的进程。它们能正确运行吗?若不能请举例说明，并改正之。 Var x:integer; Process p1 Process p2 Var y,z:integer; Var t,u:integer; Begin Begin x:=1
6、; x:=0; y:=0; t:=0; if x=1 then y:=y+1; if x=1 then t:=t+2; z:=y; u:=t; end end （分数：4.00）_6.兄弟俩共同使用一个账号，每次限存或取 10 元，存钱与取钱的进程分别如下所示： begin amount:integer: amount:=0; cobegin Process SAVE m1:integer: begin m1:=amount: m1:=m1+10; amount:=m1; end; Process TAKE m2:integer; begin m2:=amount; m2:=m2-10; am
7、ount:=m2; end; coend; end; 由于兄弟俩可能同时存钱和取钱，因此两个进程是并发的。若哥哥先存了两次钱，但在第 3 次存钱的时候弟弟在取钱，请问最后账号 amount 上面可能出现的值?如何用 P 操作、V 操作实现两并发进程的互斥执行? （分数：4.00）_7.战地指挥官通过无线电不断地向他的 3 个士兵下达作战指令，但是他必须在得到所有士兵对前一条指令的“acknowledgement”之后才能下达新的指令。请使用 P 操作、V 操作进行指挥官和士兵之间的协同管理，并对解题思路进行简要解释。 （分数：4.00）_8.假定一个阅览室最多可容纳 100 人，读者进入和离开
8、阅览室时都必须在阅览室门口的一个登记表上进行登记，而且每次只允许一人进行登记操作。用信号量实现该过程。 （分数：4.00）_用 P 操作、V 操作解决读者/写者问题的正确程序如下： Semaphore:S,Sr; int rc: S=1;Sr=1;rc=0; Reader() P(Sr); rc=rc+1; if(rc=1) then P(S); V(Sr); read_file(); P(Sr); rc=rc-1; if(rc=0) then V(S); V(Sr); Writer() P(S); write_file(); V(S); 请回答：（分数：3.99）(1).信号量 Sr 的作用
9、；（分数：1.33）_(2).程序中什么语句用于读、写互斥，写、写互斥；（分数：1.33）_(3).若规定仅允许 5 个进程同时读，怎样修改程序?（分数：1.33）_9.用信号量和 P 操作、V 操作编写程序：多个读进程和多个写进程共享一个文件。要求： (1)写操作只能互斥、独立进行； (2)读操作可以同时共享读文件； (3)当有写操作请求时，禁止新的读操作；有正在读文件的进程时，在读操作完成后进行写文件操作。 （分数：4.00）_10.假设具有 5 个进程的集合 P=P 0 ，P 1 ，P 2 ，P 3 ，P 4 ，系统中有 3 类资源 A、B、C，假设在某时刻有如下状态： （分数：4.00
10、）_一个系统中存在某类资源 m 个，被 n(nm)个进程共享，即每个进程至少需要一个资源。资源的分配和释放必须一个一个地进行，请证明在以下两个条件下系统是否会发生死锁：（分数：4.00）(1).每个进程需要资源的最大数在 1m 之间；（分数：2.00）_(2).所有进程需要的资源总数小于 m+n。（分数：2.00）_11.某银行计算机系统要实现一个电子转账功能，基本的业务流程是首先对转出方和转入方的账号进行加锁，然后进行转账业务，最后对转出方和转入方的账号进行解锁。如果不采取任何措施，系统会不会发生死锁?为什么?请设计一种能够避免死锁的方法。 （分数：4.00）_12.系统有同类资源 m 个，
11、供 n 个进程共享，如果每个进程对资源的最大需求量为由，问 m，n，k 的值分别是下列情况时(见下表)，是否会发生死锁? 序号 m n k 是否会死锁 说明 1 6 3 3 2 9 3 3 3 13 6 3 （分数：4.00）_有 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).为保证进程正确工作，应采用怎样的资源分配策略?列举出所有可能的方法。（分数
12、：2.00）_有一阅览室，读者进入时必须先在一张表上进行登记。该表为每一个座位列出一个表目(包括座位号、姓名、阅览时间)，读者离开时要撤销登记信息。阅览室有 100 个座位。（分数：4.00）(1).为描述读者的动作，应编写几个程序，应设置几个进程?程序和进程之间的对应关系如何?（分数：2.00）_(2).试用 P，V 操作描述这些进程间的同步关系。（分数：2.00）_13.有一只铁笼子，每次只能放入一只动物。猎手向笼中放入老虎，农民向笼中放入猪，动物园等待取笼中的老虎，饭店等待取笼中的猪，试用 P，V 操作写出能同步执行的程序。 （分数：4.00）_14.有三个进程 P A ，P B 和 P
13、 C 合作解决文件打印问题：P A 将文件记录从磁盘读入主存的缓冲区 1，每执行一次读一个记录；P B 将缓冲区 1 的内容复制到缓冲区 2，每执行一次复制一个记录；P C 将缓冲区2 的内容打印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录大小。请用 P，V 操作来保证文件的正确打印。 （分数：4.00）_15.某数据库有一个写进程，多个读进程，它们之间读、写操作的互斥要求是：写进程正在写该数据库时不能有其他进程读该数据库，也不能有其他进程写该数据库；读进程之间不互斥，可以同时读该数据库。请用信号量及 P、V 操作描述这一组进程的工作过程。 （分数：4.00）_16.抽烟问题：有一个
14、烟草代理和三个抽烟者。抽烟者若要抽烟，必须具有烟草、烟纸和火柴。三个抽烟者中，一个缺烟叶、一个缺烟纸、一个缺火柴。烟草代理会源源不断地分别供应烟叶、烟纸和火柴，并将它们放在桌上。如果他放的是烟叶，则缺烟叶的抽烟者会拾起烟叶，制作香烟，然后抽烟；其他类推。试用信号量同步烟草代理和三个抽烟者。 （分数：4.00）_今有三个批处理作业。第一个作业 10:00 到达，需要执行 2 小时。第二个作业 10:10 到达，需要执行 1 小时。第三个作业 10:25 到达，需要执行 25 分钟。分别采取如下(见表(a)，表(b)，表(c)三种作业调度算法： (a) 算法一 作业号 到达时间 开始执行时间 执行
15、结束时间 1 10:00 10:00 12:00 2 10:10 12:00 13:00 3 10:25 13:00 13:25 (b) 算法二 作业号 到达时间 开始执行时间 执行结束时间 1 10:00 11:50 12:00 2 10:10 10:50 13:00 3 10:25 10:25 13:25 (c) 算法三 作业号 到达时间 开始执行时间 执行结束时间 1 10:00 10:00 12:00 2 10:10 12:25 13:25 3 10:25 12:00 12:25 （分数：4.00）(1).计算各调度算法下的作业平均周转时间。（分数：2.00）_(2).调度算法一、三分
16、别是什么作业调度算法?（分数：2.00）_17.在单 CPU 和两台输入/输出设备(I 1 ，I 2 )的多道程序设计环境下，同时投入三个作业 Job 1 ，Job 2 ，Job 3 运行。这三个作业对 CPU 和输入/输出设备的使用顺序和时间如下所示： Job 1 :I 2 (30ms);CPU(10ms);I 1 (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 都能并行工作，J
17、ob 1 优先级最高，Job 2 次之，Job 3 优先级最低，优先级高的作业可以抢占优先级低的作业的 CPU，但不抢占 I 1 和 I 2 。试求： (1)三个作业从投入到完成分别需要的时间。 (2)从投入到完成的 CPU 利用率。 (3)I/O 设备利用率。 （分数：4.00）_3 种资源 A(17)、B(5)、C(20)，5 个进程 P 1 、P 2 、P 3 、P 4 、P 5 ，初始时刻的系统状态(见下表)：进程 最大资源需求量 已经分配的数量 剩余的数量 A B C A B C A B C P 1 5 5 9 2 1 2 P 2 5 3 6 4 0 2 P 3 4 0 11 4 0
18、 5 P 4 4 2 5 2 0 4 P 5 2 4 3 1 4 2 3 3 （分数：3.99）(1).初始时刻是否是安全状态?给出安全序列。（分数：1.33）_(2).如果 P2 请求资源(0，3，4)，能否实施资源分配?（分数：1.33）_(3).在(2)的条件下，P4 请求(2，0，1)能否实现资源分配?为什么?（分数：1.33）_计算机学科专业基础综合计算机操作系统-9 答案解析(总分：99.97，做题时间：90 分钟)一、综合应用题(总题数：25，分数：100.00)1.某分时系统中的进程可能出现如图所示的状态变化，回答下列问题： （分数：4.00）_正确答案：()解析：题目中没有文
19、字的框应该是就绪队列。(1)系统采用的是时间片轮转法(或者剥夺调度)策略。(2)1是调度程序选择了一个进程可以占用 CPU；2 是时间片到时；3、4 是发出 I/O 请求；5、6 是 I/O 完成。假设一个计算机系统具有如下性能特征：处理一次中断，平均需要 1ms；一次进程调度，平均需要 2ms；将 CPU 分配给选中的进程，平均需要 1ms。再假设其定时器芯片每秒产生 100 次中断。请同答：（分数：4.00）(1).操作系统将百分之几的 CPU 时间用于处理时钟中断?（分数：2.00）_正确答案：()解析：系统每秒 100 次时钟中断，时间周期是 10ms，因此 10%的 CPU 时间用于
20、时钟中断处理；(2).如果操作系统采用轮转法调度，10 个时钟中断为 1 个时间片，那么，操作系统将百分之几的 CPU 时间用于进程调度(包括调度、分配 CPU 和引起调度的时钟中断处理时间)?（分数：2.00）_正确答案：()解析：10 次时钟中断一个时间片，则一个时间片是 100ms，因此进程调度占用 CPU 的时间是 4%。有以下进程需要调度执行见下表。 进程名 到达时间/ms 运行时间/ms P1 0.0 9 P2 0.4 4 P3 1.0 1 P4 5.5 4 P5 7 2 （分数：3.99）(1).如果采用非抢占的短进程优先调度算法，请问这 5 个进程的平均周转时间和平均响应时间分
21、别是多少?（分数：1.33）_正确答案：()解析：10.6ms 6.6ms(2).如果采用抢占的短进程优先调度算法，请问这 5 个进程的平均周转时间和平均响应时间分别是多少?（分数：1.33）_正确答案：()解析：6.8ms 2.8ms(3).采用非抢占的短进程优先调度算法存在平均周转时间较大的问题。为了降低平均周转时间，有这样一种解决方案：依旧采用非抢占的短进程优先调度算法，但当就绪队列中只有一个进程等待运行时，不马上运行这个进程，而是让这个进程等待 1 个单位的时间，然后再选择一个运行时间短的进程投入运行。请问采用这种方法上述 5 个进程的平均周转时间和平均响应时间分别是多少?（分数：1.
22、33）_正确答案：()解析：7.48ms 3.48ms2.设某计算机系统有一块 CPU、一台输入设备、一台打印机。现有两个进程同时进入就绪状态，且进程 A先得到 CPU 运行，进程 B 后运行。进程 A 的运行轨迹为：计算 50ms，打印信息 100ms，再计算 50ms，打印信息 100ms，结束。进程 B 的运行轨迹为：计算 50ms，输入数据 80ms，再计算 100ms，结束。试画出它们的时序关系图，并说明： (1)开始运行后，CPU 有无空闲等待?若有，在哪段时间内等待?计算 CPU 的利用率。 (2)进程 A 运行时有无等待现象?若有，在什么时候出现等待现象? (3)进程 B 运行
23、时有无等待现象?若有，在什么时候出现等待现象? （分数：4.00）_正确答案：()解析：如图所示。 3.桌子上有一只盘子，每次只能放入或取出一个水果。现有许多苹果和橘子。一家 4 口人各行其职。爸爸专向盘子中放苹果，妈妈专向盘子中放橘子，儿子专等吃盘子中的橘子，女儿专等吃盘子中的苹果。请用P 操作、V 操作来实现 4 人之间的同步算法。 （分数：4.00）_正确答案：()解析：盘子为互斥资源，只能放入一个水果，设信号量 empty 初值为 1；爸爸放苹果前先看看有无空间，若有则抢盘子，放入苹果后向女儿发信号；妈妈放橘子前先看看有无空间，若有则抢盘子，放入橘子后向儿子发信号；女儿先看有无苹果，若
24、有则抢盘子，取走苹果后发出盘子置空的信号；儿子看有无橘子，若有则抢盘子，取走橘子后发出盘子置空的信号；置空信号应是爸爸和妈妈都可以接收的。该题是生产者/消费者问题的变形，有两对生产者和消费者。生产者需要指明是给哪个消费者的产品，但消费者取走产品后无须特别通知某个生产者，因为空出的缓冲区可由两个生产者随意争夺。此处无须设置信号量控制对盘子的互斥访问，因为盘子只能放一个产品；apple 表示盘中有苹果，orange 表示盘中有橘子，初值均为0。 Parbegin 爸爸:begin L1:p(empty); 放苹果; V(apple); Goto L1; end; 妈妈:begin L2:P(emp
25、ty); 放橘子; V(orange); Goto L2; end; 女儿:begin L3:P(apple); 取苹果; V(empty); Goto L3; end; 儿子:begin L4:p(orange); 取橘子; V(empty); Goto L4; end; Parend4.8 位哲学家围坐一方桌，桌子每边坐 2 位，每位哲学家面前放一盘面条，桌子四角和每一边(中间)各放着一把叉子。哲学家只进行两种活动：吃饭和思考问题。当一位哲学家感到饥饿时，先取自己边上的叉子，拿到之后，再取自己角上的叉子，两把叉子到手才能用餐，吃完后把两把叉子放回原处。写一段程序描述哲学家的行为，并讨论这种
26、安排是否可能导致死锁。 （分数：4.00）_正确答案：()解析：对 8 位哲学家顺序编号为：P 1 ，P 2 ，P 3 ，P 4 ，P 5 ，P 6 ，P 7 ，P 8 ，对 8 个叉子顺序编号为：1，2，3，4，5，6，7，8。讨论每个哲学家的行为过程，再总结出规律，发现下标为奇数的哲学家是先拿左边的叉子，再拿右边的叉子；下标为偶数的哲学家先拿右边的叉子，再拿左边的叉子。由此得到以下程序，信号量 Si的初值均为 1。又因为编号 P 8 的哲学家拿起的是 8 号和 1 号叉子，因此用取余运算令其返回 1。 if(i%2=0) P(Si); P(S(i+1)%8); 吃; V(Si); V(S(
27、i+1)%8); else P(Si+1); P(Si); 吃; V(Si+1); V(Si); 该题不可能死锁。死锁产生的条件是所有的哲学家都从同一边拿起叉子，导致每个进程占用一个资源(叉子)而等待另一个资源，但该题的取叉子方式避免了这一现象。5.下面是两个并发执行的进程。它们能正确运行吗?若不能请举例说明，并改正之。 Var x:integer; Process p1 Process p2 Var y,z:integer; Var t,u:integer; Begin Begin x:=1; x:=0; y:=0; t:=0; if x=1 then y:=y+1; if x=1 then
28、 t:=t+2; z:=y; u:=t; end end （分数：4.00）_正确答案：()解析：遍历 x 是两个进程的共享资源，在进程同时申请访问时很容易出错。若采用顺序执行的方法，结构为 y=1，z=1，t=2，u=2；若采用并发的方式，并按顺序执行，则结果为 y=0，z=0，出错。改正的方法是为临界资源 x 设置信号量 S，初值为 1。程序如下： Parbegin Var x:integer; Process P1 Process P2 Vat y,z:integer; Var t,u:integer; Begin Begin P(S); P(S); x:=1; x:=0; y:=0;
29、t:=0; if x=1 then y:=y+1; if x=1 then t:=t+2; V(S); V(S); z:=y; u:=t; end end Parend6.兄弟俩共同使用一个账号，每次限存或取 10 元，存钱与取钱的进程分别如下所示： begin amount:integer: amount:=0; cobegin Process SAVE m1:integer: begin m1:=amount: m1:=m1+10; amount:=m1; end; Process TAKE m2:integer; begin m2:=amount; m2:=m2-10; amount:=
30、m2; end; coend; end; 由于兄弟俩可能同时存钱和取钱，因此两个进程是并发的。若哥哥先存了两次钱，但在第 3 次存钱的时候弟弟在取钱，请问最后账号 amount 上面可能出现的值?如何用 P 操作、V 操作实现两并发进程的互斥执行? （分数：4.00）_正确答案：()解析：哥哥存两次钱后，amount=20，第三次存钱时，弟弟正在取钱，因没有对 amount 互斥操作，故发生错误。最后 amount 上可能出现的值应与两进程相对执行速度有关；若 TAKE 执行结束后 SAVE 才开始，则剩 20 元；若 SAVE 执行结束后 TAKE 才开始，也剩 20 元；问题就出在两个进程
31、交替使用 CPU 时，则会出现不同值。关键在于最后被执行的语句是 amount:=m1，还是 amount:=m2，若先 amount:=m1 后amount:=m2，则 amount=10，反之，先 amount:=m2 后 amount:=m1，则 amount=30。设信号量 mutex(初值为 1)控制两进程对变量 amount 的互斥使用。正确过程如下： begin amount:integer; amount:=0; cobegin Process SAVE m1:integer; Begin P(mutex); m1:=amount; m1:=m1+10; amount:=m1;
32、 V(mutex); end; Process TAKE m2:integer; Begin P(mutex); m2:=amount; m2:=m2-10; amount:=m2; V(mutex); end; coend; end;7.战地指挥官通过无线电不断地向他的 3 个士兵下达作战指令，但是他必须在得到所有士兵对前一条指令的“acknowledgement”之后才能下达新的指令。请使用 P 操作、V 操作进行指挥官和士兵之间的协同管理，并对解题思路进行简要解释。 （分数：4.00）_正确答案：()解析：思路如下： type semaphore=monitor; var acknowl
33、edgement1,acknowledgement2,acknowledgement3:boolean; x,y:condition; a,b,c:integer; 指挥官:begin while acknowledgement1=false or acknowledgement2=false or acknowledgement3=false do x.wait; 下达命令; a:=1; b:=1; c:=1; y.signal; end 士兵 1:begin while a=0 do y.wait; 接收命令; acknowledgement1=true; x.signal; end 士兵
34、 2:begin while a=0 do y.wait; 接收命令; acknowledgement2:true; x.signal: end 士兵 3:begin while a=0 do y.wait; 接收命令; acknowledgement3:true; X.signal; end begin a:=0; b:=0; c:=0; acknowledgement1:=false; acknowledgement2:=false; acknowledgement3:=false; end8.假定一个阅览室最多可容纳 100 人，读者进入和离开阅览室时都必须在阅览室门口的一个登记表上进行
35、登记，而且每次只允许一人进行登记操作。用信号量实现该过程。 （分数：4.00）_正确答案：()解析：读者有任意多个，但进入阅览室读最多为 100 人，为此可设一个信号量 s，代表空座位的数目；另登记表为临界资源，需设一个用于互斥的信号量 mutex，防止 2 个及 2 个以上的读者进程同时对此表访问。每个读者的动作包括进入、阅读、离开。 struct semaphore:s,mutex=100,1; cobegin void readeri(void)(i=1,2,.,k) while(TRUE) P(s); P(mutex); 查登记表,置某座位为占用; V(mutex); . reading; . P(mutex); 查登记表,置某座位为
