1 内存管理概述

内存是存储系统的一部分

存储系统核心目的是存储要运行的程序数据之类的

存储系统的设计目标可以归纳为3个问题

容量，速度，和成本之间的矛盾：

三个目标不可能同时达到最优，要权衡利弊

存取速度越快，每一位价格越高

大容量就要降低速度

高速度就要降低容量

解决方案：采用层次化的存储体系

换句话说靠近CPU的，我们把他的存取速度加大，同时他的成本就会增加，容量就会减少

寄存器（CPU内）-》高速缓冲（Cache）-》内存-》磁盘-》磁带

从左到右，存取速度下降，存取容量增大

1.1 内存管理目的

有效利用内存空间

应用程序不必特别考虑内存的大小

可以大于内存

1.2 内存管理功能

记录内存的使用情况

进程所占内存空间的分配与回收

当内存不足时，采取相应措施

内存空间的共享与保护

2 程序的连接和装入

2.1 程序的连接

2.1.1程序的连接的功能

多个目标文件及库文件连接成1个完整的可执行文件。

2.1.2 程序连接的时机

静态连接：静态的，只连接1次，多次运行
装入时连接：装入后是静态的
实际运行时连接：调用时动态连接

2.2 程序的装入

每个程序运行前，必须装入内存(为什么？这样存取速度才能匹配上CPU的速度)不一定一次性全部装入

装入方式有

2.1.1 完全静态装入

程序装入时不作任何修改。
即装入内存的每个字节与其可执行文件完全相同。

2.1.2 静态重定位装入

程序装入时进行一次地址重定位，运行时不变。

重定位是把汇编中的相对地址转换为内存中的实际地址

相对地址:
用户的程序经过汇编或编译连接后形成可执行代码，代码通常采用相对地址的形式，其首地址为0，指令中的地址都采用相对于首地址的偏移量。
机器是不能用相对地址在内存中读取信息的，必须用绝对地址
绝对地址:
内存中存储单元的实际地址

2.1.3 动态重定位装入

真正执行到一条指令要访问某个内存地址时，才进行地址重定位。

一般设置1个重定位寄存器存放当前进程在内存的起始地址
绝对地址 = 相对地址 + 重定位寄存器的值

3 实存储器管理

程序的大小不能超过可用内存空间的大小

实实在在的给我装进去哈哈哈

3.1 连续分配

为每个进程分配连续的内存空间

3.1.1 单一连续分配

一般将内存划分为2个区：
系统区：存放OS程序和数据
用户区：存放用户程序和数据

如果是单一连续分配

内存中只存在1个用户程序。
整个用户区为该程序独占！

缺点：

只能用于单用户、单任务OS。所以在现代操作系统肯定是不行的

3.1.2 固定静态分区

刚刚讲到的单一连续分配为什么不能多用户，多程序呢？

因为没有划分区域，不知道哪个用户或哪个程序该用哪一块内存

改进

所以固定分区进行划分区域操作

将内存的用户区预先划分为若干区域（分区）
分区个数和每个分区的大小是固定的
每个分区存放1个进程

管理所需要的数据结构

1个分区使用表（内存分配表），记录分区状态（比如区号id，分区大小，起始地址，状态是否被使用）

缺点：

(1) 当进程大小大于划分区域的时候，无法装入，
(2) 当进程大小小于划分区域的时候，存在内部碎片(Internal fragmentation)意味着会有内存资源的浪费
(3) 分区数目固定，使活动进程数目受限，比如划分十个区域，那么最多就是十个进程

所以也是不行的

3.1.3 可变动态分区

刚刚讲到的固定静态分区很差劲哦

原因在于很多东西都是固定的，比如分区数目，比如分区大小。

那么既然如此，我们就可以让他们“动”起来！

改进

动态分区
开始时只有1个空闲分区，随着进程的装入和退出，分区的个数和每个分区的大小、位置会动态变化，既然如此我们需要一些数据结构进行记录

需要的记录的数据结构

1 空闲分区表记录开始地址，长度，以及状态（是否分配）

2 已分配分区表记录开始地址，长度，以及进程号

动态分区有一个核心就是怎么去分配分区，所以有着一系列的分区分配算法

分区分配算法

① 最先适配法（first fit）
空闲分区链（表）按地址递增的次序排列
从头开始，选择第1个大小足够的分区

② 下次适配法（next fit）
从上次分配的分区的下一个开始，选择第1个大小足够的分区

③ 最佳适配法（best fit）
空闲分区链（表）按大小递增的次序排列
从头开始，选择第1个大小足够的分区

