操作系统导论 - 虚拟化
1. 关于本书的对话
忽略~
2. 操作系统介绍
程序执行过程:执行指令,分三步,1)获取指令;2)解码;3)执行。
本书主要内容:虚拟化CPU、虚拟化内存、并发持久化。
3. 关于虚拟化的对话
忽略~
4. 抽象:进程
进程:运行中的程序,拥有独立的资源,如内存、寄存器等。
进程API:create、destroy、wait、miscellaneous control(其他控制)、status
程序加载过程:
加载:程序到进程.png
进程状态:running、ready、blocked
进程:状态转化.png
进程数据结构:
xv6 的 proc 结构.png
用于上下文切换(context switch)时,保存和恢复进程。上下文切换很重,除了保存寄存器内容,如TLB、CPU缓存、分支预测等优化都失效。
5. 插叙:进程API
fork:创建进程
exec:执行进程
wait:等待其他进程执行
6. 机制:受限直接执行
主要挑战:性能和控制权
受限直接执行:
无限制部分:
受限制部分:通过初始化陷阱表,执行陷阱,从用户态内陷到内核态,交给操作系统执行
受限制直接执行.png
在进程之间切换:
- 协作方式:等待系统调用。假定程序任务完成后,会自动进行系统调用,把控制权交给系统,如果存在恶意程序,不交出控制权,无能为力。
- 非协作方式:操作系统进行控制。通过时钟中断(timer interrupt),产生时钟中断时,程序将执行权交给操作系统,操作系统中预先配置的中断处理程序(interrupt handler)会执行。操作系统停止老的程序,执行其他程序。
保存和恢复上下文:
首先直接执行协议(时钟中断)
7. 进程调度:介绍
周转时间:T周转时间=T完成时间-T到达时间
FIFO(first in first out,先进先出):先进的是大任务,后进的是小任务,则平均周转时间长
FIFO调度.png
SJF(shortest job first,最短任务优先):可解决同时达到问题,但无法解决小任务在大任务后达到问题
SJF调度
STCF(shortest time-to-completion first,最短完成时间优先):无法解决任务执行时间无法预测问题
STCF调度
响应时间:T响应时间=T首次执行-T达到时间
RR(rotation-robin,轮转):按照时间片轮转执行。响应时间好,但周转时间差。
结合I/O:
结合I/O:重叠执行
8. 调度:多级反馈队列
MLFQ(Multi_level Feedback Queue):多级反馈队列。
解决两个问题:1)优化周转时间;2)降低响应时间。
基本规则:
规则1:如果A的优先级>B的优先级,运行A;
规则2:如果A的优先级=B的优先级,轮转运行A和B。
尝试改变优先级:
规则3:工作进入系统时,放在最高优先级队列;
规则4a:用完整个时间片后,降低其优先级;
规则4b:如果工作在用完整个时间片前主动放弃CPU,则优先级不变。
存在两个问题:1)饥饿问题:低优先级任务无法获取时间片;2)被程序利用机制,时间片快用完时主动放弃时间片,从而一直保持在高优先级。
提升优先级:
规则5:经过一段时间S,就将系统中所有任务都重新加到最高优先级。
但S很难设置,被称为“恶毒常量(voo-doo constant)”
更好的计时方式:
为了解决被程序愚弄,优化计时,重写规则4。
规则4:一旦一个任务用完了在某一层的时间配额(不论是否主动放弃),则自动降低其优先级。
9. 调度:比例调度
基本概念:彩票数表示份额,一个进程持有的彩票数占总彩票的比例,就是其拥有资源的比例。
其优势是具有随机性,随机性的有点:1)可以避免边角问题,如LRU替换策略无法解决重复序列的问题;2)随机性具有轻量级,无需记录每个任务使用资源的总时间;3)随机性具有性能高的优点。
彩票机制:
- 彩票货币:资源持有的彩票数可以分给子任务,子任务的彩票数可以转换成全局的彩票数
- 彩票转让:可以临时将资源转让给其他进程
- 彩票通胀:一个进程可临时减少或增加自己的彩票数
实现:通过简单的遍历链表,对链表的彩票数做加法运算,第一个求和不小于随机彩票数的任务获得执行权。如下图,假设随机生成的彩票数为300,遍历到A时,和为100,小于300,继续遍历;遍历到B时,和为150(100+50),仍小于300,继续遍历;遍历到C时,和为400,大于随机彩票数,C获得执行权。
彩票链表
可优化成彩票数递减的链表,减少遍历次数
如何分配彩票:对于给定的一组任务,彩票分配的问题没有最佳机制
彩票机制的问题:在短时间内无法保证随机性。可将彩票数转换成每个任务固定步长调度可缓解。假设有三个任务A、B、C,原先各自的彩票数分别为100、50、200,则转换后每个任务的步长为100、200、40。
执行规则为:1)初始任务的计数器为0;2)每次执行计数器最小的任务;3)每次执行任务后,该任务的计数器增加其步长。
一种执行结果如下:
固定步长算法
固定步长算法的缺点是需要全局状态,每个任务都需要记录其计数器的数值。
彩票调度和步长调度因为其彩票数难确定、不能很好的适用于I/O,因此未能很好的推广。
10. 多处理器调度(高级)
多处理器每个处理器都有缓存,有缓存一致性问题。
在基于总线的系统中,可通过总线窥探(bus snooping)的方式解决。每个缓存都通过监听链接所有缓存和内存的总线,来发现内存访问。当缓存的数据被更新时,会作废本地缓存,或更新缓存。
在访问共享数据时,需对数据做加锁同步,否则会出现异常结果。
缓存亲和度问题:进程在CPU上执行时,会在CPU的缓存中维护很多状态。CPU下次再执行该进程时,因有缓存状态,可加快执行速度。多处理器应该考虑缓存亲和度问题,同一进程应在同一个CPU上执行。
单队列多处理器调度(SQMS,Single Queue Multiprocessor Schedule):
- 优点:很少的修改就可应用于多处理器
- 缺点:
- 缺乏扩展性:队列是共享数据,需对其加锁来保证原子性。锁的性能损耗大;而且在CPU变多时,竞争带来的时间开销增加,真正处理进程任务的时间减少。
-
缓存亲和度问题:假设任务有5个。
进程队列
可能的进程调度如下,与缓存亲和度背离:
可能的进程调度
为了解决这个问题,大部分SQMS调度程序都引入一些缓存亲和度机制,尽可能的让进程在同一CPU上执行,可能会牺牲其他进程的缓存亲和度。
缓存亲和度机制
多队列多处理器调度(MQMS,Multi-Queue Multiprocessor Schedule):每个CPU一个任务队列,任务加入可通过随机加入队列,或选择负载最小的队列加入。假设4个进程,2个CPU的情况:
4个进程2个CPU
可能调度过程如下:
MQMS潜在调度
MQMS具有扩展性,也满足缓存亲和度,但存在负载不均的问题。假设上述情况,C提前执行完毕,则目前有3个进程,2个CPU,如下:
3进程2CPU
潜在的调度过程如下:
image.png
A进程的时间片是B和D的2倍。假设A很快执行完,则CPU0空闲,CPU1执行B和D两个进程,存在严重的负载不均衡问题。
可以通过迁移的方式解决负载不均衡问题,
如果B和D在CPU1的队列上,CPU0的队列为空,可将B进程迁移到CPU0的队列上。
但如果是CPU0队列上存在A,CPU1队列上存在B和D,单次迁移不能解决问题,可通过多次迁移解决,不断将B在CPU0和CPU1的队列上迁移。
如何发起迁移?可通过工作窃取(work stealing)的方式实现。工作量上的CPU可不断“偷看”其他队列是否满,如果更满,则触发任务迁移。
工作窃取的方式仍存在问题,如果检查时间长,则仍存在负载不均衡的问题;如果检查时间短,则可能会导致共享数据竞争,降低系统的扩展性。
Linux调度算法:Linux社区一直未达成共识,存在三种调度算法: Q(1)调度程序、完全公平调度程序(CFS)、BF调度程序(BFS)。
Q1和CFS采用多队列,BFS采用单队列。Q(1)调度程序基于优先级,类似MLFQ;CFS采用确定的比例调度,类似步长调度;BFS也采用比例调度,但采用更复杂的调度算法,称为最早最合适虚拟截止时间优先算法(EEVEF)
11. 关于CPU虚拟化总结对话
忽略~
12. 关于内存虚拟化对话
忽略~
13. 抽象:地址空间
早期系统:操作系统实际是一组函数,在内存中。然后是运行的程序,使用剩余内存。
早期操作系统
多道程序和时分共享:未执行的进程程序和数据仍在内存中。
3个进程在:共享内存
地址空间:操作系统虚拟化内存,提供易用的物理内存抽象。
地址空间的例子
目标:
- 透明(transparency):进程感知不到内存被虚拟化,每个进程都好像拥有私有内存
- 效率(efficiency):内存虚拟化应尽可能保持空间和时间上的高效
- 保护(protection):进程之间相互隔离,互相不影响
程序打印出来的都是虚拟地址,地址都从0开始增长,真实的地址会在执行时,由操作系统将虚拟地址转换成机器中的真实地址
14. 插叙:内存操作API
栈内存:其申请和管理由编译器隐形完成,称为自动内存。进入函数时,编译器在栈上开辟空间;函数退出时,编译器自动释放内存。
占内存
堆内存:C语言中,malloc()方法分配,free()方法释放
15. 机制:地址转换
在CPU虚拟化时,一般遵循受限直接访问(Limited Direct Execution,LDE)。LDE的是思想是让程序运行时的大部分指令直接访问硬件,只在一些关键点(如发起系统调用或时钟中断)由操作系统介入。为了实现高效的虚拟化,操作系统应该尽量让程序自己运行,同时通过关键点的及时介入(interposing),来保证对硬件的控制。
虚拟内存追求的目标:
- 高效:要利用硬件的支持
- 控制:程序只能访问自己的内存空间
- 灵活:程序能以任何方式访问自己的地址空间
一种通用的技术是基于硬件的地址转换(hardware-based address translation),简称地址转换(address translation)。
程序的虚拟内存假设占用16KB,其虚拟地址如下:
程序虚拟地址
但在物理内存中,程序的地址不可能都从0开始,其真实地址可能是32-48KB内存空间。
物理内存
虚拟地址需要通过某种方式转换得到真实的物理地址。
动态(基于硬件)重定位:
提供两个硬件:基址(base)寄存器和界限(bound)寄存器,一般把负责地址转换的部分称为内存管理单元(Memory Management Unit,MMU)。基址寄存器记录程序的起始地址,界限寄存器记录程序所占内存的大小。虚拟地址转换成物理地址的算法如下:
physical address = virtual address + base
存在两种CPU模式:
- 特权模式(privilege mode,内核模式,kernel mode):操作系统可以访问所有机器资源;
- 用户模式(user mode):应用程序只能做有限的操作。
动态重定位:硬件要求只要一位就能区分CPU的模式,保存在处理器状态字(processor status word)。
硬件提供:- MMU:基址寄存器和界限寄存器
- 特殊指令:进程切换时,改变基址寄存器和界限寄存器的值(只在内核态,由操作系统修改)
- 在用户非法访问时,CPU必须产生异常(exception),安排操作系统的异常处理器(exception handler)去处理。
续表
16. 分段
将进程的整个地址空间加载到一整块内存区域,存在两个问题:
- 堆和栈之间有很大的空间未被利用,空间浪费严重
如果地址空间是4G,一般进程通常只占几兆
- 如果剩余空间充足,但不连续时,进程无法运行
分段:泛化的基址/界限
在MMU中引入多个段,每个段占用连续的地址区域。假设分为代码、堆、栈3个段,则需要3个基址寄存器和3个界限寄存器。
分段物理内存
分段寄存器
通过虚拟地址的前几位标识所属段,剩余后几位作为偏移量。假设3个段时,可用2位标识端地址:
虚拟地址
在计算段和便宜量时,可通过与和右移减少计算量。
图中,SEG_MASK 为0x3000,SEG_SHIFT 为12,OFFSET_MASK 为0xFFF。
寻址算法
上图中栈反向增长,需要特殊位标识增长方向:
栈寄存器(支持反向增长)
支持共享,代码共享非常常见。通过保护位(protection bit)实现:
段寄存器(有保护)
细粒度和粗粒度分段:上述例子中只有3个段,属于粗粒度分段。早期机器中,有些可支持成千上万的段。
操作系统支持:
- 上下文切换时,保存切出进程的分段信息,恢复获得执行权进程的分段信息
-
管理空闲地址空间。一般会遇到很多空闲空间的小洞(外部碎片,external fragmentation),有段需要分配时,整体空间足够,但空间不连续,导致无法分配。
如图空闲空间有24KB,假设有个段需要申请20KB空间,因每个空闲空间都无法满足,空间分配失败。
非紧凑的
通常的解决方案:
- 紧凑(compact)物理内存:终止在运行的程序,数据复制到连续的空间中,并修改段寄存器的值,从而获得更大的连续内存。但拷贝段属于内存密集型操作,效率低
- 空间列表管理算法,试图保留大的地址空间用于分配,算法包括最优匹配(best-fit)、最坏匹配(worst-fit)、首次匹配(first-fit)和伙伴算法(buddy algorithm)
段的问题:
- 内存中分配不同大小的段,会导致外部碎片,需要定期规整内存空间,内存管理困难
- 不足以支持更一般化的稀疏地址空间问题。假设一个很大但稀疏的堆,都在一个逻辑段中,整个堆仍需要全部加载到内存中
17. 空间空闲管理
本章讨论外部碎片,且假设用户进程申请到的是连续空间,且分配后不会再要求增加堆空间。
底层机制:
-
分配与合并:假设有30字节的空间,10-20之间的空间被占用,此时空闲列表如下:
空闲列表
如果10-20之间的空间被释放,需对空间合并,空闲空间变成0-30。
空闲空间合并 -
追踪已分配空间的大小
在free(void *ptr)时,仅传入指针,未指定要释放空间大小。一般空间分配时,会在分配空间之前加上头块(header),用于存储空间大小等信息,一般还包括魔数等,简化后的实例如下:
简化的头块
分配空间(带头块) -
嵌入空间列表
简化后的空闲空间列表结构如下:
typedef struct node_t {
int size;
struct node_t *next;
} node_t;
进程可通过mmp()
向操作系统申请内存空间。
假设剩余空间是连续的4KB,系统申请100字节,header占8字节,空间过程如下:
空间分配
假设又分配两个100字节的空间,分配后的结果如下:
空闲空间和3个已分配块
假设释放中间的块,中间块加入到头部:
释放中间块
- 让堆增长:通过
sbrk
申请
基本策略:
- 最优匹配:遍历一遍空闲列表,找到和请求大小一样,或者更大列表中最小的块。遍历的查找成本高。
- 最差匹配:找到最大的块分配,需遍历整个列表。除遍历成本外,其会产生大量碎片
- 首次匹配:首次匹配到足够大的块即分配。表头很容易产生大量小块
- 下次匹配:第二次匹配到的分配,避免对表头的频繁分割
- 分离空闲空间(segregated list):如果某个程序经常申请一种(或几种)大小的内存空间,就用一个独立列表,专门管理这样大小的对象,可有效减少碎片,且分配和释放速度快
- 伙伴系统:对空闲空间都一分为二,直到最小可适配空间大小。可更快的合并空闲(兄弟节点只有一位不同,其他都相同)。
18. 分页:介绍
空间管理主要有两种:
- 不同长度的分片,容易产生碎片
- 固定长度的分片,一般称为分页。不再以分段的形式管理内存,分页把物理内存看成定长槽块的阵列,叫做页帧(page frame),每个页帧对应一个虚拟内存页。
假设虚拟地址共64字节,每16字节为1页,共4页。物理地址共128字节,每16字节1页,共8页。虚拟页和物理页帧的对应关系假设为VP0->PF3,VP1->PF7,VP2->PF5,VP3->PF2,空间分布如下:
虚拟地址页和物理地址页分布
虚拟页和物理页帧的对应关系记录在页表(page table),页表的主要作用是为地址空间的每个虚拟页面保存地址转换(address translation)。
虚拟地址结构:
虚拟地址由VPN(虚拟页面号,Virtual Page Number)和偏移量(offset)组成,上述例子64位需要6字节,4个虚拟页面,VPN2位,偏移量4位。
虚拟地址
假设虚拟地址为21,转换成6位为010101,VPN为01,对应的PFN为7,偏移量为0101。
地址转换过程
页表存储:
因页表空间较大,真实32位操作系统,假设虚拟页20位,每个PTE(页表项,Page Table Element)占4字节,每个进程需要4M页表空间,假设操作系统同时运行100个进程,则页表需要400M。页表未存储在类似MMU(内存管理单元,Memory Management Unit)的硬件中,而是存储在内存中。
页表中的数据:
- 页表结构:页表存储VP到PF对应关系的数据结构列表,假设使用线性页表(linear page table)存储映射关系,使用数组实现,通过VPN可获取数组下标,即可获取PTE。线性列表存在空间浪费问题,19章会用多级页表的树形结构存储。
-
PTE结构:PTE中存在不同位。有效位(valid bit)指示当前PTE的转换是否有效。保护位(protection bit),表明页是否可读、写、执行。存在位(present bit)表示该页在内存中,还是被已经被交换到磁盘中。脏位(dirty bit)表示页表被带入内存中,是否被修改。参考位(reference bit,访问位accessed bit)追踪页面是否被访问,可确定页面被访问频次,页面替换时(page replacement)会用到这个数据。
image.png
页表不仅占用内存大,而且会导致程序执行变慢,每次获取地址数据时,需要两步:
- 先获取页表,通过转换得到真实的物理地址
- 通过真实的物理地址,获取该地址上的数据
页表存在页表基址寄存器(page-table base register)中,转换如下: 页转换算法
综上所述,上述线性页表的方式存在两个问题:
- 占用内存空间大
- 执行效率低
19. 分页:快速地址转换(TLB)
页表存储在内存中,导致每次地址访问都需要一次额外的内存访问。操作系统借助地址转换旁路缓冲存储器(translation-lookaside buffer,TLB)硬件,缓存部分页表,从而减少绝大多数从内存中获取页表的操作,加速执行效率。
TLB基本算法:
- 从虚拟地址中提取VPN,再从TLB中查找是否存在VPN的转换映射,如果存在,则直接使用,转换得到真实的PF;否则继续执行,
-
如果TLB未命中,硬件访问页表找到映射关系,更新到TLB中。TLB更新后,程序通过TLB获得映射关系,转换得到真实的PF
TLB控制算法
示例:访问数组:
在访问a[0]、a[3]、a[7]时需要额外访问一次内存,其他不需要,TLB缓存命中率70%。
image.png
如何处理TLB未命中:
以前硬件有复杂的指令集(复杂指令集计算机,Complex-Instruction Set Computer,CISC)不信任操作系统,硬件负责获取页表转换,并更新到硬件管理的TLB(hardware-management TLB)中。现代的体系结构都是精简指令集计算机(Reduced-Instruction Set Computer,RISC),有软件管理TLB(software-management TLB)。TLB未命中时,硬件抛出一个异常,暂停当前的指令流,将特权升级到内核模式,跳转到陷阱处理程序(trap handler)。不同于以往的陷阱,返回后执行后一个指令;TLB未命中陷阱返回后,硬件必须从导致陷阱的指令继续执行,因为映射关系已经属性到TLB中,重试会命中
image.png
TLB未命中需注意无限递归的问题,一种解决方案是将TLB未命中陷阱处理程序直接放到物理内存中(他们没有映射过,不用经过地址转换);或者在TLB中保留一些项,记录永久有效的地址转换,并将其中一些永久地址转换槽块留给处理代码本身,这些被监听的(wired)地址转换总是会命中TLB。
TLB内容:
VPN | PFN | 其他位
其他位包含有效位、保护位等。
上下文切换时对TLB的处理:
一种方式上下文切换时,清空TLB,但会导致下一次执行时重新更新TLB,执行效率低。
为了减少开销,一些系统增加硬件支持,通过在TLB中增加地址空间标识符(Address Space Identifier,ASID),实现跨上下文切换的TLB共享。
image.png可以把ASID看做进程标识符(Processor Identifier,PID),但通常比PID位数少,PID一般32位,ASID一般8位。
为了能标识当前进程,在上下文切换时,需将某个特权寄存器设置为当前进程的ASID。
TLB替换策略:
在讨论页换出到磁盘的问题时会详细讨论。常见的策略有最近最少使用(least-recently-used,LRU)和随机(random)策略,LRU看似合理,但在TLB有n个,循环长度为n+1的极端情况下,LRU表现极差。
实际系统中的TLB表项:
image.png
20. 分页:较小的表
19章解决了访问效率问题,但线性页表的内存空间占用大的问题仍无法解决。
简单的解决方案:更大的页
一般32位内存,页12位,页表20位。如果增加页大小到14位,则页表减少到18位,页表大小变成原来的1/4(218/220=1/4)。但页过大会导致内部碎片(internal fragmentation)问题。
混合方法:分页和分段
假设分为3个段,00不用,01代码段,02堆段,03栈段,可使用前2位作为段标识。
但段存在的外部碎片问题和稀疏的大堆问题仍无法解决。
多级页表(multi-level page table):将线性页表变成类似树的数据结构。将页表分成页大小的单元,如果整页的PTE都无效,则不分配该页的页表。为了追踪页表的页是否有效,以及页表所在的位置,使用名为页目录(page dictionary)的新结构,页目录中包含页表的位置。如下图所示,线性表中无论映射关系是否存在,都预先分配空间;多级页表中,增加页目录,如果整页的PTE都无效,则不分配空间(如PFN202和PFN204),从而整体节省空间。
在简单的两级页表中,第一级为页目录表,存在一个物理页中,包含多个页目录项(Page Dictionary Entities,PDE)。PDE至少包含有效位和PFN,如果PDE有效,则PDE指向的PFN中至少有一个页是有效的映射关系。第二级是虚拟地址对应的真实物理地址PFN,通过PFN可加载真实的数据。
多级页表可有效解决稀疏空间的问题。
如果页表的每个部分都可以整齐的放入一页,可以更容易进行内存管理。线性页表需要将整个页表加载到连续的物理内存中;多级列表无论页表项,还是页表项对应的真实映射关系,都放在一页中,整个页表可分散在物理内存中的各处。
多列表使用时间-空间这种(time-space trade-off)的方式,虽然空间节省,但每次TLB未命中时,相较于线性页表,多级页表需多访问内存,如两级列表,需先获取页表项,再通过页表项获取虚拟地址对应的真实物理地址,通过物理地址加载数据,整体需要3次内存访问,比线性表多1次内存访问。
假设14位虚拟地址,每页64字节,则偏移量为6位,VPN为8位,页表有28=256个。假设每个PTE大小为4字节,每页能存储16(64/4=16)个PTE,需4(16=24)位存储页表索引,剩余4位用作PDE,假设PDE也是4字节,则16个PDE共需64(16*4=64)字节,刚好存储在一页中。
综上共需4位标识页目录索引,4位用来标识页表索引,示意图如下:
超过两级:
假设虚拟地址为30位,每页512字节,则,偏移量为9位VPN为21位,页表有221个。同样假设每个PTE大小为4字节,每页能存储128(29/4)个PTE,需7(128=27)位用来存储页表索引,剩余14位用作PDE。假设PDE也是4字节,则需要216(4*214)个字节存储PDE,占用27(216/29)个页,而不是1个页。解决方法是页目录索引上再加一层索引,一页能存7个PDE,则PD索引1占用7位,PD索引0留7位,刚好可放在1页中。即三级页表也解决上述问题,其存储结构如下:
反向页表(inverted page table):保留一个页表,项存储物理页,而不是每个进程一个页表。页表项存储哪个进程使用该物理页,以及哪个虚拟页映射到该物理页。为了加速查找,数据结构选用散列表。
将页表交换到磁盘:以上都假设页表能一次加载到内存中,如果内存不足时,一些系统将无法加载的数据放入内核虚拟内存(kernel virtual memory)中,从而允许在内存压力较大时,将这些页表中的一部分交换(swap)到磁盘。
21. 超越物理内存:机制
交换空间(swap space):内存空间不足时,在硬盘或SSD中开辟一部分空间用于物理页的移入和移除,这部分空间叫swap space。
图中proc0、proc1、proc2部分在内存中,部分在交换空间中,proc3全部在交换空间中(肯定没获得执行权)。
image.png
存在位:通过页表项的存在位(present bit)判断是否在物理内存中,1表示在内存中,0表示在硬盘中。访问不在物理内存的页,称为页错误(page fault),由页错误处理器(page-fault handler)处理。
页错误:页错误由操作系统执行(无论是硬件TLB还是软件TLB,因需做I/O处理,硬件对该过程的加速无意义)。硬盘地址在PTE中的某些位中,类似PFN。当发生page fault时,从PTE中查找硬盘地址,发送给硬盘,读取到内存中。
读取成功后,更新到页表中。TLB重新执行,虽然仍未命中,但此时页已在内存中,可更新到TLB中;再次执行可从TLB中获取虚拟地址映射的内存地址,获得数据或指令。
执行I/O从硬盘获取数据时,进程处于阻塞(blocked)状态,CPU可执行其他进程。
内存已满时,空间换入(page in)前,需做空间换出(page out),如何选择换出的页,称为页交换策略(page-replacement policy)。
交换发生时机:为了保证有少量可用内存,大多数操作系统会设置高水位线(High Watermark,HW)和低水位线(Low Watermark,LW),帮助决定何时从内存中清除页。原理是当可用内存低于LW中,后台释放内存的线程(交换守护进程 swap daemon,或页守护进程 page daemon)会运行,直到可用内存高于HW。
21. 超越物理内存:策略
最优替换策略:替换出最远将来才会被访问的页,能达到总体未命中数最少,但几乎无法实现
FIFO:First In First Out,缓存命中率低
Random(随机):缓存命中率也随机,时高时低
LRU(Least-Recently-Used,最近最少使用):基于局部性原则(principle of locality),此外还有LFU(Least-Frequently-Used,最不经常使用)。相较于FIFO和Random表现较好,但实现困难,需记录并扫描每个页的访问时间。
近似LRU:在硬件中增加一个使用位(use bit,有时成为引用位 reference bit),每个页都有使用位,每当页被使用时,use bit设置为1。一种实现方案是时钟算法(clock algorithm),所有页在一个循环列表中,指针指向其中一个页,如果页的use bit=1,设置成0,继续向下寻找,直到找到use bit=0的页。
考虑脏页:脏页踢出必须将它会写到磁盘,成本较高,可选择踢出干净页。硬件中增加一个修改位(modify bit,或脏位 dirty bit)标识页是否修改。
其他虚拟内存策略:
- 页载入时的页选择(page selection)策略,对大多数按需分页(demand paging)载入。操作系统也可猜测页即将被使用,可提前载入(预取,prefetching)。
- 如何将页面写入磁盘:简单的是一次写入一页,但效率低。很多系统收集一些待完成写入,并以一种更高效的方式写入磁盘,称为聚集(clustering)或者分组写入(grouping)。
执行单次大的写操作,比许多小的写操作高效
抖动:当内存被超额请求时(进程需要的内存超过可用的物理内存),将不断进行换页,这种情况称为抖动(thrashing)。
23. VAX/VMS 虚拟内存系统
略~
24. 内存虚拟化总结对话
略~