虽然内存容量在不断增长，但仍然不可能将所有用户进程和系统所需要的全部程序和数据放入主存中，因此操作系统必须将内存空间进行合理的划分和有效的动态分配。
内存管理包括：内存的分配与回收，地址转换，逻辑地址转换成物理地址，利用虚拟存储技术扩充内存等

内容大纲

• 1、程序装入和链接
• 2、连续分配管理方式
• 3、非连续分配管理方式
• 4、虚拟内存管理

1 程序装入和链接

(1)用户程序的处理步骤

在多道程序环境下，要使程序运行，必须创建进程，而创建进程就要将程序和数据装入内存。一个用户源程序要变为在内存中可执行的程序，通常要进行以下处理：

• 编译：由编译程序将用户源程序编译成若干个目标模块。
• 链接：由链接程序将目标模块和相应的库函数链接成装入模块。
• 装入：由装入程序将装入模块装入内存。

(2) 程序的链接

静态链接方式—是一种事先链接方式，即在程序运行之前，先将各目标模块及它们所需的库函数，链接成一个完整的装入模块(执行文件)，以后不再拆开。
缺点：不便于对目标模块的修改和更新；无法实现对目标模块的共享。

image.png

装入时动态链接方式— 指将一组目标模块在装入内存时，边装入边链接的方式。
运行时动态链接方式— 在程序运行中需要某些目标模块时，才对它们进行链接的方式。具有高效且节省内存空间的优点。便于实现对目标木块的共享、便于修改和更新。

(3) 程序的装入

绝对装入—编译时根据目标程序将驻留在内存中的某个位置，从而将产生绝对地址的目标代码。目标代码根据程序中的地址放入对应的内存中。此时逻辑地址和物理地址相同，绝对装入指适用于单道程序环境。
可重定位装入—多个程序的起始地址都从0开始，程序中的其他地址都是相对于起始地址的。装入时将目标程序中的指令和数据的相对地址转换成装入位置的物理地址，该过程成为重定位。这种地址变换是装入时一次完成的，称为静态重定位。
动态运行时装入—程序装入内存时，不立即把相对地址转换成绝对地址，而是把这种地址转换推迟到程序真正要执行时才进行。故装入内存后的所有地址均为相对地址。

image.png

2 连续分配管理方式

通常将主存划分成两个分区:

• 低地址分区用于驻留操作系统，以及中断向量。
• 用户进程驻留在高地址分区。

系统为程序分配的内存都是一个连续的地址空间。又分为：单一连续分配，固定分区分配和动态分区分配。

(1) 单一连续分配

最简单的一种存储管理方式，但只能用于单用户、单任务的OS中。

• 存储管理方法：将内存分为系统区（内存低端，分配给OS用）和用户区（内存高端，分配给用户用）。采用静态分配方式，即作业一旦进入内存，就要等待它运行结束后才能释放内存。
• 主要特点：管理简单，只需小量的软件和硬件支持，便于用户了解和使用。但因内存中只装入一道作业运行，内存空间浪费大，各类资源的利用率也不高。

(2) 固定分区分配

是最早使用的一种可运行多道程序的存储管理方法。

• 内存空间的划分：将内存空间划分为若干个固定大小的分区，每个分区可装入一道用户进程。分区的大小可以相等，也可以不等，但事先必须确定，在运行时不能改变。即分区大小及边界在运行时不能改变。
• 系统需建立一张分区说明表或使用表，以记录分区号、分区大小、分区的起始地址及状态（已分配或未分配）。

image.png

(3) 动态分区分配

不事先将内存划分成一块块的分区，而是在作业进入内存时，根据作业的大小动态地建立分区，并使分区的大小正好适应作业的需要。因此系统中分区的大小是可变的，分区的数目也是可变的。

image.png

• 动态分区最开始分配时是很好的，但是之后会导致内存中出现很多小的内存块。称为外部碎片。
• 孔/空闲区（Hole） – 可用内存块；内存中遍布不同大小的空闲区。
• 当进程进入系统时，就为其寻找足够大的空闲区。
• 操作系统需要维护的信息包括：�a) 已分配分区（表） b) 自由分区 (hole)

按照一定的分配算法从空闲分区中选出一个满足作业需求的分区分配给作业，如果这个空闲分区的容量比作业申请的空间要大，则将该分区一分为二，一部分分配给作业，剩下的部分仍然留在空闲分区表（链）中，同时修改空闲分区表（链）中相应的信息。目前常用分配算法有：

