基于公平原则的调度算法

第２１卷第１期　２０１４年２月　兰州工业学院学报　Ｊｏｕｒｎａｌ　ｏｆ　Ｌａｎｚｈｏｕ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ　Ｖｏ１．２１　Ｎｏ．１　Ｆｅｂ．２０１４　

文章编号：１００９—２２６９（２０１４）０１－０００１－０４　

多用户ＭＩ　ＭＯ无线通信系统中基于ＱｏＳ的　

比例公平调度算法研究　

秦玉娟　，张伯楠　

（１．兰州工业学院电子信息工程学院，甘肃兰州７３００５０；２．中国电信甘肃公司网优中心，甘肃兰州７３００００；）　

摘要：未来的无线通信系统是一个多业务系统，不同的业务有不同的ＱｏＳ要求，如最大时延和最小　

误码率等，这就要求调度算法在提高系统吞吐量和保证用户公平性的同时，还要提供对不同业务　

ＱｏＳ的区分保障机制．针对这一趋势，在比例公平调度算法的基础上，通过引入表征ＱｏＳ的参数，　

提出了一种改进的可以保证ＱｏＳ的比例公平调度算法，并对改进算法的各项性能进行计算机仿　

真，验证了它的性能．　

关键词：ＭＩＭＯ；比例公平调度；ＱｏＳ　

中图分类号：ＴＮ９１９．７２　文献标志码：Ａ　

０　引言　

ＭＩＭＯ是未来无线通信中将要采用的关键技　

术之一，与传统的单天线系统相比，ＭＩＭＯ的多天　

线配置有很多优点．从用户调度的角度来说，ＭＩＭＯ　

系统由于在发射端使用多副天线，可以实现在一个　

调度时刻同时调度多个用户．相对于传统单天线系　

统中只调度一个用户，ＭＩＭＯ的多用户调度可以实　

现更多的分集增益，使系统性能进一步提高．但是，　

在ＭＩＭＯ多用户调度中，同时调度多个用户，会使　

每个用户的数据受到来自其他用户数据的干扰，即　

多用户干扰问题．为了抑制或消除这种干扰，主要　采用在发射端进行发射信号预处理的办法，从而使　

整个系统的容量大大提高．这些技术的实现，为多　

用户调度提供了强大的支持．如今已有一些在多用　

户调度方面的研究，比如基于随机波束成形的调度　

方案、后端比例公平门限调度算法等．　

另外，调度时的用户信息反馈量也是值得注意　

第２１卷第６期　２０１４年１２月　兰州工业学院学报　Ｊｏｕｒｎａｌ　ｏｆ　Ｌａｎｚｈｏｕ　Ｉｎｓｔｉｔｕｔｅ　ｏｆ　Ｔｅｃｈｎｏｌｏｇｙ　Ｖｏｌ＿２１　Ｎｏ．６　Ｄｅｅ．２０１４　

文章编号：１００９－２２６９（２０１４）０６－００１７－０４　

基于比例公平的改进调度算法研究　

吴守霞　，高晓艳　

（１．兰州工业学院电子信息工程学院，甘肃兰州７３００５０；　２．甘肃省新闻出版广电局无线传输中心５３５台，甘肃兰州７３００４６）　

摘要：通过分析无线网络中经典的调度算法，比较各种算法的性能特点，给出一种改进的调度算　

法，并验证了其短期服务时间保证的性能．结果表明，该方法具有较好的短期公平保证，提高了调　

度算法的整体性能，在未来的移动通信系统中有较好的应用前景．　

关键词：调度算法；短期服务；比例公平　

中图分类号：ＴＮ９２９．５　文献标志码：Ａ　

Ｏ　引言　

无线网络的业务拥有不同的特点和服务质量　

ＱｏＳ级别，ＦＴＰ、Ｅ—ｍａｉｌ这些数据业务属于非实时业　

务，用户对传输延迟没有限制，最关心的是传输数　

据量的大小；对于网页浏览等类型的业务，用户要　

求保证访问时延在允许的范围内，还需要保证足够　

的传输数据量；语音，视频电话是典型的实时业务，　

用户对延迟很敏感¨　．经典ＰＦ（Ｐｒｏｐｏｒｔｉｏｎａｌ　Ｆａｉｒ）　

算法虽然能保证长时公平性，但是没有考虑到用户　

ＱｏＳ时延要求，当用户数增多无法为用户提供短期　

时间公平，会造成数据堆存出现“饿死”状况．本文　

以数据业务为研究对象，提出了一种以公平调度准　

则为基础，具有短期服务时间保证的改进分组调度　

算法．　

１　调度算法的目标　

分组调度算法主要解决的问题是：在等待传输　

的多个分组业务中，选择高效合理的分组调度算　

法，确定好等待传输业务的服务次序和服务时　

间　ｊ．高效合理的调度算法能够保障ＣＤＭＡ实现大　

数据容量和快速传输速率．衡量调度算法最重要的　

收稿日期：２０１４　０７—２７　作者简介：吴守霞（１９７９－），女，甘肃景泰人，讲师，硕士　两个指标是公平性和吞吐量．　

