操作系统计算题（1）.doc

PAGE PAGE 1 计算题： 生产消费者问题 为解决生产者消费者问题，应该设两个同步信号量，一个说明空缓冲区的数目，用S1 表示，初值为有界缓冲区的大小N，另一个说明已用缓冲区的数目，用S2表示，初值 为０。 由于在此问题中有M个生产者和N个消费者，它们在执行生产活动和消费活动中要对有界缓冲区进行操作。由于有界缓冲区是一个临界资源，必须互斥使用，所以，另外还需要设置一个互斥信号量mutex，其初值为１。 P： P： i = 0;while (1) { 生产产品; P(S1); P(mutex); 往Buffer [i]放产品; i = (i+1) % n; V(mutex); V(S2); }; Q： j = 0; while (1) { P(S2); P(mutex); 从Buffer[j]取产品; j = (j+1) % n; V(mutex); V(S1); 消费产品; }; 地址转换 例1：若在一分页存储管理系统中，某作业的页表如下所示。已知页面大小为1024字节，试将逻辑地址1011，2148，3000，4000，5012转化为相应的物理地址。 页号 块号 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=928 查页表第2页在第1块, 所以物理地址为1796。 对于逻辑地址4000 p=int(4000/1024)=3 w=4000mod 1024=928 查页表第3页在第6块, 所以物理地址为7072。 对于逻辑地址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. 求文件最大长度 例：设文件索引节点中有7个地址项，其中4个地 址项为直接地址索引，2个地址项是一级间接地址索 引，1个地址项是二级间接地址索引，每个地址项大 小为4字节，若磁盘索引块和盘块大小均为256字 节，则可表示的单个文件的最大长度是多少？ 解答：本题的文件结构属混合索引分配方式。每个地址项大小为4字节，索引块和盘块大小为256字节，每个索引块中的项目数=256B/4B=64个。4个地址项为直接地址索引，对应的文件大小为4×256B=1KB。2个地址项是一级间接地址索引，对应的文件大小是2×64×256B=32KB，一个地址项是二级间接地址索引，对应的文件大小为1×64×64×256B=1024KB。所以单个文件的最大长度=1KB+32KB+1024KB=1057KB。 磁盘调度算法： 先来先服务FCFS 最短寻道时间优先SSTF SCAN算法 循环扫描(CSCAN)算法 例：假设一个活动头磁盘有200道, 编号从0-199. 当前磁头正在143道上服务, 并且刚刚完成了125道的请求. 现有如下访盘请求序列(磁道号): 86, 147, 91, 177, 94, 150, 102, 175, 130 试给出采用下列算法后磁头移动的顺序和移动