内容选自王道的视频课程以及汤子瀛编著的《计算机操作系统》第四版

存储器的层次结构与进程运行的基本原理

存储器的层次结构

• 存储层次至少三级：CPU寄存器、主存、辅存，还能根据具体功能细分为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质。
• 在存储层次中，层次越高（越靠近CPU），存储介质的访问速度越快，价格越高，相对所配置的存储容量也越小
• 寄存器和主存储器又被称为可执行存储器，访问可执行存储器时间远小于访问辅存，因为对富村的访问需要通过I/O设备实现。

1. 主存储器：简称内存或者主存，用于存放数据的硬件，程序执行前需要先放到内存中才能被CPU处理。
2. 寄存器：具有与处理机相同的速度，故对寄存器的访问速度最快，但价格十分昂贵，所以容量不可能做得很大。
3. 高速缓存：主要用于备份主存中较常用的数据，以减少处理机对主存储器的访问次数，大幅度提高程序执行速度。
4. 磁盘缓存：暂时存放频繁使用的一部分磁盘数据和信息，以减少访问磁盘的次数（并不实际存在，而是利用主存中的部分存储空间暂时存放从磁盘中读出（或写入）的信息）

程序的装入和链接

1. 编译：由编译程序（Compiler）对用户源程序进行编译，形成若干个目标模块
2. 链接：由链接程序（Linker）将编译后形成的一组目标模块以及他们所需要的库函数链接在一起，形成一个完整的装入模块
3. 装入：由装入程序（Loader）将装入模块装入内存

程序装入的三种方式

绝对装入方式

  编译时，如果知道程序将放到内存中的哪个位置，编译程序将产生绝对地址的目标代码，装入程序按照装入模块中的地址，将程序和数据装入内存。

• 只适用于单道程序环境
• 绝对地址既可以在编译或汇编时给出，也可由程序员直接赋予，通常都是在编译或汇编时转换。

可重定位装入方式

  又称静态重定位，编译、链接后的装入模块的地址都是从0开始，指令中使用的地址、数据存放的地址都是相对于起始地址而言的逻辑地址。可根据内存的当前情况，将装入模块装入到内存的适当位置。装入时对地址进行“重定位”，将裸机地址变换为物理地址。

• 地址变换是在装入时一次完成的
• 一个作业装入内存时，必须分配其要求的全部内存空间，如果没有足够的内存，就不能装入该作业
• 作业一旦进入内存后，运行期间不能再移动，也不能再申请内存空间

动态运行时装入方式

  又称动态重定位，编译、链接后装入模块的地址都是从0开始。装入程序把装入模块装入内存后，并不会立即把逻辑地址转换为物理地址，而是把地址转换推迟到程序真正要执行时才进行。

• 装入内存后所有的地址依然是逻辑地址
• 需要一个重定位寄存器的支持
• 允许程序在内存中发生移动
• 可以将程序分配到不连续的存储中
• 在程序运行前只需要装入他的部分代码即可投入运行，然后再程序运行期间，根据需要动态申请分配内存
• 便于程序段的共享，可以向用户提供一个比存储空间大得多的地址空间

链接的三种方式

静态链接

  在程序运行之前，先将哥目标模块以及他们所需的库函数链接成一个完整的可执行文件（装入模块），之后不再拆开。

• 对相对地址进行修改
• 变换外部调用符号，将每个模块中所用的外部调用符号也都变换为相对地址

装入时动态链接

  将各目标模块装入内存时，边装入边链接的链接方式，即在装入一个目标模块时，发生一个外部模块调用事件，将引起装入程序去找出相应的外部目标模块，并将它装入内存。

• 便于修改和更新
• 便于实现对目标模块的共享，该方式下OS很容易将一个目标模块链接到及格应用模块上，实现多个应用程序对该模块的共享

运行时动态链接

  将对某些模块的链接推迟到程序执行时才进行。

• 便于修改和更新
• 便于实现对目标模块的共享
• 凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅能加快程序的装入过程，而且可以节省大量的内存空间

内存管理

1. 操作系统负责内存空间的分配与回收
2. 操作系统需要提供某种技术从逻辑上对内存空间进行扩充（虚拟技术）
3. 操作系统需要提供地址转换功能，负责程序的逻辑地址与物理地址的转换
   
