操作系统复习题(2)及答案

最佳适配: 300k 300kb 300kb (1) (1) 100kb 512k (2) 100kb (2) 212k 112kb 112kb 150kb (3) 90kb (5) 150kb (3) (3) 150kb 60kb 150kb 150kb 100kb (2) 100kb (2) (2) 100kb 50kb 50kb 112kb (4) 62kb (4) 62kb

又申请80KB，最先适配可满足，最佳适配不能满足

12. 有一矩阵：

VAR A: ARRAY[ 1..100,1..100] OF INTEGER; 按先行后列次序存储。

在一个虚存系统中，采用LRU淘汰算法，一个进程有三页内存空间，每页可以存放200个整数，其中第一页存放程序，且假定程序已经在内存。

程序 A :

FOR I:=1 TO 100 DO FOR J:=1 TO 100 DO A [I,J] :=0;

程序B

FOR J:=1 TO 100 DO

FOR I:=1 TO 100 DO A [I,J] :=0;

分别就程序A 和 B 的执行过程计算缺页次数。

解： 共 100*100个变量，每页存放200个，共占100*100/200=50页。 A(1,1) A(3,1) A(99,1) A(1,2) A(3,2) A(99,2) ……. ……. ……….. ……. A(1,100) A(3,100) A(99,100) A(2,1) A(4,1) A(100,1) ……. ……. ……. A(2,100) A(4,100) A(100,100)

程序A的访问轨迹为：

A[1,1],A[1,2],A[1,3],…A[1,100] A[2,1],A[2,2],A[2,3],…A[2,100] . .

A[100,1],A[100,2],A[100,3],…A[100,100] 根据变量访问规律可知访问页为： 1，2，3，。。。50 中断次数为50次

程序B的访问轨迹为：

A[1,1],A[2,1],A[3,1],…A[100,1] A[1,2],A[2,2],A[3,2],…A[100,2] . .

A[1,100],A[2,100],A[3,100],…A[100,100]

可得页面访问轨迹为： 1，1，2，2，3，3，。。。。50，50，1，1，2，2，3，3，50，50，。。。。共重复100次，每次中断次数为50次，共计50*100=5000次。

13. 假定有一个开方程序SQRT,被两个进程共享，开方程序如下： （1） SQRT(X,Y)

（2） IF X<0 THEN GOTO (SQRT,L); （3） Y:=’THE RESULT OF SQRT’; （4） RETURN;

（5） (SQRT,L) :’ERROR’; （6） RETURN

若系统采用段式管理，应如何安排该程序为什么

答：该共享程序引用了自身的某个地址（语句2引用该程序自身），则各共享进程必须用同一段号来共享这一段。下面具体说明若不使用同一段号会出现何种问题：作业1和作业2分别将共享段SQRT安排在逻辑空间的第1段和0段，将出现如下问题：SQRT段调入主存时应该将语句2的符号地址转换为逻辑地址，即把（SQRT，L）转换成（段号， L）,若与作业1 一致，则为（1，L）,当作业2运行时，执行到2，则执行GOTO(1,L),按照段式系统的工作原理，应该先查段表项1，然后合成物理地址，这显然会造成错误，即转移到作业2的第一段中去。

SQRT 0段

SQRT 1段

14.

化简如图所示的资源分配图，并说明有无进程处于死锁状态

R1

R0 P0 。。 P1 R2 。 。。 R3 。 。 R4

P2 P3 P4 15. 有一个文件系统如图所示，图中的框表示目录，圈表示普通文件。根目录常驻内存，目录文件组织成链接文件，不设文件控制块，普通文件组织成索引文件。目录文件指示下一级文件名及其磁盘地址（各占2个子，共4个字节）。若下级文件是目录文件，指示其第一个磁盘块地址。若下级文件是普通文件，指示其文件控制块的磁盘地址。每个目录文件磁盘块最后4个字节供拉链使用。下级文件在上级文件目录文件中的次序在图中为自左至右。每个磁盘块有512个字节，与普通文件的一页等长。 根目录 A B C H I D E F G P M N L J K U Q R K T V W

普通文件的文件控制块组织如图所示。其中， 该文件的有关描述信息 每个磁盘地址占2个字节，前10个地址指示 磁盘地址 1 该文件前10页的地址。第11个地址指示一级 磁盘地址 2 索引表地址，一级索引表中每个磁盘地址指示 一个文件页地址；第12 个地址指示二级索引 表地址，二级索引表中每个地址指示一个一级 索引表地址；第13个地址指示三级索引表地址 磁盘地址

，三级索引表中每个地址指示一个二级索引表 11 地址。

磁盘地址

问：

12 （1） 一个普通文件最多可有多少个文件页 （2） 若要读文件J中某一页，最多启动磁盘多少次

（3） 若要读文件W中某一页，最少启动磁盘多少次

（4） 就上一问而言，为最大限度减少启动磁盘的次数，可采用什么方法此

时，磁盘最多启动多少次

答：由于一个索引表占一个磁盘块（512字节），一个磁盘地址占2个字节，因此一个一级索引表可容纳256个磁盘地址。同样，一个二级索引表可容纳256个一级索引表地址，一个三级索引表可容纳256个二级索引表地址。这样，一个普通文件最多可以有的页数为 10+256+256*256+256*256*256 对于访问文件J，首先从内存中的根目录文件中找到目录A的目录文件，读入内存（一次访问磁盘），然后再从目录A的目录文件中找出目录D的文件磁盘地址，并读入内存（第二次访问磁盘）。在目录D的目录文件中，读出文件J的文件控制块地址，并读入内存（第三次访问磁盘）。若要访问的页是文件J中通过三级索引表找到的页面，则还需要访问磁盘三次（即读入三级索引表，读入二级索引表，读入一级索引表）。

对于访问文件W,首先从内存中的根目录文件中找到目录C的目录文件，读入内存（一次访问磁盘），然后再从目录C的目录文件中找出目录I的目录文件磁盘地址，并读入内存（第二次访问内存）。然后，再依次访问目录P和目录U（第三次，第四次访问磁盘），读出文件W的文件控制块（第五次访问磁盘）。若访问的页是文件W的文件控制块中直接指出的磁盘地址，则可直接访问该页。

由于通过文件控制块访问文件时所需的访问磁盘次数无法改变，因此要减少访问磁盘的次数， 只有通过减少访问目录文件的次数来达到。 （1） 一个普通文件最多可以有的页数为页

（2） 若要读文件J 中某一页，最多启动磁盘7次 （3） 若要读文件W中某一页，最少启动磁盘6次

（4） 若要最大限度减少启动磁盘的次数，可以将文件W链接在根目录

的最左端。这样可减少4次访问磁盘的次数。此时要读文件W中某 一页，最多启动磁盘5次。

16. 今有3个并发进程R,M,和P，它们共享了一个可循环使用的缓冲区B，缓冲区B共有N个单元。进程R负责从输入设备读信息，每读一个字符后，把它存放在缓冲区B的一个单元中；进程M负责处理读入的字符，若发现读入的字符中有空格符，则把它改成‘，’；进程P负责把处理后的字符取出并打印输出。当缓冲区单元中的字符被进程P取出后，则又可用来存放下一次读入的字符。请用P,V操作写出它们能并发执行的程序。

17. 一组合作进程，执行顺序如图，请用操作实现进程间的同步操作。 P4 P2

P6 P1 P3 P5