页框算法

⑴ 最佳页面置换算法的算法描述

当产生缺页中断时，利用相应的淘汰页面的算法选择需要淘汰的页面。
页面置换算法在淘汰页面时的算法：
输入：页面号引用串P1,P2...Pn；
输出：淘汰页面Pt
实现：
1、如果页框中的某个页面P以后永不使用，则该页面为淘汰页面Pt。
2、如果每个P都会再次被访问，那么其中最长未来时间内不再被访问的页面为淘汰页面Pt。

⑵ 操作系统页式存储管理的问题

存储管理的基本原理内存管理方法 内存管理主要包括内存分配和回收、地址变换、内存扩充、内存共享和保护等功能。 下面主要介绍连续分配存储管理、覆盖与交换技术以及页式与段式存储管理等基本概念和原理。 1． 连续分配存储管理方式 连续分配是操作系统页式存储管理的问题

⑶ 几种页面置换算法的基本原理及实现方法

收藏推荐 在多道程序的正常运行过程中,属于不同进程的页面被分散存放在主存页框中,当正在运行的进程所访问的页面不在内存时,系统会发生缺页中断,在缺页中断服务程序中会将所缺的页面调入内存,如内存已无空闲页框,缺页中断服务程序就会调用页面置换算法,页面置换算法的目的就是选出一个被淘汰的页面.把内存和外存统一管理的真正目的是把那些被访问概率非常高的页存放在内存中.因此,置换算法应该置换那些被访问概率最低的页,将它们移出内存.1最佳置换算法基本原理:淘汰以后不再需要的或最远的将来才会用到的页面.这是1966年Belady提出的理想算法,但无法实现,主要用于评价其他置换算法.例:分配给某进程的内存页面数是3页,页面地址流如下:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,其内存动态分配过程如下:7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 17 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 20 0 0 0 0 0 4 4 4 0 0 0 0 0 0 01 1 1 3 3 3 3 3 3 3 3 1 1 1 12先进先出置换......(本文共计2页) 如何获取本文>>

