操作系统——页式存储管理

分区式存储管理最大的缺点是碎片问题严重，内存利用率低。究其原因，主要在于连续分配的限制，即它要求每个作用在内存中必须占一个连续的分区。
如果允许将一个进程分散地装入到许多不相邻的分区中，便可充分地利用内存，而无需再进行“紧凑”。
基于这一思想，产生了“非连续分配方式”，或者称为“离散分配方式”。

连续分配：为用户进程分配的必须是一个连续的内存空间。
非连续分配：为用户进程分配的可以是一些分散的内存空间。
分页存储管理的思想：把内存分为一个个相等的小分区，再按照分区大小把进程拆分成一个个小部分。
分页存储管理分为：实分页存储管理和虚分页存储管理

一、实分页式存储管理

实分页式存储最大的优点是内存利用率高，与目前流行的虚分页存储管理相比，具有实现简单，程序运行快的优点。目前，飞速发展的硬件制造技术使得物理内存越来越大，因此我们认为，实分页式存储管理将是一种最有发展前途的存储管理方式。

1.1、基本原理

假设一个大型饭店，所有的客房都是标准的双人间，部分客房已经住进客人，现在又有一个旅游团要求入住。接待员统计了一下，对旅游团领队说：“贵团全体成员都能住下，两人一个房间，但是不能住在同一楼层了，因为每层空着的客房不够，更没有几个挨着的。请原谅！”。对于这样的安排，一般人不会感到奇怪。因为旅游团本来就是由一位位个人或夫妻等组成的，而饭店的客房本来也是两人一间的，两人一组正好可住在一个客房里；另外，饭店几乎每天都有入住的和退房的客人，想在同一楼层找几间挨着的客房实在不容易。
①将整个系统的内存空间划分成一系列大小相等的块，每一块称为一个物理块、物理页或实页，页架或页帧（frame），可简称为块（block）。所有的块按物理地址递增顺序连续编号为0、1、2、……。
这里的块相当于饭店的客房，系统对内存分块相当于饭店把大楼所有的客房都设计成标准的双人间。

②每个作业的地址空间也划分成一系列与内存块一样大小的块，每一块称为一个逻辑页或虚页，也有人叫页面，可简称为页（page）。所有的页按照逻辑地址递增顺序连续编号为0、1、2、……。
这里，对作业地址空间分页就相当于把旅游团成员分成两人一组。

③一个作业，只要它的总页数不大于内存中的可用块数，系统就可以对它实施分配。系统装入作业时，以页为单位分配内存，一页分配一个块，作业所有的页所占的块可以不连续。系统同时为这个作业建立一个页号与块号的对照表，称为页表。
这就像饭店有个记录客户入住情况的客户登记表一样。另外，饭店安排客户入住是要查看全部客房的使用情况一览表，相应地系统给作业分配内存时要查看主存分配表或者内存块说明表。‘

④每个块的大小是固定的，一般是个1/2KB～4KB之间的数值（请读者思考：块尺寸为什么太大或太小都不好），而且必须是个2的幂次。
对块尺寸这样规定相当于饭店规定客房是双人间。可以设想一下，如果上例中饭店所有的客房都是十人间的话，效益肯定不如全是双人间的好

实模式下分页存储管理的基本原理：
操作系统以页框为单位为各个进程分配内存空间。系统自动地将作业的地址空间分页，将系统的主存空间分块，页与块等大小，在作业运行时，一次性把作业的全部页面装入内存，各个页所占的内存块可以不连续，也不必按先后顺序，可以放到不相邻的各个页框中。
这实际是个把作业从地址空间映射到存储空间的过程

1.2、页表

页面的划分完全是一种系统硬件的行为，一个逻辑地址放到这种地址结构中，自然就分成了页号和页内单元号两部分。

页面大小为：4KB
在分页系统中，允许将作业（进程）的任一页装入到内存中的任一可用的物理块中，但进程的地址空间本来是连续的，若把他分页后装入到不相邻的物理块中，要保证系统仍能正确运行，就要实现从进程的逻辑地址变换为内存的物理地址。
所以，系统为每个进程建立一张页面映射表，简称页表。

1.3、地址映射

