页式存储管理

1. 基本原理

页式存储管理是把主存储器划分成大小相等的若干区域，每个区域称为一块，并对它们加以顺序编号，如0#块、1#块等等。与此对应，用户程序的逻辑地址空间划分成大小相等的若干页，同样为它们加以顺序编号，从0开始，如第0页、第1页等。 页的大小与块的大小相等。
分页式存储管理的逻辑地址由两部分组成：页号和页内地址。其格式为：

2. 存储空间的分配与去配
分页式存储管理把主存空间划分成若干块，以块为单位进行主存空间的分配。由于块的大小是固定的，系统可以采用一张主存分配表来记录已分配的块、尚未分配的块以及当前剩余的空闲块总数。最简单的办法可用一张“位示图”来记录主存的分配情况。
例如主存的用户区被划分成512块，则可用字长为32位的16个字的位示图来构成一张主存分配表，位示图中的每一位与一个物理块对应，用0/1表示对应块的占用标志（空闲/已占用），另用一个字节记录当前系统的剩余空闲块总数。

进行主存分配时，首先查看空闲块总数是否能够满足作业要求，若不能满足，则不进行分配；若能满足，则从位示图中找出为“0”的位，并且将其占用标志置为“1”，并从空闲块总数中减去本次占用的块数，按找到的位计算出对应的块号，建立该作业的页表，并把作业装入对应的物理块中。
由于每一块的大小相等，在位示图中查找到一个为“0”的位后，根据它所在的字号、位号，按如下公式可计算出对应的块号：
块号＝字号×字长＋位号
当一个作业执行结束时，则应该收回作业所占的主存块。根据归还的块号计算出该块在位示图中对应的位置，将占用标志修改为“0”，同时把归还块数加入到空闲块总数中。假定归还块的块号为i，则在位示图中对应的位置为：
字号＝[ i / 字长 ]， 位号＝i mod 字长
其中[ ]表示对i除以字长后取其整数，而mod表示对i除以字长后取其余数部分。

3. 页表与地址转换
在分页式存储管理系统中，允许将作业的每一页离散地存储在主存的物理块中，但系统必须能够保证作业的正确运行，即能在主存中找到每个页面所对应的物理块。为此，系统为每个作业建立了一张页面映像表，简称页表。页表实现了从页号到主存块号的地址映像。作业中的所有页（0~n）依次地在页表中记录了相应页在主存中对应的物理块号。页表的长度由进程或作业拥有的页面数决定。

调度程序在选择作业后，将选中作业的页表始址送入硬件设置的页表控制寄存器中。地址转换时，只要从页表寄存器中就可找到相应的页表。当作业执行时，分页地址变换机构会自动将逻辑地址分为页号和页内地址两部分，以页号位索引检索页表，如果页表中无此页号，则产生一个“地址错”的程序性中断事件；如果页表中有此页号，则可得到对应的主存块号，再按逻辑地址中的页内地址计算出欲访问的主存单元的物理地址。因为块的大小相等，所以
物理地址=块号×块长＋页内地址

4. 总结

• 目的
  减少分区管理的“碎片”，提高内存利用率。
• 实现原理
  各个进程的虚拟空间被划分为若干个长度相等的页，并为各页加以编号，如第0页、第1页等 ；
  内存空间也按相同的页大小划分为存储块，称为(物理)块或页框(frame)， 也同样为它们加以编号，如0＃块、1＃块等等。
  为进程分配内存时，以块为单位将进程的若干个页分别装入到多个可以不相邻接的物理块中。
  采用页表进行页和块的一一对应。
  

段式存储管理

用户编制的程序是由若干段组成的：一个程序可以由一个主程序、若干子程序、符号表、栈以及数据等若干段组成。每一段都有独立、完整的逻辑意义，每一段程序都可独立编制，且每一段的长度可以不同。
段式存储管理支持用户的分段观点，具有逻辑上的清晰和完整性，它以段为单位进行存储空间的管理。

1. 原理
每个作业由若干个相对独立的段组成，每个段都有一个段名，为了实现简单，通常可用段号代替段名，段号从“0”开始，每一段的逻辑地址都从“0”开始编址，段内地址是连续的，而段与段之间的地址是不连续的。
其逻辑地址由段号和段内地址两部分所组成：

