处理机调度算法详解专题

2023-12-18 22:35:50

一.基础理论

1.基本概念

? ? ? ? 计算机中的资源数量有限无法处理多个任务时,需要制定某种规则来决定处理这些任务的顺序;处理机调度是对处理机进行分配,即从就绪队列中按照一定的算法(公平、高效的原则)选择一个进程并将处理机分配给它运行,以实现进程并发地执行~

? ? ? ? 处理机调度是多道操作系统的基础,是操作系统设计的核心问题~

2.层次

  • 高级调度:即作业调度,按照一定的规则从外存上处于后备队列的作业中挑选一个(或多个),给它们分配内存、输入/输出设备等必要的资源,并建立相应的进程~
  • 中级调度:即内存调度,引入的目的是提高内存利用率和系统吞吐量,为此,将那些暂时不能运行的进程调度至外存等待——此时进程的状态被称为挂起态
  • 低级调度:即进程调度,按照某种算法从就绪队列中选择一个进程,将处理机分配给它,使用频率极高,是最基本的一种调度

二.调度算法

1.先来先服务FCFS

  • 最简单的调度算法,既可以用于作业调度,也可以用于进程调度~
  • 每次从后备作业队列中选择最优先进入该队列的进程,将处理机分配给它使其投入运行,直到运行完成或者金额因为某种原因阻塞才会归还处理机~

? ? ? ? 属于不可剥夺算法,表面上对所有作业公平,但长作业先到后则其他作业会等很长时间,不适用于分时和实时OS~

特点:

  • 算法简单但是效率低
  • 长作业有利,短作业不利
  • 有利于CPU繁忙的作业,不利于IO繁忙的作业
  • 不会导致饥饿?

2.短作业优先SJF

从后备队列中选择约个或若干个估计运行时间最短的作业(即需求服务时间最短~)

  • 默认为非抢占式的模式
  • 追求最少的平均等待时间、平均周转时间
  • 对长作业不利(长作业会)

3.优先级调度算法

????????所谓的优先级用于描述作业的紧迫程度,在作业调度中,优先级算法每次从后备作业中选择优先级最高的一个或者几个作业,将他们调入进程并放入就绪队列。

4.高响应比优先调度算法

  • FCFS和SJF的一种综合平衡
  • 响应比计算公式:等待时间+要求服务时间的和,再与要求服务时间做商
  • 同样也是非抢占式的算法,只能由进程主动放弃
  • 可以克服饥饿现象

5.时间片轮转调度算法RR

????????调度程序选择就绪队列的第一个进程执行并分配一个时间片。在一个时间片用完之后,即使进程并未运行完成,它也必须释放出处理机给下一个就绪进程~

  • 优点在于公平,而缺点则是不区分紧急程度
  • 抢占式算法,由有关时钟中断的硬件来实现
  • 伴随着分时OS的诞生而诞生

6.多级队列调度算法

????????该算法在系统中设置多个就绪队列,将不同类型或性质的进程固定分配到不同的就绪队列,每个队列可以实施不同的调度算法,因此,系统针对不同进程的需求,很容易提供多种调度策略。同一队列中的进程可以设置不同的优先级,不同的队列本身也可以由不同的优先级——适用于多处理机的系统,每个处理机拥有一个单独的就绪队列~

7.多级反馈队列调度算法

通过动态调整进程优先级和时间片的大小,多级反馈队列调度算法可以兼顾多方面的系统目标。

步骤:

  • 设置多个就绪队列,并为每个队列设置不同的优先级
  • 优先级越高的队列,每个进程赋予的时间片就越小
  • 每个队列都采用先来先服务的FCFS先来先服务?

表格对比一下各种调度算法的区别:

文章来源:https://blog.csdn.net/jsl123x/article/details/135057055
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。