操作系统（11）----内存管理2：https://developer.aliyun.com/article/1511164
•改进型的时钟置换算法
简单的时钟置换算法仅考虑到一个页面最近是否被访问过。事实上，如果被淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。只有被淘汰的页面被修改过时，才需要写回外存。所以如果能优先淘汰没有修改过的页面，就可以减少I/O操作的次数。
因此，除了考虑一个页面最近有没有被访问过之外，操作系统还应考虑页面有没有被修改过。在其他条件都相同时，应优先淘汰没有修改过的页面，避免I/O操作。这就是改进型的时钟置换算法的思想。修改位=0，表示页面没有被修改过；修改位=1，表示页面被修改过。
为方便讨论，用(访问位，修改位)的形式表示各页面状态。如(1，1)表示一个页面近期被访问过，
且被修改过。
算法规则：将所有可能被置换的页面排成一个循环队列
访问位为0，若修改位为0，即页面没有被修改过则优先淘汰，即（0，0）
所以淘汰顺序为（0，0）（0，1）
访问位为1，就是最近被访问过，不考虑淘汰，即（1，0）（1，1）
第一轮：从当前位置开始扫描到第一个(0,0)的用于替换。本轮扫描不修改任何标志位
第二轮：若第一轮扫描失败，则重新扫描，查找第一个(0,1)的帧用于替换。本轮将所有扫描过的帧访问位设为0
第三轮：若第二轮扫描失败，则重新扫描，查找第一个(0,0)的用于替换。本轮扫描不修改任何标志位
第四轮：若第三轮扫描失败，则重新扫描，查找第一个(0,1)的帧用于替换。
由于第二轮已将所有帧的访问位设为0，因此经过第三轮、第四轮扫描定会有一个帧被选中，因此改进型CLOCK置换算法选择一个淘汰页面最多会进行四轮扫描。
而简单型CLOCK置换算法最多只会进行两轮扫描。
通俗来讲，第一轮找（9，0），第二轮降低要求找（0，1），并且修改访问位为0，所以第三轮只有（0，1）或（0，0），第三轮试图找最先淘汰的（0，0），第四轮若没有找到（0，0），只能找第2位（次位）可以被淘汰的（0，1）
假设系统为进程分配了5个内存块，5个内存块被占满后，各个页面会用链接的方式形成循环队列：
只需要经过1轮扫描的情况：
第一轮扫描不需要修改任何标志位，只需要找到第一个（0，0）用于替换。就是下一个需要访问的页面替换掉此内存块中的页面。
进行两轮扫描：
假设此时内存块中页面状态如下：
第一轮扫描都不满足（0，0）这一状态，回到（1，1）
第二轮扫描会找第一个为（0，1）的页面，并且将访问过的帧访问位设为0。
，
进行3轮扫描：
第一轮找不到（0，0）这样的页面，所以进入第二轮扫描
第二轮扫描中，试图寻找（0，1），并且将访问过的页面的访问位由1变为0
没有找到（0，1），进行第三轮扫描，找到第一个（0，0）的页面，将此页面进行替换，即淘汰此页面
进行4轮扫描：
第一轮扫描需要找到（0，0）状态页面，不改变标志位
没有（0，0）页面，进行第二轮扫描，试图寻找（0，1），并且将访问过的页面的访问位由1变为0
没有找到（0，1），进行第三轮扫描，寻找（0，0）页面，并且不修改任何标志位
第三轮扫描无（0，0）页面，所以进行第四轮扫描，寻找（0，1）页面，并且替换该页面。
第一优先级：对应第一轮，最近没访问，且没修改的页面
第二优先级：对应第二轮，最近没访问，但修改过的页面
第三优先级：对应第三轮，最近访问过，但没修改的页面，也就访问位以前是1，修改位以前是0的页面（1，0），由于前一轮中，将所有扫描过的页面的访问位由1变为0，所以第三轮实际要找的是（0，0）
第四优先级：对应第四轮，最近访问过且修改过的页面（由于第2轮已经将所有扫描过的页面的访问位由1变为0，第三轮没有找到（0，0），所以到了第四轮找（0，1））。
这一算法（改进型CLOCK）开销小，性能较好。
四.内存空间的分配与回收
1.连续分配管理方式
连续分配是指为用户进程分配的必须是一个连续的内存空间。
（1）单一连续分配
在单一连续分配方式中，内存被分为系统区和用户区。系统区通常位于内存的低地址部分，用于存放操作系统相关数据；用户区用于存放用户进程相关数据。
内存中只能有一道用户程序，用户程序独占整个用户区空间。
优点:实现简单；无外部碎片；可以采用覆盖技术扩充内存;不一定需要采取内存保护(例如早期的PC操作系统 MS-DOS)
缺点:只能用于单用户、单任务的操作系统中；有内部碎片（分配给某进程的内存区域中，如果有些部分没有用上，就是"内部碎片"）；存储器利用率极低。
补充：
内部碎片是指分配给某进程的内存区域中，有些部分没有用上。
外部碎片是指内存中的某些空闲分区由于太小而难以利用。
如果内存中空闲空间的总和本来可以满足某进程的要求但由于进程需要的是一整块连续的内存空间，因此这些“碎片”不能满足进程的需求。可以通过紧凑(拼凑，Compaction)技术来解决外部碎片。如下图，采用紧凑技术，就可以运行进程1。
紧凑技术需要修改进程的起始地址，而起始地址存放在进程的PCB中，当进程上CPU运行时，会将进程的起始地址放到重定位寄存器（基址寄存器）中。
（2）固定分区分配
20世纪60年代出现了支持多道程序的系统，为了能在内存中装入多道程序，且这些程序之间又不会相互干扰，于是将整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业，这样就形成了最早的、最简单的一种可运行多道程序的内存管理方式。
① 分区大小相等
分区大小相等的缺点在于缺乏灵活性，若是一个小进程，但是由于分区大小相等，所以会占用相对较大的分区。若有一个较大的进程，系统分区的大小不能满足这一进程，那么这一进程就不能被装入系统中（或者说只能采用覆盖技术，在逻辑上拓展分区的大小）。
但是很适合用于用一台计算机控制多个相同对象的场合。
② 分区大小不等
分区大小不等是增加了灵活性，可以满足不同大小的进程需求。根据常在系统中运行的作业大小情况进行划分(比如:划分多个小分区、适量中等分区、少量大分区)
操作系统应如何记录各个分区分配的情况：
操作系统会建立一个数据结构一分区说明表，来实现各个分区的分配与回收。每个表项对应一个分区，通常按分区大小排列。每个表项包括对应分区的大小、起始地址、状态(是否已分配)。
当某用户程序要装入内存时，由操作系统内核程序根据用户程序大小检索该表从中找到一个能满足大小的、未分配的分区，将之分配给该程序，然后修改状态为“已分配”。
用数据结构的数组(或链表)即可表示这个表。
优点：实现简单，无外部碎片。
缺点：
•当用户程序太大时，可能所有的分区都不能满足需求，此时不得不采用覆盖技术来解决，但这又会降低性能；
•会产生内部碎片，内存利用率低。
（3）动态分区分配
动态分区分配又称为可变分区分配。这种分配方式不会预先划分内存分区，而是在进程装入内存时根据进程的大小动态地建立分区，并使分区的大小正好适合进程的需要。因此系统分区的大小和数目是可变的。(例如：假设某计算机内存大小为64MB，系统区8MB，用户区共56MB..)
注：动态分区的分配应该使用动态重定位的方式
系统要用什么样的数据结构记录内存使用情况？
1.空闲分区表
每个空闲分区对应一个表项。表项中包含分区号、分区大小、分区起始地址等信息。若没有在空闲分区表中的分区，那么就是已经被使用的分区。
2.空闲分区链
每个分区的起始部分和末尾部分分别设置前向指针和后向指针（即指向前面空闲分区的指针和指向后面空闲分区的指针）。起始部分处还可记录分区大小等信息
当很多个空闲分区都能满足需求时，应该选择哪个分区进行分配?
使用动态分区分配算法：
1.首次适应算法
每次都从低地址开始查找，找到第一个能满足大小的空闲分区。
如何实现：空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。
若进程5想要进入内存运行，那么使用首次适应算法，分配情况如下：
2.最佳适应算法
由于动态分区分配是一种连续分配方式，为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间，可以尽可能多地留下大片的空闲区即，优先使用更小的空闲区。
如何实现：空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区
表)，找到大小能满足要求的第一个空闲分区。
空闲分区由小到大依次递增链接。
若进程6（9MB）想要进入内存运行，那么就需要找到大小能满足要求的第一个空闲分区，即10MB的空闲分区。
最后空闲分区链也会做出改变，重新排列
缺点：每次都选最小的分区进行分配，会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片。
3.最坏适应算法
又称最大适应算法(Largest Fit)。为了解决最佳适应算法的问题--即留下太多难以利用的小碎片，可以在每次分配时优先使用最大的连续空闲区，这样分配后剩余的空闲区就不会太小，更方便使用。
如何实现：空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。
注：因为是递减链接，所以空闲分区中的第一个分区肯定是满足要求的，否则之后的分区更加满足不了分区大小的要求。
如图，空闲分区链递减排列：
若此时进程5（3MB）进入内存运行，则选择第一个空闲分区，并且修改相应的空闲分区链：
注：若修改后空闲分区的大小不是按照递减的方式排列，那么就需要重新进行排列
缺点：每次都选最大的分区进行分配，虽然可以让分配后留下的空闲区更大，更可用，但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达，就没有内存分区可用了。
4.邻近适应算法
首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区，而每次分配查找时，都要经过这些分区，因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索，就能解决上述问题。
如何实现：空闲分区以地址递增的顺序排列(可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表)，找到大小能满足要求的第一个空闲分区。
运行流程如下：
若进程5想要进入内存运行，那么从链头开始，6MB的分区满足条件，则进入6MB的分区
因为是按照地址递增的顺序进行排列，所以顺序是不用更换的。
若现在有进程6（5MB）进入内存空间，只需要从上一次结束的位置来时检索即可，就是1
可以观察到，若使用首次适应算法，那么会进行3次比较，而使用邻近适应算法，只需要进行2次比较。
但是，邻近适应算法也有不足：
首次适应算法每次都要从头查找，每次都需要检索低地址的小分区。但是这种规则也决定了当低地址部分有更小的分区可以满足需求时，会更有可能用到低地址部分的小分区，也会更有可能把高地址部分的大分区保留下来(最佳适应算法的优点)。
邻近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用，也就导致了高地址部分的大分区更可能被使用，划分为小分区，最后导致无大分区可用(最大适应算法的缺点)。
综合来看，四种算法中，首次适应算法的效果反而更好。
操作系统（11）----内存管理4：https://developer.aliyun.com/article/1511166
