内存管理基础
程序执行前处理
- 编译：编译程序将用户代码编译成若干个目标模块
- 链接：将编译后形成的一组目标模块，以及所需库函数链接在一起，形成完整装入模块
- 装入：将装入模块装入内存
常用链接方法
1.静态链接：在程序运行之前，将各目标模块及所需函数链接成为一个完整的装入模块，以后不再拆开
2.装入时动态链接：在装入内存时，将目标模块变装入边链接
3.运行时动态链接：在程序执行过程中，需要该目标模块时才进行链接
程序装入技术
地址装入需解决的问题
将逻辑空间映射到物理空间
常用程序装入技术
地址再定位技术：
- 将逻辑空间和物理内存空间对应起来的过程
- 地址在定位由操作系统中的装入程序来完成
常用程序装入技术：
- 绝对装入技术
- 可重定位装入技术
绝对装入技术
- 也称为固定地址再定位
- 程序地址再定位在执行之前被确定，也就是在编译链接时直接指定程序在执行时访问的实际存储器地址
- 程序地址空间和内存地址空间是一一对应的
可重定位装入技术
可执行文件中列出各个需要重定位的地址单元和相对地址值，装入时再根据所定位的内存地址去修改每个重定位地址项，添加相应偏移量
两种地址再定位方式：
- 静态再定位：装入程序在程序执行之前进行地址再定位，一旦地址定位完成后，程序执行期间不会发生变化
- 动态再定位：程序在装入内存时，不修改逻辑地址，在访问物理内存之前，再实时将逻辑地址转换成物理地址
存储管理
目的
- 充分利用内存
- 方便用户使用
- 解决程序空间比实际内存空间大的问题
- 存储保护与安全
- 共享与通信
- 实现的性能和代价
存储管理方案
- 连续内存分配方法：
- 单一连续存储管理
- 分区存储管理
- 离散内存分配方法
- 分页存储管理（分配单位是页）
- 段式存储管理（分配单位是段）
- 段页式存储管理
- 虚拟存储器
分区存储管理
基本概念
分为两种：固定分区分配和动态分区分配
基本思想
把内存分为大小相等或不等的分区，每个进程占用一个或几个分区；操作系统占用其中一个分区
特点
- 适用于多道程序系统和分时系统
- 支持多个程序并发执行
缺点
- 可能存在内碎片和外碎片
- 难以进行内存分区的共享
数据结构
分区表：一张全局表，记录有哪些内存块
固定分区存储管理
基本思想
内存划分为若干个固定大小的连续分区
优点
- 内存利用率提高
- 可以支持多道程序
- 实现简单
缺点
- 程序必须预先能估计要占用多大的内存空间
- 内碎片造成浪费
- 分区总数固定，限制了并发执行的程序数目
动态分区存储管理
基本原理
动态创建分区
优缺点
没有内碎片，存在外碎片
常用分区分配算法
- 最先适配算法
- 循环最先适配算法
- 最佳适配算法
- 最坏适配算法
存在问题
碎片问题，解决方法：紧凑技术
分区保护问题
- 界限寄存器
- 保护键
内存扩充技术
内存扩充
借助大容量辅存在逻辑上实现内存扩充，以解决内存容量不足的问题
- 覆盖技术
- 交换技术
交换技术
1.交换方式：
- 整体交换
- 交换以整个进程为单位，也称为进程交换
- 目的是解决内存紧张， 进一步提高内存利用率
- 部分交换
- 以分页、分段交换为基础，也称为页面交换、分段交换
- 目的是支持虚拟存储系统
2.优点：
- 增加并发运行的程序数目
- 给用户提供适当的响应时间
- 编写程序时不影响程序结构
3.缺点：换入和换出的控制增加处理机开销
页式存储管理
管理思路
1.划分用户空间：
- 把用户程序按逻辑页划分成大小相等的部分，称为页（虚页）
- 由系统自动完成，一般页大小为2的整数次幂
2.划分内存空间：
- 按页的大小划分为大小相等的区域，称为内存块（物理页面、页框、实页）
3.分配内存：以页为单位进行分配，并按任务页数多少来分配
数据结构
进程页表
- 系统为每个进程建立一个页表，页表给出逻辑页号和具体内存块号相应的关系
- 页表放在内存，属于进程的现场信息
物理页面表
- 整个系统有一个物理页面表，描述物理内存空间的分配使用状况
请求表
- 整个系统有一个请求表，描述各个进程页表位置和大小，也可结合到各进程PCB里
内存分配过程
- 计算一个任务所需的物理页面块数N
- 查位示图，看看是否还有N个空闲页面块
- 如果有足够空闲块，则页表长度设为N，可填入PCB中；申请页表区，把页表始址填入PCB
- 依次分配N个空闲块，将块号和页号填入页表
- 修改位示图
多级页表
多级页表的页目录表中每一项存的是页表的块号！页表的页表项存的是物理地址块号！
优势：1.可以使得页表在内存中离散存储。2.可以节省页表内存
硬件支持
- 页表始址寄存器
- 页表长度寄存器
- 联想寄存器——快表
评价
- 优点：
- 解决了碎片问题
- 便于管理
- 缺点：
- 不易实现程序共享
- 不便于动态连接
段式存储管理
引入目的
- 方便编程
- 信息共享
- 信息保护
- 动态增长
- …
管理思想
1.划分用户空间：
- 按程序自身逻辑关系划分为若干个程序段
- 每个程序段都有一个段名，且有一个短号
- 段号从0开始，每一段从0开始编址，段内地址是连续的
2.划分内存空间：
- 内存空间被动态的划分为若干个长度不相同的区域，这些区域被称为物理段
- 每个物理段由起始地址和长度确定
3.分配内存：
- 以段为单位分配内存，每一个段在内存中占据连续空间
- 各段之间可以不连续存放
存储管理
进程段表
- 记录了段号、段的首地址、段长度
- 每一个进程设置一个段表，放在内存，属于进程现场信息
系统段表
- 系统内所有占用段
空闲段表
- 记录空闲段起始地址和长度，可以结合到系统段表中
内存分配算法
首先适配，最佳适配…
硬件支持
- 段表始址寄存器
- 段表长度寄存器
- 联想寄存器
评价
- 优点
- 便于动态申请内存
- 管理和使用统一化
- 便于共享
- 便于动态链接
- 缺点：产生外碎片
段式页式存储管理
基本思想
- 进程空间：段式划分
- 内存空间：页式管理
- 页为单位进行分配
数据结构
- 段表
- 页表
- 空闲块管理同页式管理
- 内存分配同页式管理
虚拟内存管理
基本思想
工作过程
1.程序装入时：只需要将当前需要执行的部分页或段读入到内存
2.程序执行中：
- 待执行的指令或访问的数据不在内存（缺页或缺段），则处理器同志操作系统将相应的页或段调入到内存，然后继续执行程序
- 操作系统可将暂不使用的页或段调出保存在外存上，腾出空间存放将要装入的程序以及将要调入的页或段
引入益处
- 存放大的程序
- 提供大的用户空间
- 更多程序并发执行
- 易于开发
虚拟内存特征
1.不连续性：
- 物理内存分配的不连续性
- 虚拟地址空间使用的不连续性
2.部分交换
3.大空间：提供大范围的虚拟地址空间，其总容量不超过物理内存和外存交换区容量
虚拟存储技术
- 请求页式管理机制
- 请求段式管理机制
虚拟页式机制
工作原理
- 只在页面需要时，才将其载入内存
- 需要更少的输入输出
- 更小的内存
- 更多的用户
数据结构
页表结构：
- 采用两级或多级页表
- 为缩短查找时间，多级页表中的每级都可以装入到联想存储器中，并按照Cache原理进行更新
页面置换算法
- 先进先出算法（FIFO）
- 最佳算法（OPT）
- 最近最久未使用算法（LRU）
- 最不常用算法（LFU）
- 轮转算法（clock）
虚拟存储策略
调入策略
- 请求调页：只调入发生缺页时所需的页面
- 预调页：发生缺页需要调入某页时，一次调入该页以及相邻的几个页
页面调入来源
- 交换区
- 进程装入时，将全部页面复制到交换区，以后总是从交换区调入
- 调入速度快，要求交换区空间大
- 文件区
- 未被修改的页面，直接从文件去读入，被置换时不需调出
- 已被修改的页面，被置换时需调出到交换区，以后从交换区调入
调出策略
1.请求调出：同上
2.预调出
常驻集和工作集策略
常驻集
1.虚拟页式管理中给进程分配的物理页面数目
2.确定方式：
- 固定分配
- 可变分配
3.置换范围：
- 局部置换
- 全局置换
4.常驻集大小和置换范围的配合策略：
- 固定分配+局部置换
- 可变分配+局部置换
- 可变分配+全局置换
缺页中断
过程：
1.地址映射过程中，在页表中发现所要访问的页不在内存，则产生缺页中断。操作系统接到此中断信号后，就调出缺页中断处理程序，将该页从外存调入内存，使作业继续运行下去。
2.如果内存中有空闲块，则分配一页，将新调入页装入内存，并修改页表中相应页表项目的驻留位及相应的内存块号。
3.如果内存中没有空闲块，则页面置换。