⑷ 基本分页存储管理

  阅读前请先阅读 内存管理基础 。从本文开始就介绍不连续分配的几种方式，本文主要介绍基本分页存储管理。

  假设进程A的大小为23MB，但是每个分区的大小只有10MB，如果进程只能占用一个分区，显然是放不下的。
  解决思路：如果允许进程占用多个分区，那么可以把进程拆分成 10MB + 10MB + 3MB三个部分 ，再把这三个部分别放在三个分区中（这些分区不要求连续）.....

  将内存空间分为一个个大小相等的分区（如每个分区4KB，每个分区就是一个 “页框” ，或称 “内存块” 、 “物理块” 。每个页框有一个编号，即 “页框号” ，或 “内存块号” 、 “物理块号” ，页框号 从0开始 ）。将用户进程的地址空间也分为与页框大小相等的一个个区域，称为 页面 或 页 。页框的大小不能太大，否则可能会产生过大的内存碎片。
  操作系统 以页框为单位为各个进程分配内存空间。 进程的每个页面分别放入一个页框中，即进程的 页面和内存的页框 有 一一对应 的关系。

  进程分页后，进程的各个页面可以放在不连续的页框中，所以如何实现逻辑地址到物理的地址的转换？
  如下图，将下面的进程分页，假设每页大小为50B，那么就分为4个页面。

  手动计算方法：
   页号 = 逻辑地址 / 页面长度（取整数部分）。
   页内偏移量 = 逻辑地址 % 页面长度
   页面在内存中的起始位置 ：操作系统需要用某种数据结构记录进程各个页面的起始位置。
  对于计算机，通常将 页面的大小划分为2的整数次幂 。假设用32个二进制位表示逻辑地址，页面大小为取2 12 B = 4096B = 4KB。

  如逻辑地址2，用二进制表示00000000 00000000 0000 0000 00000010 ，前24位二进制对应的十进制值就是逻辑地址2对应的页号，即0号页，而后12二进制位对应的十进制值就是偏移量。如果0号页在内存中的起始地址为X，那么逻辑地址2对应的物理地址就是 X + 2.
  同理，逻辑地址4097，用二进制表示00000000 00000000 0001 0000 00000001 ，前24位二进制对应的十进制值就是逻辑地址4097对应的页号，即1号页，而后12二进制位对应的十进制值就是偏移量。如果0号页在内存中的起始地址为Y，那么逻辑地址4097对应的物理地址就是 Y + 1.
  结论： 如果每个页面的大小为2 k B，用二进制表示逻辑地址，则末尾的K位表示页内偏移量，其余部分就是页号。
  因此，如果让 每个页面的大小为2的整数次幂， 计算机就可以很方便的得出一个逻辑地址对应的页号和页内偏移量。
  如果一个页面的大小为2KB，那分页存储管理的逻辑地址结构为：

  地址结构包括两个部分：前一个部分表示页号，后一个部分表示页内偏移量W。

  在知道如何计算页号和偏移量后，要计算实际的物理地址，还需要知道页号在内存中的起始地址，如何知道每个页面在内存中存放的位置——操作系统要为 每个进程建立一张页表。

  按照之前的方法计算出逻辑地址所对应的页号N，然后根据页表区查询实际的内存块号M，由于每个内存块号的大小都是相等的，所以实际地址 = M * 内存块大小 + 偏移量。

  在实际上，页表中是没有页号的，那怎么找到实际对应的内存块号呢？
  假设某系统物理内存大小为4GB，页面大小为4KB，则每个页表项至少应该占用多少字节？

  各页表项会 按顺序连续地 存放在内存中，如果该页表在内存中存放的地址为X，则M号页对应的页表项存放的地址为：X + M * 3B
  因此，页表的页号可以是隐含的。只需要知道 页表存放的起始地址 和 页表项长度 ，即可找到各个页号对应的页表项存放的位置，找到位置后就可以读取该位置的值，即实际内存块号。
  举个例子，如果按照逻辑地址计算出了偏移量为20，页号为1，页表中的页号是隐藏的，那么根据页表在内存中的起始地址20（假设的值），以及页表项长度3B，那么页号为1所对应的实际内存块号的值所在的地址就是：20 + 3 * 1 = 23的位置，然后在该位置的值，该值就是实际内存块号，如果是4的话，那么实际地址就是： 4 * 页面大小（4096B） + 20 = 16404。

  基本地址变换结构可以借助进程的页表将逻辑地址转换为物理地址。
  通常在系统中设置一个 页表寄存器（PTR Page-Table Register） ，存放 页表在内存中起始地址F 和 页表长度M 。
  进程在未执行时，页表的起址和页表长度放在 进程控制块（PCB）中 ，当进程被调度时，操作系统内核会把它们放在页表寄存器中。

  逻辑地址到物理地址变换的过程：

  比较页表长度，页表项长度和页面大小三个概念：

  在分页存储管理（页式管理）系统中，只要确定了每个页面的大小，逻辑地址结构就确定了。因此， 页式管理中地址是一维的。 即只要给出一个逻辑地址，系统就可以自动算出页号、页内偏移量两个部分，并不需要显示告系统这个逻辑地址中，页内偏移量占多少位。
  基本地址变换结构需要访问两次内存： 第一次访问内存查找页表；第二次访问物理内存对应的内存单元。

  对于上图，会很频繁地访问10号块中的指令、23号块。
   时间局部性 ：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行：如果某个数据被访问过，不久之后该数据很有可能再次被访问。（因此程序中存在大量循环）。
   空间局限性 ：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问。（因为很多数据在内存中都是连续存放的。如上面的数组，每次循环一次都会访问邻近的下一个元素地址）。
  在基本地址变换机构中，每次访问一个逻辑地址，都需要查询内幕才能中的页表。由于局部性原理，可能连续很多次查找到的都是一个页表项。既然如此，就可以利用这个特性减少访问页表的次数——快表。

   快表 ，又称 联想寄存器（TLB） ，是一种 访问速度比内存快很多 的高速缓冲存储器，用来存储当前访问的若干页表项，以加速地址变换的过程。与此对应，内存中的页表常称为 慢表。
  快表的地址包换过程：
  (1) CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，将页号与快表中的所有页号进行比较。
  (2) 如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再根据内存块号中与页内偏移量算地物理地址。最后访问该物理地址对应的内存单元。因此如果快表命中，则访问某个逻辑地址只需 一次 访问内存即可。
  (3) 如果没有找到匹配的页号，则就需要访问页表，需要两次访问内存，在第一次访问内存查询得到页号后，需要将页号添加到快表中，以便后面再次被访问。如果快表已满，则必须按照一定的算法对旧的页表项进行替换。
  由于查询快表比查询页表的速度快很多，因此只要快表命中，就可以节省很多时间。因为局部性原理，一般来说快表的命中率可以达到90%以上。

