常用调度算法比例公平算法

比例公平算法

轮询算法保证了用户间的公平性，但损失系统吞吐量；最大载干比算法获得了最大的系统吞吐量，但丧失了公平性。因此，为了在这两种算法间取得一定的折衷，提出了比例公平算法。该方法在尽量满足信道质量较好的终端的高速数据业务需求的同时，也兼顾信道质量状况不好的终端的使用体验。该算法的基本思想是在选择用户时考虑瞬时速率和长期平均速率的比值，同时利用权重值对不同用户进行调整，达到同时兼顾系统性能和用户体验的目的。

此算法为小区内每个用户都分配了一个优先级，在任意时刻系统调度优先级最大的用户，比例公平算法的数学表达式可以参考式（2），其中k是被调度用户，Ri(t)为用户i在t时刻请求的速率，Ti(t)为用户i在t时刻的累积平均速率。在调度完成后，需要对用户的优先级因子进行更新。若小区中有多个用户，当系统对某个信道质量较好的用户连续进行了调度时，Ti(t)将会逐渐增大，使得优先级逐渐变小，从而系统会调度其他优先级较高的用户。若某个用户的信道质量较差，长期得不到系统的调度，那么它的平均吞吐量Ti(t)会降低，这样的话优先级将会增大，使用户获得被调度的机会。比例公平算法综合考虑了公平性和系统性能两方面的因素，是一种性能较优的算法。

k= arg max

最大载干比算法的基本思想是在每一个调度时刻，调度器会对所有待调度用户进行载干比（也就是意味着可以达到的最大瞬时传输速率）的排序，然后调度器会选择信道质量最好的用户进行调度，这样保证系统总是能够调度到最好的用户，保证系统性能的最大化，资源利用率最高。最大载干比算法的数学表达可以参考式（1），其中k是被调度的用户，Ri(t)是第i个用户的瞬时传输速率。

k=argmaxRi(t)（1）

可见，最大载干比算法是一种追求系统性能最大化的调度算法，在调度周期内把所有资源分配给信号质量最好的终端，保证系统吞吐量可以达到最大值。但是，该方法完全没有考虑公平性的因素，对于处于小区边缘或深衰落处的终端因为信号质量不好将会长时间得不到调度，出现终端被“饿死”的情况。

轮询算法的基本思想就是认为小区内所有用户的调度优先级都是相等的，所有用户周期性地被调度，保证每个用户被调度概率相同。例如小区中有3个用户，采用轮询算法的调度器不会考虑每个用户所处的位置以及之前被调度的情况，只是简单地按照某个固定的调度顺序，如终端1、终端2、终端3、终端1、终端2、终端3……周期性地调度每个用户。因此轮询算法是一种典型的追求公平最大化的调度算法，实现起来比较简单。但是，轮询算法没有考虑不同用户的信道状况，信道质量差的用户和信道质量好的用户会被分配到相同多的调度时间，因此会导致系统的平均吞吐量受到较大影响。同时该算法也没有考虑业务特性、用户优先级、业务优先级等QoS方面的因素，所以在系统用户数较多、业务复杂的情况下，轮询算法难以发挥理想的调度效果。

计算机系统是由许多程序或进程需要使用的资源(例如处理机周期、存储单元和输入/输出设备)的 有限集合所组成的。调度算法的目标是把这些资源分配给要求它们的程序。 在每一判定时刻，调度算法 必须决定下一次应是若干相竞争的进程中的哪一个进程接收一给定资源。因而调度算法是指：根据系统的资源分配策略所规定的资源分配算法。对于不同的系统和系统目标，通常采用不同的调度算法，例如，在批处理系统中，为了照顾为数众多的短作业，应采用短作业优先的调度算法；又如在分时系统中，为了保证系统具有合理的响应时间，应采用轮转法进行调度。目前存在的多种调度算法中，有的算法适用于作业调度，有的算法适用于进程调度；但也有些调度算法既可用于作业调度，也可用于进程调度。2100433B

通常系统的设计目标不同，所采用的调度算法也不同。在操作系统中存在多种调度算法，其中有的调度算法适用于作业调度，有的调度算法适用于进程调度，有的调度算法两者都适用。下面介绍几种常用的调度算法：

FIFS先来先服务调度算法

特点：算法简单，但是效率低；有利于长作业，不利于短作业；有利于CPU繁忙型作业而不利于IO繁忙型作业。

SJF短作业优先调度算法

短作业（进程）优先调度算法是指对短作业祸端进程优先调度的算法。短作业优先调度算法是从后备队列中选择一个或若干个估计运算时间最短的作业，将他们呢掉入内存运行。

SJF调度算法的缺点：

1） 该算法对长作业不理。

2） 该算法完全未考虑作业的紧迫程度

3） 由于作业的长短只根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意的缩短其作业的估计运行时间，致使该算法不一定能真正做到算作业优先调度。

4） 注意：SJF调度算法的平均等待时间、平均周转时间最少。

高响应比优先调度算法

高响应比优先调度算法主要用于作业调度。同时考虑从每个作业的等待时间和估计需要运行的时间。

时间片轮转调度算法

时间片轮转调度算法主要适用于分时系统。

多级反馈队列调度算法

多级反馈队列调度算法主要是时间片轮转调度算法和优先级调度算法的综合和发展。通过动态调整进程优先级和时间片大小，多级反馈队列调度算法可以兼顾多方面的系统目标。

表调度算法的基本思想是通过对节点的优先级别进行排序来构造一个调度列表。

然后重复以下两个步骤直到任务图中所有节点被调度完毕：①从调度列表中顺序取出一个节点；②将节点分配到使它的启动时间最早的处理机器上。

这是传统的静态表调度算法，一些新的表调度算法是基于动态列表的调度算法，与静态方法调度列表一经构造就不会改变不同，动态列表算法在每次分配节点之后都重新计算所有未被调度节点的优先级别，并根据新的优先级别来重新安排列表中节点的顺序。

这样，动态表调度算法实际分为三步：①确定所有未被调度节点的新优先级别；②选择具有最高优先级别的节点进行调度；③将节点分配到使它的启动时间最早的处理机上。

决定节点优先级别的方法很多，有HLF(Highest LevelFirst)、LP(Longest Path)、LPT(Longest Processing Time)、CP(Critical Path)等。

2100433B