OS：3-存储管理

第3章 存储管理

3.1 存储管理的主要模式

  • 逻辑地址
    • 又称相对地址，即用户编 程所使用的地址空间
    • 一维逻辑地址（地址）
    • 二维逻辑地址（段号：段内地址）
  • 段式程序设计
    • 把一个程序设计成多个段
    • 代码段、数据段、堆栈段等
  • 物理地址：绝对地址
  • 主存复用
    • 按照分区
      • 主存划分为多个固定/可变尺寸的分区
      • 一个程序/程序段占用一个分区
    • 按照页框
      • 主存划分成多个固定大小的页架
      • 一个程序/程序段占用多个页架

存储管理的基本模式

  • 单连续存储管理：一维逻辑地址空间的程序占用一个主存固定分区或可变分区
  • 段式存储管理：段式二维逻辑地址空间的程序占用多个主存可变分区
  • 页式存储管理：一维逻辑地址空间的程序占用多个主存页架区
  • 段页式存储管理：段式二维逻辑地址空间的程序占用多个主存页架区

image-20210105191254414

3.2 存储管理的功能

地址转换

把逻辑地址转换成绝对地址

存储分配

  • 分配
  • 去配

存储共享

  • 多个进程共享主存储器资源
    • 多道程 序设计技术使若干个程序同时进入主 存储器，各自占用一定数量的存储空 间，共同使用一个主存储器
  • 多个进程共享主存储器的某些区域
    • 若干个协作进程有共同的主存程序块 或者主存数据块

存储保护

  • 为避免主存中的多个进程相互干扰，必须对主存中的程序和数据进行保护
  • 软硬件协同完成
    • CPU检查是否允许访问，不允许则产生地址保护异常
    • 由OS进行相应处理

存储扩容

  • 对换技术：把部分不运行的进程调出
  • 虚拟技术：只调入进程的部分内容

3.3 虚拟存储器的概念

想法：把物理内存扩大到大容量磁盘上，把磁盘空间当作内存的一部分，进程的程序和数据痛楚部分放在内存中、部分放在磁盘上

  • 程序执行的指令或访问的数据在内存中，可以顺利执行
  • 在磁盘上，部分装入
  • 如果没用足够的空闲内存空间，部分替换
image-20210105192703558
  • 需要建立与自动管理两个地址空间
    • (辅存)虚拟地址空间：容纳进程装入
    • (主存)实际地址空间：承载进程执行
  • 对于用户，计算机系统具有一个容量大得多的主存空间，即虚拟存储器

3.4 存储管理的硬件支撑

image-20210105192928059

image-20210105193001337

限长寄存器、基址寄存器存的是当前正在运行的线程/进程的

3.5 单连续分区存储管理

每个进程占用一个物理上完全连续的存储空间(区域)

单用户连续分区存储管理

  • 划分为系统区、用户区
    • 设置一个栅栏寄存器划分、保护
  • 采用静态重定位进行地址转换
    • 在装入一个作业时，把该作业中程序的指令地址和数据地址全部转换成绝对地址
image-20210105193331594

固定分区存储管理

image-20210105193546603
  • 静态分区
  • 内存空间被划分成数目固定不变的分区，各分区大小不等，每个分区只转入一个作业
  • 若多个分区都装有作业，可并发执行
  • 可用静态重定位
  • 需要一个主存分配表
image-20210105193556193

硬件实现+动态重定位的地址转换如下：

image-20210105193710415

缺点：不够灵活，既不适应大尺寸程序，又存在内存内零头，有浪费

3.6 可变分区存储管理

image-20210105194032584
  • 系统初始，整个用户区是一个大的空闲分区，随着作业的装入和撤离，内存空间被分为许多分区，有的被占用，有的空闲
  • 创建一个进程时，根据进程所需主存量查看主存中是否有足够的空闲空间
    • 有，按需要量分割分区
    • 无，进程等待主存资源
  • 分区大小按照进程实际需要量来确定，因此分区个数是随机变化的
  • 缺点：可变分区方式也会随着进程的内存分配 产生一些小的不可用的内存分区，称为内存外零头

主存分配表

使用链表

image-20210105194111466

