操作系统概念——CPU调度

第六章 CPU调度

6.1 基本概念
cpu调度的目的是让系统始终在执行进程,最大化利用率:当一个进程因等待挂起或结束,则应调度另一个进程执行.
另外一些分时系统场景也要求一个进程不能运行太长时间,大家轮流共享.
运行中的进程可以分为cpu执行周期和IO执行周期.
一般高IO进程cpu周期短而多,高cpu进程一般会有若干长cpu.

cpu调度器:即短期调度器,被调度的对象一般都在内存的就绪任务队列中.
抢占式调度发生节点:
1) 当进程从运行状态切换为等待状态,如等IO、信号量、或等子进程结束.
2) 当进程从运行状态切换到就绪状态,如发生中断后.
3) 当进程从等待状态切换到就绪状态,如等待的IO事件完成.
4) 进程退出.
只支持1)和4)的调度器称为非抢占式调度或协作式调度, 这时当前进程无法继续执行了,内核必须重选一个.
抢占式调度顾名思义就是把当前正在执行的可能给强制切换掉,具体策略调度器负责.
考虑到内核共享数据和异步中断,抢占式调度一般处理需要更小心.

分派器:调度器选好后的实施, 上下文保存切换/设置为用户态/跳到进程相应地址执行. 这些应尽可能的短.

6.2 调度度量指标
不同的调度算法有不同的特点和适用场景,选择哪种算法需要考虑具体的目标和度量方案.
一般有以下几种调度性能度量指标,在不同指标下不同算法表现差别较大:
1) CPU利用率. 实际系统一般保持在40(较轻负载)- 90(重负载).
2) 吞吐率:单位时间内完成进程的数量. 和进程本身也相关.
3) 进程总耗时:从提交任务到完成的时间. 包括等待载入内存、就绪等待、cpu周期、IO周期之和.
4) 进程等待时间:进程在就绪队列里的总耗时.
5) 响应时间:交互式系统下从进程起到首次开始响应用户的时间.

总的原则是,在平均意义,尽可能提升cpu利用率和吞吐率,尽可能降低进程总耗时、进程等待时间以及响应时间.
有时候可能需要实现不同的目标,比如在交互式系统中要求最小化最大响应时间.
又比如在桌面系统中,有研究指出减少响应时间的方差同样重要,因为这样系统对用户的表现是一致可预测的.

6.3 调度算法
a) 先来先服务(FCFS)
最简单的调度算法. 缺点是平均等待时间比较长.
可能造成很多少cpu进程一直在等某个大cpu周期进程,此时io空着,接着少cpu进程快速用完后又和前者去抢io,
cpu空着,然后大cpu进程又开始占据cpu,循环往复,cpu和设备的综合利用率偏低.
另外FCFS是不支持抢占的,对分时系统不适用.

b) 最短任务优先(SJF)
其实是最短下一次cpu占用时间的进程优先,对平均等待时间这个指标来说达到了理论最优.
时间相同的之间可以FCFS.
难点在于下一次cpu使用时间一般对cpu调度是不可知的,只能用历史记录做预测. 预测公式:
 \tau _{n+1} = \alpha t_{n} + (1-\alpha)\tau _{n}
其中t_{n}是上次实际运行时间,\tau _{n}是上次预测时间.
参数\alpha用于权衡预测和历史. 初始预测值可以用个常量或者系统平均值参考.
SJF调度可以支持抢占,比如新加入一个比当前进程剩余时间更短的新进程时,马上切换执行.

c) 优先级调度
最短任务优先(SJF)实际上是优先级调度的一种,优先级值为下一次使用时间的倒数.
优先级可以由内部计算和外部指定得到.可支持抢占调度.
优先级调度的主要问题是防止饿死.即低优先级进程可能长时间得不到执行,直到系统崩溃造成数据丢失.
一个解决办法是根据一定的策略动态调整优先级,使得最终一定能得到执行.

