操作系统课堂笔记1:内存管理

shell 面向应用程序,对外暴露的接口

kernel 面向内部,管理内部资源
特征:

  1. 并发(一段时间内有多个程序运行)、并行(一个时间点有多个程序运行,需要多个CPU)
  2. 共享(分时法,一个时间点上只有一个程序跑。“同时”访问、互斥共享)
  3. 虚拟
  4. 异步(即使异步,结果也是一致的)

操作系统管理硬件,
主要三大块:
CPU(CPU调度、进程/线程管理) => 进程
内存(物理、虚拟) => 地址空间
磁盘(文件管理) => 文件

中断、IO/设备驱动

什么是操作系统

功能
控制程序
提供服务
管理外设、资源分配


启动

cpu、内存、IO
硬盘放BootLoader、OS -> BIOS(基本I/O处理系统)

BIOS 从特定地址开始执行
CS:IP = 0xf000:fff0
cs段寄存器,ip指令寄存器
一加电,bios就从这个地址开始执行 -> 自检 -> BootLoader

BootLoader一般放到第一个硬盘的主引导扇区。

X86为例
0x7c00

与外设和程序交互
操作系统的接口,总的可以概括为三个
面向外设,通过中断、IO
面向应用程序,通过 系统调用、异常、中断

系统调用(来源于应用程序)
应用程序 主动 向操作系统发出服务请求

异常(来源于不良的应用程序)
非法指令或者其他坏的处理状态(如:内存出错)程序意想不到的行为

中断(来源于外设)
来自不同硬件设备的计时器和网络中断

计算机为什么不能直接操作硬件?

安全角度:
系统是可信任的应用程序
普通程序不一定

使用角度:
操作系统提供统一的接口,屏蔽硬件差异

来源
中断:外设
异常:不良的应用程序
系统调用:应用程序

处理时间
中断:异步(不知道什么时候会产生)
异常:同步(执行指令时会产生)
系统调用:异步或同步

响应
中断:持续,对用户应用程序是透明的
异常:杀死或者重新执行
系统调用:等待和持续

中断和异常的处理机制

中断表:kv表
key=地址
中断 -> 保存和恢复

中断

分两部分完成

硬件

设置中断标记(CPU初始化)
1.将内部、外部事件设置中断标记
2.中断事件的ID(发给操作系统,操作系统找到对应的处理地址)

软件

保存被打断的执行线程(便于后面的恢复)
中断服务程序处理
清理中断标记
恢复之前保存的处理状态

异常

异常编号(地址、寄存器的内容)
异常处理

  • 杀死产生了异常的程序
  • 重新执行异常指令(服务弥补 -> 恢复现场 ->重新执行异常指令)
    恢复现场

系统调用

接口

Win32 API

POSIX API(UNIX、LINUX、Mac OS X)

Java API 用于JVM

设计实现
程序调用系统接口后,状态从用户态转换到内核态。
用户态:CPU特权级低
内核态:CPU完全控制整个计算机系统

系统调用和函数调用的区别?
函数调用,完成在一个栈空间
系统调用,应用程序和内核有各自的堆栈(转换会有额外的开销(代价),换来的是确保系统安全正确的运行)

开销:
异常、中断正常处理(系统调用号、中断号,用表建立关系)
堆栈的保存和恢复
操作系统对参数进行检查
数据从内核态转到用户态
内存状态的转变

物理内存管理

计算机体系结构(计算机原理课)/内存分层体系

CPU
寄存器
L1缓存
L2缓存

|
v

内存(主存)

|
v

硬盘

金字塔结构

外设(I/O)

内存管理,操作系统完成的任务

  • 抽象(逻辑地址空间)
  • 保护(独立地址空间)
  • 共享(访问相同内存)
  • 虚拟化(更多的地址空间)

管理内存的不同方法

程序重定位
分段
分页
虚拟内存
按需分页虚拟内存

实现高度依赖于硬件

必须知道内存架构
MMU(内存管理单元):硬件组件负责处理CPU的内存访问请求

地址空间&地址生成

定义
物理地址空间,内存、硬盘
逻辑地址空间(程序看到的(一维的))

