计算机操作系统笔记总结

四、存储器管理

1、对用户程序处理步骤

1. 编译 ：把源代码编译成模块
2. 链接 ：对模块和库函数进行链接
3. 装入 ：装入内存

1.1、内存装入

1.1.1、绝对装入（单道环境）

生成绝对地址（物理地址），程序就放到内存这个绝对地址上。

地址确定方法：

• 程序员直接使用绝对地址
• 程序员使用符号地址，编译时转换成绝对地址

1.1.2、可重定位装入方式（静态重定位）

目标模块起始地址都从0开始，其它地址都相对于起始地址计算。这个地址叫逻辑地址。

重定位: 装入时对目标模块逻辑地址修改的过程。

静态重定位: 装入时修改地址，之后就不再修改。

• 静态重定位不允许程序运行时在内存移动

重定位时，每个地址都加10000，

1.1.3、动态运行时装入方式

1. 装入时逻辑地址不变，装入内存的模块全采用逻辑地址

2. 运行时才地址转换

3. 需要硬件重定位寄存器支持

4. 运行程序在内存中移动

1.2、链接方式

1. 静态链接
2. 装入时动态链接
3. 运行时动态链接

1.2.1、静态链接

运行前链接。

1、链接时解决的问题

• 对相对地址进行修改
• 变换外部调用符号

1.2.2、装入时动态链接方式

采用边装入边链接的链接方式。

优点：

• 便于修改和更新
• 便于实现对目标模块的共享。（可以将一个模块链接到几个应用程序模块上）

一般很少采用

1.2.3、运行时动态链接方式

例如

• Window 里面的 .dll文件
• Linux 里面的 .so文件

1、运行的时候才装入，用到的时候才装入，不用不装入

优点;

• 加快装入过程
• 节省内存

2、连续内存分配

2.1、程序在内存中连续分配。

1.2、单一连续分配

1. 用于单道程序环境
2. 内存分为系统区和用户区
3. 用户区仅能装入一道用户程序，程序独占整个空间

1.3、固定分区分配

1. 用户空间划分若干固定大小区域，每个分区装入一道作业
2. 用于早年的多道程序

缺点：易造成存储空间浪费。 （小的作业占用了很大的区，区内没占用的内存就浪费掉了）

1.4、动态分区分配（可变分区分配）

• 根据进程实际需要，动态分配

1、由数据结构管理空闲分区与非空闲分区

1. 空闲分区表
2. 空闲分区链 （也就是双向链表）

1.4.1、内存分配过程

1. 检索空闲分区表（链）
2. 如果检索完发现，没有符合的分区，那么程序就会堵塞掉。
3. 否则，就把检索到的分区，分配给程序，这个分区内空闲的内存，会形成新的空闲内存，加入到空闲分区表（链）中。

1.4.1、内存分区内存回收

分4种情况

根据回收区首地址，从空闲区链表找到插入点

1. 回收区与插入点前一个空闲区相邻接，回收区与前一个合并
2. 回收区与插入点后一个空闲区相邻接，回收区与后一个合并
3. 回收区与插入点同时与前一个空闲区和后一个空闲区都相邻接，那么这三个区合并
4. 回收区与插入点前一个空闲区和后一个空闲区都不邻接，回收区作为独立的一个，加入链表

1.4.2、两类分配算法：

1.4.2.1、顺序式搜索算法

2.1.1、首次适用法

以地址递增次序链接，从链首开始顺序查找，直到找到大小满足要求的一个空闲分区。

若找不到，内存分配失败。

特点;

1. 优先使用地址内存，保留高地址空闲区
2. 容易产生碎片
3. 检索速度慢

2.1.2、循环首次算法

从上次找到的空闲分区的下个分区开始查找。

特点：

1. 碎片减少
2. 缩短查找时间
3. 缺乏空的大的分区

2.2.3、最佳适应算法

分配满足要求且最小的空闲分区。

空闲分区按容量从小到大的排序

2.2.4、最坏适应算法

总是挑选最大的空闲分区

空闲区按照从大到小排序

特点;

1. 碎片少，对中小作业有利
2. 查找效率高
3. 缺乏大空间分区

1.4.2.2、索引式搜索算法