d) 轮转调度(RR)
一般用于分时系统的抢占式调度.时间片一般从10ms到100ms.
时间片轮转调度的进程等待时间一般都不是较优的.
其效果主要取决于时间片大小的选取:太大则退化为FCFS调度,太小则上下文切换占比太高,有效利用降低.
一般上下文切换在10微妙级,因此只占时间片很小比例. 一个设置参考原则是让时间片比80%的进程下一次cpu周期长.

e) 多层队列调度
为不同类型的进程分配不同的就绪(待调度)队列. 每种队列可以运行不同的调度算法.
例如前台任务队列执行轮转调度,后台任务队列执行FCFS调度.
队列和队列之间可以采用基于优先级的调度:只有当高优先级队列为空时,才调度低优先级队列任务.
高优先级队列任务会抢占低优先级队列的任务.
每层队列之间也可以采用分时间片调度,即获得相应的cpu执行时间占比,在占比时间内调度队列内任务.

f) 多层反馈队列调度
允许任务在不同调度队列间迁移. 目的是自动分离出重cpu的进程,并进入低优先级队列,让重IO类型进程多得到调度.
也可以根据需要把长时间在低优先级队列中的进程上升,防止饿死.
组织方式例如上层(高优先级)队列设置比下层较小的时间片进行RR,当进程时间片超出时进入下层(低优先级)队列,
这样就自动把重cpu的进程下沉了.
一般多层反馈队列调度器需要设置的参数:队列数量/进程分派队列类型策略/各队列调度算法/队列间任务迁移策略
该调度算法比较灵活和通用,但相对复杂并且需要确定的参数较多.

6.4 线程调度
内核调度的对象是内核线程,用户线程调度可以由线程库利用LWP实现,最终也是映射到内核线程.
Pthread线程库可以指定两种调度模式:PTHREAD_SCOPE_PROCESS/PTHREAD_SCOPE_SYSTEM,
前者在进程范围内调度线程,一般用于多对多或多对一映射的系统; 后者在系统全局范围内参与调度.
Linux 和 MacOS仅支持后者.

6.5 多处理器调度
多处理器可以分担系统负载,但对cpu调度带来了额外的问题考虑.
一种方式是其中一个cpu作为master进行进程调度、IO处理和其他系统层工作,而由其他cpu执行用户层代码.
这种非对称多核处理的好处是实现简单,仅一个cpu需要系统数据结构. 但其他方面比如整体稳定性和容错等有欠缺,不够通用.
另一种现在更普遍的方式是对称多核处理(SMP),其中每个cpu角色定位相同,分别独立自行调度;
各cpu可以共享一个全局进程就绪队列也可以用私有的队列,一般后者较多.
SMP下的进程调度有以下几个问题需要考虑:

a) 进程亲和性
指由于cache的原因,一般一个进程在某个cpu上开始执行后,不会轻易切换运行的cpu,否则会带来额外的缓存开销.
操作系统一般会维护这点但在有些情况下仍然可能发生cpu迁移;如果想明确指定不允许迁移可以显示地通过系统调用来绑定cpu.
另一个于此相关的是在非一致性内存访问(NUMA)下,内存管理需要配合调度器做其相应的策略调整.
即当一个进程指定了亲和cpu后,进程申请的内存要从其相应的NUMA片区分配.

b) 负载均衡
在各cpu队列间迁移进程,使得各调度负载尽量均衡. 如果各cpu共享调度队列则一般不需要考虑.
注意这和亲和性原则相悖,所以可以设定一定的阈值触发. 一般由push和pull两种迁移方式:
push:内核线程周期性的检查,将高负载cpu的任务重新分派给低负载cpu.
pull:空闲cpu主动向高负载cpu拉取一个等待执行的任务.
Linux和BSD都实现了这两种方式.

c) 多核处理器
与多处理(Multi-processors)不同,多核处理器(Multicore-processors)有多个核心在同一个物理芯片上,
而前者每个处理器一般是独立的芯片. 多核的好处是交换数据更快功耗也更少.
超线程调度:
一般处理器中如果cache不命中,则cpu需要等相对较长的时间从内存读取数据,这时核心可能被挂起,称为Memory Stall.
与上层调度的思路类似,这时可以起另一个隶属于该核硬件级线程来运气其他任务的指令,防止硬件空闲.
从操作系统的角度来看,每个硬件线程相当于一个独立的逻辑处理器可以同时执行2个任务,
比如在一个双核,每个核2线程的平台上,操作系统看到的其实是4个cpu资源.
有粗粒度和精粒度两类超线程切换方式.前者在cpu出现较大的空闲如Memory Stall时才做切换,
并且切换时由于要重新填充pipeline会给性能带来额外影响.
而细粒度的方式控制更精细,切换逻辑更复杂但效果较好.