2. 空间的分配与去配
分段式存储管理是在可变分区存储管理方式的基础上发展而来的。在分段式存储管理方式中，以段为单位进行主存分配，每一个段在主存中占有一个连续空间，但各个段之间可以离散地存放在主存不同的区域中。为了使程序能正常运行，即能从主存中正确找出每个段所在的分区位置，系统为每个进程建立一张段映射表，简称“段表”。每个段在表中占有一个表项，记录该段在主存储器中的起始地址和长度。段表实现了从逻辑段到主存空间之间的映射。

如果在装入某段信息时找不到满足该段地址空间大小的空闲区，则可采用移动技术合并分散的空闲区，以利于大作业的装入。
当采用分段式存储管理的作业执行结束后，它所占据的主存空间将被回收，回收后的主存空间登记在空闲分区表中，可以用来装入新的作业。系统在回收空间时同样需要检查是否存在与回收区相邻的空闲分区，如果有，则将其合并成为一个新的空闲分区进行登记管理。
段表存放在主存储器中，在访问一个数据或指令时至少需要访问主存两次以上。为了提高对段表的存取速度，通常增设一个相联寄存器，利用高速缓冲寄存器保存最近常用的段表项。

3. 地址转换与存储保护
段式存储管理采用动态重定位方式装入作业，作业执行时通过硬件的地址转换机构实现从逻辑地址到物理地址的转换工作，段表的表目起到了基址寄存器和限长寄存器的作用，是硬件进行地址转换的依据。

分页和分段存储管理的主要区别

分页和分段系统都采用离散分配主存方式，都需要通过地址映射机构来实现地址变换，有许多相似之处。但两者又是完全不同的。具体表现如下。

• 页是信息的物理单位，是系统管理的需要而不是用户的需要；而段则是信息的逻辑单位，它含有一组意义相对完整的信息，分段是为了更好地满足用户的需要。
• 页的大小固定且由系统决定，因而一个系统只能有一种大小的页面；而段的长度却不固定，由用户所编写的程序决定，通常由编译程序对源程序进行编译时根据信息的性质来划分。
• 分页式作业的地址空间是一维的，页间的逻辑地址是连续的；而分段式作业的地址空间则是二维的，段间的逻辑地址是不连续的。

段页式存储管理

段式存储管理支持了用户的观点，但每段必须占据主存储器的连续区域，有可能需要采用移动技术汇集主存空间，为此，兼用分段和分页的方法，构成可分页的段式存储管理，通常被称为是“段页式存储管理”。段页式存储管理兼顾了段式在逻辑上的清晰和页式在管理上方便的优点。

1. 原理
用户对作业采用分段组织，每段独立编程，在主存空间分配时，再把每段分成若干个页面，这样每段不必占据连续的主存空间，可把它按页存放在不连续的主存块中。
段页式存储管理的逻辑地址格式如下：

段页式存储管理为每一个装入主存的作业建立一张段表，且对每一段建立一张页表。段表的长度由作业分段的个数决定，段表中的每一个表目指出本段页表的始址和长度。页表的长度则由对应段所划分的页面数所决定，页表中的每一个表目指出本段的逻辑页号与主存物理块号之间的对应关系。

2. 地址转换机制
执行指令时，地址机构根据逻辑地址中的段号查找段表，得到该段的页表始址，然后根据逻辑地址中的页号查找该页表，得到对应的主存块号，由主存块号与逻辑地址中的页内地址形成可访问的物理地址。如果逻辑地址中的段号超出了段表中的最大段号或者页号超出了该段页表中的最大页号，都将形成“地址越界”的程序性中断事件。
可以看出，由逻辑地址到物理地址的变换过程中，需要三次访问主存，第一次是访问主存中的段表，获得该段对应页表的始址，第二次是访问页表，获得指令或数据的物理地址，最后再按物理地址存取信息。

3. 特点

• 每一段分为若干页，再按页式管理，页间不要求连续；
• 用分段方法分配管理作业或进程，用分页方法分配管理内存；
• 兼有段式和页式管理的优点,系统复杂性和开销增大.

