操作系统课外习题答案

1、第二章1. 有三个进程PA、PB和PC合作解决文件打印问题：PA将文件记录从磁盘读入主存的缓冲区1，每执行一次读一个记录；PB将缓冲区1的内容复制到缓冲区2，每执行一次复制一个记录；PC将缓冲区2的内容打印出来，每执行一次打印一个记录。缓冲区的大小等于一个记录的大小。请用PV操作来保证文件的正确打印。Empty1,empty2,full1,full2:semaphore; （1分）Empty1=empty2=1; （1分）Full1=full2=0; （1分） Main() （1分）Cobegin PA(); PB(); PC();coend;PA() （2分）While(1) 从磁盘读一个记

2、录；P(empty1);将记录存入缓冲区1；V(full1);PB() （2分） While(1) P(full1); 从缓冲区1中取出记录； V(empty1); P(empty2); 将记录存入缓冲区2； V(full2);PC() （2分） While(1) P(full2); 从缓冲区2中取出记录； V(empty2); 打印记录； 2有一只最多能装2只兔子的铁笼子，猎人仅能向笼子中放入兔子（每次只能放入1只），若笼子是满的，则猎人必须等待；饭店老板仅能从笼子中取兔子（每次只能取出1只），若笼子是空的则他也必须等待。假设初始时笼子是空的。定义信号量并初始化，使用P、V操作模拟猎人和饭店

3、老板进程之间的同步与互斥。mutex,empty,fullsemaphore; 1分mutex=1,empty=2;full=0; 2分 以下内容7分cobeginpcocedure Hunter(x)begin：P（empty）；P（mutex）；/放兔子；V（mutex）；V（full）；Goto begin；pcocedure Boss(x)begin：P（full）；P（mutex）；/放兔子；V（mutex）；V（empty）；Goto begin；coend;3桌上有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子，儿子专等吃盘中的桔子，女儿专等吃苹果。试用P、V操

4、作实现爸爸、儿子、女儿三个并发进程的同步。分析：在本题中，爸爸、儿子和女儿共用一个盘子，盘子一次只能放一个水果。当盘子为空时，爸爸可以试着将一个水果放入盘中，若放入盘子中的是橘子，则允许儿子吃，女儿必须等待；若放入盘子中的是苹果，则允许女儿吃，儿子必须等待。 在本题中，应设置3个信号量dish、apple、orange，信号量dish表示盘子是否为空，其初值为1；信号量apple表示盘中是否有苹果，其初值为0；信号量orange表示盘中是否有橘子，其初值为0。进程之间的同步描述如下：Semaphore dish=1;Semaphore apple,orange=0;Main() cobegin

5、 father(); son(); daughter(); coendFather() while(true) p(dish); 将一水果放入盘中； If 盘中放的是橘子 v(orange) Else if 盘中放的是苹果 v(apple); Son() daughter() while(true) while(true) p(orange); p(apple); 从盘中取出橘子； 从盘中取出苹果； v(dish); v(dish); 吃橘子； 吃苹果； 4、一阅览室只能容纳150人，当少于150人时，可以进入，否则，需在外等候，若将每一个读者作为一个进程，请用P、V操作编程(类C、类pasc

6、al)，并写出信号量的初值。Semaphore empty=150,full=0;（每个信号量1分，共3分）Semaphore mutex=1Process In:       While (true) P(empty); （P操作顺序写对2分，其余部分2分，共4分） P(mutex); 第i个人进入阅览室； V(mutex); V(full) Process Out:       While (true) P(full); （P操作顺序写对2分，其余部分1分，共3分） P(

7、mutex); 第i个人离开阅览室； V(mutex); V(empty) 5、如图所示的交通管理例子（各方向上的汽车是单行、直线行使），试用PV操作实现各方向上汽车行驶的同步。路口B路口A马路可停n辆汽车解：路口A和路口B可以被看成为临界资源，分别为其设定互斥信号量crossA和crossB，它们的初值设定为1。因为中间一段马路可以停靠n辆车子，所以设置资源信号量length，初值设定为n。A路口方向向下的车子：（2分）P(crossA);通过路口A;V(crossA);B路口方向向下的车子：（2分）P(crossB);通过路口B;V(crossB);方向向右的车子：（6分）P(length

8、);P(crossA); 通过路口A;V(crossA); 在马路中行进；P(crossB); 通过路口B;V(crossB);V(length);第三章1. 作业名 进入时间 运行时间（分） 需内存量KB 磁带机 打印机 A 8:00 25 15 1 1 B 8:20 10 30 0 1 C 8:20 20 60 1 0 D 8:30 20 20 1 0 E 8:35 15 10 1 1 有用户空间100KB，磁带机2台，打印机1台，并规定作业相应程序装入内存连续区域，并不能被移动，作业与进程均采用FCFS算法问题如下：1、作业调度选中各作业的次序是什么？2、最大的作业周转时间是多少？3、平

