处理机调度算法详解专题
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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!