操作系统第四章--存储器管理（内存）

存储器的层次结构
- 存储器的层次结构（缓存、内存、外存）
  - 主存储器与寄存器
    - 主存储器：用于保存进程运行时的程序和数据。
    - 寄存器：寄存器访问速度最快，与CPU协调工作。
  - 高速缓存与磁盘缓存
    - 高速缓存：CPU对高速缓存的访问，其速度比访问主存快，比访问寄存器慢。
    - 磁盘缓存：内存中一块存储区，对应于某固定磁盘，临时存储磁盘数据（如，数据预取）。
- 存储器管理的目的和功能
  - 主存储器的分配和管理
    - 记住每个存储区域的状态
    - 实施分配
    - 接受系统或用户释放的存储区域
  - 提高主存储器的利用率
  - 扩充主存容量
  - 存储保护
- 存储分配的三种方式
  - 存储分配：解决多道作业之间共享主存的问题
  - 直接指定方式：程序员在编程序时，或编译程序(汇编程序)对源程序进行编译(汇编)时，使用实际存储地址。
    - 这种分配方式的实质是：由编程人员在编写程序时，或由编译程序编译源程序时，对一个作业的所有信息确定在主存存储空间中的位置。因此，这种直接指定方式的存储分配方案，不仅用户感到不便，而且存储空间的利用也不那么有效。
  - 静态分配方式：用户在编程时，或由编译程序产生的目的程序，均可从其地址空间的零地址开始；当装配程序对其进行连接装入时才确定它们在主存中的相应位置，从而生成可执行程序。也就是说，存储分配是在装入时实现的。
    - (1)在一个作业装入时必须分配其要求的全部存储量；
    - (2)如果没有足够的存储空间，就不能装入该作业；
    - (3)一旦一个作业进入内存后，在其退出系统之前，它一直占用着分配给它的全部存储空间；
    - (4) 作业在整个运行过程中不能在内存中“搬家”、也不能再申请存储量。
  - 动态分配方式
    - (1)作业在存储空间中的位置，也是在其装入时确定的；
    - (2)在其执行过程中可根据需要申请附加的存储空间；
    - (3)一个作业已占用的部分存储区域不再需要时，可以要求归还给系统。
      - 即：这种存储分配机制能接受不可预测的分配和释放存储区域的请求，实现个别存储区域的分配和回收；
    - (4)存储区域的大小是可变的；
    - (5)允许作业在内存中“搬家”。
- 基本概念
  - 逻辑地址：用户的程序经过汇编或编译后形成目标代码，目标代码通常采用相对地址的形式，其首地址为0，其余指令中的地址都相对于首地址而编址。
  - 物理地址：内存中存储单元的地址，可直接寻址
  - 名空间：一个用高级语言编制的源程序，我们说它存在于由程序员建立的符号名字空间
  - 地址空间：程序用来访问信息所用地址单元的集合，是逻辑（相对）地址的集合，由编译程序生成。
  - 存储空间：主存中物理单元的集合。
程序的装入和链接
- 程序的装入
  - 绝对装入方式：在编译时，如果知道程序将驻留在内存的具体位置，那么编译程序将产生实际存储地址（绝对地址）的目标代码。
  - 可重定位装入方式
    - 重定位（地址映射/地址变换）
      - 重定位就是把程序的逻辑地址空间变换成内存中的实际物理地址空间的过程，也就是说在装入时对目标程序中指令和数据的修改过程。
    - 静态重定位
      - 地址变换是在装入内存时一次完成的，且以后不能移动。
      - 一般情况下,物理地址=相对地址+内存中的起始地址
    - 动态重定位
      - 装入程序将装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序执行时进行。