2.2.1、快速适应算法（分类搜索法）

系统有多个空闲分区链，每类相同容量分区单独设立一个分区链。

内存中设立一个管理索引表，每个索引表对应一个分区链

• 根据程序大小，在适合的分区链中匹配。

2.2.2、伙伴系统

规定所有分区大小均以2的K次幂。

相同大小空闲区单独设立一个双向链表。

• 内存分配时，匹配与程序相同或者大于程序的分区。
• 若大于程序，则需要把分区内多余的内存分离出来。

2.2.3、哈希算法

通过构造哈希函数（传入所需空闲大小为参数），来计算符合的分区。

3、紧凑（或拼接）

通过移动内存作业，把多个分散小空闲分区拼接大分区。

1.5、动态可重定位分区分配

动态运行时装入方式，装入内存的所有地址仍是相对地址，运行时才转换为绝对地址。

增设重定位寄存器，存放程序在内存中的起始地址

• 与动态分区分配一样，只是增加了紧凑的功能

3、离散分配内存

1、基本概念

1.1、页面的概念

内存划分成多个小单元，每个单元K大小，称为块。

作业也按照K单位划分成片，称为页面。

• 页面大小要适中。
• 物理划分块的大小=逻辑划分的页的大小。

1.2、页表的概念

为了找到被离散分配到内存的作业，记录每个作业各页映射到哪个物理块，形成的页面映射表，简称页表。

• 页表存放在内存中
• 页表首地址和页表长度存放在PCB中
• 页表寄存器PTR，

1.3、计算页号和页内地址

1.4、地址变换机构

实现逻辑地址到物理地址的转换

1.5、快表

1. 基本分页系统存取一个数据要两次访问内存。
2. 快表，联想寄存器或TLB，具有并行查找能力的特殊高速缓冲寄存器。
3. 快表用于缓冲页表中经常访问的页表项。

1. 快表同时与所有页号比较。
2. 首先找快表，若快表中没有，才去普通表中找。
3. 快表命中率越高，速度越快。

1.6、访问内存有效时间EAT

从发出逻辑地址访问请求开始到访问实际物理地址单元取出数据，所花费的总时间。

1.7、页表占用空间问题

1. 页表空间采用分散分配
2. 部分页表调入内存，其它部分在磁盘，需要时调入

1.8、两级页表

将内页表分页，为页表再建立一张页表（外层页表），该页表项记录内页表的内存首地址。

需要增设一个外页表寄存器

对于32位机器适合

1.9、多级页表

64位机器适合多级页表。3级页表适合。

1.10、反置页表（倒排页表）

整个系统一个页表，每个物理块设置一个表项，并按物理块编号排序，内容为进程标识及其逻辑页号。

地址变换

1. 根据进程标识符和页号，去检索反置页表
2. 若检索到，用物理块好及页内位移访问数据
3. 若未检索到，则此页未装入内存，产生缺页中断再调入或报错

2、分段式存储器管理

1、概念 ：把程序划分成多个段。（由编译程序，把程序划分层很多段）

• 用户地址空间划分为若干个段。
• 每个段都有名字（段号）和长度，都从0开始编址，采用连续分配
• 程序地址空间划分为多个段，各个段长度不相等。

2、段表

每个进程一张段映射表，简称段表。

3、地址变换机构

系统设置一个段表寄存器，用于存放段表始地址和段表长度。

4、优点

方便信息共享、保护、动态增长、动态链接。

3、分段与分页的区别

4、段页式存储管理

1、基本原理

• 先将用户程序划分成若干段，每个段再分成若干页。
• 地址结构由段号，段内页号及页内地址三部分组成。
• 一个进程有一张段表和多张页表

一次需要访问3次内存，速度变慢了。

4、虚拟存储

1、虚拟存储器（VM）

从逻辑上实现内存扩充功能

2、传统存储器管理方式

• 一次性：把程序全部放入内存
• 驻留性：堵塞态也占内存，部分程序根本用不上。

3、程序局部性

程序运行存在局部性现象

• 时间局部性：存在大量循环
• 空间局部性：程序顺序执行，数组访问等

4、VM工作原理

