最佳适配:

又申请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的访问轨迹为：

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的第一段中去。

14.

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

15. 有一个文件系统如图所示，图中的框表示目录，圈表示普通文件。根目录常驻内存，目录文件组织成链接文件，不设文件控制块，普通文件组织成索引文件。目录文件指示下一级文件名及其磁盘地址（各占2个子，共4个字节）。若下级文件是目录文件，指示其第一个磁盘块地址。若下级文件是普通文件，指示其文件控制块的磁盘地址。每个目录文件磁盘块最后4个字节供拉链使用。下级文件在上级文件目录文件中的次序在图中为自左至右。每个磁盘块有512个字节，与普通文件的一页等长。

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

（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） 一个普通文件最多可以有的页数为16843018页 （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. 一组合作进程，执行顺序如图，请用操作实现进程间的同步操作。