bookstack

进程调度

CPU虽然可以运行多个进程,但是在同一时刻,每一个CPU都是只运行一个进程,而其他进程要运行,那么就只能进行进程间切换,这个切换的策略就是进程调度

调度时机

  • 新进程创建时
  • 进程退出时
  • 进程在I/O阻塞时
  • I/O中断发生时

计算机硬件有时钟,根据时钟中断,可以将调度算法分为抢占式调度(根据时钟中断,进程运行固定的时长)和非抢占式调度(进程运行到阻塞为止)

调度算法分类和目标

根据操作系统的使用途径不同,调度算法需要实现的目标,目前的操作系统主要有三种

  • 批处理操作系统
  • 交互式操作系统
  • 实时操作系统

每种操作系统,应用的环境不同,所以对进程调度关注的指标也不相同

操作系统调度指标
通用操作系统公平,策略强制执行,平衡
批处理操作系统吞吐量,周转时间,CPU利用率
交互式操作系统响应时间,均衡性
实时操作系统数据完整性,可预测性

所以对于不同的操作系统,所用的调度算法也不尽相同

批处理系统调度算法

批处理系统要求吞吐量大,周转时间小,同时CPU利用率高,基于此三点,主要用到的调度算法有:先来先服务、最短作业优先、最短剩余时间优先

这三个调度原理比较简单。这里主要讲优缺点

先来先服务的优点是易于理解,便于实现;缺点是如果每个进程都有大量操作I/O,那么就会耗时比较久

最短作业优先的优点是周转时间最小;缺点是长作业可能永远无法运行

最短剩余时间是总是选择剩余时间最小的那个去运行,同样会导致长作业永远无法运行

交互式系统调度算法

交互式操作系统要求响应时间快,所以主要的调度算法有:轮转调度、优先级调度、多级队列调度、最短进程优先、保证调度、彩票调度和分享公平调度

轮转调度是最古老,最简单,最公平且使用最广的调度算法。每个程序只运行一个时间片的长度,然后抢占调度

优先级调度每个进程都有一个优先等级,优先调度高优先级的进程,可以是进程运行完才调度,也可以是时间片运行完调度

多级队列调度是解决多次调度导致的切换时长过长的问题,为调度密集型程序提供更长的调度时长。原理是设置多个级别的调度长度,最高等级的运行完一个时间片后,将进程设置成第二级的优先级,同时拥有的时间片长度更多

保证调度是向用户做出明确的性能保证

彩票调度是给用户一个保证,然后兑现。这是一个很好的想法,但是实现较难

公平分享调度是用在多个用户间的一个调度,保证多个操作系统的用户都能够有公平的CPU使用

实时系统调度算法

实时系统是一种时间起着主导作用的系统。典型地,外部的一种或多种物理设备给了计算机一个刺激,而计算机必须在一个确定的时间范围内恰当地做出反应。

实时系统的调度算法可以是静态或动态的。前者在系统开始运行之前作出调度决策;后者在运行过程中进行调度决策。只有在可以提前掌握所完成的工作以及必须满足的截止时间等全部信息时,静态调度才能工作。而动态调度算法不需要这些限制

小结

操作系统的进程调度是一个很广泛的问题,一般而言,类似于Go和Java的自己有调度系统的,都是参考操作系统的调度。这里通过分系统讨论了每个系统下的调度算法,其中轮转调度是最常用的调度算法,通过时间中断,然后进行抢占式调度的,应该需要掌握,其他的几个,了解概念即可