分配回收

内存中哪里可以放？怎么选？怎么收回结束的进程？
传统的存储管理方式:

连续分配

分配区域内没有被进程使用的部分，称内部碎片
分配区域外没有进程能使用的部分，称外部碎片

单一连续分配
优点：没有外部碎片，可以不用内存保护，采用覆盖技术
缺点：(进程没用上的)内部碎片，仅能单用户，单任务，效率很低

固定分区分配
支持多道程序

分区大小相等：死板，适用于控制多个相同对象(工厂生产)
分区大小不等：灵活，按需划分
每个分区只装入一道作业，使用==分区说明表(按大小排列)==记录，进程找到第一个能满足大小的未分配分区，记得修改分区说明表的状态！

实现简单，外部碎片 $\times$
进程过大时装不下(可以使用"覆盖" 技术抢救一下)，但内部碎片 sqrt{} ​ 效率$\times$

动态分区分配
支持多道程序，又称为 可变分区分配 ：进程装入内存时根据进程大小动态地建立分区，分区大小和数量可变

数据结构：空闲分区表     和    空闲分区链表

表项的排列顺序和动态分区分配算法有关，分配后记得修改相应表项状态
回收时只要有相邻空闲区就会合并
内部碎片$\times$     外部碎片 sqrt{} ​
可以通过 紧凑(或拼凑，Compaction) 技术，“平移”进程块来解决外部碎片的问题

动态分区分配算法

非连续分配

支持多道程序的 固定分区分配 和 动态分区分配分别会产生内部碎片 和 外部碎片，“紧凑”算法代价很高----->内存分为分为多个大小相等的小分区，再按分区大小拆分进程，实现非连续内存空间存储，分区越小内部碎片越小

基本分页存储管理

内存
每个分区称为页框、页帧、内存块、物理块(多数4KB)
每个都有号码(页框号、页帧号、内存块号、物理块号)
进程
被分为与页框大小相等的页(或页面) ，物理单位
对应的号码为页号
访问过程

其中假设地址32bit，页面4KB=2¹²B，按字节寻址，逻辑地址

每个进程创建一张页表(慢表)

表项按页号顺序存储，每页可存$4KB=1365\times 3B+1B$
但为了方便查表，常使用4B存储一个表项(没有内部碎片1B)

两级页表
一个进程最大2²⁰个页面，页表大小 = 2²²B = 2¹⁰$\times$ 4KB，需要1024个连续的页框才能存下
局部性原理：一段时间内集中访问若干页面–>其他页面不用常驻内存
再分组：为离散分配的页表再建 “页目录表” (or 外层页表 or 顶层页表)

基本地址变换机构
逻辑地址 转换 物理地址 的一组硬件机构

快表
时间局部性:被执行的指令很可能再次被执行，被访问数据很可能再次被访问(循环指令)
空间局部性:被访问存储单元附近的单元很可能近期被访问(数组)
局部性原理 导致多次重复查询同一页号 + 高速缓冲寄存器(cache) = 快表 (TLB,Translation Lookaside Buffer)

命中则只需要“取数据”仅一次内存访问，未命中则需要"慢表查询”+“数据访问"两次内存访问
“快表”溢出需要用算法找出可以替换的页表项

基本分段存储管理

逻辑单位 进程地址划分为若干段(编译器:段名–> 基址)，每段占用一个连续空间，逻辑地址：

段表

同样可以使用"快表"

基本段页式存储管理

段页式管理 = 逻辑分段+每段分页 ，从而同时获取两种管理方式的优点

用户指定

系统根据段内地址分配 页号 与 页内地址 得到逻辑地址

段表

页表

三次内存访问，引入快表{段号；页号；物理地址}可以减少至一次

空间扩充

覆盖与交换

覆盖: (同一个进程中)程序按功能分段（模块）
用户必须指明覆盖的结构，增加用户负担

交换: (不同进程间)就是中级调度，换出空间需求大的进程，换入需求小的进程
由就绪态 转换为 就绪挂起时，PCB还是常驻内存中的
内存吃紧时，降低系统负荷，反映在缺页率上

虚拟内存

局部性原理 + 高速缓冲技术

实际容量=min(内存+外存，最大容量=2^{CPU寻址位数})
操作系统提供 请求调页/请求调段+页面置换/段置换 功能

请求分页存储管理

页表增加了页面状态的描述字段

表中有省略
被“挤出快表”(从快表中删除)的表项要在慢表中修改相应的表项
被”写“过的表项“修改位”变化，没被写过的表项“置换”时可以不用拷贝回外存
I/O操作慢，频繁置换开销很大

