操作系统的经典习的题目

1、习题：进程同步，信号量机制实现设有6个程序s1, s6，它们在并发系统中执行时如下列图的制约关系，试用wait和signal原语来实现它们之间的同步。10分S1S2S5S3S4S6Var 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(c); S4;

2、 signal(g); end;begin wait(d); S5; signal(e); end;begin wait(e); wait(f); wait(g); S6; end; parend end进程同步，信号量机制实现。详见上课讲的例题有如下进程，后一个依次比前一个晚一个时间单位到达，作业运行时间优先级A33 B1 1 C2 5D1 4 E5 61画出如下调度算法下的调度时间图：FCFS、抢占式非抢占式SPF、抢占式非抢占式HPF、HRRN和RRq=1,q=22对于上述每种算法，各个作业的周转时间是多少？平均周转时间是多少？ 3对于上述每种算法，各个作业的带权周转时间和平均带权周转时

3、间各是多少？相应比=【(等待时间=现在时刻减去到达时间)+服务时间】/服务时间算法作业ABCDE平均到达时间01234服务时间31215FCFS完成时间346712周转时间33448 = average(C5:G5) * MERGEFORMAT 4.4带权周转时间13241.6 = average(C6:G6) * MERGEFORMAT 2.32SPF(非)完成时间347512周转时间33528 = average(C8:G8) * MERGEFORMAT 4.2带权周转时间132.521.6 = average(C9:G9) * MERGEFORMAT 2.02SPF(抢)完成时间3115

4、1210周转时间310396 = average(C11:G11) * MERGEFORMAT 6.2带权周转时间1101.591.2 = average(C12:G12) * MERGEFORMAT 4.54HPF非)完成时间31151210周转时间310396 = average(C14:G14) * MERGEFORMAT 6.2带权周转时间1101.591.2 = average(C15:G15) * MERGEFORMAT 4.54HPF抢)完成时间11124109周转时间1111275 = average(C17:G17) * MERGEFORMAT 7.2带权周转时间11/311

5、171 = average(C18:G18) * MERGEFORMAT 4.72HRRN完成时间346712周转时间33448 = average(C20:G20) * MERGEFORMAT 4.4带权周转时间13241.6 = average(C21:G21) * MERGEFORMAT 2.32RRr=1完成时间728512周转时间71628 = average(C23:G23) * MERGEFORMAT 4.8带权周转时间7/31321.6 = average(C24:G24) * MERGEFORMAT 1.92作出页式存储管理系统中地址变换机构图。某作业页表如下：0 2 1 5

6、 2 9 3 8试借助地址变换机构图求出逻辑地址对应的物理地址1页为1024字节(1) 2968 24599 30FCCH解：分析逻辑地址除以页面大小=商是页号：余数是页内地址偏移根据页号查找页表中的页号判断是缺页中断，越界中断.物理地址=块号*块大小+地址偏移其中十六进制的直接转换为四位二进制计算1.2968/1024=2.920 物理地址：9*1024+920=101362.4599/1024=4.503 越界中断物理地址：8*1024+972=9164有一虚拟存储系统，某作业运行中使用的操作数所在的页号依次为：4 3 2 1 4 3 5 4 3 2 5 1 2 4 2 5 3 4 1 5

7、在内存中为该作业进程开辟3个物理块。分别采用FIFO、LRU页面淘汰算法，图示该作业运行的置换情况，并计算相应的缺页率？1.最优置换算法是置换以后永不使用的页面即“向后看432143543251242534154441115554441333444222555222333111332.FIFO是淘汰最先进入的页面缺页率：(7/20)*100%=35%LRU算法是淘汰选择最近久未使用的页面就是“向前看43214354325124253415444111522222244433344445544333522233331155511缺页率：(4/20)*100%=20%假设磁盘有200个磁道编号为0

