操作系统导论 - 虚拟化

2023-04-01  本文已影响0人  仿若尘土

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

受限制部分:通过初始化陷阱表,执行陷阱,从用户态内陷到内核态,交给操作系统执行


受限制直接执行.png

在进程之间切换:

保存和恢复上下文:


首先直接执行协议(时钟中断)

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,轮转):按照时间片轮转执行。响应时间好,但周转时间差。

RR调度

结合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):

多队列多处理器调度(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个进程在:共享内存

地址空间:操作系统虚拟化内存,提供易用的物理内存抽象。


地址空间的例子

目标:

程序打印出来的都是虚拟地址,地址都从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模式:

只要一位就能区分CPU的模式,保存在处理器状态字(processor status word)。

动态重定位:硬件要求

硬件提供:- MMU:基址寄存器和界限寄存器

受限直接执行协议(动态重定向)
续表

16. 分段

将进程的整个地址空间加载到一整块内存区域,存在两个问题:

如果地址空间是4G,一般进程通常只占几兆

分段:泛化的基址/界限
在MMU中引入多个段,每个段占用连续的地址区域。假设分为代码、堆、栈3个段,则需要3个基址寄存器和3个界限寄存器。


分段物理内存
分段寄存器

通过虚拟地址的前几位标识所属段,剩余后几位作为偏移量。假设3个段时,可用2位标识端地址:


虚拟地址

在计算段和便宜量时,可通过与和右移减少计算量。
图中,SEG_MASK 为0x3000,SEG_SHIFT 为12,OFFSET_MASK 为0xFFF。


寻址算法

上图中栈反向增长,需要特殊位标识增长方向:


栈寄存器(支持反向增长)

支持共享,代码共享非常常见。通过保护位(protection bit)实现:


段寄存器(有保护)

细粒度和粗粒度分段:上述例子中只有3个段,属于粗粒度分段。早期机器中,有些可支持成千上万的段。

操作系统支持:

段的问题:

17. 空间空闲管理

本章讨论外部碎片,且假设用户进程申请到的是连续空间,且分配后不会再要求增加堆空间。

底层机制

typedef struct node_t {
    int size;
    struct node_t *next;
} node_t;

进程可通过mmp()向操作系统申请内存空间。

申请空间
假设剩余空间是连续的4KB,系统申请100字节,header占8字节,空间过程如下:
空间分配
假设又分配两个100字节的空间,分配后的结果如下:
空闲空间和3个已分配块
假设释放中间的块,中间块加入到头部:
释放中间块

基本策略

18. 分页:介绍

空间管理主要有两种:

假设虚拟地址共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)的硬件中,而是存储在内存中。

页表中的数据:

页表不仅占用内存大,而且会导致程序执行变慢,每次获取地址数据时,需要两步:

页表存在页表基址寄存器(page-table base register)中,转换如下: 页转换算法

综上所述,上述线性页表的方式存在两个问题:

19. 分页:快速地址转换(TLB)

页表存储在内存中,导致每次地址访问都需要一次额外的内存访问。操作系统借助地址转换旁路缓冲存储器(translation-lookaside buffer,TLB)硬件,缓存部分页表,从而减少绝大多数从内存中获取页表的操作,加速执行效率。

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共享。

可以把ASID看做进程标识符(Processor Identifier,PID),但通常比PID位数少,PID一般32位,ASID一般8位。
为了能标识当前进程,在上下文切换时,需将某个特权寄存器设置为当前进程的ASID。

image.png

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),从而整体节省空间。

image.png
在简单的两级页表中,第一级为页目录表,存在一个物理页中,包含多个页目录项(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位用来标识页表索引,示意图如下:

image.png

超过两级:
假设虚拟地址为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)标识页是否修改。

其他虚拟内存策略:

执行单次大的写操作,比许多小的写操作高效

抖动:当内存被超额请求时(进程需要的内存超过可用的物理内存),将不断进行换页,这种情况称为抖动(thrashing)。

23. VAX/VMS 虚拟内存系统

略~

24. 内存虚拟化总结对话

略~

上一篇 下一篇

猜你喜欢

热点阅读