因此,在多核超线程系统下,任务调度其实在两个层面上发生:
1) 在软件的进程层面,操作系统以逻辑cpu(对应每个核心的每个线程)为单位进行调度,各类调度算法如前所述.
2) 在硬件的cpu核心层面,core对各个硬件线程做调度切换,一般需要额外硬件切换逻辑支持.

6.6 实时系统调度
软实时系统:系统不做保证,只是实时进程有更多的权重得到执行.
硬实时系统:系统要保证在deadline之前执行,否则视为任务失败.

实时系统一般是事件驱动的,事件处理的延迟主要包括中断延迟、分派延迟,为降低延迟一般要求内核可抢占.
实时系统要求尽可能快的处理调度,因此一般采用带优先级的抢占式调度. 一般实时进程的优先级设为最高,但这只能保证软实时.
硬实时系统从实时进程的运行频度和dealine等切入考虑, 有一下几种调度方式:
a) 频度递增调度
这种场景下任务一般是周期性触发执行的,有一个固定的频度(周期),并且同一个进程在周期内占用cpu的时间大致相同.
则采用静态优先级,触发频度越高(周期越短)则优先级也越高. 其理由是经常请求cpu的进程应当优先执行.
在静态优先级策略下该算法是最优的.

b) 最早Deadline优先调度
动态优先级策略,谁的deadline最快到期就调度谁,可抢占,对进程类型和触发模式无要求,仅需要进程提示系统其deadline.
动态优先级是因为每个进程在重新运行时可以调整deadline.
Deadline优先调度对实时系统理论上是最优的.

c) 按比例共享调度
应用获得一定cpu资源比例的保证. 对于超出当前剩余比例的请求一律拒绝.

POSIX的实时调度扩展支持两种调度类:SCHED_FIFO/SCHED_RR.
前者使用的是FIFO队列,后者在前者基础上加了通优先级下的时间片轮转.

6.7 操作系统举例
Linux:
在内核版本2.5之前,内核采用的是延续自Unix调度的一些变体,由于初始没有考虑SMP,
因此后来对多处理器系统支持不佳,并且当待调度进程数量较多时性能表现较差.
在2.5版本新引入了一个O(1)调度算法,即不论进程多少都能在常数时间完成调度,也增强支持SMP、cpu亲和、负载均衡等.
O(1)调度固然性能很好,但发现在很多桌面交互式应用场景,对用户的响应时间较长.
到了2.6版本又重新设计了调度,目前非实时进程的默认的调度算法是CFS完全公平调度算法(Complete Fair Scheduler).
标准的Linux内核实现了2种调度类:默认调度类,采用CFS/实时调度类,优先级更高.
CFS背后的设定是,每个进程默认都能从cpu分到相同的占用比例,可以设定优先级(nice value(nv))调整相对比例.
为了体现公平,每个进程在一个目标周期内都至少能执行一次(如果进程太多可以调大周期防止切换太多),各执行占比从此周期分配.
CFS没有定义明确的时间片和优先级,但是会为每个进程记录一个虚拟运行时间vruntime,该值和实际执行的关系与nice value相关.
例如nv=0的进程vruntime=实际时间,nv<0的进程vruntime<实际时间,nv>0的进程vruntime>实际时间.
调度器调度时每次都选择vruntime最小的进程,调度是抢占式的.
CFS的效果举例:
考虑nv相同的一个重cpu进程和一个重IO进程,显然后者的vruntime一般情况下都会小于前者,于是重IO进程实际获得了更高的优先级,
并且很可能每次IO完成后都能抢到cpu,降低了平均等待时间,也保证了交互式场景的响应速度.
Linux实现了软实时调度器,即对实时类型的进程分配更高的优先级(映射到nv_min以下的范围)

