存储器的层次结构‘

多层结构的存储器系统

存储器的多层结构。

存储层次至少应具有三级：最高层为 CPU 寄存器，中间为主存，最底层是辅存。还可以根据具体的功能分工细划为寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等 6 层。在存储层次中越往上，存储介质的访问速度越快，价格也越高，相对存储容量也越小。

寄存器、高速缓存、主存储器和磁盘缓存均属于操作系统存储管理的管辖范畴，掉电后它们存储的信息不再存在。固定磁盘和可移动存储介质属于设备管理的管辖范畴，它们存储的信息将被长期保存。

可执行存储器。

寄存器和主存储器又被称为可执行存储器。

主存储器与寄存器

主存储器。

主存储器简称内存或主存。由于主存储器的访问速度远低于 CPU 执行指令的速度，为缓和这一矛盾，在计算机系统中引入了寄存器和高速缓存。

寄存器。

寄存器具有与处理机相同的速度。主要用于存放处理机运行时的数据。如用寄存器存放操作数，或用作地址寄存器加快地址转换速度等。

高速缓存和磁盘缓存

高速缓存。

高速缓存是介于寄存器和存储器之间的存储器，主要用于备份主存中较常用的数据。其容量远大于寄存器，而比内存约小两到三个数量级左右。

根据程序执行的局部性原理(即程序在执行时将呈现出局部性规律，在一较短的时间内，程序的执行仅局限于某个部分)，将主存中一些经常访问的信息存放在高速缓存中。当 CPU 访问一组特定信息时，首先检查它是否在高速缓存中，在则直接取出使用，否则再从主存中读取。

磁盘缓存。

由于目前磁盘的 I/O 速度远低于对主存的访问速度，因此将频繁使用的一部分磁盘数据和信息，暂时存放在磁盘缓存中，可减少访问磁盘的次数。但磁盘缓存与高速缓存不同，它本身并不是一种实际存在的存储介质，而是利用主存中的部分存储空间暂存从磁盘中读出(或写入)的信息。

程序的装入和链接

用户程序要在系统中运行，必须先将它装入内存，然后再将其转变为一个可以执行的程序，通常都要经过以下几个步骤：

1）编译，由编译程序将用户源代码编译成若干个目标模块。

2）链接，由链接程序将编译后形成的一组目标模块，以及它们所需要的库函数链接在一起，形成一个完整的装入模块。

3）装入，由装入程序将装入模块装入内存。

程序的装入

绝对装入方式。

仅能运行单道程序时可以采用该种方式。装入模块被装入内存后，程序中的逻辑地址与实际内存地址完全相同。

可重定位装入方式。

采用可重定位装入方式，根据内存的当前情况，将装入模块装入到内存的适当位置。值得注意的是，在采用可重定位装入程序将装入模块装入内存后，会使装入模块中的所有逻辑地址与实际装入内存的物理地址不同。通常是把在装入时对目标程序中指令和数据地址的修改过程称为重定位。又因为地址变换通常是在装入时一次完成的，以后不再改变，故称为静态重定位。

动态运行时装入方式。

动态运行时的装入程序在把装入模块装入内存后，并不立即把装入模块中的相对地址转换为绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此，装入内存后的所有地址都仍是相对地址。为使地址转换不影响指令的执行速度，这种方式需要一个重定位寄存器的支持。

程序的链接

静态链接方式。

在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装配模块，以后不再拆开。在将这几个目标模块装配成一个装入模块时，须解决以下两个问题：

1）对相对地址进行修改。这是因为在由编译程序所产生的所有目标模块中，使用的都是相对地址，其起始地址都为 0，每个模块中的地址都是相对于起始地址计算的。

2）变换外部调用符号。将每个模块中所用的外部调用符号也都变换为相对地址。

这种先进行链接所形成的一个完整的装入模块，又称为可执行文件。

装入时动态链接。

指用户源程序经编译后所得的目标模块，在装入内存时采用边装入边链接的链接方式。这样便于装入前修改和更新，以及实现对目标模块的共享。

运行时动态链接。