④ 最差适配法（worst fit）
空闲分区链（表）按大小递减的次序排列
从头开始，选择第1个分区（如果足够大）

后两种方法利用率更高，但是需要排序，开销会更大

分区给不同进程分配出去了，当进程执行结束后，还需要将该进程的所在分区释放回收，这时候可能会产生一些碎片（因为没有比这些碎片小的进程放入的时候就会产生这些碎片

如何解决

1 内存紧凑（compaction）：集中小碎片为大分区

但是涉及到程序在内存中的移动，开销很大

2 根本上是因为我们上述讨论的一直都是连续分配，所以我们可以从根本上解决，提出离散分配，也就是下一章的重点！

3.2 离散分配

刚刚3.1我们讲到连续分配导致很多的碎片，所以我们可以进行离散分配，首先进程可以分为不同部分装入内存的不同分区

典型的离散分配方式，分页管理，分段管理

3.2.1 分页管理

（1）等分内存为物理块（或称页面，页框，page frame）
物理块编号为0，1，2，．．．。
（2）进程的逻辑地址空间分为不同的页（page）
页大小 = 物理块大小
页编号为0，1，2，．．．。
（3）内存分配原则：
进程的1页可装入任一物理块

这里我们注意一下和固定分区的区别，固定分区一下子只能装入一整个程序（整个程序在内存中是连续的），而分页操作可以使得一个进程不同部分离散的存储在内存的不同位置！

问题

进程的最后1页可能装不满，产生“页内碎片”。

管理的数据结构

OS为每个进程建立1个页表（Page Table）
记录进程的页号和物理块号的对应关系

地址转换

逻辑地址 → 物理地址

我们给程序分页的时候 0，1,2,3 实际上是逻辑地址或者叫相对地址，只知道这个我们肯定不知道程序在内存中的哪里，所以我们还需要通过上图的页表转换为实际的物理地址

所以对于一个程序而言，我们要找到页表，那么我们怎么找到一个程序的页表呢？

通过页表寄存器 存放当前进程的页表起始地址和长度每个进程的页表起始地址和长度平时放在其PCB（进程管理模块）中，调度时由OS放入PTR

注意的几点问题

（1）在这个过程中，需要选择页的大小

页小：碎片小，但页表占用空间大（因为页的数量会很多）

页大：页表小，但页内碎片大
通常，页的大小为2的整数次幂

所以需要对两者进行权衡

假设我们页大小为1KB=1024B（$2^{10}=1024$）则需要10位页内地址，假设逻辑地址是16位，第0-9位是页内地址，10-15位是页号

（2）进程的逻辑地址结构 ——及地址转换
地址的高位部分为页号，低位部分为页内地址

物理地址 = 块号×页大小 + 页内地址

（3）引入快表

快表，又称联想存储器(Associative Memory) ：具有并行查找能力的特殊高速缓存（cache）。
用途：保存当前进程的页表的子集（部分表项），比如最近访问过的页表项。
当切换到新进程时，快表要刷新。

目的：提高地址转换速度

思考一个问题，加深我们对于该部分的理解

1 CPU要存取一个数据时，需要访问内存几次？

2次。
第1次：访问页表，找到该页号P对应的物理块号，将此块号×页大小与页内地址拼接形成物理地址；
第2次：访问该物理地址，存取其中的指令或数据。

假设逻辑地址中，页号占20位，页内地址12位，则总共有$2^{20}$个页1M个页，如果每个页表项4B，光页表就占用4MB的空间

因而页表本身可能占用相当大的内存空间，而且是连续的。

如何解决？

采用二级页表(只能解决连续，但解决不了占用较大的内存)

将页表进行分页，页大小 = 物理块大小
设置1个一级页表，多个二级页表
一级页表：第i项记录第i号二级页表所在的物理块号
二级页表：第i项记录第i页对应的物理块号
系统设置１个页表寄存器，存放一级页表的起始地址和长度

二级页表并未减少页表所占的内存空间，但解决了页表的离散分配问题

3.2.2 分段管理

静态段式管理

按程序的逻辑划分为若干个程序段，每一个段连续，且各个段的长度不要求相等

段号从0开始

分段类似于可变分区，但不同之处在于：
一个进程可占据多个分区，而且分区之间不要求连续
分段无内部碎片，但有外部碎片。

（2）内存分配原则

以段为单位，各段不要求相邻

我们刚刚讲到的分页管理类似于固定分区，现在的分段管理则类似于可变分区，不同之处在于分区之间不要求连续。

管理需要的数据结构

