排队算法

排队算法（共4篇）

排队算法 篇1

在网络应用迅猛发展的今天，巨大的信息传输量和实时性要求已经明显地超越了当前网络环境所能提供的性能。“好卡啊!”几乎是每个网络使用者都曾有过的体会。因此，优化网络服务质量势在必行。升级网络硬件设施固然是最有效的方法。但是成本巨大，涉及面太广，非常难以实施。为网络上的数据包进行分类、排队则是既有效，又可行的方法之一。向漏斗里倒水，倒的太快而来不及流出时，就会导致水溢出。在分组队列中，数据在Buffer里溢出时就会采取“队尾丢弃”。为了防止数据溢出或被丢弃，排队机制应运而生。排队是指在链路的输出Buffe r中对分组按照一定的规则排序的一种逻辑处理。当端口发生拥塞，分组进入的速度大于离开的速度时，就进行排队处理。目前比较常用的排队算法有：FIFO(先进先出)、PQ(按优先级)、CQ(自定义)、WFQ(加权公平排队)、CBWFQ(基于类的加权公平排队)以及LLQ(低延时排队)。

1 各种排队算法的介绍

FIFO (Firs t In Firs t OUT)：先进先出排队算法。顾名思义，先进入队列的业务就先分配资源，直到其结束，出队列，再把资源分配给下一个，就像食堂排队打饭一样。如果有耗时很长的业务进入，则排在其后面的短耗时业务就会长期无法得到处理。很明显，这种排队方法属于傻瓜式的，在大多数情况下都无法满足网络任务的需求。

PQ (PriorityQue uing)：优先级排队算法。严格按优先级进行调度，实时业务作为高优先级可以在处理时通过绝对优先调度而仅需极低的时延。PQ有着四种队列：高，中，正常(默认)，低。从高级队列开始清空，然后是中级，再到正常和低。每一级内部依然采用FIFO的方式。这种方法可能造成较低优先级的任务始终得不到处理而被“饿死”。

CQ (Cus tom Que uing)：自定义排队算法。根据设置将所有分组分成最多至17类，按照FIFO的方式分别进入1个系统队列和16个用户队列。在出队调度上，系统队列具有绝对的优先权，系统总是先处理完该队列后再用处理用户队列。16个用户队列占用出口带宽的比例可以人为地进行设置。当拥塞发生时，这种排队算法能保证不同业务根据比例获得相应的带宽占用，从而既保证关键业务能获得较多的带宽，又不至于使非关键业务被“饿死”。没有拥塞时，各业务可以根据流量中业务的相对比例充分使用接口带宽，提高资源利用率。

WFQ (We ighte d FairQue uing)：加权公平排队算法。这是一个基于流的算法，每一个流对应一个队列，每一个流根据其优先级来计算一个加权值。相同源IP地址、目的IP地址、源端口号、目的端口号、协议号相同的分组属于同一个流。在出队发送的时候，WFQ根据分类时的优先级来分配每个流应占有的出口带宽。优先级的数值越大，所得的带宽越多。在拥塞发生时，它能保证任何流量的流(业务)，都能公平地得到一定的带宽占用，减少这个网络的时延，并当流的数目减少时，能自动增加现存流可占的带宽。但是WFQ并不能对个别流提供最小带宽保障。

CBWFQ (Clas s-Bas e d WFQ)：基于类的加权公平排队算法。这是用来解决WFQ中无法对某一个特定流提供持续的最小带宽保障的一种算法。在进行WFQ算法前，先将各个任务按照一定规则分类，无法明确分类的都归为默认类别。然后在每个类中再按照WFQ来处理任务，每一个类都可以人为指定其拥有多少带宽，可定制性高。而当某个类为空时，其余类可以公平分享其带宽，提高了利用率。

LLQ (Low Late ncyQue uing)：低延迟排队算法。这是一种集合了PQ、CQ、WFQ算法优点的，能相对最有效地应对对延迟要求颇高的实时性业务的算法。当有分组要调度时，先根据其进入网络设备的接口、分组的协议、分组是否匹配访问控制列表等因素，对分组进行分类。总体上分为两大类：一是具有绝对优先级的，二是剩余的。

