改进的多队列VC调度算法模型  

Improved Multi-queued Algorithm Model for VC

作　　者：吴舜贤[1] 刘衍珩[1] 余雪岗[1] 谢阿涟[1] 

机构地区：[1]吉林大学计算机科学与技术学院,长春130012

出　　处：《吉林大学学报（信息科学版）》2005年第1期86-91,共6页Journal of Jilin University（Information Science Edition）

基　　金：吉林省自然科学基金资助项目(20030522 2)

摘　　要：在分析VC(VirtualClock)和GPS/PGPS(GeneralizedProcessorSharing/Packet by packetGeneralizedPro cessorSharing)分组调度算法的优点和缺点的基础上,提出了一种结合GPS调度算法特性的改进VC调度算法模型———多队列VC调度算法MQVC(Multi QueuedVirtualClock)。阐述了MQVC的设计目标、改进措施,并给出了MQVC算法模型和算法描述,通过定理和引理证明了该模型与单队列VC和PGPS调度算法模型相比,分组排序复杂度由原来O(mnlog(mn))降为O(mlogm),使实现复杂度、系统调度性能和包丢失等方面均有明显改善。Based on the analysis of VC(Virtual Clock) and GPS/PGPS(Generalized Processor Sharing/Packet-by-packet Generalized Processor Sharing), a new scheduling algorithm is proposed,which is an improved virtual clock packet scheduling algorithm model with GPS scheduling algorithm's characteristics, and named as is MQVC(Multi-Queued Virtual Clock). The design objectives,improving methods,MQVC model and algorithm description in pseudo code are presented. It is proved theoretically that this model is much better than single-queued VC and PGPS scheduling algorithm model in such aspects as implementation complexity, system scheduling performances and packet loss.

关 键 词：队列 分组调度算法 VC 调度性能 复杂度 算法模型 包丢失 统调 GPS 优点 

分 类 号：N941.1[自然科学总论—系统科学] TP393[自动化与计算机技术—计算机应用技术]