主要内容

  • 主存储空间的分配和去配
  • 地址转换和存储保护
  • 主存储空间共享
  • 主存储空间扩充 （虚拟内存）

地址转化：逻辑地址到物理地址
存储保护：防止操作系统和各用户程序在访问主存储器中各存储区域时相互干扰

连续存储空间管理

1. 固定分区存储管理

  • 数目不变，大小不等，一区一作业
  • 主存分配表：起始地址，长度，使用否
  • 作业进去分区前排队策略

  • 逻辑地址+下限=绝对地址（上限判断）

    2. 可变分区存储管理

  • 按照作业的实际大小分配

  • 分区的个数位置都动态分配
  • 管理数据结构：已分配表和未分配表

  • 逻辑地址<限长，逻辑地址+基址=绝对地址

    3. 伙伴系统

  • 基本思路：将用户内存区域对半分割以实现最佳适应的分配算法

  • 优点：很小的外碎片。方便内存分区的合并
  • 缺点：存在内碎片 （一定量的内碎片是好事）

外碎片应该就是分配的块之间的碎片
内碎片应该是分配的块内部浪费的空间
image.png

主存不足的管理技术

  • 移动技术
    • 把小块的合在一起，挤出大块的
    • 移动条件，移动时机、移动算法
  • 对换技术：暂时不用的数据放到外存
  • 覆盖技术：类似于C++的联合类型，一个程序不同时在主存的作为一组用一块空间

分页机制

将逻辑地址空间划分成固定大小的区—-页面
将物理地址空间划分成固定大小的区—-页框
逻辑地址：应用程序使用的地址
image.png

页表存储了页号到页框号的映射
物理地址=页框号×页框大小+页内偏移量

引入快表TLB加快查询

多级页表
image.png

页表页存储管理方法：
有用的在主存，其他的放外面，可能就会产生缺页表页中断

反置页表(IPT)
image.png

分段

分段的地址是两维的，被两个寄存器管理
image.png

虚拟存储

问题

  • 主存辅存统一管理问题
  • 逻辑地址到物理地址的转换问题
  • 部分装入和部分对换问题
  • Overhead问题
    • 时间开销
    • 存储开销
    • I/O开销

image.png

缺页处理：
请页式装入：每次只装缺的
预调式装入：根据局部性原理，每次缺页中断调入多个最可能访问的页面

页面分配策略：
固定分配：进程的页面数目固定，缺页会替换原来的一页
可变分配策略：页框数目可以变化

页面替换：
全体替换：替换的范围是整个系统
局部替换：局限于本进程

局部页面替换算法
最佳页面替换算法OPT

  • 替换以后不会访问或者距现在最长时间后要访问的页面
  • 缺页率最低
  • 很难实现：
  • 程序的引用串无法预测
  • 通常用作其他算法的衡量标准

先进先出页面替换算法FIFO

  • 算法总是淘汰最先调入主存的那一页，或者说在主存中驻留时间最长的那一页（常驻的除外）
  • 容易实现
  • 适用于具有线性顺序特性的程序.否则缺页率很高
  • Belady异常：增加可用主存页框的数目反而导致更多的缺页

image.png
最近最少用页面替换算法LRU

  • 算法淘汰的页面是在最近一段时间里最久未被访问的那页
  • 实现方法：淘汰队列，淘汰队头，刚访问的在队尾
  • 标志位法，访问了置1，从0的里面选一个，然后全部设为0，隔一会儿也设0
  • 最不常用页面LFU，计数器，选最小删除

第二次机会页面替换算法SCR

  • 改进FIFO算法,把FIFO与页表中的“引用位”结合起来使用
  • 检查FIFO中的队首页面(最早进入主存的页面),如果它的“引用位”是0,这个页面既老又没有用，选择该页面淘汰;
  • 如果“引用位”是1,说明它进入主存较早，但最近仍在使用。把它的“引用位”清0,并把这个页面移到队尾，把它看作是一个新调入的页。

时钟页面替换算法Clock

  • 当发生缺页中断时，检查指针指向位置的页面：
    • 当页面引用位为0时，替换该页面；
    • 当页面引用位1时，对该引用位置0（机器），指针累进
  • 改进算法，设置r和m位，第一次找两个都是0的，第二次找r=0，m=1的同时设置r=0。再做第一步

