5.1.1 存储系统
物理存储器的层次结构
1．高速缓存 Cache：少量的、非常快速、昂贵、易变的
2．内存 RAM（内存）：若干兆字节、中等速度、中等价格、易变的
3．磁盘：数百兆或数千兆字节、低速、价廉、不易变的
一、存储管理目的
1．充分利用内存，为多道程序执行提供存储基础；
2．尽可能方便用户使用；
（1）自动装入用户程序
（2）用户程序中不必考虑硬件细节
3．系统能够解决程序空间比实际内存空间大的问题；
4．程序在执行时可以动态伸缩；
5．存储保护与安全；
6．共享与通信；
7．了解有关资源的使用状况；
8．实现的更高的性价比。
二、存储管理的任务
1．内存空间的管理、分配与回收；
2．内存共享；
3．存储保护与安全；
4．内存“扩充”；
5．地址变换。
三、存储管理的功能
任意一个程序只有装入内存后才能运行。因此，存储管理的功能是：
● 将程序从外存中装入内存；
● 按一定的策略实现内存管理的任务。
一、程序局部性原理
在一段时间内一个程序的执行往往呈现出高度的局部性，表现在时间与空间两方面
• 时间局部性：一条指令被执行了，则在不久的将来它可能再被执行
• 空间局部性：若某一存储单元被使用，则在一定时间内，与该存储单元相邻的单元可能被使用
二、局部性原理的作用
1．支撑虚拟存储技术的基础
2．通过调整分配给进程的内存量来提高进程执行效率，从而提升计算机系统的整体效率。
5.1.4 虚拟内存
程序及相关的数据只有装入到内存中才能执行，并且同时装入到内存中的程序越多，它们被并发执行的可能性越高，也就越能提高计算机系统的性能。
当装入到系统中的程序及数据所需的存储空间大于内存时怎么办？这时就需要虚拟内存的支持。
1．概念
虚拟内存是实际内存（也称物理内存）的扩充，它是将系统外存（通常为磁盘）的一部分作为内存来管理和使用。这部分外存空间就是虚拟内存。
虚拟内存的引入扩大了内存空间，使更多的程序及数据能够装入到内存中，提高系统的并发性。虚拟内存对应的物理实体是外存空间的一部分，虽然被作为内存来管理和使用，但是对它的读取速度还是比实际物理内存低。
虚拟内存作为内存的扩充，但是放在虚拟内存中的代码是不能被执行的。只有放到实际内存中的代码才能被执行。
2．使用
虚拟内存在计算机系统中被普遍地使用。例如，在 Windows 98 中，Windows 目录下的 Win386.swp 文件所占的硬盘空间为虚拟内存；Windows 2000 或 Windows XP 中，Windows 目录下的 pagefile.sys 文件所占的硬盘空间为虚拟内存。这些系统中，可以通过设置来设定虚拟内存的最大容量。Windows 7 的虚拟内存建议为实际内存的两到三倍。
在程序执行过程中，当要执行的代码或数据在虚拟内存中时，就需要将它们交换到物理内存中才能执行。由此，将较长时间可能不被执行的代码或数据就可以先交换到虚拟内存中，而将即将要执行的代码或数据及时地交换到物理内存中，这样以提高系统执行的效率，又可以将更多的程序装入内存中提供系统的并发性。
5.2.1 固定分区管理
一、概念
操作系统预先把物理内存用户区划分为若干个连续区域，每个区域称为一个分区。
系统中分区的大小可以相等，也可以不等，但是分区划分后就不再改变。每个进程装入系统时占据一个分区。
采用固定分区的操作系统不使用虚拟内存，因此当要装入进程需求的存储空间大于当前系统中最大可用分区的大小时，该进程不能被装入。
二、固定分区管理
1．数据结构
操作系统为管理固定分区的内存空间，采用如下的数据结构：
该表说明物理内存的用户空间被划分成 4 个分区：编号为 1 的分区大小为 9KB，起始地址为 20KB，且该分区已分配给进程 A；编号为 2~4 的分区未被分配。
请求表列出了系统中等待分配内存空间的进程及需要的内存空间大小。例如：进程 B 需要分配 36KB 的内存空间。
通过分区说明表和请求表，操作系统能够有效地管理内存空间。
2．空间分配
根据请求表，操作系统可以按如下分配算法来分配分区给相应的进程。
3． 回收
当进程结束时，它需要释放所占的分区。对操作系统来说就是回收进程不再使用的分区。操作系统只需将分区说明表对应分区的状态置为可用。
4． 地址变换
如 5.1 节所讲，程序经过编译连接后的可执行代码中使用的地址是逻辑地址（也称虚地址）。当进程被装入内存时，逻辑地址需要转换成物理地址进程才能执行。操作系统通过地址变化将代码中的逻辑地址转换成进程的物理地址（也即内存地址），从而进程才能执行。
5．存储保护
为防止进程使用未分配给它的分区的地址，需要操作系统进行地址保护。通常采用的地址保护措施为：
（1）基址寄存器：存放分区说明表的起始地址；
（2）限长寄存器：存放分区说明表的地址长度。
因此，一个进程能访问的地址范式是从基址寄存器开始到基址寄存器+限长寄存器。
三、固定分区方法的优缺点
1．优点：分配回收方便，适用于用户不多的小型系统；
2．缺点：内存使用不充分，每一分区剩余部分无法利用。
5.2.2 可变分区管理
一、概念
操作系统将内存空间的用户区根据内存的使用情况划分为若干个连续区域，每个区域称为一个分区。
系统中分区的大小可以相等，也可以不等，它们根据内存使用情况而定。每个进程装入系统时占据一个分区。
二、可变分区管理
1．数据结构
可变分区管理中采用的数据结构如下：
一、概念
操作系统将内存空间的用户区根据内存的使用情况划分为若干个连续区域，每个区域称为一个分区。
系统中分区的大小可以相等，也可以不等，它们根据内存使用情况而定。每个进程装入系统时占据一个分区。
二、可变分区管理
1．数据结构
可变分区管理中采用的数据结构如下：
（1）已用分区表
（2）可用分区表
自由链表
（3）请求表
进程号 | 请求长度 |
P1 | 13K |
P2 | 20K |
······ | ······ |
2．内存分配
在可变分区中，可以采用以下算法进行内存分配：
（1）首先适配算法
① 当接到内存申请时，查可用分区表/自由链表，找到第一个不小于请求大小的可用分区，将其分割成两个分区，与请求大小相同的分区分配请求进程，另一个分区保留在可用分区表中。
② 特点：简单、快速分配。
（2）最佳适配算法
① 接到内存申请时，在可用分区表/自由链表中找到一个不小于请求的最小分区进行分割、分配。
② 特点：用最小空间满足要求。
（3）最坏适配算法
① 接到内存申请时，在可用分区表/自由链表中找到一个不小于请求的最大空块进行分割、分配。
② 特点：当分割后保留在可用分区表中的分区仍为较大分区。
3．内存回收
（1）进程结束后，将使用的空间释放并插入到可用分区表/链中。
（2）回收方法
① 直接登记可用分区；
② 相邻可用分区合并；
③ 紧凑技术：通过在内存移动进程，将所有小的空闲区域合并为大的空闲区域（紧缩技术，紧致技术，浮动技术，搬家技术）。
4．碎片问题
内存在使用一段时间之后会出现一些较小的区域（称为碎片），这些区域中的每一个都不适合装入进程。为此，通过将内存中已分配的区域移动到一起，这样就留下一个未使用区域供内存分配时使用。
5．地址变换
图 5.2.2
6．存储保护
（1）基址寄存器：存放分区说明表的起始地址
（2）限长寄存器：存放分区说明表的地址长度
三、可变分区方法的优缺点
1．实现多道程序共享内存，提高 CPU 利用率；
2．管理简单，易于实现；
3．进程大小受分区大小限制；
4．难于实现信息共享——不能定位公用信息的位置。
5.3.1 分页管理的概念与分类
、基本思想（工作原理）
1．把进程的虚拟地址空间划分成大小相等的部分，称为页。从 0 开始编制页号，页内地址是相对于 0 编址。
2．虚地址
3．进程的划分是由系统自动完成的，对用户是透明的。一般，一页的大小为 2 的整数次幂（如 2k,4k,8k 等）。因此，地址的高位部分为页号，低位部分为页内地址。
4．内存空间
按页的大小划分为大小相等的区域，称为页面（内存块，物理页面，页框）。
5．内存分配
以页为单位进行分配，并按作业的页数多少来分配。逻辑上相邻的页，物理上不一定相邻
二、页式管理的分类
1．静态页面管理：一次预先分配给进程所需的所有页面
2．动态页面管理：进程有新的页面请求时才进行分配
一、静态页式管理
1．管理数据结构
（1）页表
① 系统为每个进程建立一个页表，页表给出逻辑页和具体内存页面之间的对应关系
② 页表放在内存，属于进程的现场信息。
（2）请求表
系统通过请求表来管理每个进程/作业的内存请求和内存分配情况。如下表，“状态”指进程申请的页表是否分配。
（3）存储页面表
① 系统通过该表识别内存页面的分配情况。
② 位示图。如下图，0 表示相应页面是空闲页面（未使用页面），1 表示相应页面已使用。
③ 空闲页面链。如下图，将空闲（未使用的）页面用链表连接起来。
2．内存的分配算法
3．内存回收
撤消页表，并把页表中的页面插入到存储页面表中。
4．地址变换
二、动态页式管理
1．预调入页式管理
（1）系统对外存中的页面进行调入顺序计算，估计出这些页中指令和数据的执行和被访问的顺序，并按此顺序将它们调入和调出内存。
（2）实现问题
如何得知将要被执行的指令和将要访问的数据很困难，这种管理方式很少使用。
2．请求页式存储管理
（1）请求页式存储管理只将进程或作业的部分程序和数据驻留在内存中，当要执行的指令或存储的数据所在的页面不在内存中时，系统发出页面调入请求。因此，在执行过程中需要动态地将外存中的页调入内存。
（2）动态页式管理流程
3．两个基本问题是
① 怎样发现这些不在内存中的虚页
解决方法：通过在页表中设置中断位及虚页在外存中的始址
② 怎样处理这种情况（采用何种方法把所缺的页调入内存，以及当内存中没有空闲页面时怎么办）
解决方法：淘汰换页算法。
4．修改后的页表
三、分页存储管理的优缺点
1．优点
（1）虚存量大，适合多道程序运行，用户不必担心内存不够的调度操作。动态页式管理提供了内存与外存统一管理的虚存实现方式。
（2）内存利用率高，不常用的页面尽量不留在内存。
（3）不要求作业连续存放，有效地解决了内存碎片问题。
2．缺点
（1）要进行页面中断，缺页中断等处理，系统开销较大；
（2）有可能产生“抖动”现象；
（3）地址变换机构复杂，一般采用硬件实现，增加了机器成本。
5.4.1 置换策略
置换策略用于确定当进行页面置换时，内存中的那个页面被换出。置换策略通常指页面调度算法。通常的页面调度算法包括：
1．先进先出算法（first input first output，FIFO）
（1）先进入内存的页面先淘汰。（实现是在页表中登记页进入的次序，并将各个已分配的页面按分配时间顺序连接起来，组成 FIFO 队列。优点是实现简单，缺点是遇到常用的页效率低下，并可能产生 Belady 现象。
（2）使用 FIFO 算法时，在未给进程或作业分配足它所要求的全部页面数时，有时会出现分配的页面数增多，缺页数反而增加的奇怪现象。这种现象称为 Belady 现象。
2．循环检测法
让循环多的页面留驻内存，计算机采用记录页面驻留内存期间对该页的访问时间，t 为该页上一次访问时间，T 为该页第二次访问时间，选用相对时间（t-T）最大的淘汰。优点是适合循环多的大程序；缺点是系统开销大。
3．最近最少使用页面先淘汰（least recently useed，LRU）
该算法的基本思想是：当要淘汰某页时，选择离当时时间最近的一段时间内最久没有使用过的页面先淘汰。该算法的出发点是，如果某页被访问了，则可能它马上还要被访问，或者反过来说，如果某页面很长时间未被访问，则它在最近一段时间也不会被访问。LRU 的实现是一件十分困难的事情，我们一般采用它的近似算法。
例：下表是一个 LRL 页面淘汰的示例。可供使用的内存页面有 3 个（页 1、页 2、页 3），状态行中“x”表示缺叶，“Ö”表示不缺页。可知：共缺页中断 10 次。
表 5.4.1
LRU | 4 | 3 | 2 | 1 | 4 | 3 | 5 | 4 | 3 | 2 | 1 | 5 |
页 1 | 4 | 3 | 2 | 1 | 4 | 3 | 5 | 4 | 3 | 2 | 1 | 5 |
页 2 | 4 | 3 | 2 | 1 | 4 | 3 | 5 | 4 | 3 | 2 | 1 | |
页 3 | 4 | 3 | 2 | 1 | 4 | 3 | 5 | 4 | 3 | 2 | ||
状态 | x | x | x | x | x | x | x | Ö | Ö | x | x | x |
4．最不经常使用的页面先淘汰（least frequent used，LFU）
该算法在需要淘汰某一页时，首先淘汰到当前时间为止，被访问次数最少的那一页。这只要在页表中给每一页增设一个访问计数器即可实现。每当该页被访问时，访问计数器加 1，而发生一次缺页中断时，则淘汰计数值最小的那一页，并将所有的计数器清零。
5．最近没有使用的页面先淘汰（not used recently，NUR）
它是上述算法的一种简化，利用在页表中设置一个访问位即可实现，当某页被访问时，访问位置“1”，否则访问位置“0”当需要淘汰一页时，从那些访问位为“0”的页中选一页进行淘汰。系统周期性地对所有访问位清零。
6．随机数淘汰页面算法（random replacement algorithm）
在系统设计人员无法确定那些页的访问概率较低时，随机地选择某个用户的页面进行淘汰也是一种方法。
7．最优淘汰算法（optimal replacement algorithm，OPT）
它是一种理想的淘汰算法，系统预测作业今后要访问的页面，淘汰页是将来不被访问的页面或者最长时间后才能被访问的页面。这种算法是无法实现的，因为它要求必须预先知道每个进程的访问串。
一、评价指标
页面置换策略或者页面调度算法的评价主要指算法造成的缺页情况，包括以下两项指标：
1．缺页数：在某一个页面调度序列中，实际存在的缺页次数。
2．缺页率：指缺页次数与调度页面数之比。
二、应用
下面通过例子来说明不同置换算法的缺页情况。假设页面请求顺序为：2、3、2、1、5、2、4、5、3、2、5、2，系统给进程分配的页框数为 3。
1．先进先出算法（FIFO）
该算法的页面调度情况如下图。
图 5.4.2-1
从图中可知，缺页数为 6，缺页率为 6/12=50%
2．最近最少使用页面先淘汰（LRU）
该算法的页面调度情况如下图。
图 5.4.2-2
从图中可知，缺页数为 4，缺页率为 4/12=33%
3．最优淘汰算法（OPT）
该算法的页面调度情况如下图。
图 5.4.2-3
从图中可知，缺页数为 3，缺页率为 3/12=25%
对其它算法的分析，同学们可以参考这里的方法自己进行。
本章学习了计算机系统存储体系结构、内存管理的技术与方法。学习了局部性原理，了解了虚拟内存的概念。通过学习分区管理方法，介绍了内存管理的思路及过程。学习了逻辑地址、相对地址和物理地址的概念；学习了页式管理的技术与方法及其逻辑地址与物理地址变换方法。介绍了页面置换的过程，学习了主要的页面置换算法。
