OS-3.1 内存
3.1 内存
1.内存的基础知识
内存有什么用？
程序从硬盘调入内存，被CPU处理。
如何区分内存中的多个程序放置的位置呢？ →需要对内存进行编址。
从写程序 到 程序运行
编写源代码 –→
编译（高级语言（高级代码）到机器语言（机器指令）–→
链接（把code连接到一起，加上库函数，且形成逻辑地址）–→
装入（装入内存，形成物理地址）
链接的三种方式
- 静态链接：程序运行前一次性链接，之后不拆开。
- 装入时动态链接：边装入内存边链接。
- 运行时动态链接：程序运行时才链接。（便于修改和更新，便于实现对目标模块的共享）
机器指令的工作原理
结构：操作码+若干参数（可能包含地址参数）
指令告诉CPU从哪个地址读/写数据。
或者告诉CPU对数据进行什么处理。
物理地址 VS 逻辑地址
程序经过编译、链接后生成的指令中指明的地址是逻辑地址。
HOW 逻辑地址→物理地址
（代码中的）逻辑地址→（内存中的）物理地址
==绝对装入==
==可重定位装入（静态重定位）==
==动态运行时装入（动态重定位）==
绝对装入：
编程阶段就把物理地址计算好。
只适用于单道程序环境。（灵活性低，不可迁移）
静态重定位：
在装入时 一次完成 逻辑地址转为物理地址。
进程装入内存时，分配进程要求的全部连续地址空间。
进程一旦进入内存，就不可以移动位置了。
动态重定位：
系统只有一个==重定位寄存器==，保存存入模块存放的（物理）起始位置（又叫基址寄存器）。
【==物理地址===重定位寄存器的值+逻辑地址，==这一步就是硬件地址变化机构做的==】
在程序真正要执行的时候才进行，逻辑地址转物理地址。
只装入部分代码，根据需要动态调入调出内存。
允许程序在内存中发生移动。
回顾
2.内存管理的概念⭐
os负责：
- ①内存空间的分配与回收
- ②内存空间的扩充
- ③地址转换
- ④存储保护
①OS负责：对内存空间的分配与回收（连续分配和非连续分配方式）
②OS负责：对内存空间的扩展（覆盖，交换和虚拟内存技术）
③OS负责：提供地址转换功能，程序的逻辑地址与物理地址之间的转换。（三种装入方式）
④OS负责：提供内存保护功能。（保证各自进程在自己的空间运行，不会越界访问）
重定位寄存器保存该模块在内存中的起始位置（物理），
界地址寄存器保存进程的最大逻辑地址。
回顾
3.进程的内存映像
进程的都是虚址，实址。（eg malloc分配的）
②内存扩展 – 覆盖与交换
虚拟存储技术（之后学到）
覆盖技术
交换技术
覆盖技术
把程序分成多个段。
把内存分为一个固定区和多个覆盖区
常用的段放在固定区，调入之后不再调出。
不常用的段放在覆盖区，需要时调入内存，不需要时调出内存。
必须由程序员实现，对用户不透明，增加编程负担。
交换技术
进程在内存和磁盘之间动态调度。
when内存空间紧张时，系统将内存中的某些进程暂时调出外存，把外存中已具备条件的进程换入内存。
- Note：中级调度，就是决定把哪一个处于挂起状态的进程重新调入内存。
回顾
覆盖，是在同一个进程或程序中进行的。
交换，是在不同进程（或作业）之间的。
①内存空间的分配 – 连续分配管理方式
连续分配：系统给进程分配的必须是一个连续的内存空间。
分区存储管理，比分页分段等存储管理实现简单。（不需要特定的数据结构如页表段表）
- 单一连续分配
- 固定分区分配
- 动态分区分配
单一连续分配
内存被分为系统区和用户区。
内存中只能有一道用户程序，即用户程序独占整个用户区。
固定分区分配
内存分为多个分区。（分区大小可以相等，可以不等）
每一个分区只能装入一道程序。】【故无法实现多个进程共享同一个内存区域】
OS需要建立一个分区说明表。
动态分区分配
不会预先划分内存区，（在进程装入内存时），根据进程大小建立合适的分区。
没有内部碎片，有外部碎片。
外部碎片：内存中某些内存分区太小难以利用。
解决外部碎片：紧凑技术。（挪移拼接）
1.建立空闲分区表或者空闲分区链
2.用动态分区分配算法（之后介绍）
3.两个相邻的空闲分区合并。
回顾
动态分区分配算法
基于顺序搜索的分配算法
首次适应：按低地址开始寻找（在空闲分区表/分区链找到第一个大小满足的空闲分区）
邻近适应：每次分配内存从上次结束位置开始查找空闲分区表/链。（空闲分区以地址递增的顺序排列（可以是循环链表）
最佳适应：优先使用更小的空闲分区。（把空闲分区按大小递增链接）
- 缺点：会留下很多很小的内部碎片。（eg10给了9）
最坏适应：优先使用最大的空闲区。
- 缺点：之后有大进程来的话，没有空闲分区可用。
基于索引搜索的分配算法
事先建立索引表（如链表数组、位图、哈希表），按分区大小分类管理空闲分区，分配时直接索引到合适大小的分区，避免遍历整个空闲链表，从而提高分配速度。
| 算法 | 索引方式 | 分配速度 | 合并难度 | 碎片情况 |
|---|---|---|---|---|
| 快速适应 | 按固定大小分类 | 极快（O(1)） | 困难 | 内部碎片 |
| 伙伴系统 | 按 2 的幂分类 | 较快（对数级） | 简单（合并伙伴） | 内部碎片 |
| 哈希算法 | 哈希函数映射 | 较快（+链内查找） | 取决于链表管理 | 较灵活 |
回顾
①内存空间的分配 – 非连续分配管理方式
非连续分配：为用户进程分配的可以是分散的内存空间。
把进程分页或者分段，离散的放进内存中。
- 基本分页存储管理
- 基本分段存储管理
- 段页式存储管理
分页存储
内存分成一个一个内存块（又叫页框）
进程分成一个一个页/页面（页大小=块大小）
页表
记录页号和块号的映射关系。
一个进程对应一张页表。
进程每一页对应一个页表项。
一个页表项由“页号”和“块号”组成。
Note：
进程的页表大多数驻留在内存中。
平时进程没执行的时候，页表的始址和页表长度放在自己进程的PCB中。
unless当调度到该进程时，OS将页表始址和页表长度加载到CPU的页表寄存器中 。
虚拟地址→逻辑地址，包括查询页表的操作，硬件自动完成，不是OS实现。
页面大：页表项少。但页内碎片较大。
页面小：页内碎片小。但页表项多，且小页面会导致缺页频繁（io↑)。
所以页面大小是一件很重要的事情，是对页表开销，内存浪费，io效率之间的均衡。
页面在物理内存中只能从页面大小的整数倍地址开始存放。
Q1：每个页表项占多少字节？
Note：页号是隐藏的，不记位数。只看块号的位数就行。
（页面偏移量→页面大小）
Q2:如何实现地址转换（逻辑地址，物理地址）？
逻辑地址A对应的物理地址 = P号页面在内存中的起始地址 + 页内偏移量W
- P号页面在内存中的起始地址 = 块号 * 块大小
页面大小为2的k次方有什么好处？
无需进行除法运算，就能得到逻辑地址对应的页号和页内偏移量。（二进制数末尾k位就是页内偏移量，其余部分就是页号）
除法运算：
页号 = 逻辑地址/页面大小
偏移量 = 逻辑地址%页面大小
回顾
基本地址变换机构
就是：用于==实现逻辑地址到物理地址==转换的一组硬件结构。
VS
需要硬件地址变换机构的：用于动态重定位的情况。比如：动态分区分配，页式存储，段式存储，页式虚拟存储。
不需要硬件地址变换机构的：采用静态重定位的情况。比如：单一连续分配，固定分区分配。
页表寄存器
进程未被执行时，页表在内存的始址和页表长度放在PCB中。
当进程被调度时，os内核会把它们放到页表寄存器中。
地址变换过程
页式管理中的地址是一维的
即只要给出一个逻辑地址，系统就可以自动算出页号和页内偏移量，并不需要告诉系统页内偏移量占多少位。（因为可由页面大小得知）
进程页表通常是装在连续的内存块中的。（也成全了下条）
为了方便页表的查询，常常会让一个页表项占用更多的字节，使得每个页面恰好可以装得下整数个页表项。
回顾
两次访存：一次是查询页表，一次是访问目标内存单元。
具有快表的地址变换机构
快表TLB
- 是一种高速缓存Cache！不是内存。
- 存放最近访问的页表项的副本。（普通cache会有各种数据的副本，快表cache就很单一了哈哈哈）
- 与之对应，页表称为慢表。
- 提高TLB命中率的方法：①增大TLB容量。②提高页面大小。【TLB 覆盖范围 = TLB 条目数 × 页面大小】
如果快表命中，只需要一次访存
如果快表没命中，需要两次访存。（访存费时间，访问cache快很多）
局部性原理
基于局部性原理，快表命中率可以达到90%以上。
回顾
两级页表
单级页表存在的问题
问题一：页表必须连续存放，如果页表很大，需要占用很多个连续的页框，和内存离散分配的初衷相反。
问题二：没有必要让整个页表常驻内存，进程在一段时间内可能只需要访问某几个特定的页面。
问题一solute：把页表分块，用页目录表（外层页表）索引。
问题二solute：虚拟存储技术
Note：
如果采用多级页表机制，则各级页表大小不能超过一个页面（每个页面可以存放的页表项不能过多，以此确定页号占的位数）。
两级页表新的问题：三次访存（假设没有快表）
回顾
分段存储
分段
进程按照自身逻辑分为多个段，每个段长度不等。
每一个段都有一个段名（编译程序会转为段号）。每一个段编址都是从0开始。
各段之间可以不相邻。
逻辑地址就是：段号 | 段内地址
段表
段表记录每一个段在内存中存放的位置。
构成：段号，段长，段基址。
各个段表项的长度是相同的？怎么确定？
地址变换
分段分页对比
分页：
- 实现离散分配，提高内存利用率。
- 对用户是不可见的。
- 页的大小固定，由系统决定。
- 分页的用户进程，地址空间是一维的。程序员只需给出 单一逻辑地址 即可表示地址。
分段：
- 更好满足用户需求。
- 对用户是可见的。
- 段的大小不固定，用户编写的程序决定。
- 分段的用户进程，地址空间是二维的。程序员标识地址时，既要给出 段名，也要给出 段内地址。
- 分段更容易实现信息的共享和保护。
- 同样可以引入“快表”
回顾
段页式存储
分页和分段的优缺点
段页式
先按模块分段，再将各段分页。
逻辑地址
段表，页表
一个进程对应一个段表，可能会对应多个页表。
逻辑地址转为物理地址
三次访存（无快表）
回顾
Notes：
让不同页表的页表项指向同一个页帧，可以共享改页帧的代码。（类似于共享段表，此处应该叫共享页表？）
如果代码是可重入的，这种方法可以节省很多内存空间。
可重入程序：通过共享来使用同一块存储空间，或者通过动态链接的方式将所需的程序段映射到相关进程中。
对主存的访问，是以字节/字为单位的。
对主存的分配，是以块（页）/段位单位的。