将对某些模块的链接推迟到程序执行时才进行链接，亦即，在执行过程中，当发现一个被调用模块尚未装入内存时，立即由 OS 去找到该模块并将之装入内存，把它链接到调用者模块上。凡在执行过程中未被用到的目标模块，都不会被调入内存和被链接到装入模块上，这样不仅可加快程序的装入过程，而且可节省大量的内存空间。

连续分配存储管理方式

为了能将用户程序装入内存，必须为它分配一定大小的内存空间。

单一连续分配

只能用于单道程序环境下，整个内存的用户空间由一个程序独占。

固定分区分配

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

划分分区的方法。

分区大小相等、分区大小不等。

内存分配。

通常将分区按大小进行排队，并为之建立一张分区使用表，其中各表项包括每个分区的起始地址、大小及状态(是否已分配)。当有一用户程序要装入时，由内存分配程序检索该表，从中找出一个能满足要求的、尚未分配的分区，将之分配给该程序，然后将该表项中的状态置为“已分配”。

动态分区分配

又称可变分区分配。

动态分区分配中的数据结构。

常用的数据结构有以下两种形式：

空闲分区表，表目：分区号、分区大小、分区始址、状态。

空闲分区链，在每个分区的起始部分设置一些用于控制分区分配的信息，以及用于链接各分区所用的前向指针；在分区尾部则设置一后向指针，以及前后都重复设置状态位和分区大小表目。通过前、后向链接指针，可将所有的空闲分区链接成一个双向链。

动态分区分配算法。

顺序式搜索算法、索引式搜索算法。

分区分配操作。

1）分配内存：

系统应利用某种分配算法，从空闲分区链(表)中找到所需大小的分区。设请求的分区大小为 u.size，表中每个空闲分区的大小可表示为 m.size。若 m.size-u.size≤size(size 是事先规定的不再切割的剩余分区的大小)，说明多余部分太小，可不再切割，将整个分区分配给请求者；否则(即多余部分超过 size)，从该分区中按请求的大小划分出一块内存空间分配出去，余下的部分仍留在空闲分区链(表)中。然后，将分配区的首址返回给调用者。

2）回收内存：

当进程运行完毕释放内存时，系统根据回收区的首址，从空闲区链(表)中找到相应的插入点，此时可能出现以下四种情况之一：

①回收区与插入点的前一个空闲分区相邻接，此时应将回收区与插入点的前一分区合并。

②回收分区与插入点的后一空闲分区相邻接，此时也可将两分区合并。

③回收区同时与插入点的前、后两个分区邻接，此时将三个分区合并。

④回收区既不与前一个邻接，又不与后一个邻接，这时应为回收区单独建立一新表项，填写回收区的首址和大小，并根据其首址插入到空闲链中的适当位置。

基于顺序搜索的动态分区分配算法

顺序搜索，是指依次搜索空闲分区链上的空闲分区，去寻找一个其大小能满足要求的分区。

碎片：内存空间不断被划分，会留下许多难以利用的、很小的空闲分区。

首次适应算法。

要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止，缺点是低址部分会不断被划分，形成碎片。

循环首次适应算法。

在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找。实现可通过设置一起始查寻指针，用于指示下一次起始查寻的空闲分区，并采用循环查找方式。缺点缺乏大的空闲分区。

最佳适应算法。

总是把能满足要求、又是最小的空闲分区分配给作业，为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。缺点产生许多碎片。

最坏适应算法。

在扫描整个空闲分区表或链表时，总是挑选一个最大的空闲区，分割一部分空间给作业使用。要求将所有的空闲分区按其容量以从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求即可。缺点缺乏大的空闲分区。

基于索引搜索的动态分区分配算法

快速适应算法。

又称为分类搜索法。是将空闲分区根据其容量大小进行分类，对于每一类具有相同容量的所有空闲分区，单独设立一个空闲分区链表，同时在内存中设立一张管理索引表，该表的每一个表项对应了一种空闲分区类型，并记录了该类型空闲分区链表表头的指针。

