❶ 最佳调度问题：假设有n个任务由k个并行工作的机器来完成。完成任务i需要的时间为Ti。试设计一个算法找出完
Node{
int Path[n]; //节点对应的解空间树的路径，即到该节点为止的策略记录
int T[k]; //在本策略下的每台机器的运行时间
int Time; //本策略的总执行时间，为每台机器运行时间的最大值
int length; //本节点的深度,即当前处理的作业
}
Proc BestDispatch(int n,int k,int t[])
Node Boot,X,P,result; //Boot为根节点，result保存最优解
int f; //记录当前最优解的执行时间
f=n*max(t[]); //初始化f
Boot.T[n]={0};
Boot.Time=0;
Boot.Path[n]={0};
Boot.length=0; //初始化根节点
AddHeap(Boot); //根节点加入堆中，堆中元素按照Time值由小到大排序
While !Heap.empty() do
P=DeleteMinHeap(); //P为当前优先级最高的点
for i=1 to k do //扩展P的k个子节点
X=Newnode(P.Path[],P.T[],P.length+1);
X.Path[X.length]=i;
X.T[i]=X.T[i]+t[X.length];
X.Time=max(X.T[]);
if X.length==n then //X为叶节点
if X.Time<f then //X的执行时间小于已知最优解
f=X.Time; //将X设为最优解
result=X;
end{if}
else //X为中间节点
if X.Time<f then
AddHeap(X);
end{if}//X的当前执行时间小于已知最优解则加入堆中，否则剪去
end{if}
end{for}
end{while}
end{ BestDispatch }
❷ 调度算法详细资料大全
作业系统管理了系统的有限资源，当有多个进程（或多个进程发出的请求）要使用这些资源时，因为资源的有限性，必须按照一定的原则选择进程（请求）来占用资源。这就是调度。目的是控制资源使用者的数量,选取资源使用者许可占用资源或占用资源。
基本介绍
调度算法,评价因素,吞吐量,CPU利用率,周转时间,确定进程调度原则,调度算法分类,先来先服务(FCFS),轮转法(Round Robin),多级反馈伫列算法,
linux进程调度算法,
调度算法
在作业系统中调度是指一种资源分配，因而调度算法是指：根据系统的资源分配策略所规定的资源分配算法。对于不同的的系统和系统目标，通常采用不同的调度算法，例如，在批处理系统中，为了照顾为数众多的段作业，应采用短作业优先的调度算法；又如在分时系统中，为了保证系统具有合理的回响时间，应当采用轮转法进行调度。目前存在的多种调度算法中，有的算法适用于作业调度，有的算法适用于进程调度；但也有些调度算法既可以用于作业调度，也可以用于进程调度。 通常将作业或进程归入各种就绪或阻塞伫列。 调度算法要求：高资源利用率、高吞吐量、用户满意等原则。 进程调度所采用的算法是与整个系统的设计目标相一致的： 1.批处理系统：增加系统吞吐量和提高系统资源的利用率; 2.分时系统：保证每个分时用户能容忍的回响时间。 3.实时系统：保证对随机发生的外部事件做出实时回响。
评价因素
吞吐量
单位时间内CPU完成作业的数量。
CPU利用率
从0%～100%。
周转时间
评价批处理系统的性能指标。 Ti = 作业完成时刻 － 作业提交时刻
确定进程调度原则
在系统角度来说，公平性：每个进程（不论优先权）都有机会被运行；较大的吞吐量。 用户角度：及时性：回响速度要快；较短的周转时间：不应当让用户等待时间过长。
调度算法分类
先来先服务(FCFS)
先来先服务（FCFS, First Come First Serve）是最简单的调度算法，按先后顺序进行调度。 1. FCFS算法 按照作业提交或进程变为就绪状态的先后次序，分派CPU； 当前作业或进程占用CPU，直到执行完或阻塞，才出让CPU（非抢占方式）。 在作业或进程唤醒后（如I/O完成），并不立即恢复执行，通常等到当前作业或梁兆进程出让CPU。最简单的算法。 2. FCFS的特点 比较有利于长作业，而不利于短作业。 有利于CPU繁忙的作业，而不利于I/O繁忙的作业。
轮转法(Round Robin)
轮转法(Round Robin)是让每个进程在就绪伫列中的等待时间与享受服务的时间成正比例。 1. 轮转法 将系统中所有的就绪进程按照FCFS原则，排成一个伫列。 每次调度时将CPU分派给队碧渣戚首进程，让其执行一个时间片。时间片的长度从几个ms到几百ms。 在一个时间片结束时，发生时钟中断。 调度程式据此暂停当前进程的执行，将其送到就绪伫列的末尾，并通过上下文切换执行当前的队首进程。? 进程可以未使用完一个时间片，就出让CPU（如阻塞）。 2. 时间片长度的确定 时间片长度变化的影响2 过长－>退化为FCFS算法，进程在一个时间片内都执行完，回响时间长。2 过短－>用户的一次请求需要多个时间片才能处理完，上下文切换次数增加，回响时间长。 对回响时间的要求：T(回响悔陵时间)=N(进程数目)*q(时间片) 就绪进程的数目：数目越多，时间片越小 系统的处理能力：应当使用户输入通常在一个时间片内能处理完，否则使回响时间，平均周转时间和平均带权周转时间延长。
多级反馈伫列算法
多级反馈伫列算法时间片轮转算法和优先权算法的综合和发展。优点：2 为提高系统吞吐量和缩短平均周转时间而照顾短进程。2 为获得较好的I/O设备利用率和缩短回响时间而照顾I/O型进程。2 不必估计进程的执行时间，动态调节。 1. 多级反馈伫列算法2 设定多个就绪伫列，分别赋予不同的优先权，如逐级降低，伫列1的优先权最高。每个伫列执行时间片的长度也不同，规定优先权越低则时间片越长，如逐级加倍。2 新进程进入记忆体后，先投入伫列1的末尾，按FCFS算法调度；若按伫列1一个时间片未能执行完，则降低投入到伫列2的末尾，同样按FCFS算法调度；如此下去，降低到最后的伫列，则按“时间片轮转”算法调度直到完成。2 仅当较高优先权的伫列为空，才调度较低优先权的伫列中的进程执行。如果进程执行时有新进程进入较高优先权的伫列，则抢先执行新进程，并把被抢先的进程投入原伫列的末尾。 2. 几点说明 I/O型进程：让其进入最高优先权伫列，以及时回响I/O互动。通常执行一个小时间片，要求可处理完一次I/O请求的数据，然后转入到阻塞伫列。 计算型进程：每次都执行完时间片，进入更低级伫列。最终采用最大时间片来执行，减少调度次数。 I/O次数不多，而主要是CPU处理的进程。在I/O完成后，放回优先I/O请求时离开的伫列，以免每次都回到最高优先权伫列后再逐次下降。2为适应一个进程在不同时间段的运行特点，I/O完成时，提高优先权；时间片用完时，降低优先权。 3.shortest job next 系统计算程式调用的时间，时间最短的先执行。
linux进程调度算法
linux核心的三种调度方法： 1. SCHED_OTHER 分时调度策略， 2. SCHED_FIFO实时调度策略，先到先服务 3. SCHED_RR实时调度策略，时间片轮转 实时进程将得到优先调用，实时进程根据实时优先权决定调度权值，分时进程则通过nice和counter值决 定权值，nice越小，counter越大，被调度的机率越大，也就是曾经使用了cpu最少的进程将会得到优先调 度。 SHCED_RR和SCHED_FIFO的不同： 当采用SHCED_RR策略的进程的时间片用完，系统将重新分配时间片，并置于就绪伫列尾。放在伫列 尾保证了所有具有相同优先权的RR任务的调度公平。 SCHED_FIFO一旦占用cpu则一直运行。一直运行直到有更高优先权任务到达或自己放弃。 如果有相同优先权的实时进程（根据优先权计算的调度权值是一样的）已经准备好，FIFO时必须等待该 进程主动放弃后才可以运行这个优先权相同的任务。而RR可以让每个任务都执行一段时间。 SHCED_RR和SCHED_FIFO的相同点： SHCED_RR和SHCED_FIFO都只用于实时任务。 创建时优先权大于0(1-99)。 按照可抢占优先权调度算法进行。 就绪态的实时任务立即抢占非实时任务。 所有任务都采用linux分时调度策略时。 1. 创建任务指定采用分时调度策略，并指定优先权nice值(-20~19)。 2. 将根据每个任务的nice值确定在cpu上的执行时间(counter)。 3. 如果没有等待资源，则将该任务加入到就绪伫列中。 4. 调度程式遍历就绪伫列中的任务，通过对每个任务动态优先权的计算(counter+20-nice)结果，选择 计算结果最大的一个去运行，当这 个时间片用完后(counter减至0)或者主动放弃cpu时，该任务将被放在 就绪伫列末尾(时间片用完)或等待伫列(因等待资源而放弃cpu)中。 5. 此时调度程式重复上面计算过程，转到第4步。 6. 当调度程式发现所有就绪任务计算所得的权值都为不大于0时，重复第2步。 所有任务都采用FIFO时: 1. 创建进程时指定采用FIFO，并设定实时优先权rt_priority(1-99)。 2. 如果没有等待资源，则将该任务加入到就绪伫列中。 3. 调度程式遍历就绪伫列，根据实时优先权计算调度权值(1000+rt_priority),选择权值最高的任务使用 cpu，该FIFO任务将一直占有cpu直到有优先权更高的任务就绪(即使优先权相同也不行)或者主动放弃(等 待资源)。 4. 调度程式发现有优先权更高的任务到达(高优先权任务可能被中断或定时器任务唤醒，再或被当前运行 的任务唤醒，等等)，则调度程式立即在当前任务 堆叠中保存当前cpu暂存器的所有数据，重新从高优先权 任务的堆叠中载入暂存器数据到cpu，此时高优先权的任务开始运行。重复第3步。 5. 如果当前任务因等待资源而主动放弃cpu使用权，则该任务将从就绪伫列中删除，加入等待伫列，此时 重复第3步。 所有任务都采用RR调度策略时 1. 创建任务时指定调度参数为RR，并设定任务的实时优先权和nice值(nice值将会转换为该任务的时间片 的长度)。 2. 如果没有等待资源，则将该任务加入到就绪伫列中。 3. 调度程式遍历就绪伫列，根据实时优先权计算调度权值(1000+rt_priority),选择权值最高的任务使用 cpu。 4. 如果就绪伫列中的RR任务时间片为0，则会根据nice值设定该任务的时间片，同时将该任务放入就绪队 列的末尾。重复步骤3。 5. 当前任务由于等待资源而主动退出cpu，则其加入等待伫列中。重复步骤3。 系统中既有分时调度，又有时间片轮转调度和先进先出调度 1. RR调度和FIFO调度的进程属于实时进程，以分时调度的进程是非实时进程。 2. 当实时进程准备就绪后，如果当前cpu正在运行非实时进程，则实时进程立即抢占非实时进程。 3. RR进程和FIFO进程都采用实时优先权做为调度的权值标准，RR是FIFO的一个延伸。FIFO时，如果两 个进程的优先权一样，则这两个优先 级一样的进程具体执行哪一个是由其在伫列中的未知决定的，这样导 致一些不公正性(优先权是一样的，为什么要让你一直运行?),如果将两个优先权一样的任务 的调度策略都 设为RR,则保证了这两个任务可以循环执行，保证了公平。
❸ 常见的调度算法总结
一、FCFS——先来先服务和短作业（进程）优先调度算法
1. 先来先服务调度算法。
先来先服务（FCFS）调度算法是一种最简单的调度算法，该算法既可用于作业调度， 也可用于进程调度。FCFS算法比较有利于长作业（进程），而不利于短作业（进程）。由此可知，本算法适合于CPU繁忙型作业， 而不利于I/O繁忙型的作业（进程）。
2. 短作业（进程）优先调度算法。
短作业（进程）优先调度算法（SJ/PF）是指对短作业或短进程优先调度的算法，该算法既可用于作业调度， 也可用于进程调度。但其对长作业不利；不能保证紧迫性作业（进程）被及时处理；作业的长短只是被估算出来的。
二、FPF高优先权优先调度算法
1. 优先权调度算法的类型。
为了照顾紧迫性作业，使之进入系统后便获得优先处理，引入了最高优先权优先（FPF）调度算法。 此算法常被用在批处理系统中，作为作业调度算法，也作为多种操作系统中的进程调度，还可以用于实时系统中。当其用于作业调度， 将后备队列中若干个优先权最高的作业装入内存。当其用于进程调度时，把处理机分配给就绪队列中优先权最高的进程，此时， 又可以进一步把该算法分成以下两种：
1)非抢占式优先权算法
2)抢占式优先权调度算法（高性能计算机操作系统）
2. 优先权类型 。
对于最高优先权优先调度算法，其核心在于：它是使用静态优先权还是动态优先权， 以及如何确定进程的优先权。
3.动态优先权
高响应比优先调度算法为了弥补短作业优先算法的不足，我们引入动态优先权，使作业的优先等级随着等待时间的增加而以速率a提高。 该优先权变化规律可描述为：优先权=（等待时间+要求服务时间）/要求服务时间；即 =（响应时间）/要求服务时间
三、基于时间片的轮转调度算法
1.时间片轮转法。
时间片轮转法一般用于进程调度，每次调度，把CPU分配队首进程，并令其执行一个时间片。 当执行的时间片用完时，由一个记时器发出一个时钟中断请求，该进程被停止，并被送往就绪队列末尾；依次循环。
2. 多级反馈队列调度算法
多级反馈队列调度算法多级反馈队列调度算法，不必事先知道各种进程所需要执行的时间，它是目前被公认的一种较好的进程调度算法。 其实施过程如下：
1) 设置多个就绪队列，并为各个队列赋予不同的优先级。在优先权越高的队列中， 为每个进程所规定的执行时间片就越小。
2) 当一个新进程进入内存后，首先放入第一队列的末尾，按FCFS原则排队等候调度。 如果他能在一个时间片中完成，便可撤离；如果未完成，就转入第二队列的末尾，在同样等待调度…… 如此下去，当一个长作业（进程）从第一队列依次将到第n队列（最后队列）后，便按第n队列时间片轮转运行。
3) 仅当第一队列空闲时，调度程序才调度第二队列中的进程运行；
仅当第1到第（ i-1 ）队列空时， 才会调度第i队列中的进程运行，并执行相应的时间片轮转。
4) 如果处理机正在处理第i队列中某进程，又有新进程进入优先权较高的队列， 则此新队列抢占正在运行的处理机，并把正在运行的进程放在第i队列的队尾。
❹ 操作系统的调度算法
1)10:00Job1到达并投入运行。此时内存中有作业:Job1
2)10:05 Job2到达并进入内存。此时，Job1运行时间剩余是25min， Job2运行剩余时间是20min，根据SRTF，Job2开始运行。
3)10:25 Job2运行结束。Job3、Job4在后备队列中，据SJF，Job3进入内存，据SRTF，Job3开始运行。内存：Job1、Job3
4)10:30 Job3运行结束。Job4在后备队列中，Job4进入内存，据SRTF，Job4开始运行。内存：Job1、Job4
5)10:40 Job4运行结束。Job1重新继续运行。
6)11:05 Job1运行结束。
❺ 怎么用C语言实现多级反馈队列调度算法
调度算法的实施过程如下所述：（1）应设置多个就绪队列，并为各个队列赋予不同的优先级。（2）当一个新进程进入内存后，首先将它放入第一队列的末尾，按FCFS的原则排队等待调度。当轮到该进程执行时，如他能在该时间片内完成，便可准备撤离系统；如果它在一个时间片结束时尚未完成，调度程序便将该进程转入第二队列的末尾，再同样地按FCFS原则等待调度执行；如果它在第二队列中运行一个时间片后仍未完成，再依次将它放入第三队列……，如此下去，当一个长作业进程从第一队列依次降到第N队列后，在第N队列中便采取时间片轮转的方式运行