页面置换算法

挑选 “内存中暂时用不到的块” 换出到外存，好的算法缺页率低，磁盘I/O少
缺页率=$\frac{缺页次数}{总访问次数}$

最佳置换算法(Opt,Optimal)
淘汰最长时间内不会再使用的页面

7号页面之后出现时间最晚，被换出，其他类推
缺页率=$\frac{9}{20}$=45%
无法预知页面访问顺序无法实现，作为比较基准

先进先出置换算法(FIFO)
淘汰最早进入的页面

3号页面最早出现，被换出，其他类推
缺页率=$\frac{9}{12}$=75%
增加内存块数可能导致某些访问顺序( 如上 )会出现Belady异常(缺页率反而变大)
最先进入的通常为常驻块( 如main函数等 )
性能最差

最近最久未使用置换算法(LRU,least recently used)
淘汰最早开始没有被使用的已驻页面

7号页面最早开始没有被使用，被置换
缺页率=$\frac{6}{20}$=30%
性能最好，但开销大，需要硬件支持

时钟置换算法(CLOCK)
又称“最近未使用算法(NRU,Not Recently Used)”
被访问置1，需要置换时，(最多2圈)循环检查并置零访问位，淘汰访问位0的页面

改进型时钟置换算法
在时钟置换算法基础上，不改变修改位状态，访问位相同时优先淘汰没有被修改过的页面
未修改 = 不用回写磁盘 = 节省时间

第一轮：找(0,0) = {没访问，没修改}
第二轮：没找到(0,0)就找(0,1) = {没访问，有修改}，置0访问位
第三轮：没找到(0,1)就找(0,0) = {有访问，没修改}
第四轮：没找到(0,0)就第一个(0,1) = {有访问，有修改}
替换以上步骤找到的页面

性能最均衡

页面分配策略

驻留集：系统分配给进程的物理块集合(采用虚拟存储技术的系统 驻留集 < 进程大小)

固定分配局部置换：根据进程大小、优先级等参数确定驻留集
可变分配局部置换：根据缺页率动态调整驻留集大小，只能置换自己的页
可变分配全局置换：只要缺页一定得到新的物理块，先找空闲块，再找其他进程非核心(未锁)块

调入时机
1.预调页：= 空间局部性预测，或用户指定，主要用于首次调入(运行前调入)
2.请求调页 = 缺页 才 调页，磁盘IO开销大

调入源头

抖动(颠簸)：同一个页面频繁的换入换出内存
原因可能是驻留集不够，导致频繁访问的页面放不下，催生出了 = = 》
(Denning)工作集：某段时间内(窗口尺寸) 进程实际访问的页面集合
根据工作及调整驻留集大小(驻留集<工作集 便会抖动)，或置换驻留集中的非工作集页面

请求分段存储管理

请求段页式存储管理

地址转换

相对地址=逻辑地址
绝对地址=物理地址

寻址空间 = 2^{地址总线位}
寻址范围 = 0x00 ~ $\frac{内存大小}{字大小}$
按字节寻址
存储单元 = 1Byte = 8 bit =最小的编址
按字寻址
存储单元 = 1 Word = $\frac{(16/32/64)}{8}$ Byte

链接方式

得到完整的逻辑地址
静态链接
链接—>(.exe)—>装入—>内存
装入动态链接
(.obj)—>装入+链接–>内存
运行动态链接
运行时—>需要(.obj) or (.lib) —>链接—>内存
可以共享模块，易于修改

装入方式

地址的转换：逻辑地址—>物理地址
绝对装入
(.cpp){逻辑地址} —> 编译 —> (.obj){物理地址}
单道程序环境
静态重定位
又称 可重定位装入
(.cpp){逻辑地址} —> 编译 —> (.obj){逻辑地址} —> 装入 —> 内存{物理地址}
要求连续的全部内存空间，运行期间更不可移动！
多道批处理系统
动态重定位
又称 动态运行时装入
(.cpp){逻辑地址} —> 编译 —> (.obj){逻辑地址} —> 装入 —> 内存{逻辑地址} —> 执行时

允许进程移动，分配不连续存储区，可以共享程序段！！
现代操作系统

存储保护

保证进程互不干扰
方法一:cpu{上下限寄存器}
方法二:

最后

以上就是甜甜发带为你收集整理的计算机操作系统-内存管理分配回收空间扩充地址转换存储保护的全部内容，希望文章能够帮你解决计算机操作系统-内存管理分配回收空间扩充地址转换存储保护所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。