分配算法

  • 最先适应分配算法(first fit)
    • 顺序查找未分配区表或链表，找到第一个长度满足的空闲区
  • 邻近适应分配算法(next fit)
    • 总是从未分配区上一次扫描结束处顺序扫描，找到第一个长度满足的空闲区
  • 最优适应分配算法(best fit)
    • 挑选一个能满足用户进程要求的最小的的空闲分区来分割
  • 最坏适应分配算法(worst fit)
    • 挑选一个最大的空闲分区来分割
  • 快速适应算法(quick fit)
    • 为经常用到的长度的空闲区设立单独的空闲区链表

快速适应算法查找快速，但归还和合并复杂

最先适应算法简单、快速，用的多，其次是邻近适应和最优适应

地址转换

image-20210105194714328

移动技术

  • 解决内存外零头
  • 需要动态重定位支撑
image-20210105194838323

3.7 页式存储管理的基本原理

  • 分页存储器将主存划分成多个大小相等的页架

  • 受页架尺寸限制，程序的逻辑地址也自然分成页

  • 页表用于维系进程的主存完整性

  • 逻辑地址：image-20210105195033071

  • 物理地址：image-20210105195050461

地址转换

image-20210105195206705

分配去配

  • 位示图
  • 链表

image-20210105195431092

页的共享

  • 数据共享：不同进程可以使用不同页号共享数据页
  • 程序共享：不同进程必须使用相同页号共享代码页
    • 共享代码页中的(JMP <页内地址>)指令，使用不同页号是做不到

3.8 页式存储管理的地址转换

  • 页表放在主存: 每次地址转换必须访问两次主存

  1. 按页号读出页表中的相应页架号

  2. 按计算出来的绝对地址进行读写

  • 存在问题：降低了存取速度

  • 解决办法：利用Cache存放部分页表

  • 快表：存放在高速存储器中的页表部分

假定主存访问时间为200毫微秒，快表访问时间为40毫微秒，查快表的命中率 是90%，平均地址转换代价为 (200+40) *90%+(200+200)*10%=256毫微秒

快表转换流程

  • 若该页已在快表中，则由页架号和单元号形成绝对地址
  • 若该页不在快表中，则再查主存页表形成绝对地址，同时将该页登记到快表中
  • 当快表填满后，又要登记新页时，则需在快表中按一定策略淘汰一个旧登记项

多道程序下的进程表

  • 登记了每个进程的页表
image-20210105200607346
  • 地址转换过程

image-20210105200648976

3.9 页式虚拟存储管理

基本思想

把进程全部页面装入虚拟存储器，执行时先把部分页面装入实际内存，然后根据执行行为，动态调入不在主存的页，同时进行必要的页面调出

  • 首次只把进程第一页信息装入主存，称为请求页式存储管理

扩充页表项

每页的虚拟地址、实际地址、主存驻留标志、写回标志、保护标志、 引用标志、可移动标志

image-20210105200943350

地址转换

  • CPU处理地址
    • 若页驻留，则获得块号形成绝对地址
    • 若页不在内存，则CPU发出缺页中断
  • OS处理缺页中断
    • 若有空闲页架，则根据辅存地址调入页，更新页表与快表等
    • 若无空闲页架，则决定淘汰页，调出已修改页，调入页，更新页表与快表
image-20210105201138031 image-20210105201152862

3.10 页面调度

当主存空间已满而又需要装入新页时， 页式虚拟存储管理必须按照一定的算法把已在主存的一些页调出去

  • 选择淘汰页的工作称为页面调度
  • 选择淘汰页的算法称为页面调度算法

抖动/颠簸：页面调度算法设计不当，会出现刚被淘汰的页面立即又要调入，并如此反复

缺页中断率

假定进程P共n页，系统分配页架数m个，P运行中成功访问次数为S，不成功访问次数为F，总访问次数A=S+F

缺页中断率定义为：f=F/A

  • 可用页框数越多，缺页中断率越低
  • 页面尺寸越大，缺页中断率越低

