背景
存储器管理的对象主要是内存，是一种宝贵而又稀缺的资源。如何对它加以有效的管理，不仅直接影响到存储器的利用率，而且对系统性能也有重大的影响。
存储器的层次结构
在计算机执行时，要求存储器的访问速度能跟的上cpu的运行速度，还要求存储器有非常大的容量，而且存储器的价格还要便宜，目前这样三个严苛的条件是无法满足的，于是现代计算机系统中无一例外地采用了多层结果的存储系统。
多呈次结构的存储器系统
目前可分为：寄存器、高速缓存、主存储器、磁盘缓存、固定磁盘、可移动存储介质等6层，在存储层器中，层次越高（越靠近cpu），存储介质的访问速度就越快，价格就越高，存储容量就越小。寄存器、高速缓存、主存储器、磁盘缓存为操作系统的管理范畴，其中寄存器和主存储器又称为可执行存储器。而固定磁盘、可移动存储介属于设备管理的范畴。
主存储器
简称内存或者主存，用于保存程序运行时的数据，由于主存储器访问速度远低于cpu执行指令的速度，为了缓和这一矛盾，在计算机系统中引入了寄存器和高速缓存。
寄存器
有和处理机相同的速度，完全能与cpu协调工作，但价格却十分昂贵。
高速缓存
主要用于备份主存中常用的数据，以减少处理器对主存储器的访问次数，可以大幅度提高程序的执行速度。由于高速缓存的速度越高价格也越贵，故在计算机系统中设置了两级或者是多级高速缓存。
磁盘缓存
由于目前的磁盘的I/O速度远低于对主存的访问速度，为了缓和两者之间在速度上的不匹配，而设置了磁盘缓存。用于暂时存放频繁使用的一部分磁盘数据和信息，以减少访问磁盘的次数。
程序的装入和链接
用户在系统中运行一个程序，需要将它装入内存，然后再将其转变为一个可执行的程序：编译 -> 链接 -> 装入
程序的装入
- 绝对装入方式：用户程序经编译后将产生绝对地址（即物理地址）的目标代码，绝对装入程序便按照装入模块中的地址，将程序和数据装入内存，装入模块被装入内存后，由于程序中的相对地址与实际地址完全相同，故不需要对程序和数据的地址进行修改。适用于单道程序环境。
- 可重定位装入方式：在多道程序环境下，可以根据内存的具体情况将装入模块装入到内存合适的位置。在装入时对目标程序中指令和数据地址修改过程称为重定位，由因为地址变换同时是在转入时一次完成的，以后不再改变，故称为静态重定位。缺陷：不允许程序运行时在内存中移动位置。
- 动态运行时的装入方式：动态运行时的装入程序把装入模块装入内存后，并不立即把装入模块中的逻辑地址转换为物理地址，而是把这种地址转换推迟到程序真正要执行时才进行。因此装入内存后的所有地址都仍是逻辑地址。为使地址转换不影响指令的执行速度，需要重定位寄存器的支持。
程序的链接
是将目标模块以及它们所需要的库函数装配成一个完成的装入模块，根据链接的时机不同，可分为三种。
- 静态链接方式：程序运行之前，先将各目标模块及它们所需的库函数链接成一个完整的装配模块，以后不再拆开。
- 装入时动态链接：在装入内存时，边装入边链接的方式。便于目标模块的共享。
- 运行时动态链接：将对某些模块的链接推迟到执行时才进行，即在执行过程中，当发现一个被调用模块尚未被装入内存时，立即由OS去找到该模块，并将之装入内存，将其链接到调用者模块上。可以节省大量的内存空间。
连续分配存储管理方式
为了能将用户程序装入内存，必须为它分配一定大小的内存空间。该分配模式为用户程序分配一个连续的内存空间，即程序中代码或数据的逻辑地址相邻，体现在物理地址上也相邻。
单一连续分配
在单道程序系统下，单个用户独占用户内存。
固定分区分配
在多道程序系统中，为使程序之间互相不干扰，于是将整个用户空间划分为若干个固定大小的区域。
- 划分分区的方法：大小相等（缺乏灵活性）、大小不等（根据程序的大小灵活分配）。
- 内存分配：便于内存分配，需要一张分区使用表，用来记录使用情况。
由于每个分区大小固定，必然会造成存储空间的浪费，现在很少将它使用在通用的OS中。
动态分区分配
根据进程的需要，动态地为之分配内存空间。实现涉及到数据结构、分区分配算法和分区的分配与回收操作。
- 数据结构：空闲分区表：每个分区占一个表目；空闲分区链：将空闲分区表链接到一起，形成一个双向链。
- 动态分区分配算法：有顺序式搜索算法和索引式搜索算法。
- 分区分配操作：分配内存和回收内存。
顺序搜索的动态分区分配算法
为了实现动态分区分配，通常是将系统中的空闲分区链接程一个链，顺序搜索是指依次搜索空下分区链上的空闲分区，去寻找一个满足要求的分区。
- 首次适应算法（first fit）：该算法倾向于优先使用内存中地址部分的空闲区，从而保留了高址部分的大空闲区。这为以后到达的大作业分配大的空间创造了条件，缺点：地址不断被划分，会留下小的的碎片，而且每次都是从地址部分开始，增加了时间开销。
- 循环首次适应（next fit）：该算法不在从链首开始查找，而是从上次找到的位置的下一个分区开始，但这样会缺乏大的空闲区。
- 最佳适应（best fit）：总是把满足要求、又是最小的空间分区分配给作业，避免大材小用，该算法要求所有空闲分区按其容量以从小到大顺序形成一空闲分区链。缺点：还是会留下难以利用的碎片。
- 最坏适应法（worst fit）：与最佳适应算法相反：最挑选最大一个空闲分区分配。查找效率很高，一次即可。缺点：对大作业不利。
基于索引搜索的动态分区配算法
顺序搜索的动态分区分配算法适用于不太的系统，当系统很大时，分区链会很长，就会很慢。大中型系统往往使用索引搜索。
- 快速适应（quick fit）算法：又称为分类搜索算法，根据容量大小进行分类，每一类一个分区链，例如2kb、4kb、8kb等，同时在内存中建立一张索引管理表，对应记录每个类型的分区链表头的指针。在搜索时，第一步根据进程的大小，从索引表中找到合适分区链表，第二步从链表中去第一块分配即可。优点：能保留大分区，不会产生内存碎片，查找效率高；缺点：为了有效合并分区，在分区归还内存时算法负责。
- 伙伴系统（buddy system）：该算法规定，无论是已分配分区还是空闲分区，其大小均为2的k次幂。假设系统的可利用空间容量为2的m次方个字。在系统的不断运行过程中，将产生不同类型的分区，也将它们连接成一个链，这样会形成k个空闲分区链表。当需要为进程分配一个n的存续空间时，首先计算第一个i值，然后在空闲分区大小为2的i次方的空闲分区链表中查找。若找到，分配之；若没有找到，表明该长度的分区已经消耗完，需要去上一层i+1寻找，如果在上层找到，这将i+1分成2个i，一个用于分配，一个加入i的链表。依次类推...再最坏的情况下可能要进行k次分割才能得到所需分区。回收时也同理。优点：由于对空闲分区进行合并，减少了小的空闲分区，提高了空闲分区的可使用率。缺点：需要对空闲区进行合并，时间性能差点。
- 哈希算法：利用哈希快速查找的优点，以及空闲区在可利用空闲表中的分布规律，建立哈希函数，构建一张以空闲分区大小为关键字的哈希表，该表的每一个表项纪录一个对应的空闲分区链表表头指针。在当前OS中普遍采用。
动态可重定位分区分配
- 紧凑：连续分方式的特点是会造成内存碎片，为了把大作业装入，可采用的一种方法是：将内存中的所有作业移动，使它们全部都相邻，这样可以把碎片拼接成一个大分区，可以吧大作业装入该区，这种拼接的方法称为‘拼接’或‘紧凑’。但也存在问题，每次紧凑后会使程序在内存中的位置发生了变化，就必须对移动了程序和数据进行重新定位。缺点：每‘紧凑’一次，就要对移动了的程序或数据的地址进行修改，会大大影线系统的效率。
- 动态定位：在动态运行时的装入方式了解到需要重定位寄存器，它用来存放程序和数据在内存中的起始地址，程序在执行时，真正访问的内存地址是相对地址与重定位寄存器中的地址相加而形成的。地址变换过程是在程序执行期间，随着对每条指令或数据的访问自动进行，故称为动态重定位。当系统对内存进行了‘紧凑’，不需要对程序做任何修改，只要对该程序在内存的新起始地址去置换原来的起始地址即可。
- 动态重定位分区分配算法：与动态分区分配算法基本上一致，差别在于：增加了紧凑的功能。
对换（swapping）
也称为交换技术，要实现内、外存之间的交换，系统中必须有一台I/O速度较高的外存，而且容量也必须足够大。目前最常用的是大容量磁盘存储器。
多道程序环境下的对换技术
- 对换的引入：在内存中的某些进程由于某些事件尚未发生而被阻赛运行，但它却占用了大量的内存空间，甚至有时可能在内存中所有进程都被阻赛，而无可运行之进程，迫使cpu停下来等待；另一方面，却又许多作业，因内存空间不足，一致驻留在外存上，不能进入内存运行。这对系统资源是一种严重的浪费，且使系统吞吐量下降。‘对换’：是指把内存中的暂时不能运行的进程换出到外存上，以腾出足够的内存空间，在把以具备运行条件的进程换入内存。
- 对换的类型：1）整体对换：以进程为单位，作为处理机中级调度；2）页面（分段）对换：以进程的一个页面或者一个分段为单位。
- 为了实现对换，系统需要实现三方面的功能：对换空间的管理、进程的换出和进程的换入。
对换空间的管理
在具有对换功能的OS中，通常把磁盘空间分为文件区和对换区两个部分。
- 文件区管理：由于访问的频率较低，首先是提高文件存储空间的利用率，然后才是文件的访问速度，故采用离散分配方式。
- 对换空间管理：用于存放从内存换出的进程，对操作频率较高，首先要求提高进程换入换出的速度，然后才是提高文件存储空间的利用率，故采用连续分配方式，较少考虑外存中的碎片问题。
- 对换区空闲盘块管理中的数据结构：同样是空闲分区表和空闲分区链，在表目中应该包含2项：对换区的首地址及其大小，分别用盘块号和盘块数表示。
- 对换空间的分配和回收：由于是连续分配的方式，那么分配（回收）和连续分配存储类似。
进程的换出和换入
- 选择被换出的进程：首先选择处于阻塞或者睡眠状态的进程，然后按优先级最低的进程作为换出进程。
- 进程的换出：在进行换出时，应先申请对换空间，若申请成功，就启动磁盘，将该进程的程序和数据传送到磁盘的对换区上，若传送过程中未出现错误，便可回收该进程所占用的内存空间，并对该进程的pcb和内存分配表等修改。（注意：只能换出非共享的程序和数据断。）
- 进程的换入：对换进程定时执行换入操作，查看pcb集合中就绪的但已换出的进程，选择换出事件最久的进程，为它申请内存。如果申请成功，则可以直接将进程从外存掉入内存。
- 由于交换进程需要很多时间，目前的对换方式是：在处理机正常运行时，并不启动对换程序，但如果发现许多程序经常发生缺页且出现内存紧张的情况，才启动对换程序。如果发现所有的进程的缺页率都已明显减少，而系统的吞吐量都已下降时，则可暂停运行对换程序。
分页存储管理方式
连续分配方式会形成许多‘碎片’，虽然可以通过‘紧凑’的方式来许多碎片拼接成大片空间，但须为之付出很大的开销，若果允许一个进程直接分散地装入到许多不相邻的分区中，便可充分地利用内存空间，而无须在进行‘紧凑’。基于这一思想产生了离散分配方式。有分页存储管理方式、分段存储管理方式和段页式存储管理方式
分页存储管理方式
将用户程序的地址空间分为若干个固定大小的区域，称为‘页’或者‘页面’，如1kb，相应的也将内存空间分为若干个物理块，页和块的大小相同。这样可将用户程序的任一页放入任一物理块中，实现了离散分离。
- 页面和物理块：在为进程分配内存时，以块为单位，将进程中的若干页分别装入到多个不相邻的物理块中。由于进程的最后一页经常装不满一块，而形成了不可利用的碎片，称之为‘页内碎片’。
- 页面的大小：为2次幂，通常为1kb～8kb。在分页系统中，如果页面过小，可以减少内存碎片，但是会造成每个进程占用较多的页面，从而导致页表过大，占用内存，此外还会降低页面换进换出的速度。如果过大，却可以提高交换速度，但会导致页内碎片增大。
- 地址结构：包含2个部分，前一部分为页号P，后部分为偏移量W。
- 页表：为保证在内存中找到每个页面所对应的物理块，系统又为每一个进程建立一张页面映像表，简称页表。页表的作用是实现从页号到物理块号的地址映射。
通常在页表中也设置一个存取控制字段。
地址变换机构
为了能将用户地址空间中的逻辑地址转化为内存空间中的物理地址，在系统中必须设置地址变换机构。该机构的基本任务是实现从逻辑地址到物理地址的转化，借助于页表来完成的。
- 基于地址变换机构：在程序运行期间，需要查找页表的频率非常高，所以页面大多驻留在内存中，在系统中只设置一个页表寄存器PTR，只有在程序运行时，才将页表的始址和页表的长度装入寄存器中。当进程要访问某个逻辑地址中的数据时，分页地址变换机构会自动地将有效地址分为页号和业内地址2个部分，再以页号为索引去检索页表，然后获得物理块号，然后通过页内地址在物理块内上找到最终的物理地址。
- 具有快表的地址变换机构：由于页表是放在内存中的，这是cpu在每存取一个数据都要2次访问内存，第一次是访问页表，获取物理地址；第二次是通过物理地址获取数据。降低了处理机速度的1/2，是不能接受的，可以页表中的内容缓存在一个特殊的高速缓存寄存器上，称为快表。由于成本关系，快表不可能太大，通常只存放16～512个页表项。
访问内存的有效时间EAT
从进程发出指定逻辑地址的访问请求，经过地址变换，到内存中找到对应的实际物理地址单元并取出数据，所需要花费的总时间，称为EAT
1.基本分页存储管理方式中：EAT = t + t = 2t，其中t为访问一次内存的时间。
2.引入快表：EAT = aλ +(t+λ)(1-a)= 2t + λ - ta,其中λ表示查找快表的时间，a为命中率。
两级和多级页表
现代的大多数计算机系统都支持非常大的逻辑空间地址，如32位逻辑地址空间的分页系统，规定页面的大小为4kb即2的12次方，那么剩余的20位可以表示1MB个页表项，因为一个页表项占用1个字节，那么就占用1MB的内存。
- 两级页表，适合32位机器。
- 多级页表
反置页表
反置页表则是为每一个物理块设置一个页表项，并将它们按物理块的编号排序，其中的内容则是页号和其所录属进程的标识符。
- 地址变换：在利用反置页表进行地址变换时，是根据进程标示符和页号，去检索反置页表。如果检索到与之匹配的页表项，则该页表中的序号i便是该页所在的物理块号，可用该块号与页内地址一起构成物理地址送地址寄存器。
- 由于反置页表是每一个物理块设置一个页表项，当内存容量很大时，页表项的数目还是会非常大的，要利用进程标示符和页号去检索这样一张线性表也是相当耗时的，于是利用hash算法来检索。
分段存储管理方式
引入分段存储管理方式的目的，则是主要为了满足用户（程序员）在编程和使用上多方面的要求，其中有些要求是其他几种存储管理方式所难以满足的。
引入
一方面由于通常的程序都可以分为若干段，如主程序段、子程序段；另一方面是实现和满足信息共享、信息保护、动态链接以及信息的动态增长等需要，也都是以段为基本单位。更具体地说，分段存储管理方式更符合用户和程序员的需要。
- 方便编程
- 信息共享
- 信息保护
- 动态增长
- 动态链接
基本原理
- 分段：将作业的地址空间划分为若干个段，每个段定义一组逻辑信息。
- 地址结构：前一部分为段号，后一部分为段内地址。
- 段表：在系统中，类似于分页系统，需要为每一个进程建立一张段映射表，简称段表，段表可以放在寄存器中，但通常放在内存中，在配置了段表后，执行中的进程可以通过查找段表，找到每一个段所对应的内存区，可见，段表是用于实现从逻辑段到物理内存区的映射。
- 地址变换机构：和分页系统一样，当段表放在内存中时，每要访问一个数据，都需要访问两次内存，解决办法也是一样。
分页和分段的主要区别
- 页是信息的物理单位，采用分页存储管理方式是为实现离散分配方式，以消减内存的外零头，提高内存的利用率。分段则是信息的逻辑单位，它通常包含的是一组意义相对完整的信息，分段的目的主要是在于能更好地满足用户的需要。
- 页的大小固定且由系统决定。段的长度却不确定，决定于用户所编写的程序，通常有编译程序在对源程序进行编译时，根据信息的性质来划分。
- 分页的用户程序地址空间是一维的，分段是二维的，程序员在标示一个地址时，即需要给出段名，有需要给出段内地址。
段页式存储管理方式
分页和分段的结合
- 地址结构：由段号、段内页号及页内地址三部分所组成。
- 基本原理：在段页式系统中，为了实现从逻辑地址到物理地址转变，系统中需要同时配置段表和页表。
- 地址变换：配置一个段表寄存器，放置段表始址和段长。需要先利用段号和段表始址求出该段对应的段表项的位置，从中读出该段的页表始址，并利用逻辑地址中的段内页号来获取对应页的页表项位置，从中读出物理块，再利用块号和页内地址找到物理地址。
- 如果段表在内存中，需要三次访问内存，为了提高执行速度，增加一个高速缓存寄存器。