第２５卷第１期　２０１０年２月　成都信息工程学院学报　ＪＯＵＲＮＡＬＯＦＣＨＥＮＧＤＵＵＮＩＶＥＲＳｎ’ＹＯＦＩＮＦＯＲＭＡＴＩＯＮＴＥＣＨＮＯＬＯＧＹ　Ｖ０１．２５Ｎｏ．１　Ｆｅｂ．２０１０　

文章编号：１６７１　１７４２｛２０１０）０１．００１８．０４　

完全公平调度算法分析　

朱　旭，　杨　斌，　刘海涛　

（西南交通大学信息科学与技术学院，四川成都６１００３１）　

摘要：ｈｉｎｕｘ调度系统的调度算法几经改进，表现出优异的性能，特别是Ｌｉｎｕｘ最新的ＣＦＳ调度算法。它的设　计目的是使进程更加公平地共享处理器资源。在分析Ｌｉｎｕｘ　２．６．２８内核代码的基础上详细阐述了ＣＦＳ调度算法　的工作流程和主要特性，并从算法分析和Ｈａｃｋｂｅｎｃｈ测试两个方面对ｏ（１）和ＣＦＳ调度算法的性能进行了对比。　关键词：计算机科学与技术；计算机应用技术；完全公平调度算法；公平性　中图分类号：ＴＰ３９１　文献标识码：Ａ　

１　引言　

进程调度是操作系统的核心功能，其主要目的是合理分配处理器资源。调度算法是任务调度具体的实现方　法，一个好的调度算法将实现公平、效率、响应时间、周转时间、吞吐量等多个调度目标间的平衡。自Ｌｉｎｕｘ　２．４　

调度器使用基于优先级的调度算法以来，Ｌｉｎｕｘ２．６开发系列的内核中又经历了Ｏ（１）、ＲＳＤＬ、ＳＤ和ＣＦＳ调度算　法。其中ＣＦＳ是Ｌｉｎｕｘ２．６．２３内核引入的全新调度算法，相对于Ｏ（１），ＣＦＳ进行了很大改动，它以完全公平作为　

调度的核心思想，在性能提升的基础上大大简化了代码，成为内核采用的新一代调度算法。　

２　ＣＦＳ概述　

ＣＦＳ的总体设计可以用一句话来总结：在真实的硬件上模拟“理想的多任务处理器”，使每个进程都尽可能公　平的获得ＣＰＵ。为此，ＣＦＳ引入了一个新概念“ｖｉｒｔｕａｌ　ｒｕｎｔｉｍｅ”，它描述了进程在ＣＰＵ上的执行时问。在调度的　

过程中，ＣＦＳ为了使每个进程都获得相近的执行时间，总是选取ｖｒｕｎｔｉｍｅ最小，也就是执行时间最短的进程来运　

响应比高者优先调度算法

响应比高者优先调度算法（Response Ratio Scheduling）是一种可以在多道程序环境中有效控制响应时间并改善系统性能的调度算法。它是基于响应比的原则，将响应时间和作业优先级结合起来，根据作业的响应比来决定作业的执行顺序。

作业的响应比是指作业的等待时间加上作业需要的服务时间与作业需要的服务时间的比值，即响应比=（等待时间+服务时间）/服务时间。响应比越高，表示该作业越需要执行，它的作业优先级就越高。

1.从就绪队列中选取一个作业进行执行。

2.计算作业的响应比。

3.执行作业。

4.如果作业未完成，则更新该作业的等待时间，并且将该作业重新插入就绪队列的适当位置，以便根据新的响应比进行重新排序。

5.重复步骤1~4，直到所有作业完成。

1.提高系统的响应性：通过计算作业的响应比，能够将响应时间长的作业优先执行，从而减少作业的等待时间，提高系统的响应性和用户体验。

2.公平地调度作业：响应比高者优先调度算法考虑了作业的等待时间和服务时间的比值，更加公平地调度作业。作业等待时间越长，其响应比就越高，使得长作业和短作业之间的调度更加平衡。

3.提高系统的效率：通过优先执行响应比高的作业，可以减少长作业对系统资源的占用时间，从而提高系统的效率。 4.适用性广泛：响应比高者优先调度算法不需要用户给出作业的执行时间，只需根据已有信息计算作业的响应比即可。这使得该算法适用于各种类型的作业和不同的系统环境。

然而，响应比高者优先调度算法也存在一些缺点：

1.对于长作业，可能存在饥饿现象：由于响应比高者优先调度算法倾向于执行响应比高的作业，对于长作业来说，等待时间可能会很长，导致长作业在执行前一直处于饥饿状态。

2.对于短作业，可能存在饥饿现象：由于短作业的响应时间通常较短，响应比也会比较低，导致短作业在就绪队列中的位置比较靠后，可能要等待较长时间才能执行。

3.对于输入输出密集型作业，可能存在优先级翻转问题：当一个低优先级的输入输出密集型作业和一个高优先级的计算密集型作业同时竞争资源时，由于计算密集型作业的响应比高，系统会优先执行计算密集型作业，导致低优先级的输入输出密集型作业等待时间过长，产生优先级翻转问题。