当拥有绝对优先级的队列里有分组、有任务时，调度器对此队列进行优先发送，直至其为空。如果该队列本来为空，在调度不具备绝对优先级的分组时有分组进入优先队列，则在当前调度的分组出队时立刻转去调度优先队列里的分组。每个队列本身可以人为的为其分配带宽。

进入优先队列的分组在接口没有发生拥塞的时候(此时所有队列中都没有分组)，所有属于优先队列的分组都可以被发送。在接口发生拥塞的时候(队列中有分组时)，进入优先队列的分组被限速，超出规定流量的分组将被丢弃。这样，在接口不发生拥塞的情况下，可以让属于优先队列的分组获得空闲的带宽。而在接口拥塞的情况下，又可以保证属于优先队列的分组不会占用超出规定的带宽，保护了其他分组的应得带宽。另外，由于只要优先队列中有分组，调度器就会发送优先队列中的分组，所以优先队列中的分组被发送的延迟最多是接口发送一个最大长度分组的时间，无论是延迟还是延迟抖动，优先队列都可以将之降低为最低限度。这为对延迟敏感的应用如VoIP业务提供了良好的服务质量保证。

2 各种排队算法的对比

3对各种排队算法的总结

如果不需要对数据流区分处理又需要算法复杂度低、处理速度快，可以选择FIFO算法。如果要求带宽公平分配并对部分应用提供一定的减少时延处理时，可以用WFQ算法。如果任务要区分对待，再在此基础上进一步细化带宽分配，CBWFQ算法是不错的选择。如果不仅要满足以上提及的种种要求，还要在实时业务上实现比较理想的低时延处理效果，则可以选择LLQ算法。不过其处理复杂度高，对设备要求高。

4 结语

如今的网络，需要我们积极探索开发新的、具有实质性飞跃的排队算法。新算法可以从严格的、多层的分类或组合，以及算法复杂度低等方面入手，尽可能让数据分组里的附加信息减少，从而降低网络总体负荷。在慢慢普及光纤通信的今天，相信通过这一系列的改进能够使网络上的各种应用，尤其是实时业务的应用得到长足的发展。

摘要：通过多年的发展, 网络已经成为很多人生活中必不可少的一部分。网络服务质量的提高是优化实时业务效果的重要一环, 而排队算法正是实现服务质量提高的方法之一。

关键词：排队算法,优先级,分类,对比

参考文献

[1]宁科.IP网络的Cisco QoS管理[M].北京:机械工业出版社, 2002.

[2]李秋, 王秀欣.基于优先级输入排队的调度算法的研究[J].中国科技信息, 2008.

[3]QoS拥塞管理的几种技术比较[EB/OL].http://shig007.blog.51cto.com/270113/53648.

基于排队论的进程调度算法分析 篇2

排队理论是研究排队现象的理论和应用的学科, 专门研究由于随机因素的影响而产生拥挤现象的科学, 也称为随机服务系统。排队分析是计算机和网络人员的重要工具之一。早在九几年就出现了运用排队理论来分析进程调度算法, 但基本上偏向于排队论模型的理论分析, 而本文通过模拟排队论m/m/1模型来分析FCFS进程调度算法, 主要集中分析调度算法的响应时间, 系统吞吐量, 等待时间等, 深入评价进程调度算法, 对于以后算法的改进提供强有力的依据。

1建模和分析

1.1m/m/1排队模型

任何一个排队过程都包括以下三个过程:到达过程;排队过程;服务过程。 如果一个排队系统仅有一个服务系统, 到达顾客数服从泊松分布, 服务时间服从负指数分布和FIFO排队过程, 则该排队系统被称为m/m/1系统。

假设m/m/1排队模型中顾客到达队列的速率为λ, 顾客平均服务时间1/μ[2]且λ<μ, 则顾客在系统中的平均响应时间如式 (1) [2]所示。

undefined (1)

1.2建模

FCFS调度算法是最简单的进程调度算法。算法描述: 当一个进程处于就绪状态, 就进入就绪队列, 当前进程停止运行时, 就从就绪队列中选等待时间最长的进程运行。

将FCFS调度算法的处理过程模拟为如图1所示服务模型, 该模型由一个队列和单CPU组成。假设进程到达就绪队列的过程是速率为λ的泊松流, CPU的服务时间服从负指数分布, 服务速率为μ。操作系统中处于就绪状态的进程数目是有限的并且相对比较小, CPU的服务速率μ较大。因此FCFS服务模型可以认为是一个m/m/1随机服务模型。