全局页面替换算法
全局最佳页面替换算法

  • 引用串。不论发生缺页与否，算法在每一步要考虑引用串，如果该页面在时间间隔(t,t+τ)内未被再次引用，那么就移出页面；否则，该页被保留在进程的驻留集中，直到再次被引用

image.png
工作集模型和工作集置换算法

  • 进程工作集：在某一段时间间隔内进程运行所需访问的页面集合
  • 基于程序局部性原理向后看，在任何给定时刻，一个进程不久的将来所需主存页框数，可通过考查其过去最近的时间内的主存需求做出估计。
  • 和全局最佳的算法相反，过去一段时间没用就直接移出

模拟工作集替换算法

  • 老化(Aging)算法
    • 例如，时间间隔T定为1000次存储器引用，页面P在时刻t+0时寄存器为“1000”，在时刻t+1000时寄存器为“0100”，在时刻t+2000时寄存器为“0010”，在时刻t+3000时寄存器为“0001”，在时刻t+4000时寄存器为“0000”，此时，页面p被移出工作集，
  • 时间戳算法
    • 若t_off>t_max，把页面从工作集中移出

缺页频率替换算法

  • 缺页频率替换算法根据连续的缺页之间的时间间隔来对缺页频率进行测量，每次缺页时，利用测量时间调整进程工作集尺寸。
  • 规则：如果本次缺页与前次缺页之间的时间超过临界值τ，那么，所有在这个时间间隔内没有引用的页面都被移出工作集。
  • 优点：只在缺页发生时才调整页面

如何确定页面的大小

  • 页表大小
    • 页面越小，页表越大页面应该大一点
  • 主存利用率
    • 最后一页产生碎片，页面越大，碎片越大页面应该小一点
  • 读写页面时间
    • 读入页面所需时间=等待时间和传输时间
    • 等待时间>>传输时间
    • 大页面有利于I/O传输
  • 现代操作系统：512b-8k

页面交换区&写时复制
淘汰页面存放在哪？

  • 磁盘对换区
  • 磁盘外页表：进程页面号与盘块号的对照表

写时复制

  • 进程创建时仅复制父进程的页表，权限为只读。当父进程或者子进程修改页面内容写时复制中断操作系统创建新页(可读可写)，映射到这个进程的地址空间。父进程子进程一开始拷贝了页表，共享了数据内存。修改了数据之后就会分家，发生复制

请求分段存储管理

  • 当作业被调度投入运行时，首先把当前需要的一段或几段装入主存
  • 如果请求段不在内存中缺段中断
  • 中断处理程序调入请求段
    • 需要连续的存储区域
    • 空闲内存足够，但不连续移动
    • 空闲内存不够对换不用的段

image.png

段式存储

  • 优点：基于用户程序结构的存储管理技术，有利于模块化程序设计，便于段的扩充、动态链接、共享和保护
  • 缺点：产生碎片，内存利用率不高

页式存储

  • 优点：基于系统存储器结构的存储管理技术, 存储利用率高,便于系统管理
  • 缺点：不易实现存储共享、保护和动态扩充

段页式存储管理:结合两者的优点，先分段再分页

  • 虚地址以程序的逻辑结构划分成段
  • 实地址划分成位置固定、大小相等的页框(段页式存储管理的页式特征)
  • 逻辑地址->线性地址->物理地址

逻辑地址：
image.png
作业表：登记进入系统中的所有作业及该作业段表的起始地址 （PCB链表）
段表：至少包含这个段是否在主存，以及该段页表的起始地址
页表：包含该页是否在主存(中断位)、对应主存块号
image.png

真实
image.png
image.png
image.png

全局描述符表(GDT)

  • 只有一个

局部描述符表(LDT)

  • 每个进程有一个

每个描述符表含有8192个描述符
段内偏移量32bit->段长最大为4G
整个虚拟地址空间为819224G=64TB

image.png

非一致存储结构(NUMA)

  • 物理存储空间包含多种存储单元，访问速度不一致
  • Linux 2.4支持NUMA
  • 引入存储节点概念：访问时间相同的存储空间称为一个“存储节点”
  • 连续的物理页面应该分配在相同的存储节点上

Linux将物理主存分为三个层次管理：存储节点(node), 管理区(zone)、页框

image.png