OS-存储器管理

第四章存储器管理

存储器管理最主要的对象是内存的管理

存储器的层次结构

由于几乎每条指令都涉及存储器的访问，所以对速度有很高要求

对存储器的三个要求

存储器的访问速度要快，能与处理机速度匹配
存储器容量要大
存储器价格要便宜

但这三个条件目前无法同时满足，于是现代计算机系统无一例外地采用了多层结构的存储器系统

多层结构的存储器系统

存储层次至少三级，从高到低为：CPU寄存器，主存，辅存

细分可以如下六层，层次越高，访问速度越快，价格越高，容量越小

可执行存储器

两者又被称为可执行存储器，进程可以使用一条load或store指令对可执行存储器进行访问，但对辅存的访问则需要通过I/O设备实现

主存储器

简称内存或主存，用于保存进程运行时的程序和数据
主存储器访问速度远低于CPU执行指令的速度

寄存器

主要用于存放处理机运行时的数据，以加速存储器的访问速度
具有和处理机相同的速度，访问速度最快，但价格高昂

缓存

高速缓存

主要用于备份主存中较常用的数据，以减少处理机对主存储器的访问次数（局部性原理）
作用是缓和内存和处理机之间的矛盾，大幅度提高程序执行速度

磁盘缓存

主要用于暂时存放频繁使用的一部分磁盘数据和信息，以减少访问磁盘的次数
本身并非是实际存在的存储器，而是利用主存中部分存储空间暂时存放从磁盘读取的信息，主存也可以看作辅存的高速缓存

程序的装入和链接

程序要在系统中运行，需经过

编译：编译程序对源程序进行编译，形成若干目标模块
链接：链接程序将目标模块以及所需的库函数链接在一起，形成完整的装入模块
装入：装入程序将装入模块装入内存

装入方式

绝对装入方式

装入前就修改成物理地址
装入前完全知道程序将驻留在内存什么位置，装入后程序的逻辑地址（相对地址）与实际地址(物理地址)完全相同。
只适用于单道程序环境

可重定位装入方式

装入时修改地址
装入时，装入程序会把装入模块装入到内存合适的位置，即重定位地址，每个程序起始地址本来为0
指令的逻辑地址+装入内存位置的起始地址=正确的物理地址
地址变换通常在进程装入时一次完成，故又称为静态重定位。

动态运行时的装入方式

用到指令时修改地址(CPU支持，效率高)
装入程序在把装入模块装入内存后，不立即把装入模块中的逻辑地址转换为物理地址，而是推迟到程序执行时才进行
在具有对换功能的系统中，一个进程可能多次换出换入，每次换入后的位置不同，则应采用该方式

链接方式

静态链接方式

在程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的装配模块，以后不再拆开的方式
将多个目标模块装配成一个装入模块需解决
- 对相对地址进行修改
- 变换外部调用符号，即将新的相对地址替换原来的起始地址

装入时动态链接方式

装入一个目标模块时，若发生外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存，同时还有修改目标模块的相对地址
优点：
- 便于修改和更新
- 便于实现对目标模块的共享

运行时动态链接方式

将某些模块的链接推迟到程序执行时才进行
即凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上
加快了程序的装入过程，节省了大量内存空间

连续分配存储管理方式

单一连续分配

在单道程序环境下，内存分为系统区和用户区。用户区仅装有一个用户程序，即整个内存都被该程序独占。

固定分区分配

为了能在内存中装入多道程序，且使程序之间不会相互干扰，则将整个用户空间划分为若干个固定大小的区域，每个分区中只装入一道作业

分区大小固定，导致程序太小时造成内存浪费，太大时又装入失败

动态分区分配

又称可变分区分配，根据进程实际需要，动态地为之分配内存空间

数据结构

常用如下数据结构描述空闲分区和已分配分区情况

动态分区分配算法

基于顺序搜索的动态分区分配算法
1. 首次适应
  - 空闲分区链的地址为增序，在分配地址时从链首开始查找，找到第一个大小可满足的空闲分区为止
  - 再按作业大小从该分区分出一块内存，其余部分仍作为空闲区留在空闲链中；整条链内都无法找到满足的分区即分配失败。
  - 显然该算法倾向于优先利用低位地址的空闲分区，保留了高位地址的大空闲区，为大作业预留了空间，但同时也会造成低址部分留下大量内存碎片