1.3FCFS的性能指标分析

1.3.1 FCFS算法平均响应时间分析

对于交互式系统或者实时系统, 响应时间是用户所关心的。特别是, 当系统中有大量进程共存时, 仍要能保证每个用户都有可以接受的响应速度而并不感到明显的延迟。根据测定, 当这种延迟超过150ms时, 使用者就会明显地感觉到[3]。响应时间是评价算法的一个重要标准, 所以响应时间越小越好。

根据公式 (1) 如果μ越大, λ越小, 则T越小。这与直觉一样, 如果λ不变, 进程平均服务时间1/μ越短, 则就绪队列中进程的等待时间就越短, 平均响应时间就越短。如果μ=λ, 则T将趋于无穷大, 此时系统性能是最差的。

2实验及结果分析

实验环境: CPU P4 2.80GHz, 内存512M, 操作系统 Linux, 编程语言 C, 编译工具 GCC。本实验模拟m/m/1模型, 实验中输入参数分别为:进程进入就绪队列的概率ρι, 进程离开就绪队列的概率ρο, 离散化时间增量S;输出参数分别为:进程的平均等待时间Wt, 进程平均服务时间St。实验数据如表1所示, 实验结果如图2～图7所示。所有图中横坐标表示进程数目, 纵坐标表示进程平均等待时间或平均服务时间。

根据表1中第1, 2, 3组数据可看出进程集的平均等待时间Wt接近于平均服务时间St的两倍, 则说明进程集中部分进程的等待时间远高于服务时间, 即进程花费大部分的时间等待CPU调度, 这是系统不可容忍的。根据表2中第2, 3组数据可看出长进程集的平均等待时间明显高于短进程集的平均等待时间, 因此可以得出FCFS调度算法更适用于短进程集中。

因为FCFS调度与进程所需的服务时间无关, 所以进程集中进程的等待时间都是一致的[4], 周转时间=等待时间/服务时间+1, 服务时间越长周转时间越短, 所以FCFS更有利于长进程。

与定性分析方法相比, 进程到达队列的过程是随机的, 实验模拟过程较接近于真实环境。但也存在一些缺点:要进行一些简化假设, 实验模拟结果受输入的限制。

3结束语

采用数学模型分析FCFS进程调度算法, 对于其他的进程调度算法也可以利用类似的方法进行分析。本文通过对FCFS进程调度算法的定量分析得出了与定性分析相同的结果。定量分析过程尽管比定性分析过程复杂, 但它可以对进程调度算法细节做深入分析, 得出的结论也更具有说服力。

摘要：采用排队论方法分析进程调度算法性能使进程调度算法性能评价更具说服力。本文先建立了FCFS进程调度算法的数学模型, 再对模型先进行理论分析和实验模拟。根据理论分析和实验模拟对FCFS进程调度算法进行性能评价。

关键词：FCFS进程调度算法,排队论,性能评价

参考文献

[1]任泰明.如何用数学模型定量评价进程调度算法的性能.兰州石化职业技术学院学报, 2001, 1 (1) :7~9

[2] Dimitri Bertsekas, Robert Gallager.Data Networks.2 nd Edition.Prentice Hall.1991.150~269

[3]毛德操, 胡希明.Linux内核源代码情景分析 (第一版) .浙江:浙江大学出版社, 2001.356

排队算法 篇3

在日常生活中,人员排班问题是一个很常见而又现实的问题。所谓排班问题,实际上是如何根据既定工作计划,制定符合既定的排班规则的工时分配表的问题。一个良好的排班方案对企业生产运行具有积极的意义,例如可以激发员工的工作积极性、减少员工无效工作时间、降低企业人力资源成本等。但在实际生产过程中,进行排班时需要考虑问题往往较多,如必须要遵守国家的相关劳动法规及行业闺房、所从事工作的劳动强度以及员工的自身状态等问题, 随着排班规模的不断增大,技能分类的不断细化,排班问题也是变得日趋复杂,以往通过经验进行排班的方法难以满足目前行业发展的需求,因此,有必要对排班问题进行研究,对现有的排班制度进行优化改进。