Windows:
整体基于优先级的抢占式调度,局部分时时间片轮转.
一般分为普通和实时两大类,对每个优先级都设置有调度队列,从高到低查找,如果没有线程可执行则调度Idle Thread.
普通类型的优先级可以动态调整,如时间片用完后可以适当降低其优先级,限制重cpu的任务;又如当IO事件完成时,
可以适当提升其优先级,以快速响应类似用户键盘或鼠标输入的场景.
用户当前的活跃窗口也会获得优先级提升. 如前台任务的时间片加长为后台任务时间片的3倍.
Windows 7提供了用户模式调度(UMS),每个用户线程也都有独立的上下文;由于不需要内核介入性能比较高.
基于UMS微软提供了C++多核并发任务编程框架ConcRT,带用户模式调度器实现.

Solaris:
整体上也是基于优先级的调度.
一共划分了六大线程调度类,每类的优先级和调度算法不同.
默认类型是分时类型,采用的是多层反馈队列调度,即优先级可动态调整,一般优先级越高时间片越短.
为了限制重cpu的任务,如果时间片用完任务还没结束会适当调低优先级.
为了提高响应速度,IO事件完成后任务的优先级也会保证调整到一个合理的范围.
与windows类似会对交互式窗口应用(如KDE/GNOME管理器)赋予更高的优先级.

6.8 算法评估
可用于评估的指标一般包括cpu使用率、响应时间、总吞吐等.
由于各方面通常无法全部满足需要权衡,因此评估之前要明确具体的目标是什么,比如:
在最大响应时间不超过1秒的前提下,最大化cpu的利用率. 或者:最大化系统吞吐使得进程总耗时与总执行时间成正比.

有几种评估方法:
1) 定量模拟分析,即确定的输入case的调度算法表现分析.
好处是简单快速,有具体数据对比,有一个整体的粗略认知.
坏处是只能覆盖具体的测试case,有局限性. 因此主要用于描述算法和理论启发,如SJF最优性证明.

2) 排队模型分析
为了突破局限性,从统计意义角度出发,先收集一些统计数据如进程cpu占用分布、IO占用分布、进程创建时间分布等,
可以进一步推导出总体吞吐、利用率、等待时间等有用信息.
将cpu和调度看做一个带队列的服务,如果已知任务提交速率、服务速率等可以推算出利用率、平均队列长度、平均排队时间等.
Little's Formula: 设W为任务等待时长,r为任务进入队列的速率,则队列长度 n = r * W.
排队模型一般用于对比分析不同的算法,但由于做有假设,建模复杂,以及待评估算法的实际行为与理想模型不符,结果一般只有近似意义.

3) 仿真
拿实际数据来做模拟。数据可以合理随机产生也可以从真实系统日志收集.
好处是模拟系统越精细效果越好,但需要额外的存储、计算和开发成本.

4) 实现后检验
实现调度算法并投入到真实环境看实际效果. 但成本最高也影响系统稳定性.
另一个途径是直接调整现有调度系统的可变部分,或者运行时通过API调整优先级等,前提是系统支持并足够灵活.

第七章 死锁
7.1 系统模型
进程对资源的使用一般分为申请、使用、释放三个阶段.
资源分为共享资源和独占资源,后者一般要求进程间互斥访问,当不能满足时需要等待.
死锁现象就是一批进程陷入了无限等待,因为每个进程都在等其中一个进程占用的资源,整体无法继续.

7.2 死锁的特征
发生死锁有以下4必要条件:
a) 互斥访问资源:共享资源不会造成死锁
b) 持有并等待:进程占有至少一个资源后,又去申请另一个资源时陷入了等待
c) 资源不可抢占:已占有的资源只能进程用完后自愿释放
d) 循环等待:进程等待关系存在循环:P0->P1->...PN->P0

可以用资源分配图来描述当前状态:
%e5%b1%8f%e5%b9%95%e5%bf%ab%e7%85%a7-2016-11-10-%e4%b8%8b%e5%8d%882-33-23

