虚拟分页存储管理

① 基本分页存储管理

假设是按字节编址

考虑支持多道程序的两种连续分配方式

原因：连续分配要求进程占有的必须是一块连续的内存区域
能否讲一个进程分散地装入到许多不相邻的分区，便可充分利用内存

基本分页存储管理的思想：把内存分为一个个相等的小分区，再按照分区大小把进程拆分成一个个小部分

页框/页帧：内存空间分成的一个个大小相等的分区（比如4KB）
页框号：页框的编号，从0开始，从低地址开始

页/页面：用户进程的地址空间分为和页框大小相等的一个个区域
页号梁李弯：页/页面的编号，从0开始

进程的最后一个页面可能没有一个页框那么大，页框不能太大，否则可能产生过大的内部碎片

操作系统以页框为单位为各个进程分配内存空间。进程的每个页面分别放入一个页框中，也就是说，进程的页面与内存的页框有一一对应的关系
每个页面不必连续存放，也不必按照先后顺序，可以放到不相邻的各个页框中

进程在内存中连续存放时，通过动态重定位实现逻辑地址到物理地址的转换。在装入模块之后，内存中指令使用的依然是逻辑地扰早址，直到指令执行的时候才会进行地址转换。系统会设置一个重定位寄存器，用来存放装入模块存放的起始位置，重定位寄存器橡闷中的值加上逻辑地址就是该逻辑地址实际对应的物理地址

如果采用分页技术

页框大小为4KB，地址空间为4GB的系统
页号为前20位，页内偏移量为后12位

页表：为了能知道进程的每个页面在内存中存放的位置，操作系统要为每个进程建立一张页表

一个进程对应一张页表
进程的每一页对应一个页表项
每个页表项由页号和页框号组成
页表记录进程页面和实际存放的页框之间的对应关系

每个页表项的长度是相同的，页号是隐含的
各页表项会按顺序连续存放在内存中，如果该页表在内存中的起始地址是X，4GB/4KB系统的页框有

用于实现逻辑地址到物理地址转换的一组硬件机构

通常会在系统中设置一个页表寄存器(PTR)，存放页表在内存中的起始地址F和页表长度M（M个页表项）
进程未执行时，页表的起始地址和页表长度放在进程控制块(PCB)中，当进程被调度时，操作系统内核会把他们放到页表寄存器中

基本分页存储管理中地址是一维的，即只要给出一个逻辑地址，系统就可以自动计算出页号、偏移量，不需要显式告诉系统偏移量是多少

理论上，页表项长度为3即可表示内存块号的范围，但是为了方便页表查询，会让页面恰好能装得下整数个页表项，令每个页表项占4字节
4KB页面，可以放4096/3 =1365个页表项，有4096%3 =1B的碎片，访问1365及之后的页表项时，还要考虑前面的页框中的碎片，才能得到页表项的物理地址，比较麻烦

进程页表通常存放在连续的页框中，这样就能用统一的计算方式得到想要得到的页表项存储的位置

地址变换过程中有两次访存操作：查询页表、访问目标内存单元

局部性原理

如果这个程序将程序对应的指令存放在10号内存块，将程序中定义的变量存放在23号内存块，当这个程序执行时，会很频繁地反问10、23号内存块

时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能被再次执行；如果某个数据被访问过，不久之后该数据很有可能再次被访问（因为程序存在大量循环）
空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也很有可能被访问（因为很多数据在内存中连续存放）

基本地址变换机构中，每次要访问一个逻辑地址，都要查询页表，由于局部性原理，可能连续多次查询同一个页表项

快表：又称联想寄存器（TLB），是一种访问速度比内存块很多的高速缓存，用来存放当前访问的若干页表项，以加速地址变换的过程。内存中的页表常称为慢表

引入快表后地址的变换过程

一般来说，快表的命中率可以达到90%以上

单级页表存在的问题

对问题1