⑸ 内存管理

在一段时间内，程序的执行仅限于某个部分，相应地，它所访问的存储空间也局限于某个区域。

局部性原理的 分类 ：

将编译后的目标模块装配成一个可执行程序。

可执行程序以 二进制可执行文件 的形式存储在磁盘上。

链接程序的 任务 ：

程序的链接，可划分为：

重定位 ：将逻辑地址（相对地址）转换为物理地址（绝对地址）的过程。

物理地址 = 逻辑地址 + 程序在内存中的起始地址

程序的装入，可划分为：

任何时刻主存储器 最多只有一个作业 。

每个分区 大小固定不变 ：分区大小相等、分区大小不等。

每个分区可以且 仅可以装入一个作业 。

使用 下限寄存器 和 上限寄存器 来保存当前作业的起始位置和结束位置。

使用 固定分区说明表 区分各分区的状态。

分区 大小不是预先固定的 ，而是按作业（进程）的实际需求来划分的。

分区 个数也不是预先固定的 ，而是由装入的作业数决定的。

使用 空闲分区表 说明空闲分区的位置。

使用 空闲分区链 说明空闲分区的位置。

首次适应算法的 过程 ：

外部碎片：空闲内存 没有在 分配的 进程 中。

内部碎片：空闲内存 在 分配的 进程 中。

从 上次找到的 空闲分区的 下一个 空闲分区开始查找。

优点：空闲区分布均匀、查找开销较小。

缺点：缺乏大空闲区。

最佳适应算法的 过程 ：

优点：提高内存利用率。

注意点：每次在进行空闲区的修改前，需要先进行 分区大小递增 的排序。

页 ：将一个 进程 的 逻辑地址空间 分成若干个 大小相等 的 片 。

页框 ：将 物理内存空间 分成与页大小相同的若干个 存储块 。

分页存储 ：将进程的若干 页 分别装入多个 可以不相邻 的 页框 中。

页内碎片 ：进程 最后一页 一般装不满一个页框，形成 页内碎片 。

页表 ：记录描述页的各种数据，实现从 页号 到 页框号 的映射。

注意： 页内偏移量 的单位是 字节 。

分页地址变换指是： 逻辑地址 通过 地址变换机构 变换为 物理地址 。

分页地址变换的 过程 ：

操作系统在修改或装入页表寄存器的值时，使用的是 特权级 指令。

页大小：512B ~ 4KB，目前的计算机系统中，大多选择 4KB 大小的页。

页大小的 选择因素 ：

快表也称为“转换后援缓冲”，是为了提高CPU访问速度而采用的专用缓存，用来存放 最近被访问过的页表项 。

英文缩写：TLB。

组成： 键和值 。

在TLB中找到某一个页号对应的页表项的百分比称为 TLB命中率 。

当 能 在TLB中找到所需要的页表项时：

有效访问时间 = 一次访问TLB 的时间 + 一次访问内存 的时间（访问内存读写数据或指令）

当 不能 在TLB中找到所需要的页表项时：

有效访问时间 = 一次访问TLB 的时间 + 两次访问内存 的时间（一次访问内存页表，一次访问内存读写数据或指令）

将页表再分页，形成两级或多级页表，将页表离散地存放在物理内存中。

在进程切换时，要运行的进程的页目录表歧视地址被写入 页表寄存器 。