• 首次适应算法
• 最佳适应算法
• 最大适应算法
• 邻近适应算法

首次适应算法

• 将空闲分区（块）按地址递增的顺序排列，每次分配内存时，总是从空闲分区表（链）首开始顺序查找，直到找到第一个满足其大小要求的空闲分区为止。然后再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲分区表（链）中。
• 优先利用内存低地址部分的空闲分区,从而保留了高地址部分的大空闲区。但由于低地址部分不断被划分,致使低地址端留下许多难以利用的很小的空闲分区(碎片或零头),而每次查找又都是从低地址部分开始,这无疑增加了查找可用空闲分区的开销。

最佳适应算法

空闲分区表/链按容量大小递增的次序排列。在进行内存分配时，从空闲分区表/链的首开始顺序查找，直到找到第一个满足其大小要求的空闲分区为止。
按这种方式为作业分配内存，就能把既满足作业要求又与作业大小最接近的空闲分区分配给作业。如果该空闲分区大于作业的大小，则与首次适应算法相同，将剩余空闲分区仍留在空闲分区表/链中。

3 非连续分配管理方式

(1) 引入原因

在连续分区存储管理中，要求把进程放在一个连续的存储区中，因而会产生许多碎片。解决方法代价高。
允许将作业/进程离散放到多个不相邻接的分区中，就可以避免拼接。基于这一思想产生了以下的离散分配方式：

• 分页存储管理
• 分段存储管理
• 段页式存储管理

(2)分页存储管理-基本概念

• 进程物理地址空间可以不连续；
• 将内存物理空间划分成固定大小的块 (大小通常为2的若干次幂，如 512B，4096B)，称为页框。
• 将逻辑空间分成与物理块同样大小的页（pages）。
• 系统建立一张空闲页框表，用以维护系统中的自由空间。
• 当需要执行一个大小为 n 页的进程时，就在内存中寻找 n 自由页框，并将进程装入其中。
• 为进程设置一张页表，记录页编号和页框编号的对应关系。实现逻辑地址向物理地址的转换。

页表

image.png

地址结构及页表

CPU生成的逻辑地址被自动分成:

• 页号 (p) – 用作访问页表的索引，页表内保存每页在内存中的物理地址（块号）
• 页内偏移量 (w) – 与物理块号一同构成实际的内存物理地址。
  
  image.png

地址变换机构

为了能将用户地址空间中的逻辑地址变换为内存空间中的物理地址，在系统中必须设置地址变换机构。
地址变换结构的基本任务为：实现逻辑地址向物理地址的转换（页号->页框号）。地址变换借助页表来完成。

image.png

存在的问题

• 采用纯分页内存分配方式， CPU每存取一个指令/数据时，需要两次访问内存，一次访问页表，一次物理地址存取数据。
• 引入一种能快速搜索的高速缓冲存储器--快表。
• 快表：一种特殊高速缓冲存储器；内容--为页表中的一部分或全部。
• CPU产生的逻辑地址的页首先在快表中寻找，若找到（命中），就找出其对应的物理块；若未找到（未命中），再到页表中找其对应的物理块，并将之复制到快表。
• 若快表中内容满，则按某种算法淘汰某些页。

快表

有些处理器设计为快表和主存同时查找，如果快表命中，则主存查找终止。
一般块表的命中率达90%以上。

image.png

(3)段式存储管理

• 引入分段存储管理方式， 主要是为了满足用户和程序员。
• 程序是程序段的集合：程序段可以是：main program, procedure/ method, object等。因此进程地址形成了一个二维空间，段名和段内偏移量。
• 分段的优点：
  （1）方便编程：按逻辑关系分为若干个段，每个段从0编址，并有名字和长度，访问的逻辑地址由段名和段内偏移量决定。
  （2）信息共享和保护：共享和保护是以信息为逻辑单位，页是存储信息的物理单位，段却是信息的逻辑单位。
  （3）动态增长：实际应用中，某些段（数据段）会不断增长，前面的存储管理方法均难以实现。

地址结构及段表

每个进程都有一张逻辑空间与主存空间映射的段表。
段表项记录该段在主存中的起始地址和段的长度。

地址变换机构

为了能将用户地址空间中的逻辑地址变换为内存空间中的物理地址，在系统中必须设置地址变换机构。

image.png

(4)段页式存储管理

段页式存储管理是分段和分页原理的结合，即先将用户程序分成若干个段（段式），并为每一个段赋一个段名，再把每个段分成若干个页（页式）。其地址结构由段号、段内页号、及页内位移三部分所组成。