可将页表进行分组，使每个内存块刚好可以放入一个分组。为离散分配的页表再建立一张页表，称为页目录表，或外层页表
各级页表的大小不能超过一个页面

针对两级页表

对问题2

可以在需要访问页面时，才把页面调入内存（虚拟存储技术），可以在页表项中增加一个标志位，用于表示该页面是否已经调入内存
若想访问的页面不在内存中，会产生缺页中断（内中断），然后将目标页面从外存调入内存
之后的文章会有展开

两级页表访存次数分析：如果没有TLB，第一次访存是访问内存中的页目录表，第二次访存是访问内存中的二级页表，第三次访存是访问目标内存单元

② 采用页式虚拟存储管理方式页大小为8KB，主存块大小为64B，为什么物理地址的页内偏移量不等于主存块大小

物理地址的页偏移量等于对应虚拟地址的页偏移量，虚拟地址的页偏移量与页大小有关，这里页大小8KB，2的13次方，所以页偏移量为13位。

③ 储存管理中,分页式虚拟储存管理的页面淘汰算法有

储存管理中，分页式虚拟储存管理的页面淘汰链森算法有先进先出法，最近最少使用页面陆樱先淘汰，最优淘汰算法。最优淘汰算法(OPT)：系统预测作业今后要访问的页面，淘汰页是将来不被访问的页面或者在最长时间早唤丛后才被访问的页面。它保证有最少的缺页率，但它实现困难，只能通过理论分析用来衡量其它算法的优劣。

④ 分页式虚拟存储系统中，页面大小与可能产生的缺页中断次数____。 A.成正比 B.成反比 C.无关 D.成固定比例

分页式虚拟存储系统中，页面大小与可能产生的缺页中断次数成固定比例；答案选择D；

若执行的程序占用内存很大或很多，则会导致内存消耗殆尽。为解决该问题，Windows中运用了虚拟内存技术，即匀出一部分硬盘空间来充当内存使用。当内存耗尽时，电脑就会自动调用硬盘来充当内存，以缓解内存的紧张。

调度方式

调度方式有分页式、段式、段页式3种。页式调度是将逻辑和物理地址空间都分成固定大小的页。主存按页顺序编号，而每个独立编址的程序空间有自己的页号顺序，通过调度辅存中程序的各页可以离散装入主存中不同的页面位置，并可据表一一对应检索。

页表对程序员来说是透明的，地址变换快，调入操作简单；缺点是各页不是程序的独立模块，不便于实现程序和数据的保护。段式调度是按程序的逻辑结构划分地址空间，段的长度是随意的，并且允许伸长，它的优点是消除了内存零头，易于实现存储保护，便于程序动态装配；缺点是调入操作复杂。

将这两种方法结合起来便构成段页式调度。在段页式调度中把物理空间分成页，程序按模块分段，每个段再分成与物理空间页同样小的页面。段页式调度综合了段式和页式的优点。其缺点是增加了硬件成本，软件也较复杂。大型通用计算机系统多数采用段页式调度

⑤ 页式虚拟存储管理,过小的页会引起什么问题

会引起内存变小。在页式虚拟存储管理系统中，页面的大小是由计算机系统的地址结构所决定的，一般由软硬件共同决定。对于某一种系统一般采用一种大小穗简的页面，也有部分现代操芦皮作系统采用双页面系统的。在确定地址结构时，若选择的页面较小，一方面可使内碎片减小，并减少了内碎猜哗裤片的总空间，有利于提高内存利用率。另一方面，也会使每个进程要求较多的页面，从而导致页表过长，占用大量内存。此外还会降低页面换进换出的效率。

⑥ 内存扩充之虚拟存储技术

传统存储管理

特征

时间局部性：如果执行了程序中的某条指令，那么不久后这条指令很有可能再次执行；如果某个数据被访问过，不久之后该数据很可能再次被访问（因为程序中存在大量循环）
空间局部性：一旦程序访问了某个存储单元，在不久之后，其附近的存储单元很有可能被访问（因为很多数据在内存中是连续存放的，并且程序的指令也是顺序地在内存中存放的