该算法仅需要根据进程的长度，寻找到能容纳它的最小空闲区链表，并取下第一块进行分配即可。在分配过程中，不会对任何分区产生分割。

伙伴系统。

规定，无论已分配分区或空闲分区，其大小均为 2 的 k 次幂（k 为整数，l≤k≤m）。通常 2^m是整个可分配内存的大小。

对于每一类具有相同大小的所有空闲分区，单独设立一个空闲分区双向链表。

当需要为进程分配一个长度为 n 的存储空间时，首先计算一个 i 值，使 2^(i-1) < n ≤ 2^i，然后在空闲分区大小为 2^i 的空闲分区链表中查找。若找到则直接分配。否则，则在分区大小为 2^(i+1) 的空闲分区链表中寻找。若存在 2^(i+1) 的一个空闲分区，则把该空闲分区分为相等的两个分区，这两个分区称为一对伙伴，其中的一个分区用于分配，而把另一个加入分区大小为 2^i 的空闲分区链表中。若仍然找不到，依次类推去寻找更高1次幂的分区。

与一次分配可能要进行多次分割一样，一次回收也可能要进行多次合并，如回收大小为 2^i的空闲分区时，若事先已存在回收块所对应的2^i伙伴块的空闲分区时，则应将其与伙伴分区合并为大小为2^(i+1)的空闲分区，若事先已存在新合并空闲块对应的2^(i+1)伙伴块的空闲分区时，依次类推合并。

对于一个大小为2^k，地址为x的内存块，其伙伴块的地址则用buddy k (x)表示，其通式为：

if(x MOD 2^(k+1) == 0) {

buddy k (x) = x + 2^k;

}

else if(x MOD 2^(k+1) == 2^k) {

buddy k (x) = x - 2^k;

}

哈希算法。

构造一张以空闲分区大小为关键字的哈希表，该表的每一个表项记录了一个对应的空闲分区链表表头指针。

动态可重定位分区分配

紧凑。

在连续分配方式中，必须把一个系统或用户程序装入一连续的内存空间。当一台计算机运行了一段时间后，它的内存空间将会被分割成许多小的分区，而缺乏大的空闲分区。

通过移动内存中作业的位置，以把原来多个分散的小分区拼接成一个大分区的方法，称为“拼接”或“紧凑”。由于经过紧凑后的某些用户程序在内存中的位置发生了变化。为此，在每次“紧凑”后，都必须对移动了的程序或数据进行重定位。

动态重定位。

在动态运行时装入的方式中，作业装入内存后的所有地址都仍然是相对(逻辑)地址，将相对地址转换为物理地址的工作，被推迟到程序指令要真正执行时进行。

地址变换过程是在程序执行期间，随着对每条指令或数据的访问借助重定位寄存器自动进行的，故称为动态重定位。当系统对内存进行了“紧凑”而使若干程序从内存的某处移至另一处时，不需对程序做任何修改，只要用该程序在内存的新起始地址，去置换原来的起始地址即可。

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

动态重定位分区分配算法与动态分区分配算法基本上相同，差别仅在于：在这种分配算法中，增加了紧凑的功能。

对换

多道程序环境下的对换技术

对换的引入。

所谓“对换”，是指把内存中暂时不能运行的进程或者暂时不用的程序和数据调出到外存上，以便腾出足够的内存空间，再把已具备运行条件的进程或进程所需要的程序和数据调入内存。

对换的类型。

1）整体对换。

处理机中级调度实际上就是存储器的对换功能。其目的用于解决内存紧张问题。由于中级调度是以进程为单位的，故又称之为“进程对换”或“整体对换”。

2）页面(分段)对换。

以进程的一个“页面”或“分段”为单位进行的，分别称为“页面对换”、“分段对换”，又统称为“部分对换”。

在此，我们只介绍进程对换，而分页或分段对换将放在虚拟存储器中介绍。

对换空间的管理

对对换空间管理的主要目标。

在具有对换功能的 OS 中，通常把外存分为文件区和对换区。

1）对文件区管理的主要目标。

是提高文件存储空间的利用率，为此，对文件区采取离散分配方式。