机场的主要服务对象主要有三方面,分别是旅客、飞机以及货邮。而机场一线员工主要位于值机、安检、特种司机、行李搬运等方面,都是与服务对象有重要交流的环节,他们工作服务质量的高低,直接决定着机场的服务质量,乃至整个机场的形象,对他们进行合理的排班调度,不但可以为机场降低人力资源成本,还可以起到提升员工服务水平的作用[1]。

1 排班问题描述

当在机场乘机时,在一天中的某些时段,值机以及安检柜台前的排队人数相对会比较多,员工的劳动强度比较大,旅客可能需要等待比较长的时间来接受相关服务,而也有一些时段,同样存在着大量的值机以及安检柜台在已经开放的情况下处于闲置状态,员工的劳动强度比较小,造成资源的浪费。而产生这些问题的本质,就是航班计划的波动性和周期性。

因此在进行排班时,就需要考虑排班日的航班时刻计划,此外还应考虑到相关人员工作的各种限制条件因素如:法定工作小时数,班次之间所要求的休息时间间隔,人员拟定的假期,病休,以及学习和训练时间等。机场一线员工都是在机场为日常航班提供地面服务的,在某一天的各个时间段内,所需的地服员工数量与进场和离场的航班架次相关,即如果具体时间段的航班情况一旦确定,就可以知道所需地服员工的数量和种类。为此机场公司考虑尽量将人员成本减到最少,也可以尽最大量提高人员使用效率,将富余人员减到最少。通常来说,一架航班大概需要接受10种地面服务,总共花费的时间大概为30分钟[2]。根据这些思想,机场一线员工排班流程如图1所示。

2 员工需求预测

员工需求数量的预测主要运用经典排队论的方法来进行研究,为了简化模型,本文仅以机场值机员工做分析,包括下文的计划排班模型,同样以机场值机员为例做分析研究。机场值机柜台可以分为专用式和公用式,而对于机场提供的值机服务通常都是公用式,因此本文对于员工需求数量的预测以公用式柜台为背景。

由于各个时段的航班数都在发生着变化,因此各个时段的旅客到达率都在发生着变化。根据在我国某机场的调研数据,各个时段旅客到达量和航班量数据如下所示。

图2中的柱状图表示该时段内预计离场的航班架次,线状图表示该时段内进入值机队列的旅客数,每一时段的时间长为半小时。

而当旅客开始进入值机队列,到旅客接受完值机服务,离开值机柜台,实质上可以用排队论中的排队模型M/M/C表示。根据排队论的通常表示方法,做出如下参数假设:

c:表示机场开放的值机柜台数。

λ:表示旅客的到达率。

μ:表示值机员的服务率。

ρ:服务强度。

Lq:排队队长。

则旅客在接受值机服务前的平均等待时间为[3]:

undefined

根据机场自身的服务水平和服务能力,可以自由设置Wq的大小,旅客排队时间一般不能超过20分钟,理想排队时间应在12分钟以内。以w′表示旅客等待时间上限,则有Wq

①设排队过程可以达到稳态,则有undefined。

②将c的值代入上式,计算Wq ,如果Wq w′则继续下一步。

③c=c+1,转入第②步,继续运算。

通过以上步骤,依据航班时刻表,便可以预测出各个时段所需员工数量。

3 计划排班

当获得了各个时段所需员工数量、员工资料和员工排班规则等信息后,便可以进入计划排班阶段。

3.1 数学模型

①参数

P:一个排班周期的时间跨度,以星期为单位。

D:一个排班周期排班日的集合,如D=1,2,3,…,7P。

Dp:一个排班周期中第p∈P个星期排班日的集合,如undefined。

k:一个排班日所划分的时间段的个数。

M:一个排班周期所划分的时间段的个数。

Rt:时间段t内,最少所需员工的数量,其中t=1,2,3,…,M。

N:员工的总数。

D:松弛参数,员工计划排班与员工实际需求之间的最大偏移量。

②变量

Wi ⊂D:员工i在一个排班周期中工作日的集合。

undefined:员工i在一个排班周期中休息日的集合。

Siw :员工i在排班周期中某个工作日w的上班开始时间。

fiw:员工i在排班周期中某个工作日w的上班结束时间。