OS为每个进程建立1个段表（Segment Table）
每个段在段表中有1项，记录该段在内存中的基址和长度

分段分页比较

（1）分页对程序员是不可见的；分段通常是可见的，并作为组织程序和数据的手段提供给程序员；
（2）页的大小由系统确定，段的大小由用户程序确定；
（3）分段更利于多个进程共享程序和数据；
（4）分段便于实现动态链接;
（5）分页可有效提高内存利用率，分段可更好地满足用户需要。

3.2.3 分页分段管理

动机：结合分段和分页的优点，克服二者的缺点。

进程分段——同段式管理
每段分页，内存分块，内存以块为单位分配——同页式管理

进程的逻辑地址结构

由段号、页号和页内地址构成

管理需要的数据结构

每个进程有一个段表

记录每个段对应的页表的起始地址和长度

每个段有一个页表

记录该段所有页号与物理块的关系

CPU要存取一个数据时，需要访问3次内存。

第1次：访问段表，获得该段的页表地址；
第2次：访问页表，取得物理块号，形成物理地址；
第3次：访问该物理地址，存取其中的指令或数据。

实存储管理模式下，怎么提高运行程序的大小

覆盖

把程序划分为若干个功能上相对独立的程序段（称为覆盖块），按照其自身的逻辑结构使那些不会同时执行的程序段共享同一块内存区域；

覆盖块存放在磁盘上，当一个程序段执行结束，把后续程序段调入内存，覆盖前面的程序段（内存“扩大”了）

(1) 要求程序员划分程序，提供一个明确的覆盖结构；
(2) 增加了编程的复杂度。
(3) 增加执行时间，从外存装入覆盖模块，时间换空间
对用户不透明，增加了用户负担。

所以更好的方式是虚拟存储管理

4 虚拟存储管理

进程的大小可以超过可用物理内存的大小，
由OS把当前用到的那部分留在内存，其余的放在外存中。

几个概念

虚拟地址：程序中使用的地址。进程的虚拟地址从0开始。
物理地址：可寻址的内存实际地址
虚拟地址空间：虚拟地址的集合
物理地址空间：实际的内存空间

交换技术

将当前要使用的那部分程序或数据装入内存，将暂时不用的放在磁盘上，待需要时再装入。

交换是虚拟存储器设计的基础，最初的交换是针对整个进程的交换

4.1 分页+虚拟存储

在进程开始运行之前，不是装入全部页，而是装入部分或0个页，之后根据进程运行的需要，动态装入其它页；
当内存空间已满，而又需要装入新的页时，则根据某种算法淘汰某个页，以便装入新的页。

除了页号和物理块号外，需要增加下列字段：

有效位（状态）：表示该页是否在内存中
1 表示该页位于内存中，该页表项是有效的，可以使用
0表示该页当前在外存中，访问该页表项将导致缺页异常

修改位M：表示该页在装入内存后是否被修改过
在有效位为1的情况下有效的情况下
用于回收该物理页面时，据此判断是否要把它的内容写回外存

访问位A（访问字段）：记录该页最近是否被访问过
用于页面置换算法

保护位：表示该页的允许访问方式
只读、可读写、可执行等

外存地址：该页在磁盘上的地址

由于访问的页可能不在内存，所以需要

报告不在内存——缺页中断处理

将页从外存读入内存——页的换入换出

4.1.0 缺页中断处理

1 保护当前进程现场；
2 根据页表中给出的外存地址，在外存中找到该页；
3 若内存中无空闲物理块，则选择1页换出；
4 分配一个空闲物理块，将新调入页装入内存；
5 修改页表中相应表项的状态位及相应的物理块号，修改空闲物理块表（链）；
6 恢复现场。

4.1.1 页的换入换出

页的换入换出涉及到

如何给进程分配物理块——页的分配策略

在什么范围内选择淘汰页——页的置换策略

页该怎么调入——页的调入策略

该选择哪些页被换出去——页的置换算法

1）页的分配策略：为每个进程分配多少个物理块

固定分配
为每个进程分配的总物理块数固定，在整个运行期间不变。

可变分配
先为每个进程分配一定数目的物理块，OS自身维持一个空闲物理块队列。
当发生缺页时，由系统分配一个空闲块，存入调入的页；

2）页的置换策略：在什么范围内选择淘汰页
局部置换
只从缺页进程自身选择淘汰页
全局置换
从整个内存中选择淘汰页当无空闲块时，才会换出。

