第三章-内存管理

3.0 程序装入和链接

一、程序装入和链接

C程序执行过程：

• 编译：源程序编译后得到若干目标模块
• 链接：与库函数链接后形成完整装入模块（可执行文件）。可执行文件中的地址都是逻辑地址/相对地址
  • 静态链接：程序运行前就链接完全
  • 动态链接：边装入边链接，若发生外部事件，再链接需要的模块。动态链接库dll是PE文件（可执行文件）。优点是方便模块的修改和更新
• 装入（加载）：读取可执行文件头，确定代码段和数据段大小，创建一个足够大的内存空间，将可执行文件装入内存运行，要确定物理地址
  • 绝对装入：编译时就知道程序要装入内存的绝对地址，只适用于单道程序环境
  • 静态重定位装入：
    • 多道程序时，每个目标模块的起始地址从0开始，各地址均为相对地址
    • 每个作业内存连续，作业全部装入内存，不可移动
  • 动态重定位装入：
    • 程序可以移动，可以装入不连续的存储区，借助重定位寄存器（基址寄存器，作业的起始地址）动态申请内存。
    • 程序执行时，把逻辑地址转为物理地址

对于Java程序，首先被编译成Java字节码而不是汇编语言。为了可移植性，使用Java虚拟机JVM解释Java字节码文件，不同机器的Java虚拟机不同

2.逻辑地址空间和物理地址空间

• 编译后，每个目标模块从0开始编址，这是相对地址。
• 链接时，将每个模块顺序相连，构成从0开始的逻辑地址空间，相对地址->逻辑地址。
• 装入时，通过地址重定位，将逻辑地址转为物理地址，装入内存。

3.内存保护

重定位（基址）寄存器包含物理地址最小值，界地址寄存器包含逻辑地址最大值。逻辑地址先判断是否小于界地址寄存器内容，保证不越界，然后再加上基址，得到物理地址

3.1 内存管理概念

内存管理包括：内存空间的分配和回收，地址转换，扩充内存，存储保护

二、内存扩充：覆盖，交换技术

覆盖技术：解决进程放不进内存的问题

将用户空间分成固定区和若干覆盖区，进程中经常活跃的部分放入固定区，其余的部分按调用关系分段，把即将访问的段放入覆盖区，其他部分放在外存。

交换技术：将整个就绪态进程挂起，换出内存到外存；将准备运行的程序换入（中级调度）

三、连续分配管理方式

连续分配：为一个用户程序分配连续的内存空间

• 单一连续分配：内存中只有一道程序。无碎片，可采用覆盖技术，但只能单道程序
• 固定分区分配：
  • 将内存分成固定大小（大小可以相同）的若干区域，每个分区一道作业。
  • 程序小于空间大小时，会导致分区内部存在空间浪费，产生内部碎片
• 动态分区分配：
  • 动态建立分区，分区大小=进程大小
  • 随着旧进程的换出和新进程的换入，分区之间会产生外部碎片
  • 紧凑技术：操作系统不断对进程移动和调整，避免外部碎片
  • 回收时，若回收的块与空闲块相邻，需要合并

动态分区分配策略

• 首次适应算法(First Fit)：空闲分区以地址递增的次序链接，分配内存时顺序查找，通常效果最好
• 最佳适应算法(Best Fit)：空闲分区按照从小到大的次序链接，最后找到的总是大小最接近的空闲分区。但会产生最多的外部碎片
• 最坏适应算法：空闲分区按照从大到小的次序链接
• 邻近适应算法(Next Fit)：从上次查找结束的位置继续查找，没有查找开销

四、非连续分配管理方式

非连续分配只能动态重定位

1.基本分页存储管理

为了避免固定分区的内部碎片和动态分区的外部碎片，引入分页思想：把页作为主存的基本单位。

然而分页机制仍会产生内部碎片，即进程为最后一个不完整的块分配一整个页时，但内部碎片很小。

分页机制分为：

• 基本分页存储管理：程序全部放入内存
• 请求分页存储管理（虚拟内存）：程序部分进入内存，需要换入换出（这就叫请求机制）

逻辑地址：【虚页号|页内偏移】

• 如果计算机按字节编址，虚拟空间为$2^n$B，则逻辑地址就是n位
• 根据页面大小确定页内偏移位数

页表项：【虚页号|物理页号】

访存过程：首先根据页表基址+虚页号*页表项长度可找到页表项，页表项中的物理页号拼接上页内偏移就是物理地址

所有进程的PCB和页表都常驻内存。注意页表在内存的系统区

二级页表

逻辑地址：【一级页号|二级页号|页内偏移】

一级页表项：索引-【二级页表所在物理块号】

二级页表项：索引-【物理块号】

2.基本分段存储管理

为了让用户方便编程，将逻辑空间划分成不同段，存储不同逻辑的内容。如数据段，代码段，堆栈段等。

段内连续，段间不一定连续

逻辑地址：【段号|段内偏移】

段表项：【段号|段长|段基址】

每个进程都有一张段表，通过段基址+段内偏移得到物理地址

• 程序如何分段是在用户编程时决定的；
• 分段有利于动态链接；
• 因为在内存中直接划分出来段，所以只有外部碎片。只要是固定的分配就有内部碎片，其余的都会产生外部碎片

