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) 和时间片的长短有关，比较繁琐！ 2)运行顺序是(6,8,10,2,4) (6+14+24+26+30)/4=100/4=25 3)(10+16+18+22+30)/4=96/4=24 4) (2+(2+4)+(2+4+6)+(2+4+6+8)+( 2+4+6+8+10))/4=17.5 32：有5个待运行的作业，他们的估计运行时间分别是9,6,3,5，采用哪中次序运行各个 作业将得到最短的平均响应时间？答案依赖于X 答：由于5个作业同时到达，所以按最短作业优先调度会得到最短的响应时间： 9≤x 3 5 6 9 x 6≤x≤9 3 5 6 x 9 5≤x≤6 3 5 x 8 9 3≤x≤5 3 x 5 8 9 x≤3 x 3 5 8 9 33,在一间酒吧里有三个音乐爱好者队列，第一列音乐爱好者只有随身听，第二列只 有音乐 磁带，第三列只有电池，而要听音乐就必须有随身听，音乐磁带和电池这三中物品 。酒吧老板一次出售这三种物品中的任意两种，当一名音乐爱好者得到这三种物品 并听完乐曲后，酒吧老板才能再一次出售这三种物品中任意两种，于是第二名音乐 爱好者得到这三种物品。并开始听乐曲，全部买卖九这样进行下去。 使用P,V操作正确解决这一买卖。 解：买方有三个进程，卖方有1个进程 卖方，和买方的同步信号量 S1,S2 ,初值为0,1. 听音乐时的互斥信号量;mutex 卖方进程 P(S1) (没有音乐爱好者，等待) 卖物品 P(mutex) 放音乐 V(mutex) V(S2) 买方进程 P(S2) 买物品 V(S1) {老板可以卖东西} 34.巴拿马运河建在太平洋和大西洋之间，由于太平洋和大西洋水面高度不同，有巨大落 差，所以运河中建有T(T≥2)级船闸，并且只能允许单向通行，船闸依次编号为1,2,…,T ，由大西洋来的船需要经过船闸T,T-1.,,,2,1通过运河到达太平洋，由太平洋来的船需要 经由船闸1,2,…,T-1,T通过运河到达大西洋。 使用P,V操作正确解决大西洋和太平洋的船只通航问题。 答：答：Array: S1[T] of Semaphore {为每个船闸设置的信号量初值都为1} Array: count1[T] of INTEGER {为每个船闸设置通往大西洋的船的计数值,初值都为 0} Array: count2[T] of INTEGER {为每个船闸设置通往太平洋的船的计数值,初值都为 0} 对count设置互斥信号量 mutex 去大西洋的进程: int j for(j=0;j if(count1[j]==0) P(S[j]) count[j]++ 过第j+1个船闸 P(mutex) count[j]-- if(count[j]==0) V(S[j]) V(mutex) } 去太平洋的进程： int k for(k=T-1;k≥T,k++){ P(mutex) if(count2[k]==0) P(S[k]) count[k]++ 过第k+1个船闸 P(mutex) count[k]-- if(count[k]==0) V(S[k]) V(mutex) } 35.某银行有人民币储蓄业务，由n个柜员负责，每个顾客进入银行后，先取一个号，并且 等着叫号，当一个柜员人员空闲下来，就叫上一个号，使用P,V操作正确编写柜台人员和 顾客进程的程序！ 解; 取号的互斥信号量 mutex,叫号的互斥信号量mutex1 柜台人员和顾客进程的同步信号量为 S1,S2, 初值分别为n,0 柜台人员进程： P(S2) (无顾客则等待) P(mutex1) 叫号 V(mutex1) 服务 V(S1) 顾客进程 P(mutex) 取号 V(mutex) P(S1) 享受服务 V(S2) 36,设A,B,C三个进程共享一个存储资源F,A对F只读不写，B对F只写不读，C对F先读后写。 （当一个进程写F时，其他进程既不能读F，也不能写F,但多个进程同时读F是允许的）试 利用管程的方法或者P,V操作，写出A,B,C三个进程的框架，要求：（1）执行正确 （2）正常运行时不产生死锁；(3)使用F的并发度高 37,某系统如此定义P,V操作 P(S) S=S-1 若S<1本进程进入等待队列末尾，否则继续进行 V(S) S=S+1 若S≤0,释放等待队列中末尾的进程，否则继续运行。 现有四个进程P1,P2,P3,P4竞争使用某一需要互斥使用的资源（每个进程可能反复使用多 次），使用这样的P,V操作来正确的实现互斥。 解: S:ARRAY[0,,,3] OF Semaphore{初值为s[i]=i,i=0,1,2,3 } 访问进程 for i:=3 downto 1 do P(s[i]) 临界区操作 for i:=1 To N-1 Do V(S[i]) 38,请用进程通信的办法解决生产者，消费者问题 39,请用管程实现哲学家就餐问题 进程管理（笔记） 1).多道程序设计和并发 内存允许多个程序进入，操作系统能够同时执行这些程序 CPU在多个进程之间调度，切换 系统有时有进程，有线程 对CPU的管理： 每个实体都有一个环境，多个实体间存在一个切换 从顺序执行开始，到并发执行，会产生许多特征 顺序执行----并发执行(不可再现性)------与时间有关的错误 并发执行的结果，不可再现，由于每个程序执行的速度不同，会带来不一致性。