xit∈[0,1]:在时间段t,员工i是否上班,其中t=1,2,3,…,M。

at:在时间段t,实际在岗员工数量,其中t=1,2,3,…,M。

undefined:员工在一个排班周期的平均工作时间。

③目标函数

minundefined

④约束条件

undefined

undefined

undefined

目标函数式(2)表示排班结果要尽量均衡每名员工的负荷;约束式(3)和约束式(4)表示了在时间段t中,实际安排的员工数量;约束式(5)表示每名员工每个星期休息两天;约束式(6)表示员工在两个休息日间连续工作不超过4天;约束式(7)表示每个班次工作时长在5.5小时到9.5小时之间;约束式(8)表示每名员工每周至少工作42小时;约束式(9)表示每名员工的连续两个班次之间至少间隔12小时;约束式(10)和约束式(11)表示所有班次都不得跨日期,即班次的开始时间和结束时间都在同一天;约束式(12)表示每个时段在岗员工人数需满足一定范围。

3.2 求解算法

对于上文所提出的模型,很难用解析法来求解,因此考虑运用启发式算法来求解。目前对于排班问题的主要的算法有遗传算法和模拟退火算法,在实际的使用中遗传算法容易发生成熟前的收敛,在选择时也很难满足对目标优化的要求,因此本文采用模拟退火算法来解决上文所提出的排班模型。模拟退火算法(simulated annealing)[4]是在1983年由Kirkpatrick等人首先提出的一种随机优化算法,它是通过对固体物质退火过程的研究而得来的。因此它也被称为蒙特卡洛退火法、冷却统计法以及模拟冷却法等。

由排班模型可知,该问题实质上就是要确定N名员工在一个排班周期的上班班次组合,每一个班次组合方案对应一个函数适应值。在运用模拟退火算法求解的过程中,核心是根据适应值进行对比计算,用以判断是否接受新的排班方案为当前最佳方案而进行一步步的迭代。因此,运用模拟退火法的首要问题就是:必须首先产生一个满足所有排班约束的可行解,即可行的排班方案[5]。对于初始解的求法,可以采用试探性的算法为每名值机员分配分配每个排班周期的任务,将复杂的问题转换为大量易于解决的子问题,算法步骤如下:

①在值机员表中任意挑选一名值机员。

②指派该值机员到某些具体的班次并满足除约束(12)外的所有约束条件。

③把这个值机员从待排班的列表中移除。

④检查是否把所有值机员分配完了,确定后,运算结束,否则执行步骤①按照上面的步骤,就可以得到一个初始解,记作X。

由于该初始解不一定满足约束(12),因此在目标函数中将约束(12)以惩罚函数形式考虑在内,即为:

undefined

上式中的H是惩罚系数,为一个极大的正数。

因此前文所得到初始解即可以满足所有约束条件,即为可行解。

然后对该排班方案其进行一次随机的“退火”,产生一个新的排班方案X′,该新方案的前提是满足所有约束条件,若出现不符合约束的情况,则需重新调整“退火”。每次对解空间的“退火”都是随机对某位值机员进行的,本文提出了如下几种“退火”方式:

①同时调整某一班次的开始时间Siw和结束时间fiw,并同时保持该班次的时长undefined不变。

②仅调整某一班次的开始时间Siw或结束时间fiw,使的班次时长undefined发生变化。

③将某个工作班次和本周中某休息日交换。

在进行一次“退火”后的方案目标值的变化量为:

Δ C = CXundefined

如果Δ C<0或者undefined,则X′取代X,作为当前最佳排班方案,其中p是(0,1]间的一个随机数,θn是第n次“退火”的温度参数,θn则为初始状态下的温度,ρ为退火温度冷却系数,算法迭代代数为αN|D|,其中α和ρ都是控制算法运行速度和收敛状态的一个参数,热平衡状态为在某一温度状态下连续计算5次结果相同,模拟退火算法步骤如下所示:

①产生初始可行解X,设θ0为初始温度。

②对随机产生的初始可行解进行“退火”,随机采用上文所提到的三种微扰方案之一进行演化。

③计算目标函数的变化值,得出undefined如果ΔC≤0则转入步骤⑤,否则转入步骤④。

④产生一个固定的随机数,计算新方案的接受概率p,如果undefined则保持原有的解决方案,转入步骤②。