2）对对换区管理的主要目标。

对换操作较频繁。故是提高进程换入和换出的速度。为此，采取的是连续分配方式，较少考虑外存中的碎片问题。

对换空间空闲盘块管理中的数据结构。

与动态分区分配方式中的数据结构相似，即空闲分区表或空闲分区链。在每个表目中包含两项：对换区的首址及其大小，分表用盘块号和盘块数表示。

对换空间的分配与回收。

与动态分区分配方式中内存分配与回收方法雷同。

进程的换出与换入

进程的换出。

换出过程：

1）选择被换出的进程。首先选择处于阻塞或睡眠状态的进程，如果有多个，则选择优先级最低的进程。在有的系统除了考虑优先级，还需考虑进程在内存的驻留时间。如果系统中已无阻塞进程且内存仍不足时，则选择优先级最低的就绪进程换出。

2）进程换出过程。只能换出非共享的程序和数据段，对于共享的只要还有进程需要，就不能换出。在进行换出时，①需要申请对换空间。②若申请成功，就启动磁盘，将该进程的程序和数据传送到磁盘的对换区上。③若传送成功，便可回收该进程所占的内存空间，并对该进程的PCB和内存分配表等进行相应的修改，若还有可换出进程，则继续换出，直至内存中再无阻塞进程为止。

进程的换入。

定时执行换入操作。找出“就绪”状态但已换出的进程，将其中换出时间最久的进程作为换入进程，为它申请内存。若申请成功则调入，若失败则需先将内存中的某些进程换出，再将进程换入。直到外存中再无“就绪且换出”状态的进程为止，或者已无足够的内存来换入进程时，对换进程停止换入。

基本分页存储管理方式

比较连续分配方式：

作业逻辑地址空间有M大，就需要向内存申请一个M大的连续区域。

分页的目的是更细粒度的处理空间，减少粗放管理的浪费或开销问题。

离散分配内存：

作业规定大小划分成小份；内存也按同样大小划分成小份

作业的任一小份可分散放入内存任意未使用的小份

分页方式下，内存的使用率高，浪费少。但不是绝对没有碎片（进程的最后一页不总是能占满一个物理块）

1）页面的概念

内存划分成多个小单元，每个单元K大小，称（物理）块。作业也按K单位大小划分成片，称为页面。

① 物理划分块的大小 = 逻辑划分的页的大小

②页面大小要适中。

太大，（最后一页）内碎片增大，类似连续分配的问题。  

太小的话，页面碎片总空间虽然小，提高了利用率，但每个进程的页面数量较多，页表过长，反而又增加了空间使用。

2）页表的概念

为了找到被离散分配到内存中的作业，记录每个作业各页映射到哪个物理块，形成的页面映射表，简称页表。

每个作业有自己的页表

页表的作用：

        页号到物理块号的地址映射

要找到作业A

    关键是找到页表（PCB）

    根据页表找物理块

若内存和作业均按1K大小划分块或页，一个4K大的作业可如下图般分配：

①离散分配过程：

找空---空闲空间管理

放入---装入与地址映射 （形成页表）

记录---页表地址记入pcb

②如何运行一个作业?

连续方式下

  PCB记录内存首地址，根据该地址顺序取指令执行即可。

离散方式下

  页表记录作业的各页分别占用了内存的哪些块；  pcb则记录页表在内存的地址——进程构造时伴随着构造页表，该核心信息也要放在内存中供访问；

3）地址的处理

地址映射（地址计算）的过程：

若要执行某作业的一条指令，其相对地址是24B （设10B一页，页表如右表），其物理地址到底是多少呢？

分析其所在的页和偏移得：2号页（页号从0开始） ，偏移4B处是该条指令

查页表找页面对应的块（2号页保存在6号物理块）

找物理块6，向下偏移4B，找到要执行的指令。取出执行即可。

计算上就是求商（页号）及取余（偏移量）的过程

任意一条指令的相对地址如何知道是第几页的第几条指令？

逻辑地址空间分析  

设一分页系统，页面大小为8B（设8条指令）  一个大小为 32B 的作业分配内存

