计算机操作系统(三)内存

3内存

3.1内存管理

3.1.1内存基础知识

3.1.1.1内存的基础知识

缓和CPU与硬盘直接的速度矛盾，程序运行在内存中被CPU处理

地址：编号
存储单元：地址对应的空间

2^10 = 1k 千
2^20 = 1M 兆，百万
2^30 = 1G 千兆，十亿

3.1.1.2内存管理的概念

• OS负责内存空间的分配与回收
• 提供从逻辑上对内存空间进行扩充
• 提供地址转换功能，负责程序的逻辑地址与物理地址的转换
• 提供内存保护功能，保证进程互不干扰

三种装入方式

• 绝对装入：编译时产生绝对地址
• 可重定位装入：装入时将逻辑地址转换为物理地址
• 动态运行时装入：运行时将逻辑地址转换为物理地址，需要重定位寄存器

内存保护方式：

• 设置一对上、下限寄存器
  • 存放进程的上、下限地址，访问地址时检测是否越界
• 重定位寄存器(基址寄存器)和界地址寄存器(限长寄存器)进行越界检查
  • 存放起始物理地址，最大逻辑地址

3.1.1.3进程的内存映像

• 0xFFFF FFFF
  • 1G操作系统内核区
• 0xC000 0000
  • 用户栈stack(向下增长)
  • 共享库的存储映射区
• 0x4000 0000
  • 堆heap(向上增长 有上限 0x4000 0000)
  • 读/写数据
• 0x0804 8000
  • 只读代码/数据
• 0x0000 0000

3.1.1.4覆盖与交换

覆盖技术

解决程序大小超过物理内存总和问题

将程序分为多个段

• 固定区：不被换出
• 覆盖区：需要用到时调入，不需要时调出
  必须程序员声明覆盖结构，对用户不透明，编程负担大

交换技术

内存紧张时，某些进程暂时换出到外存，某些具备运行条件的进程换入内存

中级调度(内存调度)

换出进程：挂起状态

• 就绪挂起
• 阻塞挂起

3.1.2内存分配

3.1.2.1连续分配管理方式

连续分配：为用户进程分配的必须是一个连续的内存空间

单一连续分配

内存分为系统区和用户
内存中只能有一道用户程序

优点：实现简单，无外部碎片，可以采用覆盖技术扩充内存，不一定需要内存保护

缺点：只能用于单用户、单任务OS，有内部碎片，存储器利用率极低

内部碎片：分配给进程的内存区域中，有没用上的部分

固定分区分配

用户空间划分为若干个固定大小的分区
每个分区中只装入一道作业

分区大小相等：缺乏灵活性，但适合用于一台计算机控制多个相同对象的场合

分区大小不相等：增加灵活性，可以满足不同大小的进程需求
根据常在系统中运行的作业大小情况进行划分

建立分区说明表管理分区
表项：大小、起始地址、状态(是否已分配)

优点：实现简单，无外部碎片
缺点：用户程序太大时，可能所有分区都不能满足，若用覆盖技术，会降低性能
会产生内部碎片，内存利用率低

动态分区分配

可变分区分配：不会预先划分内存分区，根据进程的大小动态建立分区

如何记录内存使用情况

• 空闲分区表
  • 包含空闲分区的表项
• 空闲分区链
  • 包含指向前后分区的指针

分配哪个

• 动态分区分配算法

如何分配与回收

• 修改表项/节点信息
• 增删表项/节点
• 合并相邻表象/节点

动态分区分配没有内部碎片，但是有外部碎片

外部碎片：内存中某些空闲分区太小，难以利用

可通过紧凑(拼凑) 技术解决外部碎片

3.1.2.2动态分区分配算法

首次适应算法

• 算法思想：
  • 每次从低地址开始查找，找到第一个能满足大小的空闲分区
• 如何实现：
  • 空闲分区以地址递增次序排列
  • 查找数据结构

最佳适应算法

• 算法思想：动态分区分配是一种连续分配方式
  • 分配的是一片连续的区域，于是保证大进程来时有连续大片空间
  • 优先使用更小的空闲区，尽可能多的留下大片的空闲区
