存储管理

存储管理的基本任务：

1. 内存空间的分配与回收
2. 实现存储器扩充
3. 地址转换与重定位
4. 存储保护与主存共享

1. 程序装入和重定位

程序装载的三种方式：绝对装入、静态地址重定位、动态地址重定位

绝对装入：提前知道会在内存什么为止，在编译时确定
关于重定位

• 基本概念：可执行程序逻辑地址转换为物理地址的过程叫做地址重定位
• 分类：
  • 静态地址重定位
    • 程序装入内存时由链接装入程序完成从逻辑地址到物理地址的转换。

• 动态地址重定位
  • 编译、链接后转入模块的地址都是从0开始的，装入内存之后的所有地址仍然是逻辑地址。逻辑地址到物理地址的转换在程序真正运行时确定，设置一个重定位寄存器，存放装入模块存放的起始位置。

存储保护

1. 界地址寄存器：记录上限和下限
2. 重定位寄存器和界地址寄存器（最大逻辑地址）
3. 存储保护键：一个内存块加一把锁 只有正确的钥匙才能使用

2. 连续存储空间管理

1. 固定分区存储管理

• 主存分成若干个固定大小的区域，每个分区分给一个作业使用，直到作业完成后才将该分区归还系统。
• 两种划分方式：分区大小相等，分区大小不等
• 存储分块表MBT：当分区大小不等时记录每个分区的信息，包括大小、位置、状态
• 静态重定位，界地址寄存器实现保护
• 优点：管理简单、对硬件要求小
• 缺点：主存利用率不高，存在内部碎片；分区总数固定，限制并发执行的程序数目

• 没有外部碎片，但是有内部碎片

  2. 可变分区存储管理

• 分区大小、数量均可变

• 链表空闲区管理方法
• 可变分区管理分配算法
  • 最先适应分配算法：按照分区在内存中的先后次序从头查找，找到符合要求的第一个分区进行分配
  • 最坏适应分配算法：找到其大小与要求相差最大的分区进行分配；减少了外部碎片，不利于大作业分配
  • 最优适应分配算法：找到其大小与要求相差最小的分区进行分配；容易产生外部碎片
  • 快速适应分配算法
    
• 地址转换与存储保护：限长寄存器+基址寄存器
• 没有内部碎片，但是有外部碎片

3. 内部碎片和外部碎片

• 内部碎片：分配给某进程的内存区域中，有些部分没用使用到
• 外部碎片：内存中的某些空闲分区由于太小而难以利用

  3. 内存不足的存储管理

1. 移动技术
   • 解决可变分区管理中产生的外部碎片，将碎片整合起来形成一个大分区
2. 对换技术
   • 解决多个程序存在而导致的内存不足，将某个进程暂时移动到磁盘，腾出空间给其他进程使用，结束后再移动到原处
3. 覆盖技术
   • 解决用户程序长度超出物理内存总和，即一个作业的若干程序段或数据段，或几个作业的某些空间共享一些主存空间

3. 分页存储管理

1. 分页存储管理基本原理

• 等分主存：把主存划分为相同大小的存储块，称为页架，并按照其在内存中的地址顺序从0开始对其编号，记作页架号或块号。
• 逻辑地址空间分页：大小与页架大小相等；页，页号
• 逻辑地址表示

（p，d） p页号 = INT(逻辑地址/页大小) d偏移量 = 逻辑地址mod页大小

• 页表：存放进程页面实际存放的内存块之间的对应关系。（页号-块号/页架号）

  2. 逻辑地址向物理地址的转换

1. 算出逻辑地址对应的页号
2. 知道该页号在物理内存中的起始地址（页表）
3. 算出逻辑地址对应的偏移量
4. 物理地址 = 起始地址 + 偏移量

3. 特点

• 优点：主存利用率高，不存在页外碎片，极少页内碎片；主存分配和释放快；分区管理简单
• 缺点：要求一次将进程全部页装入主存；存在页内碎片

4. 快表

快表，是基于程序局部性原理的一种访问速度比内存快很多的高速缓冲存储器，用来存放当前访问的若干页表项，以加速地址变换的过程。
查询快表命中时不会再访问慢表

4. 分段存储管理

1. 分段的基本原理

• 进程的地址空间按照自身的逻辑关系划分为若干个段，每个段都有一个段名，每段从0开始编址
  • V = （S，W）S：段号 W段内地址
  • 
• 内存分配规则：以段为单位进行分配，每个段再内存中占据连续空间，但各段之间可以不相邻
• 段表：（段号、段长、基质）类似页表，记录各个逻辑段在内存中的实际存储位置

2. 逻辑地址到物理地址的转换

3. 特点

• 没有内部碎片，存在外部碎片
• 便于共享和保护
• 段的长度受内存空闲区大小的限制
• 需要更多硬件支持

  4. 分页和分段的区别

  页是信息的物理单位。分页的主要目的是为了实现离散分配。提高内存利用率。分页仅仅是系统管理上的需要，完全是系统行为，对用户是不可见的
  段是信息的逻辑单位。分段的主要目的是更好地满足用户需求。一个段通常包含着一组属于一个逻辑页的大小固定且由系统决定。