生成(逻辑地址空间)

  1. C里函数的位置、变量的名字其实就是一个地址(逻辑地址)
  2. 汇编程序 贴近机器,符号代表变量和函数的名字(逻辑)
  3. 机器语言(.o 文件),起始地址都是从0开始的,将变量符号名和函数符号名转换为地址。地址是相对从0开始的连续地址空间(逻辑)
  4. 程序间的调用,通过link工具把多个.o程序变成一个单一的程序。地址做了全局的分布,地址还是在硬盘中的
  5. loader应用程序,把硬盘中的程序放到内存中运行。把逻辑地址进行相应的分配(逻辑地址)

过程不需要操作系统参与。

  1. ALU(计算逻辑单元)
  2. ALU查找逻辑映射表(有,直接拿到物理地址)
  3. 没有去内存中(MMU)找,没?到MMMap中找
  4. 主存通过总线把内存内容交给CPU

操作系统起的作用

建立映射关系
确保地址合法(起始地址、长度)

连续内存分配

内存碎片问题(无法进一步使用的空间)
外碎片(分配单元时未使用的内存)、内碎片(在分配单元中未使用的内存)

简单的内存管理方法:

需求
程序运行时分配连续空间
访问数据时,分配连续的内存空间

算法

首次适配

有3块地址空间,如果应用程序需要n字节,如果找到的第一个空闲块满足应用程序需求,则将其分配给它。

需求

  1. 按地址排序空闲块列表
  2. 分配需要寻找一个合适的分区
  3. 重分配需要检查,看是否能自由分区能合并于相邻的空闲分区

优点:简单、易于产生更大空闲块,向着地址空间的结尾
缺点:外部碎片、不确定性

最佳适配

避免分割大空闲块,最小化外部碎片产生的尺寸
粒度大,差值小

需求

  1. 按尺寸排列的空闲块列表
  2. 分配需要寻找一个合适的分区
  3. 重分配需要搜索及合并于相邻的空闲分区,若有

优点:当大部分分配时小尺寸时非常有效、比较简单
缺点:外部碎片、重分配慢、易产生很多没有的微小碎片

最差适配

为了避免有太多微小的碎片

需求

  1. 按尺寸排列的空闲块列表
  2. 分配很快(获得最大的分区)
  3. 重分配需要搜索及合并于相邻的空闲分区

优点:假如分配是中等尺寸效果最好
缺点:重分配慢、外部碎片、易于破碎大的空闲块以致大分区无法被分配

以上都是简单的算法

压缩式与交换式碎片整理

紧致算法

拷贝

问题
什么时候做?(等待的时候可以)
开销?

交换式碎片整理

使用硬盘

问题
使用那个程序给它换出去?
什么时候做换入换出?(粒度,一个程序)


非连续内存分配:分段

为什么?

避免碎片

优点:

  • 一个程序的物理地址空间是非连续的
  • 更好的内存利用和管理
  • 允许共享代码和数据(共享库等…)
  • 支持动态加载和动态链接

缺点:
管理开销本身

  • 软件方案(开销特别大)
  • 硬件方案

有哪些方法?

分段

程序的分段地址空间
分段寻址方案

更好的分离和管理

逻辑内存里是连续的,物理内存可能是分段的。

好处:
用户代码段和主程序段共享
数据相对隔离
保护机制实现

连续到不连续,需要映射关系

怎么寻?

段访问机制

新概念:一个段:一个内存“块”
一个逻辑地址空间
程序访问内存地址需要:
一个2维的二元组(s,addr)

  • s 段号
  • addr 段内偏移

段表(逻辑 => 物理)【硬件支持的,由操作系统设置段表】
重要的两个东西:段的起始地址,长度限制

段号就是段表的索引

怎么实现?

CPU -> 段号 -> 段表 -> 比对(段的限制和本身表示的地址是否满足,满足合法,不满足,CUP产生异常给操作系统)-> (起始地址+逻辑地址中的偏移量=物理地址)

不足
在分段的映射方法中,每次换入换出内存的都是整个程序,这样会造成大量的磁盘访问操作,导致效率低下。所以这种映射方法还是稍显 粗糙,粒度比较大。实际上,程序的运行有局部性特点,在某个时间段内,程序只是访问程序的一小部分数据,也就是说,程序的大部分数据在一个时间段内都不会被用到。基于这种情况,人们想到了粒度更小的内存分割和映射方法,这种方法就是分页(Paging)。

分页(用的多)

地址空间

区别
段的尺寸是可变的,页帧的大小是固定的

划分:大小是2的幂次方
逻辑地址空间和物理空间大小相同

frame 物理页
pag 逻辑页