• 如何实现
  • 按容量递增排序
  • 查找能满足要求的第一个空闲分区

缺点：每次都选择最小的分区，会造成很多外部碎片

最坏适应算法

最大适应算法

• 算法思想：
  • 为解决最佳适应算法，先用最大的连续空闲区
• 如何实现：
  • 按容量递减次序链接
  • 查找能满足要求的第一个空闲分区

缺点：导致大的连续分区被迅速用完
导致之后到来的大进程没有内存分区可用

邻近适应算法

• 算法思想：
  • 首次适应每次从链头开始查找，可能导致低地址出现很多较小分区
  • 每次查找经过这些分区，加大了查找开销
  • 于是每次从上次查找结束的位置开始检索
• 如何实现：
  • 从上次查找结束的位置开始查找
  • 不需要重排链表

首次适应的优点：能可能保留下大分区

邻近适应：可能导致无论低地址、高地址空闲区。都有相同的概率被使用
缺点：可能导致最后无大分区可用

最佳、最坏适应：需要重新排序，算法开销大
另外两个，开销小

3.1.3分页

3.1.3.1基本分页存储管理的概念

分页存储

分为大小相等的分区(页框)

将进程逻辑地址空间也分为与页框大小相等的一个个部分

OS以页框为单位为各个进程分配空间

页表

每个进程建立一张页表
通常存储在PCB中

页表项占多少字节
内存块大小/块大小=内存块个数
二进制位数最接近的字节(8bit)
页表项是块号，而不是块地址
页号可以用逻辑地址直接计算出，不占用空间

如何实现地址转换
进程在内存中连续存放
逻辑地址A对应的物理地址=页号对应的在内存中的起始地址+页内偏移量

如何确定页号、页内偏移量
页号=逻辑地址/页面长度
页内偏移量=逻辑地址%页面长度

若页面大小为2的整数幂
2^k 则 末尾k位是页内偏移量，其余部分是页号

逻辑地址结构

31...12|11...0
页号P   | 页内偏移量W

若有K为表示页内偏移量，则一个页大小为2^k个内存单元
若有m位表示页号，则一个进程最多允许有2^m个页面

若不是2的整数次幂，则只能慢慢算了

3.1.3.2基本地址变换机构

用于实现逻辑地址到物理地址转换的一组硬件机构

页表寄存器PTR
存放页表在内存中的起始地址F和页表长度M
进程未执行时，F和M在进程控制块PCB中
进程被调度时，OS会将其放到PTR中

• 根据逻辑地址计算出页号(P=A/L)、页内偏移量(W=A%L)
• 判断页号(b)是否越界
• 查询页表，找到页号对应的页表项，确定页面存放的内存块号
• 用内存块号和页内偏移量得到物理地址(E=b * L + W)
• 访问目标内存单元

页式管理中地址是一维的

各页表项会按连续存储在页面中
理论上，页表长度为3B即可表示内存块号的范围
但为了方便页表查询，通常会让页表项占更多字节
使得每个页面恰好可以装下整数个页表项

3.1.3.3具有快表的地址变换机构

快表：联想寄存器TLB
是一种访问速度比内存块的高速缓存
用来存放最近访问的页表项的副本
可以加快地址变换的速度

• 先与快表中所有页号比较
• 如果找到，则直接去除
• 否则，快表未命中，访问慢表(两次访问)
  • 找到页表项后，同时存入快表

查询快表比页表快很多，所以会节省很多时间
根据局部性原理，一般命中率高达90%以上

有的系统支持快表和慢表同时查找

3.1.3.4两级页表

单级页表存在的问题

问题一：

• 页表必须连续存放，因此页表很大时，需要占用很多个连续的页框
  问题二：
• 没有必要让整个页表常驻内存，因为进程在一段时间内可能只访问某几个特定的页框

可将页表进行分组，使每个内存块刚好可以放入一个分组

还要为离散分配的页表再建立一张页表
称为页目录表，或外层页表，顶层页表

两级页表的原理、地址结构

31...22|21...12|11...0
一级页号|二级页号|页内偏移量

