计算机专业基础综合操作系统（进程管理）历年真题试卷汇编1

mutex—i=1，mutex—j=1； ／／顾客 Consumer() { 进入面包店； P(mutex—i)； 取号i; i++； V(mutex—i)， 等待叫号i并购买面包; } ／／销售人员 Seller() { while(1) { P(mutex—j); if(J 解析：

31.假设缓冲区buf1和缓冲区buf2无限大，进程p1向buf1写数据，进程p2向buf2写数据，要求bufll数据个数和buf2数据个数的差保持在[m，n](m

__________________________________________________________________________________________ 正确答案：(正确答案：题中没有给出两个进程执行顺序之间的制约关系，只给出了一个数量上的制约关系，即m≤[buf]数据个数一bur2数据个数J≤n。不需要考虑缓冲区的大小，只需要考虑两个进程的同步和互斥。p2向buf2写数据比p1向buf1写数据的次数最少不超过m次，最多不能超过n次，反之也成立。所以是一个生产者和消费者问题。将等式展开得1)m≤(buf1数据个数一bur2数据个数)≤n；2)m≤(buf2数据个数一buf1数据个数)≤n；由于m、n都是正数，等式只有一个成立，不妨设1)成立。在进程p1和p2都没有运行时，两个缓冲区数据个数之差为0，因此，p1必须先运行，向buf1至少写m+1个数据后再唤醒p2运行。信号量s1表示p1一次写入的最大量，初值为n，s2表示p2一次写入的最大量，初值为一m。 semaphore mutex1=1，mutex2=1，S1=n，s2=一m; P1() { while(1){ get data； P(S1)； P(mutex1)， 写数据到buf1; v(mutex1); v(s2); } } p2() { while(1){ get data; P(S2)； P(mutex2)； 写数据到buf2， v(mutex2)； V(S1)； } } 注tpl和p2每次执行时需要进行一些额外的操作。对于p2来说，它首先必须在自己的缓冲区buf2中写入至少m个数据，此后p1和p2的同步可简单地通过两个信号量来控制。题目的一个变形是要求：一m≤(buf2数据个数-buf1数据个数)≤n，那么信号量的初值就变成m和n，若只有p1向buf1放入数据，而p2不放入数据到bur2中，则p1最多可放m次。因此，设置信号量s1，初值为m，此外，每当p2放入一个数据到bur2中时，则使信号量s1增1，即p1增加一次放入数据到buf1的机会。反之，若只有p2向buf2放入数据而p1不放入数据到buf1中，则p2最多可放n次。因此，设置信号量s2初值为n，此外，每当p1放入一个数据到buf1中时，则使信号量s2增1，即p2增加一次放入数据到bufl的机会。) 解析：

32.某工厂有两个生产车间和一个装配车间，两个生产车间分别生产A、B两种零件，装配车间的任务是把A、B两种零件组装成产品。两个生产车间每生产一个零件后都要分别把它们送到装配车间的货架F1、F2上。F1存放零件A，F2存放零件B，F1和F2的容量均可以存放10个零件。装配工人每次从货架上取一个A零件和一个B零件后组装成产品。请用P、V操作进行正确管理。【南京大学1999年】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：本题是生产者．消费者问题的变形，生产者“车间A”和消费者“装配车间”共享缓冲区“货架F1”；生产者“车间B”和消费者“装配车间”共享缓冲区“货架F2”。因此，可为它们设置6个信号量，其中，empty1对应货架1上的空闲空间，其初值为10：full1对应货架l上面的A产品，其初值为0；empty2对应货架2上的空闲空间，其初值为10；ful12对应货架2上面的B产品，其初值为0：mutex1用于互斥地访问货架1，其初值为1；mutex2用于互斥地访问货架2，其初值为1。A车间的工作过程可描述为 while(1) { 生产一个产品A; p(empty1); P(mutex1)； 将产品A存放到货架F1上; V(mutex1)； V(fulll)； } B车间的工作过程可描述为 while(1) { 生产一个产品B; P(empty2)； P(mutex2); 将产品B存放到货架F2上， V(mutex2); V(full2)； } 装配车间的工作过程可描述为 while(1) { P(full1)； P(mutex1); 从货架F1上取一个A产品; V(mutex1); V(emptY1)； P(full2); P(mutex2)； 从货架F2上取一个B产品; V(mutex2); V(empty2)； 将取得的A产品和B产品组装成产品; }) 解析：

33.某寺庙，有小、老和尚若干，有一水缸，由小和尚提入水缸供老和尚饮用。水缸可容10桶水，水取自同一井中。水井径窄，每次只能容一个桶取水。水桶总数为3个。每次入缸取水仅为1桶水，且不可同时进行。试给出有关从缸取水、入水的算法描述。 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案： semaphore weli=i; ／／用于互斥地访问水井 semaphore vat=1； ／／用于互斥地访问水缸 semaphore empty=10； ／／用于表示水缸中剩余空间能容纳的水的桶数 semaphore fuli=0 ;

／／表示水缸中的水的桶数 semaphore pail=3; ／／用于互斥地访问水桶 ／／老和尚