2. 循环首次适应
  - 为了避免低址存在大量的内存碎片而改进的算法
  - 使用额外的起始查询指针保留上一次找到的空闲分区的下一分区的地址，下次查找时从此地址开始查找，并且采用循环查找方式。
3. 最佳适应：找最接近的 (效率最低)（Best Fit，BF）
  - 总是把能满足要求的、最小的空闲分区分配给作业
  - 后果：每次分配后剩余的部分也是最小的，即产生许多难以利用的内存碎片
4. 最坏适应：找最大的（Worst Fit，WF）
  - 与最佳适应相反，每次都选取最大的空闲分区
  - 要使效率最高，使最大的放前面
基于索引搜索的动态分区分配算法
- 快速适应（Quick Fit，QF）
  - 又称分类搜索法，把具有相同容量的所有空闲分区单独设置一个空闲分区链表，再设立一张管理索引表管理所有分区表
  - 在进行分配时，先根据进程长度从索引表找到能容纳它的最小空闲区大小对应的链表，然后直接取出其中的第一块即可
  - 此做法并不分割分区。优点即不产生碎片，查找效率高
  - 缺点是为了有效合并分区，算法复杂，系统开销大
- 伙伴系统
  - 规定分区大小必须为2的幂
  - 当需要为进程分配长度n的存储空间时，先找到i，使得2^(i-1)<n<=2^i,然后就在空间分区大小为2^i的空闲分区链表中查找
    - 若找到，则分配给该进程
    - 若找不到，则往更大一级空闲分区链表中查找，如2^(i+1)
      - 若存在2^(i+1)空闲分区，则将其分为相等的两个分区(进行k次切割)，称为一对伙伴，一个用于分配，一个加入小一级的2^i空闲分区链表中
      - 若不存在，继续往更大一级空闲分区链表中查找，直到大于可利用空间容量则结束
  - 回收时也可能需要多次合并，若存在与待回收分区相同大小的分区则合并这两个分区，并把合并分区归入下一级分区链，若下一级分区同样存在该情况，则依次合并
  - 优于QF算法，但比顺序搜索算法差
- 哈希算法
  - 以空闲分区大小为关键字构建哈希表，从而在分区分配时快速得出分区链表表头指针。

分区分配和回收操作

分配内存

设请求分区大小为u.size，每个空闲分区大小为m.size，size为规定的不再切割的剩余分区大小界限
回收内存

可能出现的情况
1. 回收区与插入点的前一个空闲分区F1相邻接，则二者合并，修改前一分区F1大小
2. 回收区与插入点的后一个空闲分区F2相邻接，则二者合并，F1分区首址改为回收区首址，修改前一分区F1大小
3. 回收区与插入点的前后两分区F1,F2邻接，则三者合并，用F1的表项和首址，取消F2的表项，大小为三者之和
4. 回收区不与谁相邻接，为其单独建立一个新表项，填写其首址和大小，并将首址插入空闲链适当位置

动态可重定位分区分配

紧凑算法

之前提到分区分配剩下来不能被利用的小分区称为碎片，而紧凑算法就是把内存中所有作业移动，使其相邻接，从而把分数的多个空闲小分区拼接成大分区

紧凑虽然提高了内存利用率，但紧凑后的用户程序在内存中位置发生了变化，若不对程序和数据地址进行变换，程序将无法执行

每紧凑一次就变换一次，麻烦且影响效率，从而引入动态重定位

动态重定位

之前介绍的动态运行时装入，就是把作业相对地址(逻辑地址)转换为绝对(物理)地址的工作推迟到程序真正执行时进行，而这个操作需要硬件地址变换机构支持，即是在系统增设重定位寄存器。

地址变换过程是在程序执行期间，随着每条指令或数据的访问自动进行的，故称为动态重定位

重定位寄存器的存在使得紧凑操作仅需修改寄存器保存的程序起始地址即可

动态重定位分区分配算法

在动态分区分配算法基础上增加了紧凑功能

对换

又称为交换技术

指把内存中暂时不能运行的紧凑或者暂时不用的程序和数据换出到外存上，以腾出足够内存空间，把已具备运行条件的进程或进程所需的数据和程序换入内存

有利于提高内存利用率，提高处理机利用率和系统吞吐量

对换类型