分段机制是二维地址结构，确定地址需要两个参数：因为段长不确定，所以需要告知段号和段内偏移位数，才能知道段内偏移到底是多少。而分页机制地址是一维的，因为页大小固定，知道页号剩下的就是页内偏移了。段页式也是二维。

共享段：

如果两个进程共享内存中的一个段S，则操作系统对这个段维护一张共享段表。共享段表包括使用该段的所有进程名，以及存取控制权限等。

由于两个进程有不同的段表，因此S的逻辑段号可能不同，但是对应段表项的段基址肯定相同。

3.段页式存储管理

既能反应程序的逻辑结构，又能提高内存利用率

逻辑地址：【段号|页号|页内偏移】

段号-段表项-页表基址-页表项-物理页号-物理地址

内部碎片，外部碎片都有

计算题：log页表数=页目录项数

3.2 虚拟内存管理

一、虚拟内存的基本概念

虚拟存储器：包括内存和作为虚拟内存的部分硬盘，将需要的页换入内存，不需要的页换出，好像给程序员提供了比实际大得多的内存

按需调页策略适用于有局部性原理（时间、空间）的场景

虚拟存储器需要的硬件支持：

• 内存和外存
• 页表
• 中断机构
• 地址变换机构

二、请求分页管理方式

请求分页系统：在基础分页系统之上，增加了请求调页、页面置换功能。只需把当前需要的部分页面装入内存

请求分页管理的页表项：【页号|物理块号|状态位|访问字段（次数）|修改位|外存地址】

• 先在快表（cache）中查需要的页表项，没有则查页表
• 若页表中该页表项有效位为0，则发生缺页，产生缺页中断（内部中断），请求操作系统将页调入内存
• 首先阻塞进程，然后看内存中有没有空闲块，若有则将需要的页从磁盘调入内存块中，并建立页表项到物理页的映射，然后再访问内存块
• 若没有，则淘汰内存的一页，换入需要的页

三、页面置换算法

选择哪个页用于换出

（1）最佳置换算法OPT：换出未来最长时间内不被访问的页面

（2）先进先出FIFO：可能会产生Belady现象，物理页数增大，缺页次数反增

（3）最近最久未使用LRU：

• 在页表项中增加一个访问字段LRU记录自上次访问以来的时间。
• 给进程分配k个物理页，则LRU位的长度是$\log_2k$位
• 需要硬件支持，来对所有的页进行排序，所以耗费高

（4）时钟置换算法CLOCK：页面在一个循环队列中，若进入内存就置访问位为1。需要替换时，系统查找访问位=0的页面换出，如果找到1，则置0，在后面继续找直到找到0

（5）改进型时钟置换算法：设置两个位（访问位u，修改位m），最多进行四轮扫描：

• 第一轮：找（0,0）用于置换，失败进入第二轮
• 第二轮：找（0,1）用于置换。所有扫描过的帧的访问位u设为0，即(1,0)变为(0,0), (1,1)变为(0,1)。失败进入第三轮
• 第三轮：找（0,0）用于置换。失败进入第四轮
• 第四轮：找（0,1）用于置换
• 因此页面淘汰顺序是(0,0)->(0,1)->(1,0)->(1,1)，先淘汰没访问过的，再淘汰访问过没修改过的，最后淘汰访问过修改过的

四、页面分配策略

驻留集大小

驻留集：os决定到底读多少页进入内存，即给特定的进程分配多少物理页（页框）

分配策略：【固定】指的是每个进程分配的物理页数一定，【局部】指的是一个进程缺页时只能把自己的页换出

• 固定分配局部置换：每个进程分配一定数目的物理页，只能换入换出自己的页
• 可变分配全局置换：每个进程物理块数不确定，os维护一个空闲块队列，按需分配
• 可变分配局部置换：前期每个进程块数固定，但若频繁换页，os为其分配物理块

没有固定分配全局置换！！因为每个进程的页面数是不变的，不能换入其他进程的页

调入页面的时机

预调页策略：预先将不久之后会访问的页面调入内存

请求调页策略：缺页时请求，系统将物理页调入内存

从何处调入页面

在具有对换功能的操作系统中，通常将外存分为文件区和对换区

文件区用于存放文件，对换区用于存放从内存换出的进程，对换区io速度更快

若对换区足够大，程序运行前，将文件从文件区复制到对换区；

否则，不会被修改的文件放在文件区，可能被修改的放入对换区

五、抖动现象

表现为：磁盘的繁忙率很高，CPU利用率很低

只有虚拟存储才会产生抖动现象。因为频繁访问的页面数>可用的物理页数，所以刚换出的页面又要换入（宏观的，不一定是紧邻的）。导致处理机一直在换页而不是执行进程

解决方法：撤销部分进程，减少需要交换的页面数量

六、工作集

某段时间内，进程要访问的页面集合，构成工作集窗口。

当前访问的前n页去重就是工作集

七、地址翻译的全过程

虚拟地址划分

页表项

TLB表项

物理地址划分

cache项

虚存大小问题

虚存大小<=内存+外存，否则没有足够的空间供虚存使用

虚存大小<=计算机地址位数能表示的最大容量（虚存理论上的上限，是决定因素）

如何确定使用几级页表：

先根据虚拟地址空间大小确定虚拟地址位数，从而划分虚拟地址为【虚页号|页内偏移】。

每页的页表项数=页大小/页表项大小，那么每级页表的索引需要log2(页表项数)位

虚页号长度/log(页表项数)就是需要的页表级数。P208(29)