寄存器
高速缓存
内存
外存（如磁盘、磁带等）

越往上容量越小，访问速度越快，成本越高
越往下容量越大，访问速度越慢，成本越低

高速缓存技术的思想：将近期会频繁访问到的数据放到更高速的存储器中，暂时用不到的数据放在更低速存储器中
快表机构就是将近期常访问的页表项副本放到更高速的cache中

基于局部性原理，在程序装入时，可以将程序中很快就会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行
在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序
若内存空间不够，由操作系统将内存中暂时用不到的信息换出到外存

因此，在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存
操作系统虚拟性的一个体现，实际的物理内存大小没有变，只是在逻辑上进行了扩充

虚拟内存的最大容量是由计算机的地址结构（CPU寻址范围）确定的
虚拟内存的实际容量 = min(内存外存容量之和，CPU寻址范围)

虚拟内存有以下三个主要特征

虚拟内存技术，允许一个作业多次调入内存。如果采用连续分配方式，会不方便实现。因此，虚拟内存的实现需要建立在离散分配的内存管理方式基础上

传统的非连续分配存储管理
基本分页存储管理
基本分段存储管理
基本段页式存储管理

虚拟内存的实现
请求分页存储管理
请求分段存储管理
请求段页式存储管理

主要区别：在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存
操作系统要提供请求调页/段功能、页面/段置换功能

请求分页存储管理和基本分页存储管理的主要区别

页表机制
页表项：内存块号、状态位、访问字段、修改位、外存地址，页号时隐含的
内存块号是页面在内存中对应的页框号，如果状态位为0，则内存块号为无
状态位表示是否已被调入内存
访问字段记录最近被访问过几次，或者上次访问时间，由此操作系统能够提供置换算法
修改位记录页面被调入内存后是否被修改过，如果没有，就不需要浪费时间写回外存
外存地址是页面在外存中的存放位置

缺页中断机构
在请求分页系统中，每当要访问的页面不在内存时，便会产生一个缺页中断，然后由操作系统的缺页中断处理程序处理中断（内中断）
此时缺页的进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列
如果内存中有空闲块，则为进程分配一个空闲块，将所缺页面装入该块，并修改页表中相应的页表项
如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面在内存期间被修改过，则要将其写回外存，为修改过的页面不用写回外存
一条指令再执行期间可能产生多次缺页中断（ A to B）

新增的步骤

页面的换入、换出需要磁盘IO，会有较大的开销，因此好的页面置换算法应该追求更少的缺页率

缺页中断≠页面置换
发生缺页中断会发生调页，只有内存块满了才发生页面置换

最佳置换算法OPT：每次淘汰以后永不使用或最长时间内不再被访问的页面
理想化的算法，很难实现

先进先出算法FIFO：每次淘汰最先进入内存的页面
实现：把调入内存的页面根据调入的先后顺序排成队列，页面置换时换出队头页面，新调入的页面排到队尾
优点：实现简单
缺点1：belady异常，为进程分配的物理块数增大时，缺页次数不减反增的异常现象。只有FIFO会产生belady异常。
缺点2：算法与进程实际运行时的规律不适应，因为先调入的页面有可能最经常被访问，因此算法性能差

最近最久未使用置换算法LRU：淘汰最近最久未使用的页面
实现方法：赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t
优点：性能最接近OPT
缺点：实现困难、开销大

时钟置换算法CLOCK/NRU

简单NRU：为每一个页表项设置一个访问位，再将内存中的页面都通过连接指针连成一个循环队列，当某页被访问时，访问位为1，只需检查页的访问位。如果为0，就将该页换出，否则将其改为0，暂不换出，继续向后扫描，若第一轮扫描都是1，将这也页面的访问位改为0后，进行第二轮扫描，第二轮扫描中一定会有访问位为0的页面，将其换出。因此最多经过两轮扫描