整体对换
- 用于多道程序系统中，作为处理机中级调度
页面/分段对换
- 对换以进程的一个页面或分段为单位
- 目的是支持虚拟存储系统

为了实现进程对换，系统需实现三方面功能：对对换空间的管理，进程的换出，进程的换入

对换空间的管理

对换空间管理的主要目标

在具有对换功能的OS中，通常把磁盘空间分为文件区和对换区

对文件区的管理的主要目标
- 文件长时间驻留在外存，访问频率低
- 提高文件存储空间利用率，然后才是提高文件访问速度
- 采取离散分配方式
对对换空间的管理的主要目标
- 进程驻留时间短，对换频率高
- 提高进程换出换入速度，然后才是提高文件存储空间利用率
- 采取连续分配方式

对换区空闲盘块管理中的数据结构，分配和回收

与动态分区分配方式类似，同样使用空闲分区表或空闲分区链，分配回收也是类似

进程的换出与换入

进程换出

选择被换出
- 检查所有驻留在内存中的进程
- 若有处于阻塞状态或睡眠状态的进程，优先选择
- 最后选择优先级最低的进程
进程换出
- 只能换出非共享的程序和数据段，而共享部分只要有进程还需要就不能换出
- 先申请对换空间
- 申请成功则启动磁盘，将该进程数据和程序传送到磁盘的对换区上
- 若传送过程正常，则可回收该进程所占用的内存空间，并对该进程的相关数据结构进行修改

进程换入

查看PCB集合中所有进程状态
找出就绪状态但已换出的进程
选择已换出时间最久的进程，为它申请内存
申请成功则直接将其从外存调入
申请失败则先将内存中某些进程换出，直到内存空间足够再调入
反复以上步骤，直到内存无就绪且换出状态的进程为止；或者已经无足够内存换入为止

分页存储管理方式

基本思想

连续分配方式会形成很多碎片，虽然可通过紧凑算法拼凑成可用的大空间，但开销大，若允许一个进程直接分散地装入许多不相邻接的分区中，便可充分利用内存空间，且无须紧凑。

由此产生了离散分配方式。

分页存储管理方式思想

将用户程序的地址空间分为若干个固定大小的区域，称为页，相应地也将内存空间分为若干物理块，页和块大小相同，这样可将用户程序的任一页放入任一物理块中，实现离散分配

分页存储管理的基本方法

页面和物理块

页面
- 分页存储管理将进程逻辑地址空间分成若干页，并为之编号；也将内存物理地址空间分成若干块，为之编号。
- 在分配内存时，以块为单位，把进程中若干页分别装入不相邻接的物理块中
  
  用不完一块，也要占用一块的空间
  
  由于最后一页经常装不满一块，形成页内碎片
页面大小
- 页面过小则减少内存碎片，有利于提高内存利用率，但导致页表过长，占用内存多
- 页面过大则页内碎片增大
- 页面大小应是2的幂

地址结构

地址结构=页号+位(偏)移量(页内地址)

若给定一个逻辑地址空间中地址为A，页面大小L，则页号P和页内地址d可按下式求，INT是整除函数，MOD是取余函数

例：其系统页面大小L=1KB=1024B，A=2170B，

则2170/1024=2，余122，P=2，d=122

页表

为了能在内存中找到每个页面对应的物理块，系统为每个进程建立了一张页面映像表，简称页表

页表的表项会设置存取控制字段，用于规定为读/写，只读，只执行等存取方式

例题：假设每一块大小为1000(十进制)，那么逻辑地址499，4399对应的物理地址是？

解：499/1000=0，余499；所以对应页号0，块号2，物理地址2499

4399/1000=4，余399，所以对应页号4，块号9，物理地址9499

地址变换机构

地址变换机构的任务即把逻辑地址转换为内存中的物理块号，是借助页表完成的，页表功能是由页表寄存器来实现的。一个页表项用一个寄存器。页表本身是存放在内存中的。

快表

由于页表存放于内存，CPU在每存取一个数据都需要访问内存两次

先访问页表获取物理块号，再把其与页内地址拼接成物理地址
访问物理地址中的数据

为了提高地址变换速度，可以在地址变换机构中增设一个具有并行查询能力的特殊高速缓冲寄存器，即快表（Associative Memory），又称为联想寄存器
快表用于存放那些当前正在访问的页表项。
配备快表后，每当需要访问数据时，首先在快表中寻找是否存在相匹配的页号，有则直接读取；否则继续在内存中寻找页号，并将此页表项存入快表
若快表已满，则选取一个被认为是不再需要的快表项并替换

