操作系统作业

2. 某采用分页存储管理的系统中，物理地址占20位，逻辑地址中页号占6位，页大小为1KB，问：该系统的内存空间大小为多少？每块的大小为多少？逻辑地址共几位，每个作业最大长度为多少？若0页放在3块中，1页放在7块中，2页放在9块中，逻辑地址0420H对应的物理地址是多少？

3.已知某分页系统，主存容量为64K，页面大小为1K，对一个4页大的作业，其0、l、2、3页分别被分配到主存的2、4、6、7块中。 (1)将十进制的逻辑地址1023、2500、4500转换成物理地址。 (2)以十进制的逻辑地址1023为例画出地址变换过程图。

：（1）对上述逻辑地址，可选计算出它们的页号和页内地址，然后通过页表转换成对应的物理地址。

①逻辑地址

3500：p=[3500/1k]=3，d=[3500/1k]取余=428，由页号可查页表找到对应的物理块号为7，

故物理地址为：7*1k+428=7596

因为页号p=4不小于页表长度4，就产生越界中断。

②逻辑地址

4500：p=[4500/1k]取整=4，d=[4500/1k]取余=404

4.某页式虚拟存储管理系统的物理空间共3K，页面大小为1K，一进程按下列地址顺序引用内存单元：3635，3632，1140，3584，2892，3640，0040，2148，1700，2145，3209，0000，1102，1100。如果上述数字均为十进制数，而内存中尚未装入任何页。给出使用OPT 、 FIFO 、 LRU时的缺页次数，并比较三种算法所得结果。

解:根据题意,分配给进程的内存块数为3,而页面的引用次序为:3﹑3﹑1﹑3﹑2﹑3﹑0﹑2﹑1﹑2﹑3﹑0﹑1﹑1。

LRU算法的情形：引用页33313132312页框303022110223132003210311FIFO算法的情形：引用页33313132312页框300122123032010311

因此可以计算出,采用LRU算法时,缺页次数为8,采用FIFO算法时, 缺页次数为6。

LRU算法用最近的过去来作为预测最近的将来的依据,一般认为其有较好的性能,但实现时,要记录最近在内存的每个页面的使用情况,比FIFO困难,其开销也大.有时,因页面的过去和未来的走向之间并无必然的联系,如上面,LRU算法的性能就没想象中那样好。

5.有一个程序要把100×100数组置初值为“0”，现假定有两个主存块可用来存放数组信息，主存块的大小为可存放200个数组元素，数组中的元素按行编址。两个主存块的初始状态都为空，若编程编制如下：

①Var A: arrary[1..100] of array[1..100] of integer; for j:=1 to 100 do for i:=1 to 100 do A[i,j]:=0;

②Var A: arrary[1..100] of array[1..100] of integer; for i:=1 to 100 do for j:=1 to 100 do A[i,j]:=0;

当采用LRU页面调度算法时各会产生多少次缺页中断？

每页存放100个数组元素，按行编址，存放顺序为A[1,1]→A[1,2] →A[1,3] →„ →A[1,100] →„ →A[100,100]。因此， A[1,1]→A[1,100] 存放在第1页， A[100,1]→A[100,100] 存放在第100页。 [1] 产生10000次缺页中断； [2] 产生100次缺页中断。

［分析]根据题意，主存块的大小为每块可存放200个数据元素，故作业信息也按每页200个元素来划分。现作业信息是由 100 X 100的数组元素组成，因而共被分成 50页。由于作业信息是按行编址的，故每顺序的两行元素在同一页面中，可被同时装到一个主存块中。

有两个主存块可供该程序使用，因而程序被装人主存时可把开始两页（共四行元素）的信息分别装人两个主存块。那么，程序执行时若按（1）的编制方法，将对每一列中的各元素顺序清“0”，即对一列中的元素都清“0”后再对下一列的元素清“0”。由于开始两页已被装人主存，所以第一列的四个元素将先被顺序清“0”。但当要对第一列的第五个元素清“0”时却发现该元素不在主存中，因而产生一次缺页中断，按LRU调度算法应淘汰最近最少使用的第一页，使腾出的主存空间可用来存放当前需访问的第三页，即装人第五、六两行元素。程序继续执行时每对两个元素初始化后都要产生一次缺页中断，因而对第一列的100个元素初始化会产生（50-2）次缺页中断。对以后的99列来说，为对每一列元素初始化都将产生50次缺页中断。故（1）的编制方法执行程序时总共会产生（50*100-2）次缺页中断。 若按（2）的编制方法，将对一行的元素都清“0”后再对下一行的元素清“0”。因而，开始的两页（四行元素）信息先被初始化。当要对第五行元素初始化时将产生缺页中断，按LRU调度算法淘汰最近最少用的第一页后可把当前需访问的包含第五、六两行元素的第三页装人主存。程序继续执行时每对两行元素全部初始化后才产生一次缺页中断，因而共会产生（50-2）次缺页中断。

[题解]程序被装人主存时可把开始两页（四行）装人所分到的主存块中。对于（1）所编制的程序执行时将按列对元素初始化，除对第一列的前四个元素初始化时不会产生缺页中断外，以后每对两个元素初始化时都要产生一次缺页中断，故缺页中断次数为（50*100-2）次。

对于（2）所编制的程序执行时将按行对元素初始化，除对前四行元素初始化时不会产生缺页中断外，以后每对两行元素初始化时都要产生一次缺页中断，故缺页中断次数为（50-2）次。