OSTEP笔记1–CPU虚拟化

截图来自原书,贴出书的官方主页: 《Operating Systems: Three Easy Pieces
(作者Remzi H. Arpaci-Dusseau and Andrea C. Arpaci-Dusseau)。感谢原作者这么好的书。

本篇笔记是书的第一部分(Virtualization)的上半部分,讲述了操作系统是怎么通过进程的抽象,将CPU计算资源进行虚拟化的。

第一节 进程的抽象

1.1. 策略和机制

Policy在mechanism(策略和机制)在操作系统中通常是分开设计的。比如如何切换上下文是一个low-level的mechanism,指底层的方法或者协议。当前时刻应该让哪个进程运行更好是一个high-level的policy的问题,指一些“智能”的调度。

1.2. 虚拟化和OS

OS本身就可以看做是“虚拟机”(virtual machine)。系统通过在可以被接受的合理开销(时间、空间)范围内,将计算机CPU、内存、存储等资源进行虚拟化(抽象),目的是为了用户的方便使用。

CPU虚拟化 主要体现在将任务抽象为 进程(process) ,将资源按进程隔离,然后多个进程轮转使用计算资源; 内存虚拟化 主要体现在 虚拟地址空间(virtual address space 或 adress space) ;而对于持久化的 存储 ,OS让文件共享,没有那么多私有隔离,OS假定用户会用文件来共享数据。 (????)

第二节 进程API

2.1. fork和exec

exec()函数组和fork()的区别是:fork()复制当前进程为一个子进程执行,exec()会执行一个新的程序;exec()执行以后就再也不会返回。

2.2. shell和stdout redirect

例如shell就是一个普通的用户程序,利用了fork和exec的组合。给出一个提示符,你输入可执行程序时,会先fork(),然后在fork出的子进程中exec()这个命令,然后调用wait()来结束。这种fork和exec的组合使用,可以在让shell在fork后运行一些其他代码:fork后的子进程可以redirect操作再exec;fork后的父进程可以执行wait操作在exec结束后再显示提示符prompt。

stdout redirect的原理很简单,stdout一般的fd都是0,在fork后的子进程中close掉stdout,然后打开要redirect到的文件,这个文件就会获得为0的fd,这时执行新命令的exec,则会把这个为0的文件看做stdout进行输出,程序清单如下图:

2.3. 其他

kill()可以向进程发送信号,让程序sleep, die。

第三节 机制:有限的直接执行(Limited Direct Excution)

为了实现多个程序在同一个机器上执行,即CPU时间被多个进程共享,需要一种称为Limited Direct Excution(LDE)的机制。若单说Direct excution,指的是程序直接在CPU上执行(类似单片机?),OS对各程序加以限制,让进程间交替执行,即LDE。

3.1 用户空间和内核空间的切换

用户程序操作受限

OS的执行模式可以分为 kernel modeuser mode ,kernel mode下内核程序代码可以为所欲为,而user mode下的应用程序是受限的:比如,user mode程序无法直接进行IO请求,这种限制是必要的,因为OS不希望用户随便更改磁盘,而且OS的FS也希望用户访问文件前检查用户的访问权限。

系统调用并陷入内核

系统调用(system call) 可以说是连接用户空间和内核空间的桥梁。用户程序想执行受限的操作,需要通过OS的系统调用来 陷入(trap) OS内核。(这就类似于OS是个代理,特殊的操作都要由内核程序经手办理。最开始OS的系统调用可能有二十种左右,现在一般OS都有几百种系统调用。)

系统调用并陷(trap)入内核的流程可以看成是LDE执行协议,如下图,分为两段,第一段是系统启动时的向硬件的注册,第二段是正常运行:进行系统调用时,控制权将从用户程序转交内核,这需要用户程序执行trap指令,硬件首先会把当前程序的寄存器信息备份(x86下会将PC、各种标志位等寄存器push到对应进程的kernel stack中),然后根据(系统启动时注册到硬件的)系统调用trap表jump到指定的内核代码,OS内核为所欲为地执行完后,会最后执行return-from-trap指令,恢复用户程序寄存器(pop from kernel stack),用户程序会继续运行。

比如,open()等函数就属于系统调用,在open的C库中,会有进行trap的汇编指令,所以我们可以直接调用系统调用函数,而不用写汇编,因为已经有人封装好了。

3.2 用户空间多个程序的切换(交替执行)

要使多个程序一起执行,需要OS进行整体的控制和调度,但是当用户程序在CPU运行时,意味着OS没有在运行,所以要在程序间复用CPU,OS需要频繁地拿回控制权并向多个进程进行分配。

早期的苹果系统和Xerox系统等采用了一种和谐 “合作”方式 处理这个问题,OS相信用户会调用一个成为yield的系统调用,主动交出控制权给内核。但是这样并无法保证程序不存在恶意,OS只能期望程序交出控制权或者程序执行出错(illegal operation)。

最常用的方法是用 timer中断方式 保证OS可以拿回控制权。系统启动时会设定一个定时器,若一个进程在一定时间没有放弃控制权,timer中断也会把控制权“夺回”给OS,OS决定是继续执行当前进程还是将时间片分给其他程序。需要注意的是,在这个过程中,存在两中保存和恢复(saves/restores)寄存器的过程:首先,在timer中断时, 硬件 会保存当前程序A的寄存器以便恢复执行;其次,如果OS决定从A切换到B,需要 软件 (OS)将A的寄存器保存到memory中。

中断还存在很多并发的问题,比如OS会在中断代码执行时禁止中断,并会引入很多锁保证内部数据结构的并发访问,书的第二部分将详细讨论。

第四节 进程调度

workload的信息

