操作系统复习习题

各章的作业请大家自己复习！
1．假定在某移动臂磁盘上，刚刚处理了访问75号柱面的请求，目前正在80号柱面上读信
息，并有下列请求序列等待访问磁盘：
请求序列：l 2 3 4 5 6 7 8
欲访问的柱面号：160 40 190 188 90 58 32 102
试用(1)电梯调度算法；(2)最短查找时间优先算法，分别排出实际处理上述请求的次序。

答：(1)电梯调度算法是从移动臂当前位置开始，沿臂的移动方向取选择离当前移动
臂最近的柱面访问，如果该方向上没有访问请求，则改变臂的方向再选择。

从题中可以看出，先访问的是75柱面，正在访问80柱面。

显然移动臂当前的移动方向是从小柱面号到大柱面号。

所以采用电梯调度算法，先依次访问的应该是90、102、160、188、190号柱面，之后掉转方向去依次访问58、
40、32号柱面。

(2)最短查找时间优先算法每次总是让查找时间最短的请求先执行，不管它是不是先访问的，也不管
它在什么方向上。

所谓查找时间最短的是指移动臂从当前位置移动要访问的若干个位置中移动距离最短的位置上所花的时间。

针对本题，依次先处理的是90、102号柱面后，磁头当前离58号柱面有44个柱面的距离，而离160号柱面有58个柱面的距离，显然要先访问58号柱面，依次下去访问的应该是40、32、160、188、190号柱面。

(1)用电梯调度算法处理次序是5、8、1、4、3、6、2、7。

(2)用最短查找时间优先算法处理的次序5、8、6、2、7、l、4、3。

2．假定磁盘转速为20毫秒／周，磁盘格式化时每个盘面被分为8个扇区，今有8个逻辑记录要存放在同一磁道上供处理程序使用，处理程序每次从磁盘上读出一个记录后要花5毫秒进行处理，现在用户要求顺序处理这8个记录，请回答下列问题：
(1)应怎样安排这8个记录，使得处理它们时能保证最高效率．
(2)按照最优分布时，计算出磁盘需旋转几圈，才能使处理程序顺序处理完这8个记录·
解：
(1)如图A-11所示，将记录以交叉方式存放才能获得最高的效率，且记录之间间隔的扇区
数与传输速度有关密切。

图A-11记录交叉方式存放图
(2)已知磁盘转速为20ms/周，每个盘面有8个扇区，则读一个扇区的时间为：
20／8=2.5(ms)
又因为处理一个记录的时间为：5ms，所以读出并处理一个记录的时间为： 2.5+5=7.5(ms)
若按上图的顺序存放记录，这时，记录2正好转到了磁头下，正好可以读出记录2，再处理记录2，也需要7.5ms的时间．其他记录同样．所以全部处理完这
8个记录共需时间：
7.5*8 = 60(ms)
正好需要转的圈数为：
60／20 = 3(圈)
3、设有4个进程P1，P2，P3，P4共享一组资源r1，r2，r3，r4，假定在某个时刻它们的资源分配状态如下图所示，要求：
（1）给出该状态的资源分配图RAG。

（2）化简该RAG。

（3）判断该状态是否为死锁状态。

解：有4个进程P1，P2，P3，P4共享一组资源r1，r2，r3，r4，假定在某个时刻它们的资源分配状态如下图所示，存在安全序列：〈P3，P2，P1，P4〉，系统不会发生死锁。

4、某系统有r1，r2，r3，r4这4类资源供P1，P2，P3，P4，P5这5个进程共享，进程对资源的需求和分配情况如下表所示。

现在系统还剩下资源r1，r2，r3，r4分别为1，5，2，0个，请按银行家算法回答下面问题：
进程及资源分配情况一览表
进程已占有资源数最大需求数
r1 r2 r3 r4 r1 r2 r3 r4
P1 0 0 1 2 0 0 1 2
P2 1 0 0 0 1 7 5 0
P3 1 3 5 4 2 3 5 6
P4 0 6 3 2 0 6 5 2
P5 0 0 1 4 0 6 5 6
（1）现在系统是否处于安全状态。

（2）如果进程P2提出申请资源申请R2=（0，4，2，0），系统能否满足它的请求。

解：某系统有r1，r2，r3，r4这4类资源供P1，P2，P3，P4，P5这5个进程共享，由进程对资源的需求和分配情况，可得状态图如下所示：
（1）现在系统是安全的。

安全序列：〈P1，P3，P4，P5，P2〉
执行过事：
（a）W=A=(1,5,2,0),Ui≠0，故F[i ]=false (I=1,2,3,4,5)。