- 程序的链接
  - 静态链接：在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装入模块（又称执行模块），以后不再拆开。
  - 装入时动态链接：用户源程序经编译后所得到的目标模块，是在装入内存时，边装入边链接的。即在装入一个目标模块时，若发生一个外部模块调用，将引起装入程序去找出相应的外部目标模块，并将其装入内存。
  - 运行时动态链接：将某些目标模块的链接推迟到执行时才进行，即在执行过程中，若发现一个被调用模块尚未装入内存时，由OS去找到该模块，将它装入内存，并链接到调用模块上。
连续分配存储管理方式
- 连续分配方式
  - 连续分配：指为用户程序分配一个连续的内存空间
  - 存储保护（存储分配的前提）
    - 自动地址修改
    - 0页，1页寻址
    - 界限寄存器
  - 单一连续分配：内存中仅驻留一道用户程序，整个用户区为一个用户独占。内存分为两个区域：系统区，用户区。应用程序装入到用户区，可使用用户区全部空间。
  - 固定分区分配：将内存用户空间划分为若干个固定大小的区域，每个区域称为一个分区（region），在每个分区中只装入一道作业，从而支持多道程序并发设计。
    - 分区的划分方式
      - 分区大小相等
      - 分区大小不等
    - 分区说明表：指出可用于分配的分区数以及每个区的大小、起始地址及状态。
    - 内存分配过程：当有作业要装入内存时，内存分配程序检索分区说明表，从中找出一个尚未使用的满足大小要求的分区分配给该作业，然后修改分区的状态；如果找不到合适的分区就拒绝为该作业分配内存。
    - 内碎片：内存中已分配给用户但未被利用的区域
  - 动态分区分配：根据进程的实际需要，动态地为之分配连续的内存空间。即分区的边界可以移动，分区的大小是可变的。
    - 分区数目大小固定
    - 分区数目大小可变
- 分区分配
  - 数据结构
    - 空闲分区表
    - 空闲分区链
  - 分区分配算法
    - 基于顺序搜索：
    - (1)最佳适应算法(Best Fit)
      - 为一作业选择分区时总是寻找其大小最接近作业所要求的存储区域。即：把作业放入这样的分区后剩下的零头最小。
      - 将存储空间中所有的空白区按其大小递增的顺序链接起来，组成一空白区链(Free List)。
    - (2)最坏适应算法(Worst Fit)
      - 为作业选择存储区域时，总是寻找最大的空白区。在划分后剩下的空白区也是最大的，因而对以后的分配很可能仍然是有用的
      - 空白块应以大小递减的顺序链接起来
    - (3)首次适应算法(First Fit)
      - 每个空白区按其在存储空间中地址递增的顺序链在一起，即每个后继空白区的起始地址总是比前者的大。在为作业分配存储区域时，从这个空白区链的始端开始查找，选择第一个足以满足请求的空白块，而不管它究竟有多大。
      - 外零头：没有分配但无法分配的空间，在低地址部分会积累大量外零头
      - 内零头：分配给用户但用户没有使用的空间，单一连续分配有较大的内零头
    - (4)循环首次（下次）适应算法(Next Fit)
      - 我们把存储空间中空白区构成一个循环链。每次为存储请求查找合适的分区时，总是从上次查找结束的地方开始，只要找到一个足够大的空白区，就将它划分后分配出去。
    - 基于索引搜索：
    - (5)快速适应算法(Quick Fit)
      - 将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表。
      - 同时，在内存中设立一张管理分区类型，并记录了该类型空闲分区链表表头的索引表，该表的每一个表项记录了对应类型空闲分区链表表头的指针。
      - 分配过程：根据进程的长度，寻找到能容纳它的最小空闲分区链表，并取下第一块进行分配即可
    - (6)伙伴系统
  - 分区分配操作
    - 分配内存：向操作系统提出一特定存储量的请求。通常，它并不要求这个分配的存储区域限于特定的位置，但是，这个区域必须是连续的。
    - 回收内存：进程用于归还一个不再需用的存储区域。当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点。
