计算机不可能将所有用户进程和系统所需要的全部程序和数据放入主存，因此操作系统必须对内存空间进行合理的划分和有效的动态分配。内存管理的概念就是操作系统对内存的划分和动态分配。

内存管理功能：

创建进程首先要将程序和数据装入内存。将用户源程序变为可在内存中执行的程序，通常需要以下几个步骤：

程序的链接有以下三种方式：

内存的装入模块在装入内存时，有以下三种方式： 重定位：根据内存的当前情况，将装入模块装入内存的适当位置，装入时对目标程序中的指令和数据的修改过程称为重定位。

内存分配前，需要保护操作系统不受用户进程的影响，同时保护用户进程不受其他用户进程的影响。内存保护可采取如下两种方法：

覆盖与交换技术是在多道程序环境下用来扩充内存的两种方法，目的是减少程序占用的主存空间来扩充内存。 覆盖是在同一个程序或进程中的，交换是在不同进程之间的。

覆盖技术的基本思想：将程序分为多个段，常用的段常驻内存，不常用的段在需要时调入内存。

特点：打破了必须将一个进程的全部信息装入主存后才能运行的限制，解决了程序大小超过物理内存总和的问题。但对用户不透明，增加了编程的负担

交换技术的基本思想：内存空间紧张时，系统将内存中的某些进程暂时换出外存，把外存中某些已具备运行条件的进程换入内存。

交换的时机选择的策略：

连续分配方式是指为一个用户程序分配一个连续的内存空间。主要包括单一连续分配、固定分区分配和动态分区分配。

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

固定分区分配是最简单的一种多道程序存储管理方式，它将用户内存空间划分为若干固定大小的分区，每个分区只装入一道作业，当有空闲分区时，便可再从外存的后备队列中选择适当大小的作业装入该分区。

固定分区分配分为分区大小相等和分区大小不等两种方式。

动态分区分配不预先分配内存，而是在进程装入内存时，根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。系统中分区的大小和数目是可变的。

动态分区分配会产生外部碎片，克服外部碎片可以采用紧凑技术来解决，即操作系统不时地对进程进行移动和整理。但这需要重定位寄存器的支持，且相对费时。

动态分区分配的策略有以下几种算法：

其中，首次适应算法不仅是最简单的，而且通常也是最好和最快的，但是会使得内存的低地址部分出现很多小的空闲分区，每次分配查找时，都要经过这些分区，因此增加了查找的开销。邻近适应算法试图解决这个问题，但实际上，它常常导致在内存的末尾分配空间分裂成小碎片，通常比首次适应算法的效果要差。 最佳适应算法会产生最多的外部碎片。 最坏适应算法会很快导致没有可用的大内存块。

非连续分配允许一个程序分散地装入不相邻的内存分区，但这也需要额外的存储空间去存储它们的索引，使得非连续分配方式的存储密度低于连续存储方式。 非连续分配管理方式根据分区的大小是否固定，分为分页存储管理方式和分段存储管理方式。在分页存储管理方式中，又根据运行作业时是否要把作业的所有页面都装入内存才能运行，分为基本分页存储管理方式和请求分页存储管理方式。

不会产生外部碎片，只会产生少量的内部碎片 分页的基本思想：把主存空间划分为大小相等的块，块相对较小，作为主存的基本单位。每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的块空间。

分页存储的基本概念如下：

逻辑地址到物理地址的变换过程如下：

分页管理方式存在的两个主要问题：

具有快表的地址变换机构：

若页表全部放在内存中，则存取一个数据或一条指令至少要访问两次内存，第一次是访问页表，确定所存取的数据或指令的物理地址；第二次是根据该地址存取数据或指令。 在地址变换机构中增设一个具有并行查找能力的高速缓冲存储器——快表，又称相联存储器（TLB），用来存放当前访问的若干页表项，以加速地址变换过程。

引入快表后的地址变换过程如下：

两级页表 单级页表存在的问题：

为了压缩页表，采用二级页表机制。在进程执行时，只需要将这一页的上一级页表调入内存即可，进程的页表和进程本身的页面可在后面的执行中再调入内存。

建立多级页表的目的在于建立索引，以便不用浪费主存空间去存储无用的页表项，也不用盲目地顺序式查找页表项。若采用多级页表机制，则各项页表的大小不能超过一个页面。

不会产生内部碎片，会产生外部碎片

分段存储管理的相关概念如下：

分页与分段的对比

页式管理方式能有效地提高内存利用率，而分段存储管理能反映程序的逻辑结构并有利于段的共享。将这两种存储管理方式结合起来，便形成了段页式存储管理方式。

在段页式系统中，作业的地址空间首先被分成若干逻辑段，每段有自己的段号，然后将每段分成若干大小固定的页。对内存空间的管理仍然和分页存储管理一样，将其分成若干和页面大小相同的存储块，对内存的分配以存储块为单位。

段页式系统中的作业逻辑地址分为三部分：段号、页号和页内偏移量。 段号的位数决定了每个进程最多可以分几个段 页号位数决定了每个段最大有多少页 页内偏移量决定了页面大小、内存块大小是多少

其中，在一个进程中，段表只有一个，而页表可能有多个。进行一次访问需要查段表、查页表和访问目标单元三次访存。

段页式系统的地址变换机构如下所示：

高速缓存技术利用的是局部性原理，将频繁使用的数据放到更高速的存储器中。

基于局部性原理，在程序装入时，可以将程序中很快会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需信息从外存调入内存，然后继续执行程序。若内存空间不够，由操作系统负责将内存中暂时用不到的信息换出到外存。在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存。