（b）找到i=1,有R1≤W且F[1]= false，故W=W+U1=（1，5，3，2），F[1]：=ture。

找到i=3,有R3≤W且F[3]= false，故W=W+U3=（2，8，8，4），F[3]：=ture。

找到i=4,有R4≤W且F[4]= false，故W=W+U4=（2，14，11，6），F[4]：=ture。

找到i=5,有R5≤W且F[5]= false，故W=W+U5=（2，14，12，10），F[5]：=ture。

找到i=2,有R2≤W且F[2]= false，故W=W+U2=（3，14，12，10），F[2]：=ture。

（c）对所有i=1，2，3，4，5，都有F[i]：=ture，则RAG可以完全化简，故S(t)为非死锁状态。

（2）若P2请求分配资源（0，4，2，0），则系统能满足它的请求。

现在R2=（0，4，2，0）
(a) R2=（0，4，2，0），N2=（0，7，5，0），有R2≤N2。

（b）R2=（0，4，2，0），A=（1，5，2，0），有R2≤A。

（c）假分配。

A：=A-R2=（1，5，2，0）-（0，4，2，0）=（1，1，0，0）
U2：=U2+R2=（1，0，0，0）+（0，4，2，0）=（1，4，2，0）
N2：=N2-R2=（0，7，5，0）-（0，4，2，0）=（0，3，3，0）
那么，得到新状态如下图：
（d）执行安全算法：
W=A=（1，1，0，0）F[i]=false （i=1，2， (5)
找到i=1有F[1]=false，N1≤W
置F[1]：=ture，且W=W+U1=（1，1，0，0）+（0，0，1，2）=（1，1，1，2）
找到i=3有F[3]=false，N3≤W
置F[3]：=ture，且W=W+U3=（1，1，1，2）+（1，3，5，4）=（2，4，6，6）
找到i=4有F[4]=false，N4≤W
置F[4]：=ture，且W=W+U4=（2，4，6，6）+（0，6，3，2）=（2，10，9，8）
找到i=5有F[5]=false，N5≤W
置F[5]：=ture，且W=W+U5=（2，10，9，8）+（0，0，1，4）=（2，10，10，12）
找到i=2有F[2]=false，N2≤W
置F[2]：=ture，且W=W+U2=（2，10，10，12）+（1，4，2，0）=（3，14，12，12）
得到安全序列：〈P1，P3，P4，P5，P2〉
（e）实施真分配。

5．表6．8列出了A、B、C和D共4个作业到达系统的时间、运行时间、开始时间及各自完成的时间，采用FCFS算法、短作业优先，计算各自的周转时间和带权周转时间和等待时间，分析结果可以得出什么结论?
表6．8 FCFS调度下4个作业的执行情况表
解：采用FCFS算法。

各进程的周转时间和带权等待时间，如表A．13所示，分析结果可知，FCFS算并没有照顾短进程C，致使进程C的带权周转时间很长。

表A．13采用FCFS算法各进程运行情况表
6．试给出构成SPLOOLing系统的各个部分，它们各有什么功能?
答：(1)预输入程序模块：负责把用户的作业信息从输入设备读入输入井中。

(2)井管理程序模块：负责管理输入井和输出井。

(2)缓输出程序模块：负责检查输出井中是否有要输出的信息，如果有，则启动打印机或其
他输出设备输出用户作业的结果。

7.考虑一个有760个字节程序的如下存贮器引用：
12，90，351，190，180，475，30，550，635，650，227，430，640，710，745，10，15，650，740，249
(1)假定主存贮器中每块为100个字节，对于以上存贮器的引用序列，给出其页面走向．
(2)假定主存贮器中每块为100个字节，有3块可供该程序使用，采用页式虚拟存储管理方式，程序开始
执行时已程序的前三页装入主存，试分别给出采用先进先出页面置换算法和最近最少用页面置换法时产生缺页中断的次数(设FIFO时先顺序置换O，1，2页，LRU时先置换O页)。

解：（1）因为主存贮器中每块为100个字节，因此逻辑上每页也为100个字节，对于给定的存贮器引用地址，除以100后取整，即是该地址所在页面号，因此，页面走向为： 0，0，3，1，1，4，0，5，6，6，2，4，6，7，7，0，0，6，7，2
（2）因为执行前已将前面三页装入主存即：0，1，2页在主存，故对于FIFO 置换算法，如图所示，共产生11次缺页中断。

页面存取顺序：（FIFO ）
页面存取顺序：（续上图）
对于LRU 置换算法如下图，共10次缺页中断。

页面存取顺序：（LRU ）
页面存取顺序：（续上图）。