1、内存连续分配

单一连续分配方式

• 内存在此方式下分为系统区和用户区
• 系统区仅提供给操作系统使用，通常在低地址部分
• 用户区是为用户提供的、除系统区之外的内存空间
• 优点：简单、无外部碎片，可以釆用覆盖技术，不需要额外的技术支持
• 缺点：只能用于单用户、单任务的操作系统中，有内部碎片，存储器的利用率极低

固定分区分配

• 固定分区分配是最简单的一种多道程序存储管理方式。
• 将用户内存空间划分为若干个固定大小的区域，每个分区只装入一道作业。
• 当有空闲分区时，便可以再从外存的后备作业队列中,选择适当大小的作业装入该分区，如此循环。
• 划分分区方法：
  • 分区大小相等
  • 分区大小不等
• 存在的问题：
  • 程序可能太大而放不进任何一个分区中，这时用户不得不使用覆盖技术来使用内存空间
  • 主存利用率低，当程序小于固定分区大小时，也占用了一个完整的内存分区空间，产生内部碎片

动态分区分配

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

动态分区算法

1. 首次适应(First Fit)算法：空闲分区以地址递增的次序链接。分配内存时顺序查找，找到大小能满足要求的第一个空闲分区。
2. 最佳适应(Best Fit)算法：空闲分区按容量递增形成分区链，找到第一个能满足要求的空闲分区。
3. 最坏适应(Worst Fit)算法：又称最大适应(Largest Fit)算法，空闲分区以容量递减的次序链接。找到第一个能满足要求的空闲分区，也就是挑选出最大的分区。
4. 临近适应算法(Next fit)算法：从当前位置开始，搜索第一个能满足进程要求的内存空间

动态分区的缺点

随着时间的推移，内存中会产生越来越多的外部碎片，内存的利用率随之下降。

2、逻辑地址vs物理地址

①逻辑地址，是指计算机用户(例如程序开发者)，看到的地址。是程序在内存中的相对地址或者说相对于当前进程某一点（程序起始位置或段基地址）的偏移位置；（逻辑地址并不唯一）例如，当创建一个长度为100的整型数组时，操作系统返回一个逻辑上的连续空间：指针指向数组第一个元素的内存地址。由于整型元素的大小为4个字节，故第二个元素的地址时起始地址加4，以此类推。事实上，逻辑地址并不一定是元素存储的真实地址，即数组元素的物理地址(在内存条中所处的位置)，并非是连续的，只是操作系统通过地址映射，将逻辑地址映射成连续的，这样更符合人们的直观思维。

②物理地址也称为绝对地址，是内存的实际地址——加载到内存地址寄存器（CS,IP）中的地址；

3、内存的非连续分配

①页式存储

用户程序的地址空间被划分成若干固定大小的区域，称为“页”，相应地，内存空间分成若干个物理块或页帧（Page Frame），页和块的大小相等。可将用户程序的任一页放在内存的任一块中，实现了离散分配：物理块不一定连续。每个页对应一个物理块。

逻辑地址结构：地址结构包含两部分：前一部分为页号P，后一部分为页内偏移量W。如果是32位地址，则 0-11 位为页内地址，即每页大小为4KB；12-31位为页号，地址空间最多允许有2^{20}页

延续上面的例子，考虑一个n+m的位的地址，则最左边的n位是页号（相对于进程来说的页号，是进程页表的索引），最右边的m位是偏移量。则地址转换步骤为：

• 提取页号，即逻辑地址最左面的n位；
• 以这个页号为索引查找该进程页表中对应的页表项得到该页对应的页框号k；
• 该页框的起始物理地址为k*2^m，被访问字节的物理地址是这个起始地址加上偏移量。

页表：因为程序数据存储在不同的页面中，而页面又离散的分布在内存中，因此需要一个页表来记录逻辑地址和实际存储地址之间的映射关系，以实现从页号到物理块号的映射

每一个进程都拥有一个自己的页表，PCB表中有指针指向页表。

分页存储管理方式中，又根据运行作业时是否要把作业的所有页面都装入内存才能运行分为基本分页存储管理方式和请求分页存储管理方式。

地址转换

地址变换的任务是将逻辑地址转换为内存中物理地址，地址变换是借助于页表实现的

当进程执行时，将页表始址和长度存入页表寄存器