1. 根据局部性原理，只装入部分程序就开始运行，其余在硬盘
2. 若访问的页（段）不在内存，产生缺页（段）中断
3. 由os请求调页功能调入内存再运行
4. 若内存满则置换再调入

5、虚拟存储器特征

• 多次性：传统存储器是一次性，VM多次调用
• 对换性：传统存储器是常驻性，VM多次对换
• 虚拟性：从逻辑上扩充容量，运行更大程序

所有虚拟存储器都是离散式分配。

6、实现方法

• 分页请求系统（页式虚拟存储器）
• 分段请求系统（段式虚拟存储器）
• 段页式虚拟存储器

大多数CPU集成有实现虚拟存储器功能的硬件，称为MMU

7、分页请求系统

在分页系统的基础上增加请求调页和页面置换功能的页式VM

a、页表增加四个表项：

1. 状态位P：指示是否在内存中（0,1）
2. 访问字段A：访问次数或者未访问时间，供置换算法参考
3. 修改位M，是否修改过，供页面置换时参考
4. 外存地址：

b、缺页中断机构

与常规中断不同之处：

1. 在指令执行期间产生和处理缺页中断信号。（中断产生必须执行中断）
2. 一条指令执行期间可能产生多次缺页中断。

c、最小物理块数确定

概念：能保证进程正常运行所需的最小物理块数。

能满足最复杂的指令所需的页面数。

d、内存分配策略

1、固定分配局部置换策略

• 固定分配，进程物理块数固定
• 局部置换，缺页时只从该进程页面选择一页换出
• 进程物理块数根据进程类型或程序员，管理员建议确定

2、可变分配全局置换策略

• 可变分配，先确定一定数目物理块，运行期间可增减
• 全局置换，缺页时从整个系统空闲物理块分配或者所有进程页面选择一页换出

3、可变分配局部分配策略

• 可变分配，先确定一定数目物理块，运行期间可增减
• 局部置换，缺页时只从该进程页面选择一页换出

e、物理块分配算法

1、平均分配算法：所有进程平均分配

2、按比例分配算法：

f、调入页面

1、预调页策略

以预测为基础，将那些预计不久就会访问的页面预先调入。

2、请求调页策略

发生缺页中断时调入，开销大，IO频繁

g、从哪里调入

外存分为：文件区（离散分配），对换区（连续分配）

• 未修改文件，从文件区调
• 修改过的文件，从对换区

h、页面调入过程

1. 页面不在内存，发出缺页中断
2. 中断机构保留现场
3. 根据页表项找到外存地址
4. 若内存有空闲页，启动IO调入，修改页表和快表
5. 若内存满，按照置换算法换出一页，再调入，修改页表快表
6. 根据修改后的页表访问调入页

i、缺页率

j、页面置换算法

1、最佳置换算法（理论上可以实现）

把以后不再使用或者以后很长时间不再使用的置换出去。

2、先进先出页面置换算法（很少使用）

把最先进来的页面置换出去。

3、最近最久未使用算法（LRU）算法（需要较多硬件支持）

置换最近最久未使用的页面

4、最少使用算法（LFU）

置换在最近时期使用次数最少的页面。

5、简单的CLOCK算法

1. 为每页设置一访问位，将所有内存页面链接成一个循环队列
2. 页面访问时访问位置为1
3. 若为0则淘汰，若为1则置0再给一次机会。

6、改进型CLOCK算法

选择未使用过且未修改过的页面，设访问位A修改位M：

AM四种取值情况 00,01,10,11

1. 从头寻找AM=00页面，找到淘汰
2. 没找到，找01的页面，找到淘汰
3. 没找到，把所有A变成0，
4. 从头找00页面，找到淘汰
5. 没找到，找01页面，找到淘汰

l、影响页面换进换出的因素

1. 页面置换算法
2. 写回磁盘的频率
3. 读入内存的频率

m、页面缓冲算法（PBA）

• 可变分配局部置换
• 空闲页面链表 （放被置换出来的页面）
• 修改页面链表

n、访问内存的有效时间

8、分段请求系统

在分段系统的基础上增加请求调段和分段置换功能的段式VM

参考文献
B站 计算机操作系统（第四版）西安科技