操作系统复习点

（1）将十进制的逻辑地址1023，2500，3500，4500转换成物理地址。

（2）以十进制的逻辑地址1023为例画出地址变换过程图。

答：（1）对于上述逻辑地址，可先计算出它们的页号和页内地址（逻辑地址除以页面大小得到的商为页号，余数为页内地址），然后通过页表转换成对应的物理地址：

逻辑地址1023。1023/1K，得到页号为0，页内地址为1023，查页表找到对应的物理块号为2。故物理地址为2*1K+1023=3071。

逻辑地址2500。2500/1K，得到页号为2，页内地址为452，查页表找到对应的物理块号为6。故物理地址为6*1K+452=6596。

逻辑地址3500。3500/1K，得到页号为3，页内地址为428，查页表找到对应的物理块号为7。故物理地址为7*1K+428=7596。

逻辑地址4500。4500/1K，得到页号为4，页内地址为404，因页号大于页表长度，故产生越界中断。

越界

5、    在一个批处理操作系统中，有5个作业进入系统，它们的进入时刻、估计运行时间如下表所示.

         作业号       进入时刻        估计运行时间   

          JOB1         8：00            90分钟   

          JOB2         8：10            30分钟  

          JOB3         8：30            20分钟  

          JOB4         8：50            15分钟  

          JOB5         9：20            10分钟    

    系统采用最高响应比优先作业调度算法，作业一旦被调度运行就不再退出。

    试用列表表示各个作业的运行情况，并计算出作业的平均周转时间和平均带权周转时间。

6、混合索引，文件最大长度，由偏移量得物理块号和块内偏移

7、给出四种分配方案（连续，链接，二级索引，混合索引），给出方案的比较

8、磁盘上有物理块8000个，其中第101-5999号盘块用于存放文件，请用成组链接法给出空闲盘块的组织状态图，并标出空闲盘块号栈的栈底和栈顶，说明分配和回收的过程

9、对于下表所示的段表，请将逻辑地址（0, 137），（1, 4000），（2, 3600），（5,  230）转换成物理地址。

段      表

（1，4000）：段号合法，段内地址4000超过3K，产生越界中断            

（2，3600）：70K+3600=75280                                         

（3，270）：120K+270=123150                                        

（5，230）：段号5>4，段号不合法                                    

10、什么是动态链接？用何种内存分配方法可以实现这种链接技术？

答：动态链接有装入时动态链接和运行时动态链接两种方式。装入时动态链接是指链接在装入时进行，即在装入一个目标模块时，如发生一个外部模块调用事件，则由装入程序去找出相应的外部模块，将它装入内存，并把它链接到调用者模块上。运行时动态链接是指链接在运行时进行，即在执行过程中，当发现一个被调用模块尚未装入内存时，立即由OS去找出该模块，将它装入内存，并把它链接到调用者模块上。

    采用分段存储管理方式可实现动态链接。分段方式中，段的划分由程序员或编译程序进行，每一段是一组具有相对完整意义的逻辑信息，因此用户可方便地将某个调用模块组成一个的段，从而让系统在装入程序或运行程序时将相应的模块链接到调用者模块上。

11、存放在某个磁盘上的文件系统采用混合索引分配方式，其FCB有13个地址项，第0至9个地址项为直接地址，第10个地址项为一次间接地址，第11个地址项为二次间接地址，第12个地址项为三次间接地址。如果每个盘快的大小为512字节，若盘块号需要用3个字节来描述，而每个盘块最多存放170个盘块地址，则：

1、该文件系统允许文件的最大长度是多少？

2、将文件的字节偏移量5000、15000、150000转换为物理块号和块内偏移量。

3、假设某个文件的FCB已经在内存，但其他信息均在外存，为了访问该文件中某个位置的内容，最少需要几次访问磁盘？ 

分析：在混合索引分配方式中，文件FCB的直接地址中登记有分配给文件的前n块的物理块号（n大小由直接地址项数确定，本题为10）；一次间接地址中登记有一个一次间接地址块的块号，而在一次间址块中登记有分配给文件的第n至第n+k-1块的块号（k 的大小由盘块大小和盘块号的长度决定，本题中是170）；二次简址中登记有一个二次间址块的块号，其中可给出k个一次间址块的块号，而这些一次间址块被用来登记分配给文件的第n+k块到第n+k+k2-1块的块号；三次间址中则登记有一个三次间址块的块号，其中可给出k个二次间址块的块号，这些二次间址块又可给出k2个一次间址块的块号，而这些一次间址块则被用来登记分配给文件的第n+k+k2块到第n+k+k2+k3-1块的物理块号。

1、该文件系统中一个文件的最大长度：

 最大物理块数：10 + 170 + 170*170 + 170*170*170  = 4942080 块

 文件的字节数：4942080 * 512B  = 2471040 KB

2、将文件的字节偏移量转换为物理块号及块内偏移量

       5000/512得到商为9，余数为392，即字节偏移量5000对应的逻辑块号为9，块内偏移量为392。由于9<10,故可直接从该文件的FCB的第9个地址项处得到物理盘块号，块内偏移量为392；15000/512得到商为29，余数为152，即字节偏移量15000对应的逻辑块号为29，块内偏移量为152。由于10<=29<10+170,而且29-10=19,故可从FCB的第10个地址项，即一次间址中得到一次间址块的地址，并从一次间址块的第19项(即该块的第57-59这三个字节）中获得对应的物理盘块号，块内位移量为152。

12、对于一个将页表存放在内存中的分页系统 

（1）如果访问内存需要0.2μs，有效访问时间为多少？

（2）如果加一个快表，且假定在快表中找到页表项的几率高达90%，则有效访问时间又是多少？

答：（1）有效访问时间为：2*0.2 = 0.4 μs。

   （2）有效访问时间为：0.9*0.2 + 0.1*2*0.2 = 0.22 μs。