设页大小为L（一般为4K），逻辑地址A到物理地址E的变换过程如下：

1. 计算页号P(P=A/L)和页内偏移量W (W=A%L)，这里的P取整
2. 比较页号P和页表长度M，若P >= M，则产生越界中断，否则继续执行
3. 页表中页号P对应的页表项地址 = 页表起始地址F + 页号P * 页表项长度（一般为4B），取出该页表项内容b，即为物理块号
4. 计算E=b*L+W，用得到的物理地址E去访问内存

在虚拟内存中

在表示页号的内容中，最后一位是用于表示此页是否已经提取出来，已经提取出来则为1，还在物理内容中则为0.如果为1则将剩余的页号直接复制到输出物理内存的前n-1位。

分页管理方式存在的问题

每次访存操作都需要进行逻辑地址到物理地址的转换，地址转换过程必须足够快，否则访存速度会降低
每个进程引入了页表，用于存储映射机制，页表不能太大，否则内存利用率会降低

局部性原理：
时间上的局部性：最近被访问的页在不久的将来还会被访问，因为程序中存在大量的循环（因此在页表系统中，可能连续很多次查到同一个页表项）
空间上的局部性：内存中被访问的页周围的页也很可能被访问，因为很多数据在内存中都是连续存放的

因此引入快表。

快表

又称联想寄存器TLB，是一种访问速度比内存快很多的高速缓冲存储器，用来存发当前访问的若干页表项，以加速地址变换的过程。因此内存中的页表常称为慢表

引入快表之后的地址转换过程

1. CPU给出逻辑地址，由某个硬件算得页号、页内偏移量，然后将页号与快表中的所有页号进行比较。

2. 如果找到匹配的页号，说明要访问的页表项在快表中有副本，则直接从中取出该页对应的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此，若快表命中，则访问某个逻辑地址仅需一次访存即可。

3. 如果没有找到匹配的页号，则需要访问内存中的页表，找到对应页表项，得到页面存放的内存块号，再将内存块号与页内偏移量拼接形成物理地址，最后，访问该物理地址对应的内存单元。因此,若快表未命中，则访问某个逻辑地址需要两次访存
   (注意:在找到页表项后，应同时将其存入快表,以便后面可能的再次访问。但若快表已满，则必须按照-定的算法对旧的页表项进行替换)

例子:某系统使用基本分页存储管理，并采用了具有快表的地址变换机构。访问- -次快表耗时1us， 访问一次内存耗时100us。若快表的命中率为90%，那么访问一个逻辑地址的平均耗时是多少?
(1+100) * 0.9 + (1+100+100) * 0.1 = 111 us（因为无论快表是否命中，但都会先查询快表，且至少会读取一次内存）
有的系统支持快表和慢表同时查找，如果是这样，平均耗时应该是(1+100) * 0.9+ (100+100) *0.1=110.9 us
若未采用快表机制，则访问一个逻辑地址需要100+100 = 200us
显然，引入快表机制后，访问一个逻辑地址的速度快多了。

总结

二级页表

单级页表的问题

很多时候，进程在一段时间内只需要访问某几个页面就可以正常运行了，因此没有必要让整个页表都常驻内存。

如果内存的逻辑地址很大，将会导致程序的页表项会很多，而页表在内存中是连续存放的，所以相应的就需要较大的连续内存空间。

两级页表的原理

为了解决这个问题，可以采用两级页表或者多级页表的方法：外层页表一次性调入内存且连续存放，内层页表离散存放。
所以一共需要访问内存3次才可以读取一次数据：访问顶级页表->访问二级页表->访问内存中的数据

两级页表实现地址转换

4、基本分段存储管理方式

分段

进程的地址空间按照程序的自身逻辑关系划分为若干个段，每个段都有一个段名，每段从0开始编址
内存分配规则：以段为单位进行分配，每个段在内存中占据连续空间，但各段之间可以不相邻

段表

为了在内存中找到各个段的存放位置，建立映射表

地址转换

1. 根据逻辑地址得到段号、段内地址
2. 判断段号是否越界
3. 查询段表，找到对应的段表项，段表项的存放地址为段表开始的地址+段号*段表项的长度
4. 检查段内地址有没有超过段长
5. 计算得到物理地址（段基址+段内地址）
6. 访问

