1、 习题： 1. 进程同步，信号量机制实现 设有 6 个程序 s1, , s6，它们在并发系统中执行时如图所示的制约关系，试用 wait和 signal 原语来实现它们之间的同步。（ 10 分） Var a, b, c, d, e, f, g, h; semaphore:= 0, 0, 0, 0, 0, 0, 0; begin parbegin begin S1; signal(a); signal(b);signal(c); end; begin wait(a); S2; signal(d); end; begin wait(b); S3; signal(f); end; begin wait
2、(c); S4; signal(g); end; begin wait(d); S5; signal(e); end; begin wait(e); wait(f); wait(g); S6; end; parend end 2. 进程同步，信号量机制实现。详见上课讲的例题 3. 有如下进程，后一个依 次比前一个晚一个时间单位到达， 作业 运行时间 优先级 A 3 3 B 1 1 C 2 5 S1 S2 S4 S3 S5 S6 D 1 4 E 5 6 （ 1）画出下列调度算法下的调度时间图： FCFS、抢占式 非抢占式SPF、抢占式 非抢占式 HPF、 HRRN和 RR（ q=1,q=2） （
3、 2）对于上述每种算法，各个作业的周转时间是多少？平均周转时间是多少？ （ 3）对于上述每种算法，各个作业的带权周转时间 和 平均带权周转时间 各 是多少？ 相应比 =【 (等待时间 =现在时刻减去到达时间 )+服务时间】 /服务时间 算 法 作业 A B C D E 平均 到达时间 0 1 2 3 4 服务时间 3 1 2 1 5 FCFS 完成时间 3 4 6 7 12 周转时间 3 3 4 4 8 4.4 带权周转时间 1 3 2 4 1.6 2.32 SPF(非 ) 完成时间 3 4 7 5 12 周转时间 3 3 5 2 8 4.2 带权周转时间 1 3 2.5 2 1.6 2.02
4、 SPF(抢 ) 完成时间 3 11 5 12 10 周转时间 3 10 3 9 6 6.2 带权周转时间 1 10 1.5 9 1.2 4.54 HPF（非 ) 完成时间 3 11 5 12 10 周转时间 3 10 3 9 6 6.2 带权周转时间 1 10 1.5 9 1.2 4.54 HPF（抢 ) 完成时间 11 12 4 10 9 周转时间 11 11 2 7 5 7.2 带权周转时间 11/3 11 1 7 1 4.72 HRRN 完成时间 3 4 6 7 12 周转时间 3 3 4 4 8 4.4 带权周转时间 1 3 2 4 1.6 2.32 RR（ r=1） 完成时间 7
5、2 8 5 12 周转时间 7 1 6 2 8 4.8 带权周转时间 7/3 1 3 2 1.6 1.92 4. 作出页式存储管理系统中地址变换机构图。已知某作业页表如下： 0 2 1 5 2 9 3 8 试借助地址变换机构图求出逻辑地址对应的物理地址（ 1 页为1024 字节） (1) 2968 （ 2） 4599 （ 3） 0FCCH 解：分析 逻辑地址 除以页面大小 =商是页号：余数是页内地址偏移 根据页号查找 页表 中的页号判断是（缺页中断，越界中断 .） 物理地址 =块号 *块大小 +地址偏移 其中十六进制的直接转换为四位二进制计算 1.2968/1024=2.920 物理地址： 9
6、*1024+920=10136 2.4599/1024=4.503 越界中断 3.0FCCH二进制为： 111111001100/210=11.111001100 物理地址： 8*1024+972=9164 5. 有一虚拟存储系统，某作业运行 中使用的操作数所在的页号依次为： 4 3 2 1 4 3 5 4 3 2 5 1 2 4 2 5 3 4 1 5 在内存中为该作业进程开辟 3个物理块。分别采用 FIFO、 LRU 页面淘汰算法，图示该作业运行的置换情况，并计算相应的缺页率？ 1.最佳置换算法是置换以后永不使用的页面即“向后看” 2.FIFO是淘汰最先进入的页面 缺页率： (7/20)*
7、100%=35% LRU 算法是淘汰选择最近久未使用的页面就是“向前看” 4 3 2 1 4 3 5 4 3 2 5 1 2 4 2 5 3 4 1 5 4 4 4 1 1 1 5 2 2 2 2 2 2 4 4 4 3 3 3 4 4 4 4 5 5 4 4 3 3 3 5 2 2 2 3 3 3 3 1 1 5 5 5 1 1 缺页率： (4/20)*100%=20% 6. 假设磁盘有 200 个磁道（编号为 0 199）的移动头磁盘，在完成4 3 2 1 4 3 5 4 3 2 5 1 2 4 2 5 3 4 1 5 4 4 4 1 1 1 5 5 5 4 4 4 1 3 3 3 4 4
8、 4 2 2 2 5 5 5 2 2 2 3 3 3 1 1 1 3 3 了磁道 125 处的请求后，当前正在磁道号为 143 的磁道处为一个请求服务。若请求队列以 FIFO 次序存放，即 86， 147， 91， 177，94， 150， 102， 175， 130。对下列每一中磁盘调度算法，若要满足这些要求，则总的磁头移动次数为多少 (后两种要求，读写头朝着磁道号增大的方向移动 ) ？ （ 1） FCFS (2)SSTF (3)SCAN (4)CSCAN 首先根据题意可知：磁头正由低磁道号向高磁道号方向移动。 fcfs: 顺序是： 143-86-147-91-177-94-150-102-
9、175-130 (143-86)+(147-86)+(147-91)+(177-91)+(177-94)+(150-94)+(150-102)+(175-102)+(175-130)=565 sstf:顺序是： 143-147-150-130-102-94-91-86-175-177 (147-143)+(150-147)+(150-130)+(130-102)+(102-94)+(94-91)+(91-86)+(175-86)+(177-175)=162 scan:顺序是：先移动到最大柱面号 (199)再移动到最小柱面号 (0)再移动到 130 (199-143)+(199-0)+(130-
10、0)=385 例 :假定某磁盘共有 200个柱面，编号为 0-199，如果在为访问 143号柱面的请求者服务后，当前正在为访问 125号柱面的请求服务，同时有若干请求者在等待服务，它们每次要访问的柱面号为 86， 147， 91， 177， 94， 150， 102， 175， 130 1、先来先服务算法（ FCFS） First Come First Service 这是一种比较简单的磁盘调度算法。它 根据进程请求访问磁盘的先后次序进行调度 。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不 会出现某一进程的请求长期得不到满足 的情况 。此算法由于未对寻道进行优化，在对磁盘的访
11、问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。 先来先服务 （ 125） 86.147.91.177.94.150.102.175.130 2、最短寻道时间优先算法（ SSTF） Shortest Seek Time First 该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使 每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。 其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟
12、，有些请求的响应时间将不可预期。 最短寻道时间优先（ 125） 130.147.150.175.177.102.94.91.86 3、扫描算法（ SCAN）电梯调度 扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更 优先考虑的是磁头的当前移动方向 。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问 ，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而避免了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称 为电梯
13、调度算法 。此算法基本上克服了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比较大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。 电梯调度（ 125） 102.94.91.86.130.147.150.175.177 4、循环扫描算法（ CSCAN） 循环扫描算法是对扫描算法的改进。如果对磁道的访问请求是均匀分布的，当磁头到达磁盘的一端， 并反向运动时落在磁头之后的访问请求相对较少 。这是由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待的时间较长，为了解决这种情况，循环扫描算法
14、规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。 循环扫描 （ 125） 130.147.150.175.177.86.91.94.102 7. 说明文件物理结构中显式链接的原理，并计算一个 200M的硬盘（盘块大小为 1KB）其 FAT表的大小。 解：盘块 =容量 /盘块大小 200M/1KB=200K（个 ) 表项大小满足为四位二进制的整数倍 又因为： 128K200K256K 故 表项大小为 2.5个字节 FAT 表的大小 =表项大小 *表项数 =200*2.5=500KB 解：由题目所
15、给条件可知，硬盘大小为 540M，磁盘块的大小为 1K，所以该硬盘共有盘块： 540M/1K=540K（个） 又 512K 540K 1024K 故 540K 个盘块号要用 20位二进制表示，即文件分配表的每个表目为 2.5个字节。 FAT 要占用的存储空间总数为： 2.5540K=1350K 当硬盘大小为 1.2G，硬盘共有盘块： 1.2G/1K=1.2M（个） 又 1M 1.2M 2M 故 1.2M 个盘块号要用 31位二进制表示。为方便文件分配表的存取，每个表目用 32位二进制表示，即文件分配表的每个表目大小为 4个字节。 FAT 要占用的存储空间总数为： 41.2M=4.8M 这题关于
16、 1.2G 的解答那个 “1.2M 个盘块号要用 31位二进制表示 ”这个我怎么都想不明白，上面 “540K 个盘块号要用 20位二进制表示 ”我是这样理解 540K 介于 512k（ 219）和 1024k（ 220）之间，故用 20位二进制表示。 8. 存放在某个磁盘上的文件系统采用混合索引分配方式，其 FCB 中共有 6 个地址项，第 0 3个地址项为直接地址，第 4个地址项为一次间接地址，第 5 个地址项为二次间接地址，。如果每个盘块的大小为 512 字节，若盘块号需要用 4 个字节来描述，而每个盘块最多存放 128个盘块地址。则： （ 1）该文件系统允许文件的最大长度是多少？ （ 2）将文件的字节偏移量 500， 15000 和 150000 转换为物理块 号和块内偏移量。 150000/512=292， 15000 mod 512=496，即字节偏移量 150000对应的逻辑块号为 292，可从 FCB 的第 11个地址项中得到二次间接地址块的地址 ;并从二次间接地址块的第 0项中获得一个一次间接地址快递地址，再从该一次间接地址块的第 112项中获得对应的物理块号，块内偏移为 496。 (c) 最少需要 1次访问磁盘，最多需要 4次访问磁盘。
