1、计算题： 一、 生产消费者问题 为解决生产者消费者问题，应该设两个同步信号量，一个说明空缓冲区的数目，用 S1表示，初值为有界缓冲区的大小 N，另一个说明已用缓冲区的数目，用 S2 表示，初值为。 由于在此问题中有 M 个生产者和 N 个消费者，它们在执行生产活动和消费活动中要对有界缓冲区进行操作。由于有界缓冲区是一个临界资源，必须互斥使用，所以，另外还需要设置一个互斥信号量 mutex，其初值为。 二、 地址转换 例 1： 若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为 1024 字 节，试将逻辑地址 1011， 2148， 3000， 4000， 5012 转化为相应的物理
2、地址。 页号 块号 0 2 1 3 2 1 3 6 解：本题中，为了描 述方便，设页号为 P，页内位移为 W，逻辑地址为 A，页面大小为 L，则： p=int(A/L) w=A mod L 对于逻辑地址 1011 p=int(1011/1024)=0 w=1011 mod 1024=1011 查页表第 0 页在第二块，所以物理地址为 3059。 对于逻辑地址 2148 p=int(2148/1024)=2 w=2148 mod 1024=100 查页表第 2 页在第 1 块，所以物理地址为 1124。 对于逻辑地址 3000 p=int(3000/1024)=2 w=3000 mod 1024
3、=928 查页表第 2 页在第 1 块 , 所以物理地址为 1796。 Q： j = 0; while (1) P(S2); P(mutex); 从 Bufferj取产品 ; j = (j+1) % n; V(mutex); V(S1); 消费产品 ; ; P： i = 0; while (1) 生产产品 ; P(S1); P(mutex); 往 Buffer i放产品 ; i = (i+1) % n; V(mutex); V(S2); ; 对于逻辑地址 4000 p=int(4000/1024)=3 w=4000mod 1024=928 查页表第 3 页在第 6 块 , 所以物理地址为 70
4、72。 对于逻辑地址 5012 p=int(5012/1024)=4 w=5012mod1024=916 因页号超过页表长度，该逻辑地址非法。 例 2： 在一分页存储管理系统中 ,逻辑地址长度为 16 位 ,页面大小为 4096 字节 ,现有一逻辑地址为2F6AH,且第 0, 1, 2 页依次存放在物理块 5, 10 ,11 中 ,问相应的物理地址为多少 ? 解 :由题目所给给条件可知 ,本页式系统的逻辑地址结构为 : 逻辑地址 2F6AH 的二进制表示如下 : 由此可知逻辑地址 2F6AH的页号为 2,该页存放在第 11 号物理块中 ,用十六进制表示志号为 B,所以物理地址为 BF6AH.
5、三、 求文件最大长度 例 ： 设文件索引节点中有 7 个地址项，其中 4 个地 址项为直接地址索引， 2 个地址项是一级间接地址索 引， 1 个地址项是二级间接地址索引，每个地址项大 小为 4 字节，若磁盘索引块和盘块大小均为 256 字 节，则可表示的单个文件的最大长度是多少 ？ 解答：本题的文件结构属混合索引分配方式。每个地址项大小为 4 字节，索引块和盘块大小为 256 字节，每个索引块中的项目数 =256B/4B=64 个。 4 个地址项为直接地址索引，对应的文件大小为 4256B=1KB。 2 个地址项是一级间接地址索引，对应的文件大小是 264256B=32KB，一个地址项是二级间
6、接地址索引，对应的文件大小为 16464256B=1024KB。所以单个文件的最大长度 =1KB+32KB+1024KB=1057KB。 四、 磁盘调度算法： 1. 先来先服务 FCFS 2. 最短寻道时间优先 SSTF 3. SCAN 算法 4. 循环扫描 (CSCAN)算法 例：假设一个活动头磁盘有 200 道 , 编号从 0-199. 当前磁头正在 143 道上服务 , 并且刚刚完成了 125 道的请求 . 现有如下访盘请求序列 (磁道号 ): 86, 147, 91, 177, 94, 150, 102, 175, 130 试给出采用下列算法后磁头移动的顺序和移动总量 (总磁道数 ).
7、 (1). 先来先服务 (FCFS)磁盘调度算法 . (2). 最短寻道时间优先 (SSTF)磁盘调度算法 . (3). 扫描法 (SCAN)磁盘调度算法 .(假设沿磁头移动方向不再有访问请求时 , 磁头沿相反方向移动 .) 答案：三、（ 1） 86， 147， 91， 177， 94， 150， 102， 175， 130 （ 2）当前磁头在 143 道上： 147， 150， 130， 102， 94， 91， 86， 175， 177 （ 3）当前磁头在 143 道上，并且刚刚完成 125 道的请求 147， 150， 175， 177， 130， 102， 94， 91， 86 五、
8、调度算法（求周转时间，加权周转时间） 1先来先服务调度算法 FCFS： 该算法按 照进程进入就绪队列的先后顺序选择最先进入该队列的进程，把处理机分配给它，使之投入运行。 例2优先级调度算法 ： 总是选择具有 最高优先级 的进程首先使用处理机 。 在这种算法中，首先考虑的问题是如何确定进程的优先数。 分为 ： 静态优先权： 在创建进程的时候便确定的，且在进程的运行期间保持不变。（ 简单易行，系统开销小，但不够精确，很可能出现优先权低的作业（进程）长期不被调度的情况。所以，只在要求不太高的系统中，才使用静态优先数（权） ） 动态优先权： 在创建进程时所赋予的优先权，可以随进程的推进而改变，以便 获
9、得更好的调度性能 例：3.最短作业 /进程优先法（ SJF/SPF） ： SJF:从后备队列中选择估计运行时间最短的作业，先调入内存运行。 SPF:从就绪队列中选择估计运行时间最短的进程，先将处理机分配给它，使它立即执行。 4.最高响应比作业优先算法（ HRN） ： 是对 FCFS 方式和 SJF方式的一种综合平衡响应比。 R (作业等待时间需运行时间 )/ 需运行时间 1已等待时间 / 需运行时间 1 W/T 例：六 ： 页面置换算法 先进先出页面淘汰算法（ FIFO） 选择在内存中驻留时间最长的页并淘汰之 理想淘汰算法 最佳页面算法（ OPT） 淘汰以后不再需要的或最远的将来才会用到的页面
10、 最近最久未使用页面淘汰算法（ LRU） 选择最后一次访问时间距离当前时间最长的一页并淘汰之 即淘汰没有使用的时间最长的页 1 已知页面走向为 1、 2、 1、 3、 1、 2、 4、 2、 1、 3、 4，且开始执行时主存中没有页面。若只给该作业分配 2 个物理块，当采用 FIFO 页面淘汰算法时缺页率为多少？假定现有一种淘汰算法，该算法淘汰页面的策略为当需要淘汰页面时，就把刚使用过的页面作为淘汰对象， 试问就相同的页面走向，缺页率又为多少？ 分析及相关知识 在进行内存访问时，若所访问的页已在主存，则称此次访问成功；若所访问的页不在主存，则称此次访问失败，并产生缺页中断。若程序 P 在运行过
11、程中访问页面的总次数为 S,其中产生缺页中断的访问次数为 F,则其缺页率为： F/s. 解： 根据所给页面走向，采用 FIFO 淘汰算法的页面置换情况如下： 页面走向 1 2 1 3 1 2 4 2 1 3 4 物理块 1 1 1 3 3 2 2 1 1 4 物理块 2 2 2 1 1 4 4 3 3 缺页 缺 缺 缺 缺 缺 缺 缺 缺 缺 从上述页面置换图可以看出：页面引用次数为 11 次，缺页次数为 9 次，所以缺页率为9/11。 若采 用后一种页面淘汰策略，其页面置换情况如下： 页面走向 1 2 1 3 1 2 4 2 1 3 4 物理块 1 1 1 3 1 1 1 3 4 物理块 2
12、 2 2 2 4 2 2 2 缺页 缺 缺 缺 缺 缺 缺 缺 缺 在一个请求分页存储管理系统中，一个作业的页面走向为 4， 3， 2， 1， 4， 3， 5， 4， 3， 2，1， 5，当分配给该作业的物理块数分别为 3， 4 时，试计算采用下述页面淘汰算法时的缺页率（假设开始执行时主存中没有页面），并比较所得结果。 （ 1） 最佳置换淘汰算法 （ 2） 先进先出淘汰算法 （ 3） 最近最久未使用淘汰算法 解：（ 1）根据所给页面走向，使用最佳页面淘汰 算法时，页面置换情况如下： 走向 4 3 2 1 4 3 5 4 3 2 1 5 块 1 4 4 4 4 4 2 2 块 2 3 3 3 3
13、 3 1 块 3 2 1 5 5 5 缺页 缺 缺 缺 缺 缺 缺 缺 缺页率为： 7/12 走向 4 3 2 1 4 3 5 4 3 2 1 5 块 1 4 4 4 4 4 1 块 2 3 3 3 3 3 块 3 2 2 2 2 块 4 1 5 5 缺页 缺 缺 缺 缺 缺 缺 缺 缺页率为： 6/12 由上述结果可以看出，增加分配 给作业 的内存块数可以降低缺页率 （ 2）根据所给页面走向，使用最佳页面淘汰 算法时，页面置换情况如 下： 走向 4 3 2 1 4 3 5 4 3 2 1 5 块 1 4 4 4 1 1 1 5 5 5 块 2 3 3 3 4 4 4 3 2 块 3 2 2
14、2 3 3 2 1 缺页 缺 缺 缺 缺 缺 缺 缺 缺页率为： 9/12 走向 4 3 2 1 4 3 5 4 3 2 1 5 块 1 4 4 4 4 5 5 5 5 1 1 块 2 3 3 3 3 4 4 4 4 5 块 3 2 2 2 2 3 3 3 3 块 4 1 1 1 1 2 2 2 缺页 缺 缺 缺 缺 缺 缺 缺 缺页率为： 10/12 由上述结果可以看出，对先进先出算法而言， 增加分配给作业的内存块数反而使缺页率上升，这种异常现象称为 Belady 现象 。 (3) 根据所给页面走向，使用最佳页面淘汰 算法时，页面置换情况如下： 走向 4 3 2 1 4 3 5 4 3 2 1 5 块 1 4 4 4 1 1 1 5 2 2 2 块 2 3 2 4 4 4 4 1 1 块 3 2 3 2 3 3 3 3 5 缺页 缺 缺 缺 缺 缺 缺 缺 缺页率为： 10/12 走向 4 3 2 1 4 3 5 4 3 2 1 5 块 1 4 4 4 4 4 4 4 5 块 2 3 3 3 3 3 3 3 块 3 2 2 5 5 1 1 块 4 1 1 2 2 2 缺页 缺 缺 缺 缺 缺 缺 缺 缺 缺页率为 :8/12 由上述结果可以看出 ,增加分配给作业的内存块数可以降低缺页率 .