建立映射关系

  • 页表
  • MMU(内存管理单元,cpu重要组成)/TLB(快表,完成对页表的缓存)

一个内存物理地址是一个二元组(f,o)

  • f 帧号(F位,共有$2^F$个帧)
  • o 帧内偏移(S位,每帧有$2^S$字节)

物理地址 = $2^S$ * f + o

一个程序的逻辑地址空间被划分为大小相等的页

  • 页内偏移的大小 = 帧内偏移的大小
  • 页号大小 <> 帧号大小

计算方式与帧基本是一致的,区别在于页号size和页帧size可能不一样,每一个页的大小和每一个页帧的大小是一样的

一个逻辑地址是一个二元组(p,o)

  • p 页号(P位,$2^P$个页)
  • o页内偏移(S位,每页有$2^$字节)

虚拟地址 = $2^S$ * p + o $2^n$ - 1 = ($2^P$ - 1, $2^S$ - 1)

实现方式

分段和分页的区别在于:粒度

非连续内存分配:页表、TLB

页表

本质是大数组

结构

分页机制的性能问题
问题:
访问一个内存单元需要2次内存访问

  • 一次用于获取页表项
  • 一次用于访问数据

页表可能非常大
64位机器如果每页1024字节,那么一个页表的大小会是多少? $2^52$

CPU放不下,放内存里

计算机系统解决时间空间问题一般两种办法:

  1. 缓存
  2. 间接访问(如:多级页表)

Translation Look-aside Buffer (TLB)

CPU里的

缓存近期访问的页帧转换表项

  • TLB使用accociative memory(关联内存)实现,具备快速访问性能
  • 如果TLB命中,物理页号可以很快被获取
  • 如果TLB未命中,对应的表项可以被更新到TLB中

非连续内存分配:页表-二级、多级页表

解决空间问题

把大地址分为多个小地址

一级页表项的值是二级页表的起始地址,根据p2作为二级页表的index +一级页表中存的起始地址,找二级页表项的值(帧number)+ 对于的offset(页表和页帧的offset是一样的)

开销大(多次访问),但空间会小(不存在的内存地址在二级页表就可以不必存在),以时间换空间。
时间的开销可以通过TLB缓解

非连续内存分配:页表-反向页表

页表大小和逻辑逻辑空间大小有对于关系:逻辑逻辑空间越大,对于的寻址空间就越多。

有没有办法让他们没有那么大的关系?

大地址空间问题
有大地址空间(64bit),向前映射页表变得繁琐

  • 比如:5级页表

不是让页表与逻辑地址空间的大小相对应,而是让页表与物理地址空间的大小相对应。

  • 逻辑(虚拟)地址空间增长速度快于物理地址空间。

反向页表

基于页寄存器(Page Registers)的方案

以页帧号为索引,页表项的内容是页号。与前面的相反。使得寄存器的容量与物理地址空间大小相同,限制寄存器的数量。

好处:占的空间很少

一个例子

  • 物理内存大小:40964096=4K4KB=16MB
  • 页面大小:4096bytes=4KB
  • 页帧数:4096=4K
  • 页寄存器使用的空间(假设8bytes/register):
  • 8*4096=32Kbytes
  • 页寄存器代理的额外开销:
  • 32K/16M = 0.2%(大约)
  • 虚拟内存的大小:任意

问题:怎么根据页号找到页帧号?

基于关联内存(associative memory)的方案

并行查找

key 页号
value 页帧号

类似TLB

问题:实现成本大

在反向页表中搜索一个页对应的页帧号
如果帧数比较少,页寄存器可以被放置在关联内存中。
在关联内存张查找逻辑页号

  • 成功:帧号被提取
  • 失败:页错误异常(page fault)
    限制因素:
  • 大量的关联内存非常昂贵
  • 难以在单个时钟周期内完成
  • 耗电

基于哈希(hash)查找的方案

hash函数 输入的是页号,输出是页帧号

提高效率,hash函数+PID

问题:

  1. hash碰撞
  2. 放内存中,内存开销还是大,需要一个类似TLB的机制

反向页表在高级CPU中会有出现。


虚拟内存

为何要?
内存不够用

##早期技术

  1. 手动的覆盖技术
  2. 自动的交换技术

自动的虚拟存储技术
更小的页粒度为单位

覆盖技术

890年用的技术

程序员累啊~
开销:程序员设计的开销、换入换出的开销