3）页的调入策略
① 何时调入
请求调页（demand paging）
只有访问的页不在内存中时，才会调入该页。
预调页（prepaging）
一次调入多个连续的页。为什么这样做？
② 从何处调入：文件区（可执行文件）、交换区
全部从交换区调入
进程创建时，全部从文件区拷贝到交换区。
首次调入从文件区，以后从交换区

4）页的置换算法

选择换出页减少缺页率

最优置换算法 OPT

淘汰以后永不使用的，或者过最长时间才会被访问的页

因为无法预测将来，所以不好实现

先进先出置换算法 FIFO

只需把进程中已调入内存的页，按先后次序链成一个队列即可；链首最长，链尾最短；出现缺页时，选择链首页面进行置换，新页面加到链尾。

优点：开销较小，实现简单。
缺点：
① 它与进程访问内存的动态特性不相适应；有可能调出的页面可能是经常访问的
② 会产生belady现象。即：当分配给进程的物理块数增加时，有时缺页次数反而增加。

最近最久未使用算法 LRU

淘汰最近一次访问距当前时间最长的页。
即淘汰未使用时间最长的页
关键：如何快速地判断出哪一页是最近最久未使用的。
算法较好，但实现代价高。

实现方法

方法一：计时器

对于每一页增设一个访问时间计时器

每当某页被访问时，当时的绝对时钟内容被拷贝到对应的访问时间计时器中，这样系统记录了内存中所有页最后一次被访问的时间。
淘汰时，选取访问时间计时器值最小的页。

方法二：移位寄存器

为内存中的每一页配置一个移位寄存器
当访问某页时，将相应移位寄存器的最高位置1
每隔一定时间，寄存器右移1位
淘汰寄存器值最小的页。

方法三：栈

每次访问某页时，将其页号移到栈顶。使得栈顶始终是最近被访问的页，
栈底是最近最久未用的。

以上的最近最久未使用算法核心需要判断最久，开销较大

所以我们提出一个近似，最近未使用算法NRU

最近未使用算法 NRU 也叫做CLOCK算法

实现方法

页表中设置一个访问位，当访问某页时，将访问位置1
将内存中的所有页链成一个循环队列
从上次换出页的下一个位置开始扫描
在扫描过程中，将访问位=1的页清0，直到遇到访问位=0的页，淘汰该页，并将指针指向下一页

改进：

该算法的提出基于如下考虑：
① 对于已修改的页，换出时必须重新写回到磁盘上。因此，优先选择未访问过、未修改过的页换出；
② 淘汰一个最近未访问的已修改页要比淘汰一个被频繁访问的“干净”页好。

所以按照下面的顺序进行淘汰

第1类：A = 0，M = 0：未访问，未修改；最佳淘汰页
第2类：A = 0，M = 1：未访问，已修改
第3类：A = 1，M = 0：已访问，未修改；有可能再次访问
第4类：A = 1，M = 1：已访问，已修改

算法

① 找第1类页，将遇到的第1个页作为淘汰页；
② 若查找1周后未找到第1类页，则寻找第2类页，并将扫描经过的页的访问位清0。将遇到的第1个页作为淘汰页；
③ 否则，转①、②，一定能找到淘汰页。

最少使用算法 LFU

选择最近访问次数最少得页淘汰

通常不直接利用计数器来记录页的访问次数，而是采用移位寄存器R。
类似于LRU算法，每次访问某页时，将其移位寄存器的最高位置1。每隔一定时间将移位寄存器右移1位。

这样，在最近一段时间内使用次数最少的页就是移位寄存器各位之和最小的页。

往往配合页缓冲算法，提高LFU的效率

基本方法设置两个空闲链表空闲页链表，已修改页链表

① 若淘汰页未修改，则直接放入空闲页链表，否则放入已修改页链表；
② 当已修改页达到一定数量时，再将其一起写回磁盘，即成簇写回，以减少I/O操作的次数。

缺页率对于虚拟存储来说非常重要

因为缺页导致的中断处理相对处理时间也比较长

前面进程没有考虑进程对内存块需求的差异性，有可能给进程多增加一个物理页面，就会导致缺页率大幅度下降

所以全局置换算法可能效果更好，为进程分配可变数目的物理页面，经典的算法有工作集

工作集置换算法

1 基本思想

根据程序的局部性原理，一般情况下，进程在一段时间内总是集中访问一些页，这些页称为活动页。
如果分配给一个进程的物理块数太少了，使该进程所需的活动页不能全部装入内存，则进程在运行过程中将频繁发生缺页中断。
如果能为进程提供与活动页数相等的物理块数，则可减少缺页中断次数。

首先什么是工作集