**

页式存储管理

**

一、页式存储管理的基本原理

【页式存储管理的基本原理】

• 分页存储器将主存划分成多个大小相同的页架
• 受页架尺寸限制，程序的逻辑地址也自然分页
• 不同的页可以放在不同页架中，不需要连续
• 页表用于维系进程的主存完整性
  

【页式存储管理中的地址】

• 页式存储管理的逻辑地址由两部分组成：页号和单元号，逻辑地址形式：
  
• 页式存储管理的物理地址也有两部分组成：页架号和单元号，物理地址形式：
  
• 地址转换（直接把页号变为页架号）可以通过查页表完成

【页式存储管理的地址转换思路】

【页式存储管理的内存分配/去配】

• 可用一张位示图来记录主存分配情况
• 建立进程页表维护主存逻辑完整性
  

【页的共享】

• 页式存储管理能够实现多个进程共享程序和数据
• 数据共享：不同进程可以使用不同页号共享数据页
• 程序共享：不同进程必须使用相同页号共享代码页
  #共享代码中的（JMP<页内地址>）指令，使用不同页号时做不到

二、页式存储管理的地址转换

【页式存储管理的地址转换代价】

• 页表放在主存：每次地址转换必须访问两次主存
  1.按页号读出页表中的相应页架号
  2.按计算出来的绝对地址进行读写
• 存在问题：降低了存取速度
• 解决方法：利用Cache存放部分页表

【页式存储管理的快表】

• 为提高地址转换速度，设置一个专用的高速存储器，用来存放页表的一部分
• 快表：存放在高速存储器中的页表部分
• 快表表项：页号，页架号
• 这种高速存储器是联想存储器，即按照内容寻址，而非按照地址访问

【引入快表后的地址转换代价】

• 采用快表后，可以加快地址转换速度
• 假定主存访问时间为200毫微秒，快表访问时间为40毫微秒，查快表的命中率是90%。平均地址转换代价为：（200+40）*90%+（200+200）*10%=256毫微秒
• 比两次访问主存的时间（400毫微秒）下降了36%

【基于快表的地址转换流程】

• 按逻辑地址中的页号查快表
• 若该页已在快表中，则由页架号和单元号形成绝对地址
• 若该页不在快表中，则再查主存页表形成绝对地址，同时将该页登记到快表中
• 当快表填满后，又要登记新页时，则需在快表中按一定策略淘汰一个旧登记项

【多道程序环境下的进程表】

• 进程表中登记了每个进程的页表
• 进程占有处理器运行时，其页表起始地址和长度送入页表控制寄存器
  

【多道程序环境下的地址转换】

三、页式虚拟存储管理

【页式虚拟存储管理的基本思想】

• 把进程全部页面装入虚拟存储器，执行时先把部分页面装入实际内存，然后，根据执行行为，动态调入不在主存的页，同时进行必要的页面调出
• 现代OS的主流存储管理技术
• 首次只把进程第一页信息装入主存，称为请求页式存储管理

【页式虚拟存储管理的页表】

• 需要扩充页表项，指出
  #每页的虚拟地址、实际地址
  #主存驻留标志、写回标志、保护标志、引用标志、可移动标志
  

【页式虚拟管理的实现】

• CPU处理地址
  #若页驻留，则获得块号形成绝对地址
  #若页不在内存，则CPU发出缺页中断
• OS处理缺页中断
  #若有空闲页架，则根据辅存地址调入页，更新页表与快表等
  #若无空闲页架，则决定淘汰页，调出已修改页，调入页，更新页表与快表

【页式虚拟存储管理的地址转换】

【缺页中断的处理流程】

四、页面调度

【页面调度】

• 当主存空间已满又需要装入新页时，页式虚拟存储管理必须按照一定的算法把已在主存的一些页调出去
• 选择淘汰页的工作称为页面调度
• 选择淘汰页的算法称为页面调度算法
• 页面调度算法如果设计不当，会出现（刚被淘汰的页面立即又要调入，并如此反复）这种现象称为抖动或颠簸

【缺页中断率】