在二级分页系统中，为页表再建立一个页目录表的目的是为了能在地址映射时得到页表在物理内存中的地址，在页目录表的表项中存放了每一个 页表 在物理内存中所在的 页框号 。

虚拟存储器 ：是指具有 请求调入功能 和 置换功能 ，能 从逻辑上对内存容量进行扩充 的一种存储系统。

请求调入 ：就是说，先将进程一部分装入内存，其余的部分什么时候需要，什么时候请求系统装入。

置换 ：如果请求调入时，没有足够的内存，则由操作系统选择一部分内存中的进程内容移到外存，以腾出空间把当前需要装入的内存调入。

为了实现请求分页，需要：

保证进程正常运行的所需要的最小页框数。

最小页框数与进程的大小没有关系，它与计算机的 硬件结构 有关，取决于 指令的格式、功能和寻址方式 。

内存不够时，从进程本身选择淘汰页，还是从系统中所有进程中选择？：

采用什么样的算法为不同进程分配页框？：

常用的两种 置换策略 ： 局部置换 和 全局置换 。

从分配给进程的页框数量上看，常使用的两种 分配策略 ： 固定分配 和 可变分配 。

用新调入的页替换 最长时间没有访问 的页面。

找到 未来最晚被访问 的那个页换出。

，P为缺页率。

有效访问时间与缺页率成 正比 ，缺页率越高，有效访问时间越长，访问效率越低。

工作集 ：某段时间间隔里，进程实际要访问的页的集合。

引入工作集的 目的 ：降低缺页率，提高访问内存效率。

抖动 ：运行进程的大部分时间都用于页的换入换出，几乎不能完成任何有效果工作的状态。

抖动的 产生原因 ：

抖动的 预防方法 ：

在分段存储管理的系统中，程序使用 二维 的逻辑地址，一个数用来表示 段 ，另一个数用来表示 段内偏移量 。

引入分段的 目的 ：

引入分段的 优点 ：

进程的地址空间被划分成 若干个段 。

每个段定义了一组逻辑信息，每个段的大小由相应的逻辑信息组的长度确定， 段的大小不一样 ，每个段的逻辑地址从0开始，采用一段 连续的地址空间 。

系统为每个段分配一个 连续的物理内存区域 ，各个 不同的段可以离散 地放入物理内存不同的区域。

系统为 每个进程建立一张段表 ，段表的每一个表项记录的信息包括： 段号、段长和该段的基址 ，段表存放在内存中。

分段的 逻辑地址结构 ：

段表是由操作系统维护的用于支持分段存储管理 地址映射 的数据结构。

每个进程有一个段表，段表由段表项构成。每个段表项包括： 段号、段长（段的大小）和该段的基址（段的起始地址） 。

若已知逻辑单元的地址为 S:D （段号:段内偏移量），求相应物理地址的步骤如下：

相同点 ：分页和分段都属于 离散 分配方式，都要通过数据结构与硬件的配合来实现 逻辑地址到物理地址 的映射。

不同点 ：

将用户进程的逻辑空间 先划分为若干个段 ， 每个段再划分成若干个页 。

进程以页为单位在物理内存中 离散 存放，每个段中被离散存放的页具有 逻辑相关性 。

为了实现地址映射，操作系统为 每个进程建立一个段表 ，再为 每个段建立一个页表 。

进程段表的段表项组成：

满足以下条件的两个块称为 伙伴 ：

⑹ 实际中操作系统能为一个进程分配多少个页框

根据LRU算法，需要替换上次使用距现在最远的页面。
首先2,3,2这三页进入内存（进程只分配到3个页面，切顺序为由内到外，第二个2进入时不缺页，所以共缺页2次），1进入时，内存不满且内存中没有1这个页面即第1个进入内存，所以顺序是2,3,1（缺页1次）；下一个进入的是5，替换3（缺页1次），得到2，1，5；下一个进入的是2，内存中有2号页面，进行下一个页面；下一个进入4,4替换1，得到2,5,4（缺页1次）；下一个进入5，内存中有5号页面，进行下一个页面；下一个进入3，3替换2，得到3,5,4（缺页1次）；下一次进入2,2替换4，得到3,5,2（缺页1次）；后面2号和5号内存中均存在，则不需要替换。所以一共发生了7次缺页.

