请输入您要查询的百科知识:

 

词条 调度算法
释义

调度算法

在操作系统中调度是指一种自远方分配,因而调度算法是指:根据系统的资源分配策略所规定的资源分配算法。对于不同的的系统和系统目标,通常采用不同的调度算法,例如,在批处理系统中,为了照顾为数众多的段作业,应采用短作业优先的调度算法;又如在分时系统中,为了保证系统具有合理的响应时间,应当采用轮转法进行调度。目前存在的多种调度算法中,有的算法适用于作业调度,有的算法适用于进程调度;但也有些调度算法既可以用于作业调度,也可以用于进程调度。

通常将作业或进程归入各种就绪或阻塞队列。

调度算法分类

1.先来先服务(FCFS)

先来先服务(FCFS, First Come First Serve)是最简单的调度算法,按先后顺序进行调度。

1. FCFS算法

按照作业提交或进程变为就绪状态的先后次序,分派CPU; 当前作业或进程占用CPU,直到执行完或阻塞,才出让CPU(非抢占方式)。 在作业或进程唤醒后(如I/O完成),并不立即恢复执行,通常等到当前作业或进程出让CPU。最简单的算法。

2. FCFS的特点

比较有利于长作业,而不利于短作业。 有利于CPU繁忙的作业,而不利于I/O繁忙的作业。

2. 轮转法(Round Robin)

轮转法(Round Robin)是让每个进程在就绪队列中的等待时间与享受服务的时间成正比例。

1. 轮转法

将系统中所有的就绪进程按照FCFS原则,排成一个队列。

每次调度时将CPU分派给队首进程,让其执行一个时间片。时间片的长度从几个ms到几百ms。

在一个时间片结束时,发生时钟中断。

调度程序据此暂停当前进程的执行,将其送到就绪队列的末尾,并通过上下文切换执行当前的队首进程。? 进程可以未使用完一个时间片,就出让CPU(如阻塞)。

2. 时间片长度的确定

时间片长度变化的影响2 过长->退化为FCFS算法,进程在一个时间片内都执行完,响应时间长。2 过短->用户的一次请求需要多个时间片才能处理完,上下文切换次数增加,响应时间长。

对响应时间的要求:T(响应时间)=N(进程数目)*q(时间片)

就绪进程的数目:数目越多,时间片越小

系统的处理能力:应当使用户输入通常在一个时间片内能处理完,否则使响应时间,平均周转时间和平均带权周转时间延长。

3. 多级反馈队列算法(Round Robin with Multiple Feedback)

多级反馈队列算法时间片轮转算法和优先级算法的综合和发展。优点:2 为提高系统吞吐量和缩短平均周转时间而照顾短进程。2 为获得较好的I/O设备利用率和缩短响应时间而照顾I/O型进程。2 不必估计进程的执行时间,动态调节。

1. 多级反馈队列算法2 设置多个就绪队列,分别赋予不同的优先级,如逐级降低,队列1的优先级最高。每个队列执行时间片的长度也不同,规定优先级越低则时间片越长,如逐级加倍。2 新进程进入内存后,先投入队列1的末尾,按FCFS算法调度;若按队列1一个时间片未能执行完,则降低投入到队列2的末尾,同样按FCFS算法调度;如此下去,降低到最后的队列,则按“时间片轮转”算法调度直到完成。2 仅当较高优先级的队列为空,才调度较低优先级的队列中的进程执行。如果进程执行时有新进程进入较高优先级的队列,则抢先执行新进程,并把被抢先的进程投入原队列的末尾。2

2. 几点说明2

I/O型进程:让其进入最高优先级队列,以及时响应I/O交互。通常执行一个小时间片,要求可处理完一次I/O请求的数据,然后转入到阻塞队列。2

计算型进程:每次都执行完时间片,进入更低级队列。最终采用最大时间片来执行,减少调度次数。2 I/O次数不多,而主要是CPU处理的进程。在I/O完成后,放回优先I/O请求时离开的队列,以免每次都回到最高优先级队列后再逐次下降。2 为适应一个进程在不同时间段的运行特点,I/O完成时,提高优先级;时间片用完时,降低优先级。

3.shortest job next

系统计算程序调用的时间,时间最短的先执行。

随便看

 

百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。

 

Copyright © 2004-2023 Cnenc.net All Rights Reserved
更新时间:2025/3/4 0:36:31