yishujixiaoxiao 2020-04-20
本文是
操作系统系列
第四篇文章,介绍处理机调度进程相关算法。处理器调度进程的算法和调度框架(Kubernetes)类似,可以相互借鉴。原文链接,更多内容见公号机器学习与系统
,欢迎与我互动~
发生进程切换时,本质是CPU资源占用者间的切换。此时需要保存当前进程在PCB中的执行上下文(CPU状态),然后恢复下一个进程的执行上下文。
处理机调度涉及两个方面,一是选择进程:从就绪队列中挑选下一个占用CPU运行的进程。二是选择CPU资源:从多个可用CPU中挑选就绪进程可使用的CPU资源。
调度策略是指确定如何从就绪队列中选择下一个执行进程,可以理解为调度算法。评价算法的基准有以下几个:
另外,处理机调度需要保证公平:
FCFS依据进程进入就绪状态的先后顺序排列,它简单、易于实现。
但是也存在一些缺点,以上图为例,进程到达次序不同,对周转时间影响较大。总结如下:
SPN是FCFS算法的改进,它选择预期执行时间最短进程占用CPU进入运行状态。SPN算法的优点是具有最优平均周转时间。缺点:
选择就绪队列中响应比R值最高的进程,R计算方法如下:
R=(w+s)/s
w: 等待时间(waiting time)
s: 执行时间(service time)
RR算法是对FCFS的改进,在FCFS的基础上加入对进程执行时间(CPU时间片)的限制。当进程的时间片用完后,按照FCFS的规则选择下一个进程。
上图是RR算法的示意图,三个进程按照P1、P2和P3的顺序到达,执行时间分别为53、16和68。基准数据如下:
RR算法主要开销在进程的上下文切换,重点是选择合适的时间片(delta)。
根据经验规则,delta应保证上下文切换开销处于1%以内。
该算法的思想是把就绪队列根据更细的维度划分成不同的子队列,不同队列选择不同的算法。如前台交互就绪队列
和后台批处理就绪队列
,前台使用RR,后台使用FCFS。
将就绪队列中进程按照不同的优先级分成不同的队列,优先级越高时间片反而越小,进程可以在不同的队列间移动,如进程在当前的时间片没有完成,则降到下一个优先级。
MLFQ算法中,CPU密集型进程的优先级下降很快,I/O密集型进程停留在高优先级。
FSS强调资源的公平分配,对用户进行分组。用户组比其他用户组更重要,则分配更多的资源。未使用的资源按比例分配,没有达到资源使用率目标的组获得更高的优先级,这样就避免不重要的用户垄断资源。
算法 | 特点 |
---|---|
先来先服务算法(FCFS) | 不公平,平均等待时间较差 |
短进程优先算法(SPN) | 不公平,平均等待时间较差需要精确预测计算时间可能导致饥饿 |
最高响应比优先算法(HRRN) | 可能导致饥饿不可抢占 |
时间片轮转算法(RR) | 可能导致饥饿 |
多级反馈队列算法(MLFQ) | 多种算法的集成 |
公平共享调度算法(FSS) | 强调公平 |
对时间的要求很严格,要求操作系统在一定时间内完成相应功能。它的性能指标有两个:
实时操作系统可分为两类:
实时调度算法:
即多个处理机组成一个多处理机系统,处理机间可负载共享。
该调度中,每个处理器运行自己的调度程序,调度程序对共享资源的访问需要进行同步。在分配进程时有静态进程分配和动态进程分配。
优先级反置是一种现象,发生在基于优先级的调度算法中,即高优先级进程等待低优先级进程的现象。主要原因是资源的占用现象,低优先级占用资源,等待资源使用结束后才能释放资源,需要相同资源的高优先级进程就需要等待。
下面介绍两个解决方法。
本文介绍了操作系统中处理器调度进程的算法,包括单处理器和多处理器。调度算法的应用很广泛,从操作系统中的进程到Kubernetes中的Pod调度等,值得深入学习,顺便给自己埋个坑,希望完成调度算法系列...
文章持续更新,可以微信搜索「 机器学习与系统 」阅读最新内容,回复资料 内推 考研获取我准备的
计算机学习资料
、工作内推
和考研
参考。