• 假定进程P共n页，系统分配页架数m个
• P运行中成功访问次数为S，不成功访问次数为F，总访问次数A=S+F
• 缺页中断率定义为：f=F/A
• 缺页中断率是衡量存储管理性能和用户编程水平的重要依据

【影响缺页中断率的因素】

• 分配给进程的页架数：可用页架数越多，则缺页中断率就越低
• 页面的大小：页面尺寸越大，则缺页中断率就越低
• 用户的程序编制方法：在大数据量情况下，对缺页中断率也有很大影响

【用户编程的例子】

• 程序将数组置为“0”，假定仅分得一个主存页架，页面尺寸为128个字，数组元素按行存放，开始时第一页在主存
  

【OPT页面调度算法】

• 理想的调度算法是：当要调入新页面时，首先淘汰以后不再访问的页，然后选择距现在最长时间后再访问的页
• 该算法由Belady提出，称Belady算法，又称最佳算法（OPT）
• OPT只可模拟，不可实现

【先进先出FIFO页面调度算法】

• 总是淘汰最先调入主存的那一页，或者说主存驻留时间最长的那一页（常驻的除外）
• 模拟的是程序执行的顺序性，有一定合理性

【最近最少用LRU页面调度算法】

• 淘汰最近一段时间较久未被访问的那一页，即那些刚被使用过的页面，可能马上还要被使用到
• 模拟了程序执行的局部属性，既考虑了循环性又兼顾了顺序性
• 严格实现的代价大（需要维持特殊队列）

【LRU算法的模拟实现】

• 每页建一个引用标志，供硬件使用
• 设置一个时间间隔中断：中断时页引用标志置0
• 地址转换时，页引用标志置1
• 淘汰页面时，从页引用标志为0的页中随机选择
• 时间间隔多长是个难点

【最不常用LFU页面调度算法】

• 淘汰最近一段时间内访问次数较少的页面，对OPT的模拟性比LRU更好
• 基于时间间隔中断，并给每一页设置一个计数器
• 时间间隔中断发生后，所有计数器清0
• 每访问页1次就给计数器加1
• 选择计数值最小的页面淘汰

【时钟CLOCK页面调度算法】

• 采用循环队列机制构造页面队列，形成了一个类似于钟表面的环形表
• 队列指针则相当于钟表面上的表针，指向可能要淘汰的页面
• 使用页面引用标志位

【CLOCK算法的工作流程】

• 页面调入主存时，其引用标志位置1
• 访问主存页面时，其引用标志位置1
• 淘汰页面时，从指针当前指向的页面开始扫面循环队列
  #把所遇到的引用标志位是1的页面的引用标志位清0，并跳过
  #把所遇到的引用标志位是0的页面淘汰，指针推进一步

五、反置页表

【反置页表的提出】

• 页表及相关硬件机制在地址转换、存储保护、虚拟地址访问中发挥了关键作用
• 为页式存储管理设置专门硬件机构
• 内存管理单元MMU：CPU管理虚拟/物理存储器的控制线路，把虚拟地址映射为物理地址，并提供存储保护，必要时确定淘汰页面
• 反置页表IPT：MMU用的数据结构

【反置页表的基本设计思想】

• 针对内存中的每个页架建立一个页表，按照块号排序
• 表项包含：正在访问该页架的进程标识、页号及特征位，和哈希链指针等
• 用来完成内存页架到访问进程页号的对应，即物理地址到逻辑地址的转换

【反置页表的页表项】

• 页号：虚拟地址页号
• 进程标志符：使用该页的进程号（页号和进程标志符结合起来标志一个特定进程的虚拟地址空间的一页）
• 标志位：有效、引用、修改、保护和锁定等标志信息
• 链指针：哈希链

【基于反置页表的地址转换过程】

• MMU通过哈希表把进程标识和虚页号转换成一个哈希值，指向IPT（反置页表）的一个表目
• MMU遍历哈希链找到所需进程的虚页号，该项的索引就是页架号，通过拼接移位便可生成物理地址
• 若遍历整个反置页表中未能找到匹配表项，说明该页不在内存，产生缺页中断，请求操作系统调入

【反置页表下的地址转换示意】