• 按照地址结构将逻辑地址拆分成三部分
• 从PCB中读出页目录表起始地址
  • 根据一级页号查找页目录表
  • 找到下一级页表在内存中的存放位置

可以在需要访问页面是才把页面调入内存

注：各级页表的大小不能超过一个页面

• 两级页表的访存次数分析
  • 第一次 ：页目录表
  • 第二次：二级页表
  • 第三次：目标内存单元

3.1.4基本分段管理方式

与分页的最大区别：离散分配时分配的地址空间基本单位不同

分段

进程的地址空间：按照自身逻辑关系，划分为若干个段，每段从0开始编址

每段在内存总占据连续空间
但各段之间可以不相邻

由于按照功能逻辑划分，用户编程更方便，程序的可读性更高

31...16|15...0
端号|段内地址

段号的位数：决定每个进程最多可以分几个段
段内地址位数：决定了每个段的最大长度是多少

段表

为每个进程建立一张段映射表

每个段对应一个段表项：记录了段在内存中的起始位置

各个段表项的长度是相同的
段号可以隐含的，不占存储空间

段表寄存器：

• 段表始址F

• 段表长度M

• 根据逻辑地址得到段号、段内地址

• 判断段号是否越界

  • 段长度至少是1，段号从0开始

• 查询段表，找到对应的段表项

  • 段表项：段号、段长C、基址b
  • 段表项存放地址=F + S * 段表项长度

• 检查段内地址是否超过段长

  • 若超过，则产生越界中断

• 计算得到物理地址

• 访问目标内存单元

注：分页的页长固定，不需要对偏移量检查
段长度不固定，需要检查

分段、分页管理的对比

页：信息的物理单位，为了实现离散分配
对用户不可见
段：信息的逻辑单位，为了更好的满足用户需求
对用户可见

页大小由系统决定，段长度不固定

分页的地址空间是一维的
分段的地址空间的二维的

分段比分页更容易实现信息的共享和保护
只有纯代码(不可被修改的代码)/可重入代码可以被共享

3.1.5段页式管理方式

分页、分段的优缺点分析

• 分页
  • 优点
    • 空间利用率高
    • 不会产生外部碎片
    • 只有少量页内碎片
  • 缺点
    • 不方便按照逻辑模块实现信息的共享和保护
• 分段
  • 优点
    • 方便按照逻辑模块实现信息的共享和保护
  • 缺点
    • 如果段长过大，为其分配很大的连续空间会很不方便
    • 会产生外部碎片

段页式管理

将进程按照逻辑模块分段，再将各段分页

逻辑地址结构

31...16|15...12|11...0
段号|页号|页内偏移量

段号位数：每个进程最多可以分几个段
页号位数：每个段最大有多少页
页内偏移量：决定页面大小、内存块大小

表项：段号、页表长度、页表存放块号

一个进程对应一个段表，但可能对应多个页表

地址变换
先访问段表，再访问页表，然后找到块地址，拼接成物理地址

3.2虚拟内存

3.2.1虚拟内存的基本概念

传统存储管理方式的特征、缺点

很多暂时用不到的数据也会长期占用内存，导致内存利用率不高

一次性：作用必须一次性全部装入内存后才能开始运行

• 作业很大时，导致大作业无法运行
• 大量作业要求运行时，只有少量作业能运行，导致多道程序并发度下降

驻留性：作业一旦被装入内存，就会一直驻留内存中
因为程序有局部性，所以会驻留很多暂时用不到的数据，浪费了内存资源

局部性原理

时间局部性：短时间内执行过的指令可能会不久后再次执行

空间局部性：某个被访问的存储单元不久后附近的存储单元也会被访问到

虚拟内存的定义和特征

可以将程序中很快就会用到的部分装入内存
暂时用不到的部分留在外存
访问的信息不在内存时，OS将其调入内存

若内存不足，由OS负责将内存中暂时用不到的信息换出到外存

在OS管理下，用户感受到的内存比实际内存大得多：即虚拟内存

主要特征