⑤接受新产生的排班方案。

⑥如果现有的温度下达到了热平衡,则θi+1=ρ·θi,如果运算达到预设退火代数undefined,停止运算,当前结果可视为最优,否则以退火温度θi+1,转入步骤②。如果未能达到平衡,则温度不变,转入步骤②。

3.3 算例分析

为了验证模型与算法的可行性与正确性,使用了某机场公司的数据,对机场值机员进行月排班。

模型具体参数如下:共有N=357名值机员,航班时刻表为2011年4月1日至2011年4月28日,P=4,每天的值机服务时间从上午5:00到晚上12∶00,共19个小时,以半小时为一个时间段,k=38,则总排班期为M=1064,松弛参数,惩罚系数H=10000。

模拟退火算法的参数如下:迭代总数为5000次,初始温度为90,温度冷却系数为0.97。

仿真计算结果中,某一天的排班结果如图3所示。

4 实时排班

航班往往受突发状况的影响比较大,因此提前制定好计划排班表之后,在机场实际运行过程中,决策者往往需要对排班情况进行动态调整,也就是实时排班过程。

实时排班的过程很难使用数学模型来进行描述,其排班结果的好坏通常依赖与决策者的从业经验[6]。

5 结束语

研究了机场一线员工排班的特点,提出了根据航班时刻进行弹性排班的思想,并给出了排班的整个流程。在整个流程中,有三个主要环节,分别为员工需求预测、计划排班和实时排班。员工需求预测主要是根据航班时刻以及旅客流量来确定各个时段所需员工的最少数量,本章采用了经典排队论来解决该问题;计划排班就是根据所需员工最少数量,员工数据信息以及排班的规则,进行计划排班,运用模拟退火算法进行了求解,该排班过程通常提前于实际上班时间;而航班计划以及实际运行过程中突发情况较多,因此在实际运行过程中,还需进行实时排班调度,该过程很难用数学模型进行描述,排班效果通常依赖与排班者的从业经验,本文对此没有过多赘述。

参考文献

[1]Chu C K.Goal programming model for crew duties generation[J].Jour-nal of Multi-Criteria Decision Analysis,2001,10(3):143-151.

[2]张倩.机场地面作业调度问题研究[D].天津:南开大学,2007.

[3]F Baskett,KM Chandy,Richard R Muntz,et al.Open,closed,and mixed networks of queues with different classes of customers[J].Journal of the Association for Computing Machinery,1975,22(2):248-260.

[4]Kirkpatrick S,Gelatt C D,Vecchi M P.Optimization by SimulatedAnnealing[J].Science,1983,220:671-680.

[5]李青,张军,张学军.解决排班问题的多目标优化模型及算法研究[J].北京航空航天大学学报,2003,9:821-824.

排队算法 篇4

在目前的工业自动化控制应用中,越来越多的企业实现了生产过程的联网监控,信息化与工业化深度融合水平不断提高。网络上,设备之间数据通信基本上都是采用异步串行通信接口RS-232、RS-422、RS-485等,且通过相关通信协议将多个设备连接成底层传输与控制网络,但是网络的覆盖面积很小[1]。为使这些设备具备远程传输、扩大底层网络的覆盖面积,需要应用串口服务器(Serial Device Server,简称SDS)。串口服务器可以实现串行数据与以太网数据的相互转换,从而将串行设备控制网络与信息网络连接起来。SDS可以把分散的串行设备、主机等通过网络集中管理,可以很大程度地降低系统复杂性和提高系统的可扩展性[2]。目前市场上现有的各种SDS都是单串口对单网口的构造,如果要支持多总线,则必须使用多个单总线型SDS或者使用带有多串口、多网口的多总线型SDS。这样带来的问题是:成本增加、系统设计复杂、设备资源利用率不高,故此本文提出一种基于优先级排队算法的改进型串口服务器(Modified Serial Device Server,简称MSDS)。

1 串口服务器的改进方案

串口服务器将分散的串口设备通过局域网或互联网集中管理,增强了系统的可扩展性和降低了系统的维护难度,只需每条总线连接到对应的串口服务器,控制系统只需围绕SPS进行开发,可以有效减少工作量。