调度算法

  • OPT/最佳/Belady调度算法

    • 当要调入新页面时，首先淘汰以后不再访问的页，然后选择距现在最长时间后再访问的页

  • FIFO

    • 总是淘汰最先调入主存的那一页，或者说主存驻留时间最长的那一页

    • 可能出现belady异常

      使用4个页框时的缺页次数比3个页框时的缺页多，因此这种奇怪的情况称为Belady异常

  • LRU

    • 淘汰最近一段时间较久未被访问的那一页
    • 模拟了程序执行的局部属性，既考虑了循环性又兼顾了顺序性

  • LFU

    • 淘汰最近一段时间内访问次数较少的页面，对OPT的模拟性比LRU更好

  • CLOCK

    • 页面调入主存时，其引用标志位置1
    • 访问主存页面时，其引用标志位置1
    • 淘汰页面时，从指针当前指向的页面开始扫循环队列
      • 把所遇到的引用标志位是1的页面的引用标志位清0，并跳过
      • 把所遇到的引用标志位是0的页面淘汰，指针推进一步

3.11 反置页表

  • MMU：CPU管理虚拟/物理存储器的控制线路，把虚拟地址映射为物理地址，并提供存储保护，必要时 确定淘汰页面
  • 反置页表IPT：MMU用的数据结构
  • 优点：只需为所有进程维护一张表

设计思想

  • 针对内存中的每个页架建立一个页表
  • 表项包含：正在访问该页框的进程标识、页号及特征位，和哈希链指针等

地址转换

  1. MMU通过哈希表把进程标识和虚页号转换成一个哈希值，指向IPT的一个表目
  2. MMU遍历哈希链找到所需进程的虚页号， 该项的索引就是页架号
  3. 若遍历整个反置页表中未能找到匹配页 表项，说明该页不在内存，产生缺页中断，请求操作系统调入

image-20210105203555963

3.12 段式存储管理

  • 页式存储的缺点：页面与源程序并不存在逻辑关系，难以源程序以模块为单元进行分配、共享和保护
  • 段式存储：每个程序可由若干段组成，如主程序段、子程序段、数据段、工作区段，每一段都可以从“0”开始编址，段内的地址是 连续的

image-20210105203932749

基本思想

  • 基于可变分区存储管理实现， 一个进程要占用多个分区
  • 硬件需要增加一组用户可见的段地址寄存器（代码段、数据段、堆栈段，附加段），供地址转换使用

image-20210105204148631

段的共享

  • 通过不同进程段表中的项指向同一个段基址来实现
  • 对共享段的信息必须进行保护，如规 定只能读出不能写入，不满足保护条 件则产生保护中断

3.13 段式虚拟存储管理

把进程的所有分段都存放在辅存中，进程运行时先把当前需要的一段或几段装 入主存，在执行过程中访问到不在主存 的段时再把它们动态装入

  • OS实现，对用户透明

扩充段表

image-20210105204516741

地址转换

image-20210105204552811

3.14 段页式存储管理

image-20210105204711371

image-20210105204753521

image-20210105204800993

补充

伙伴系统

伙伴系统(Knuth，1973)，又称buddy算法，是一种固定分区和可变分区折中的主存管理算法，基本原理 是：任何尺寸为2i的空闲块都可被分为两个尺寸为2i-1 的空闲块，这两个空闲块称作伙伴，它们可以被合并 成尺寸为2i的原先空闲块

image-20210105213215398

寻址计算

  • 从0开始

分段：

image-20210105213416534

分页:

image-20210105213511919

多级页表

image-20210105213606733

反置页表

不论由多少进程、支持多少虚拟页，页表都只需要实存中的一个固定部分

页面大小

image-20210105214613088

局部最佳页面替换算法

如果该 页面在时间间隔(t, t+τ)内未被再次引用，那么就移出；否则，该页被保留在进程驻留集中

image-20210105224855497

工作集置换算法

工作集模型用来对局部最佳页面替换算法进行模拟实现，不向前查看页面引用串，而是基于程序局部性原理向后看

W(t，Δ)表示在时刻t-Δ到时刻t之间( (t-Δ，t))所访问的页面集合，进程在时刻t的工作集

image-20210105224954776

PFF替换算法

规则：如果本次缺页与前次缺页之间的时间超过临界值τ，那么，所有在这个时间间隔内没有引用的页面都被移出工作集

image-20210105224738884
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/cpaulyz/p/14238540.html