9、均周转时间是多少？解答：（1）作业调度选中作业的次序是：A,C,D,B,E （2）作业A的周转时间是：8:25-8:00=25分钟 作业B的周转时间是：9:15-8:20=55分钟 作业C的周转时间是：8:45-8:20=25分钟 作业D的周转时间是：9:05-8:30=35分钟 作业E的周转时间是：9:30-8:35=55分钟 因此最大的作业周转时间是：55分钟 (3) 平均的周转时间是：T=(25+55+25+35+55)/5=39分钟2、在单CPU和两台输入输出设备（I1，I2）的多道程序设计环境下，同时投入3个作业Job1、Job2、Job3运行。这3个作业对CPU和输入输出设备的使用

10、顺序和时间如下所示： Job1:I2(30ms); CPU(10ms); I1(30ms); CPU(10ms); I2(20ms) Job2:I1(20ms); CPU(20ms); I2(40ms); Job3:CPU(30ms); I1(20ms); CPU(10ms); I1(10ms) 假定CPU、I1、I2都能并行工作，Job1优先级最高，Job2次之，Job3优先级最低，优先级高的作业可以抢占优先级低的作业的CPU但不抢占I1和I2。试求：（1） 3个作业从投入到完成分别需要的时间。（2） 从投入到完成的CPU利用率。（3） 输入输出设备利用率。 解： 时间 010 20 30

11、40 50 60 70 80 90 100 110CPUJob3Job2Job1Job2Job3等待Job1等待Job3等待IO1 Job2 等待 Job1 Job3等待Job3IO2 Job1 等待 J0b2 Job1Job1 I2CPU I1CPU等待 I2Job2 I1CPU等待CPU I2Job3 CPU 等待CPU等待 I1CPU I1（1）由图可以看出，Job1从投入到运行完成需要110ms，Job2从投入到运行完成需要90ms，Job3从投入到运行完成需要110ms。（2）CPU在时段60ms至70ms、80ms至90ms，100ms至110ms期间空闲，所以CPU利用率为：（1

12、1030）/110=72.7%（3）外设I1在时段20ms至40ms，90ms至100ms期间空闲，所以外设I1利用率为：（11030）/110=72.7%外设I2在时段30ms至50ms期间空闲，所以外设I2利用率为：（11020）/110=81.8%3、系统中有三种资源（A，B，C）和5个进程P1P5，资源总数为（17，5，20），T0时刻系统状态如表所示，系统采用银行家算法实施死锁避免策略请解答以下问题：（1）T0时刻是否为安全状态？若是则给出安全序列（2）在T0时刻P2请求资源（0，3，4），是否能够实施资源分配，为什么？（3）在（2）的基础上，若P4请求资源（2，0，1），是否能够实

13、施分配，为什么？（4）在（3）的基础上，若P1请求资源（0，2，0），是否能够实施分配，为什么最大资源需求量已分配资源量ABCABCP1559212P2536402P34011405P4425204P5424314第四章1. 某操作系统采用可变分区分配存储管理方法，用户区为512K且始址为0，用空闲分区表管理空闲分区。若分配时采用分配空闲区低地址部分的方案，且初始时用户区的512K空间空闲，对下述申请序列：Req(300K), req(100K), release(300K), req(150K), req(30K), req(40K), req(60K), release(30K)回答下列问

14、题：（1） 采用首次适应算法，空闲分区中有哪些空闲块（给出图示，并给出始址、大小）？（2） 采用最佳适应算法，空闲分区中有哪些空闲块（给出图示，并给出始址、大小）？解答：（1） 首次适应算法（5分）(用阴影表示空闲)0（图2分）150K150K作业180K220K40K作业280K60K作业300K400K100K作业512K-1(指出空闲分区大小和始址，每个1分)分区大小起始地址01230K20K112K150K280K400K0（2） 最佳适应算法（5分）(用阴影表示空闲)（图2分）150K150K作业210K60K作业300K400K100K作业430K470K40K作业512K-1(指

15、出空闲分区大小和始址，每个1分)分区大小起始地址01230K42K90K400K470K210K第六章1. 假设某系统现有两个用户user1和user2共用其文件系统（该文件系统采用两级目录结构）。假定user1有四个文件，其文件名为A、B、C、D；user2也有四个文件，其文件名为A、E、F、G。已知：user1的文件A和user2的文件A实际上不是同一个文件，user1的文件C和user2的文件E是同一文件。请画出该系统的文件目录结构，使这两个用户能共享该文件系统而不致造成混乱。并说明此题中有无重名问题？如有，是如何解决的？此题中有无文件共享问题？如有，是如何解决的（1）（2分）（2）有重名问题，通过二级目录解决。User1的A和User2的A同名，但由于系统取文件时是先找用户名再找文件名，因此完整的文件名是由用户名和文件名组成。（2分）（3）有文件共享问题，通过二级目录解决。User1的C和User2的E虽然文件名不同，但它们在UFD中指向同一文件，这样两个用户就可以用不同的文件名共享一个文件。（2分）2设某文件A有10个逻辑记录（R0R9，逻辑记录大小与物理块大小相等，都为512KB ）。要求用连续文件、串联文件和索引文件结构来构造。回答以下问题：   1)分别画出连续文件、串联文件的物理结构图（物理块号由考生确定）。(1)连续