操作系统例题讲解.doc

操作系统例题讲解一、调度算法对如下表所示的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: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页。采用局部置换策略，置换算法采用改进的时钟算法，当有页面新装入内存时，页表的时钟指针指向新装入页面的下一个在内存的表项。设当前进程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 0111B，高于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读到内存页框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管理设系统磁盘只有一个移动磁头，磁道由外向内编号为：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问 题：1 写出对上述I/O请求序列的调度序列，并计算磁头引臂的移动量；2 计算：总寻道时间（启动时间忽略）、总旋转延迟时间、总传输时间和总访问处理时间。解： 考虑序列中有重复磁道的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次访盘总传输时间=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：写出记录个数；buf：内存起始位置；执行步骤： 由fd查找用户打开文件表，找到对应的系统打开文件表入口； 根据用户打开文件表中所记录的打开方式和存取方式核查访问的合法性； 查系统打开文件表，找到文件的地址； 计算欲访问起始记录的地址； 如果需要，申请存储块； 将内存中由buf起始的count个记录写到文件中由当前写指针所确定的区域； 调整用户打开文件表的读写指针。五、死锁问题某系统采用死锁检测发现死锁。设系统有资源类集合为RA，B，C，6个进程P0、P1、P2、P3、P4、P5并发运行。当前系统状态如下：allocationrequestavailableABCABCABCP0100000221P1321000P2012202P3000000P4210031P5001000问 题： 在上述状态下，系统依次接收请求：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)，系统状态变化如下：allocationrequestavailableABCABCABCP0200000121P1321210P2012202P3000002P4210031P5001000上一状态没有死锁。因为，用死锁检测算法，进程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_wait=0;semaphore wq , eq; /*初值均为0*/semaphore mutex; /*初值均为1，用于共享变量的互斥*/semaphore num;/*初值为4，用于限制过河人数*/semaphore w_wait, e_wait; /*初值均为1，防止对方饿死*/东面过河者算法：P(east_wait);/*后续过桥者将在此等待*/P(mutex);if (west_crossing 0) east_wait + ; if (east_wait= =1) P(w_wait);/东边有等待，西边后续过桥者将等待 V ( mutex ) ; P ( eq ); /*东边第一位过桥者在此等待*/ else P(num); /*过河人数超过4人则等待*/east_crossing+; V ( mutex );V(east_wait);P ( mutex ) ;east_crossing - ;V(num); /*过桥人数减少1人*/if (east_crossing = = 0) if (west_wait 0) do west_wait ; west_crossing + ; V ( wq ) ; /*唤醒西边第一位等待者*/ V(w_wait); /*唤醒西边后续的等待者*/ V ( mutex ) ;西面过河者算法：P(w_wait); /*后续过桥者将在此等待*/P(mutex);if (east_crossing 0) west_wait + ; if (west_wait= =1) P(e_wait);/西边有等待，东边后续过桥者将等待V ( mutex ) ;P ( wq ); /*西边第一位过桥者在此等待*/ else P(num); /*过河人数超过4人则等待*/west_crossing+; V ( mutex ); V(w_wait);P ( mutex ) ;west_crossing - ;V(num); /*过桥人数减少1人*/if (west_crossing = = 0) if (east_wait 0) do east_wait ; east_crossing + ; V ( eq ) ; /*唤醒东边第一位等待者*/ V(e_wait); /*唤醒东边后续的等待者*/ V ( mutex ) ;七、进程互斥并发进程P0和P1关于共享变量的临界区分别为region0和region1。用软件方法解决P0和P1互斥进入其临界区的不完整的C伪代码如下：int flag2=0,0; /*公共变量*/进程 P1：do flag1=1; turn= ;while ( ) do continue;；flag1=0;； while(1);int turn; /*公共变量*/进程 P0：do flag0=1; turn= ;while ( ) do continue;；flag0=0;； while(1); 问 题：1. 在、处分别填上正确的数；在、处分别填上正确的C表达式，使P0、P1满足临界区管理的互斥性、进展性、有限等待性原则；2.当P0和P1两进程都要进入临界区，并分别执行完各自有关turn的赋值语句后，哪个进程先进入临界区？说明理由。解：1. 完善进程： =1、=0；=flag1&turn=1、=flag0&turn=0;2.当P0和P1两进程都要进入临界区，并分别执行完、处的有关turn的赋值语句后，哪个进程先执行完turn的赋值语句，哪个进程就先进入临界区。理由如下：假设P0先执行turn=1，P1后执行turn=0，执行各自的while语句之前，turn=0，使P0的while循环条件为假、P1的while循环条件为真，所以P0不用while循环等待，直接跳出循环先进入临界区。八、文件系统在UNIX系统中，进程P部分程序如下：Int pid1,pid2;Int fd2;Char buf50;Pipe(fd);If(Pid1=fork()=0) close(fd1; /* 关闭写端 */read(fd0,buf,6); sleep(100);exit(1);If(pid2=fork()=0) close(fd0); /* 关闭读端 */write(fd1,”Hello”,6);sleep(100);exit(2);close(fd0);close(fd1);画图说明上述程序在exit执行前，系统中u_ofile表、file表、inode表的主要内容及表之间的联系情况，以及buf的内容。解：给定程序在执行exit前，各表主要内容及各表之间的关系如下图所示。进程P和写子进程pid2的buf值不确定，pid1读子进程的buf=H,e,l,l,o,0 ;fd0-1fd1-1 if_flagRpipef_count=1f_inode=kf_offset=6jf_flagWpipef_count=1f_inode=kf_offset