页的大小固定，由系统决定；段的长度却不固定，取决于用户编写的程序。

分页的用户进程地址空间是一维的，程序员只需给出一个记忆符即可表示一个地址
分段的用户进程地址空间是二维的，程序员在标识一个地址时，既要给出段名，也要给出一个段内地址

分段比分页更容易实现信息的共享和保护。

访问一个逻辑地址需要访问几次内存？
分页：第一次访问内存中的页表，第二次访问目标内存单元
分段：第一次访问内存中的段表，第二次访问目标内存单元

5. 虚拟存储管理

1. 虚拟内存概念

1. 为什么引入？

   • 传统存储管理需要将作业一次全部存入内存才能执行，作业很大时，不能全部装入内存，部分大作业无法运行；当有大作业运行时，由于内存无法容纳所有作业，只有少量作业可以运行，并发性能下降。
   • 作业被装入内存会一直存在于内存中，知道运行借书，但实际上一个时间段内只需要部分数据就可以正常运行，导致内存被大量无用数据占满

2. 原理：程序运行的局部性：时间局部性、空间局部性

3. 虚拟内存的定义和特征/虚拟内存的实现

   1. 基于局部性原理，在程序装入时，可以将程序中很快就会用到的部分装入内存，暂时用不到的部分留在外存，就可以让程序开始执行
   2. 在程序执行过程中，当所访问的信息不在内存时，由操作系统负责将所需的信息从外存调入内存，然后继续执行程序
   3. 若内存空间不够，操作系统负责将内存中暂时用不到的信息换出到外存
   4. 在操作系统的管理下，在用户看来似乎有一个比实际内存大得多的内存，这就是虚拟内存

      2. 请求分页虚拟存储管理

• 与实存分页管理的区别在于只需要将部分页面装入，如果访问到不存在的页面时产生缺页中断，再进行装入
• 页表机制：单级页表、多级页表、反置页表
• 缺页中断机构
• 地址变换机构

3. 页面管理策略

1. 页面装入策略

• 请页式调度：需要访问时才将该页调入主存

• 预调式调度：访问之前将该页调入主存

  2. 页面清除策略

• 请页式清楚：仅当一页被选中进行替换且内容被修改过才把他写回磁盘

• 预清楚：对所有更改过的页面，在需要替换之前把他们都写回磁盘

  3. 页面分配策略

• 固定分配：给进程分配的页框数固定不变

• 可变分配：给进程分配的页框数可变

  4. 页面替换策略

1. 全局替换：页面替换算法的作用范围是整个系统
2. 局部替换：页面替换算法的作用范围局限于进程

   5. 缺页中断率

   假定作业p共计n页，系统分配给它的内存块只有m块（1<=m<=n）。如果作业p在运行中成功的访问次数为s，不成功的访问次数为F，则总的访问次数A为： A = s+ F
   缺页中断率为： f = F/A
   影响缺页中断率f的因素有：

• 内存页架数
• 页面大小
• 页面替换算法
• 程序特性

  6. 全局页面替换策略

1. 最佳页面替换算法OPT

选择将来不再使用的或在最远的将来被访问的页面被置换

1. 先进先出的页面替换算法

淘汰的是最早进入内存的页面
Belady现象：当为进程分配的物理块数增大时，缺页次数不减反增的异常现象

1. 最近最少使用算法LRU

淘汰的是最近最少使用的页面
实现：

1. 维护一个存放页号的队列，每访问一次就将这一项移动到队列尾部，队列头就是当前最少使用的页。
2. 引用位法/最近未使用页面替换算法：每页设置一个引用位R，访问某页时，由硬件将每页标志位R置1，每隔一段时间t将所有页的标志R清零。发生缺页中断时，从标志位R为0的页中挑选一页淘汰，挑选到要淘汰的页后，也将所有页的标志位R清零
3. 计数法：最不常用页面替换算法LFU；每访问一次计数器+1，中断时选择计数值最小的
4. 计时法：为每个页面设置一个多位计时器，当页面被访问时，系统的绝对时间计入计时器，中断时选择计时器值最小的
5. 老化算法：为每个页设置一个多位寄存器R，当页面被访问时，最左边置1，每隔时间t，寄存器右移一位，淘汰时选择寄存器值最小的页面淘汰
   1. 第二次机会页面替换算法

改进FIFO算法，把FIFO与页表中的“引用位”结合起来使用。
检查FIFO中的队首页面（最早进入内存页面）如果它的“引用位”是0，这个页面既老又没有用，选择该页面淘汰；如果“引用位”是1，说明它进入内存较早，但最近仍在使用，把他的引用位清零，并把这个页面移到队尾，把它看作是一个新调入的页
算法含义：最先进入内存的页面，如果最近还在被使用的话，仍然有机会作为像一个新调入的页面一样留在内存中。

1. 时钟页面替换算法

• 始终页面替换改进算法

**

7. 局部页面替换算法