第四章-存储管理
存储管理的功能：
- 内存分配和回收
- 内存抽象和映射
- 存储隔离和共享
- 存储扩充
1.地址重定位方式
（1）静态重定位
概念
根据程序所装入的内存位置由装入程序依据重定位信息一次性将程序中所有的逻辑地址转变为物理地址，然后程序开始执行，这种重定位方式称为静态重定位（可重定位装入方式）。
（2）动态重定位
概念
地址转换工作穿插在指令执行的过程中，每执行一条指令，CPU对指令中涉及的逻辑地址进行转换，这种重定位方式称为动态重定位（动态运行时装入方式）。
2.地址
（1）逻辑地址（相对地址）
概念
由于程序在内存中的位置不可预知，链接时程序地址空间中的地址总是相对某个基准（通常为０）开始编号的顺序地址，称为逻辑地址或相对地址。
（2）物理地址
概念
物理内存从统一的基地址开始顺序编址的存储单元。
3.内存分配与回收
方案：
- 连续
- 固定分区
- 可变分区
- 伙伴系统
- 离散
- 实存
- 分页
- 分段
- 段页
- 虚存
- 请求分页
- 请求分段
- 请求段页
- 实存
（1）连续分配（连续）
连续分配：为用户进程分配的必须是一个连续的内存空间。
①单一连续分配
单一连续分配：用户区存放用户进程相关数据，内存中只能有一道用户程序，该程序独占整个用户区。
②固定分区分配
固定分区分配：在早期多道程序系统中，整个用户空间划分为若干个固定大小的分区，在每个分区中只装入一道作业。
③动态分区分配
动态分区分配：不会预先划分内存分区，而在进程装入内存时，根据进程大小动态建立分区，使得分区的大小为进程的大小。
1）空闲分区表
空闲分区表：每个空闲分区在表中占一个表目，表目中包括分区序号、分区起始地址以及分区大小等数据项。
可变分区主存分配表由两张表格组成：
已分配区表：
| 分区号 | 其始地址 | 长度 | 标志 |
|---|---|---|---|
| 1 | 4KB | 6KB | Job1 |
| 2 | 46KB | 6KB | Job2 |
未分配区表：
| 分区号 | 其始地址 | 长度 | 标志 |
|---|---|---|---|
| 1 | 10KB | 36KB | 未分配 |
| 2 | 52KB | 76KB | 未分配 |
2）空闲分区链
空闲分区链：由于分区的个数不定，采用链表是较好的一种管理方式，每个内存空闲区的开头单元存放本空闲区长度及下一个空闲区的起始地址指针，所有的空闲区都被链接起来，系统设置一个第一块空闲区地址指针，让它指向第一块空闲区的地址。
3）常见算法
首次适应算法（从头到尾找最合适的空闲分区）
基本思想：查找空闲分区表/链,每次都从低地址开始查找，找到第一个满足大小的空闲分区，即要进入内存的进程需要的分区大小 ≤ 某空闲分区大小。
最佳适应算法（优先使用更小的空闲分区，保留更多大分区）
基本思想：先找到并使用第一个能满足进程的最小的空闲分区。
最坏适应算法（优先使用更大的空闲分区，防止太小的不可用碎片）
解决最佳适应算法中会导致产生太多外部碎片的问题，因为先用的小分区，但小分区中又可能用不完。 基本思想：先找到并使用第一个能满足进程的最大的空闲分区。
邻近适应算法（每次从上次查找结束的位置开始查找）
基本思想：每次分配内存时都从上次查找结束的位置开始查找空闲分区表/链，找到第一个满足大小的空闲分区。
（2）非连续分配（离散）
非连续分配：为用户进程分配的可以是分散的内存空间。
①分段存储
在分段存储管理方式中，作业的地址空间被划分为若干个段（大小不一定相等），每个段定义了一组逻辑信息。
段是信息的逻辑单位，分段的主要目的是更好地满足用户需求。
分段对用户是可见的，用户编程时需要显式地给出段名。
段的长度不固定由用户编写的程序决定。
1）分段
2）段表
3）地址变换机构
caution
段内地址要判断是否越界，因为段的大小不等，不判断无法知道是否越界。
②分页存储
分页目的：为了实现离散分配，提高内存利用率，尽量避免碎片产生。
分页思想：把主存空间划分为大小相等的且固定的块（相对较小），作为主存的基本单位把每个进程也以块为单位进行划分，进程在执行时，以块为单位逐个申请主存中的空间。
页是信息的物理单位。分页仅仅是系统管理上的需要，完全是系统行为，对用户不可见。
页的大小固定由系统决定。
1）页
important
进程中的块称为：页 / 页面（Page）
内存中的块称为：页框 / 页帧 / 内存块 / 物理块 / 物理页面（Page Frame）
外存中的块称为：块 / 盘块（Block）
2）逻辑地址到物理地址的转换
important
①确定A对应的页号P
页号 = 逻辑地址 / 页面长度（结果取整数部分）
②找到P号页面在内存中的起始地址
第 P 号内存块的起始地址 = P × 内存块大小
上一个内存块的末尾地址是下一个内存块的起始地址，而内存块从0开始，所以得到上面的结论。
③求解
逻辑地址A对应的物理地址 = 内存块的起始地址 + 页内偏移量W
页内偏移量 = 逻辑地址 % 页面长度（结果取余数部分）
3）基本地址变换机构
通过页表实现从逻辑地址到物理地址转换的硬件机构，需要两次访存。
4）具有快表的地址变换机构
快表（TLB）是一种高速缓存（硬件），用于存放最近访问的页表项（页号 + 内存块号）的副本，加快地址转换速度，（页表为慢表，在内存中，故访问页表需要访问内存）。
快表只存了页表项的一部分副本。
important
情况一：TLB未命中，需要访问页表
如果要查询的页号在TLB中未命中，则下一步查询页表，在页表中命中后得到对应的内存块号，随后将对应内存块的起始地址+页内偏移量得到物理地址，最后由该物理地址访问对应的内存单元（TLB未命中，则需两次访存）。
情况二：TLB命中，无需访问页表
如果要查询的页号在TLB中命中，得到对应的内存块号，随后将对应内存块的起始地址+页内偏移量得到物理地址，最后由该物理地址访问对应的内存单元（TLB命中，只需一次访存）。
5）两级页表
note
单级页表出现的问题：
问题一：页表必须连续存放，当页表很大时，需要占用很多连续的页框
K号页对应页表项的存放位置 = 页表起始地址 + K × 4KB，K必须连续取才能找到任一内存块，所以导致页表必须连续存放。
问题二：没有必要把整个页表都常驻内存，因为一段时间内可能只需访问某几个页面（局部性原理）
可以在需要用到的时候才将页面调入内存（虚拟存储技术），可以给页表项增加一个标志位，代表某页面是否已经调入内存。若想要访问的页面不在内存中，则产生缺页中断（属于内中断），然后将目标页面从外存调入内存。
③段页式存储
先将程序划分为多个有逻辑意义的段，也就是前⾯提到的分段机制，接着再把每个段划分为多个⻚，也就是对分段划分出来的连续空间，再划分固定⼤⼩的⻚。
④分段和分页对比
（3）分区回收
①回收区的后面有一个相邻的空闲分区
回收前：
回收后：
②回收区的前面有一个相邻分区
回收前：
回收后：
③回收区的前、后各有一个相邻的空闲分区
回收前：
回收后：
④回收区的前、后都没有相邻的空闲分区
回收前：
回收后：
4.虚拟存储管理（离散）
虚存
- 请求分页
- 请求分段
- 请求段页
前面的连续的（分区）、离散的（分页和分段）管理均是将程序一次性全部装入内存后才能运行，在下面情况下：
- 一个特别大的作业，不能够一次装入内存；
- 有大量作业在外存上等待运行，而又没有足够大的内存容纳这些作业，只能将少量作业装入内存运行，大量的作业在外存上等待。
解决办法：
- 可以从物理上扩大内存；
- 逻辑上扩充内存，即虚拟内存技术。
分析:
- 较小的一段时间内,整个作业空间中只有某一局部模块的指令和数据会被执行和访问到。作业其它部分暂时不会访问到；
- 这就允许这部分暂时不用的作业部分不必占据内存空间，可以先留在外存上，待以后需要访问时再装入内存；
- 内存中一些暂时不用的部分还可以临时调出到外存上，这样就可将内存空间优先分配给当前急需使用的作业进程，能够提高内存利用率；
- 部分装入即可运行，运行过程中作业的部分可以在内外存之间对换（部分对换），从逻辑上扩充内存容量，使得程序员的编程空间大于内存容量，这就是虚拟存储管理的主要思想（操作系统虚拟性的体现）。
important
虚拟内存的最大容量是由计算机的地址结构（CPU寻址范围）确定的。
虚拟内存的实际容量 = min（内存和外存容量之和，CPU寻址范围）
如：某计算机地址结构为32位，按字节编址，内存大小为512MB，外存大小为2GB。
则虚拟内存的最大容量为2³²B = 4GB，虚拟内存的实际容量 = min （2³²B，512MB + 2GB） = 2GB + 512MB
（1）概念
虚拟存储器：在具有层次结构存储器的计算机系统中，采用自动实现部分装入和部分对换功能，为用户提供一个比物理主存容量大得多的，可寻址的一种“主存储器”称为虚拟存储器。
（2）引入基础
虚拟存储器引入的基础是程序执行的局部性原理：
- 顺序局部性：程序中只有少量分支和过程调用，大都是顺序执行的指令；
- 空间局部性：程序执行的局部性是指在一段时间内程序访问的存储空间仅限于某个区域；
- 时间局部性：最近访问过的程序代码和数据很快会再被访问。
（3）请求分页
①基本原理
在进程开始运行之前，不是装入全部页面，而是装入一个或几个页面，进程运行过程中，访问的页面不在内存时，再装入所需页面；若内存空间已满，而又需要装入新的页面时，则根据某种算法淘汰某个页面，以便装入新的页面。
②页表机制
③缺页中断机构
缺页中断处理过程
处理过程如下：
- 挂起请求缺页的进程
- 根据页号搜索外页表，找到该页的磁盘物理地址
- 查看主存是否有空闲页框，如有则找出，并修改相应表项的内容，转6
- 如无空闲页框，按照替换算法选择淘汰页面，检查该页是否又被修改过，若有转6，若无转5
- 淘汰页面被修改过，将其内容写回磁盘的原先位置
- 进行调页，把页面装入主存所分配的页框中，同时修改进程页表
- 返回进程断点
④地址变换机构
⑤页面置换算法
- 最佳置换算法（OPTimal replacement，OPT）
- 先进先出置换算法（First - In First - Out replacement，FIFO）
- 最近最少使用置换算法（Least Recently Used replacement，LRU）
- 第二次机会置换算法（Second Chance replacement，SCR）
- 时钟置换算法（Clock policy replacement，Clock）
- 改进型时钟置换算法
important
假定作业p共计n页，系统分配给它的主存块只有m块（１≤m≤n）。如果作业p在运行中成功的访问次数为S，不成功的访问次数（缺页次数）为F。
则总的访问次数Ａ为： A = S + F
又定义：f = F / A ，称f为缺页中断率。
影响缺页中断率f的因素有：
- 主存页框数
- 页面大小
- 页面替换算法
- 程序特性
1）最佳置换算法（OPTimal replacement，OPT）
2）先进先出置换算法（First - In First - Out replacement，FIFO）
3）最近最少使用置换算法（Least Recently Used replacement，LRU）
4）第二次机会置换算法（Second Chance replacement，SCR）
FIFO只考虑进人内存的时间，不关心一个页面被访问的频率，从而有可能造成一个经常被访问的页面替换掉而造成效率低下。我们对FIFO改进的方向就是考虑一个页面是否是经常被访问的页面，即页面访问的频率。改进的手段就是在使用FIFO更换一个页面时，看一下该页面最近是否被访问过：
当页面被访问 (读或写) 时设置该页面的 R 位为 1。需要替换的时候，检查链表头部的 R 位。如果 R 位是 0，那么这个页面既老又没有被使用，可以立刻置换掉；如果是 1，就将 R 位清 0，并把该页面放到链表的尾端，修改它的装入时间使它就像刚装入的一样，然后继续从链表的头部开始搜索。
这样，对于最近被访问过的页面来说，相当于给了它第二次机会。（访问位设置为1）
5）时钟置换算法（Clock policy replacement，Clock）
第一轮扫描：
因访问位都为1，故所有访问位置0。
第二轮扫描：
1号页访问位为0，被淘汰，6号页进入，访问位置1，然后指针指向下一页面：
接下来访问3号页和4号页，并将访问位置1：
接下来需要处理页号7，需要淘汰一页，故进入第三轮扫描：
第三轮扫描：
3号页、4号页访问位置0后，指针指向下一页：
2号页访问位为0，故将其淘汰，7号页进入，访问位置1，指针指向下一页：
6）改进型时钟置换算法
考虑了修改页面的情况。
7）总结
⑥页面分配策略
1）驻留集
驻留集：给进程分配的物理块的集合。
分配小了装不下，会频繁缺页中断；分配大了，给一个进程分配多了物理块，别的进程就少了——并发性下降。
全局置换：把空闲的分给缺页进程，或把别的进程持有的物理块置换到外存再给缺页进程——总之缺页进程的物理块会变大，所以就不会是固定分配。
2）置换策略
固定分配局部置换：分配的物理块固定，缺页了就换走进程自己的其他页，换入需要的页。
可变分配全局置换：缺页就分配新物理块。
可变分配局部置换：根据缺页频率动态地增加或介绍进程的物理块。
3）何时调入页面
局部性原理主要是空间局部性原理，即：如果当前访问了某个内存单元，在之后很有可能会接着访问与其相邻的那些内存单元。
4）从何处调入页面
5）抖动（颠簸）现象
6）工作集
驻留集：内存块的集合。
工作集：访问的页面的集合。
页面要放在内存块里，所以驻留集大小不能小于工作集，否则会频繁缺页。