讨论调度首先要了解workload(当前系统运行的进程集),有时条件比较宽松,比如知道任务同时来,任务长短已知等,这时SJF(short job first)这种简单调度就是最优的;但一般情况下,workload的很多信息并无法预知,所以需要更复杂的调度方法。

调度的metrics:完成时间和响应时间

有两个衡量调度优劣的评判标准,Turnaround time和response time,一般两者不可兼得。

4.1 调度思想

两种简单的 非抢占(non-preemptive)调度 ,任务是一个接一个执行的:

  • FIFO 或者称为FCFS,最简单,但是可能引起convoy effect(护送效应?),即第一个任务时间很长,后边的任务需要等很长时间。

  • SJF 改进了这种情况,让最短的任务最先执行。

但是,实际中的任务一般不是同时到达的,如果短的任务来晚了一会,长的任务已经执行了,又要等很长时间。于是有了 抢占式(preemptive)调度

  • STCF 即shortes time-to-completion first,或者叫 PSJF (Preempttive Shorted Job First),改进了SJF 可以在预知完成时间的情况下,让可以先执行完的任务抢占执行。

但是,实际中很少知道任务什么时候将执行完一般很难知道,为了保证响应时间,有了 时间片(time slice或scheduling quantum) 的概念:

  • Round Robin ,简称 RR ,是一种轮询调度,保证了响应时间,但是完成时间确是最差的。另外时间片的长短选择时,有一个 trade-off :即进程的上下文切换需要时间,如果时间片太短,则会导致用在切换的时间太长,时间片太长,又会导致响应时间变差,这也是一个时间 分摊(amortize) 的问题。作者之后讨论的调度多是基于时间片的调度。

4.2 进行磁盘I/O的进程的调度

一个进程进行IO请求后,很可能会阻塞,但是这个阻塞并不占用CPU,因此这是应该利用这个时间去执行其他的进程,这样可以提升CPU利用率。当IO完成时,一般会有中断发生,这时OS才把进行IO的进程改回“ready”状态。

4.3 多级反馈队列调度(MLFQ)

Multi-level feedback queue主要通过”learn from history”的方法,解决完成时间(turnaround time)和响应时间(response time)的优化问题。

MLFQ有多个queue,每个queue有不同的优先级,并且可以根据任务执行的情况调整优先级:若任务在时间片结束前就放弃控制权,说明是 交互型任务 (类似latency-sensitive任务),放在高优先级;如果每次都用完了时间片,说明是 CPU-bound 的任务(类似best-effort任务),对响应要求不高,放在低优先级。比如对于鼠标键盘等IO,时间片结束前就会放弃CPU控制权,从而保持高优先级,保证了响应时间。

但是这种优先级调整会遇到几个问题:

饥饿问题(starvation) 如果高优先级的任务太多,低优先级队列的任务永远饿着,解决这个问题的办法是定期的 优先级boost ,即定期(如1s)将任务全调到最高优先级,这样可以防止饥饿。但是这个周期S参数怎么选又是个 trade-off :太长的话,低优先级队列的任务就要饿很久;太短的话,对响应要求高的任务就不能更好地工作。

欺骗问题(game the scheduler) 既然执行完时间片会被降级,那么执行99%的时间片再放弃CPU,会同时获得高优先级和大量的CPU时间,这种欺骗是恶意的,会导致系统性能问题。解决的方法是将各个优先级间调整的依据(时间片)改为更精确的计时,高优先级的队列要求的时间更短,向下的优先级逐级递增(优先级越低,时间配额越大)。这里当然还会有很多参数设定的问题。

任务特征变化的问题 任务不都是一成不变的,可能由CPU-bound型转为interactive型。这个问题也可以通过定期 优先级boost 解决。

参数设定的问题 队列数目、队列长度、boost周期、优先级调整时间配额等都是可变的参数,但是这个参数很难调。我们大家都知道,多数用户从不改默认参数,改的话也可能越改越差,这个问题很难解决。有些系统给出了方便调优的工具,有些利用了应用或用户的建议(advise)或提示( hint ),比如进程优先级 nice 和内存管理 madvise 等。

MLFQ达到了一定的fairness,BSD UNIX的衍生版本、Solaris、Windows NT及后续版本都在用它作为基本调度器。

4.4 按比例(Proportion-Share)调度

比例调度(proportional-share scheduler, fair-share scheduler)保证了fairness,保证某个进程得到一定比例的CPU时间。

主要介绍了两种方法: lottery schedulingstride scheduling ,前者为不同人物分配不同数量的ticket,然后随机选一个数,根据概率决定下一次哪个进程执行;后者根据步长,将每个任务的“计步器”初始化为0,CPU配额大的任务步长小,每次步数最少的程序执行。

stride scheduling更精确,因为没有随机数的应用;lottery scheduling更灵活,因为中途可以很方便地加入新的任务而不用新的初始化。

而且,lottery scheduling有很多有趣的玩法,ticket可以看成一种通货( ticket currency ),这种ticket通货在进程间进行转增( ticket transfer )、可能发生“通胀( ticket inflation )”的ticket增发等。ticket转赠即一个进程可以将自己的ticket划给其他进程,这样CPU比例就发生了变化;如果进程间 相互信任 ,还可以允许某个进程暂时凭空增加(借贷)和减少(放贷)ticket数目,这可能引起问题,但的确很灵活。这种讨论还可以参见[1]。

ticket assignment problem是指应该怎么指定给每个进程发多少tickets的问题,这个问题是开放性的。


[1] Lottery Scheduling, https://cs.nyu.edu/rgrimm/teaching/sp07-os/lottery.pdf

发表评论

电子邮件地址不会被公开。 必填项已用*标注