分段和分页的对比

1. 页是信息的物理单位。分页的主要目的是为了实现离散分配，提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的。段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑模块的信息。分段对用户是可见的，用户编程时需要显式地给出段名。
2. 页的大小固定且由系统决定。段的长度却不固定，决定于用户编写的程序。
3. 在分段的方法中，每次程序运行时总是把程序全部装入内存，而分页的方法则有所不同。分页的思想是程序运行时用到哪页就为哪页分配内存，没用到的页暂时保留在硬盘上。当用到这些页时再在物理地址空间中为这些页分配内存，然后建立虚拟地址空间中的页和刚分配的物理内存页间的映射。
4. 分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址。分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出段内地址。（？我不是很懂这里）
   
5. 分段比分页更容易实现信息的共享和保护。不能被修改的代码称为纯代码或可重入代码(不属于临界资源)，这样的代码是可以共享的。可修改的代码是不能共享的
   

优缺点分析

访问一个逻辑地址需要几次访存?

分页(单级页表) :第一次访存–查内存中的页表，第二次访存一-访问目标内存单元。总共两次访存
分段:第一次访存–查内存中的段表，第二次访存–访问目标内存单元。总共两次访存
与分页系统类似，分段系统中也可以引入快表机构，将近期访问过的段表项放到快表中，这样可以少一次访问，加快地址变换速度。

段页式管理

1. 根据逻辑地址得到段号、页号、页内偏移量
2. 判断是否越界
3. 查询段表，得到段表项
4. 检查页号是否越界
5. 根据页表存放块号、页号查询页表，找到对应页表项
6. 根据内存块号、页内偏移量得到物理地址

5、虚拟内存

虚拟内存的基本思想是：在程序装入时，可以将程序的一部分装入内存，而将其余部分留在外存，就可以启动程序执行。在程序执行过程中，当所访问的信息不在内存时，由操作系统将所需要的部分调入内存,然后继续执行程序。

虚拟内存的最大容量是由计算机的地址结构(CPU寻址范围)确定的
虚拟内存的实际容量= min (内存和外存容量之和，CPU寻址范围)

如:某计算机地址结构为32位，按字节编址，内存大小为512MB，外存大小为2GB。
则虚拟内存的最大容量为2^32 B = 4GB
虚拟内存的实际容量= min (2^32 B, 512MB+2GB) = 2GB+512MB

虚拟内存使整个地址空间可以用相对较小的单元映射到物理内存，而不是为正文段和数据段分别进行重定位。

##与传统存储器比较虚拟存储器有以下三个主要特征：
多次性，是指无需在作业运行时一次性地全部装入内存，而是允许被分成多次调入内存运行。
对换性，是指无需在作业运行时一直常驻内存，而是允许在作业的运行过程中，进行换进和换出。
虚拟性，是指从逻辑上扩充内存的容量，使用户所看到的内存容量，远大于实际的内存容量。

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

1. 请求分页存储管理。（最常用）
2. 请求分段存储管理。
3. 请求段页式存储管理。

1、请求分页

1、为了实现请求调页，需要知道页面是否已经调入内存，也需要知道存放的位置
2、需要算法来实现决定调哪个页面

缺页中断机制

缺页中断是因为当前执行的指令想要访问的目标页面未调入内存而产生的，因此缺页中断作为中断同样要经历，诸如保护CPU环境、分析中断原因、转入缺页中断处理程序、恢复CPU环境等几个步骤。

一般的中断

所谓的中断就是在计算机执行程序的过程中，由于出现了某些特殊事情，使得CPU暂停对程序的执行，转而去执行处理这一事件的程序。等这些特殊事情处理完之后再回去执行之前的程序。中断一般分为三类：

1. 由计算机硬件异常或故障引起的中断，称为内部异常中断；
2. 由程序中执行了引起中断的指令而造成的中断，称为软中断（这也是和我们将要说明的系统调用相关的中断）；
3. 由外部设备请求引起的中断，称为外部中断。简单来说，对中断的理解就是对一些特殊事情的处理。

