进程调度

讨论cpu调度的概念和算法

1.基本概念

多道程序的目标:多个进程同时处于内存,当一个进程等待时,操作系统将CPU交给另个进程,有效利用CPU。

执行周期:在CPU执行和IO等待之间,不断交替。经验表明,执行时间有大量短CPU执行和少量长CPU执行

image-20220506234242598

调度程序:CPU空闲时,从内存中选择一个能够执行的进程,为其分配CPU。

需要进行CPU调度的情况:

  • 运行状态->等待状态(IO请求)
  • 运行态->就绪态(中断)
  • 等待态->就绪态(IO完成)
  • 进程终止

调度方案

  • 非抢占式:一旦某个进程分配到CPU,就会一直使用CPU,直到该进程切换到等待状态或终止。(1或4)

  • 抢占式

多个进程共享数据时,抢占式可能导致竞争情况。

调度程序:将CPU控制权交给调度程序选择的进程。调度所需时间叫调度延迟

  • 切换上下文
  • 切换到用户模式
  • 跳转到用户程序合适位置, 以便重新启动程序

2.调度准则

最大化CPU使用率和吞吐量,并且最小化周转时间,等待时间和响应时间

3.调度算法

3.1 先到先服务FCFS

先请求CPU的进程先分配到CPU。最简单,可以使用FIFO队列实现。

缺点

  • 平均等待时间往往很长
  • 调度性能不好,CPU和IO使用率低。“护航效果”
  • 非抢占式。一旦CPU分配给了某个进程,该进程就会一直使用CPU,直到终止或IO

3.2 最短作业优先SJF

该算法将每个进程与其下次CPU执行的长度关联起来。当CPU空闲时,会先分配给具有最短CPU执行的进程。

因此该算法也叫做最短下次CPU执行算法。

可以证明,SJF算法是最优的,平均等待时间最少。但是困难的是,如何知道下次CPU执行的长度。

在批处理的长期调度中,可以将用户指定的进程时限作为长度。但是短期调度就无法实现了,只能根据历史情况近似预测。

3.3 优先级调度

每个进程都有一个优先级与其关联,高优先级的进程会分配到CPU。

上一个算法SJF是优先级调度的一个特例,其优先级是下次CPU执行的时间的倒数。CPU执行越长,优先级越小。

优先级的定义分为内部和外部。内部采用测量数据来定义,例如时限,内存,打开文件数量等。外部定义例如进程的重要性等

存在的问题:“无穷阻塞”,低优任务可能永远获取不到CPU

解决方案:“老化”,逐渐增加低优任务的优先级

3.4 轮转调度

3.5 多级队列调度

3.6 多级反馈队列调度