本文设计的改进型串口服务器采用嵌入式单片机S3C6410和以太网卡DM9000搭建硬件平台,充分利用单片机的多个UART、嵌入式操作系统的多线程和多队列缓冲将接收到的多个串口数据排队,使用优先级排队算法进行数据处理。下面以实现RS232数据与以太网数据之间的转换为例,三串口到单网口的M S D S的工作原理如图1所示:RS232_1~RS232_3对应MSDS的三个串口,UART_1~UART_3对应嵌入式单片机的三个异步收发器,Transverter Threa_1~Transverter Threa_3对应MSDS的三个是串口数据与以太网数据的转换线程,FIFO_Receive是串口端到以太网端的接收队列,FIFO_Send是以太网端到串口端的发送队列。Ethenet表示以太网单网口。如果嵌入单片机的UART支持RS485通讯方式,用该方案同样可以实现RS485总线数据与以太网数据的转换,区别在于串口端接口和设备驱动不同。

M S D S软件结构如图2所示,运行协议转换用户程序后产生线程Transverter Thread1~Transverter Thread3,这三个线程根据数据流向通过系统调用接口分别调用对应的设备驱动,如以太网转串口驱动和串口转以太网驱动,这两个驱动编写后可以直接编译到内核或通过命令安装的方式添加到内核。Transverter Thread线程的产生的数量与MSDS设计的规模有关,由于本文改进方案使用三条串行总线,所以产生3条Transverter Thread线程。

2 基于优先级排队算法的数据处理

由于MSDS是多串口对单网口的结构,存在共享资源,需通过合理的调度,才能使MSDS正常地接收和发送数据[3]。考虑使用串口服务器组网的底层设备大多用在工业生产、安防等的重要场合,而一些对于生产安全和主要指标的参数,必须优先送达控制中心[5],从这个角度本文选择基于优先级排队算法处理底层设备到以太网之间数据的流通。

优先级排队算法(简称PQ算法)是按照优先规则为队列服务的,规定从具有最高优先级的非空队列的头部选择包[6]。为了保证关键业务运行,在拥塞发生时,优先处理关键业务。预先根据网络协议、数据流入口、源地址/目的地址等制定好控制策略,PQ算法处理数据队列的优先顺序就可以确定[7]。将队列按优先级高低分为四级,而在优先级缺省的情况下数据流入正常队列。

PQ算法的原理如图3所示,其中:1高优先级数据,在调度分类时进入了高优先级队列,依此类推,2、3、4号分组在调度时分别进入为中优先级队列、正常优先级队列以及低优先级队列。遵循先进先出(FIFO)原则,由高到低依次处理四个优先级队列的数据[8]。

3 方案的实施

为验证串口服务器改进方案的可行性,使用现成的嵌入式开发板进行二次开发的方式实现MSDS,而无须从头到尾设计硬件电路。采用的嵌入式开发板是国嵌QK6410,其处理器是三星公司32位RISC处理器S3C6410,有4个UART和1个网口,所以该开发板可二次开发为3串口对单网口的MSDS,如图4所示,只需使用QK6410核心板、DM9000以太网卡和三个串口就足以满足MSDS的硬件需要。

国嵌QK6410开发板支持ARM-Linux2.6操作系统,Linux2.6内核支持多线程和具有丰富的网络协议栈。使用国嵌提供的Linux2.6内核可直接烧写到QK6410的Flash中,而且该内核提供了串口驱动和DM9000以太网卡驱动。MSDS软件的开发流程为:

(1)配置和编译ARM_linux 2.6内核,配置和编译过程中,取消不需要的驱动;

(2)构建应用于ARM-linux的根文件系统;

(3)将启动引导程序Uboot移植到的MSDS板子上;

(4)在linux主机上开启tftp和nfs服务,利用tftp服务可将ARM-linux内核映下载到MSDS板的内存中,ARM-linux的根文件系统通过NFS服务挂载到linux主机,使开发过程得到了简化;

(5)编写以太网转RS232和RS232转以太网的设备驱动程序,以加载的方式,把它们放到ARM-linux内核中;

(6)编写协议转换应用程序,通过系统调用接口调用驱动程序。

