什么是进程?

  • 一段程序的执行过程
  • 资源分配的基本单位

进程的基本状态

  1. 新建态:刚刚创建的进程,操作系统还没有把它加入到可执行进程组中,通常是进程控制块已经创建但是还没有加载到内存中的进程
  2. 就绪态:进程已经做好了准备,已分配到所需资源,只要分配到 CPU 就能够立即运行
  3. 运行态:进程处于就绪状态被调度后,进程进入运行态
  4. 阻塞态(等待态):正在执行的进程由于某些事件(I/O请求,申请缓存区失败)而暂时无法运行,进程受到阻塞。在满足请求时进入就绪状态等待系统调用
  5. 退出态:进程结束,或出现错误,或被系统终止,进入退出态。无法再执行

状态切换

进程基本状态之间的切换

⚠️注:

  • 只有就绪态和运行态可以相互转换,其它的都是单向转换
    • 就绪状态的进程通过调度算法从而获得 CPU 时间,转为运行状态
    • 运行状态的进程,在分配给它的 CPU 时间片用完之后就会转为就绪状态,等待下一次调度
  • 阻塞状态是缺少需要的资源从而由运行状态转换而来,但是该资源不包括 CPU 时间,缺少 CPU 时间会从运行态转换为就绪态

进程调度

为什么需要调度?

用户进程数一般都多于处理机数,从而导致进程互相争夺处理机。同时,系统进程也需要使用处理机。

因此,这就需要进程调度程序按一定的策略,动态地把处理机分配给处于就绪队列中的某一个进程,使之执行。

分类

抢占式

系统一旦把处理机分配给就绪队列中优先权最高的进程后,该进程便一直执行下去,直至完成。或因发生某事件使该进程放弃处理机时,系统方可再将处理机重新分配给另一优先权最高的进程。

这种调度算法主要用于批处理系统中,也可用于某些对实时性要求不严的实时系统中。

非抢占式

系统同样是把处理机分配给优先权最高的进程,使之执行。但在其执行期间,只要又出现了另一个其优先权更高的进程,进程调度程序就立即停止当前进程(原优先权最高的进程)的执行,重新将处理机分配给新到的优先权最高的进程。

抢占式的优先权调度算法能更好地满足紧迫作业的要求,故而常用于要求比较严格的实时系统中,以及对性能要求较高的批处理和分时系统中。

调度算法

不同环境的调度算法目标不同,因此需要针对不同环境来讨论调度算法。

批处理系统

批处理系统:用户将一批作业提交给操作系统后就不再干预,由操作系统控制它们自动运行。

批处理系统没有太多的用户操作,在该系统中,调度算法目标是保证吞吐量周转时间(从提交到终止的时间)。

先来先服务(FCFS)

First-Come First-Serverd(FCFS)

按照请求的顺序进行调度,不考虑等待时间和执行时间。

  • 优点:公平,实现简单
  • 缺点:有利于长作业,不利于短作业。因为短作业必须一直等待前面的长作业执行完毕才能执行,而长作业又需要执行很长时间,造成了短作业等待时间过长

短作业优先(SJF)

Shortest Job First(SJF)

按估计运行时间最短的顺序进行调度。

长作业有可能会饿死,处于一直等待短作业执行完毕的状态。因为如果一直有短作业到来,那么长作业永远得不到调度。

最短剩余时间优先(SRTN)

Shortest Remaining Time Next(SRTN)

按估计剩余时间最短的顺序进行调度。将短作业优先进行改进,改进为抢占式,这就是最短剩余时间优先算法。

  • 优点:利于短进程
  • 缺点:开销大,不利于长进程

交互式系统

交互式操作系统是为达到人机交互目的而为机器所编写的操作系统。常见的交互操作系统有 Windows,DOS 等,在交互式系统当中,最常见的是分时操作系统

交互式系统有大量的用户交互操作,在该系统中调度算法的目标是快速地进行响应

时间片轮转(RR)

Round-Robin Scheduling(RR)
此算法是最古老、最简单、最公平且使用最广的算法

  • 所有就绪进程按 FCFS 的原则排成一个队列
  • 每次调度时,把 CPU 时间分配给队首进程,该首进程可以执行一个时间片
  • 时间片用完时,由计时器发出时钟中断,调度程序便停止该进程的执行,并将它送往就绪队列的末尾,同时继续把 CPU 时间分配给队首的进程

时间片轮转

⚠️注:时间片轮转算法的效率和时间片的大小有很大关系

  • 进程切换都要保存进程的信息并且载入新进程的信息,如果时间片太小,会导致进程切换得太频繁,在进程切换上就会花过多时间
  • 如果时间片过长,那么实时性就不能得到保证

优先级调度(HPF)

  • 为每个进程分配一个优先级,按优先级进行调度
  • 为了防止低优先级的进程永远等不到调度,可以随着时间的推移增加等待进程的优先级

多级反馈队列

  • 将时间片轮转与优先级调度相结合
  • 设置了多个队列,每个队列时间片大小都不同
  • 进程在第一个队列没执行完,就会被移到下一个队列
  • 每个队列优先权不同,最上面的优先权最高。只有上一个队列没有进程在排队,才能调度当前队列上的进程
  • 优点:兼顾长短作业,有较好的响应时间

多级反馈队列

参考资料