内存管理（第五、六章）

功能

内存空间的分配与回收

地址转换（地址映射）——逻辑地址转换为物理地址，实现内存的访问和管理

内存空间的扩充，即虚拟内存

存储保护

管理内存的方式

连续分配

单一连续分配

内存分为系统区和用户区

简单但内存利用率低

固定分区分配

分区划分有大小相等，也有大小不等

将分区大小进行排队

产生内碎片（不连续、零散的未被使用的小块内存）问题，造成内存浪费

动态分区分配

数据结构：动态分区表和动态分区链

分配算法：

基于顺序搜索的动态分区分配算法——

首次适应算法【空闲分区地址递增】

循环首次适应

最佳适应【空闲分区容量递增】

最坏适应【空闲分区容量递减】

基于索引搜索的动态分区分配算法——

快速适应算法

伙伴系统【二叉树】

哈希算法【哈希函数映射】

分区分配与回收：

分配内存

回收内存——

①回收区上面的分区是空闲分区->空闲区容量增大为原来空闲区和回收区的容量之和

②回收区下面的分区是空闲分区->空闲区和回收区合并的容量为新的空闲区的容量，新的空闲区在空闲链表中的地址使用之前回收区的地址

③回收区上下面的分区都是空闲分区->两个空闲区和回收区合并的容量为新的空闲区的容量，新的空闲区在空闲链表中的地址使用回收区上面的空闲区地址

④回收区上下面的分区都不是空闲分区->新建一个单独的地址节点存放到空闲链表中，大小为回收区的大小

动态重定位分区分配

紧凑-时间换空间的策略

离散分配

分页存储管理方式

单级分页

进程的虚拟地址空间被划分为相同大小的页，物理内存也被划分为相同大小的物理块（页框）

核心思想：虚拟地址（一维）映射到物理地址

逻辑地址分离成逻辑页号和页内偏移量

访问一个数据需要访存2次，快表（最近访存表）中需要访存1次

多级分页

每一个一级页表的每个表项对应一个区域，区域又分别包含一个二级页表，进一步映射到物理页

页表基址寄存器存放的是顶级页表的起始物理地址

※

※

没有外碎片，但有页内碎片

分段存储管理方式

段是一个逻辑上相关的内存区域，每个段都有自己的起始地址和长度以及属性

段表——二维表

逻辑地址——段号+段内偏移量，二维地址

地址变换机构

优点：方便编程、信息共享、信息保护、动态链接、动态增长

外部碎片

段页式存储管理方式

段中分页——段表，段内页表

逻辑地址——段号+段内页号+页内偏移量

产生内碎片

地址变换机构

※

碎片：分段无内碎片

扩充内存

多道程序环境下逻辑扩充内存的方法

覆盖

划分模块

大型程序，不需要内存支持，但程序设计复杂

对换/交换

暂时移到磁盘或其他存储介质

内存不足的情况下

性能开销

虚拟内存管理

虚拟存储器：请求调入功能和置换功能，容量=内存+外存，运行速度->内存运行速度，每位成本->外存

局部性原理：时间局部性，空间局部性

特征：多次性（对应传统的一次性）（多次调入内存）、对换性（对应传统的驻留性）、虚拟性

※作业在运行前，不必全部装入内存，且运行过程中也不必一直驻留内存

管理内存方式：

请求分页管理方式——

请求调页功能、

页表、

缺页中断机构、

地址变换机构、

内存分配【页面分配策略：固定分配，局部置换；固定分配，全局置换；可变分配，局部置换。物理块分配算法：平均分配算法，按比例分配算法，考虑优先权算法】、

页面调入策略、【何时：预调页策略、请求调页策略。何处：文件区、对换区。缺页率】

页面置换功能【最佳置换算法（无法实现），先进先出页面置换算法（会有Belady现象），最近最久未用页面置换算法LRU，最少适用页面置换算法（最先淘汰被修改且没访问的页面），Clock时钟页面置换算法（淘汰最近未用的页面）】

调入页面的时机【预调页策略、请求调页策略】

异常：抖动

※发生抖动时，可以采取的有效策略：撤销部分进程

※

请求分段管理方式

虚拟容量：

最大不超过计算机的地址位数

内存和外存的容量之和