在系统中设置地址变换机构，能将用户进程地址空间中的逻辑地址变为内存空间中的物理地址。
由于页面和物理块的大小相等，页内偏移地址和块内偏移地址是相同的。无须进行从页内地址到块内地址的转换。
地址变换机构的任务，关键是将逻辑地址中的页号转换为内存中的物理块号。物理块号内的偏移地址就是页内偏移地址。
页表的作用就是从页号到物理块号的转换，所以地址变换的任务借助于页表来完成的。

如果题目中是用十进制数表示逻辑地址，则：

例题1：有一系统采用页式存储管理，有一作业大小是8KB，页大小为2KB，依次装入内存的第7、9、10、5块，试将虚地址7145，3412转换成内存地址。

虚地址 3412
P＝3412 ％ 2048＝1
W＝3412 mod 2048＝1364
MA=92048+1364=19796
虚地址3412的内存地址是19796

虚地址 7145
P＝7145 ％ 2048 ＝3
W＝7145 mod 2048 ＝1001
MA=52048+1001=11241
虚地址7145的内存地址是：11241

1.4、快表

因为页表是存放在内存中的，CPU要存取一个数据，需访问主存两次。
第一次：访内存中的页表，找到该页的的物理块号，将此块号与页内地址拼结形成物理地址；
第二次：真正访问该物理地址，存取其中的内容。
这样就把程序的执行速度降低一倍。
为了提高存取速度，在地址变换机构中增设一组寄存器，用来存放访问的那些页表。
快表是一种访存速度比内存快很多的高速缓冲器。
把存放在高速缓冲寄存器中的页表叫快表，这个高速缓冲寄存器又叫联想存贮器（TLB）。与此对应，内存中的页表称为慢表。
当进程访问一页时，系统将页号与快表中的所有项进行并行比较。若访问的页在快表中，即可立即进行地址转换。
当被访问的页不在快表中时，去内存中查询页表，同时将页表找到的内存块号与虚页号填入快表中
例题2：
快表命中率98%，访问时间是10ns， 内存访问时间是100ns， 平均访问时间？
平均访问时间=98%(10+100)+（1-98%）（10+100+100）
若快表命中
联想寄存器检索时间：10ns
访问内存1次取数据时间：100ns
取数据总时间：110ns
若快表中未命中
联想寄存器检索时间：10ns
访问内存1次检索页表时间：100ns
访问内存1次取数据时间：100ns
取数据总时间：210ns

1.5、两级和多级页表

现代的大多数计算机系统，都支持非常大的逻辑地址空间(232~264)。页表就变得非常大，要占用相当大的内存空间。可采用两个方法来解决这一问题：
① 采用离散分配方式来解决难以找到一块连续的大内存空间的问题：
② 只将当前需要的部分页表项调入内存，其余的页表项仍驻留在磁盘上，需要时再调入。

二级页表如何实现地址变换？

1.6、页的分配与回收

用一张“位示图”构成主存分配表。位示图的每一位与一个主存块对应，其值为0，表示对应的主存块空闲，其值为1，表示对应的主存块已分配。
位示图优点是占用内存空间小，可常驻内存，加快分配进程，但缺点是不够直观。

内存分配过程：
计算一个作业所需要的总块数N
查位示图，看看是否还有N个空闲块
如果有足够的空闲块，则页表长度设为N，可填入PCB中；申请页表区，把页表始址填入PCB
依次分配N个空闲块，将块号和页号填入页表
修改位示图

1.7、存在的问题

为每个进程配置一张页表，进程逻辑空间非常大，带来的问题？
可以引入Inverted page tables(反置页表)
反置页表 – 按物理块号排序
IBM RT; HP Spectrum…
反置页表很大，使用Hash表加快检索
所有在内存中的并发进程只有一张页表
除了Hash表，联想寄存器也被用来存放最近使用过的页表项

1.8、分页存储管理方案的评价

优点：
较好地解决了碎片问题
打破了存储分配的连续性要求
提高了主存的利用率

缺点：
页内碎片
动态地址变换、方案实施需耗用额外的系统资源
存储扩充问题没有解决——作业大小受到限制，可用块数小于作业需求时需等待

二、虚拟存储器(Virtual Memory)

2.1、局部性原理(principle of locality)

