存储管理
分页存储
1、离散存储的基本概念
将一个进程直接分散地装入到许多不相邻的分区中，而无须“紧凑”的分配方式，称为离散分配。
离散分配的种类包括分页存储管理、分段存储管理和段页式存储管理。
不具备页面对换功能的分页存储管理方式称为基本分页存储管理方式。
2、页面和页表
分页原理
1）页：把将进程的逻辑地址空间分成若干个大小相等的片，称为页面或页
2)内存空间分成与页大小相等的若干个存储块，称为物理块或页框。
通过适当的变换可以使逻辑空间的一页对应到物理空间的一块上。
3)在为进程分配内存时，以块为单位，将进程中的若干页分别装入多个可以不相邻的块中。
页划分原则：页面的大小由机器的地址结构确定。1)不能太大：否则会造成碎片太大。2)不能太小：否则页表太长。3）通常页面大小要适中，在512B--4Mb之间
3、页式存储管理逻辑地址结构
划分为页号和页内位移两部分
4、页表
在分页系统中，允许将进程的每一页离散地存储在内存的任一物理块中，但系统应能保证进程的正确运行，即能在内存中找到页面所对应的物理块。
为此，系统为每个进程建立了一张页面映像表，简称页表。
页表的物理空间是内存中的物理块。
页表中的内容是第i页(i=1,2,3,…)在内存中存储的的物理块号。如下图所示为逻辑页面和物理块号之间的映射关系：
页表的作用：页表中记录了逻辑地址和物理地址的对应关系；页表的每一项称为页表项；
5、地址变换机构
地址变换机构实现代码、数据的逻辑地址到物理地址的变换。
为什么要进行地址变换？
1）程序或数据装入内存时，操作系统记录的是它的逻辑地址。
2）进程运行过程中，CPU欲访问程序或数据时，需要知道它们的物理地址。
因此，需要在运行时实现逻辑地址到物理地址的转换。
基本的地址变换过程
1)截取页号和页内地址：当进程要访问某个逻辑地址中的数据时，分页地址变换机构会自动将有效地址(相对地址)分为页号和页内地址。
2)越界检查：在检索之前，首先将页号和页表长度进行比较，若页号长度大于或等于页表程度，则表示本次所访问的地址已超越进程的地址空间。于是，这一错误将被系统发现并产生越界错误。若未越界，则检索页表。
3)检索页表：将页表始址与页号和页表项长度的乘积相加，得到该表项在页表中的位置，于是得到该页的物理块号，将之装入物理地址寄存器中。
4)物理地址的形成：与此同时，再将有效地址寄存器中的页内地址送入物理地址寄存器的块内地址字段中。这样便完成了从逻辑地址到物理地址的转换。
具有快表的地址变换
由于页表放在内存，使得CPU存取一个数据时，要两次访问内存，为了提高速度，增设快表（高速缓存）。
两级和多级页表
分段存储
分段存储管理方式的目的，则主要是为了满足用户（程序员）在编程和使用上多方面的要求，其中有些要求是其他几种存储管理方式所难以满足的。
基本分段存储管理方式具有方便编程、信息共享、信息保护、动态增长和动态链接的优点。
1、分段存储管理的基本原理
整个作业的地址空间被分成若干个段，每个段采用一段连续的地址空间，段的长度由相应的逻辑信息的长度决定。
地址变换机构
分页和分段的区别
1)分页方式降低了内存碎片，提高了内存的利用率。
2)页的大小是固定且由系统决定的，而段的大小不固定，取决于用户所编写的程序。
3)分页的作业地址空间是一维的，而分段的作业地址空间则是二维的，程序员在标识一个地址时，既要给出段名，还要给出段内地址
段页式存储
1、基本原理
1)是分段和分页原理的结合。
2)将用户程序分为若干段，再把每个段分成若干个页，并为每一个段赋予一个段名。
3)在段页式系统中，其地址结构由段号、段内页号和页内地址三部分组成
2、地址变换过程
请求式分页
1、页表机制
请求分页存储管理方式中页表的作用是将用户地址空间的逻辑地址转换为内存空间的物理地址。
页表结构
2、缺页中断机构
在请求分页系统中，每当所要访问的页不在内存时，便产生一次缺页中断，请求OS将所缺之页调入内存。
缺页中断步骤：保护CPU环境、分析中断原因、转入缺页中断处理程序和恢复CPU环境。
特点：1)在指令执行过程中产生，即异常。2)在一条指令执行过程中可发生多次缺页中断。
虚拟存储器
1、 定义
所谓虚拟存储器，是指具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统。
虚存的逻辑容量是内存容量和外存容量之和，最大容量由计算机的地址结构决定。
虚存的运行速度接近内存，成本接近外存。
2、工作原理
1) 在分页(段)系统的基础上，增加了请求调页(段)功能和页面(段)置换功能所形成的页(段)式虚拟存储系统。
2) 它允许只装入部分页面(段)的程序(数据)，便启动运行。以后需要尚不在内存的程序或数据时，再通过调页(段)功能和页面(段)置换功能，陆续把即将运行的页面(段)调入内存，同时把暂不运行的页面(段)换出到外存上。
3) 置换时以页面(段)为单位进行
3、特征
1)多次性，作业分多次调入内存，是虚拟存储器的独特的特征。
2)对换性，允许作业在执行的过程中换入、换出，从而提高内存利用率。
3)虚拟性，从逻辑上扩大内存容量，使用户看到的内存容量远大于实际内存容量 。
页面置换算法
1、 先进先出算法
1)最早出现的置换算法
2)原理：淘汰最先进入内存的页面，即选择在内存中驻留时间最长的页面予以淘汰。
3)实现：把某进程已调入内存的页面，按先后次序链接成一个队列，并设置一个指针，称为替换指针，使它总是指向最老的页面。
4)特点：实现简单，但不合理 。
2、最近最久未使用算法
最近最久未使用算法(LRU)赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间t，当须淘汰一个页面时，选择现有页面中t值最大的，即最近最久未使用的页面予以淘汰。
硬件支持
(1)寄存器
1) 记录某进程在内存中各页的使用情况而为在内存中的每个页面配置的移位寄存器。
2)进程访问某物理块时，将相应的寄存器最高位置1。
3)定时信号每隔一段时间将寄存器右移一位。
4)将寄存器看成一个整数，则该数最小的寄存器对应的页面，即最近最久未使用的页面 。
(2)栈
保存当前使用的各个页面的页面号的特殊栈。
进程访问某个页面时，将该页号从栈内移出，置于栈顶。
栈顶始终是最新被访问页面的编号，栈底是最近最久未使用页面的页号。