规律

作业相对地址在分页下不同位置的数有一定的意义结构：

            页号+页内地址（即页内偏移）

关键的计算是：根据系统页面大小找到不同意义二进制位的分界线。

从地址中分析出页号后，地址映射只需要把页号改为对应物理块号，偏移不变，即可找到内存中实际位置。

注意：一作业所有指令在用户地址空间是顺序编址

计算口诀             

页面大小决定偏移量（页内地址）的位数 n；

作业大小页面数量

      页表长度 a

      页号的位数 m（或总位数-页内位数）

内存容量决定块数，块数决定编址位数，即页表项位数 b。

4）地址变换机构

围绕页表进行工作，那么页表数据放在哪？

寄存器。一个进程有n个页，页表就需要记录n项数据，需要n个寄存器。不现实。

内存。只设置一个页表寄存器PTR（page table register）记录页表在内存中的首地址和页表长度，运行时快速定位页表。

地址变换过程：

分页系统中，进程创建，放入内存，构建页表，在PCB中记录页表存放在内存的首地址及页表长度。

1.运行某进程A时，将A进程PCB中的页表信息写入PTR中；

2.每执行一条指令时，根据分页计算原理，得到指令页号X和内部偏移量Y；

3.CPU高速访问PTR找到页表在哪里；

      为防止错误检索，增加预先的判断：  计算得到的页号是否大于页表长度（即页表项数）  一个5页的进程，页面编号0-4，若地址计算出的页号不在该范围，一定产生了越界错误。

4.查页表数据，得到X实际对应存放的物理块，完成地址映射计算，最终在内存找到该指令。

5）引入快表——针对访问速度问题

问题：基本分页机制下，一次指令需两次内存访问，处理机速度降低1/2，分页空间效率的提高以如此的速度为代价，得不偿失。

改进：减少第1步访问内存的时间。增设一个具有“并行查询”能力的高速缓冲寄存器，称为“快表”，也称“联想寄存器”（Associative memory），IBM系统称为TLB（Translation Look aside Buffer）。

快表放什么？： 正在执行进程的页表的数据项。

快表的寄存器单元数量是有限的，不能装下一个进程的所有页表项。虽不能完全避免两次访问内存，但如果命中率a高还是能大幅度提高速度。

设一次查找访问快表时间为t' ，则  

EAT= a*t' + (1-a)(t'+t)    +    t

       = 2t +t' -t*a

6）两级、多级页表，反置页表 ——针对大页表占用内存问题

 进程分页离散存放，但页表的数据是连续在存放内存的。而页表可能很大：

        现代操作系统支持非常大的逻辑地址空间的进程。如32位系统，可编址的最大代码数为232，若页面大小为4KB（4*210），则支持的最大进程页表项数可达码232/212=220，有1M个，每个页表项占1B（字节），则页表大小就有1MB。

两级页表

将页表分页，并离散地将页表的各个页面分别存放在不同的物理块中

为离散分配的页表再建立一张页表，称为“外层页表”，其每个表项记录了页表页面所在的物理块号。

分段存储管理方式

请求分段式的虚拟存储器系统是基于分段基础的，自然也具有分段管理系统的好处；同时，同请求分页管理方式一样，也需要扩展页表项的字段，增加状态位、修改位、存取方式、访问字段、外存地址和增补位；最后一个字段是分段系统独有的，用来标记该段是否发生过动态增长；

分段系统的特点就是便于信息的保护和共享；而分段保护中包括越界检查、存取控制检查和环保护机构；环保护机制是一种比较完善的保护机制，在该机制中规定：低编号的环具有较高的优先级。OS内核处于0号环内；某些重要的实用程序和操作系统服务处于中间环；而一般程序则被安排到外环上；在环系统中，程序的访问和调用遵守以下规则：一个程序只可以访问驻留在相同环或者较低特权环（外环）中的数据和服务；

至于地址转换、内存空间的分配和回收等与分段系统基本类似（增加了分段置换功能以实现虚拟存储的需求），详见存储器管理之分段存储管理方式；