访问内存的有效时间

从进程发出访问逻辑地址的请求开始，经过地址变换，到在内存中找到对应的实际物理地址单元并取出数据所花费的总时间即内存的有效访问时间（Effective Access Time，EAT）

设访问一次内存的时间为t，则有效访问时间等于两次访问之和

引入快表前：EAT=t+t=2t

引入快表后：EAT=a×λ+(t+λ)(1−a)+t=2t+λ−t×a

λ表示查找快表所需时间，a为命中率，t为访问一次内存所需时间

快表虽然减少了一次内存访问，但存在容量限制，所以在快表中查找所需表项存在命中率的问题

多级页表

现代操作系统大多支持非常大的逻辑地址空间，页表随之变得非常大，要占用较大内存空间。对于页面大小为4KB的32位逻辑地址，页表项数最高可达1M，这就意味着对应进程的页表就会占用1MB的连续内存。

为解决这一问题，对页表所需内存空间采用离散分配方式，只将当前需要的部分页表项嗲如内存，其余仍驻留在磁盘上

以32位逻辑地址空间为例，当页面大小为4KB(12位)

若采用一级页表结构，则具有20位的页号，页表项有1M个

若采用两级页表结构，则每页包含2^10(即1024)个页表项，最多允许1024个页表分页，外层页表中外层页内地址P2为10位，外层页号P1也是10位

反置页表

为了减少页表占用的内存空间，引入了反置页表

一般页表的页表项是按页号排序，页表项内容是物理块号

反置页表为每个物理块设置一个页表项，并将它们按物理块的编号排序，内容是页号和所隶属进程的标识符

可利用Hash算法检索，但可能出现地址冲突，在文件系统会进一步介绍

分段存储管理方式

引入原因

方便编程

访问的逻辑地址由段名和段内偏移量决定，方便编程，程序直观

如: LOAD 1,[A]|<C>将分段A中C单元读入寄存器1
信息共享

段是信息的逻辑单位，避免共享过程占用多个页面，简化实现
信息保护

分段可用更有效地对信息进行统一保护
动态增长
动态链接

动态链接的要求是以目标程序(即段)作为链接的基本单位

基本原理

分段

各段从0开始编址且地址空间连续，段长度由相应的逻辑信息组决定，因此各段的长度很可能各不相同。

段表

与分页管理类似，分段管理系统也会为每个分段分配一个连续分区，并为每个进程建立一张段映射表，即段表。

段表的作用即建立逻辑段到物理内存区的映射，每个段在表中都有一个表项，用于记录段的起始地址以及段的长度。

地址变换机构

为了实现地址变换，同样也要在系统中设置段表寄存器，用于存放段表起始地址以及段长度

同样，增设联想存储器保存最近使用的段表项，来提高存取速度

分页和分段的主要区别

页是信息的物理单位，其对用户是不可见的，是系统管理的需要；段是信息的逻辑单位，为了用户的需要而划分
页的大小固定且由系统决定；段的长度不固定且由用户决定。
分页是系统行为，页地址空间是线性的，即通过一个逻辑地址就可以计算出对应的物理地址；分段是用户行为，其地址空间是二维的，即需要提供段号以及段内地址才可以得到实际地址。

段页式存储管理方式

将分页系统和分段系统二者各取所长，形成新的存储器管理方式

基本原理

先把用户程序分为若干段，并为每个段赋予一个段名，再把每个段分为若干页。
其地址结构由三部分组成：段号、段内页号、页内地址。
为了实现从逻辑地址到物理地址的转换，系统中需同时配置段表和页表。段的内容不再是内存起始地址以及段长，而是页表的起始地址以及页表长度。

地址变换

访问内存中的段表，首先判断段号是否越界，未越界则利用段表起始地址以及段号求出该段对应项在段表中的位置，从中得出该段的页表起始地址
访问内存中的页表，利用逻辑地址中的段内页号获取对应页的页表项所在位置并从中读取物理块号，再利用块号和页内地址计算物理地址
用物理地址从主存获取数据

在一次数据或指令访问中，需要访问三次内存。为了提高执行速度，同样可以设置高速缓冲寄存器。