- 伙伴系统
  - 在伙伴系统中，可用内存块的大小为 2^k
  - 对空闲区按照大小分类，相同大小的分区链接为一个双向空闲链表
  - 进程请求大小为n的存储空间
    - 首先计算一个 i 值，使2^i－1< n ≤ 2^i；
    - 在空闲分区大小为2^i的空闲分区链表中查找。
    - if 找到，即把该空闲分区分配给进程。
- 哈希算法
  - 利用哈希快速查找的优点，以及空闲分区在可利用空间表中的分布规律，建立哈希函数，构造一张哈希表，以空闲分区大小为关键字，每一个表项记录了一个对应的空闲分区链表表头指针。
  - 当进行空闲分区分配时，根据所需空闲分区大小，通过哈希函数计算，即得到在哈希表中的位置，从中得到相应的空闲分区链表，实现最佳分配策略。
- 可重定位分区分配
  - 紧凑：将内存中的所有作业进行移动，使它们全都相邻接，这样，可把原来分散的多个小分区合成一个大分区。
  - 动态重定位
    - 在动态运行时装入的方式中，作业装入内存后的所有地址都仍然是相对地址，将相对地址转换为物理地址的工作，被推迟到程序指令要真正执行时进行。
    - 程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。
  - 动态重定位分区分配算法
对换
- 对换概念
  - 指把内存中暂时不能运行的进程或者暂时不用的程序和数据，调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据，调入内存
- 对换空间的管理
  - 在具有对换功能的OS中，通常把磁盘空间分为文件区和对换区
    - 文件区：为提高存储空间利用率，采用离散分配方式；
    - 对换区：为提高进程换入换出的速度，采用连续分配方式
- 进程的换出
  - 进程选择：先选择阻塞状态的，后选择就绪状态的；尽量选择优先级低的；考虑内存驻留时间长短
- 进程的换入
  - 系统定时地查看所有进程的状态，从中找出“就绪”状态但已换出的进程
基本分页存储管理
- 离散分配
  - 连续分配引起：碎片
  - 碎片问题的解决：紧凑方式消耗系统开销
  - 分页：程序地址空间划分为许多固定大小的页或页面，内存空间也按该大小划分为若干物理块或页框；将程序页放入任一页框。
  - 分段：程序地址空间划分为若干个不同大小的段，每个段可以定义一组相对完整的信息。以段为单位分配内存，段间无需相邻。
  - 段页：综合分页和分段
- 分页存储管理
  - 页面和物理块
    - 页面：将一个进程的逻辑地址空间分成若干个大小相等的片
    - 物理块（页框）：把内存空间分成与页面相同大小的若干个存储块
    - 在为进程分配内存时，以块为单位将进程中的若干个页分别装入到多个可以不相邻接的物理块中。
    - 由于进程的最后一页经常装不满一块而形成了不可利用的碎片，称之为“页内碎片”或称为“内零头”。
    - 页表：页号、块号
  - 地址变换
    - 页表寄存器PTR：存放当前运行的进程的页表在内存中的起始地址，此进程的页表长度
    - 变换过程
      - 分页地址变换机构会自动地将有效地址(相对地址)分为页号和页内地址两部分，再以页号为索引去检索页表。
      - 查找操作由硬件执行。在执行检索之前，先将页号与页表长度进行比较，如果页号大于或等于页表长度，则产生一地址越界中断。
      - 若未出现越界错误，则将页表始址与页号和页表项长度的乘积相加，便得到该表项在页表中的位置，于是可从中得到该页的物理块号，将之装入物理地址寄存器中。
      - 与此同时，再将有效地址寄存器中的页内地址送入物理地址寄存器的块内地址字段中。这样便完成了从逻辑地址到物理地址的变换。
    - 快表
      - 分页系统：处理机每次存取指令或数据至少需要访问两次物理内存：第一次访问页表，第二次存取指令或数据
      - 快表：为了提高地址变换速度，为进程页表设置的一个专用的高速缓冲存储器，专门保存当前进程最近访问过的一组页表项
      - 分页系统地址转换
        通过根据逻辑地址中的页号，查找快表中是否存在对应的页表项。
        若快表中存在该表项，称为命中（hit），取出其中的页框号，加上页内偏移量，计算出物理地址。
        若快表中不存在该页表项，称为命中失败，则再查找页表，找到逻辑地址中指定页号对应的页框号。同时，更新快表，将该表项插入快表中。并计算物理地址.
