操作系统习题答案.doc

习题一(前三章)1、 系统如何由目态转为管态？如何由管态转为目态？目态到管态的转换(中断，trap)：修改处理机状态字指令属于特权指令，只能在管态执行，目态程序无法直接控制处理机状态的转换。处理机状态由目态转换为管态的唯一途径是中断，中断发生时，中断向量中的PSW标识处于管态，这个标识一般由操作系统初始化程序设置的。管态到目态的转换(置程序状态字)：通过修改程序状态字(置PSW)来实现，操作系统运行于管态，该状态转换伴随着由操作系统程序到用户程序的转换。2、 为什么有硬件时钟，有时还要设置软件时钟？解：硬件时钟由硬件提供，保存在硬件寄存器中，开机由电源供电，关机由机内电池供电，可由程序设定和修改，一般通过特权指令完成，应用程序可读取该值。不发生中断。间隔时钟：定时发生中断，一般间隔单位为“毫秒”。中断发生后，操作系统获得系统的控制权，以便运行系统管理和实现程序并发。是实现多道程序的基础保证操作系统获得控制权。软件时钟：利用间隔时钟实现，主要用于定时启动一些服务，如定时备份，软件时钟通过赋内存的一个单元一个初值，通过间隔时钟中断，对该单元值减一，减到0就启动相应的服务，这是间隔时钟做不到的。3、 通过一个案例分析进程的状态转换过程。 比如用播放器播放音乐，当启动播放器，产生播放器进程，进入挂起就绪状态，当用户点击播放按钮时，进入就绪状态，当被处理机调度时，处于运行态，当需要听歌曲，且歌曲还在外存时，该进程启动磁盘读进程，然后自己进入等待态，当磁盘读进程将相应歌曲读进内存时，向处理机发出中断，该中断进程将播放器进程送入就绪队列，当被处理机调度时，开始播放歌曲，处于运行态，如此反复，直到关闭播放器，进程结束。 单击暂停键，进入挂起就绪队列4、 通过一个案例描述可以由用户处理的中断的处理过程。比如在一个C语言程序中发生除零错误（1）发生出除零中断（2）保存旧PSW和PC(入系统栈)（3）取中断向量（4）转到中断处理程序（5）访问中断续元表（假定非0）（6）系统栈中现场转移到用户栈（7）中断续元入口送寄存器（OS中断处理完成）（8）执行中断续元 中断续元的执行同目态子程序 （9）用户栈PSW和PC送寄存器 （10）中断执行完，遇RET指令由用户栈弹出现场信息送入处理机 （11）返回中断断点 5、下表列出了四个进程到达时间和执行时间，使用先来先服务算法、循环（时间片2）、短作业优先、响应比高者优先的调度算法的调度过程，分别计算每个调度算法的周转时间、平均周转时间、带权周转时间、带权平均周转时间. 画出相应的Gantt图进程到达时间执行时间A03B16C44D62解：先来先服务算法A B C D 0 3 9 13 15进程 到达时间 运行时间 开始时间 完成时间 周转时间 带权周转时间 A0 3 0 3 31 B1 6 3 98 8/6 =1.33C 44 9 13 9 9/4 =2.25D62131599/2=4.5平均周转时间 =(3+8+9+9)/4=7.25 平均带权周转时间 =(1+1.33+2.25+4.5)/4=2.27 循环（时间片2）A B C D A B C B0 2 4 6 8 9 11 13 15周转时间: 由就绪开始时刻到处理完毕时刻的时间带权周转时间：周转时间/运行时间等待时间(waiting time)：周转时间与处理时间之差进程 到达时间 运行时间 开始时间 完成时间 周转时间 等待时间带权周转时间 A0 3 0 9 969/3=3 B1 6 21514 814/6 =2.33C 44 4 13 9 59/4 =2.25D6268202/2=1平均周转时间 =(9+14+9+2)/4=8.5 平均等待时间 = (6+8+5+0)/4=4.75平均带权周转时间 =(3+2.33+2.25+1)/4=2.145 短作业优先进程到达时间执行时间A03B16C44D62A B D C 0 3 9 11 15 进程 到达时间 运行时间 开始时间 完成时间 周转时间 带权周转时间 A0 3 0 3 33/3=1 B1 6 398 8/6 =1.33C 44 11 15 11 11/4 =2.75D6291155/2=2.5平均周转时间 =(3+8+11+5)/4=6.75 平均带权周转时间 =(1+1.33+2.75+2.5)/4=1.895 响应比高者优先RR=1+WT/BT在 9时刻出现了D和CC的响应比=1+5/4=2.25D的响应比=1+3/2=2.5A B D C 0 3 9 11 15 进程 到达时间 运行时间 开始时间 完成时间 周转时间 带权周转时间 A0 3 0 3 33/3=1 B1 6 398 8/6 =1.33C 44 1115 11 11/4 =2.75D6291155/2=2.5平均周转时间 =(3+8+11+5)/4=6.75 平均带权周转时间 =(1+1.33+2.75+2.5)/4=1.895 7、在一个使用多级反馈队列的系统中，一个只使用CPU的进程的执行时间为40秒，如果第1队列时间片为2，每级时间片增加5个时间单元，那么这个作业运行结束前会被中断多少次，结束时处于哪级队列？解3：进程被中断的情况有：在时刻2（第1队列），在时刻2+7（第2队列），在时刻9+12（第3队列），在时刻21+17（第4队列），当该进程结束时位于第5队列，中断4次。练习二 互斥、同步与通信1、 设有3个进程R、W1和W2，共享缓冲区B，B中每次只能存放一个数，当B中无数据时，可以从输入设备上读数据到B中，若数为奇数时允许W1取出打印，否则允许W2取出打印，W1和W2每次仅能打印一次，它们不能从空的B中取数据。解：设信号量sr表示是否可读，初值为1 设信号量sp1表示w1进程是否可打印，初值为0 设信号量sp2表示w2进程是否可打印，初值为0cobegin sr, sp1, sp2 :semaphore :=1,0,0; x :integer; process reader process w1 process w2 begin begin begin repeat repeat reapet p(sr); p(sp1); p(s2p); 读入一个数放入x; 打印x1; 打印x1; if x mod 2 = 0 then v(sp2) v(sr); v(sr); else until false; until false; v(sp1); end; end; until false; end;end;2、 有3个好朋友预定在一个地方集合，然后一起去看电影，请用PV描述他们的同步操作。解： 定义一个计数器，统计到达的人数：count，初值为0 定义三个同步信号量s1，s2，s3，表示是否可以去看电影，初值都不可以看，为0 定义一个互斥信号量mutex，用于对count的互斥访问 var count :integer :=0; s1,s2,s3,mutex :semaphore :=0,0,0,1;P1进程 P2进程 P3进程P(mutex) p(mutex) p(mutex)Count := count+1; count := count+1; count := count+1V(mutex); v(mutex) v(mutex)If count=3 then if count=3 then if count=3 thenBegin begin begin V(s2); v(s1); v(s1); V(s3); v(s3); v(s2);End end endElse else else P(s1); p(s2); p(s3);练习三 互斥、同步与通信1、两进程PA，PB通过两FIFO缓冲区队列连接（如图），每个缓冲区长度等于传送消息长度。进程PA，PB之间的通信满足如下条件： buf0 buf1(1) 至少有一个空缓冲区存在时，相应的发送进程才能发送一个消息。(2) 当缓冲队列中至少存在一个非空缓冲区时，相应的接收进程才能接收一个消息。试描述发送过程send(i,m)和接收过程receive(i,m)。这里i代表缓冲区。解：bufempty0、bufempty1表示缓冲区是否空，初值为nbuffull0、buffull1 表示缓冲区是否满，初值为0buf0、buf1表示两个缓冲区 Send(i,m) Begin local x P(bufemptyi) 按FIFO方式选择一个空缓冲区 bufi(x)=m bufi(x)置满标记 V(buffulli) End Receive(i,m) Begin Lccal x P(buffulli) 按FIFO方式选择一个装满数据的缓冲区bufi(x) m=bufi(x) bufi(x)置空标记 V(bufemptyi) End Pa调用send(0,m)和receive(1,m) Pb调用send(1,m)和receive(0,m)2、设有三组进程PA，PB，PC，PA进程每次从磁盘中读入一条记录到缓冲区1中，缓冲区1可存放N条记录，PB进程每次只能从缓冲区1中取出一条记录到缓冲区2中，缓冲区2可存放N/2条记录，PC进程每次只能从缓冲区2中取出一条记录来打印，请用管程描述它们之间的同步操作。解：本题中，PA是一个生产者，PB既是生产者又是消费者，PC是消费者， 解：条件变量： notfull1: 表示B1是否满， notfull2： 表示B2是否满 notempty1：表示B1是否空， notempty2：表示B2是否空k1,k2: 分别表示在B1中PA放记录的位置和PB取记录的位置，初值为0。t1,t2: 分别表示在B2中PB放记录的位置和PC取记录的位置，初值为0。count1, count2：分别表示B1存放记录数和B2存放记录数.初值为0。count1=n： 表示B1已满，这时PA进程不能再读入记录到B1中，将wait(notfull1)count1=n/2： 表示B2已满，这时PB进程不能从B1中读记录到B2中，将wait(notfull2)，当count1=0时表示B1中无记录，PB不能从B1中取记录，将wait(notempty1)count20：表示PB可以从B1中取1条记录到B2中，此时检查是否有等待B2的记录，若有则将singal(notempty2)count2=n then wait(notfull1); B1k1 := item; k1 :=(k1+1) mod n; count1:=count1+1; signal(notempty1);end;procedure entry getput(item)begin if count2=n/2 then wait(notfull2); if count1 =0 then wait(notempty1); B2t1 := B1k2; t1 :=(t1+1) mod n/2; k2 :=(k2+1) mod n; signal(notfull1); signal(notempty2);end;procedure entry get(item)begin if count2 =0 then wait(notempty2); 打印B2t2; t2 := (t2+1) mod n/2; signal(notfull2)end;begin k1=k2=t1=t1=0; count1=-count2=0;end;process PA process PB process PCbegin begin begin repeat repeat repeatread an item; PC.getput(item); PC.get(item);PC.put(item); untill false; print item; Untill false; end; untill false;End; end;练习四 死锁1、某系统采用死锁检测手段发现死锁，设系统中资源类集合为A，B，C，资源类A中共有17个实例，资源类B中共有5个实例，资源类C中共有20个实例又设系统中进程集合为p1,p2,p3,p4,p5, T0时刻系统状态如下： Allocation Need Available A B C A B C A B C p1: 2 1 2 3 4 7 p2: 4 0 2 1 3 4 p3: 4 0 5 0 0 6p4: 2 0 4 2 2 1 p5: 3 1 4 1 1 0在T0时刻是否安全，请给出安全系列在T0时刻若进程P2请求资源（0 3 4），能否实现分配，为什么？在(2)的基础上，若进程P4请求资源(2 0 1) ，能否实现分配，为什么？在(3)的基础上，若进程P1请求资源(0 2 0) ，能否实现分配，为什么？解：(1)由已知可知，系统剩余资源为(2 3 3) Allocation Need Available Work Finish A B C A B C A B C A B C p1: 2 1 2 3 4 7 2 3 3 p2: 4 0 2 1 3 4 p3: 4 0 5 0 0 6p4: 2 0 4 2 2 1p5: 3 1 4 1 1 0 Work Allocation Need Work+ Allocation Finish A B C A B C A B C A B C p1: 7 4 11 2 1 2 3 4 7 9 5 13 true3p2: 9 5 13 4 0 2 1 3 4 13 5 15 true4 p3: 13 5 15 4 0 5 0 0 6 17 5 20 true5p4: 2 3 3 2 0 4 2 2 1 4 3 7 true1p5: 4 3 7 3 1 4 1 1 0 7 4 11 true2可以找到一个系列p4,p5,p1,p2,p3(2) 在T0时刻若进程P2请求资源（0 3 4），因请求资源大于剩余资源(2 3 3)，不能分配(3) 在(2)的基础上，若进程P4请求资源(2 0 1)，由于请求资源(2 0 1)需求资源(2 2 1)， 请求资源(2 0 1) 剩余资源(2 3 3)，进行试分配 Allocation Need Available A B C A B CA B C p1: 2 1 2 3 4 7 0 3 2 p2: 4 0 2 1 3 4 p3: 4 0 5 0 0 6p4: 4 0 5 0 2 0 p5: 3 1 4 1 1 0再使用安全性检测算法，得到 Work Allocation Need Work+ Allocation Finish A B C A B C A B C A B C p1: 7 4 11 2 1 2 3 4 7 9 5 13 true3p2: 9 5 13 4 0 21 3 4 13 5 15 true4 p3: 13 5 15 4 0 5 0 0 6 17 5 20 true5p4: 0 3 2 4 0 5 0 2 0 4 3 7 true1p5: 4 3 7 3 1 4 1 1 0 7 4 11 true2可以找到一个系列p4,p5,p1,p2,p3(4) 在(3)的基础上，若进程P1请求资源(0 2 0), 由于请求资源(0 2 0)需求资源(3 4 7)，请求资源(0 2 0) 剩余资源(0 3 2)，进行试分配Allocation Need Available A B C A B C A B C p1: 2 3 2 3 2 7 0 1 2 p2: 4 0 2 1 3 4 p3: 4 0 5 0 0 6p4: 4 0 5 0 2 0 p5: 3 1 4 1 1 0由于资源（0 1 2）不能满足任何进程故不能分配2、有三类资源R1,R2,R3，R1和R2资源数分别为，R3为，有四个进程P1,P2,P3,P4，每个进程占用资源和等待资源的情况如下：进程已占资源类已占用个数 等待的资源P1 R3 , R2 1 ,1 R1P2 R1 1 -P3 R1 1 R2P4 R2 1 R3请画出资源分配图，使用资源分配图的约简证明是否产生死锁。P2 解：R1 P3 R2 P1 P4 R3 (1)该图中非孤立节点且没有请求边的是P2(2)去掉分配边成为孤立节点P2 R1 P3 R2 P1 R3 P4 (3)寻找请求边可以满足的节点，并将请求边改为分配边P2 R1 P3 R2 P1 R3 P4 (4)没有请求边的是P1，去掉分配边成为孤立节点P2 R1 P3 R2 P1 R3 P4 P2 (5)寻找请求边可以满足的节点，并将请求边改为分配边R1 P3 R2 P1 R3 P4 (6)没有请求边的是P3,P4，去掉分配边成为孤立节点P2 R1 P1 P3 R2 R3 P4 (7)最后全部为孤立节点，系统没有死锁3、在A、B两车站之间为单轨，且在中间有一个小站C，小站C为双轨道，给出一个无死锁、无饿死、并发度最高的算法，使用PV实现。 解： C1 A B C2 若AB方向火车在小站C走上边轨道，BA方向走下边轨道，则： 当同时不超过3辆火车时，不会发生死锁 设信号量 train=3 AC、BC为单轨，设信号量 ac=1 bc=1 C站： c1=1 c2=1 A到B B到C P(train) P(train) p(ac) p(bc) ac上行驶 bc上行驶 p(c1) p(c2) 进入C小站 进入C小站 v(ac) v(bc) p(bc) p(ac) 出C站 出C站 v(c1) v(c2) bc上行驶 ac上行驶 到达B 站 到达A站 v(bc) v(ac) v(train) v(train)若AB和BA方向在小站C不规定轨道，则： 当同时不超过2辆火车时，不会发生死锁 设信号量 train=2 AC、BC为单轨，设信号量 ac=1 bc=1 A到B B到C P(train) P(train) p(ac) p(bc) ac上行驶 bc上行驶 进入C小站 进入C小站 v(ac) v(bc) p(bc) p(ac) 出C站 出C站 bc上行驶 ac上行驶 到达B 站 到达A站 v(bc) v(ac) v(train) v(train)练习五 存储1、一个物理内存为64MB的计算机系统，该系统的内存管理模式为页式，页长为4KB，用户程序的一个逻辑地址为6D9C（16进制），进程页表如下 进程页表 4 2 22 16 222 18 3 9 11 126 30 12 0 请计算： 1) 内存物理地址用多少位表示 2) 逻辑地址结构图 3) 逻辑页号和物理页号（10进制） 4) 物理地址（16进制）解：1) 内存物理地址用多少位表示 64M26220226 内存物理地址用26位表示 2) 逻辑地址结构图 页长为4KB，4K22210212 所以页地址位数为12位， （6D9C）16（0110 1101 1001 1100）2逻辑地址结构图：逻辑页号 页内位移0000000000 0110 1101 1001 1100逻辑页号页内位移0000000000 01101101 1001 1100 3) 逻辑页号和物理页号（10进制） 逻辑页号=6，物理页号34) 物理地址（16进制）（0000000000 0011 1101 1001 1100）2(3D9C)162、 在一个请求分页存储管理系统中，进程P的访问串为3，2，2，1，4，3，2，3，1，2，4，1，当分配给该进程的页面数为3时，请用LRU置换算法计算访问过程中发生的缺页次数和缺页率。（请用表的方式写出计算过程）.解：3 22143231241333444112223334111222缺缺缺缺缺缺缺缺缺页次数：缺页率：3、在采用页式存储管理的系统中，页长128B，现某个用户编写将128*128的数组设置初值为0的个程序for i:=1 to 128(2) for j:=1 to 128for j:=1 to 128 for i:=1 to 128 ai,j :=0; ai,j:=0假设在分页时将数组中的每一行放在一页中，并且分该用户在内存中只有一页的内存，请计算分别运行上述两个程序，各会产生多少缺页中断。解：(1) 第一行不是缺页，则发生127次缺页第一行是缺页，则发生128次缺页 (2) 第一行第一列不是缺页，则发生128*128-1次缺页第一行第一列是缺页，则发生128*128次缺页