• 未显示选择淘汰页面，同样由MMU完成

**

段式存储管理

**

一、段式存储管理

【段式程序设计】

• 每个程序可由若干段组成，每一段都可以从“0”开始编址，段内的地址是连续的
• 分段存储器的逻辑地址由两部分组成
  #段号：单元号
  #和页式存储管理（段号：单元号）有本质区别。“段号：单元号”是用户程序设计自己设定的。而“页号：单元号”是系统自动切割的，用户并不知道。所以分页存储器是用户编程原则上不可见的，除了性能优化。而分段存储器是用户可控制的

【程序的分段结构】

【段式存储管理的基本思想】

• 段式存储管理基于可变分区存储管理实现，一个进程要占用多个分区
• 硬件需要增加一组用户可见的段地址寄存器（代码段、数据段、堆栈段、附加段），供地址转换使用
• 存储管理需要增加设置一个段表，每个段占用一个段表项，包括：段始址、段限长，以及存储保护、可移动、可扩充等标志位

【段式存储管理的地址转换流程】

【段的共享】

• 通过不通进程段表中的项指向同一个段基址来实现
• 对共享段的信息必须进行保护，如规定只能读出不能写入，不满足保护条件则产生保护中断

二、段式虚拟存储管理

【段式虚拟存储管理的基本思想】

• 把进程的所有分段都存放在辅存中，进程运行时先把当前需要的一段或几段装入主存，在执行过程中访问到不在主存的段时再把他们动态装入
• 段式虚拟存储管理中断的调进调出是由OS自动实现的，对用户透明
• 与段覆盖基数不同，它是用户控制的主存扩充技术，OS不感知

【段式虚拟存储管理的段表扩充】

• 段表的扩充
  #特征位：00（不在内存）01（在内存）11（共享段）
  #存取权限：00（可执行）01（可读）11（可写）
  #扩充位：0（固定长）1（可扩充）
  #标志位：00（未修改）01（已修改）11（不可移动）
  

【段式虚拟存储管理的地址转换】

三、段页式存储管理

【段页式存储管理的基本思想】

• 段式程序设计可以基于页式存储管理实现
• 每一段不必占据连续的存储空间，可存放在不连续的主存页架中
• 能够扩充位段页式虚拟存储管理
• 装入部分段，或者装入段中部分页面

【段页式存储管理的段表和页表】

【段页式存储管的地址转换】

【段页式虚拟存储管理的地址转换】

页式管理

从页式管理开始，到之后的段式管理，都与之前的分区管理不同，最大的区别就在于一个是分区管理是连续存储，二这两种方式可以非连续。

实现原理

首先是必要概念：

物理块：将物理存储空间划分为大小相等的若干存储块，每块大小为2的整数次幂，总大小在4KB-1GB之间。

页面：将进程的逻辑地址空间划分成的与物理块大小相同的若干片。

页表：存放于主存中，记录进程的逻辑页与主存中的物理块的对应关系，实现从页号到物理块号的地址映射，每一页对应一个表目，页表的长度和页表的主存起始地址存放于PCB中。

在进程分配内存时，以块为单位，将进程的多个页分别装入可以不连续的块中，逻辑地址空间占用m位，每一页大小为2的n次方个地址单元，所以页内位移号占用n个单位，剩下m-n个位表示页号。用页号去页表中寻找对应的项，由此找到物理块号，再加上本身带的页内偏移量，就可以得到物理地址。

动态地址变换

上图为基础地址变换的图示，首先强调的是页式存储管理的逻辑地址是一维的，和段式存储管理的二维不一样，尽管有页号与页内地址两个量，但是这个分离是由硬件做的，一开始是在一起的，而段式存储管理中，地址分离是我们来做的。

因为分离是由硬件做好的，所以比较只用进行第一次，块的大小都是相同的，硬件分离好滞后不用担心页内地址越界，这个过程中共要访问两次主存，一次查表，一次找块，虽然看起来只有两次，但是这种查找行为在系统中多不胜数，所以我们要想办法优化。只是最后一次的找块是不可能取消的，所以我们只能从前一次的查表出发，这就是快表的引入。

快表