改进NRU：如果淘汰的页面没有被修改过，就不需要执行IO操作，只有淘汰的页面被修改过时，才需要写回外存。因此，同时考虑最近有无访问和有无修改，在其他条件相同时，优先淘汰没有修改过的页面，避免IO操作
第一轮：找到第一个访问位和修改位都为0的页面进行替换，如果没有找到进行下一轮扫描
第二轮：查找第一个访问位为0，修改位为1的页面进行替换，本轮将所有被扫描过的访问位设置为0，如果没有进行下一轮扫描
第三轮：查找0，0替换否则下一轮
第四轮：查找0，1替换
最多会进行四轮扫描

驻留集：请求分页管理中给进程分配的物理块的集合
在采用了虚拟存储技术的系统中，驻留集大小一般小于进程的总大小
驻留集太小，导致缺页频繁，系统要花大量时间处理缺页，实际用于进程推进的时间很少
驻留集太大，会导致多道程序并发度下降，资源利用率降低

固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变
可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况作适当的增加或减少

局部置换：发生缺页时只能选进程自己的物理地址块进行置换
全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程

不存在固定分配全局置换的策略，因为全局置换意味着一个进程拥有的物理块数量必然改变
其他三种组合存在

固定分配局部置换：系统为每个进程分配一定数量的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，并且需要进行页面置换，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面
缺点：很难在刚开始就确定应为每个进程分配多少个物理地址块才算合理（采用这种策略的系统可以根据进程大小、优先级、或是根据程序员给出的参数来确定为一个进程分配的内存块数

可变分配全局置换：刚开始会为进程分配一定数量的物理块。操作系统会保持一个空闲物理块队列，当某进程发生缺页时，从空闲物理块中取出一块分给该进程；若无空闲物理块，则选择一个未锁定的页面换出到外存，再将该物理块分配给缺页的进程。采用这种策略时，只要某进程发生缺页，都将获得新的物理块，仅当空闲物理块用完时，系统才选择一个未锁定的页面调出。被选择调出的页面可能是系统中任何一个进程的页面，因此这个被选中的进程拥有的物理块会减少，缺页率会增加
只要缺页就给该进程分配新的物理块

可变分配局部置换：刚开始会为每个进程分配一定数量的物理块，当某进程发生缺页时，只允许从该进程自己的物理块中选出一个进行页面置换。如果进程在运行过程中频繁缺页，系统会为该进程多分配几个物理块，直至该进程缺页率趋于适当程度；反之，如果缺页率太低，就是当减少分配给该进程的内存块数
要根据发生缺页的频率来动态增加或减少进程的物理块

何时调入页面

从何处调入页面
对换区：读写速度更快，采用连续分配方式
文件区：读写速度更慢，采用离散分配方式

抖动/颠簸现象：刚刚换出的页面马上要换入内存，刚刚换入的页面马上要换出外存，这种频繁的页面调度行为称为抖动/颠簸
主要原因是进程频繁访问的页面数目高于可用的物理块数（分配给进程的物理块不够）

为进程分配物理块太少会使进程发生抖动现象，为进程分配的物理块太多会降低系统的并发度降低某些资源的利用率。因此提出了“工作集”的概念
工作集：在某段时间间隔里，进程实际访问页面的集合
驻留集：请求分页存储管理中给进程分配的内存块的集合
驻留集不能小于工作集，否则进程运行过程中将频繁缺页

⑦ linux为什么主要采用分页机制来实现虚拟存储管理