while(1){ wait(full)； wait(pail); wait(vat)， 从水缸中打一桶水; Signal(vat)， signal(emptY)； 喝水; Signal(pall)； } ／／小和尚 while(1){ wait(empty)； wait(pall)； wait(well)， 从井中打一桶水; signal(well)； wait(vat)； 将水倒入水缸中； signal(vat); Signal(full)； Signal(pail); }) 解析：

34.如图2-2所示，三个合作进程P1、P2、P3，它们都需要通过同一设备输入各自的数据a、b、c，该输入设备必须互斥地使用，而且其第一个数据必须由P1进程读取，第二个数据必须由P2进程读取，第三个数据则必须由P3进程读取。然后，三个进程分别对输入数据进行下列计算：的同步。 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：为了控制三个进程依次使用输入设备进行输入，需分别设置三个信号量s1、s2、s3，其中S1的初值为1。s2和S3的初值为0。使用上述信号量后，三个进程不会同时使用输入设备。故不必再为输入设备设置互斥信号量。另外，还需要设置信号量sb、Sy、Sz来表示数据b是否已经输入，以及Y、Z是否已计算完成，它们的初值均为0。三个进程的动作可描述为 P1() { P(S1)； 从输入设备输入数据a； V(S2)， P(Sb)， x=a+b； P(Sy)； P(Sz)； 使用打印机打印出x、y、z的结果； } P2() { P(S2)； 从输入设备输入数据b； V(S3); V《Sb)； y=a*b， V(Sy)； V(Sy)； } P3() { P(S3)； 从输入设备输入数据c； P(Sy)； Z=y+c—a； V(Sz); }) 解析：

35.我们将只读数据的进程称为“读者”进程，而写或者修改数据的进程称为“写者”进程，允许多个“读者”同时读数据，但不允许写者与其他读者或者写者进程同时访问数据。另外要保证：一旦有写者等待，新到达的读者必须等待，直到该写者完成数据访问为止，用PV操作实现读者、写者同步。【北京航空航天大学2005年】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：这是一个“写优先”的读者．写者问题。在经典的“读优先”的读者一写者问题的PV操作中，只要再增加一个信号量w=1，用以在写进程到达时封锁后续进程，即可实现“写优先”。 int count=0； ／／用于记录当前的读者数量 semaphore mutex=1； ／／用于保护更新count变量时的互斥 semaphore rw=1； ／／用于保证读者和写者互斥地访问文件 semaphore w=1j ／／于实现“写优先” writer(){ ／／者进程 while(1){ P(W)； P(rw)； writing V(rw)， V(W)； } } reader(){ ／／读者进程 while(1){ P(w); p(mutex); if(count==0) ／／若当前没有读者在读文件 P(rw)， ／／申请读文件 COUnt++; V(mutex)； V(w)； reading P(mutex)； count一一； if(count==0) V(rw); V(mutex)， } } 注:读者．写者问题是经典的PV题。这里的代码应该熟记。“写优先”的代码只是在“读优先”的基础上各增加一对PV操作，这一点应注意。) 解析：

36.有桥如图2—3所示，车流方向如箭头所示。回答如下问题：1)假设该桥上每次只能有一辆车行

p1：x=a+b；P2：y=a*b；

P3：z=y+c—a；最后，P1进程通过所连的打印机将计算结果x、v、z的值打印出来。请用信号量实现它们

驶，试用信号灯的P、V操作实现交通管理。2)假设该桥上不允许两车交会，但允许同方向多个车一次通过(即桥上可有多个同方向行驶的车)。试用信号灯的P、V操作实现桥上交通管理。 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案： 1) semaphore bridge=1; ／／用于互斥地访问桥 ／／从北向南 NtoS() { P(bridge)， 通过桥； v(bridge)， } ／／从南向北 StoN() { P(bridge)， 通过桥； v(bridge)； } 2) int cuntSN=0； ／／用于表示从南到北的汽车数量 int countNS=0； ／／用于表示从北到南的汽车数量 semaphore mutexSN=1； ／／用于保护countSN semaphore mutexNS=1； ／／用于保护countNS semaphore bridge=1； ／／用于互斥地访问桥 ／／从南向北 StoN() { P(mutexSN)； if(countSN==0) P(bridge); COUNtSN++； V(mutexSN)； 过桥; P(mutexSN)； countSN一一; if(COUNtSN==0) V(bridge); v(mutexSN); } ／／从

北向南 NtoS() { P(mutexNS); if(countNS=0 ) P(bridge)； coHntNS++; V(mutexNS); 过桥； P(mutexNS); countNS一一； if(countNS==0) V(bridge)； v(mutexNS)； }) 解析：