4. 操作系统需要提供内存保护功能。保证各进程在各自存储空间内运行，互不干扰
   方法一：在CPU设置一对上、下限寄存器，存放进程的上、下限地址。进程的指令要访问某个地址时，CPU检查是否越界。
   方法二：采用重定位寄存器（基址寄存器）和界地址寄存器（限长寄存器）进行越界检查。重定位寄存器中存放的是进程的起始物理地址。界地址寄存器中存放的是进程的最大逻辑地址。

覆盖技术

  用于解决“程序大小超过物理内存总和”的问题

• 将程序分为多段。常用的段常驻内存，不常用的段在需要时调入内存
• 内存中分固定区和若干个覆盖区，需要常驻内存的段放在固定区中，知道运行结束才调出，而不常用的段放在覆盖区，需要用到时调入内存，用不到时调出内存。
• 必须由程序员显性声明覆盖结构，操作系统完成自动覆盖。对用户不透明，增加了用户编程负担
  

对换（交换）技术

  内存空间紧张时，系统将内存中某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存

• 整体对换：即中级调度，也称“进程对换”
• 页面（分段）对换：对换是以进程的一个“页面”或“分段”为单位进行的
• 选择被换出的进程：优先选择阻塞状态、睡眠状态的进程以及选优先级低的
• 进程的换出：只能换出非共享的程序和数据段

交换空间的管理

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

• 文件区：占用磁盘大部分空间，用于存放各类文件，访问频率较低，优先提高存储空间利用率，采取离散分配方式管理
• 对换区：占用磁盘小部分空间，用于存放从内存换出的进程，访问频率较高，优先提高进程换进与换出的速度，采取连续分配方式管理
• 需要记录外存对换区中空闲盘块使用情况，对换区空闲盘块管理中的数据结构与动态分区分配方式所用类似（空闲分区表或空闲分区链）
• 对换空间的分配与回收与下文中分区分配类似

连续分配管理方式

  连续分配指为用户进程分配的必须是一个连续的内存空间

单一连续分配

  内存被分为系统区和用户区，系统区通常位于内存的低地址部分，用于存放操作系统的相关数据；用户区用于存放用户进程相关数据。内存中只能有一道用户程序，用户程序独占整个用户区空间。

• 优点：实现简单，无外部碎片，可以采用覆盖技术扩充内存，不一定需要内存保护
• 缺点：只能用于单用户、单任务的操作系统中；有内部碎片；存储器利用率低。

固定分区分配

  将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业

• 分区大小相等：缺乏灵活性，程序太小浪费内存空间，太大装不下，但很适用于一台计算机控制多个相同对象的场合。
• 分区大小不等：增加灵活性，可以满足不同大小的进程需求，最好能对常在该系统中运行的作业大小进行调查，根据用户的需要划分。
• 操作系统需要建立一个数据结构——分区说明表，来实现各个分区的分配与回收，当用户程序要装入内存时，有内存分配程序依据用户程序的大小检索该表，找到一个能满足大小、未分配的分区，将它分配给该程序，然后修改状态为“已分配”
    优点：实现简单，无外部碎片
    缺点：当用户程序太大时，可能所有的分区都不能满足需求，不得不采用覆盖技术解决，这又会降低性能；会产生内部碎片，内存利用率低
  

动态分区分配

  又称为可变分区分配，不会预先划分内存分区，而是在程序装入内存时，根据进程的大小动态地建立分区。

• 动态分区分配中的数据结构：空闲分区表和空闲链
• 动态分区分配没有内部碎片，但是有外部碎片
    内部碎片，分配给某进程的内存区域中，有部分没用上
    碎片，指内存中的某些空闲分区由于太小而难以利用

分区分配操作

  分配内存：利用某种分配算法，从空闲分区链（表）中找到所需大小的分区
  回收内存：当进程运行完毕释放内存时，系统根据回收区的首地址，从空闲链（表）中找到相应的插入点，对物理地址相邻的可分配内存分区进行合并

动态可重定位分区分配（"紧凑"技术）

  采用上述动态分区分配算法一定时间后，内存空间会被分割成许多小的分区，而缺乏大的空闲空间。此时想要装入大作业，可以使用**"紧凑"技术**，将内存中的所有作业进行移动，使他们全部都相邻接。

• 紧凑后的用户程序在内存中的位置发生了变化，此时需要对程序和数据的地址加以修改，否则程序必将无法执行，因此，每次紧凑后，都需要对移动的程序或数据进行重定位

