存储管理
地址访问保护机制
作业拥有上下界,执行访存指令时,判断是否越界
要求:作业程序是绝对地址或静态可浮动
2. 基址寄存器、长度寄存器和动态地址转换机制
当作业被调度运行时，将作业所占内存基址及长度送基址、长度寄存器，在用户态每次执行访存指令时，先看访问地址是否小于长度，然后+基址进行访存。用户程序代码是动态浮动的
可变分区
思想:预先不划分内存，当作业需要时向系统申请，系统从其中挖出一块给该作业
Q:空闲区域如何管理?
多道连续可变分区法
特点:多道,连续,不固定划分内存
管理方法
系统设置一个空闲块队列，初始状态时队列中只有一个连续的空闲块。作业到达后，以某种策略分配空间。作业撤离时，将释放的空间加入空闲队列。
释放方法
相邻合并,否则插入
例一
进入执行顺序:(1,2,3)->(4)->(5)
分配方法
- 首次满足法 从头到尾找,找到的第一个满足它的空间就给它
- 最佳满足法 从队列中找一个最接近的空闲队列给它
- 最大满足法 每次找最大的空间给最新创建的进程
可用空间管理
紧致机制–将已有的进程挪到一起,腾出大块的连续空间
可再定位式分区–浮动分区分配
页式存储管理
解决作业不连续存放的问题
特点： 作业 (进程) 分成页面，内存也划分成页面，将作业 **(进程 **) 页面不连续地分布到内存页面
基本原理
分页逻辑地址 = P(页号).d( 页内位移 ** ) **
分页物理地址 = f(页帧号).d(同上)
P = 线性逻辑地址 / 页面大小；
d = 线性逻辑地址 **- P***页面大小。
为什么是2的k次幂?
将乘除法转成移位运算
为了取出一个数据，系统需要访问内存几次？–两次:1.取页表,2.取数据
快表
由一组联想寄存器(TLB, Translation Lookaside Buffer)组成。
联想寄存器：一种按内容进行并行查找的快速寄存器，访问速度比主存快得多
使用bitmap数组/空闲页帧链管理可用页帧
共享
通过页表可以使几个逻辑空间指向同一个物理空间，实现程序共享。
越界保护
设置页表长度寄存器,查页表前,检查页号是否越界
访问保护
在每个页表项中增设一存储保护域，用于说明对该页的访问权限，每一个对该页存储的访问都首先要比照是否满足该页访问权限的说明，满足则访问，否则报异常。
Ø优点
ü没有外碎片，每个内碎片不超过页大小。
ü程序不必连续存放。
Ø主要缺点：
ü程序要一次全部装入内存才能执行。
ü采用动态地址变换机构会增加计算机的成本和降低处理机的速度。
ü各种数据结构(页表，空闲页表)要占用一定的内存空间，而且系统要花费一定的时间来建立和管理这些表格。
ü依然存在内碎片。
段式存储管理
特点:按作业的自然段将其逻辑空间分成若干段，作业以段为单位分配内存。
Ø用户作业逻辑空间为二维空间，由若干自然段组成。
Ø 逻辑地址：段号段内偏移，记作S,d。编译及装配时把所有地址记成(S,d)的形式。
Ø 物理内存空间管理：与多道可变划分法一样，系统以段为单位分配物理内存。
段页式管理
特点：将作业分成若干段，每段用页式管理实现内存分配
为了获得一条指令或者数据，需要访问内存几次？–3次,段表,页表,数据
内存扩充技术
借助大容量的辅存实现内存的扩充
覆盖技术
将用户空间划分成一个固定区和多个覆盖区。主程序放固定区，依次调用的子程序则放在同一个覆盖区。****操作系统提供覆盖系统调用函数，由用户编程序显式调用
相当于时间换空间
交换技术
将处于等待状态(等I/O结束)或就绪(等CPU)状态的作业从主存换出到辅存，把将要执行的进程移入主存。
优点:
提高并发性
缺点:
换入换出增加处理机开销
程序换入时存在重定位问题
和覆盖技术对比
虚拟存储技术
基础
程序中不是每一条指令都会在程序的一次运行过程中执行到。
错误处理子程序
条件语句(if…else…)
程序中有的指令可能只执行一次
程序的初始化部分
程序执行的局部性原理：在一段时间内，作业一般不会执行到所有程序的指令，也不会存取绝大部分数据，执行的代码和要存取的数据往往集中在某些区域中(例如一个循环、一个数组)。
目的：提供用户进程一个巨大的虚拟存储空间
手段：利用外存(磁盘)实现此虚空间。
基本思想
系统为进程提供一个比物理内存大得多的虚拟存储空间，虚拟空间大小不受物理内存大小的限制。
虚拟空间的容量由系统的有效地址长度决定。假设地址长度为32，按字节寻址，则虚拟存储空间大小为$2^{32}$个字节。
原理
在程序装入时，不必一次将其全部读入到内存，而只需将当前需要执行的某些区域读入到内存，然后程序开始执行。在程序执行过程中，如果需执行的指令或访问的数据尚未在内存，则由处理器通知操作系统将相应的区域调入内存，然后继续执行。
分类
虚拟页式
页表增加外存标识位和外存地址项
当内存中没有空闲页面时，如果还要调入一个新页，如何处理？
淘汰掉一个内存中的页(淘汰策略)
交换区
用来回写数据初始值和初值为0的工作区
页表项结构
合法位：置上表示该页在内存。
修改位：置上表示该页被修改过，在释放或淘汰时应写
回外存。
页类型：零页时：表示该页在分配物理页帧时应清0页帧
空间;回写swap区页时:表示回写swap区。
保护码：R、W、E保护说明。
外存块号：该页所在外存的块号。
页 帧 号：当合法位置上时代表该页所在内存的页帧号。
缺页处理
根据发生页故障的虚地址得到页表项；
申请一个可用的页帧(根据所采用的替换策略可能需要引起淘汰某一页);
检查页类型，若为零页，则将页帧清0，将页帧号填入页表项的页帧号一栏，置合法位为1。若非零页，则调用I/O子系统将外存块号所指的数据读到可用页帧，将页帧号填入页表项中，合法位置1，结束。
页淘汰
查P页表项的修改位，若未修改，则清0合法位，将页帧送回空闲页帧队列。
若已修改，则检查类型栏。
若是零页或回写swap区页（代表还没有分配交换区空间），则申请一块swap区空间，将P的外存块号置上并清除页类型。
调用I/0子系统将页帧上的数据写到外存块号所指的外存空间。清0合法位，将页帧送回空闲页帧队列。
页面置换策略
出发点： 把未来不再使用的或者短时期内较少使用的页面调出
基本概念
驻留集：进程的合法页集合
访问串：进程访问虚拟空间的地址踪迹
举例：某进程依次访问如下地址，0100，0432，0101，0612，0102，0103，…
页式虚存管理以页为基本单位，只需页号即可。设页面大小为100，上述访问串可简化为1，4，1，6，1，1，…
驻留集大小固定的局部置换策略
FIFO（先进先出）
替换最早进入的页
效果奇差
有Belady奇异 指置换策略不满足随着驻留集的增大，页故障数一定减少的规律。
OPT（最佳算法）
需要预先知道整个访问串的序列（因此不可实现）
理论最优
LRU（最近最少使用）
淘汰上次使用距当前最远的页
栈算法
LRU策略中，当驻留集大小为m时，S（m，t）中保持着最近使用过的m个页帧；当驻留集大小为m+1时，S（m+1，t）中保持着最近使用过的m+1个页帧。故S（m，t）属于 S（m+1，t），LRU策略是栈算法。
CLOCK
基于LRU的思想
硬件在页面被访问时设置页表项中的访问位
随着表针的移动，淘汰访问位是0的页面，或清除页面的访问位。
实用的页面置换算法
NRU(最近未使用)
为页帧在页表项中增加一位使用位，硬件每访存一次即将对应页的使用位置1，操作系统页面管理程序定时将所有使用位清0。淘汰时任选一个使用位为0(表示OS清0周期内没被使用过）的页。
操作系统选择淘汰页时，尽量避免选被修改过的页。因此，选择淘汰页次序：
驻留集大小可变的全局置换策略
WS
若驻留集中某页有$\triangle$个访问间隔没被访问则将其淘汰(正是因为这个特性,才是动态的)
实现:
每一页面设一计数器,每访存一次,将所有其他页计数器+1,所访存的计数器清零,淘汰计数器等于$\triangle$的页面
实际上:开销太大,没有用
SWS
定时检查计时器,淘汰计时器值大于等于$\triangle$的页面(当前时钟值-页表时钟值)>$\triangle$的页面)
硬件消耗还是很大
置换策略选择
动态驻留集sws+淘汰页数据延迟清除
设立两个队列：自由链表和修改链表。
定时做页淘汰（SWS）：淘汰时不立即抹去页中数据，根据页面修改否挂入自由链/修改链，修改链过长或自由链过短时，回写页面后改挂到自由链中。
若paging in要用空页时,选自由链的第一页帧，这时页中数据被覆盖。
若在自由链/修改链中的页面再次被访问时，则将该页从链中摘除,使该页又能通过页表项访问到。
1 | 某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为2^10 字节，页表项大小为2字节，逻辑地址结构为： |
逻辑空间: 2^16 *2^10 =2^26
页大小为2^10 页表项大小为2,则一页能写2^9 个页表项
共2^16逻辑页,故需要 2^7页