页面置换算法

1、页面置换算法首先了解页面置换算法：在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，操作系统必须在内存中选择一个页面将其移除内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。       1、分类：最佳置换算法（OPT）：所选择的被淘汰页面将是以后永不使用的，或者是最长时间内不被访问的页面，这样可以保证获得最低的缺页率。先进先出算法（FIFO）：优先淘汰最早进入的页面，也就是在内存中停留时间最长的页面。最近最久未使用算法（LRU）：选择最近最长时间未被访问过的页面进行淘汰。最少使用（

2、LFU）置换算法、工作集算法、NRU算法等2、真题解析：某虚拟存储系统采用最近最少使用（LRU）页面淘汰算法。假定系统为每个作业分配三个页面的主存空间，其中一个页面用来存放程序。现在某作业的部分语句如下。Var A:Array1.128,1.128 OF integer;i,j:integer;FOR i:=1 to 128 DO FOR j:=1 to 128 DO Ai,j:=0; 设每个页面可存放128个整数变量，变量i、j放在程序页中，矩阵A按行序存放。初始时，程序及变量i、j已在内存，其余两页为空。在上面程序片段执行过程中，共产生_次缺页中断。最后留在内存中的是矩阵A的最后

3、_。解析：系统为每个作业分配三个页面的主存控件，其中一个存放程序，另外两个存放的是：二位数组A128，,128共128行，128列，所以每行都有128个整型变量。因为矩阵A按行序排列，又因为一个页面可以存放128个整数变量，所以一个页面存放矩阵A中的一行，两个页面存放矩阵A中的两行。其用最近最少使用页面淘汰算法（淘汰最久未被访问的页面，如1、2行先进入页面，当第三行进入页面的时候，第一行相对于第二行就是最久未被访问的页面，所以淘汰第一行，第三行进入主存）如下分析行数   1 23 4 5 . . 128 页面一  11     3  

4、     3      5       . .       页面二    2  2       4      4       . .缺页（*）   *      *     *       *      *     &#

5、160; *   *         *    128次缺页        由以上分析可知，最后留在内存中的是矩阵A的最后两行，因为是一行一行的进入的，而且内存中允许两个页面存在，再有前5行进入主存的规律分析，所以是最后两行127行和128行。在某计算机中，假设某程序的6个页面如下图所示，其中某指令“COPY A TO B”跨两个页面，且源地址A和目标地址B所涉及的区域也跨两个页面。若地址为A和B的操作数均不在内存，计算机执行该COPY指令时，系统将产生_次缺页中断；若系统产

6、生产生三次缺页中断，那么该程序应有_个页面在内存。解析：如题，系统存在6个页面，12存放指令，36将来要用来存放A的源地址和B的目标地址，当执行指令的时候，系统会去访问A的源地址和B的目标地址，因为AB本身没有存在主存中，所以每次访问的页面不在主存中，就会发生一次缺页中断。即访问AB时，36的页面都会发生缺页中断，即发生4次缺页中断。整个程序中有6个页面，若发生3次中断，应该就是进入主存35页面时发生了中断，那时程序里有35页面再内存里，即3个页面。设文件索引节中有8个地址项，每个地址项大小为4字节，其中5个地址项为直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，磁盘

7、索引块和磁盘数据块大小均为1KB。若要访问文件的逻辑块号分别为5和518，则系统分别采用_；而且可表示的单个文件最大长度是_KB。解析： (1)磁盘索引块和磁盘数据块的块长1024字节，索引块号长8*4=32字节，所以一个索引可以存放1024/32=32个盘块号直接索引可寻址的文件的最大长度1个块（1*1K=5/8KB）因为磁盘索引块的块长1024字节（1个块）一级索引可寻址的文件的最大长度32个块（32*1024B=32KB）二级索引可寻址的文件的最大长度N=32*32=1024个盘块（1024*1024B=1MB=1024KB）题中是求第5个块和518个块，分别是一级间接地址索引

8、（1<5<32+1）和二级间接地索引(32+1<518<1024+32+1)(2)1024/4=256    1024/32=32个块5个直接地址对应的文件大小5*1=5KB2个一级间接地址对应文件大小2*256*1=512KB1个二级间接地址对应文件大小1*256*256*1=65536KB单个文件的最大长度为：5+512+65536=66053KB可变分区的请求和释放分区主要有如下4种算法。· 最佳适应算法：选择等于或接近作业需求的内存自由区进行分配。这种方法可以减少碎片，但同时也可能带来更多小得无法再用的碎片。· 首次适应算法：从主存低地址开始，寻找第一个可用（即大于等于作业需求的内存）的自由区。这种方法可实现快速分配，缩短查找时间。· 最差适应法：选择整个主存中最大的内存自由区。· 循环首次适应算法：是首次适应法的一个变种，也就是不再是每次都从头开始匹配，而是连续向下匹配。（2）分页存储管理分成两部分：其一部分为页号P；后一部分为偏移量W，即页内地址。途中的地址长度为32位，其中011位为页内地址（每页的代销为4KB），1231位为页号，所以允许地址空间的大小最多为1MB个页&#