一个进程在时刻t、参数为△的工作集W(t, △)，表示该进程在过去的△个时间单位中被访问到的页的集合。△称为工作集的窗口大小。

工作集大小的三个因素

访页序列特性
时刻t
观察该进程的时间窗口大小(△)

实现方法：

访存链表：维护窗口内的访存页面链表
访存时，换出不在工作集的页面；更新访存链表
缺页时，换入页面；更新访存链表

4.2 分段+虚拟存储

要比虚拟页式管理复杂一些

会有缺段中断

4.3 段页+虚拟存储

涉及缺段中断、缺页中断。
注意的是，对于缺段中断处理，主要是在内存中建立该段的页表，而非调入完整的一段。

影响缺页次数的因素

（1）分配给进程的物理块数
一般来说，进程的缺页中断率与进程所占的内存块数成反比。
分配给进程的内存块数太少是导致抖动现象发生的最主要原因。
（2）页的大小
缺页中断率与页的大小成反比，但页的大小也不能一味地求大，它一般在0.5KB~4KB之间，是个实验统计值。因为页大时，页表较小，占空间少，查表速度快，缺页中断次数少，但页内碎片较大。页小时，恰恰相反。
（3）程序的编写方法
进程的缺页中断率与程序的局部性（包括时间和空间局部性）程度成反比。
用户程序编写的方法不合适可能导致程序运行的时空复杂度高，缺页次数多。
（4）页置换算法
算法不合理会引起抖动。

页式管理

页

相对物理块来说，页是逻辑地址空间（虚拟内存空间）的划分，是逻辑地址空间顺序等分而成的一段逻辑空间，并依次连续编号。页的大小一般为 512B~8KB。

例如：一个 32 位的操作系统，页的大小设为 2^12=4Kb，那么就有页号从 0 编到 2^20 的那么多页逻辑空间。

段式管理

段页式管理

段页

虚拟内存

让用户感觉像是在分段，但实际上是分页管理

$命中率h=\frac{N_c}{N_c+N_m}$

其中$N_c$为Cache完成存取的总次数，$Nm$表示主存完成存取的次数

页框是什么

高级调度：

功能：调度对象是作业。其主要功能是根据某种算法，其选择从就绪队列中选择哪个进程进入内存执行，以便后续的执行。决定从外存中处于后备队列中的哪几个作业调入内存，为创建进程、分配必要的资源。

关系：高级调度与中级调度之间的关系是，高级调度将作业从后备队列中选择并将它们加载到内存中，然后中级调度负责将这些作业分配给可运行队列。高级调度与低级调度之间的关系是，它确定了哪些进程将被带入内存，以供后续的执行。

中级调度：

又称为内存调度。引入中级调度的主要目的是，提高内存利用率和系统吞吐量。

功能：中级调度的主要任务是管理内存中的进程。它可以将某些进程从内存中暂时移出，以便为其他进程腾出空间，以减轻内存压力，提高内存利用率和系统吞吐量。

关系：中级调度与高级调度之间的关系是，它接受高级调度分配的作业，将它们加载到内存中，并可以在必要时将它们暂时移出内存。中级调度还与低级调度之间有关，因为它可以调整进程的内存分布，以优化系统性能。

低级调度：

功能：低级调度是最频繁的调度级别，其任务是从就绪队列中选择下一个要执行的进程。它控制着CPU的分配，决定哪个进程将在CPU上执行，以确保公平性和性能。

关系：低级调度与高级调度之间的关系是，它执行高级调度选择的进程，将其分配给CPU执行。它还与中级调度之间有关，因为中级调度可能会将某些进程暂时移出内存，而低级调度负责在需要时将它们带回内存。

慢表（Page）：页表、段表存放在主存中，收到虚拟地址后要先访问主存，査询页表、段表，进行虚实地址转换。

快表（TLB）：提高变换速度→用高速缓冲存储器存放常用的页表项（注意不是放在内存的）

假设某计算机硬件提供了动态重定位寄存器和地址越界检查，现在为计算机涉及一个操作系统的内存管理方案，支持多进程并发执行,且不大于内存空间大小的进程可以装入内存执行

（1）阐述方案的设计思路

由于该计算机需要多进程并发执行，所以可以采用可变动态分区的方法进行内存管理，同时计算机只需要装入不大于内存的进程，所以可以采用实存储器管理方案。

综上所述可以采用实存储器管理的可变动态分区的方案进行管理

开始时只有1个空闲分区，随着进程的装入和退出，分区的个数和每个分区的大小、位置会动态变化

（2）管理所需要的数据结构