从以上的开发流程可以看出:编写以太网转RS232和RS232转以太网驱动程序和协议转换应用程序是实现MSDS软件功能的主要步骤。因为国嵌提供的Linux2.6内核已经实现了串口驱动和DM9000以太网卡驱动,所以实现以太网转RS232和RS232转以太网驱动程序相对简单,定义设备操作时只需结合串口驱动和DM9000以太网卡驱动,如图5所示。自定义Dev结构体可作为串口数据与以太网数据转换时过渡数据,其结构如表1所示。

对于用户,直接接触到的是协议转换用户程序,在该程序中,首先初始化M S D S的运行参数,然后建立线程Transverter Thread1~Transverter Thread3,在Transverter Thread线程中主要通过调用接口转换驱动实现了串口和网口数据首发的功能,其中收发的数据根据数据传输方向分别放入Dev结构体队列FIFO_Receive和FIFO_Send中。Transverter Thread线程的工作原理如图6所示。

4 组网对比实验与分析

S3C6410有4个UART,利用其中三个配置成MSDS的三个RS232通信接口,设计成三串口对单网口的MSDS。使用三块51单片机开发板(设备A、B、C),作为下位机设备,实验组网如图7所示。通过组网对比发现,单MSDS模式的网络连接明显比多SDS模式要简洁,系统的可维护加强。单MSDS模式,开发工作只需围绕一个MSDS展开,极大地减小了设计的工作量;而多SDS模式,要同时设计多个SDS的收发过程。

每块设备以9600的波特率分别经3个SDS和1个MSDS向上位机传送1MB的数据。以轮寻的方式每次发送一个字节,每个设备都轮寻1024次,所以上位机能接收到1024*3个字节。MSDS的组网性能可通过数据传输的流量曲线进行分析,两种模式下数据传输流量的对比如图8所示。

两种模式下传输1024*3个字节的数据,所用的时间相近,而且两条曲线有非常高的拟合度,说明基于优先级排队算法在数据传输过程中发挥了作用。单MSDS模式在传输的过程中,流量总会稍微落后于多SDS模式,这是要是受限于硬件和线程处理速度,但能在节约成本的前提下能满足传输需求。

5 结束语

通过组网对比实验发现改进型串口服务器处理传输数据的速率非常接近传统的串口服务器的处理传输速率,单个的改进型串口服务器的具有多个传统的串口服务器的组网能力。在实验结果中还可以看出优先级排队算法在数据处理传送环节发挥了作用,在软件上弥补了硬件的不足。单MSDS模式设计的工作量显著减小。以嵌入式单片机S3C6410和以太网卡DM9000搭建硬件平台,充分利用单片机的多个UART、嵌入式操作系统的多线程和多队列缓冲将接收到的多个串口数据排队,利用优先级排队算法进行数据处理的串口服务器改进方案,可以有效的降低成本、简化系统设计、提高设备资源利用率。

摘要：针对目前市场上的串口服务器都是单串口对单网口的结构,提出了一种多串口对单网口的接口服务器改进方案。以嵌入式单片机S3C6410和以太网卡DM9000搭建硬件平台,充分利用单片机的多个UART、嵌入式操作系统的多线程和多队列缓冲将接收到的多个串口数据排队,最后利用优先级排队算法进行数据处理。通过使用改进型串口服务器进行组网实验,表明利用优先级排队算法的方案具有可行性,单个的改进型串口服务器具备多个传统串口服务器的组网能力。

关键词：改进型串口服务器,UART,嵌入式系统,优先级排队算法

参考文献

[1]周超.基于Cortex-M3的以太网串口服务器的设计与实现[D].武汉理工大学,2012.

[2]范永刚,刘绍方,董晶,等.基于ARM的高性能串口服务器的研究与实现[J].计算机工程与设计,2012,33(4):1378-1384.

[3]李毅.嵌入式串口服务器的设计与实现[D].北京交通大学,2012.

[4]闾军,成爱国.一种低成本串口服务器的设计[J].电子设计工程,2014(14):190-192.

[5]王海勇.基于ARM9的嵌入式多串口服务器设计[J].化工自动化及仪表,2013,40(3):372-376.

[6]罗宁,刘峰.基于优先级队列的多约束无线链路资源调度算法[J].指挥控制与仿真,2012(6):55-59.

[7]范珊珊,李石君.基于优先级队列的分布式多主题爬虫[J].计算机工程与设计,2015(6):1630-1636.