• 与中断紧密相连的一个概念就是中断处理程序了。当中断发生的时候，系统需要去对中断进行处理，对这些中断的处理是由操作系统内核中的特定函数进行的，这些处理中断的特定的函数就是我们所说的中断处理程序了。
• 另一个与中断紧密相连的概念就是中断的优先级。中断的优先级说明的是当一个中断正在被处理的时候，处理器能接受的中断的级别。中断的优先级也表明了中断需要被处理的紧急程度。每个中断都有一个对应的优先级，当处理器在处理某一中断的时候，只有比这个中断优先级高的中断可以被处理器接受并且被处理。优先级比这个当前正在被处理的中断优先级要低的中断将会被忽略。
• 典型的中断优先级如下所示：
• 机器错误 > 时钟 > 磁盘 > 网络设备 > 终端 > 软件中断*

地址变换机构

6、页面置换算法（重中之重）

1、最佳置换法：OPT

每次选择的页面是在最长时间内不再被访问的页面，可以保证最低的缺页率
但是实际上os无法预判页面的访问序列，所以是无法实现的

2、先进先出置换算法FIFO

每次选择淘汰的页面时最早进入内存的页面

注意！！此处放入4之后，再访问3、2时没有缺页。当想要访问1时，虽然3不是最久没有被访问的，但是3是最久以前放入的，所以还是要置换3.

Belady异常—当为进程分配的物理块数增大时，缺页次数不减反增的异常现象。

只有FIFO算***产生Belady异常，而LRU和OPT算法永远不会出现Belady异常。另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应，因为先进入的页面也有可能最经常被访问。因此，算法性能差

FIFO的性能较差，因为较早调入的页往往是经常被访问的页，这些页在FIFO算法下被反复调入和调出，并且有Belady现象。所谓Belady现象是指：采用FIFO算法时，如果对—个进程未分配它所要求的全部页面，有时就会出现分配的页面数增多但缺页率反而提高的异常现象。

3、最近最久未使用置换算法LRU

每次淘汰的页面是最近最久未使用的页面
实现方法:赋予每个页面对应的页表项中，用访问字段记录该页面自上次被访问以来所经历的时间t(该算法的实现需要专门的硬件支持，虽然算法性能好，但是实现困难，开销大)。当需要淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面。

LRU性能较好，但需要寄存器和栈的硬件支持。LRU是堆栈类算法，理论上可以证明，堆栈类算法不可能出现Belady异常。

4、时钟置换算法CLOCK（NRU）

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

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

5、改进型的时钟置换算法

简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过,就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。

因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。这就是改进型的时钟置换算法的思想。修改位=0，表示页面没有被修改过;修改位=1，表示页面被修改过。

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

改进型的Clock算法需要综合考虑某一内存页面的访问位和修改位来判断是否置换该页面。在实际编写算法过程中，同样可以用一个等长的整型数组来标识每个内存块的修改状态。访问位A和修改位M可以组成一下四种类型的页面。

算法规则:将所有可能被置换的页面排成–个循环队列

总结

7、页面调用

驻留集：指请求分页存储管理中给进程分配的物理块的集合。
对于分页式的虚拟内存，不需要把一个进程的所有页都读取到主存，操作系统必须决定读取多少页。也就是说，给特定的进程分配多大的主存空间，这就是驻留集。

主要考虑以下几点：

• 分配给一个进程的存储量越小，在任何时候驻留在主存中的进程数就越多，从而可以提高处理机的时间利用效率
• 如果分配给一个进程的存储量太小，尽管有局部性原理，页错误率仍然会相对较高
• 如果存储量太大，页数过多，由于局部性原理，给特定的进程分配更多的主存空间对该进程的错误率没有明显的影响

操作系统通常釆用三种策略：

1、固定分配局部置换

为每个进程分配一定数目的物理块，在整个运行期间都不改变。若进程在运行中发生缺页，则只能从该进程在内存中的页面中选出一页换出，然后再调入需要的页面

2、可变分配全局置换

为系统中的每个进程分配一定数目的物理块,操作系统自身也保持一个空闲物理块队列。
当某进程发生缺页时，系统从空闲物理块队列中取出一个物理块分配给该进程，并将欲调入的页装入其中。

3、可变分配局部置换

为每个进程分配一定数目的物理块
当某进程发生缺页时，只允许从该进程在内存的页面中选出一页换出，这样就不会影响其他进程的运行
如果进程在运行中频繁地缺页，系统再为该进程分配若干物理块，直至该进程缺页率趋于适当程度
反之，若进程在运行中缺页率特别低，则可适当减少分配给该进程的物理块