1 分页机制
在虚拟内存中，页表是个映射表的概念, 即从进程能理解的线性地址(linear address)映射到存储器上的物理地址(phisical address).
很显然，这个页表是需要常驻内存的东西, 以应对频繁的查询映射需要(实际上，现代支持VM的处理器都有一个叫TLB的硬件级页表缓存部件，本文不讨论）。
1.1 为什么使用多级页表来完成映射

但是为什么要使用多级页表来完成映射呢?
用来将虚拟地址映射到物理地址的数据结构称为页表, 实现两个地址空间的关联最容易的方式是使用数组, 对虚拟地址空间中的每一页, 都分配一个数组项. 该数组指向与之关联的页帧, 但这会引发一个问题, 例如, IA-32体系结构使用4KB大小的页, 在虚拟地址空间为4GB的前提下, 则需要包含100万项的页表. 这个问题在64位体系结构下, 情况会更加糟糕. 而每个进程都需要自身的页表, 这回导致系统中大量的所有内存都用来保存页表.
设想一个典型的32位的X86系统，它的虚拟内存用户空间(user space)大小为3G, 并且典型的一个页表项(page table entry, pte)大小为4 bytes，每一个页(page)大小为4k bytes。那么这3G空间一共有(3G/4k=)786432个页面，每个页面需要一个pte来保存映射信息，这样一共需要786432个pte!
如何存储这些信息呢？一个直观的做法是用数组来存储，这样每个页能存储(4k/4=)1K个，这样一共需要(786432/1k=)768个连续的物理页面(phsical page)。而且，这只是一个进程，如果要存放所有N个进程，这个数目还要乘上N! 这是个巨大的数目，哪怕内存能提供这样数量的空间，要找到连续768个连续的物理页面在系统运行一段时间后碎片化的情况下，也是不现实的。
为减少页表的大小并容许忽略不需要的区域, 计算机体系结构的涉及会将虚拟地址分成多个部分. 同时虚拟地址空间的大部分们区域都没有使用, 因而页没有关联到页帧, 那么就可以使用功能相同但内存用量少的多的模型: 多级页表

但是新的问题来了, 到底采用几级页表合适呢?
1.2 32位系统中2级页表
从80386开始, intel处理器的分页单元是4KB的页, 32位的地址空间被分为3部分

单元
描述

页目录表Directory 最高10位
页中间表Table 中间10位
页内偏移 最低12位
即页表被划分为页目录表Directory和页中间表Tabl两个部分
此种情况下, 线性地址的转换分为两步完成.
第一步, 基于两级转换表(页目录表和页中间表), 最终查找到地址所在的页帧
第二步, 基于偏移, 在所在的页帧中查找到对应偏移的物理地址
使用这种二级页表可以有效的减少每个进程页表所需的RAM的数量. 如果使用简单的一级页表, 那将需要高达220个页表, 假设每项4B, 则共需要占用220?4B=4MB的RAM来表示每个进程的页表. 当然我们并不需要映射所有的线性地址空间(32位机器上线性地址空间为4GB), 内核通常只为进程实际使用的那些虚拟内存区请求页表来减少内存使用量.
1.3 64位系统中的分页
正常来说, 对于32位的系统两级页表已经足够了, 但是对于64位系统的计算机, 这远远不够.
首先假设一个大小为4KB的标准页. 因为1KB覆盖210个地址的范围, 4KB覆盖212个地址, 所以offset字段需要12位.
这样线性地址空间就剩下64-12=52位分配给页中间表Table和页目录表Directory. 如果我们现在决定仅仅使用64位中的48位来寻址(这个限制其实已经足够了, 2^48=256TB, 即可达到256TB的寻址空间). 剩下的48-12=36位被分配给Table和Directory字段. 即使我们现在决定位两个字段各预留18位, 那么每个进程的页目录和页表都包含218个项, 即超过256000个项.
基于这个原因, 所有64位处理器的硬件分页系统都使用了额外的分页级别. 使用的级别取决于处理器的类型

平台名称
页大小
寻址所使用的位数
分页级别数
线性地址分级

alpha 8KB 43 3 10 + 10 + 10 + 13
ia64 4KB 39 3 9 + 9 + 9 + 12
ppc64 4KB 41 3 10 + 10 + 9 + 12
sh64 4KB 41 3 10 + 10 + 9 + 12
x86_64 4KB 48 4 9 + 9 + 9 + 9 + 12