image.png

地址映射

image.png

4 虚拟内存管理

(1)基本概念

• 传统存储管理方式的特征：一次性（ 作业一次性全部装入内存后，才能运行。作业很大，作业很多？）；驻留性（运行完之前，作业任何部分都不能换出）。
• Bill Joy（sun CEO）说：“在研究所时，我经常开玩笑说高速缓存是计算机科学中唯一重要的思想。” 广义来说，快表、页高速缓存、虚拟内存技术都属于高速缓存技术。
• 高速缓存技术都依赖于局部性原理。时间局限性。如果程序中的某条指令一旦执行， 则不久以后该指令可能再次执行；如果某数据被访问过， 则不久以后该数据可能再次被访问。空间局限性。一旦程序访问了某个存储单元，在不久之后，其附近的存储单元也将被访问。

基于局部性原理，程序在运行之前，没有必要全部装入内存，仅须将当前要运行的页（段）装入内存即可。
运行时，如访问的页（段）在内存中，则继续执行，如访问的页未在内存中（缺页或缺段），则利用OS的请求调页（段）功能，将该页（段）调入内存。
如内存已满，则利用OS的页（段）置换功能，按某种置换算法将内存中的某页（段）调至外存，从而调入需访问的页。
虚拟存储的实现技术：

• 请求分页（Demand paging）
• 请求分段（Demand segmentation）

虚拟存储器是指仅把作业的一部分装入内存便可运行作业的存储管理系统，它具有请求调入功能和部分置换功能，能从逻辑上对内存容量进行扩充，其逻辑容量由外存容量和内存容量之和决定，其运行速度接近于内存，成本接近于外存。

(2)请求分页管理

分页请求系统—在分页系统的基础上，增加了请求调页功能、页面置换功能所形成的页式虚拟存储器系统。允许只装入若干页的用户程序和数据，便可启动运行，以后在硬件支持下通过调页功能和置换页功能，陆续将要运行的页面调入内存，同时把暂不运行的页面换到外存上，置换时以页面为单位。
系统须设置相应的硬件支持和软件：
硬件支持：请求分页的页表机制、缺页中断机构和地址变换机构。
软件：请求调页功能和页置换功能的软件。

请求分页的页表机制

image.png

缺页中断机构

在请求分页系统中，当访问的页不在内存，便产生一缺页中断，请求OS将所缺页调入内存空闲块，若无空闲块，则需置换某一页，同时修改相应页表表目。
缺页中断与一般中断的区别：
（1）在指令执行期间产生和处理中断信号
（2）一条指令在执行期间，可能产生多次缺页中断

image.png

image.png

页面置换算法

实施页面置换 – 按照某种策略从内存中寻找某页，将其换出，以腾出空间装入请求页面。
希望得到一个算法，能保证系统的缺页率最低。
刚被淘汰出内存的页面，过后不久又要访问它，需要再次将其调入，而该页调入内存后不入又再次被淘汰出内存，然后又要访问它，如此反复，使得系统把大部分时间用在了页面的调进换出上，而几乎不能完成任何有效的工作，这种现象称为抖动（又称颠簸）。
利用修改位 （modify /dirty bit ）降低页面传输开销 – 只需把发生修改的页面写回磁盘。

常用的页面置换算法：
最佳置换算法：选择永远不再需要的页面或最长时间以后才需要访问的页面予以淘汰。
先进先出置换算法：选择先进入内存的页面予以淘汰。
最近最久未使用置换算法LRU：选择最近一段时间最长时间没有被访问过的页面予以淘汰。

最佳置换

选择被淘汰的页面是以后永不使用，或是在最长时间内不再被访问的页面，从而得到最低的缺页率。
例如：系统为某进程分配了三个物理块，若有下列页面号引用串：7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1

image.png

先进先出

算法总是淘汰最先调入主存的那一页，或者说在主存中驻留时间最长的那一页（常驻的除外）。

image.png

LRU算法

算法思想：如果某个页面被访问了，则它可能马上还要访问。反之，如果很长时间未被访问，则它在最近一段时间也不会被访问。

image.png

LRU的性能接近于最佳算法，但实现起来较困难。因为要找出最近最久未使用的页面，必须为每一页设置相关记录项，用于记录页面的访问情况，并且每访问一次页面都须更新该信息。这将使系统的开销加大，所以在实际系统中往往使用该算法的近似算法。