虚拟存储器的最大容量由计算机的地址结构决定，实际容量 = min{内存和外存的容量之和，CPU的寻址范围}。并不是简单的内外存容量相加。

虚拟存储器有以下三个特性：

虚拟内存技术的实现需要建立在离散分配的内存管理方式的基础上。

虚拟内存的实现有以下三种方式：

不管哪种实现方式，都需要硬件技术的支持。一般需要的支持有以下几个方面：

请求分页产生内部碎片，请求分段产生外部碎片

请求分页系统建立在基本分页系统的基础之上，为了支持虚拟存储器功能而增加了请求调页和页面置换功能。在请求分页系统中，只要求将当前需要的一部分页面装入内存，便可以启动程序运行。

请求分页系统的页表机制不同于基本分页系统，请求分页系统在一个作业运行之前不要求全部一次性调入内存，因此在作业运行过程中，必然会出现要访问的页面不在内存中的情况，如何发现和处理这种情况是请求分页系统必须解决的两个基本问题。为此，在请求页表项中增加了4个字段，如下图所示。

在请求分页系统中，每当要访问的页面不在内存中时，便产生一个缺页中断，请求操作系统将所缺的页调入内存。此时应将缺页的进程阻塞（调页完成唤醒），若内存中有空闲块，则分配一个块，将要调入的页装入该块，并修改页表中的相应页表项，若此时内存中没有空闲块，则要淘汰某页，若被淘汰的页在内存期间被修改过，则要将其写回外存。

缺页中断与一般中断的不同：

在进行地址变换时，先检索快表：

请求分页中的地址变换过程如下所示：

进程运行时，若其访问的页面不在内存中而需将其调入，但内存已无空闲空间时，就需要从内存中调出一页程序或数据，送入磁盘的对换区。 选择调出页面的算法就称为页面置换算法。用页面置换算法决定应该换出哪个页面。页面的换入换出需要有磁盘的I/O，会有较大的开销，因此好的页面置换算法需要追求更少的缺页率。

最佳页面置换算法选择的被淘汰页面是以后永不使用的页面，或是在最长时间内不再被访问的页面，以便保证获得最低的缺页率。但是，人们无法预知进程在内存下的若干页面中的哪个是未来最长时间内不再被访问的，因为该算法无法实现。

优先淘汰最早进入内存的页面，即再内存中驻留时间最久的页面。 FIFO算法还会产生所分配的物理块数增大而页故障数不减反增的异常现象，这成为Belady异常。只有FIFO算法可能出现Belady异常。 Belady异常如下图所示： 物理块数由三个增加到四个，缺页数反而增加。

选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。 LRU算法需要寄存器和栈的硬件支持。

最佳置换算法性能最好，但无法实现;先进先出置换算法实现简单，但算法性能差;最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。 时钟置换算法是一种性能和开销较均衡的算法，又称CLOCk算法，或最近未用算法（NRU，NotRecently Used)

简单的CLOCK算法实现方法 为每个页面设置一个访问位，再将内存中的页面都通过链接指针链接成一个循环队列。当某页被访问时，其访问位置为1。当需要淘汰一个页面时，只需检查页的访问位。如果是o，就选择该页换出;如果是1，则将它置为0，暂不换出，继续检查下一个页面，若第一轮扫描中所有页面都是1，则将这些页面的访问位依次置为o后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过两轮扫描)

改进型的时钟算法 简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。 因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。这就是改进型的时钟置换算法的思想。修改位=0，表示页面没有被修改过;修改位=1，表示页面被修改过。

为方便讨论，用（访问位，修改位）的形式表示各页面状态。如（1，1）表示一个页面近期被访问过，且被修改过。

算法规则:将所有可能被置换的页面排成一个循环队列 第一轮:从当前位置开始扫描到第一个(0,0）的帧用于替换。本轮扫描不修改任何标志位 第二轮:若第一轮扫描失败，则重新扫描，查找第一个（0,1）的帧用于替换。本轮将所有扫描过的帧访问位设为o 第三轮:若第二轮扫描失败，则重新扫描，查找第一个(0,0）的帧用于替换。本轮扫描不修改任何标志位 第四轮:若第三轮扫描失败，则重新扫描，查找第一个(0,1）的帧用于替换。 由于第二轮已将所有帧的访问位设为0，因此经过第三轮、第四轮扫描一定会有一个帧被选中，因此改进型cLOcK置换算法选择一个淘汰页面最多会进行四轮扫描.

驻留集：指请求分页存储管理中给进程分配的物理块的集合。

固定分配：操作系统为每个进程分配一组固定数目的物理块，在进程运行期间不再改变。即，驻留集大小不变

可变分配：先为每个进程分配一定数目的物理块，在进程运行期间，可根据情况做适当的增加或减少。即，驻留集大小可变

局部置换：发生缺页时只能选进程自己的物理块进行置换。

全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，也可以将别的进程持有的物理块置换到外存，再分配给缺页进程。

页面分配、置换策略 调入页面的时机

从何处调入页面

刚刚换出的页面马上又换入主存，刚刚换入的页面马上又换出主存，这种频繁的页面调度行为称为抖动或颠簸。 抖动发生的主要原因是，进程频繁访问的页面数目高于可用的物理页帧数目，即分配给进程的物理块不够。

工作集指在某段时间间隔内，进程要访问的页面集合。基于局部性原理，可以用最近访问过的页面来确定工作集。

若工作集窗口大小为4，则各时刻工作集如下所示： 为了防止抖动现象，一般来说给进程分配的物理块数（即驻留集大小）要大于工作集大小。