为了提高存储速度，在地址变换机构中设置的具有并行查找能力的专用高速缓冲寄存器组（32~1024个寄存器），用来存放页表的一部分，也就是页表的子集。
上图是快表的结构，前两项与页表一致，访问位表示最近此项是否被访问，是就置1，状态位表示寄存器是否被占用，是就置1。
这是加入了快表的变换过程，可以看到，在查表的过程中添加了一个快表的查找部分，要知道的是，快表的查找是并行的，当查快表成功时，就仅仅只用访问一次主存，不用再查页表，而失败时，就继续查找快表，再到主存中，成功找到物理块后，要向快表中写入新项，因为快表是有限的，如果已经占满，就找到状态为为0的写入，如果没有，就找到访问位为0的写入，写入后将后两项置1。

多级页表

当页表过大时，由于页表是连续存储，就会导致页表也需要一个连续的较大物理地址空间存储页表。
而解决方法就是将页表再分页。

如上图为一种示例，就是将整个页表分开，再用页去存储，可以理解为，外页表是子页表的索引。

还可以用哈希表来解决这个问题，以逻辑页号作为哈希值，在此不做赘述。

页式管理的主存分配

存储分块表
第一项记录空闲块总数，第二项是指向第一个空闲块的指针。

分配过程：首先检查是否能满足要求，如果不能，则等待，如果可以满足，第一项减去本次分配块数，第二项找到所需块，并建立页表，修改第二项指针。

回收过程：将占用的主存归还系统，并修改存储分配表中有关各项。

位示图
使用一个位向量磁盘中的每个块占用其中一位，0代表空闲块，1为占用快。
过程与第一种方式类似，不做赘述。

页式管理的保护

越界保护
页号与页表长度进行比较。
访问保护
在页表中为每个物理块设置保护位，表示有效或无效。

页式管理的共享

如图，对于一些可重代码段，并不需要多次申请物理块，而是可以重复使用，图中ed 1、2、3都是刚好占满了三个页，也就是三个物理块，所以可以重用，此时三个程序一共用了7个物理块，但是如果未占满物理块，例如ed3和data的一部分在一个块内，那么这部分不能被重用，所以就变成了2*3+2=8个物理块。

段式管理

实现原理

满足用户（程序员）在编程和使用上的要求，逻辑地址由段名和段内偏移决定，程序和数据的共享以信息的逻辑单位为基础。
按照程序自身的逻辑关系将地址空间划分为若干部分，每个段都有自己的名字，每个段都占用从0开始的连续空间。
段表
记录进程分段与物理空间的对应关系，实现地址映射；每个分段一个表目，指出在主存中的起始地址和段长；段表的主存起始地址和段表长度也存在PCB中。

地址变换

如上图，第一步与页式管理类似，也是先对比段号和段表长度的关系，如果段号大于等于段表长度，产生段号越界；之后的步骤也差不多，不同的地方在于，段式管理要检查地址越界问题，在页式管理中，因为地址的分离由硬件实现，所以不存在地址越界问题，但是段式管理需要。

存储保护

第一级和第二级保护已经在地址变换中写出来了，也就是段号越界保护和段内地址越界保护；第三级保护则是对段设置操作权限所进行保护。

段式管理的共享

段式管理的共享也比页式管理好了一些，因为是按逻辑关系分配的长度，并不是等长，所以同样的可重用逻辑段可以共享，也就是重复利用，方式与页类似。

段式管理的主存分配

与可变式分区类似，区别在于可变式分区管理分配单位为进程，而段式管理的分配单位为段。

段式管理与页式管理的比较

段是信息的逻辑单位，根据用户的需求划分；页是信息的物理单位，它为了方便管理而划分。
段式管理为二维地址空间；页式管理为一维地址空间。
页的大小固定不变；段的大小可变。
页式管理存在内部碎片，消除了外部碎片；段式管理存在外部碎片，消除了内部碎片。
段式管理和页式管理都需要在作业运行前将信息全部装入主存。

引申——段页式管理简单介绍

结合分段管理和分页管理，将程序先分成若干个段，再分成若干个页，段内地址有三部分，段号、页号、页内位移。