发布时间 : 星期四 文章北大操作系统课后题参考答案更新完毕开始阅读cc4057323968011ca3009174
叠卡片逐一输入到缓冲区B1中，加工处理后再搬到缓冲区B2中，并在打印机上印出，问： 1）系统要设几个进程来完成这个任务？各自的工作是什么？ 2）这些进程间有什么样的相互制约关系 3）用P,V操作写出这些进程的同步算法
4）设系统中只有上述几个进程，用图表示出各自状态变迁情况及原因？ 答：这是一个典型的生产者，消费者问题
1）系统要设三个进程完成任务，第一个进程P1,从卡片输入机中读入数据，并且把数据放 入缓冲区B1中，第二个进程从B1缓冲区中取数据，加工处理后放入缓冲区B2中。第三个进 程将缓冲区的内容输入到打印机中打印出来 2）这三个进程之间是同步和互斥的关系
3)三个进程之间必须协调工作，需设置四个信号量，S1,S2,S3,S4并令S1的初值为1,S2的 处置为0，S4的初值为1,则程序为：
进程 p1 进程p2 进程p3 P(S1) P(S2) P(S3)
从卡片机中读入数据 P(S4) 将缓冲区B2内容 V(S2) 将Buffer B1中的数据 在打印机中输出 拷贝道Buffer B2中 V(S4) V(S1) V(S3)
4)当缓冲区B1为空时，当有输入时，进程p1进入就绪态，如果CPU为空，则为运行态，输 入完成后，进入等待态
如果存在进程p2，则为等待态，当S2+1后，处于等待态进程进入就绪态，如果CPU为空 进入运行态，拷贝完成后，进入等待态
如果存在进程p3，则为等待态，当S3+1后，处于等待态进程进入就绪态，如果CPU为空 进入运行态，输出完成后，进入等待态
12.设有无穷多个信息，输入进程把信息逐个写入缓冲区，输入进程逐个地从缓冲区中取 出信息。在下述情况下：1)缓冲区是环形的，最多可以容纳n个信息；2）缓冲区是无穷大 的。
试分别回答下列问题？
1)输入，输出两进程读，写缓冲区需要什么条件？
2)用P,V操作写出输入，输出两进程的同步算法，并给出信号量含义以及初值 3)指出信号量的值的变化范围和其值的含义 答：
一：当缓冲区的大小为n时
1）当缓冲区信息为空的时候，输出进程无法读，处于等待状态，当缓冲区信息为满的时 候无法写，都某个缓冲区单位进行读写的时候，要互斥 2）
1.空的信号量empty 初值为n, 满的信号量为full 初值为0, 对缓冲区单元的互斥信号 量为mutex,j,k为缓冲区单位地址，初值为 0
写进程 读进程 P(empty) P(full) P(mutex) P(mutex) 向Buffer[i]写入信息 从Buffer[k]中读信息 V(mutex) V(mutex) V(full) V(empty) j:=(j+1)mod n k:=(k+1)mod n
4)empty表示还有多少缓冲区单元为空，如果empty=0,表示缓冲区满，系统调用写进程时 ，写进程处于等待态
full 表示缓冲区都多少有信心的单元，如果full=0, 表示缓冲区空，系统调用写进程时 ，读进程处于等待态
mutex 表示对于缓冲区单元的互斥信号量,当mutex=1时，开锁，mutex=0时，闭锁
二．当缓冲区大小为无穷大时 1）同上 2）
1．空的信号量empty 不用设, 满的信号量为full 初值为0, 对缓冲区单元的互斥信号量 为mutex,j,k为缓冲区单位地址，初值为 0
写进程 读进程 P(full) P(mutex) P(mutex)
向Buffer[i]写入信息 从Buffer[k]中读信息 V(mutex) V(mutex) V(full)
j:=(j+1)mod n k:=(k+1)mod n
4)full 表示缓冲区都多少有信心的单元，如果full=0, 表示缓冲区空，系统调用写进程 时，读进程处于等待态
mutex 表示对于缓冲区单元的互斥信号量,当mutex=1时，开锁，mutex=0时，闭锁
13.假定一个阅览室最多可以容纳100人，读者进入和离开阅览室都必须在阅览室门口的一 个登记表上标志（进入时登记，离开时去掉登记项）而且每次只允许一人登记或者去掉登 记，问： 1) 应编写几个进程完成这项工作，程序的主要动作是些什么？应该设置几个进程？进程 和程序间的关系如何？ 2) 用P,V操作写出这些进程的同步通信关系
答：编写两个进程，一个处理读者进入，一个处理读者离开，进程是程序的动态执行 设置信号量 full 为初值为 0， 空的信号量 empty 初值为100, 互斥信号量 mutex 初值 为1
进入 离开 P(empty) P(full) P(mutex) P(mutex) 登记 取消登记 V(mutex) V(mutex) V(full) V(empty) 进入 离开
14．在生产者和消费者问题中，如果对调生产者（或消费者）进程中的两个P操作和两个 V操作的次序，会发生什么情况？请说明！
答：对调P操作, 会发生死锁 因为P(empty)在 p(mutex)和 v(mutex)内部，也就是临界 区中，当 empty≤0,时，P(empty)在临界区中进入到了休眠状态。那么就别的进程都进入 不到临界区中，进入死锁状态。
而两个V操作无关紧要
15.为什么引入高级通信机构？他有什么优点？说明消息缓冲通信机构的基本工作过程？ 答：
1）为了解决大量的消息交换，
2）优点：不仅能够保证相互制约的进程之间的相互关系，还同时实现了进程之间的信息 交换
3）消息缓冲通信技术的工作过程：
其基本思想是：根据“生产者-消费者”原理，利用内存中公用消息缓冲区实现进程之间 的信息交换。
内存中开辟了若干消息缓存区，用以存放消息，每当一个进程（发送进程）向另一个进程 （接收进程）发送消息时，便申请一个消息缓冲区，并把已准备好的消息发送到缓冲区中 ，然后把该消息缓冲区插入到接受进程的消息队列中，最后通知接受进程，接收进程收到 发送进程发送到的通知后，从本进程的消息队列中摘下一消息缓冲区，取出所需的消息， 然后把消息缓冲区还给系统。
16.进程间为什么要进行通信？在编写自己的程序时，是否考虑到要和别的用户程序进行 通信？各个用户进程间是否存在制约关系?
答；1)各个进程在运行的时候，共享内存，或者共同完成一个特定的功能，都需要进行通 信，
2)需要，
3）促在同步和互斥的关系，比如聊天程序
17.假定一个系统的磁盘块大小为2KB，一个块的平均访问时间是20毫秒。一个有40KB进程 由于资源请求从运行态变为阻塞态，它必须保持阻塞多长时间？ 答： 40/2 * 20=400毫秒 保持阻塞态 400毫秒
18.假设A,B两个火车站之间是单轨线，许多列车同时到达A站，然后经过A站到达B站；又 列车从A到B的行驶时间是t,列车在B战后的停留时间是t/2,试问在该问题模型中，什么是 临界资源，什么是临界区?
答：临界资源： A到B之间的单轨线，以及B站是临界资源 临界区： 在A到B之间行驶，以及在B上停留是临界区 19.同步机制应该遵循哪些原则？为什么？
答：1.它的描述能力应该足够强，既能解决各种进程间的同步互斥问题； 2．其次，应该容易实现并效率高 3．第三，使用方便
20.我们为某临界资源设置一把锁W。当W=1时，表示关锁，W=0时，表示开锁，试写出开锁 和关锁原语，并利用它去实现互斥。 答： while(1==w); enter 临界区
21.进程A1,A2,…,An通过m个缓冲区向进程B1,B2,…,Bn不断发送消息，发送和接收工作遵 循如下规则：
1)每个发送进程每次发送一个消息，写入一个缓冲区，缓冲区大小与消息长度一样 2)对每一个消息，B1,B2,..Bn都需要各接收一次，读到各自的数据区中； 3)m个缓冲区都满时，发送进程等待，没有可读消息时，接受进程等待 试用P,V操作组织正确的发送和接收操作。 答： VAR
mutex： Semaphore：{初值为1，实现对缓冲区的互斥}
empty： Semaphore：{初值为n,有多少缓冲}
Full： Array[1..n] OF Semaphore：{初值为0,每个接收进程当前可接收的缓冲区 }
Count：Array[1..n] OF INTEGER;{初值为0,n个缓冲区被访问的次数}
ReceivePointer:Array[1…n] OF INTEGER{初值为0，该接收进程要取哪个 } SendPointer：INTEGER;{初值为0,发送进程下次要放到哪个缓冲区} 发送进程 (num：INTEGER) {num为进程号} Repeat P(empty) P(mutex)
向buff[sendPointer]放消息
sendPointer：=（sendPointer+1）mod k count[sendPointer]：=0 V(mutex)
For i:=1 To n Do V(Full[i]) Until FALSE
接收进程 （num:INTEGER）:{num为接收进程号} Repeat
P(Full[num]) P(mutex)
从buff[ReceivePoiner[num]]中取消息 V(mutex)
Count[ReceivePoiner[num]]：= Count[ReceivePoiner[num]]+1 IF(Count[ReceivePoiner[num]]==n) THEN V(empty)
Count[ReceivePoiner[num]]==0
ReceivePoiner[num]]：=(ReceivePoiner[num])+1)mod n
Until FALSE
22．有K个进程共享一个临界区，对于下述情况，请说明信号量值的初值，含义，并用P, V
操作写出相关的互斥算法。 1） 一次只允许一个进程进入临界区 2） 一次只允许m个进程进入临界区 答：1)设置互斥信号量mutex，初值为1 P(mutex) Enter_region V(mutex)
2)设置同步信号量mutex,初值为m; P(mutex) Enter_region V(mutex)
23．爱睡觉的理发师问题，一个理发店有两间相连的屋子，一间是私室，里面有一把理发 椅，另一个是等候室，有一个滑动门和N把椅子。理发师忙的时候，通向私室的门被关闭 ，新来的顾客找一把空椅子坐下，如果椅子都被占用了，则顾客只好离去，如果没有顾客 ，则理发师在理发椅上睡觉。并打开通向私室的门。理发师睡觉时，顾客可以叫醒他理发 ，请编写
理发师和顾客的程序，正确实现同步和互斥问题！ 答：
解：VAR:
S1,S2 ：Semaphore;{初值为0,实现理发师与顾客的同步} Mutex：Semaphore：{初值为1,实现对waiting的互斥} waiting：INTEGER:{初值为0,等待的顾客数} 理发师进程 REPEAT
P(S1) {若无顾客，则睡觉 } P(mutex)
Waiting:=waiting-1
V(S2); (唤醒一个等待的客户) V(mutex) 理发 Until FALSE
顾客进程 P(mutex)
IF(waiting Waiting：=-waiting+1 ;(等待顾客数加1) V(mutex); V(S1) {通知理发师} P(S2) {若无理发师，挂起} 坐下理发 END ELSE V(mutex) 24.进程之间的通信方式有几种？在单机环境下，常用的哪几种通信方式？ 答：三种：共享内存，消息机制，以及管道通信 在单机环境下：常采用 共享内存以及管道通信。 25. 一个快餐店有四类雇员：1）领班，他们接受顾客点的菜单；2)厨师，准备饭菜；3） 打包工，将饭菜装在袋子里；4）收银元，将食品袋交给顾客并收钱，每个雇员都可以看 作一个进行通信的顺序进程，他们采用的进程间通信方式是什么？ 答：通信方式为消息传递。 26．抢占式进程调度是指系统能够强制性的使执行进程放弃处理机，试问分时系统采用的 是抢占式还是非抢占式进程调度？实时系统？ 答：分时系统采用的是非抢占式进程调度 实时系统采用的是抢占式进程调度 27．试述进程调度得主要任务，为什么说它把一台物理机变成了多台逻辑上的处理机 答：处理机调度的任务是控制协调进程对CPU的竞争即按一定的调度算法从就绪队列中选 中一个进程，把CPU的使用权交给被选中的进程 多个进程虽然在微观上仍然是顺序执行，但是在宏观上，仿佛是并发执行 28.在CPU按优先级调度的系统中 1），没有运行的进程是否一定没有就绪进程 2）没有运行进程，没有就绪进程或两者都没有是否可能？各是什么情况？ 3）运行进程是否一定是自由进程中优先数最高的？ 答：1)一定没有 2) 没有运行进程，一定没有就绪进程;没有就绪进程可能有等待进程，也可能有运行 进程；两者都没有，可能有等待进程 3)不一定，可能出现等待进程中优先级更高 29.对某系统进行监测后表明平均每个进程在I/O阻塞之前的运行时间为T，一次进程切换 的需要的时间是S,实际上就是开销，对于采用的时间片长度为Q的时间片轮转法，请给出 1）Q=无穷，2)Q>T , 3)S 解：1）当Q=无穷时， CPU的利用率=T/(T+S)*100%(当进程运行完后，就切换，也就相当 于时间 片=T) 2)当Q>T时, CPU的利用率=T/(T+S)*100%(当进程运行完后，就切换，也就相当于时间 片=T ) 3)当S 5)当Q趋于0,CPU的利用率=T/T+nS=0 （n趋于无穷） 30，大多数时间片轮转调度程序使用一个固定大小的时间片，请给出选择小时间片的理由 ，然后再给出选择大时间片的理由 答：选择小时间片：I/O密集型,可以缩短响应时间，满足短的交互需求 选择大时间片：CPU密集型，可以防止过多的进程切换，提高CPU效率 31.有5个批处理作业A到E几乎同时到达一计算中心。他们估计运行时间分别为10,6,2,4和 8分钟，其优先数(由外部设定)分别为3，5，2，1，4其中5级为最高优先级，对于下列每 种调度算法，计算其平均周转时间，可忽略进程切换的开销。 1） 时间片轮转法 2） 优先级调度法 3） 先来先服务法（按照次序10,6,2,4,8运行） 4） 最短作业优先 对1），假设系统具有多道处理能力，每个作业均获得公平的CPU时间，对(2) 和(4)假设 任一时刻只有一个作业运行，直到结束，所有作业都是CPU密集型作业! 答：1) 和时间片的长短有关，比较繁琐！