8、199的移动头磁盘，在完成了磁道125处的请求后，当前正在磁道号为143的磁道处为一个请求服务。假如请求队列以FIFO次序存放，即86，147，91，177，94，150，102，175，130。对如下每一中磁盘调度算法，假如要满足要求，如此总的磁头移动次数为多少 (后两种要求，读写头朝着磁道号增大的方向移动) ？ 1FCFS (2)SSTF (3)SCAN (4)CSCAN首先根据题意可知：磁头正由低磁道号向高磁道号方向移动。fcfs: 顺序是：143-86-147-91-177-94-150-102-175-130(143-86)+(147-86)+(147-91)+(177-91)+(1

9、77-94)+(150-94)+(150-102)+(175-102)+(175-130)=565sstf:顺序是：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)=162scan:顺序是：先移动到最大柱面号(199)再移动到最小柱面号(0)再移动到130 (199-143)+(199-0)+(130-0)=385例:假定某磁盘共有200个柱面，编号为0-199，如果在为访问143号柱面的请求者服务后，当前

10、正在为访问125号柱面的请求服务，同时有假如干请求者在等待服务，它们每次要访问的柱面号为 86，147，91，177，94，150，102，175，1301、先来先服务算法FCFSFirst e First Service这是一种比拟简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进展调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进展优化，在对磁盘的访问请求比拟多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。先来先服务1252、最短寻道时间优先算法

11、SSTF Shortest Seek Time First该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比拟好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有些请求的响应时间将不可预期。最短寻道时间优先1253、扫描算法SCAN电梯调度扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当

12、前磁道之外，又是距离最近的。这样自里向外地访问，直到再无更外的磁道需要访问才将磁臂换向，自外向里移动。这时，同样也是每次选择这样的进程来调度，即其要访问的磁道，在当前磁道之内，从而防止了饥饿现象的出现。由于这种算法中磁头移动的规律颇似电梯的运行，故又称为电梯调度算法。此算法根本上克制了最短寻道时间优先算法的服务集中于中间磁道和响应时间变化比拟大的缺点，而具有最短寻道时间优先算法的优点即吞吐量较大，平均响应时间较小，但由于是摆动式的扫描方法，两侧磁道被访问的频率仍低于中间磁道。电梯调度1254、循环扫描算法CSCAN循环扫描算法是对扫描算法的改良。如果对磁道的访问请求是均匀分布的，当磁头到达磁盘

13、的一端，并反向运动时落在磁头之后的访问请求相对较少。这是由于磁道刚被处理，而磁盘另一端的请求密度相当高，且访问请求等待的时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进展扫描。循环扫描 125说明文件物理结构中显式的原理，并计算一个200M的硬盘盘块大小为1KB其FAT表的大小。解：盘块=容量/盘块大小 200M/1KB=200K个)表项大小满足为四位二进制的整数倍又因为：128K200K256K 故 表项大小为2.5个字节FAT表的大小=表项大小*表项数=20

14、0*2.5=500KB解：由题目所给条件可知，硬盘大小为540M，磁盘块的大小为1K，所以该硬盘共有盘块：540M/1K=540K个又512K540K1024K故540K个盘块号要用20位二进制表示，即文件分配表的每个表目为2.5个字节。FAT要占用的存储空间总数为：2.5540K=1350K当硬盘大小为1.2G，硬盘共有盘块：1.2G/1K=1.2M个又1M1.2M2M故1.2M个盘块号要用31位二进制表示。为方便文件分配表的存取，每个表目用32位二进制表示，即文件分配表的每个表目大小为4个字节。FAT要占用的存储空间总数为：41.2M=4.8M这题关于1.2G的解答那个“1.2M个盘块号要用31位二进制表示这个我都想不明白，上面“540K个盘块号要用20位二进制表示我是这样理解540K介于512k219和1024k220之间，故用20位二进制表示。存放在某个磁盘上的文件系统采用混合索引分式，其FCB有6个地址项，第03个地址项为直接地址，第4个地址项为一次间接地址，第5个地址项为二次间接地址，。如果每个盘块的大小为512字节，假如盘块号需要用4个字节来描述，而每个盘块最多存放128个盘块地址。如此：1该