P表示进程,R表示资源类型,每个资源类型有多个实例(黑点).
P到R的边表示资源申请时的等待,R到P的边表示当前资源被哪个进程占有.
一般来说发生死锁则有向图中一定存在一个环,但有环不一定死锁,除非每种资源类型只有一个实例.
如上图中有环但系统不会死锁.

7.3 死锁处理方法
一般由三种方法:
a) 避免发生死锁,杜绝系统进入死锁状态的可能.
b) 检测系统死锁并试图恢复(打破)死锁, 让系统整体可继续.
c) 不处理,假设程序不会发生死锁,留给开发者解决.

多数系统一般不处理死锁,死锁检测和恢复等开销较大,而死锁又不常发生.
Linux和Windows系统本身不处理死锁.

7.4 死锁杜绝
目的是针对死锁发生的四个条件,使至少其一无法满足,从而杜绝死锁出现:
a) 打破-互斥访问:
最大程度共享,但有些必须互斥的没有办法.
b) 打破-持有并等待:
持有时不需要再进入等待:比如程序启动时一次性获取所有资源,结束时一并释放.
等待时不持有资源:在申请其他资源之前,必须释放当前已持有的资源.
缺点是资源利用率可能偏低,提前持有了但不立即使用,另外可能一直不能一次性申请到资源而饿死.
c) 打破-禁止抢占
即使得资源可以抢占,比如当进程申请其他资源而进入等待时,其已占用资源变为可被其他进程抢占,
而原进程必须等到所有资源满足时才能继续.
一般只适用于状态能快速保存和恢复的资源比如cpu寄存器和内存等,对互斥锁和信号量不适用.
d) 打破-循环等待
指定资源申请的顺序:为每种资源编号,申请占用资源时按编号从小到大的顺序,
即申请编号为i的资源时,要保证当前没有占用编号>i的资源.
设计资源层次是一方面,具体需要开发人员申请资源时遵循规定的顺序.

7.5 死锁避免
杜绝死锁的方式比较严,可能造成系统利用率下降;另一种更温和的做法是利用额外资源来指导分配,避免死锁发生.
如果事先知道每个进程将要申请的资源申请和占用模式或最大值,则可以通过调整申请资源时是否强制
等待来避免将来可能出现的死锁,也就是使得每一步资源分配都是整体"安全"的.
做决策的时候要求系统记录并维护当前资源分配状态,以及每个进程将来的(最大)资源需求.

安全状态:存在一个进程资源分配序列,后面的进程需求总能通过当前剩余资源和前面进程后结束的释放资源得到满足,因而不会导致死锁.

资源分配图算法:适用于没类资源单个实例的场景,将进程将来对资源的可能需求加入到资源分配图作为边,每次分配资源时
转换为资源占用边(方向逆转),然后检测该有向图有无循环,有则可能发生死锁,进程需要等待.

银行家算法:适用于每类资源多个实例的场景;记录动态的资源分配矩阵,每次尝试分配后检测当前是否是安全的状态.
安全检测算法详见本章节描述.

7.6 死锁检测
单实例资源类型:即检测资源分配图(可转为进程等待关系图)有无回路即可,复杂度O(n^2),n为进程数量.
多实例资源类型:类似银行家算法,利用当前资源分配情况,剩余资源等数据判断下一批已持有资源的进程的申请能否满足,
如一个都不能满足,则可以断定发生了死锁.
死锁检测可以每个时间间隔运行一遍,但这样可能无法追踪产生死锁的第一个进程.

7.7 死锁恢复
检测到死锁发生后系统可以采取一定的恢复措施,一般有杀进程和资源抢占两种方法:
杀进程重启:杀所有进程,代价大;逐步杀进程直到不再死锁,具体杀那个最经济要考虑很多因素.
资源抢占:挑选进程将其占用的资源强制释放,让其他进程能继续执行,
但可能需要回滚进程到一个可安全重启的状态,极端情况就是杀掉完全重头开始;
另一个问题是防止同一个进程反复被抢占饿死,可以设置一个被抢占次数上限.

一般需要组合利用上述多种方法方能较好地解决系统死锁问题.

发表评论

电子邮件地址不会被公开。