程的控制下，将用户要求的数据从输入机通过输入缓冲区送到输入井，CPU需要数据时，直接从输入井读入内存；在输出进程的控制下，把用户要求输出的数据，先从内存送入输出井，待输出设备空闲时，再将输出井的数据经输出缓冲区送到输出设备上。
五、综合题
1．假设一个系统中有五个进程{P1,P2,P3,P4,P5}和三类资源{A,B,C}，当前资源分配和请求情况如表：试用银行家算法进行分析：1
①当前状态安全吗？
②当进程P4提出资源请求{1,1,2}后，系统能否满足？
1.解：①存在一个安全序列P3,P2,P1,P4,P5,所以当前状态安全。 P1 P2 P3 P4 P5 P3 P2 P1 P4 P5 work A B C Allocation A B C 2 1 1 3 2 0 1 1 2 0 2 0 0 1 1 2 2 4 3 3 6 6 5 6 8 6 7 8 8 7 Allocation A B C Need A B C 3 0 1 1 3 2 1 1 2 1 4 7 2 5 0 1 1 2 3 2 0 2 1 1 0 2 0 0 1 1 Need A B C Available A B C 2 2 5 1 1 2 1 3 2 3 0 1 1 4 7 2 5 0 3 3 6 6 5 6 8 6 7 8 8 7 8 9 8 true true true true true Work+ Allocation A B C finish A B C ②当进程P4提出资源请求{1,1,2}后 因为（1，1，2）<(1,4,7),请求合理
因为（1，1，2）<(2，2，4)，假设满足P4的请求，修改数据结构如下
P1 P2 P3 P4 P5 Allocation A B C 2 1 1 3 2 0 1 1 2 1 3 2 0 1 1 Need A B C 3 0 1 1 3 2 1 1 2 0 3 5 2 5 0 Available A B C 1 1 2 找不出安全序列，所以不能满足P4的请求。
2．有四个作业，它们的提交、运行时间如下表所示，说明采用先来先服务、短作业优先和响应比高者优先调度算法，作业调度顺序各是什么？并计算各种调度算法的平均周转时间和平均带权周转时间。1
作业号 A B C D
提交时间 8．0 8．3 8．5 9．0 运行时间 2．0 0．5 0．1 0．4
2． . 解：先来先服务的作业调度顺序是A、B、C、D， 作业A的周转时间是2，带权周转时间是1； 作业B周转时间是2.2, 带权周转时间是4.4; 作业C周转时间是2.1, 带权周转时间是21; 作业D周转时间是2, 带权周转时间是5;
平均周转时间是2.075，平均带权周转时间是7.85 。
短作业优先的作业调度顺序是A、C、D、B，
作业A的周转时间是2，带权周转时间是1； 作业C周转时间是1.6, 带权周转时间是16; 作业D周转时间是1.5, 带权周转时间是3.75; 作业B周转时间是2.7, 带权周转时间是5.4;
平均周转时间是1.95，平均带权周转时间是6.54 。
高响应比优先的作业调度顺序是A、C、B、D，
作业A的周转时间是2，带权周转时间是1； 作业C周转时间是1.6, 带权周转时间是16; 作业B周转时间是2.3, 带权周转时间是4.6; 作业D周转时间是2, 带权周转时间是5;
平均周转时间是1.975，平均带权周转时间是6.65 。
3． 若在一分页存储管理系统中，某作业共4页，已知页面大小为1024字节，假定某时刻系统为用户
的第0、1、2、3页分配的物理块号为5、6、3、7，试将逻辑地址2365(十进制)，3402(十进制)，09BA(十六进制)，19B9(十六进制)转化为相应的物理地址。1
3．若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024字节，假定某时刻系统为用户的第0、1、2、3页分配的物理块号为5、3、7、6试将逻辑地址2148(十进制)，3000(十进制)，08A7(十六进制)，18C6(十六进制)转化为相应的物理地址。
解：2148 的逻辑页号为2，页内偏移为100，故物理地址为7*1024+100=7268 3000的逻辑页号为2，页内偏移为952，故物理地址为7*1024+952=8120
08A7转换为二进制位000010 0010100111，页号为2，对应块号为7，故物理地址为000111 0010100111 即1CA7,同理，18C6页号为6，越界，发生越界中断。
5．有5个任务A，B，C，D，E，它们几乎同时到达，预计它们的运行时间为10，6，4，2， 8min。其优先级分别为3，2，5， 1和4，这里5为最高优先级。对于下列每一种调度算法，计算其平均进程周转时间（进程切换开销可不考虑）。
（1）先来先服务（按A，B，C，D，E）算法。 （2）优先级调度算法。
（3）时间片轮转算法（每个时间片为2min）。
（1）采用先来先服务（FCFS）调度算法时，5个任务在系统中的执行顺序、完成时间及周转时间如下表所示：
执行次序 A 运行时间 10 优先数 3 等待时间 0 周转时间 10
B C D E 6 2 4 8 5 2 1 4 10 16 18 22 16 18 22 30 根据表中的计算结果，5个进程的平均周转时间T为： T=（10+16+18+22+30）/5=19.2min
（2）采用最高优先级调度（HPF）算法时，5个任务在系统中的执行顺序、完成时间及周转时间如下表所示： 执行次序 B E A C D 运行时间 6 8 10 2 1 优先数 5 4 3 2 1 等待时间 0 6 14 24 26 周转时间 6 14 24 26 27 它们的平均周转时间为： T=（6+14+24+26+27）/5= 19.4min
（3）如果系统采用时间片轮转（RR）算法，令时间片为2分钟，5个任务轮流执行的情况为： 第1轮：（A，B，C，D，E） 第2轮：（A，B，D，E） 第3轮：（A，B，E） 第4轮：（A，E） 第5轮：（A）
显然，5个进程的周转时间为：T1=30min、 T2=22min、 T3=6min、T4=16min、T5=28min。它们的平均周转时间T为：
T=（30+22+6+16+28）/5=20.4min
6．某车站售票厅，任何时刻最多可容纳40名购票者进入，当售票厅中少于40购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请用wait、signal操作管理这些并发进程时，应怎样定义信号量？写出信号量的初值以及信号量取值的含义。
3．解：设置一个信号量S，表示售票厅里还可以容纳的人数，初值为20。每个购票者的描述如下：
Semaphore S=20; Buyer() {
wait(S); 进入售票厅； 购票；
退出售票厅； signal(S); }
7．假定某页式管理系统，主存为64KB，分成16块，块号为0，1，2，3，4，…，15。设某作业有4页，其页号为0，1，2，3，被分别装入主存的2，4，1，6块。试问：
（1）该作业的总长度是多少字节？
（2）写出该作业每一页在主存中的起始地址。 （3）若有多个逻辑地址[1，120］、［0，40］、［2，5］、［3，70］，试计算出相应的内存地址。（方括号内的第一个元素为页号，第二个元素为页内位移）。
解答：
（1）每块的长度为64KB/16＝4KB
在页式存储管理系统中，页与块大小相等，因此作业总长度为4KB*4=16KB=16384B。
（2）因为页号为0、1、2、3的页分别装入主存入2、4、1、6块中，所以该作业每一页在主存中的起始地址如下：
第0页在主存中的起始地址：4KB*2=8KB=8192B 第1页在主存中的起始地址：4KB*4=16KB=16384B 第2页在主存中的起始地址：4KB*1=4KB=4096B 第3页在主存中的起始地址：4KB*6=24KB=24576B （3）内存地址=块地址+页内地址，地址变换如下： 逻辑地址[0，100]的内存地址为：4KB*2+100=8292B 逻辑地址[1，50]的内存地址为：4KB*4+50=16434B 逻辑地址[2，0]的内存地址为：4KB*1+0=4096B 逻辑地址[3，60]的内存地址为：4KB*6+60＝24636B
8．假定一个盘组共有200个盘面，每个盘面上有16个磁道，每个盘面分成4 个扇区，问： （1）若一个扇区为一个盘块，整个磁盘空间共有多少个盘块？ （2）如果用字长为32位的单元来构造位示图，共需要多少个字？
（3）位示图中第19个字的第18位对应的盘块号是多少？（位示图的行列下标、盘块号都从0开始编号）
9．在一个请求分页存储管理系统中，一个作业的页面走向为2、1、3、5、2、4、2、5、3、2、5、2，分配给该作业的物理块为3，初始时为空，计算采用先进先出置换算法、最近最久未使用置换算法的缺页次数。
10．有一个长度为n的有界缓冲区，一组生产者进程生产产品，每生产一件产品，就放到缓冲区的一个空单元格中，一组消费者消费产品，每次在缓冲区中取出一件产品消费。生产者和消费者共享缓冲区，要求：如果缓冲区的产品已经满了，则生产者不能再放，如果缓冲区已经空了，则消费者不能再取。用信号量写出生产者和消费者并发执行的过程
11．某系统有R1、R2和R3共三种资源，在T0时刻P1、P2、P3和P4这4个进程对资源的占有和需求情况见下表，此时系统的可用资源向量为（2，1，2）。
P1 P2 P3 P4
最大资源需求量 R1 R2 R3 3 2 2 6 1 3 3 1 4 4 2 2 已分配资源数量 R1 R2 R3 1 0 0 4 1 1 2 1 1 0 0 2