操作系统例题讲解

-10 -操作系统例题讲解、调度算法对如下表所示的 5个进程:进程到达时间(ms)优先级CPU阵发时间(ms)P1233P2012P3443P4024P5552采用可剥夺的静态最高优先数算法进行调度(不考虑系统开销)问题：画出对上述5个进程调度结果的 Gantt图;计算5个进程的平均周转时间、平均带权周转时间。 解：调度结果的Gantt图如下：P4P1P3P5P3P1P4P2024579101214(2)时间计算:进程到达时间(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/15 = 3.07(ms)、存储管理某系统采用虚拟页式存储管理方式，页面大小为2KB ,每个进程分配的页框数固定为4页。采用局部置换策略，置换算法采用 改进的时钟算法，当有页面新装入内存时，页表的时钟指针指向新装入页面的下一个在内存的表项。设当前进程P的页表如下(“时钟”指针指向逻辑页面3的表项)逻辑页号012345页框号访问位r修改位m内外标识101H001一0110H101138H001一0100H111问 题： 当进程P依次对逻辑地址执行下述操作： 引用 4c7H; 修改19B4H ; 修改 0C9AH ;写出进程P的页表内容； 在的基础上，当 P对逻辑地址27A8H进行访问，该逻辑地址对应的物理地址是多少？解： 页面大小为 2KB , 2KB= 2X 210=211,即逻辑地址和物理地址的地址编码的低11位为页内偏移；(1) 逻辑地址4c7H=0 100 1100 0111B,高于11位为0,所以该地址访问逻辑页面0;引用4C7H,页表表项 0: r=1 ; 逻辑地址19B4H=0001 1 001 1011 0100 B,高于11位为3,所以该地址访问逻辑页面3;修改19B4H ,页表表项 3： r=1, m=1; 逻辑地址0c9AH=0000 11 00 1001 1010 B,高于11位为1,所以该地址访问逻辑页面1;逻辑页1不在内存，发生缺页中断；逻辑页号2*3页框号访问位r修改位m内外标识101H101一0110H101138H111一0100H111按改进的时钟算法，且时钟指针指向表项3,应淘汰0页面,、两操作后， P的页表如下:即把P的逻辑页面1读到内存页框101H ,页表时钟指针指向表项2并执行操作：修改0C9AH 。逻辑页号012345页框号访问位r修改位m内外标识一000101H111110H001138H011一0100H011经上述3个操作后，P的页表如下: 逻辑地址27A8H=0010 0 111 1010 1000 B,高于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请求序列的调度序列，并计算磁头引臂的移动量； 计算：总寻道时间(启动时间忽略)、总旋转延迟时间、总传输时间和总访问处理时间。解：(1)考虑序列中有重复磁道的I/O请求，调度序列 为：60-75503020151065 7080磁头移动量=(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 (磁道) 总寻道时间 =1 X 155=155 (ms)一次访盘的旋转时间=1/(2R)=1/(2 X 7500/min)=(60 X 1000)/(2 X 7500)ms=4(ms)请求序列共12次访盘，总旋转延迟时间 =4X 12=48(ms)1 次访盘的传输时间 =1/(R X32)=(60 X 1000)/(7500 X 32)=1/4ms12次访盘 总传输时间=1/4 X 12=3(ms)总访盘处理时间 =155+48+3=206(ms)四、文件系统(1)给出“用户打开文件表”和“系统打开文件表”的形式，并图示二者之间的联系;(2)说明写文件系统调用命令write(fd,buf,count)的实现过程。解：用户打开文件表和系统打开文件表图示如下：文件 描述符打开 方式读写 指针系统打开 文件表入口fd1进程P1的用户打开文件表文件 描述符打开 方式读写 指针系统打开 文件表入口fd2进程P2的用户打开文件表FCB主部文件号共享计数修改标志1520/1系统打开文件表(2) write(fd,buf,count)的实现过程如下：参数含义：fd ：文件描述符；count：写出记录个数； buf ：内存起始位置；执行步骤： 由fd查找用户打开文件表，找到对应的系统打开文件表入口；根据用户打开文件表中所记录的打开方式和存取方式核查访问的合法性；查系统打开文件表，找到文件的地址；计算欲访问起始记录的地址；如果需要，申请存储块； 将内存中由buf起始的count个记录写到文件中由当前写指针所确定的区域;调整用户打开文件表的读写指针。五、死锁问题某系统采用死锁检测发现死锁。设系统有资源类集合为P5并发运行。当前系统状态如下：R= A, B, C , 6 个进程 P0、P1、P2、P3、P4、ABCABCABCP0100000221P1321000P2012202P3000000P4210031P5001000allocationrequestavailable问题:(1)在上述状态下，系统依次接收请求：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),系统状态变化如下:P0P1P2P3P4P5ABCABCABC200000121321210012202000002210031001000allocationrequestavailable上一状态没有死锁。因为，用死锁检测算法，进程 P5、P0、P1、P2、P3、P4能依次运行完。 在所确定的状态下，系统接收请求：request0=(0,3,1),系统状态变化如下:P0P1P2P3P4P5ABCABCABC200031121321210012202000002210031001000allocationrequestavailable对上一状态用死锁检测算法，P5、P3能完成，P0、P1、P2、P4不能完成,发生死锁，参与死锁的进程为P0、P1、P2、P4o六、信号量与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,防止对方饿死 */P1P2P3P4P2P1西面过河者算法：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);V上独木桥过河;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 );东面过河者算法：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);V上独木桥过河;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 );)优先算法调度 CPU。已知四个进程 P1、P2、P3、ProcessArrival timeBurst timeP1010P236P343P474七、处理机调度算法某系统按最短剩余时间(Shortest Remaining Time FirstP4的到达时间和 CPU阵发时间如下(时间单位：毫秒)：问题：(1)画出按最短剩余时间优先的CPU调度算法得到的进程调度结果的Gantt图;计算四个进程的平均等待时间、平均周转时间、平均带权周转时间。解： 按最短剩余时间优先调度算法的进程调度结果Gantt图：0347111623四个进程的平均等待时间、平均周转时间、平均带权周转时间见下表:进程到达时间运行时间开始时间完成时间等待时间周转时间带权周转时间P1010023132323/10P23631671313/6P34347031P474711041平均等待时间=(13+7+0+0) /4=20/4=5 ms平均周转时间=(23+13+3+4) /4=43/4=10.75 ms平均带权周转时间=( 23/10+13/6+1+1) /4=194/(30*4 尸 1.62 ms八、进程互斥并发进程P0和P1关于共享变量的临界区分别为临界区的不完整 的C伪代码如下： int flag2=0,0;/* 公共变量 */int turn;/*公共变量*/进程P0：do flag0=1;turn=;while （ ）do continue; ；flag0=0;其余代码; while（1）;region。和regionl。用软件方法解决P0和P1互斥进入其进程P1：do flag1=1; turn= ； while ( )do continue; ；flag1=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循环等待，直接跳出循环先进入临界区。九、存储管理设某计算机主存按字节编址，容量为512KB ;系统采用虚拟页式存储管理方式，虚拟地址空间为4MB ,页面大小为4KB,每个进程分配的页框数固定为4页。采用局部置换策略， 置换算法采用 改进的时钟算法（“时钟”指针初始指向第一个调入页面）。主存空闲区管理采用空闲页面表的结构，存储分配采用下次适应算法（即从上次分配下标的下一个表项开始分配）。系统对上次内存请求，分配了下标为1的空闲区中的页框后，空闲页面表如下（表中数字均为10进制）：问题:下标首页框号页框个数020413562803395204.0空闲页面表（1）该计算机内存的物理地址编码是多少位？当进程P初始运行，对逻辑页面的操作依次为修改0页；引用1页；修改2页；改3页写出进程P的页表内容，页表表项为：（逻辑页号、页框号、访问位r、修改位 m）; 在的基础上，当 P依次对逻辑地址 97B0H和逻辑地址 0B7B0H均进行修改访问时，这两个逻辑地址 访问的逻辑页号和物理地址各是多少？解：该计算机主存容量为512KB=2 9X210bytes= 219所以该机内存物理地址编码为19位；当进程P初始运行，访问的逻辑页面依次为：修改0、引用1、修改2、修改3时,按下次适应算法应该从下标为2的空闲区开始依次分配，进程P的页表如下：逻辑页号页框号（十进制）访问位r修改位m08011195102201133511逻辑地址 97B0H=00,0000,1001,0111,1011,0000B ; （ 4MB = 222bytes,故逻辑地址为 22 位）因为页面大小为 4KB=2 12bytes,所以地址的低12位为页内偏移，高于 12位的部分为逻辑页号。所以逻辑地址 97B0H访问的逻辑页号为 9,该逻辑页未调入内存，发生缺页；由于固定分配 4个页框，且已分配了4个页框，按局部置换的修改的时钟算法置换，时钟指针应从逻辑页号0的表项开始，9号逻辑页置换的逻辑页为1,其页框为95号页框；95=5FH ,所以逻辑地址 97B0H访问的19位物理地址为 101,1111,0111,1011,0000B = 5F7B0H此时页表的第二项为：（9,95,1,1）逻辑地址 0B7B0H=00,0000,1011,0111,1011,0000B ;所以逻辑地址 0B7B0H访问的逻辑页号为11,该页未调入内存，发生缺页；采用局部置换改进的时钟算法，并考虑上次置换时清过的访问位，应置换逻辑页面2,由于逻辑页面 2分配的是20号页框，20=14H , 所以逻辑地址 0B7B0H 访问的20位物理地址为 001,0100,0111,1011,0000B = 147B0H十、文件系统在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,T,o,0 ;Fd0 Fd1-1Pid1 的 U ofileif_flag = Wpipe f_count=1 f_inode=k f offset=6f_flag = Rpipe f_count=1 f_inode=k foffset=6Fd0Fd1内存file表i count=2Helloi_addr0=bi_addr1 7=null磁盘块Pid2 的 U ofile1一、设备与I/O管理0、1内容in ode表199;磁头移动一个磁道所需时设系统磁盘只有一个移动磁头，磁道由外向内编号为:间为1毫秒；每个磁道有 32个扇区；磁盘转速R=6000r/min.系统对磁盘设备的I/O请求采用 N-Step Look（即N-Step Scan,但不必移动到磁道尽头），N=4。设当前磁头在50号磁道，向内移动。现有对磁道的I/O请求序列：12, 24, 7, 60, 30, 77, 5, 26, 61, 80, 53, 66 ;每个I/O请求访问磁道上的1个扇区。题：写出给定磁道的I/O请求序列的调度序列，并计算磁头的移动量；(4)对给定I/O请求序列，计算：总寻道时间（启动时间忽略）、总旋转延迟时间、总传输时间和总访问 处理时间。解：调度序列为（不包括括号内的磁道）：(50) - 60 24 12 752630 77 80 6661 53磁头移动量 =(60-50)+(60-24)+(24-12)+(12-7)+(7-5)+(26-5)+(30-26)+(77-30)+(80-77)+(80-66)+(66-61)+(61-53)=10+36+12+5+2+21+4+47+3+14+5+8=167 (磁道)总寻道时间=1 X 167=167 ( ms)一次访盘的旋转时间=1/(2R)=1/(2 X 6000/min)=(60 X 1000)/(2 X 6000)ms=5(ms)请求序列共12次访盘，总旋转延迟时间 =5X 12=60(ms)1 次访盘的传输时间 =1/(R X32)=(60 X 1000)/(6000 X 32)=5/16(ms)12次访盘 总传输时间=5/16 X 12=3.75(ms)总访盘处理时间=167+60+3.75=230.75(ms)十二、死锁问题设系统有资源集合为R= A, B, C , 5个进程P0、P1、P2、P3、P4并发运行。按银行家算法，当前系统状态如下：ABCABCABC554010211432221652101322211443002P0P1P2P3P4ClaimAllocationAvailable问题：(1)系统中各类资源总量是多少？ 矩阵Need的值是多少？判断当前系统状态是否安全？ 在当前状态下，如果进程P0提出资源请求request0=(1,0,0),系统能否实施分配？说明原因解：系统各类资源总量( A, B, C) = (7, 5, 6);矩阵need的值如下：NeedABC544211551111441ABCABCABCABC554110444111432221211652101551322211111443002441在当前系统状态下，可找到进程安全状态序列：所以当前系统状态是安全状态； 在当前系统状态下，进程P0提出资源请求request0=(1,0,0),系统预分配后的状态如下：ClaimAllocationNeedAvaiableP0P1P2P3P4该系统状态可找到进程安全序列: ,所以系统能满足该请求。十三、信号量与P/V操作侏罗纪公园内有一个恐龙博物馆和一个花园，游客先步行参观恐龙博物馆，然后乘游览车游览花园。设共有n辆游览车(有司机)，每辆游览车一次只能搭载一位游客。试用信号量和PV操作实现游客和游览车之间的同步。要求：(1)给出信号灯及其它变量的定义；(2)分别给出游客和游览车的活动。解：设游客与游览车的进程分别为tourist 和car ；信号量定义及算法如下：Int car_statusn; /*初值为均为 0, car_statusi表示i号车的X大态,0空闲，1占用。*/semphore car_waitn; /*初值均为 0,用于游客与i号车的上车、启动的同步。*/semphore car_stopn; /*初值均为 0,用于游客与i号车的下车、停车的同步。 */semphore downn; /*初值均为0,用于游客下车与i号车空闲的同步。*/semaphore S; /*初值为n,用于n辆游览车的管理；*/semaphore mutex;初值为1,用于修改车状态的互斥；void tourist()参观博物馆;P(S);/*有空闲游览车？*/P(mutex);在car_status中找一空闲车i;car_status1=1;V(mutex);上i号游览车；V(car_waiti) ; /* 游客已上车 */游览花园；P(car_stopi); /* 停车了 ? */下i号游览车；V(downi); /*游客已下车*/void car( int i) do P(car_waiti);/* 游客上车？ */ 启动、行驶(顾客游览)； 停车；V(car_stopi);/*通知游客已停车*/P(downi);/* 游客下车？ */P(mutex);car_statusi=0; /* 车空闲 */ V(mutex);V(S); while(1);六、同步互斥问题P4, P5, P6六个进程，其执行次序如下图所示:设有 P1, P2, P3,其含义是：P1首先执行；只有P1执行完，才能执行 P2;只有P2执行完，才能执行 P3和P4;只有P1和P3都执行完，才能执行 P5;只有P3、P4、P5都执行完，才能执行 P6。问 题：试用信号量和 巳V操作来完成上述六个进程的同步控制。要 求：对定义的信号量说明其含义和初值。解：信号量定义及进程如下：Semphore S1,S2,S3,S4; /*初值均为0,用于进程同步*/进程P1:进程P2:进程P3:进程P4 :进程P5:进程P6:P1代码;P(S1)P(S2)P(S2)P(S3)P(S4)V(S1);P2代码;P3代码;P4代码 ;P(S3)P(S4)V(S3);V(S2);V(S3);V(S4);P5代码;P(S4)V(S2);V(S4);V(S4);P6代码;- 11 -