内存管理基础
内存管理概述
存储管理的主要任务是为多道程序的运行提供良好的环境，方便用户使用存储器，提高存储器的利用率以及逻辑上扩充存储器。
功能：
- 内存的分配和回收
- 地址变换
- 扩充内存
- 存储保护
应用程序的编译、链接与装入
应用程序从用户编写的源文件到内存中执行的进程，大致分为三个阶段：
- 经编译层序，将源代码编译为若干个目标模块
- 通过丽娜姐程序将编译好的目标模块以及所需的库函数链接在一起，形成完整的装入模块
- 通过装入程序将这些装入模块装入内存并执行。
————————————————————————————————————————————————————————————————————————————
一些小笔记
名地址
：对程序设计者来说，数据的存放地址由数据名称决定，因此称为名地址。
相对地址
（
虚拟地址、逻辑地址
）：源程序经过编译后得到目标代码，由于编译程序无法得知代码驻留在内存的实际位置（物理地址），一般总是从0号单元开始编址，并顺序分配所有地址单元，并不是真实的内存地址。
————————————————————————————————————————————————————————————————————————————
重定位
：通过地址转换将逻辑地址转换为物理地址的过程。
程序的链接有三种方式：
-
静态链接
：在程序运行之前，先把各个目标模块及所需库连接为一个完整的可执行程序，以后不再擦爱开。 -
装入时动态链接
：将应用程序编译后所得到的一组目标模块装入内存时采用边装入边链接的动态链接方式。 -
运行时动态链接
：直到程序运行过程中需要一些模块时，才对这些模块进行链接。
程序的装入也有三种方式：
-
绝对装入
：在编译时酒直到程序将要驻留的物理地址，编译层序残生含有物理地址的目标代码 -
可重定位装入
：根据内存当前情况，将装入模块装入到内存的适当位置，地址变换通常在装入时一次完成，之后不再改变，也称
静态重定位
。 -
动态运行装入
：允许程序运行时在内存中移动位置，也称动态重定位。
逻辑地址和物理地址
逻辑地址：由程序产生的与段（与页无关，因为只有段对用户可见）相关的便宜地址部分。总是从0号带能源开始编址。
物理地址：出现在CPU外部地址总线上的寻址物理地址内存的地址信号，是逻辑地址变换后的最终结果地址。
内存保护
内存保护是为了防止一个作业有意或无意地破坏操作系统或其他作业。常用的方法有
有界限寄存器
和
存储保护键方法
。
覆盖与交换
覆盖技术：把大的程序划分为一些列覆盖，每个覆盖是一个相对独立的程序单位。把程序执行时并不要求同时装入内存的覆盖组成一组，称为覆盖段。覆盖区大小由覆盖段中最大的覆盖来决定。
交换技术：把暂时不用的某个程序及数据部分（或全部）从内存移到外存中；或把指定的程序或数据从外存读到相应的内存中，并将控制权转交给它，让其在系统上运行。
连续分配管理方式
内部碎片：指已经分配给作业但不能被利用的内存空间
外部碎片：指系统中还没有分配给作业，但由于碎片太小而无法分配给申请内存空间的新进程的存储块。
单一连续分配
将内存分为两个连续存储区域，其中一个存储区域固定地分配给操作系统使用，通常放在内存低地址部分，另一个存储区域给用户作业使用。
会产生内部碎片
固定分区分配
将内存空间划分为若干个固定大小的分区，每个分区可以装入一道程序。
动态分区分配
为实现动态分区分配，系统中需设置相应的数据结构来记录内存的使用情况。常用的数据结构形式如下。
- 空闲分区表：登记系统中的空闲分区。
- 空闲分区链：用链头指针将内存中的空闲分区链接起来，构成空闲分区链。
分区分配算法
-
首次适应算法（First Fit，FF）。把空闲分区按照
地址递增
的次序用链表串成一个队列，每次需要为要给进程分配内存时都从队首开始找，顺着链表直到找到足够大的空闲分区，然后按照作业大小从该分区划分出一块内存空间分配给请求者，余下的空闲分区仍然留在空闲分区表中。 - 下次适应算法（Next Fit，NF）：即在首次适应算法的基础上把队列改成循环队列，不再每次都从队首开始空闲分区，而是从上一次找到的空闲分区的下一个分区开始找。
- 最佳适应算法（Best Fit，BF）：要求将空闲分区按照容量大小递增的次序排列。
- 最差适应算法（Worst Fit，WF）：要求将空闲分区按照容量大小递减的次序排列。
非连续分配管理方式
基本分页存储管理方式
分页原理
在分页存储管理中，用户作业的地址空间被划分成若干个大小相等的区域，称为
页
或
页面
。相应地，将主存的存储空间也分成与页面大小星等的区域，称为
块
或
物理块
。可以将作业中的任意一页放到主存的任意一块中。
分页存储管理系统中的逻辑地址包含两部分：页号P，业内位移W。
页表
页面和物理块的映射关系。
基本地址变换机构
具有快表的地址变换机构
页的共享和保护
：使共享用户地址空间中的页指向相同的物理块。地址越界保护，访问控制信息保护。
基本分段存储管理方式
在分段存储管理系统中，作业的地址空间由若干个逻辑分段组成，每个分段式一组逻辑意义上相对玩真的信息集合，每个分段都有子集的名字，每个分段都从0开始编址，并采用一段连续的地址空间。
分段管理系统的逻辑地址结构由段号S和段内位移W组成。
段表及地址映射
分页与分段的区别
页是信息的物理单位；段是信息的逻辑单位。
页的大小固定且由系统决定；段的长度不固定。
分页系统中作业的地址空间是一维的；分段系统中作业的地址空间是二维的。
分页系统有内部碎片，无外部碎皮；分段系统中无内部碎片，有外部碎片。
基本段页式存储管理方式
作业的地址空间首先被分成若干个逻辑分段，每段都有自己的段号，然后再将每一段分成若干个大小固定的页。、
虚拟内存管理
基本概念
局部性原理
大多数程序执行时，再一个较短的时间内仅使用程序代码的一部分，相应地，程序所访问的存储空间也局限于某个区域，这就是程序执行的局部性原理。表现为：
时间局部性、空间局部性
。
常用的虚拟存储管理技术有
请求分页存储管理、请求分段存储管理和请求段页式存储管理。
请求分页存储管理方式
请求分页原理
作业运行之前，只要将当前需要的一部分页面装入主存，便可以启动作业运行。在作业运行过程中，若索要访问的页面不在主存中，则通过调页功能将其调入，同时还可以通过置换算法将暂时不用的页面置换到外存上，以腾出内存空间。
请求分页=基本分页+请求调页功能+页面置换功能
页表结构
页表中个字段的作用如下
- 页号和物理号：进行地址变换所必须的字段
- 状态位：用于判断页面是否存在主存中。
- 访问字段：用于记录页面在一段时间内被访问的次数。
- 修改位：用于表示页面调入内存后是否被修改过。
- 外存地址：用于指出页面在外存上的存放地址。
缺页中断与地址变换
页面置换算法
用来选择患处页面的算法。
最佳置换（OPT）算法
在预知一个进程的页面号引用串的情况下，没看此都淘汰以后不再使用的或以后最迟别使用的页面。无法实现，只能作为一个标注来衡量其他置换算法的优劣。
先进先出（FIFO）算法
每次总是淘汰最先进内存的页面，也就是淘汰在内存驻留时间最长的页面。
最近最少使用（LRU）算法
选择最近最长时间没有被使用的页面语义淘汰。
在常用的页面置换算法中，LRU算法最接近最佳置换算法。
时钟置换（CLOCK）算法（最近未使用（NRU）算法）
CLOCK维护一个内存中所有页面的循环链表，当程序需要访问链表中存在的页面时，该页面的访问位就被置为1；否则，若程序要访问的页面没有在链表中，那就需要淘汰一个内存中的页面，于是一个指针就从上次别淘汰页面的下一个位置开始顺序遍历链表，当这个指针指向的页面的访问位为1时，就把该访问位清零，指针再向下移动，当指针指向的页面的访问位为0时，淘汰这一页面。
改进型时钟（CLOCK）算法
在访问位为0的进程间有限淘汰没有修改过的页面。
与简单CLOCK算法相比，减少了磁盘I/O次数，但增加了扫描次数。
工作集与页面的分配策略
工作集
是最近n次内存访问的页面的集合。
页面分配策略
：固定分配局部置换、可变分配全局置换、可变分配局部变换。
页面调入策略
：请求调页策略、预调页策略。
抖动现象
FIFO置换算法的缺页率可能会随着所分配的物理块数的增加而增加，这种现象就是
Belady异常
。
产生Belady异常的原因：FIFO算法的置换特征预进程访问内存的动态特征相矛盾，被置换的页面并不是进程不会访问的。
LRU永远不会出现Belady异常。
抖动现象：
若选用的页面置换算法不合适，可能会出现这种现象：
刚被淘汰的页面，过后不久又要访问，并且调入不久后又调出，如此反复
，使得系统吧大部分时间用在了页面的调入调出上，而几乎不能完成任何有效的工作，这种现象称为
抖动
。
内存管理间的对比与一些计算方法
内存管理方式之间的比较
离散分配方式的比较
内存管理方式的比较
内存管理计算中地址的处理
十六进制、八进制、二进制对应的后最分别为字母H、O、B。
在请求分页系统中，若将
逻辑地址转换为物理地址
，处理过程如下：
- 将其他进制转化为二进制，方便处理。
- 求出页号，页号为逻辑地址与页面大小的商，二进制下为地址高位。
- 求出页内位移，业内位移为逻辑地址与页面大小的余数，二进制下为地址低位。（把地址平均分,前面的叫高位,后面的叫低位）
- 根据题意产生页表，通过查找页表得到对应页的内存块或页框号。
- 若给出的是内存块号，则用内存块号诚意块大小，加上基址，再加上页内位移得到物理地址。
- 若给出的是页框号，则用页框号与页内位移进行拼接，得到物理地址。
- 将二进制表示的物理地址根据题目要求转换为十六进制或十进制。
基本分页管理方式中有效访问时间的计算
有效访问时间（EAT）指给定逻辑地址找到内存中对应物理地址单元中的数据所有的的时间。
没有块表的情况
访存一次所需时间为t，有效访问时间分为：查找页表找到对应页表项，需要访存一次，消耗时间t；通过对应页表项中的物理地址访问对应内存单元，需要访存一次，消耗时间t。
因此，
EAT=t+t=2t
。
存在快表的的情况
设访问快表的时间为a，访存一次时间为t，快表命中率为b，则有效访问时间分为：查找对应页表项的平均时间a*b+（t+a)(1-b）。其中，a表示快表命中所需查找时间；t+a表示查找快表未命中时，需要再次访存读取页表找到对应页表项，两种情况的概率分别为b和1-b，可以计算得到期望值，即平均时间。通过页表项中的物理地址访存一次取出所需数据，消耗时间t。因此，
EAT=a*b+(t+a)(1-b)+t
。
请求分页管理方式中有效访问时间的计算
与基本分页管理方式相比，多了缺页中断的情况，需要耗费而外的时间，因此计算有效访问时间时，要将缺页这种情况考虑进去。
- 访问的页在主存中，且访问页在快表中，则EAT=查找快表时间+根据物理地址访存时间=a+t。
- 访问的页在主存中，但不在快表中，则EAT=查找快表时间+查找页表时间+修改快表时间（题目未给出则忽略不计）+根据物理地址访存时间=a+t+a+t=2（a+t）。
- 访问的页不在主存中（此时也不可能在快表中），即发生缺页，设处理缺页中断的时间未T（包括将该页调入主存，更新页表和快表的时间），则EAT=查找快表时间+查找页表时间+处理缺页时间（通常包括了跟新页表和快表时间）+查找快表时间+根据物理地址访存时间=a+t+T+a+t=T+2（a+t）。
然后加入缺页率和命中快表的概率，将上述3中情况组合起来，形成完整的有效访问呢时间计算公式。设命中快表的概率为d，缺页率为f，则
EAT=查找快表时间+d*根据物理地址访存时间+（1-d）*[查找页表时间+f*（处理缺页时间+查找快表时间+根据物理地址访存时间）+（1-f）*(修改快表时间+根据物理地址访存)]=a+d*t+(1-d)[t+f(T+a+t)+(1-f)(a+t)].
快表访问和修改时间，若没有说明则默认没有快表，将命中率和访问时间变为0即可。如忽略访问和修改快表的时间，则将a变为0即可。
关于处理缺页中断时间T的计算，若题中没有说明被置换出的页面是否被修改，则缺页中断时间统一为T。若分修改和未修改的情况，设被修改的概率为n，处理被修改的页面的时间为T1，处理未修改的页面的时间为T2，则T=n*T1+(1-n)T2.