chanong 内存管理功能：
逻辑地址和物理地址
内存分配管理方法
分为连续分配管理法和间断分配管理法。
1 持续分配管理方法
为用户程序分配连续的内存空间。 主要包括单个连续分配/固定分区分配/动态分区分配。 会产生大量的内存碎片。
动态分区分配算法（主要数据结构是空闲分区表和空闲分区链）
1）基于顺序搜索的动态分区分配（适合不太大的系统）
(1) 第一次适配
空闲分区链表要求按照地址递增顺序链接。 每次分配内存时，都会从链的开头开始顺序查找，直到找到第一个大小满足要求的空闲分区。
缺点：会产生大量难以使用的、小的空闲分区，即碎片。 而且每次查找都是从最低地址开始依次进行，这增加了查询开销。
优点：优先使用内存低地址部分的空闲分区，高地址部分预留较大的空闲区域，为以后处理大型作业提供方便。
(2) 第一次适应循环
这是一种改进的首次适应方式。 每次搜索从最后找到的空闲分区之后的下一个空闲分区开始，直到找到满意的空闲分区。 并采用循环搜索的方法。
优点：均匀分布空闲内存区域，从而减少寻找空分区的成本
缺点：缺乏大的可用分区。
(3) 最佳适应
每次分配内存时，总是将满足空间要求的最小空闲分区分配给用户程序。 这就需要所有的空闲分区按照容量从小到大的顺序形成一个空闲分区链表。
优点：第一次找到的满足空间要求的空闲分区一定是最好的。
缺点：会产生大量难以使用的碎片。
(4) 最差适应
每次分配内存时，总是选择最大的空闲分区，并将一部分存储空间分配给用户程序。 这就需要所有的空闲分区按照容量从大到小的顺序形成一个空闲分区链表。
优点：剩余空闲分区不会太小，内存碎片的可能性降到最低，有利于中小型操作。
缺点：内存中缺乏大的空闲分区。
2）基于索引的动态分区算法（适合内存分区较多且对应空闲分区链表较长的比较大的系统）
(1)快速自适应算法
将空闲分区按照容量进行分类，并为每一类中所有相同容量的空闲分区建立一个单独的空闲分区链表。 内存中建立管理索引表。 每个索引项对应一个空闲分区类型，记录了指向空闲分区链表头的指针。
优点：分配空闲分区时，不会划分任何分区，因此可以保留大分区，不会产生内存碎片，查找效率高。
缺点：为了有效地合并区间，分区返回主存时算法复杂，系统开销较高。
（二）合伙人制度
(3)哈希算法
利用哈希快速搜索的优点，建立哈希函数，以空闲分区的大小为键构造哈希表。 表中的每个条目记录了对应的空闲分区链表的头指针。 进行分区分配时，根据需要的空闲分区大小，通过哈希函数计算在哈希表中的位置，快速找到对应的空闲分区链表。
2 非连续分配管理方法
非连续分配管理允许程序以分布式方式加载到不相邻的内存分区中。 根据分区大小是否固定分为分页存储管理和分段存储管理。 后来出现了分段页存储管理方式。
1）分页存储管理
将用户程序的地址空间划分为若干个固定大小的区域，即页或页。 同时，内存空间被划分为若干物理块，物理块的大小与页大小相同。 这样，用户程序的任意页都可以放置在任意物理块中，实现非连续分配/离散分配。
2）分段存储管理
为了满足用户的要求，存储管理方法将用户程序的地址空间划分为若干不同大小的段。 每个段都可以定义一组相对完整的信息。 分配内存时，以段为单位。 它在内存中也可能是不连续的。
分段存储适用于信息保护/信息共享/动态链接。
逻辑地址由段号和段内的偏移量指定。
3）段页存储管理
虚拟内存管理
虚拟内存的实现 1）请求分页存储管理
2）请求分段存储管理 3）请求分段页存储管理
替换算法（1）最佳替换算法
它选择淘汰的页面将来永远不会被使用，或者在很长一段时间内不会被访问。 这确保了最低的页面错误率。 然而，由于无法预测某个进程的几个页面中的哪一个将来不会被访问，因此该算法无法实现。 但它可以用来评估其他算法。
(2)先进先出页面替换算法(FIFO)
最先进入内存的页总是被淘汰，即选择在内存中驻留时间最长的页进行淘汰。
实现比较简单。 只需要按照进程已调入内存的页面顺序组成一个队列，并始终消除队列中的第一个页面。
缺点：不适合进程的实际运行规则，因为进程中可能会频繁访问某些页面。 并且可能会出现异常（当分配的物理块数量增加时，页面错误的数量反而增加）。
（3）最近未使用的算法（LRU）
始终选择最近使用的页面进行替换。
实现算法的硬件支持：寄存器或堆栈
1）注册
存储器中的每一页都配置一个移位寄存器。 当进程访问一个物理块时，将相应寄存器的高位设置为1，然后每隔一段时间将寄存器右移一位。 如果将n位寄存器视为整数，则具有最小整数值的页是最近未使用的页。
2）堆栈
使用堆栈来保存当前使用的每个页面的页码。 每当进程访问某个页面时，该页号就会从堆栈中删除并推入堆栈顶部。 因此，栈顶始终是最近访问的页的页号，栈底是最近未使用的页的页号。
(4) 最少使用替换算法(LFU)
为每个页面设置一个移位寄存器，记录该页面被访问的频率。 该算法总是选择最近一段时间内使用最少的页面作为驱逐页面。
每当访问一页时，将寄存器的最高位设置为1，然后每隔一段时间将寄存器右移一位，这样就将最近一段时间最少使用的页作为当前页。寄存器中所有位中 1 数量最少的页。
(5) CLOCK 替换算法 1) 简单的 CLOCK 替换算法
为每个页面设置一个访问位，然后通过链接指针将内存中的所有页面链接成循环队列。 当访问某个页时，其访问位置为1。选择淘汰页时，请检查该页的访问位。 如果是0，则交换掉。 否则设置为0，暂时不换出，按照先进先出算法检查下一页。
只需交换最近未使用的页面即可。
2）改进CLOCK替换算法
抖动
好友系统
(1)将空闲页分为m组。 第一组存储2^0个单元的页面，第二组存储2^1个单元的页面，第m组存储2^(m-1)个页面。 单位页
m最大为11，页一般为4K，所以内存块最大为4M。
(2) 每组都是一个链表，用于连接大小相等的内存块。
(3)好友块的大小相同，第一和第二块是好友块，第三和第四块是好友块。 比喻。
内存分配
如果请求的内存大小为n，则将n向上舍入到2的2次方，则需要分配一个大小为s的内存块并将其定位到相应的组中。
1. 如果数组中还有剩余内存块，则分配它们。
2、如果没有剩余的内存块，则沿着数组向上查找，然后将内存块分成s个，将剩余的内存块放入相应大小的组中。
内存回收
当用户用完内存后，会归还，然后根据内存块的实际大小（向上取整到2的幂）将其纳入链表中。 在被纳入之前，
1.我们还需要检查他的伙伴的内存块是否空闲。
2. 如果它们是空闲的，则将它们合并在一起。 合并后，转到步骤1继续执行。
3.如果不空闲，则直接添加到链表中。
微信扫一扫打赏
支付宝扫一扫打赏
