《操作系统例题讲解.doc》由会员分享，可在线阅读，更多相关《操作系统例题讲解.doc（10页珍藏版）》请在金锄头文库上搜索。
1、操作系统例题讲解一、调度算法对如下表所示的5个进程：进程到达时间（ms）优先级CPU阵发时间（ms）P1233P2012P3443P4024P5552采用可剥夺的静态最高优先数算法进行调度（不考虑系统开销）。问 题： 画出对上述5个进程调度结果的Gantt图； 计算5个进程的平均周转时间、平均带权周转时间。解： 调度结果的Gantt图如下：P4P1P3P5P3P1P4P2024579101214(2) 时间计算：J2J4J3J110:2011:2011:4012:3014:30J2J4J3J110:2011:2011:4012:3014:30J2J4J3J110:2011:2011:4012:
2、3014:30J2J4J3J110:2011:2011:4012:3014:30进程到达时间（ms）优先级运行时间（ms）开始时间（ms）完成时间（ms）周转时间（ms）带权周转时间（ms）P123321088/3P20121214147P34434955/3P4024012123P55525721平均周转时间=(8+14+5+12+2)/5=41/5=8.2 (ms)平均带权周转时间=(8/3+7+5/3+3+1)/5=46/153.07(ms)二、存储管理某系统采用虚拟页式存储管理方式，页面大小为2KB，每个进程分配的页框数固定为4页。采用局部置换策略，置换算法采用改进的时钟算法，当有页面
3、新装入内存时，页表的时钟指针指向新装入页面的下一个在内存的表项。设当前进程P的页表如下（“时钟”指针指向逻辑页面3的表项）：逻辑页号页框号访问位r修改位m内外标识0 101H0011 02 110H1013 138H0014 05 100H111问 题： 当进程P依次对逻辑地址执行下述操作： 引用 4C7H； 修改 19B4H； 修改 0C9AH；写出进程P的页表内容； 在 的基础上，当P对逻辑地址27A8H进行访问，该逻辑地址对应的物理地址是多少？解： 页面大小为2KB，2KB=2210=211，即逻辑地址和物理地址的地址编码的低11位为页内偏移； 逻辑地址4C7H=0100 1100 01
4、11B，高于11位为0，所以该地址访问逻辑页面0；引用4C7H，页表表项0：r=1； 逻辑地址19B4H=0001 1001 1011 0100B，高于11位为3，所以该地址访问逻辑页面3；修改19B4H，页表表项3：r=1, m=1; 逻辑地址0C9AH=0000 1100 1001 1010B，高于11位为1，所以该地址访问逻辑页面1；逻辑页1不在内存，发生缺页中断；、两操作后，P的页表如下：逻辑页号页框号访问位r修改位m内外标识0 101H1011 02 110H1013 138H1114 05 100H111按改进的时钟算法，且时钟指针指向表项3，应淘汰0页面，即把P的逻辑页面1读到内
5、存页框101H，页表时钟指针指向表项2。并执行操作： 修改 0C9AH。经上述3个操作后，P的页表如下：逻辑页号页框号访问位r修改位m内外标识0 0001 101H1112 110H0013 138H0114 05 100H011 逻辑地址27A8H=0010 0111 1010 1000B，高于11位为4，所以该地址访问逻辑页面4；页面4不在内存，发生缺页中断；按改进的时钟算法，淘汰页面2，页面4读到110H页框，所以，逻辑地址27A8H对应的物理地址为：0001 0001 0000 111 1010 1000B=887A8H。三、设备与I/O管理设系统磁盘只有一个移动磁头，磁道由外向内编号
6、为：0、1、2、199；磁头移动一个磁道所需时间为1毫秒；每个磁道有 32 个扇区；磁盘转速R=7500r/min. 系统对磁盘设备的I/O请求采用N-Step Look（即N-Step Scan，但不必移动到磁道尽头），N=5。设当前磁头在60号磁道，向内移动；每个I/O请求访问磁道上的1个扇区。现系统依次接收到对磁道的I/O请求序列如下：50, 20, 60, 30, 75, 30, 10, 65, 20, 80, 15, 70问 题： 写出对上述I/O请求序列的调度序列，并计算磁头引臂的移动量； 计算：总寻道时间（启动时间忽略）、总旋转延迟时间、总传输时间和总访问处理时间。解： 考虑序列
7、中有重复磁道的I/O请求，调度序列为：60755030201510657080磁头移动量=(75-60)+(75-50)+(50-30)+(30-20)+(20-15)+(15-10)+(65-10)+(70-65)+(80-70)=15+25+20+10+5+5+55+5+10=155（磁道） 总寻道时间=1155=155（ms）一次访盘的旋转时间=1/(2R)=1/(27500/min)=(601000)/(27500)ms=4(ms)请求序列共12次访盘，总旋转延迟时间=412=48(ms)1次访盘的传输时间=1/(R32)=(601000)/(750032)=1/4ms12次访盘总传输
8、时间=1/412=3(ms)总访盘处理时间=155+48+3=206(ms)四、文件系统（1）给出“用户打开文件表”和“系统打开文件表”的形式，并图示二者之间的联系；（2）说明“写文件”系统调用命令write(fd,buf,count)的实现过程。解： 用户打开文件表和系统打开文件表图示如下：文件描述符打开方式读写指针系统打开文件表入口fd1进程P1的用户打开文件表FCB主部文件号共享计数修改标志1520/1系统打开文件表文件描述符打开方式读写指针系统打开文件表入口fd2进程P2的用户打开文件表（2）write(fd,buf,count)的实现过程如下：参数含义：fd：文件描述符；count：
9、写出记录个数；buf：内存起始位置；执行步骤： 由fd查找用户打开文件表，找到对应的系统打开文件表入口； 根据用户打开文件表中所记录的打开方式和存取方式核查访问的合法性； 查系统打开文件表，找到文件的地址； 计算欲访问起始记录的地址； 如果需要，申请存储块； 将内存中由buf起始的count个记录写到文件中由当前写指针所确定的区域； 调整用户打开文件表的读写指针。五、死锁问题某系统采用死锁检测发现死锁。设系统有资源类集合为RA，B，C，6个进程P0、P1、P2、P3、P4、P5并发运行。当前系统状态如下：allocationrequestavailableABCABCABCP010000022
10、1P1321000P2012202P3000000P4210031P5001000问 题： 在上述状态下，系统依次接收请求：request0=(1,0,0)、request1=(2,1,0)、request3=(0,0,2)，给出系统状态变化情况，并说明没有死锁。 在所确定的状态下，系统接收请求：request0=(0,3,1)，说明此时已经发生死锁，并找出参与死锁的进程。解： 在上述情况下，系统依次接收请求：request0=(1,0,0)、request1=(2,1,0)、request3=(0,0,2)，系统状态变化如下：allocationrequestavailableABCABCA
11、BCP0200000121P1321210P2012202P3000002P4210031P5001000上一状态没有死锁。因为，用死锁检测算法，进程P5、P0、P1、P2、P3、P4能依次运行完。 在所确定的状态下，系统接收请求：request0=(0,3,1)，系统状态变化如下：allocationrequestavailableABCABCABCP0200031121P1321210P2012202P3000002P4210031P5001000对上一状态用死锁检测算法，P5、P3能完成，P0、P1、P2、P4不能完成，发生死锁，参与死锁的进程为P0、P1、P2、P4。六、信号量与P/V操作一南北流向的小河上有一座独木桥，如下图所示：西东该独木桥宽度只能容纳一人，且该桥最多只能承重4人；东、西两方向过桥人只能前进、不能后退。问 题：写出用信号量和PV操作实现东、西两方向行人过桥没有死锁、没有饿死的并发运行算法。要 求：给出定义的各信号量和变量的含义及其初值；算法用类C伪代码描述。解：共享变量定义：int west_crossing=0,east_crossing=0,west_wait=0,east_wai
