论文部分内容阅读
随着网络的迅速发展,网络的服务质量(quality of service, QoS)保证成为当前研究的热点问题。而分组调度算法是实现QoS的重要内容。本文首先分析了现有的典型分组调度算法：基于优先级的调度算法、基于比例共享的调度算法和基于时间的调度算法。详细研究和分析了一种动态优先级调度算法：EDF (Earliest Deadline First,最早截止期优先)调度算法,由于网络环境下直接采用EDF方案会存在诸如任务超截止期等问题,本文研究探讨了一种改进的分组调度算法：EDF_BO (Earliest Deadline First Based on Overtime)算法,即基于超时处理的EDF算法。此改进算法通过仔细分析算法的每个调度步骤,采取充分利用空闲时间片和设置临时优先级的方法,较好地解决了本文所研究的实时高速局域网任务超截止期的问题。为了在系统运行前计算出调度方案,实现真正的高速调度,本文设计了一个离线设计器。依据时间片机制和实时任务调度的特点,在系统中提供了周期性任务模型、连接模型和交换机EDF_BO调度算法,以满足系统的计算需求。此设计器适用于一级或多级交换机网络的离线调度方案计算。论文中用一个三级交换机网络的例子验证了系统的可行性和实用性。考虑到运行时总存在时基误差或线路延迟等各种不稳定因素,本论文就如何进行动态调整也做了深入研究,做了大量实验和复杂度分析,主要介绍了两种方案：最大延迟值优先调度方案和先延先服务方案。最大延迟值优先方案以添加硬件方式实现,先延先服务方案时间复杂度为常数O(1),可以直接用软件方法实现。这些方法与EDF_BO相结合后,都能够一定程度地满足周期性业务环境下的运行时高速调度要求。最后对EDF_BO算法和动态调整算法均在OPNET网络仿真环境下进行了仿真实验,实验结果表明改进后的算法在时延和吞吐率方面的性能明显提高。