• 多次性：作业允许被分成多次调入内存
• 对换性：允许在作业运行中，将作业换入换出
• 虚拟性：从逻辑上扩充了内存的容量

如何实现虚拟内存技术

需要建立在离散分配的内存管理方式基础上

与基本分页存储管理的区别：

• 访问信息不在内存时，OS负责调入内存
• 若空间不足，OS将内存中暂时用不到的信息换出
  所以需要
• 请求调页功能
• 页面置换功能

3.2.2请求分页管理方式

页表机制

请求分页存储管理的页表项

• 页号
• 内存块号
• 状态位：是否已调入内存
• 访问字段：可记录最近被访问过几次/上次访问时间
  • 供置换算法选择换出页面时参考
• 修改位：页面调入内存后是否被修改过
• 外存地址：页面在外存中的存放位置

缺页中断机构

每当要访问的页面不在内存时
产生缺页中断，OS的缺页中断处理程序处理中断

缺页进程阻塞，放入阻塞队列，调页完成后再将其唤醒，放回就绪队列

如果内存中有空闲块，则分配一个空闲块

若内存中没有空闲块，由页面置换算法选择一个页面淘汰
若该页面在内存期间被修改过，则将其写回外存
未修改过则不用写回外存

更新页表项

缺页中断属于内中断
一条指令可能产生多次缺页中断

地址变换机构

先查询快表，未命中则查询请求页表
若页面被换出外存，则快表中的相应表项也要被删除

注：只有写指令才需要修改 修改位

• 缺页中断处理和普通中断一样，需要保留CPU上下文
• 需要使用某种页面置换算法
• 换入/换出页面要启动慢速I/O操作，如果太频繁换出，会有很大开销
• 页面调入内存后，需要修改慢表，也要复制到快表

3.2.4页面置换算法

最佳置换算法OPT

每次选择淘汰的页面将是以后永不使用，或在最长时间内不再被访问的页面
这样可以保证最低的缺页率

预知未来算法，难绷

缺页时未必发生页面置换，若还有可用的空闲内存块，可以不用进行页面置换

缺页率=缺页次数/访问总数

最佳置换算法是无法实现的

先进先出置换算法FIFO

每次选择淘汰的页面是最早进入内存的页面

实现方法：队列，换出队列头页面、新页面插入队尾即可，队列长度为系统分配给进程多少内存块

Belady异常：当为进程分配的物理块数增大时，缺页次数不减反增的现象

只有FIFO算法会产生Belady异常
虽然实现简单，但是与实际运行规律不符，因此算法性能差

最近最久未使用置换算法LRU

每次淘汰的界面是最近最久未使用的页面

用访问字段记录该页面自上次被访问以来所经理的时间t

做题时：可以逆向扫描前面的访问页号
最后一个出现的页号就是要淘汰的页面

最接近最佳置换算法的
性能好，但是实现困难，开销大

时钟置换算法CLOCK

性能和开销较均衡的算法
CLOCK算法，或叫做最近未使用算法NRU

简单的CLOCK算法
每个页面设置一个访问位
将内存中所有页面通过链接指针链接成循环队列

• 当某页被访问时，访问位置1
• 淘汰页面时，检查访问位
  • 如果是0，则换出
  • 如果是1，则置0，暂时不换出，检查下一个
• 若第一轮扫描全是1，则会进行第二轮扫描(一定有0，所以最多扫描两轮)

改进型的时钟置换算法

简单的时钟置换算法：仅考虑一个界面最近是否被访问过
实际上，只有被淘汰的界面被修改过时，才需要写回内存

因此还要考虑页面是否被访问过
在其他条件都相同时，应优先淘汰没修改过的页面

(访问位, 修改位)
算法规则：循环队列
第一轮：找第一个(0,0)帧用于替换

• 不修改任何标志位

第二轮：若第一轮扫描失败，则重新扫描

• 查找第一个(0, 1)的帧用于替换
• 本轮，将所有扫描过的帧访问位设为0：(0, X)

第三轮：若第二轮失败，则重新扫描

• 查找第一个(0, 0)的帧用于替换
• 不修改任何标志位

