存储器的基础知识
首先，一般的存储器我们就会认为它包含着三部分：
- 寄存器
- 速度最快，但是造价高
- 主存储器
- 速度次之，被通俗称为内存
- 外存
- 速度最慢，用于存储文件数据，因为上边两种一旦断电，数据就会丢失。这个用来做持久化存储的。
因此，我们的存储器往往是使用三层结构的。
程序的装入和链接
在操作系统的角度而言，我们面对存储器就是面对程序的装入和连接
一般地，用户程序向要在系统上运行，就要经历下面几个步骤：
- 编译：对用户源程序进行遍历，形成若干个目标模块
- 链接：将目标模块以及他们所需要的库函数链接在一起，形成完整的模块。
- 装入：将模块装入内存
绝对装入（麻烦）
用户程序中使用的地址称为相对地址或逻辑地址或虚拟地址。 在早期，当程序装入内存时，指令存储在内存中的物理地址与其逻辑地址完全相同. 这种程序的装入方式称为绝对装入方式(Absolute Loading Mode)。
可重定位装入方式（避免地址叠加）
采用可重定位的装入方式(Relocation loading Mode)时，如果能够将不同的的程序装入到地址范围不同的物理内存空间，避免分配给各个程序的内存空间叠加(相交或“撞车”)，就能实现将多个程序安全装入内存，使它们共享内存空间，从而支持多任务系统
如果使用可重定位装入方式，就必须要解决：逻辑地址对物理地址之间的转换
静态装入
静态链接是由链接器在链接时将库的内容加入到可执行程序中的做法。 链接器是一个独立程序，将一个或多个库或目标文件(先前由编译器或汇编器生成)链接到一块生成可执行程序。
在程序运行前一次性装入
动态装入
随着内存技术的发展，为了让更多的程序投入有限的内存并发运行，操作系统只将运行程序所必须的模块装入内存，其他诸如帮助系统等不常用的程序模块不装入内存，进而只装入能够使程序运行起来的那部分模块，更加节省了空间。
在程序运行时，分批装入到内存中
静态链接
静态链接是由链接器在链接时将库的内容加入到可执行程序中的做法。 链接器是一个独立程序，将一个或多个库或目标文件(先前由编译器或汇编器生成)链接到一块生成可执行程序。
和静态装入是一样的。
动态链接
载入时动态链接是在将功能模块读入内存时把动态库中调用到的相关模块的内容载入内存。 载入时动态链接是分别载入，当把一个模块载入内存时检查有调用关系的模块并将其载入内存，比静态链接节省了许多开销。 运行时动态链接则是把当前模块调用的模块推迟到调用的时候再载入。
在运行时和运行前进行链接。
连续分配存储管理方式
操作系统将内存分为系统区和用户区两部分
- 系统区仅提供给OS使用，通常是放在内存的低址部分，用户区指系统区以外的全部内存空间，提供给用户使用，通常在高地址部分。
- 内存会被分成为系统区和用户区，比例为1:3。
- 内存分配方式指的是对用户区的分配方式。原因是用户提交的任务只能在用户区运行。
固定分区方式
为了支持多道程序系统和分时系统，支持多个程序并发执行，引入了分区式存储管理。
分区式存储管理是把内存分为一些大小相等或不等的分区，操作系统占用其中一个分区，其余的分区由应用程序使用，每个应用程序占用一个或几个分区。
1 划分内存分区的方法
- 1)分区大小相等
- 内存分区大小一致，可能浪费空间；也可能空间不够。
- 2)分区大小不等
- 含较多的较小分区、适量的中等分区和少量的大分区。
系统对内存的管理和控制通过数据结构—分区说明表进行。 分区说明表说明各分区号、分区大小、起始地址和是否是空闲区(分区状态)。 内存的分配释放、存储保护以及地址变换等都通过分区说明表进行。
内存分区的分配：
- 1)为了便于内存分配，通常将分区按大小进行排队，并为之建立一张分区表。
- 2)分配
- 3)回收
动态分区
- 固定分区的重大意义在于操作系统开始支持多任务。
- 但是仍然存在内存浪费的问题。
- 原因是内存分区在先，而运行程序在后，对于每个待运行的程序而言内存分区的大小并非量身定做。
- 于是就出现了当运行某个任务时只能将该任务装载到内存空间中更大的分区。
- 尽管浪费没有单一连续分区严重，但是内存的使用率仍然很低。
如果内存分区的划分不是预先划定，而是根据所要运行的程序的大小分配内存，在内存分配阶段就不会出现内存碎片。 于是，动态分区技术应运而生。
1 基本问题：
1)动态分区的基本思想：在作业执行前不直接建立分区，分区的建立是在作业的处理过程中进行的。且其大小可随作业或进程对内存的要求而改变。 2)动态创建分区：在装入程序时按其初始要求分配，或在其执行过程中通过系统调用进行分配或改变分区大小，按需分配。 3)采用的数据结构：内存分配表，由两个表格组成。一个是已分配区表，另一张是空闲区表.
动态分区就有两张表来进行说明了。
动态分区分配内存时从可用表或自由链中寻找空闲区的常用方法
- 1)首次适应算法(First Ft Algorithm, FFA)
- 首次适应法要求可用表或自由链按起始地址递增的次序排列。
- 2)最佳适应算法(Best Fit Algorithm, BFA)
- 要求按空闲区大小从小到大的次序组成空闲区可用表或自由链。
- 3)最坏适应算法(Worst Fit Algorithm, WFA)：
- 要求空闲区按其大小递减的顺序组成空闲区可用表或自由链。
碎片问题
4)碎片问题
- 经过一段时间的分配回收后，内存中存在很多很小的空闲块。它们每一个都很小，不足以满足分配要求； 但其总和满足分配要求。这些空闲块被称为碎片。
5)碎片问题的解决
- 通过在内存移动程序的技术将所有小的空闲区域合并为大的空闲区域，这种技术称为紧凑技术，也称为紧缩技术、紧致技术、浮动技术、搬家技术。
可重定位分区分配
动态分区很完美地在内存初次分配阶段解决了内存空间浪费的问题。但是，内存是需要重复利用的。 随着任务的不断运行完毕，内存空间会被回收；同时，操作系统又会不断接收新的任务，内存空间会被分配。
于是，当运行一个新任务时，只能从回收回来的分区上分配内存，一方面动态分区技术在一定程度上退化为固定分区，另一方面分配后余下的碎片(小块的内存空间)就被保留了下来，较小的内存空间被分配出去的可能性很小，造成了浪费(碎片）。
最终，内存空间会存在很多小块的空闲空间，而不再有大块的空闲空间，于是当较大型的任务到达时，没有足够的空间供分配（尽管这些小块的空闲内存空间之和比任务所需的空间大）
- 针对动态分区中碎片之和大于任务所需空间的情况，考虑对内存空间采用紧凑技术进行整理，将已进入内存的任务所占有的内存空间尽量搬到较低的地址，相对的，空闲碎片的会被换到了高地址空间。
- 当所有进入内存的任务都被搬到较低的地址后，空闲碎片都被移动到了内存空间的高地址空间。
- 于是，所有的碎片被整合成了一个大块，从而可以装载任务。这就是可重定位的动态分区。
将碎片合成一大块---可重定位的动态分区
实现
- 1）动态重定位依靠硬件地址变换机构完成。
- 2）地址重定位机构需要基地址寄存器(BR)和程序虚地址寄存器(VR)。 指令或数据的虚地址(VA)，也称为逻辑地址(LA)。内存地址MA(MA)，也称物理地址(PA) 实现逻辑地址到物理地址的转换，可以通过公式MA＝(BR)十(VR)完成。
图5-10所示为指令或数据的逻辑地址到物理地址的转换过程
优点
- 1)可以对内存进行非连续分配。
- 2)动态重定位提供了实现虚拟存储器的基础。
- 3)有利于程序段的共享。
4 动态重定位分区的分配算法
- 1)主干是动态分区的分配算法。
- 2)在动态分区的基础上增加了紧凑技术。
- 3)内存分配算法，如图5-11所示。
基本分页存储管理
上面的存储都是连续的内存分配技术，我们的分页存储是离散的
与其花费巨大的代价搬家，不如离散地存储在这些碎片中
- 一种离散存储的方法是面向系统的，将内存用户空间划分为大小相等(2nB，如4KB)的物理块；
- 另一种方法是面向用户的，将内存空间划分为物理段，32位系统中，以高16位表示段号，低16位表示段内地址。
这就是汇编语言中定义一个段时大小不可以超过64KB的根本原因。
离散存储思想产生的原因：
- (1)紧凑技术的弊端
- 尽管可重定位分区方式下的紧凑技术使得碎片得以利用，提高了内存空间的利用率。但这是以牺牲时间进行搬家而获得的，代价是很高的。
- (2)求变创新
- 从内存连续分配的思想上突破、创新，提出离散的内存分配方式，从而使存在大量碎片和无足够大的连续空间供分配这一矛盾得以缓解。
离散存储的基本概念
- 将一个进程直接分散地装入到许多不相邻的分区中，而无须“紧凑”的分配方式，称为离散分配。
- 离散分配的种类包括分页存储管理、分段存储管理和段页式存储管理。
- 不具备页面对换功能的分页存储管理方式称为基本分页存储管理方式。
分页存储管理
分页存储管理的基本方法
- 页面和物理块
- 页面。
- 页面大小。
将用户作业的地址空间分成若干个大小相同的区域，称为页面或页，并为每个页从“0”开始编号； 相应地，主存空间也分成与页大小相同的若干个存储块，或称为物理块或页框(frame)，并且采用同样的方式为它们进行编号，从0开始：0块，1块，…，n-1块
分页地址中的地址结构如下：
对某特定机器，其地址结构是一定的。若给定一个逻辑地址空间中的地址为A，页面的大小为L，则页号P和页内地址d可按下式求得：
页表
在分页系统中，允许将进程的各个页离散地存储在内存的任一物理块中，为保证进程仍然能够正确地运行，即能在内存中找到每个页面所对应的物理块，系统又为每个进程建立了一张页面映像表，简称页表
进程在运行期间，需要对程序和数据的地址进行变换，即将用户地址空间中的逻辑地址变换为内存空间中的物理地址，由于它执行的频率非常高，每条指令的地址都需要进行变换，因此需要采用硬件来实现。页表功能是由一组专门的寄存器来实现的。一个页表项用一个寄存器。
由于页表是存放在内存中的，这使CPU在每存取一个数据时，都要两次访问内存。第一次是访问内存中的页表，从中找到指定页的物理块号，再将块号与页内偏移量W拼接，以形成物理地址。第二次访问内存时，才是从第一次所得地址中获得所需数据(或向此地址中写入数据)。因此，采用这种方式将使计算机的处理速度降低近1/2。可见，以此高昂代价来换取存储器空间利用率的提高，是得不偿失的。
因此，我们采用：具有快表的地址变换机
分段存储管理
用户把自己的作业按照逻辑关系划分为若干个段，每个段都从0开始编址，并有自己的名字和长度。因此，程序员们都迫切地需要访问的逻辑地址是由段名(段号)和段内偏移量(段内地址)决定的，这不仅可以方便程序员编程，也可使程序非常直观，更具可读性。
在实现对程序和数据的共享时，是以信息的逻辑单位为基础的。
- 分页系统中的“页”只是存放信息的物理单位(块)，并无完整的逻辑意义，这样，一个可被共享的过程往往可能需要占用数十个页面，这为实现共享增加了困难。
信息保护同样是以信息的逻辑单位为基础的，而且经常是以一个过程、函数或文件为基本单位进行保护的。
在实际应用中，往往存在着一些段，尤其是数据段，在它们的使用过程中，由于数据量的不断增加，而使数据段动态增长，相应地它所需要的存储空间也会动态增加。然而，对于数据段究竟会增长到多大，事先又很难确切地知道。对此，很难采取预先多分配的方法进行解决。
分段系统的基本原理
在分段存储管理方式中，作业的地址空间被划分为若干个段，每个段定义了一组逻辑信息。例如，有主程序段MAIN、子程序段X、数据段D及堆栈段S等。
段表
在前面所介绍的动态分区分配方式中，系统为整个进程分配一个连续的内存空间。而在分段式存储管理系统中，则是为每个分段分配一个连续的分区。进程中的各个段，可以离散地装入内存中不同的分区中。为保证程序能正常运行，就必须能从物理内存中找出每个逻辑段所对应的位置。这就需要段表了
为了实现进程从逻辑地址到物理地址的变换功能，在系统中设置了段表寄存器，用于存放段表始址和段表长度TL。在进行地址变换时，系统将逻辑地址中的段号与段表长度TL进行比较。若S>TL，表示段号太大，是访问越界，于是产生越界中断信号。若未越界，则根据段表的始址和该段的段号，计算出该段对应段表项的位置，从中读出该段在内存的起始地址。然后，再检查段内地址d是否超过该段的段长SL。若超过，即d>SL，同样发出越界中断信号。若未越界，则将该段的基址d与段内地址相加，即可得到要访问的内存物理地址。图示出了分段系统的地址变换过程。
分页和分段的总结
（1）页是信息的物理单位，分页是为了实现离散的分配方式，以消减主存“碎片”，提高主存的利用率。或者说，分页仅仅是由于系统管理的需要，而不是用户的需要。段是信息的逻辑单位，它包含一组意义相对完整的信息。分段的目的是为了能更好地满足用户的需要。 （2）页的大小固定且由系统确定，把逻辑地址划分为页号和页内地址两部分，是由机器硬件实现的，因而一个系统只能有一种大小的页面。段的长度却不固定，决定于用户所编写的程序，通常由编译程序在对源程序进行编译时，根据信息的性质来划分。 （3）分页的作业地址空间是一维的，即单一的线性地址空间，程序员只需要利用一个记忆符，即可表示一个地址。分段的作业地址空间是二维的，程序员在标识一个地址时，既需给出段名，又需给出段内地址。
段页式存储管理
段页式系统的基本原理是分段和分页原理的结合，即先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。图(a)示出了一个作业地址空间的结构。该作业有三个段：主程序段、子程序段和数据段；页面大小为 4 KB。在段页式系统中，其地址结构由段号、段内页号及页内地址三部分所组成，如图(b)所示。
在段页式系统中，为了实现从逻辑地址到物理地址的变换，系统中需要同时配置段表和页表。段表的内容与分段系统略有不同，它不再是内存始址和段长，而是页表始址和页表长度。图示出了利用段表和页表进行从用户地址空间到物理(内存)空间的映射。
地址变换过程：
在段页式系统中，为了便于实现地址变换，须配置一个段表寄存器，其中存放段表始址和段长TL。进行地址变换时，首先利用段号S，将它与段长TL进行比较。若S < TL，表示未越界，于是利用段表始址和段号来求出该段所对应的段表项在段表中的位置，从中得到该段的页表始址，并利用逻辑地址中的段内页号P来获得对应页的页表项位置，从中读出该页所在的物理块号b，再利用块号b和页内地址来构成物理地址。图示出了段页式系统中的地址变换机构。
虚拟存储器
要求将一个作业全部装入内存后方能运行，于是，出现了下面这样两种情况：
- (1) 有的作业很大，其所要求的内存空间超过了内存总容量，作业不能全部被装入内存，致使该作业无法运行；
- (2) 有大量作业要求运行，但由于内存容量不足以容纳所有这些作业，只能将少数作业装入内存让它们先运行，而将其它大量的作业留在外存上等待
局部性原理：
- 程序在执行时将呈现出局部性规律，即在一较短的时间内，程序的执行仅局限于某个部分，相应地，它所访问的存储空间也局限于某个区域。时间局部性和空间局部性
基于局部性原理可知，应用程序在运行之前没有必要将之全部装入内存，而仅须将那些当前要运行的少数页面或段先装入内存便可运行，其余部分暂留在盘上。
虚拟存储器的定义
当用户看到自己的程序能在系统中正常运行时，他会认为，该系统所具有的内存容量一定比自己的程序大，或者说，用户所感觉到的内存容量会比实际内存容量大得多。但用户所看到的大容量只是一种错觉，是虚的，故人们把这样的存储器称为虚拟存储器。
实现方法
主要的硬件支持有：
- (1) 请求分页的页表机制。
- (2) 缺页中断机构。
- (3) 地址变换机构。
为了实现请求分页，系统必须提供一定的硬件支持。计算机系统除了要求一定容量的内存和外存外，还需要有请求页表机制、缺页中断机构以及地址变换机构。
在请求分页系统中需要的主要数据结构是请求页表，其基本作用仍然是将用户地址空间中的逻辑地址映射为内存空间中的物理地址。为了满足页面换进换出的需要，在请求页表中又增加了四个字段。这样，在请求分页系统中的每个页表应含以下诸项
一个显而易见的事实是，随着为每个进程所分配的物理块的减少，将使进程在执行中的缺页率上升，从而会降低进程的执行速度。最小物理块数是指能保证进程正常运行所需的最小物理块数，当系统为进程分配的物理块数少于此值时，进程将无法运行。
考虑优先权的分配算法。在实际应用中，为了照顾到重要的、紧迫的作业能尽快地完成，应为它分配较多的内存空间。通常采取的方法是把内存中可供分配的所有物理块分成两部分：一部分按比例地分配给各进程；另一部分则根据各进程的优先权进行分配，为高优先进程适当地增加其相应份额。在有的系统中，如重要的实时控制系统，则可能是完全按优先权为各进程分配其物理块的。
页面调入策略
为使进程能够正常运行，必须事先将要执行的那部分程序和数据所在的页面调入内存。现在的问题是：
- (1) 系统应在何时调入所需页面；
- (1) 预调页策略。
- (2) 请求调页策略
- (2) 系统应从何处调入这些页面；
- 系统拥有足够的对换区空间，这时可以全部从对换区调入所需页面，以提高调页速度
- 系统缺少足够的对换区空间，这时凡是不会被修改的文件，都直接从文件区调入；而当换出这些页面时，由于它们未被修改，则不必再将它们重写到磁盘(换出)，以后再调入时，仍从文件区直接调入。但对于那些可能被修改的部分，在将它们换出时便须调到对换区，以后需要时再从对换区调入。
- (3) 是如何进行调入的。
- 每当程序所要访问的页面未在内存时(存在位为“0”)，便向CPU发出一缺页中断，中断处理程序首先保留CPU环境，分析中断原因后转入缺页中断处理程序
缺页率
事实上，在缺页中断处理时，当由于空间不足，需要置换部分页面到外存时，选择被置换页面还需要考虑到置换的代价，如页面是否被修改过。没有修改过的页面可以直接放弃，而修改过的页面则必须进行保存，所以处理这两种情况时的时间也是不同的。假设被置换的页面被修改的概率是β，其缺页中断处理时间为ta，被置换页面没有被修改的缺页中断时间为tb，那么，缺页中断处理时间的计算公式为 t=β×ta (1—β)×tb
页面置换算法
在进程运行过程中，若其所要访问的页面不在内存，而需把它们调入内存，但内存已无空闲空间时，为了保证该进程能正常运行，系统必须从内存中调出一页程序或数据送到磁盘的对换区中。但应将哪个页面调出，须根据一定的算法来确定。通常，把选择换出页面的算法称为页面置换算法(Page-Replacement Algorithms)。置换算法的好坏将直接影响到系统的性能。
最佳(Optimal)置换算法
最佳置换算法是由Belady于1966年提出的一种理论上的算法。其所选择的被淘汰页面将是以后永不使用的，或许是在最长(未来)时间内不再被访问的页面。采用最佳置换算法通常可保证获得最低的缺页率。但由于人们目前还无法预知，一个进程在内存的若干个页面中，哪一个页面是未来最长时间内不再被访问的，因而该算法是无法实现的，但可以利用该算法去评价其它算法。
该算法是无法实现的，但是会利用该算法去评价其它算法。
先进先出(FIFO)页面置换算法
FIFO算法是最早出现的置换算法。该算法总是淘汰最先进入内存的页面，即选择在内存中驻留时间最久的页面予以淘汰。该算法实现简单，只需把一个进程已调入内存的页面按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。但该算法与进程实际运行的规律不相适应，因为在进程中，有些页面经常被访问，比如，含有全局变量、常用函数、例程等的页面，FIFO算法并不能保证这些页面不被淘汰。
淘汰最先进入内存的页面，但可能那些页面也会被再次使用。所以这个算法也不太行。
LRU(Least Recently Used)最近最久未使用置换算法
FIFO置换算法的性能之所以较差，是因为它所依据的条件是各个页面调入内存的时间，而页面调入的先后并不能反映页面的使用情况。最近最久未使用(LRU)的页面置换算法是根据页面调入内存后的使用情况做出决策的。
需要的硬件支持：
可利用一个特殊的栈保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。假定现有一进程，它分有五个物理块，所访问的页面的页面号序列为：4，7，0，7，1，0，1，2，1，2，6
抖动
“抖动”与工作集 ：
由于请求分页式虚拟存储器系统的性能优越，在正常运行情况下，它能有效地减少内存碎片，提高处理机的利用率和吞吐量，故是目前最常用的一种系统。但如果在系统中运行的进程太多，进程在运行中会频繁地发生缺页情况，这又会对系统的性能产生很大的影响，故还须对请求分页系统的性能做简单的分析。
由于虚拟存储器系统能从逻辑上扩大内存，这时，只需装入一个进程的部分程序和数据便可开始运行，故人们希望在系统中能运行更多的进程，即增加多道程序度，以提高处理机的利用率。**但处理机的实际利用率却如图中的实线所示。 **
产生“抖动”的原因：
发生“抖动”的根本原因是，同时在系统中运行的进程太多，由此分配给每一个进程的物理块太少，不能满足进程正常运行的基本要求，致使每个进程在运行时，频繁地出现缺页，必须请求系统将所缺之页调入内存。这会使得在系统中排队等待页面调进/调出的进程数目增加。显然，对磁盘的有效访问时间也随之急剧增加，造成每个进程的大部分时间都用于页面的换进/换出，而几乎不能再去做任何有效的工作，从而导致发生处理机的利用率急剧下降并趋于0的情况。我们称此时的进程是处于“抖动”状态。