指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。还可以表现为：
时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内；
空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的数据都集中在一个较小区域内。
局部性原理的具体体现：
程序在执行时，大部分是顺序执行的指令，少部分是转移和过程调用指令。
过程调用的嵌套深度一般不超过5，因此执行的范围不超过这组嵌套的过程。
程序中存在相当多的循环结构，它们由少量指令组成，而被多次执行。
程序中存在相当多对一定数据结构的操作，如数组操作，往往局限在较小范围内。

2.2、引入虚拟存储技术的好处

大程序：可在较小的可用内存中执行较大的用户程序；
大的用户空间：提供给用户可用的虚拟内存空间通常大于物理内存(real memory)
并发：可在内存中容纳更多程序并发执行；
易于开发：与覆盖技术比较，不必影响编程时的程序结构

2.3、虚拟存储技术的特征

不连续性：物理内存分配的不连续，虚拟地址空间使用的不连续（数据段和栈段之间的空闲空间，共享段和动态链接库占用的空间）
部分交换：与交换技术相比较，虚拟存储的调入和调出是对部分虚拟地址空间进行的；
大空间：通过物理内存和快速外存相结合，提供大范围的虚拟地址空间

2.4、虚拟存储技术的种类

虚拟页式
虚拟段式
虚拟段页式

三、虚拟页式(virtual paging)存储管理

3.1、基本原理

系统自动地将作业的地址空间分页，将系统的主存空间分块，页与块等大小，在作业运行前，只把初始需要的一部分页面装入内存块里，运行中需要访问自己地址空间中的但当前不在内存的页面时产生缺页中断，由缺页中断服务程序将所需的页面调入内存，若此时内存中没有空闲物理块安置请求调入的新页面，则系统按预定的置换策略自动选择一个或一些在内存的页面，把它们换出到外存。
虚拟页式存储管理实际是实分页技术与虚拟存储技术相结合的产物，其分页思想与实分页是一样的。
这里的请求调入和置换功能都是比实分页存储管理增加的内容，是实现虚拟存储的主要功能。
为实现虚拟页式存储管理:
需要置换技术、请求装入技术和大硬盘支持，另外：
页表表目需要增加外存块号、状态位、访问位或访问字段、修改位、存取控制字段等。
外存块号指出该页在外存的地址，供调入该页时用；
状态位指示该页是否在内存；
访问位或访问字段则是该页被访问过的标志或被访问过的次数；
修改位表示该页是否被修改过；
存取控制字段则是用来限制页面被安全共享的。

作业1在请求分页系统中的存储映像