第四轮：若第三轮失败，则重新扫描

• 查找第一个(0, 1)的帧用于替换

最多四轮

第一轮：找最近未被访问，且未被修改
第二轮：找最近未被访问，且被修改

• 置为0，因为未被访问的已经全都考虑过了
  第三轮：找最近被访问过(被置0了)，且未被修改
  第四轮：找最近被访问过(被置0了)，且被修改

3.2.5页面分配策略

页面分配、置换策略

驻留集：请求分页存储管理中，给进程分配的物理块的集合

• 虚存系统中，驻留集一般小于进程的总大小

驻留集太小，会导致缺页频繁，进程推进的时间少
驻留集太大，多道程序并发度下降，资源利用率低

固定分配：驻留集大小不变
可变分配：驻留集大小可变

局部置换：发生缺页时只能选进程自己的物理块置换
全局置换：可以将操作系统保留的空闲物理块分配给缺页进程，或者将别的进程的物理块置换到外存，再分给缺页进程

	局部置换	全局置换
固定分配	1	不存在
可变分配	2	3
全局置换一定会改变驻留集大小

固定分配，局部置换

• 缺点：很难在刚开始确定应该分配多少物理块才合适

可变分配，全局置换

• 选择未锁定的页面换出外存(有的界页面不能换出外存)
• 只要某进程发生缺页，就将会获得新的物理块
• 被选中进程的物理块会减少，缺页率会增加

可变分配，局部置换

• 若OS发现该进程频繁缺页，则多分配几个物理块
• 反正，缺页率特别低，可以适当减少物理块
• 根据发生缺页的频率动态增减物理块

何时调入页面

• 预调页策略：

  • 根据空间局部性，一次调入若干个可能比一次调入一个更高效
  • 可以预测不久后可能访问的页面，但是成功率只有50%
  • 主要用于进程首次调入
    运行前调入

• 请求调也策略：

  • 进程在运行期间发现缺页时才将所缺页面调入内存
  • 调入的页面一定会被访问到
  • 但每次只调入一页，每次调页都要磁盘I/O操作，I/O开销较大
  • 运行时调入

何处调入页面

外存(磁盘)

• 对换区：读写速度快，连续分配
• 文件区：读写速度慢，离散分配

若有足够的对换区空间，内存与对换区

若缺少足够对换区空间，凡是不会被修改的数据，直接从文件区调入

• 由于不会被修改，因此不必写回磁盘
• 可能被修改的部分，换出时需要写回磁盘对换区，下次需要时从对换区调入

UNIX方式

• 运行前进程有关数据全放在文件区
• 未使用过的页面：都可从文件区调入
• 使用过的页面需要换出：写回对换区，下次需要时从对换区调入

抖动(颠簸)现象

刚刚换出的页面马上又要换入内存/换出外存
这种频繁的页面调度行为：抖动

产生的主要原因：进程频繁访问的页面数目高于可用物理块数目(不够用)

工作集

工作集：某短时间间隔中，进程实际访问页面的集合
驻留集：请求分页存储管理中，给进程分配的内存块的集合

工作集大小可能小于窗口尺寸
OS可以统计工作集大小，据此分配若干内存块

一般，驻留集大小不能小于工作集大小，否则运行过程中将频繁缺页

基于局部性原理：可以选择在工作集之外的界面淘汰

3.2.6内存映射文件

OS向上层程序员提供的功能(系统调用)

• 方便程序员访问文件数据
• 方便多个进程共享一个文件

传统文件访问方式：

• open打开文件
• seek移动读写指针
• read从读写指针位置读入若干数据
• write将内存中指定数据写回磁盘

内存映射文件的访问方式：

• open打开文件
• mmap将文件映射到虚存地址空间
• 以访问内存的方式访问数据文件
• 文件数据读入、写出由OS自动完成(缺页，换页)
• 进程关闭文件时，OS自动将被修改的数据写回磁盘

多个进程可以映射同一文件，方便共享

优点：编程更简单，访问内存的方式读写即可

• 文件数据读入/写出完全由OS完成，I/O效率可由OS负责优化(预读/缓写出等)