调入页面的时机

1.预调页策略：根据局部性原理(主要指空间局部性，即:如果当前访问了某个内存单元，在之后很有可能会接着访问与其相邻的那些内存单元。)，一次调入若干个相邻的页面可能比一次调入一个页面更高效。但如果提前调入的页面中大多数都没被访问过，则又是低效的。因此可以预测不久之后可能访问到的页面，将它们预先调入内存，但目前预测成功率只有50% 左右。故这种策略主要用于进程的首次调入(运行前调入)，由程序员指出应该先调入哪些部分。
2. 请求调页策略：进程在运行期间发现缺页时才将所缺页面调入内存(运行时调入)。由这种策略调入的页面一定会被访问到，但由于每次只能调入一页，而每次调页都要磁盘I/0操作，因此I/0开销较大。

从何时调入页面

请求分页系统中外存分为两部分：用于存放文件的文件区和用于存放对换页面的对换区。对换区通常是采用连续分配方式，而文件区采用离散分配方式，故对换区的磁盘I/O速度比文件区的更快。

1.系统拥有足够的对换区空间:页面的调入、调出都是在内存与对换区之间进行，这样可以保证页面的调入、调出速度很快。在进程运行前，需将进程相关的数据从文件区复制到对换区。
2.系统缺少足够的对换区空间:凡是不会被修改的数据都直接从文件区调入，由于这些页面不会被修改，因此换出时不必写回磁盘，下次需要时再从文件区调入即可。对于可能被修改的部分，换出时需写回磁盘对换区，下次需要时再从对换区调入。
3.UNIX方式:运行之前进程有关的数据全部放在文件区，故未使用过的页面，都可从文件区调入。若被使用过的页面需要换出，则写回对换区，下次需要时从对换区调入。

抖动现象

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

为进程分配的物理块太少，会使进程发生抖动现象。为进程分配的物理块太多，又会降低系统整体的并发度，降低某些资源的利用率
为了研究为应该为每个进程分配多少个物理块，Denning 提出了进程工作集” 的概念

工作集

驻留集:指请求分页存储管理中给进程分配的内存块的集合。
工作集:指在某段时间间隔里，进程实际访问页面的集合。

原理：让操作系统跟踪每个进程的工作集，并为进程分配大于其工作集的物理块。如果还有空闲物理块，则可以再调一个进程到内存以增加多道程序数。如果所有工作集之和增加以至于超过了可用物理块的总数，那么操作系统会暂停一个进程，将其页面调出并且将其物理块分配给其他进程，防止出现抖动。

工作集大小可能小于窗口尺寸，实际应用中，操作系统可以统计进程的工作集大小，根据工作集大小给进程分配若干内存块。如:窗口尺寸为5，经过一段时间的监测发现某进程的工作集最大为3，那么说明该进程有很好的局部性，可以给这个进程分配3个以上的内存块即可满足进程的运行需要。
–般来说，驻留集大小不能小于工作集大小，否则进程运行过程中将频繁缺页。
拓展:基于局部性原理可知，进程在–段时间内访问的页面与不久之后会访问的页面是有相关性的。因此，可以根据进程近期访问的页面集合(工作集)来设计- -种页面置换算法- --选择-一个不在工作集中的页面进行淘汰。

外部碎片&内部碎片

• 在内存管理中，内部碎片是已经被分配出去的的内存空间大于请求所需的内存空间。
• 外部碎片是指还没有分配出去，但是由于大小太小而无法分配给申请空间的新进程的内存空间空闲块。
• 固定分区存在内部碎片，可变式分区分配会存在外部碎片；
• 页式虚拟存储系统存在内部碎片；段式虚拟存储系统，存在外部碎片
• 为了有效的利用内存，使内存产生更少的碎片，要对内存分页，内存以页为单位来使用，最后一页往往装不满，于是形成了内部碎片。
• 为了共享要分段，在段的换入换出时形成外部碎片，比如5K的段换出后，有一个4k的段进来放到原来5k的地方，于是形成1k的外部碎片。

参考：
1、 操作系统面试：内存管理
2、 操作系统
3、 操作系统理论知识
4、 强推！！写得很详细！！大部分来自于：操作系统-内存管理