内存管理

基本概念

地址空间：一个进程可用于寻址内存的一套地址集合。每个进程都有一个自己的地址空间。

操作系统中的存储器管理是指对内存（又称主存）的管理，是操作系统重要功能之一。

内存管理的功能

**内存空间的分配与回收。**由操作系统完成主存储器空间的分配和管理，是程序员拜托存储分配的麻烦

**地址转换。**在多道程序环境下，程序中的逻辑地址与内存的物理地址不可能一致，一次存储器管理必须提供地址变换功能，把逻辑地址转换成相应的物理地址。

内存空间的扩充。 利用虚拟存储技术或自动覆盖技术，从逻辑上扩充内存。

存储保护。 保证各道作业在各自的存储空间内运行，互不干扰。

装入和链接

内存保护

重定位寄存器（基址寄存器）含有最小的物理地址值，界地址寄存器（限长寄存器）含有最大的逻辑地址值。每个逻辑地址值必须小于界地址寄存器。

连续分区分配管理方式

单一连续分配

单一连续分配会产生内部碎片

什么是内部碎片和外部碎片

根据碎片出现的情况，可以将碎片分为内部碎片和外部碎片。

内部碎片是指已经分配给作业但不能被利用的内存空间。

外部碎片是指系统中还没有分配给作业，但是由于碎片太小而无法分配给申请内存空间的新进程的存储块。

固定分区分配中存在内部碎片，而动态分区分配中存在外部碎片。通俗点理解是，某个作业所占用的内存区域如果没有装满，就是内部碎片，而作业与作业之间，如果有内存区域没有分配给某个作业，但又不能分配给任何作业，就是外部碎片。

固定分区分配

存在内部碎片。

动态分区分配

存在外部碎片，可以通过紧凑技术解决。

首次适应算法（First Fit，FF）

下次适应算法（Next Fit，NF）

从上次查找结束的位置继续查找。

最佳适应算法（Best Fit，BF）

要求将空闲分区按照容量大小递增的次序排列

最差适应算法（Worst Fit，WF）

要求将空闲分区按照容量大小递减的次序排列

非连续分配管理方式

非连续分配管理方式根据分区大小是否固定分为分页存储管理方式和分段存储管理方式，其中分页存储管理方式根据运行作业时是否需要把作业的所有页都装入内存才运行而分为基本分页存储管理方式和请求分页存储管理方式

基本分页存储管理

假设逻辑地址为A，页面大小为L，则页号P = (int)(A/L)。页内偏移量W = A % L。

知道页号，题目中会给出相应的页表来记录每个页号存放的物理块号。块号乘以块的大小就是页面起始地址。

物理地址 = 页面起始地址 + 页内偏移量

分页存储管理的逻辑地址结构

如果每个页面大小为 2^k^B，用二进制数表示逻辑地址，则末尾k位即为页内偏移量，其余部分就是页号。因此，如果让每个页面的大小为2的整数幂，计算机就可以很方便得出一个逻辑地址对应的页号和页内偏移量。

31 12	11 0
页号P	页内偏移量W

地址结构中包含两部分：前一部分为页号P，后一部分为页内偏移量W。

==如果有K位表示“页内偏移量”，则说明该系统中一个页面的大小是 2^k^ 个内存单元==

==如果有M位表示“页号”，则说明该系统中，一个进程最多允许有2^M^ 个页面==

什么是快表（TLB）

快表，又称联想寄存器（TLB），是一种访问速度比内存快很多的告诉缓冲器，用来存放当前访问的若干页表项，以加速地址变换的过程。与此对应，内存中的页表常称为慢表。

基本分段存储管理

分页和分段的区别

分页	分段
页是信息的物理单位	段信息的逻辑单位
分页的目的是系统管理所需，为了提高内存利用率	分段的目的是为了更好地满足用户的需要
页的大小固定且由系统决定	段的长度不固定，不同的段有不同的段长，是由用户编写的程序决定的
作业地址空间是一维的	作业地址空间是二维的
有内部碎片，无外部碎片	无内部碎片，有外部碎片

因为页的大小固定，程序最后很少能刚好填满一个页，所以会有内部碎片。一般固定分配都会有内部碎片

段内连续，段间不连续，所以会有外部碎片。

为什么分页存储管理系统的地址空间是一维，而分段存储管理系统是二维的

段号是程序员自己定义的，每个段都是有特定含义。因此不同的段大小不同，代表的意义也不相同。想要找到某个数据或者指令，需要指定段号和位移两个变量。

而页号是系统自动生成的，本身地址是线性连续的。当访问特定地址时，只需要提供地址即可。系统会自动将地址划分为页号和页内位移（地址整除页的大小，商为页号，余数为页内位移），而页号对程序员来说是没有实际意义的，因此是一维的。

基本段页式存储管理

虚拟内存管理

请求分页存储管理方式

请求分页 = 基本分页 + 请求调页功能 +页面置换功能

页面置换算法

最佳置换算法（OPT）

在预知一个进程的页面号引用串的情况下，每次都淘汰以后不再使用的或以后最迟不再使用的页面，这种算法就是最佳置换算法。

显然，最佳置换算法是最优的，具有最低的缺页率。但由于实际操作中往往无法事先知道以后会引用到的所有页面信息，因此最佳置换算法无法实现，只能作为一个标准来衡量其他置换算法的优劣。

先进先出算法（FIFO）

FIFO算法是最简单的页面置换算法，每次总是淘汰最先进入内存的页面，也就是淘汰在内存驻留时间最长的页面。

该算法实现简单，用数据结构中的队列就可以实现。首先将页面按照次序排成一个队列，并设置指针指向最先进入的页面，每次需要淘汰页面时，将指针所指的页面淘汰即可。

不过FIFO算法可能会导致Belady异常（缺页次数随着分配的物理块号的增加而增加）。这是因为FIFO算法忽略了一种现象——最早调入的页面往往是使用最频繁的页面。因此FIFO算法与进程的实际运行规律不符，实际效果不好。

最近最少使用算法（LRU）

选择最近最长时间没有被使用的页面予以淘汰，其思想是用以前的页面引用情况来预测将来会出现的页面引用情况。也就是假设一个页面刚被访问，那么不久该页面还会被访问。最佳置换算法（OPT）是"向后看"，最近最少使用算法（LRU）则是"向前看"。

该算法可用寄存器组合栈来实现，性能较好。常用的页面置换算法中，LRU算法最接近最佳置换算法

时钟置换算法（CLOCK）

如果所有的引用位都为1，则会退化成FIFO替换。

改进型时钟算法

通过将引用位和修改位作为有序对，有下面四种类型：

引用位	修改位
0	0	最近没有使用过且没有修改过的页面。最佳的页面置换选择
0	1	最近没有使用过但是修改过的页面。不太好置换，因为需要将页面写出
1	0	最近使用过但没有修改过的页面。很可能会再次使用
1	1	最近使用过且修改过，很可能会再次被使用且置换之前需要将页面写出到磁盘。

其他页面置换算法

最不常用置换算法（LFU）

页面缓冲算法（PBA）