交换技术

UNIX提供的方法,操作系统重要的组成部分。
swap out、swap in

需要考虑的问题

  1. 什么时候交换:只有当内存空间不够或有不够的危险时换出;
  2. 交换区的大小:必须足够大以存放所有用户进程的所有内存映像的拷贝;必须能对这些内存映像进行直接存取;
  3. 程序换入时的重定位:换出后在换入的内存位置一定要在原来的位置上的?(不一定)最好采用动态地址映射的方法

覆盖技术和交换技术的比较

覆盖只能发生在那些相互间没有调用关系的程序模块之间(一个程序内),因此程序员必须给出程序内各个模块之间的逻辑覆盖结构。
交换技术是以在内存中的程序大小为单位来进行的,它不需要程序员给出各个模块之间的逻辑覆盖结构。换而言之,交换发生在内寸中程序与管理程序或操作系统之间,而覆盖则发生在运行程序的内部。


虚存技术

覆盖技术和交换技术的不满足(覆盖,废程序员、交换,粒度太大!以程序为单位,增加处理器的开销)

目标

  • 像覆盖技术那样的效果,但不需要程序员来做这工作。
  • 像交换技术一样,实现程序在内存与外存之间的交换,但做的更好,只对进程的部分内容(如:页)在内外存之间进行交换。

程序的局部性原理(虚存技术的支持)
指程序在执行过程中的一个叫短期,所执行的指令地址和指令的操作数地址,分别局限于一定区域。
可以表现为:

  • 时间局部性:一条指令的一次执行和下次执行,一个数据的一次访问和下次访问都集中在一个较短的时期内;
  • 空间局部性:当前指令和邻近的几条指令,当前访问的数据和邻近的几个数据都集中在一个较小的区域内。

基本概念

可以在页式或段式内存管理的基础上实现

装入程序时只需要将要执行的部分页面或段装入到内存中,然后就可以执行程序。当缺页/段异常时,操作系统就要将另外的数据装载到内存中,再重新执行异常指令。如果内存不够,操作系统则需要预判哪些数据将暂时不使用,将其放到外面去,腾出需要的空间。

基本特征

  • 大的用户空间:物理内存空间+硬盘
  • 部分交换
  • 不连续行:物理内存分配的不连续,虚拟地址空间使用的不连续。

虚拟页式内存管理

大部分虚拟存储系统采用虚拟页式存储管理技术,即在页式存储管理的基础上,增加 请求调页页面置换功能。

基本思路:

  • 当用户程序需要调入内存运行时只装部分的页面
  • 当运行过程中发行需要访问的数据不存在,CPU产生缺页中断交给操作系统处理,数据放回内存后重新执行错误的指令。
  • 页面越来越多,不够用了,就需要把一些页(不常用)给替换出去。

页表项

逻辑页号+访问位+修改位+驻留位+物理页帧号

  • 驻留位:表示改页是否在内存中,1存在、0不存在产生缺页中断。
  • 保护位:表示允许对该页的访问权限,如只读、可读写、可执行等。
  • 修改位:表明此页在内存中是否被修改过。当系统回收该物理页时,根据此位来决定是否把它的内容回写外存。
  • 访问位:如果该页面被访问过(包括读操作或写操作),则设置此位。用于页面置换算法。

缺页中断

缺页中断处理过程:

  1. 如果内存中有空闲的物理空间,则分配一物理页帧f,然后转第4步;否则转第2步;
  2. 采用某种页面置换算法,选择一个将被替换的物理页帧f,它对应的逻辑页在内存期间被修改过,则需把它写回外存;
  3. 对q所对应的页表项进行修改,把驻留位置为0;
  4. 将需要访问的页p装入到物理页面f当中;
  5. 修改p所对应的页表项的内容,把驻留位置为1,把物理页帧号置为f;
  6. 重新运行被中断的指令。

后备储存 Backing Store(二级存储)

在何处保存未被映射的页?

  • 能够简单地识别在二级存储器中的页
  • 交换空间(磁盘或文件):特殊格式,用于存储未被映射的页面

概念:

  • 一个虚拟地址空间的页面可以被映射到一个文件(在二级存储中)中的某个位置
  • 代码段:映射到可执行二进制文件
  • 动态加载的共享库程序段:映射到动态调用的库文件
  • 其他段:可能被映射到交换文件(swap file)

虚拟内存性能