37.假设一个系统有三个抽烟者进程和一个供应者进程。每个抽烟者不停地卷烟并抽掉它，但是要卷起并抽掉一支烟，抽烟者需要有三种材料：烟草、纸和胶水。一个抽烟者有烟草、另一个有纸，第三个有胶水。供应者进程无限地提供三种材料，供应者每次将两种材料放到桌子上，拥有剩下那种材料的抽烟者卷一根烟并抽掉它，并给供应者一个信号告诉完成了，供应者就会放另外两种材料在桌上，这种过程一直重复(让3个抽烟者轮流地抽烟)。请用信号量及PV操作实现这四个进程的并发执行。 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：int random； ／／存储随机数 semaphore offeri=0； ／／定义信号量对应烟草和纸组合的资源 semaphore offer2=0， ／／定义信号量对应烟草和胶水组合的资源 semaphore offer3=0； ／／定义信号量对应纸和胶水组合的资源 semaphore finish=0 ; ／／定义信号量表示抽烟是否完成 ／／供随着 while(1){ random=任意一个整数随机数; random=random％3； if(random==01 signal(offer1)； else if(random==1) signal(offer2)； else signal(offer3)； 任意两种材料放在桌子上; wait(finish)； } ／／拥有烟草者 while(1) { wait(offer3); 拿纸和胶水，卷成烟，抽掉; signal(finish)； } ／／拥有纸者 while(1){ wait(offer2)； 拿烟草和胶水，卷成烟，抽掉; signal(finish); } ／／拥有胶水者 while(1)( wait(offer1); 拿烟草和纸，卷成烟，抽掉， signal(finish)； }) 解析：

38.两个进程A和B，每个进程都需要读取数据库中的记录1、2、3。假如这两个进程都以1、2、3的次序请求读取记录，系统将不会发生死锁。但如果A以3、2、1的次序读取记录，B以1、2、3的次序读取记录，则死锁可能会发生。试计算两个进程读取记录的次序如果不确定，那么系统保证不发生死锁的概率是多少?【华南理工大学2006年】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：本题中进程请求到一个记录后，会独占读取该记录并继续请求下一个记录，直到进程结束，释放所有记录的读取权。当两个进程都以相同次序请求读取记录时，先请求到读取记录的进程会先执行，而另一进程只有在此进程全部读取结束后才能执行，故系统不会发生死锁。如果进程A、B以不同次序读取记录，死锁可能会发生。按题中条件可知，两进程读取次序正好相反，若某一时刻两进程都在读取记录，则随着进程的执行，必定出现各自占有记录并请求读取对方记录的死锁局面。所以只有在两个进程依次读取3个记录(不能出现交替)的情况下，才能保证系统不发生死锁。我们以简单的平均概率进行分析：每次读取记录时，两进程各有1／2的概率请求成功。对于依次读取的情形，A以3、2、1的次序连续读取记录成功的概率为(1／2) =1／8；同理，B以1、2、3的次序连续读取记录成功的概率也为1／8。故系统不发生死锁的概率为1／8+118=1／4。注l本题可能会有一种错误的思路，按照6次读取记录出现AAABBB和BBBAAA的概率计算，结果为(C 6 一2)／C 6 =1／10。这里的错误在于，有些读取记录的序列是不可能出现的，如ABABAB，A读取记录3，B读取记录1，A再读取记录2，这时已经出现死锁，进程不能继续推进。) 解析：

39.假设具有5个进程的进程集合P={P0，P1，P2，P3，P4}，系统中有三类资源A、B、c，假设在某时刻有如下状态：请问当前系统是否处于安全状态?如果系统中的可利用资源．Available为(0，6，2)，系

2

2

3

统是否安全?如果系统处在安全状态，请给出安全序列；如果系统处在非安全状态，请简要说明原因。【西安交通大学2005年】 （分数：2.00）

__________________________________________________________________________________________ 正确答案：(正确答案：Need=Max—Allocation={004，175，235，064，065}一{003，100，135，002，001}={001，075，100，062，064}1)根据Need矩阵可知，当前Available为(1，4，0)，可以满足进程P2的需求；P2结束后释放资源，Available为(2，7，5)，可以满足P0、P1、P3和P4中任一进程的需求，所以系统不会出现死锁，当前处于安全状态。2)若Available为(0，6，2)，可以满足进程P0、P3的需求；这两个进程

结束后释放资源，Available为(0，6，7)，仅可以满足进程P4的需求：P4结束后释放资源，Available为(0，6，8)，此时不能满足余下任一进程的需求，系统出现死锁，故当前系统处在非安全状态。注：在银行家算法中，实际计算分析系统安全状态时，并不需要逐个进程进行。如本题中，在1)情况下，当计算至进程P2结束并释放资源时，系统当前空闲资源可满足余下任一进程的最大需求量，这时已经不需要考虑进程的执行顺序。系统分配任意一个进程所需的最大需求资源，在其执行结束释放资源后，系统当前空闲资源会增加，所以余下的进程仍然可以满足最大需求量。因此，在这里可以直接判断出系统处于安全状态。在2)情况下，系统当前可满足进程P0、P3的需求，所以可以直接让系统推进到P0、P3执行完并释放资源后的情形，这时系统出现死锁：由于此时是系统空闲资源所能达到的最大值，所以按照其他方式推进，系统必然还是出现死锁。因此，在计算过程中，将每步中可满足需求的进程作为一个集合，同时执行并释放资源，可以简化银行家算法的计算。) 解析：