动态重定位

  作业装入内存后的所有地址仍然都是相对（逻辑）地址，而将相对地址转换为绝对（物理）地址的工作被推迟到程序指令真正要执行的时候。增设一个重定位寄存器，用它来存放程序在内存中的起始地址，从而当若干程序从内存的某处移到另一处时，不需要对程序做任何修改，只要用该程序在内存的新起始地址去置换原来的起始地址即可。

动态分区分配算法

首次适应（first fit，FF）算法

  空闲分区以地址递增的次序排序。每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一空闲分区，并修改对应的空闲分区链（或表）。

• 优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区
• 低址不断被划分，会留下许多难以利用的、很小的空闲分区（外部碎片）
• 每次查找从低址部分开始，之后随着低址不断出现外部碎片，会增加查找可用空闲分区时的开销

循环首次适应（next fit，NF）算法

  又称“邻适应算法”，空闲分区以地址递增的次序排序，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，知道找到一个能满足要求的空闲分区。

• 该算法能使空闲分区分部得更均匀，从而减少了查找空闲分区时的开销
• 导致低地址与高地址的空闲分区都有相同的概率被使用，导致了高地址部分的大分区更可能被使用，划分为小分区，最后无大分区可用

最佳适应（best fit，BF）算法

  空闲分区按容量递增次序链接，每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

• 每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块，会产生很多外部碎片。

最坏适应（worst fit，WF）算法

  空闲分区按容量递减次序链接，每次分配内存时顺序查找空闲分区链（或空闲分区表），找到大小能满足要求的第一个空闲分区。

• 每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是会导致较大的连续空闲区被迅速用完，如果之后有大进程到达，就没有内存分区可用了。

算法比较

动态可重定位分区分配算法

  与动态分区分配算法基本相同，差别仅在于：在这种分配算法中，增加了“紧凑”的功能。但如果所有小的空闲分区的容量总和仍然小于用户的需求，则返回分配失败信息。

非连续分配管理方式（离散分配方式）

分页存储管理方式

• 页面和物理块

• 地址结构
  
  如果有K位表示“页内偏移量”，说明一个页面的大小是2^K个内存单元
  如果有M位表示“页号”，说明在该系统中一个进程最多允许有2^M个页面

• 地址转换

• 页表
  页表是为每一个进程建立一张
  
  假设某系统物理内存大小为4GB，页面大小为4KB
  则总共有2^{32B**的内存，页面大小为**2}12B，则有2^20B个页表项，需要用3个字节才能够表示。

基本地址变换机构

  基本地址变换机构可以借助进程的页表将逻辑地址转换为物理地址

具有块表的地址变换机构

• 局部性原理
• 快表：又称联系寄存器（TLB），是一种访问速度比内存快很多的告诉缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程，与此对应，内存中的页表常称为慢表
  
• 地址变换机构比较
  

两级页表

• 单级页表的问题：
  要在所有的页表项都连续存放的基础上才能根据K号对应的页表项存放位置=页表始地址 + K*4 的方式找到页表项，当页表项数量较大，会导致需要的页框也大，这显然非连续存储方式的初衷
  没有必要让整个页表常驻内存，因为进程一段时间内可能只需要访问几个特定的页面（局部性原理）

• 原理、地址结构：
  

• 实现地址变换
  

• 不需要让整个页表常驻内存

• 多级也表中，各级页表的大小不能超过一个页面，若两级页表不够，则可以分更多级
  
• 多级页表的访存次数相较于单级页表会有所增加，增加访问逻辑地址负担。N级页表访问一个逻辑地址需要N+1次访存（假设没有块表机构）

基本分段存储管理

与分页最大区别就是——离散分配时所分配地址空间的基本单位不同

• 分段
  

• 段表：与页表思路一致，为每个进程建立一张段映射表，保证程序正常运行，能够记录物理内存与各个逻辑段的对应关系
  

• 地址变换
  

• 分段、分页管理对比
  

• 分段比分页更容易实现信息的共享和保护

• 不能被修改的代码称为纯代码或可重入代码（不属于临界资源），这样的代码是可以共享的。课修改的代码是不能共享的。
  
  

段页式管理方式

一个进程对应一个段表，但可以对应多个页表

• 分页、分段优缺点分析
  

• 分段+分页=段页式管理
  

• 逻辑地址结构
  

• 段表、页表

• 地址变换