⑺ 分页存储管理的实现原理

采用分页存储器允许把一个作业存放到若干不相邻的分区中，既可免去移动信息的工作，又可尽量减少主存的碎片。分页式存储管理的基本原理如下：

1、 页框：物理地址分成大小相等的许多区，每个区称为一块；
2、址分成大小相等的区，区的大小与块的大小相等，每个称一个页面。
3、 逻辑地址形式：与此对应，分页存储器的逻辑地址由两部分组成，页号和单元号。逻辑地址格式为 页号 单元号（页内地址） 采用分页式存储管理时，逻辑地址是连续的。所以，用户在编制程序时仍只须使用顺序的地址，而不必考虑如何去分页。

4、页表和地址转换：如何保证程序正确执行呢？
采用的办法是动态重定位技术，让程序的指令执行时作地址变换，由于程序段以页为单位，所以，我们给每个页设立一个重定位寄存器，这些重定位寄存器的集合便称页表。页表是操作系统为每个用户作业建立的，用来记录程序页面和主存对应页框的对照表，页表中的每一栏指明了程序中的一个页面和分得的页框的对应关系。绝对地址=块号*块长+单元号 以上从拓扑结构角度分析了对称式与非对称式虚拟存储方案的异同,实际从虚拟化存储的实现原理来讲也有两种方式;即数据块虚拟与虚拟文件系统. 数据块虚拟存储方案着重解决数据传输过程中的冲突和延时问题.在多交换机组成的大型Fabric结构的SAN中,由于多台主机通过多个交换机端口访问存储设备,延时和数据块冲突问题非常严重.数据块虚拟存储方案利用虚拟的多端口并行技术,为多台客户机提供了极高的带宽,最大限度上减少了延时与冲突的发生,在实际应用中,数据块虚拟存储方案以对称式拓扑结构为表现形式. 虚拟文件系统存储方案着重解决大规模网络中文件共享的安全机制问题.通过对不同的站点指定不同的访问权限,保证网络文件的安全.在实际应用中,虚拟文件系统存储方案以非对称式拓扑结构为表现形式. 虚拟存储技术,实际上是虚拟存储技术的一个方面,特指以CPU时间和外存空间换取昂贵内存空间的操作系统中的资源转换技术 基本思想:程序,数据,堆栈的大小可以超过内存的大小,操作系统把程序当前使用的部分保留在内存,而把其他部分保存在磁盘上,并在需要时在内存和磁盘之间动态交换,虚拟存储器支持多道程序设计技术 目的:提高内存利用率 管理方式
A 请求式分页存储管理 在进程开始运行之前,不是装入全部页面,而是装入一个或零个页面,之后根据进程运行的需要,动态装入其他页面;当内存空间已满,而又需要装入新的页面时,则根据某种算法淘汰某个页面,以便装入新的页面

B 请求式分段存储管理 为了能实现虚拟存储,段式逻辑地址空间中的程序段在运行时并不全部装入内存,而是如同请求式分页存储管理,首先调入一个或若干个程序段运行,在运行过程中调用到哪段时,就根据该段长度在内存分配一个连续的分区给它使用.若内存中没有足够大的空闲分区,则考虑进行段的紧凑或将某段或某些段淘汰出去,这种存储管理技术称为请求式分段存储管理

⑻ 页面置换算法淘汰某一页后的页框号怎么处理

我也是刚刷题看到的，想了一下，有些见解，有误还望指正。
1.操作系统调出页面0到外存
2.页面1调入内存(我想这里把页面1的内容放到了101H这个地址)
因此页号1对应的页框号是101h

⑼ 如果将FIFO页面置换算法用到4个页框和8个页面上，若初始时页框为空，访问字符串为0172327103，请问会发生

FIFO的页框：
x0172333300
xx017222233
xxx01777722
xxxx0111177
LRU的页框：
x0172327103
xx017232710
xxx01773271
xxxx0111327
FIFO发生6次缺页，LRU为7次