- 内存的有效访问时间
  - 从进程发出指定逻辑地址的访问请求，经过地址变换，到在内存中找到对应的实际物理地址单元并取出数据，所需要花费的总时间，称为内存的有效访问时间（EAT）。
  - 无块表时：EAT = t + t = 2t t为单次内存访问需要的时间。
  - 有快表时：EAT = a λ + ( t + λ )(1-a) + t = 2t + λ – t a λ为查找快表所需的时间，a为命中率
- 两级和多级页表
  - 为了处理大页表的存储与检索，引入了两级页表
  - 两级页表：外层页号+外层页内地址+页内地址
- 反置页表
  - 反置页表为每一个物理块设置一个页表项，并将它们按物理块的编号排序，其中的内容则是页号和其所属进程的标志符。
基本分段存储管理
- 引入分段的原因：方便编程、信息共享、信息保护、动态增长、动态链接
- 分段存储基本原理
  - 程序由若干逻辑段组成，每个段有自己的名字和长度。程序的逻辑地址是由段名（段号）和段内偏移量决定。每个段的逻辑地址从0开始编址.
  - 系统采用动态划分技术，将物理内存动态地划分成许多尺寸不相等的分区。
  - 当一个进程被装入物理内存时，系统将为该进程的每一段独立地分配一个分区。同一进程的多个段不必存放在连续的多个分区中。
- 分段系统的基本数据结构
  - 段表：每个进程建立一个段表，用于描述进程的分段情况，记载进程的各个段到物理内存中分区的映射情况。其中包含段号、段长、段基址以及对本段的存取控制权限等信息。
  - 空闲分区表 : 用于记载物理内存中的空闲分区情况。
  - 段表寄存器：实现快速地址变换，用来存放当前执行进程的段表在物理内存中的起始地址（即基址）。
    - 当创建进程，将进程的程序和数据装入内存时，系统为之建立段表，并将段表的起始地址填入进程的PCB中。
    - 当进程被调度执行时，取出其PCB中的段表首址，填入段表寄存器中。
  - 地址变换和存储保护
    - （1）根据逻辑地址中的段号检索进程段表，获得指定段对应的段表项；
    - （2）判断是否地址越界。比较逻辑地址中的段内偏移量与段表项中的段长，若超过段的长度，则产生存储保护中断（该中断将由操作系统进行处理）；否则，转（3）；
    - （3）把逻辑地址中的段内偏移量与段表表项中的段基址相加，从而得到物理地址。
- 分页和分段的比较（划重点）
  - （1）页是信息的物理单位，分页是为实现离散分配方式，以消减内存的外零头，提高内存的利用率；段则是信息的逻辑单位，它含有一组意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。
  - （2）页的大小固定且由系统决定，因而在系统中只能有一种大小的页面，而段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。
  - （3）分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需利用一个记忆符，即可表示一个地址；而分段的作业地址空间则是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。
- 段页式存储管理
  - 基本原理
    - 采用分段方法组织用户程序，采用分页方法分配和管理内存。
    - 先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。
  - 地址变换
    - ①首先，从段表寄存器从获得进程段表的起始地址，根据该地址，查找进程的段表。
    - ②然后，根据逻辑地址指定的段号检索段表，找到对应段的页表起始地址。
    - ③再根据逻辑地址中指定的页号检索该页表，找到对应页所在的页框号。
    - ④最后，用页框号加上逻辑地址中指定的页内偏移量，形成物理地址。