为了方便于理解分页的开销,使用有效存储器访问时间 effective memory access time(EAT)

  • EAT = 访存时间 * 页表命中几率 + page fault处理时间 * page fault几率

例子:
访存时间:10ms
磁盘访问时间:5ms
参数p = page fault几率
参数q = dirty page几率
EAT = 10(1-p)+5000000p(1+q)


页面置换算法

  • 局部页面置换算法
    • 最优页面置换算法(OPT, optimal)
    • 先进先出算法(FIFO)
    • 最近最久未使用算法(LRU,Least Recently Used)
    • 时钟页面置换算法(Clock)
    • 最不常用算法(LFU,Least Frequently Used)
    • Belady现象
    • LRU、FIFO和Clock的比较
  • 全局页面置换算法
    • 工作集模型
    • 工作集页置换算法
    • 缺页率置换算法

局部页面算法

针对一个进程

功能目标

  • 功能:发生缺页中断时,调入新的页面时内存已满时,需要选择内存中的哪个物理页面被置换。
  • 目标:尽可能减少页面的换进换出(即缺页中断的次数)通常只能在局部性原理指导下依据过去的统计数据来进行预测;
  • 页面锁定(frame locking):用于描述必须常驻内存的操作系统相关的关键部分或时间关键(time-critical)的应用进程。实现的方法是:在也飙中添加锁定标志位(lock bit)。

最优页面置换算法

  • 基本思路:缺页中断发生时,对于保存在内存中的每一个逻辑页面,计算在它 下一次访问之前,还需等待多长时间,从中选择等待最长的那个,作为被置换的页面。
  • 这只是理想情况,在实际系统中是无法实现的,因为操作系统无从知道每一个页面需要等待多长时间以后才会再次被访问。
  • 可作其他算法的性能评价的依据(在一个模拟器上运行某个程序,并记录每一次的页面访问情况,在第二遍运行时即可使用最优算法)。

先进先出算法

  • 基本思路:选择在内存中驻留最长的页面并淘汰之。具体来说,系统维护着一个链表,记录了而所有位于内存当中的逻辑页面。从链表的排列顺序来看,链首页面的驻留时间最长,链尾页面的驻留时间最短。当发生一个缺页中断时,把链首页面淘汰出局,并把新的页面添加到链表的末尾。
  • 性能较差,调出的页面有可能是经常访问的页面,并且有 Belady现象。FIFO算法很少单独使用。

最近最久未使用算法(Least Recently Used, LRU)

  • 基本思路:当一个缺页中断发生时,选择最久未使用的那个页面,并淘汰之。
  • 它是对最优页面置换算法的一个近似,其依据是程序的局部性原理,即在最近一小段时间(最近几条指令)内,如果某些页面被频繁地访问,那么将来的一小段时间内,它们还可能再一次被频繁地访问。反过来说,如果在过去某些页面长时间未被访问,那么在将来它们还可能会长时间地得不到访问。
  • 需要记录使用顺序,开销比较大(并不是有效的方法)
    • 算法,链表,淘汰末端。
    • 堆栈,访问某页时,将页号压入栈顶,然后,考察栈内是否有与此页面相同的页号,若有则抽出。当需要淘汰一个页面时,总是选栈底的页面,它就是最久未使用的。

时钟页面置换算法

