之前忘了发出来的一篇。
[4]存储器管理
存储器层次结构
| 存储器 | 描述 |
|---|---|
| 寄存器 | 在CPU内，具有与其相同的速度，主要用于存储处理机运行时的数据 |
| 高速缓存 | 分为多级缓存，L1 cahce速度最快，因内置而容量不能太大，L2 cache速度差一些，但容量大，对性能起主要影响作用 |
| 主存 | 即内存，早期的内存由磁芯构成，现在的内存由VLSI(超大规模集成电路)构成 |
| 磁盘缓存 | 不是实际存在的存储器，利用主存中的部分存储空间暂时存放磁盘中读出或要写入的信息 |
| 固定磁盘 | 如固态硬盘，机械硬盘等，计算机内永久存储信息的存储器 |
| 可移动存储器 | 如光盘，U盘，移动硬盘，磁带等 |
程序的装入和链接
装入
| 装入方式 | 描述 | 地址转换 |
|---|---|---|
| 绝对装入方式 | 装入时使用绝对地址，可在编译或汇编时给出，也可由程序员指定 | 程序中的相对地址(逻辑地址)=实际内存地址 |
| 可重定位装入方式 | 起始地址从0开始，地址转换装入时由装入模块进行，即静态地址重定位 | 程序中的相对地址(逻辑地址)≠实际内存地址 |
| 动态运行时装入方式 | 刚刚装入时不做地址转换，程序可在内存中移动，地址转换在程序需要执行时进行，即动态地址重定位 | 因为在需要执行时转换，所以为了使转换不影响指令执行速度，需要重定位寄存器的支持 |
链接
链接细节：
①链接时需对各个模块中的相对地址进行修改统一
②链接时需将模块中所用的外部调用符号变换为相对地址
| 链接方式 | 描述 | 优缺点 |
|---|---|---|
| 静态链接方式 | 在程序运行前就已经将各目标模块和库函数链接成完整的装入模块，不再拆开 | ①对于链接好的模块难以修改 ②无法实现模块共享 |
| 装入时动态链接 | 在这组目标模块装入内存时边装入边链接，即装入的模块需要哪个模块，就去寻找并装入 | ①便于修改 ②可以实现模块共享 |
| 运行时动态链接 | 不运行的模块装入内存是一种浪费，故对某些模块的链接推迟到运行时，若在运行时发现缺少某个需要的模块，再由OS去查找，装入，链接 | ①能加快程序装入过程 ②能节省内存空间 |
连续分配存储管理方式
连续分配存储管理方式指的是，若程序中代码或数据的逻辑地址相邻，则内存空间分配时物理地址相邻。
单一连续分配
单道程序环境下，把内存分为系统区和用户区，系统区仅供OS使用，用户区仅装有一道用户程序。 
固定分区分配
早期多道程序环境下，将用户区分为多个固定大小的分区，每个分区只装入一道作业。 
动态分区分配
即可变分区分配，可以使用空闲分区表或者空闲分区链去记录每个空闲分区的情况。 
①在程序需要装入内存时，需根据某些算法从空闲分区中找出一个足够的分区，如果将这个分区分配给程序后余下的内存不超过一个阈值(该阈值是规定的不再切割的剩余分区的大小)：
就把这个分区都分配给它；否则要把剩余的部分保留，即在空闲分区表(链)中记录。
②当程序运行完释放内存时，OS根据需要回收的部分的首地址找到空闲分区表(链)中的插入位置，回收并考虑和上下接壤的空闲分区合并。
基于顺序搜索的的动态分区分配算法
这四个算法在分区分配时是依次搜索空闲链上的空闲分区的，比较传统。
| 算法 | 描述 | 特点 |
|---|---|---|
| FF首次适应算法 | 空闲分区链按照地址递增排序，遇到第一个够用的空闲分区时即做分配 | 低地址碎片较多，高地址具有大空闲分区 |
| NF循环首次适应算法 | 与FF的区别是，分配的搜索指针不回退，从上次查找到的空闲分区的下一个空闲分区开始循环查找 | 分配较均匀，但缺乏大空闲分区 |
| BF最佳适应算法 | 每次选择最小的能满足要求的分区进行分配 | 每次分配切割下来的剩余部分总是最小的，产生很多小碎片 |
| WF最坏适应算法 | 每次选择最大的能满足要求的分区进行分配 | 分配切割下来的剩余部分不会很小，即产生碎片的概率最小，但存储器中缺乏大的空闲分区 |
基于索引搜索的动态分区分配算法
建立索引能够提高搜索空闲分区的速度，适用于存储空间较大的系统。
①快速适应算法
即分类搜索算法，将空闲分区按进程常用的空间大小进行分类，用一张管理索引表串起来。 
在分配时直接找到最小能容纳的分区链表，从中读出一个分区(的地址)，将这个分区整个分配给该进程即可。回收时为了位置这个链的形式，可能尤为复杂。虽然复杂且会造成一些浪费(所以更要在存储空间大的系统里使用)，但不会造成碎片，而且查找效率很高。
②伙伴系统
伙伴系统算法多用在多处理机系统下的内存分配，其规定所有以已分配和未分配的分区都是大小，将相同大小的空闲分区设立一个空闲分区双向链表管理。 
在分配一个长度为n的存储空间时，去计算使得：
成立的i，并在链中寻找一块，若没有，则去寻找链中的一块(如果没有则继续向上寻找)，将其拆半分别用于分配和插入下层双向空闲链。
在回收时，如果已经存在等大的空闲块，则要考虑合并并向上层空闲链传递。
③哈希算法
如果索引表也很大，搜索起来也很费时，哈希算法彻底消除了对索引的搜索，可以结合其它算法，根据空闲分区的大小，通过哈希函数立即得到相应的空闲分区链表表头指针。
动态可重定位分配
前面的连续分配要求连续的系统或用户程序必须装入连续的内存空间，可能会产生很多碎片和零头，使得较大的程序没法再装入。
紧凑
类似于外存的”磁盘碎片整理”，只不过紧凑是针对内存而言的。紧凑把原来多个分散的小分区拼接成一个大分区，每次紧凑后都必须对移动了的程序或数据进行重定位。
动态重定位
在动态运行时装入方式下，地址转换在程序需要执行时发生。
如果把装入时即做好了重定位的”可重定位装入方式”称为”静态重定位”，则这种”动态运行时装入”即为”动态重定位”。
这种方式之所以是动态的，是因为即便程序在内存中的地址发生了变化(如因为前面说的紧凑)，也可以正常执行，因为重定位寄存器记录的总是程序在内存中的起始地址。
动态重定位分区分配算法
有了动态重定位，就不怕那些已经装进来的程序不能移动了！在这样的环境下，如果有较大的程序没法找到足够大的分区满足用户的需求，就可以对内存进行紧凑。所以，动态重定位分区分配算法是在动态运行时装入方式下允许了内存紧凑的动态分区分配算法，这是在硬件地址变换机构(如重定位寄存器)的支持下的一大改进。
对换
对换是指将内存中暂时不能运行的进程、暂时不用的程序、暂时不需要的数据换出到外存，腾出一些内存空间，并从外存中将具备运行条件的进程或正在运行的进程所需的数据换入内存。 
对换的类型
①整体对换：即上学期学的处理机中级调度，又称进程调度，用于解决内存紧张问题。
②页面(分段)对换：用于实现请求分页和请求分段，以支持虚拟存储系统。
对换空间管理的主要目标
磁盘被分为文件区和对换区。
①文件区用于存放各类文件，访问频率较低，对文件区管理的主要目标是提高文件存储空间的利用率，故采取离散分配方式。
②对换区用于存放从内存换出的进程，访问频率较高，对对换区管理的主要目标是提高进程换入换出都是速度，故采取连续分配方式。
分页存储管理方式
分页存储管理方式属于离散分配方式(将进程分散地装入内存的若干位置)。
分页存储管理的基本方法
页面和物理块
页面：将进程的逻辑地址空间分为若干个页。
物理块：把内存的物理地址空间分为若干个块。
页内碎片：进程的最后一页往往装不满，余下的部分是页内碎片。 
页地址结构
偏移地址的位数决定了页面的大小，即物理块的大小。
页表(页面映像表)
页表存放页号和物理块号的映射关系，每个进程一张，用于实现从页号到物理块号的地址映射。
地址变换机构
基本分页存储管理
地址变换机构做的事情是实现从逻辑地址到物理地址的转换，对于分页存储管理方式来说，即实现从页号到块号的转换(找到块之后使用页内地址就可以了)，页表寄存器PTR存放页表在内存中的首地址和页表长度： 
PTR只有一个，其中存的是调度程序调度到的那个进程的页表的这两个参数。
页号从0开始编号，在执行地址变换时先对页号进行检查是否越界，合法的页号需满足：
当不满足时会产生地址越界中断。页表存在内存中，查找页表项所在的地址：
注意”页表项的长度”是内存中的页表每一项跨过的地址，而不是”页长”。找到页表项后，就可以从中读出物理块号了。
引入快表的分页存储管理
还是因为程序的局部性原理，增设一个快表TLB在cahce中，存放的是部分页表项，做地址变换时先访问快表，如果未命中再去访问内存中的页表，并且用找到的记录以某种算法去更新快表。
内存的有效访问时间EAT
EAT是从发出访问请求到实际取出数据所需的时间，
基本分页存储管理
设访问内存的时间为t。第一次访问内存是查找内存中的页表项对应的物理块号，第二次访问内存是访问实际需要的物理地址单元。
引入快表的分页存储管理
设访问内存的时间为t，访问快表的时间为，快表命中率为a。当快表命中时，只需要再访问一次内存；当快表未命中时，仍然需要访问两次内存。
多级页表
用于解决难以找到大的连续的内存空间存放页表的问题，即为页表本身建立外层页表。
反置页表
普通的页表以页号为索引，存的是物理块号或者下一级页表的首地址；反置页表以物理块号为索引，存的是隶属的页号和进程标识符。反置页表能规避进程的逻辑地址空间很大带来的页表项过多的问题，但只包含了已经调入内存的页面，对于未调入内存的页面则需要访问外部页表。 
分段存储管理方式
页是信息的物理单位，段是信息的逻辑单位，对程序分段更符合程序的逻辑，而且更容易实现动态链接等。
段地址结构
段表结构
地址变换机构
类似于分页的情况，分段时使用的是段表寄存器： 
查到段表中的项目，之间将段基地址加上偏移量即可：
段页式存储管理方式
先分段，再分页。略。