当前位置：问答库＞考研试题

一、应用题

1． 系统中有多个生产者进程和消费者进程，，共享用一个可以存1000个产品的缓冲区（初始为空）当缓冲区为未满时，生产者进程可以放入一件其生产的产品，否则等待；当缓冲区为未空时，消费者进程可以取走一件产品，否则等待。要求一个消费者进程从缓冲区连续取出10件产品后，其他消费者进程才可以取产品，请用信号量

求写出完整的过程；并指出所用信号量的含义和初值

【答案】设置5个信号量

empty :表示缓冲区是否为空，初值为1000

full ： 表示缓冲区是否为满，初值为0

mutex 1：生产者之间的互斥信号，初值为1

mutex2：消费者之间的互斥信号，初值为1

available :当前消费者能否访问缓冲区，初值为1

定义变量in , out 分别为生产者和消费者进程所要使用的指针，指向下一个可用的缓冲区单元，MaXNum= 1000 为缓冲区的大小，count 标志当前消费者已经取的产品的数量，初值为0

生产者进程：

生产一个产品；

产品送入buffer （in ）;

消费者进程

取出产品buffer （out ）;

操作实现进程间的互斥和同步，要

2． 假设以S 和X 分别表示入栈和出栈操作，则对初态和终态均为空的栈操作可由S 和X 生成的序列表示（如SXSX ）。

（1）试指出判别给定序列是否合法的一般规则；

（2）两个不同合法序列（对同一输入序列）能否得到相同的输出元素序列? 如能得到，请举列说明。

【答案】（1）通常有两条规则。第一是给定序列中S 的个数和X 的个数相等；第二是从给定序列的开始，到给定序列中的任一位置，S 的个数要大于或等于X 的个数。

（2）可以得到相同的输出元素序列。例如，输入元素为A , B , C , 则两个输入的合法序列ABC 和BAC 均可得到输出元素序列ABC 。对于合法序列ABC ，使用SXSXSX 操作序列；对于合法序列BAC ，使用SSXXSX 操作序列。

3． 假设计算机系统采用CSCAN （循环扫描）磁盘调度策略。使用2KB 的内存空间记录16384个磁盘块的空闲状态。

（1）请说明在上述条件下如何进行磁盘空闲状态的管理。

（2）设某单面磁盘旋转速度为每分钟6000转，每个磁道有100个扇区，相邻磁道间的平均移动时间为lms 。若在某时刻，磁头位于100号磁道处，并沿着磁道号增大的方向移动（如下图

，所示）磁道号请求队列为50, 90, 30, 120, 对请求队列中的每个磁道需要读取1个随机分布的扇区，则读完这4个扇区总共需要多少时间? 要求给出计算过程。

图

SSD 等），（3）如果将磁盘替换为随机访问的FLash 半导体存储器（如U 盘、是否有比CSCAN

更高效的磁盘调度策略? 若有，给出磁盘调度策略的名称并说明理由；若无，说明理由。

【答案】（1）采用位示图法管理磁盘空闲块，每一位表示一个磁盘块的状态，共需要16384/32=512个字节即2KB 的空间，正好可放在系统提供的内存中。

（2）采用CSCAN 调度算法，访问磁道的顺序和移动的磁道数如下表所示：

故移动的磁道数为20+90+20+40=170, 所花的时间为170ms 。由于转速为

花的时间为0.4ms 。综上所述，读取磁道上所有扇区所花的总时间为则平均旋 转延迟为5ms ，总的旋转延迟时间为20ms ，读取一个扇区的平均时间为0.1ms , 故读取4个扇区所

（3）采用先来先服务（FCFS ）调度策略更高效，因为Flash 半导体存储器的物理结构不需要考虑寻道时间和旋转延迟，可直接按请求的先后顺序服务。

4． 设有6个有序表A 、B 、C 、D 、E 、F , 分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。

（1）给出完整的合并过程，并求出最坏情况下比较的总次数。

（2）根据你的合并过程，描述

n

【答案】

（1）6个表的合并顺序如下图所示。

个不等长升序表的合并策略，并说明理由。

对应于合并过程的哈夫曼树

根据上图中的哈夫曼树，6个序列的合并过程为：

第1次合并：表A 与表B 合并，生成含45个元素的表AB ;

第2次合并：表AB 与表C 合并，生成含85个元素的表ABC ;

第3次合并：表D 与表E 合并，生成含110个元素的表DE ;

第4次合并：表ABC 与表DE 合并，生成含195个元素的表ABCDE ;

第5次合并：表ABCDE 与表F 合并，生成含395个元素的最终表。

由于合并两个长度分别为m 和n 的有序表，最坏情况下需要比较m+n-1次，故最坏情况下比较的总次数计算如下：

第1次合并：最多比较次数= 10+35-1=44;

第2次合并：最多比较次数=45+40-1 = 84;

第3次合并：最多比较次数=50+60-1 = 109;