当执行 “mov r1，[2120］”时
CPU产生的虚地址为2120
分页机构得 p=2，w=72（每页1K）
查页表。该页中断位i=1，发生缺页中断

如主存中有空白块，直接调入
如主存中无空白块，则需淘汰该作业在主存中的一页

3.2、主存页面分配策略

在虚拟页式存储管理中，内存分配似实分页方式，但还必须考虑解决下面两个问题：
（1）是否对各进程采用平均分配策略？
（2）发生缺页中断时，如何为所缺的页面分配内存？

对问题(2)有一下几种做法：
a、平均分配。
b、按进程长度比例分配。
c、按进程优先级分配。
d、按进程长度和优先级别分配。
对问题(2)主要有一下两种做法：
a、固定分配局部置换。
b、可变分配全局置换。

3.3、页面调入策略

（1）请求调入
当发生页面故障时进行调度，即当进程访问不在内存的页面引发缺页中断时，由系统根据这种访问请求把所缺页面装入内存。
优点：由请求调入策略装入的页一定会被访问，再加之比较容易实现，故在目前的虚拟存储器中，大多采用此策略。
缺点：每次仅调入一页，增加了磁盘I/O的启动频率。
（ 2）预调入
=>也称先行调度，即一页面被访问前就已经预先置入内存，以减少今后的缺页率。
=>主要适于进程的许多页存放在外存的连续区域中的情况。有的系统结合请求调入使用，即每次缺页时装入多个页面。
优点：提高调页的I/O效率。
缺点：基于预测，若调入的页在以后很少被访问，则效率低。常用于程序装入时的调页。

调入页面的来源：
通常对外存交换区的I/O效率比文件区的高。
进程装入时，将其全部页面复制到交换区，以后总是从交换区调入。执行时调入速度快，要求交换区空间较大。
凡是未被修改的页面，都直接从文件区读入，而被置换时不需调出；已被修改的页面，被置换时需调出到交换区，以后从交换区调入。
存储分配的安全性考虑:
把一个页面分配给进程之前，先要清除页面中的数据（如全部填充为0），以免该进程读取前一进程遗留在页面中的数据；

3.4、页面调度算法

由缺页中断服务程序将所需的页面调入内存，若此时内存中没有空闲物理块安置请求调入的新页面，则系统按预定的策略自动选择一个（请求调入策略）或一些（预调入策略）在内存的页面，把它们换出到外存。
a、什么是淘汰策略（置换策略）？
用来选择淘汰哪一页的规则就叫做置换策略，或称淘汰算法。如何决定淘汰哪一页？根据页面在系统中的表现（如：使用的频繁程度、进入系统时间的长短）
b、颠簸
颠簸(thrashing)，又称为“抖动”。
简单地说，导致系统效率急剧下降的主存和辅存之间的频繁页面置换现像称为“抖动”。
现象？淘汰的页面恰好是不久又要访问的页面。

（1）最佳淘汰算法——OPT(Optimal)
这是Belady贝莱迪于1966年提出的一种理论上的算法。该算法每次都淘汰以后永不使用的，或者过最长的时间后才会被访问的页面。
显然，采用这种算法会保证最低的缺页率，但它是无法实现的，因为它必须知道页面“将来”的访问情况。不过，该算法仍有一定意义，可作为衡量其他算法优劣的一个标准。

假定系统为某个进程分配了三个物理块，进程的访问顺序为7，0，1，2，0，3，0，4，2，3，0，3，2，1，2
采用OPT淘汰算法：
（2）先进先出淘汰算法——FIFO
这是最早出现的淘汰算法。
总是淘汰最先进入内存的页面。它实现简单，只需把进程中已调入内存的页面，按先后次序链成一个队列，并设置一个所谓的替换指针，使它总是指向内存中最老的页面。
缺点：效率不高，因为它与进程实际的运行规律不相适应，比如常用的全局变量所在的页面或者循环体所在页面都可能被它选为淘汰对象。出现bleady现象。

页面进入主存的先后次序：
2->4->5->1

当要调入第6页时：
置换第2页
将第2页改为6
替换指针指向第4页4->5->1->6

Belady现象：采用FIFO算法时，如果对一个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多，缺页率反而提高的异常现象。
Belady现象的描述：一个进程P要访问M个页，OS分配N个内存页面给进程P；对一个访问序列S，发生缺页次数为PE（S,N）。当N增大时，PE(S, N)时而增大，时而减小。
Belady现象的原因：FIFO算法的置换特征与进程访问内存的动态特征是非常不一致的，即被置换的页面通常并不是进程不会访问的。

采用FIFO淘汰算法：

（3） 最近最久未使用算法 (LRU, Least Recently Used）
根据页面调入内存后的使用情况，选择内存中最久未使用的页面被置换。这是局部性原理的合理近似，性能接近最佳算法。
OPT算法使用页面将要被访问的时间，LRU算法使用页面最后一次被访问的时间。二者唯一的差别是：OPT是向前看的，而LRU是向后看的。
下面给出LRU的实现算法：
a、计时法：对于每一页面增设一个访问时间计时器，每当一个页面被访问时，当时的绝对时钟内容被拷贝到对应的访问时间计时器中，这样系统记录了内存中所有页面最后一次被访问的时间。淘汰时，选取访问时间计时器的值最小的页面。
b、堆栈法：每当进程访问某页面时，便将该页面的页号从栈中移出，将它压入栈顶。栈顶始终是最新被访问的页面的编号。栈底则是最近最久未被使用的页面的页面号。
c、多位寄存器法
为每页设置一个R位的寄存器
每次访问一页时，将该页所对应的寄存器最左位置1
每隔时间间隔T，所有寄存器右移一位。
选择R值最小的页淘汰。
例如，r寄存器共有四位，页面P0、P1、P2在T1、T2、T3时刻的r寄存器内容如下：
页面 时刻
T1 T2 T3
P0 1000 0100 1010
P1 1000 1100 0110
P2 0000 1000 0100

给某作业分配了三块主存，该作业依次访问的页号为：4，3，0，4，1，1，2，3，2。当访问这些页时，页面淘汰序列变化情况如下

LRU的开销是很大的，必须有硬件的支持，完全由软件实现其速度至少会减少10倍，因此LRU近似算法更实用些
（4）二次机会淘汰算法——SC(Second Chance)淘汰算法
这是一种LRU的近似算法，是通过对FIFO算法进行简单改造，结合页表中的访问位而得来一种淘汰算法。
该算法首先检查位于FIFO链链首的页，如果它的访问位为0，则选择该页淘汰；如果它的访问位为1，则清除其访问位，将它移至FIFO链的链尾，重复此算法的查找过程，直至遇到新链首页是一个访问位为0的较早进入内存的页为止，把它选为被淘汰的页。
为每一个存储块（存储分块表）或页面（页表）设立一个引用位。
当访问某页时，就将该页引用位置1
页面管理软件周期性地（设周期为T）将所有引用位重新置0
在T内，被访问过的页面引用位为1，否则为0
选择引用位为0的页面淘汰。

（5）时钟(Clock)淘汰算法
二次机会淘汰算法缺点：就是需要把访问位为1的处于链首的页移至链尾，这需要一定的开销。
改进的方法：就是把进程所访问的页面链成一个环形链表，再设一个指针指向最老的页面，于是形成了一种简单实用的LRU近似算法——时钟淘汰算法。
该算法首先检测指针所指的页面，如果它的访问位为0，则淘汰该页，新装入的页插入到此位置，然后指针前进一个位置；如果它的访问位为1，则清除为0，并将指针前进一个位置，继续检查访问位。重复此过程，直到找到访问位为0的页面为止。
访问页号727
引发缺页

（6）最近未用淘汰算法——NRU(Not Used Recently)淘汰算法
它把FIFO算法的思想与页面的访问位和修改位结合起来确定一个接近LRU算法的淘汰对象。
该算法每次都尽量选择最近最久未被写过的页面淘汰，这种干净的页面可以不被写回到磁盘。在实现时，为每一个页面设置初始值0的访问位和修改位。当对某页面执行写操作时，其修改位和访问位均由硬件置成1；当对某页面执行读操作时，只有其访问位被硬件置成1。系统每隔固定时间将所有访问位都清0。

按照下列次序选择被淘汰的页面：
①访问位＝０，修改位＝０；直接淘汰；
②访问位＝０，修改位＝１；写回外存后淘汰；
③访问位＝１，修改位＝０；直接淘汰；
④访问位＝１，修改位＝１；写回外存后淘汰；

页面请求序列为：2，3，2，1，5，2，4，5，3，2，5，2
内存分配3块
用OPT、LRU、FIFO、Clock算法写出页面置换过程

时钟clock算法中的箭头是当前指针的位置！

3.5、影响缺页中断率的因素

（1）页面调度算法不合理
抖动又叫颠簸，是指一段时间里，页面在内存与外存之间频繁地调度或换入换出，以至于系统用于调度页面所需要的时间比进程实际运行所占用的时间还要多。
显然，抖动是由于缺页中断率很高而引起的一种坏现象，它将严重影响系统的效率，甚至可能使系统全面崩溃。
（2）分配给作业的内存块数太少
作业的缺页中断率与作业所占内存块数成反比。分配给作业的内存块数太少是导致抖动现象发生的最主要的原因，实验分析表明：对所有的程序来说，要使其有效地工作，它在内存中的页面数不应少于它的总页面数的一半。
（3）页面大小的选择不合理
虽然缺页中断率与页面尺寸成反比，但页面尺寸却不能一味地求大，它一般在0.5KB~4KB之间，是个实验统计值。因为页面大时，页表较小，占空间少，查表速度快，缺页中断次数少，但页面调度时间长，页内碎片较大。页面小时，恰恰相反。
（4）用户程序编制的方法不合适
作业的缺页中断率与程序的局部化（包括时间局部化和空间局部化）程度成反比。用户程序编制的方法不合适可能导致程序运行的时空复杂度高，缺页次数多。