Clock页面置换算法,LRU的近似,对FIFO的一种改进;
基本思路:

  • 需要用到页表项当中的 访问位,当一个页面被装入页内存时,把该位初始化为0.然后如果这个页面被访问(读/写),则把该位置为1;(由CPU设置,操作系统会定期的清零
  • 把各个页面组织成环形链表(类似钟表面),把指针指向最老的页面(最先进来);
  • 当发生缺页中断时,考察指针所指向的最老页面,若它的访问位为0,立即淘汰;若为1,则把该位置置为0(手动),然后指针往下移动一格。如此下去。直到找到被淘汰的页面,然后把指针移动到它的下一格。

二次机会法

Clock页面置换算法有一个巨大的代价来替换“脏”页。

程序在内存中修改了数据,替换时需要将数据保存到硬盘才能将其换出,如果是只读数据,内存数据和硬盘数据一致,则可以直接释放。

修改Clock算法,使它允许脏页总是在一次时钟扫描中保留下来

  • 同时使用 脏位使用位来指导置换。

如果两页都是11,则它有两次机会。

只读页被优先替换,被写的页则最多有两次机会被保留。

最不常用法(Least Frequently Used, LFU)

  • 基本思路:当一个缺页中断时,选择访问次数最少的那个页面,并淘汰之。
  • 实现方法:对每个页面设置一个访问计数器,每当访问时该页面的访问计数器加1.发生缺页中断时,淘汰技术值最小的那个页面。(访问次数

缺点:假如程序初始化时对某个数访问了很多次,但后面用的就很少了,然而它的次数仍是最大的,就一直被保留。
改进:将访问次数随着时间的推移而把次数寄存器右移一位。


Belady现象

FIFO
Belady现象:在采用FIFO算法时,有时会出现分配物理页面数增加,缺页率反而提高的异常现象;
现象原因:FIFO算法的置换特征与进程访问内存的动态特征时矛盾的,与置换算法的目标是不一致的(即替换较少使用的页面),因此,被它置换出去的页面并不一定是进程不会访问的。

LRU
为什么LRU算法比FIFO算法优?
LRU符合 栈算法特点140

LRU、FIFO和Clock的比较

LRU和FIFO本质上都是先进先出的思路,LRU比FIFO多记录了使用使用时间,而FIFO只是记录了进入内存的时间。Clock是LRU的近似。

程序的局部性很相关,如果程序不具有局部性,那么LRU算法就可能退化为FIFO算法!

Clock利用硬件属性(使用位)将LRU需要独立维护的表给替换,时间相对没那么准确。本质上类似LRU算法,开销小、效果逼近LRU。


全局页面置换算法

操作系统支持多进程,每个进程使用固定的局部算法,则会带来问题。

工作集模型

前提 程序具有局部性

工作集:一个进程 当前正在使用的逻辑页面集合,可以用一个二元函数W(t,Δ)来表示:

  • t是当前的执行时刻;
  • Δ称为工作集窗口(working-set window),即一个定长的页面访问的时间窗口;
  • W(t,Δ)=在当前时刻t之前的Δ时间窗口当中的所有页面所组成的集合(随着t的变化,改集合页在不断地变化);
  • |W(t,Δ)|指工作集的大小,即页面数目。

常驻集模型

是指在当前时刻,进程实际驻留在内存当中的页面集合。

  • 工作集是进程运行过程中固有的性质,而常驻集取决于系统分配给进程的物理页面数目,以及所采用的页面置换算法;
  • 如果一个进程的整个工作集都在内存中,即常驻集 <= 工作集,那么程序将很顺利地运行,而不会造成太多的缺页中断(直到工作集发生剧烈变动,从而过渡到另一个状态);
  • 当进程常驻集的大小达到某个数目之后,再给它分配更多的物理页面,缺页率也不会明显下降。

两个全局置换算法

工作集页置换算法

缺页率页面置换算法

可变分配策略:常驻集大小可变。

  • 可采用全局页面置换的方式,当发生缺页中断时,被置换的页面可以时在其他进程当中,各个并发进程竞争地使用物理页面。
  • 优缺点:性能好,但增加了系统开销。
  • 具体实现:可以使用缺页率算法(PFF,page fault frequency)来动态调整常驻集的大小。

缺页率=缺页次数/内存访问次数(比例)或缺页的平均时间间隔的倒数。

影响缺页率的因素:

  • 页面置换算法
  • 分配给进程的物理页面数目
  • 页面本身的大小
  • 程序的编写方法

一个交替的工作集计算明确的试图最小化页缺失

  • 当缺页率高的时候 - 增加工作集
  • 当缺页率低的时候 - 减少工作集

算法:
保持追踪缺失发生概率
当缺失发生时,从上次页缺失起计算这个时间记录这个时间,tlast是上次的页缺失的时间。
如果发生页缺失之间的时间是“大”的,之后减少工作集。
如果 tcurrent - tlast > T,之后从内存中移除所有在【tcurrent tlast】时间内没有被引用的页。
如果这个发生页缺失的时间是“小”的,之后增加工作集。
如果tcurrent - tlast ≤ T,之后增加缺失页到工作集中。

只在中断的时候才会判断是否需要调整工作集


抖动问题

物理页面太少,大量的要用内存在外面,产生很多缺页中断,操作系统需要频繁的IO操作,从而使程序的运行速度变得很慢,这种状态成为“抖动”。

改善:
调整MPL
平均缺页时间(MTBF) = 页缺失服务时间(PFST)

MTBF
____ = 1
PFST