实时系统动态优先级任务调度算法的研究
|
摘要
实时系统计算结果的准确性及输出结果的及时性使得其在工业、国防、一医疗和通信等诸多领域得到越来越广泛的应用。随着对实时系统性能要求的不断提高,传统任务调度算法的调度性能越来越难以满足应用的要求。论文围绕实时系统单处理器任务调度和多处理器任务调度两个方面展开研究,特别针对动态优先级任务调度算法中存在的若干问题,进行了深入研究。本文主要研究工作归纳如下：
针对单处理器最小空闲时间优先调度算法作业切换常出现颠簸的现状,提出一种改进的动态模糊阈值最小空闲时间优先软实时调度算法。给出“模糊阈值系数”的概念,选取当前作业的剩余空闲时间和周期为模糊输入,运用模糊理论生成模糊阈值系数,用动态模糊阂值作为当前作业的虚拟剩余空闲时间参予优先级比较以尽量避免抢占。仿真结果表明,与最小空闲时间优先调度算法相比,该算法在不降低调度成功率的同时有效地减少了作业的切换次数。
针对最早截止期优先调度算法作业切换多、超载时错失率高的现状,提出两种改进的最早截止期优先软实时动态调度算法。两种算法选取当前作业的剩余空闲时间和关键性系数为模糊输入以生成动态模糊阈值系数,分别通过缩短和延长当前作业的绝对截止期至动态模糊阈值的方法减少抢占、避免作业错失。阈值的大小由作业的多种参数共同决定,大大提高了重要作业被成功调度的几率。仿真结果表明,与最早截止期优先调度算法比较,两种算法有效地提高了重要作业的完成率,当截止期被延长时,错失率明显降低,当截止期被缩短时,作业间的切换次数大大减少。
针对优先级个数受限系统中调度算法难以确保分组准确性问题,提出一种改进的组优先级最早截止期优先调度算法。给出作业分组可调度性能测试,将满足分组可调度测试公式的作业作为一个作业组,以作业组内最早绝对截止期为作业组优先级,作业组与其他作业按照最早截止期优先调度,在作业组得到系统资源后,作业组内按照最短作业优先的原则执行作业。仿真结果表明,与最早截止期优先调度算法、尽力服务调度算法及其他组优先级调度算法相比,新算法不仅能有效降低算法所需优先级个数,还能提高调度的成功率,缩短平均响应时间,减少作业切换次数。
针对同构多处理器动态优先级局部调度中密度算法和DBF*算法的判据存在可能将可调度任务误判为不可调度的情况,提出一种新的高效需求界限函数局部调度算法。算法采用更为精准的可调度性判据,分别在最小数目处理器以及固定数目处理器两种情况下,通过多阶跟踪需求界限函数轨迹确保了对任务可调度性判断的准确性。仿真结果表明,新算法与密度算法和DBF*算法相比,可调度任务的数量大大提升。
针对异构多处理器局部调度算法复杂度高且难以实现最优分配的问题,提出一种新的整数线性规划局部调度算法。在准确表达处理器之间的差异以及任务参数后,设定总处理器利用率为目标函数,通过建立约束条件求取目标函数的最小值,将异构多处理器调度问题描述为整数线性规划问题,利用Lingo快速求解整数线性规划问题,进而求得异构多处理器任务的优化分配。仿真结果表明了新算法的有效性。
The accuracy of the computing results and the timeliness when the results come out in a real time system make it widely used in more and more areas, such as industry, defense, medical care and communications.However, with the higher demands of schedulability of real time systems, it is harder and harder for the traditional real-time scheduling algorithms to satisfy the demands of the applications.In this dissertation, we have researched on the scheduling on uniprocessor systems and multiprocessor systems, especially focused on the dynamic prioritiy scheduling algorithms.The main contributions and achievements of this dissertation are stated as follows:
The least slack time first scheduling algorithm may frequently cause switching or serious thrashing among jobs.In this dissertation, an improved dynamic fuzzy threshold least slack time first scheduling algorithm for soft real-time sytems is proposed. The notion of fuzzy threshold coefficient is given. The slack time and the period of the running job are selected as the fuzzy inputs.The fuzzy threshold coefficient is generated by fuzzy theory.We regard the dynamic fuzzy threshold as the virtual slack time of the running job to avoid preemption. The simulation results show that, the dynamic fuzzy threshold makes the switching number of the improved algorithm smaller and the ratio of success not descreased.
To avoid the frequenty switching and decrease the missed deadline percentage when the systems is overloaded in earliest deadline first scheduling algorithm, two improved earliest deadline first algorithms are presented in this dissertation. In the two algorithms, the slack time and the cruces coefficient of the running job are selected to be the fuzzy inputs in order to genenrate the fuzzy threshold coefficient. The absolute deadline of the running job is extended to save the resource in one algorithm and is shorten to increase the ratio of success in the other. The threshold is decided by several parameters of the running job, as a result, the ratio of success for important jobs is increased in both of two algorithms. The performance of the algorithms is experimentally examined and compared with the earliest deadline algorithm in detail.Results show that, the missed deadline percentage is decreased obviously while the deadline is extended and the switching number is reduced greatly while the deadline is shortened. The ratio of success for important jobs is increased efficiently by using these two algorithms.
When the number of priority levels supported by the system is limited, it is hard to ensure the accuracy of grouping method in the scheduling algorithms.To solve this problem, an improved group priority earliest deadline first scheduling algorithm is proposed. We give the schedulability test. All the jobs satisfying the schedulability test are formed into a group and the earliest absolute deadline of the jobs in the group is chosen to be the priority of the group. The group and the other jobs in the system are scheduled under earliest deadline first. When the group gets the system resource, the jobs in the group are scheduled under shortest job first. Compared with earliest deadline first algorithm, best effort algorithm and other grouping algorithms, the simulation results show that the novel algorithm not only can decrease the priority levels effectively, but only can increase the ratio of success, shorten the average response time and reduce the switching number.
In the scheduling of sporadic tasks on identical unit-capacity mulitiprocessors, the criterions used in density algorithm and the DBF* algorithm may cause the tasks which are feasible under the partitioned paradigm be flagged as "infeasible" sometimes.In this dissertation, a novel efficient demand bound function partitioned scheduling algorithm is proposed. A criterion which tracks the demand bound function exactly as needed is used on least-number processors and fixed-number processors respectively to avoid the incorrect judgment in determining whether a processor can accommodate an additional task in the novel algorithm. The experimental results demonstrate that the number of tasks schedulable in the novel algorithm is much higher than in density algorithm and DBF* algorithm.
The partitioned scheduling on heterogeneous multiprocessors is complicated and hard to be optimal.To solve the problem, a novel integer linear programming partitioned scheduling algorithm is proposed. After describing the parameters of the tasks and the processors correctly,we regard the total utilization as the objective function and get the minimal value of the objective function by the constraints.The scheduling problem is changed to an integer linear programming problem.We use Lingo to get the solutions and assign the tasks according to it. The simulation results show the validity of the novel algorithm.
针对单处理器最小空闲时间优先调度算法作业切换常出现颠簸的现状,提出一种改进的动态模糊阈值最小空闲时间优先软实时调度算法。给出“模糊阈值系数”的概念,选取当前作业的剩余空闲时间和周期为模糊输入,运用模糊理论生成模糊阈值系数,用动态模糊阂值作为当前作业的虚拟剩余空闲时间参予优先级比较以尽量避免抢占。仿真结果表明,与最小空闲时间优先调度算法相比,该算法在不降低调度成功率的同时有效地减少了作业的切换次数。
针对最早截止期优先调度算法作业切换多、超载时错失率高的现状,提出两种改进的最早截止期优先软实时动态调度算法。两种算法选取当前作业的剩余空闲时间和关键性系数为模糊输入以生成动态模糊阈值系数,分别通过缩短和延长当前作业的绝对截止期至动态模糊阈值的方法减少抢占、避免作业错失。阈值的大小由作业的多种参数共同决定,大大提高了重要作业被成功调度的几率。仿真结果表明,与最早截止期优先调度算法比较,两种算法有效地提高了重要作业的完成率,当截止期被延长时,错失率明显降低,当截止期被缩短时,作业间的切换次数大大减少。
针对优先级个数受限系统中调度算法难以确保分组准确性问题,提出一种改进的组优先级最早截止期优先调度算法。给出作业分组可调度性能测试,将满足分组可调度测试公式的作业作为一个作业组,以作业组内最早绝对截止期为作业组优先级,作业组与其他作业按照最早截止期优先调度,在作业组得到系统资源后,作业组内按照最短作业优先的原则执行作业。仿真结果表明,与最早截止期优先调度算法、尽力服务调度算法及其他组优先级调度算法相比,新算法不仅能有效降低算法所需优先级个数,还能提高调度的成功率,缩短平均响应时间,减少作业切换次数。
针对同构多处理器动态优先级局部调度中密度算法和DBF*算法的判据存在可能将可调度任务误判为不可调度的情况,提出一种新的高效需求界限函数局部调度算法。算法采用更为精准的可调度性判据,分别在最小数目处理器以及固定数目处理器两种情况下,通过多阶跟踪需求界限函数轨迹确保了对任务可调度性判断的准确性。仿真结果表明,新算法与密度算法和DBF*算法相比,可调度任务的数量大大提升。
针对异构多处理器局部调度算法复杂度高且难以实现最优分配的问题,提出一种新的整数线性规划局部调度算法。在准确表达处理器之间的差异以及任务参数后,设定总处理器利用率为目标函数,通过建立约束条件求取目标函数的最小值,将异构多处理器调度问题描述为整数线性规划问题,利用Lingo快速求解整数线性规划问题,进而求得异构多处理器任务的优化分配。仿真结果表明了新算法的有效性。
The accuracy of the computing results and the timeliness when the results come out in a real time system make it widely used in more and more areas, such as industry, defense, medical care and communications.However, with the higher demands of schedulability of real time systems, it is harder and harder for the traditional real-time scheduling algorithms to satisfy the demands of the applications.In this dissertation, we have researched on the scheduling on uniprocessor systems and multiprocessor systems, especially focused on the dynamic prioritiy scheduling algorithms.The main contributions and achievements of this dissertation are stated as follows:
The least slack time first scheduling algorithm may frequently cause switching or serious thrashing among jobs.In this dissertation, an improved dynamic fuzzy threshold least slack time first scheduling algorithm for soft real-time sytems is proposed. The notion of fuzzy threshold coefficient is given. The slack time and the period of the running job are selected as the fuzzy inputs.The fuzzy threshold coefficient is generated by fuzzy theory.We regard the dynamic fuzzy threshold as the virtual slack time of the running job to avoid preemption. The simulation results show that, the dynamic fuzzy threshold makes the switching number of the improved algorithm smaller and the ratio of success not descreased.
To avoid the frequenty switching and decrease the missed deadline percentage when the systems is overloaded in earliest deadline first scheduling algorithm, two improved earliest deadline first algorithms are presented in this dissertation. In the two algorithms, the slack time and the cruces coefficient of the running job are selected to be the fuzzy inputs in order to genenrate the fuzzy threshold coefficient. The absolute deadline of the running job is extended to save the resource in one algorithm and is shorten to increase the ratio of success in the other. The threshold is decided by several parameters of the running job, as a result, the ratio of success for important jobs is increased in both of two algorithms. The performance of the algorithms is experimentally examined and compared with the earliest deadline algorithm in detail.Results show that, the missed deadline percentage is decreased obviously while the deadline is extended and the switching number is reduced greatly while the deadline is shortened. The ratio of success for important jobs is increased efficiently by using these two algorithms.
When the number of priority levels supported by the system is limited, it is hard to ensure the accuracy of grouping method in the scheduling algorithms.To solve this problem, an improved group priority earliest deadline first scheduling algorithm is proposed. We give the schedulability test. All the jobs satisfying the schedulability test are formed into a group and the earliest absolute deadline of the jobs in the group is chosen to be the priority of the group. The group and the other jobs in the system are scheduled under earliest deadline first. When the group gets the system resource, the jobs in the group are scheduled under shortest job first. Compared with earliest deadline first algorithm, best effort algorithm and other grouping algorithms, the simulation results show that the novel algorithm not only can decrease the priority levels effectively, but only can increase the ratio of success, shorten the average response time and reduce the switching number.
In the scheduling of sporadic tasks on identical unit-capacity mulitiprocessors, the criterions used in density algorithm and the DBF* algorithm may cause the tasks which are feasible under the partitioned paradigm be flagged as "infeasible" sometimes.In this dissertation, a novel efficient demand bound function partitioned scheduling algorithm is proposed. A criterion which tracks the demand bound function exactly as needed is used on least-number processors and fixed-number processors respectively to avoid the incorrect judgment in determining whether a processor can accommodate an additional task in the novel algorithm. The experimental results demonstrate that the number of tasks schedulable in the novel algorithm is much higher than in density algorithm and DBF* algorithm.
The partitioned scheduling on heterogeneous multiprocessors is complicated and hard to be optimal.To solve the problem, a novel integer linear programming partitioned scheduling algorithm is proposed. After describing the parameters of the tasks and the processors correctly,we regard the total utilization as the objective function and get the minimal value of the objective function by the constraints.The scheduling problem is changed to an integer linear programming problem.We use Lingo to get the solutions and assign the tasks according to it. The simulation results show the validity of the novel algorithm.
引文
[1]Sha L. Real-time in the real world[M].New York, USA:ACM Workshop on Strategic Directions in Computing Research,1996.
[2]Daponte P, Grimaldi D, Marinov M. Real-time measurement and control of an industrial system over a standard network:Implementation of a prototype for educational purposes[J].Ieee Transactions on Instrumentation and Measurement,2002,51(5):962-969.
[3]Morelli E, Smith M. Real-time dynamic modeling:data information requirements and flight-test results[J].Journal of Aircraft,2009,46(6):1894-1905.
[4]Marjanovic O, Lennox B,Sandoz D, et al. Real-time monitoring of an industrial batch process[J]. Computers & Chemical Engineering,2006,30(10-12):1476-1481.
[5]Keller M, Kolb A.Real-time simulation of time-of-flight sensors[J].Simulation Modelling Practice and Theory,2009,17(5):967-978.
[6]Steenburgh W J. Using real-time mesoscale modeling in undergraduate education[J].Bulletin of the American Meteorological Society,2002,83(10):1447-1451.
[7]Neves P, Fontes F, Sargento S,et al.Broadband wireless real-time communications[J].Ieee Vehicular Technology Magazine,2008,3(4):39-47.
[8]胡天亮,张承瑞,刘日良,等.功能分离的嵌入式实时系统设计方法及应用[J].计算机集成制造系统,2008,14(3)：431-437.
[9]Stankovic J. Misconceptions about real-time computing:a serious problem for next-generation systems[J].IEEE Computer,1988,10:10-19.
[10]Krishna C, Shin K. Real-time systems[M].New York:The McGraw-Hill Companies, Inc,1997.
[11]The authorized guide to version 3 of the single UNIX specification[M]:The Open Group,2002.
[12]Liu C, Layland J. Scheduling algorithms for multiprogramming in real-time systems.[J].Journal of ACM,1973,20(1):46-61.
[13]张杰.最早截止期优先实时调度算法的研究[D].(博士论文).武汉：华中科技大学,2009.
[14]周立,赵然,于航,等.航空电子WDM网络的实时性能分析[J].北京航空航天大学学报,2009,35(11)：1408-1412.
[15]谢文涛.略论航空电子在空中力量建设中的作用和地位[J].航空电子技术,2004,35(3)：1-5.
[16]王卫东.面向第四代战斗机航空电子系统应用的分布式计算机系统[D].(博士论文).西安：西北工业大学,2001.
[17]Lu W, Hsieh H, Shin W, et al. A faster exact schedulability analysis for fixed-priority scheduling[J].Journal of Systems and Software,2006,79(12):1744-1753.
[18]王立刚.开放式混合实时系统中的调度方法研究[D].(博士论文).合肥：中国科学技术大学,2006.
[19]Bertossi A, Mancini L. Fault-tolerant rate-monotonic first-fit scheduling in hard-real-time systems[J].IEEE Transactions on Parallel and System,1999,10(9):934-945.
[20]Shaw A. Real-time systems and software[M].New York:John Wiley&Sons, Inc.,2001.
[21]Nissanke N. Real-time systems[M]:Prentice Hall,1997.
[22]Liu J. Real-time systems[M].Beijing:Higher Education Press,2000.
[23]Bernat G, Burns A.Specification and analysis of weakly hard real-time systems[D].(Ph.D. Dissertation):Universitat de les Illes Balears,1998.
[24]Zhao W, Ramamritham K, Stankovic J. Preemptive scheduling under time and resource constraints[J].IEEE Transactions on Computers,1987,36(8):949-960.
[25]Lu C. Feedback control real-time scheduling[D].(Ph.D. Dissertation):University of Virginia 2001.
[26]Han C, Lin K, Hou C.Distance-constrained scheduling and its applications to real-time systems[J].IEEE Transactions on Computers,1996,45(7):814-826.
[27]Jones M, Regehr J. CPU reservations and time constraints:implementation experience on Windows NT[C].Proceedings of the 3rd USENIX Windows NT Symposium,1999:93-102.
[28]Kopetz H. The time-triggered model of computation[C].Proceedings of the 19th IEEE Real-Time Systems Symposium,1998:168-177.
[29]Leung J, Whitehead J. On the complexity of fixed-priority scheduling of periodic real-time tasks[J].Performance Evaluation,1982,2:237-250.
[30]Mok A.Fundamental design problems of distributed systems for the hard real-time environment[D].(Ph.D.Dissertation). Cambridge:Massachusetts Institute of Technology,1983.
[31]Locke C. Best-effort decision making for real-time scheduling[D].(Ph.D. Dissertation). Pittsburgh:Carnegie-Mellon University,1986.
[32]Tari Z, Broberg J, Zomaya A, et al. A least flow-time first load sharing approach for distributed server farm[J].Journal of Parallel and Distributed Computing,2005,65(7):832-842.
[33]Guo J, Bhuyan L. Load balancing in a cluster-based web server for multimedia applications[J]. Ieee Transactions on Parallel and Distributed Systems,2006,17(11):1321-1334.
[34]Cheng A, Rao S.Real-time traffic scheduling and routing in packet-switched networks using a least-laxity-first strategy[J].Journal of Vlsi Signal Processing Systems for Signal Image and Video Technology,2003,34(1-2):139-148.
[35]Dertouzos M, Mok A. Multiprocessor online scheduling of hard-real-time tasks[J].IEEE Trans on Software Engineering,1989,15:1497-1506.
[36]Abbott R, Garcia-Molina H. Scheduling real-time transactions:a performance evaluation[J]. ACM Transactions on Database Systems,1992,17(3):513-560.
[37]Hildebrandt J, Golatowski F, Timmemann D. Scheduling coprocessor for enhanced least-laxity-first scheduling in hard real-time systems[C].Proceeding of the 11th Euromicro Conference on Real-Time System, Los Alamitos,1999:208-215.
[38]Oh S,Yang S.A modified least-laxity first scheduling algorithm for real-time tasks[C]. Proceeding of the 5th international Conference on Real-Time Computer Systems and Applications, Los Alamitos,1998:31-36.
[39]金宏,王宏安,王强,等.改进的最小空闲时间优先调度算法[J].软件学报,2004,15(8)：1116-1123.
[40]Lee J, Tiao A, Yen J. A fuzzy rule-based approach to real-time scheduling[C].Proceedings of the 3rd IEEE International Conference on Fuzzy Systems, Orlando, Florida, USA,1994: 1394-1399.
[41]Uthaisombut P. Generalization of EDF and LLF:Identifying all optimal online algorithms for minimizing maximum lateness[J].Algorithmica,2008,50(3):312-328.
[42]Narlikar G, Wilfong G, Zhang L. Designing multihop wireless backhaul networks with delay guarantees[J].Wireless Networks,2010,16(1):237-254.
[43]Hei X, Tsang D. Earliest deadline first scheduling with active buffer management for real-time traffic in the Internet[J].Telecommunication Systems,2002,19(3-4):349-359.
[44]Pedreiras P, Almeida L. EDF message scheduling on controller area network[J].Computing & Control Engineering Journal,2002,13(4):163-170.
[45]Zhu Y, Mueller F. Exploiting synchronous and asynchronous DVS for feedback EDF scheduling on an embedded platform[J].Acm Transactions on Embedded Computing Systems,2006,5:1-24.
[46]Choi Y, Kim H. A new scheduling scheme for high-speed packet networks: Earliest-virtual-deadline-first[J].Computer Communications,2007,30(10):2291-2300.
[47]Jeffay K, Stanat D, Martel C. On non-preemptive scheduling of periodic and sporadic tasks[C]. Proceeding of the 12th IEEE Symposium on Real-Time Systems,1991:129-139.
[48]Kargahi M, Movaghar A. A method for performance analysis of earliest-deadline-first scheduling policy[J].Journal of Supercomputing,2006,37(2):197-222.
[49]Elsayed K, Ayad A, El-Hadidi M. Performance evaluation of resource reservation policies for rate-controlled earliest-deadline-first scheduling in multi-service packet networks[J]. Telecommunication Systems,2004,26(1):69-91.
[50]Zhang F, Burns A. Schedulability analysis for real-time systems with EDF scheduling[J].IEEE Transactions on Computers,2009,58(9):1250-1258.
[51]Sivaraman V, Chiussi F. Statistical analysis of delay bound violations at an earliest deadline first (EDF) scheduler[J].Performance Evaluation,1999,36-7:457-470.
[52]Hanada M, Nakazato H. An approximation analysis of nonpreemptive EDF scheduling[J]. Electronics and Communications in Japan Part Iii-Fundamental Electronic Science,2006, 89(2):13-23.
[53]Guan N, Deng Q, Gu Z, et al. Schedulability analysis of preemptive and nonpreemptive EDF on partial runtime-reconfigurable FPGAs[J].Acm Transactions on Design Automation of Electronic Systems,2008,13(4):56:51-56:43.
[54]Danne K, Platzner M. An EDF schedulability test for periodic tasks on reconfigurable hardware devices[J].Acm Sigplan Notices,2006,41(7):93-102.
[55]Abdelzaher T, Sharma V, Lu C. A utilization bound for aperiodic tasks and priority driven scheduling[J].IEEE Transactions on Computers,2004,53(3):334-350.
[56]Baker T. Stack-based scheduling of realtime processes[J].Journal of Real-Time Systems,1991, (3):67-99.
[57]Sivaraman V, Chiussi F, Gerla M. Deterministic end-to-end delay guarantees with rate controlled EDF scheduling[J].Performance Evaluation,2006,63(4-5):509-519.
[58]Zhu Y, Mueller F. Feedback EDF scheduling exploiting hardware-assisted asynchronous dynamic voltage scaling[J].Acm Sigplan Notices,2005,40(7):203-212.
[59]Xiong M, Wang Q, Ramamritham K. On earliest deadline first scheduling for temporal consistency maintenance[J].Real-Time Systems,2008,40(2):208-237.
[60]Spuri M, Buttazzo G. Scheduling aperiodic tasks in dynamic priority systems[J].Real-Time Systems,1996,10(2):179-210.
[61]Lamie W. Preemption-threshold[M]:White Paper, Express Logic Inc.
[62]Kim S,Hong S, Kim T. Perfecting preemption threshold scheduling for object-oriented real-time system design:From the perspective of real-time synchronization[J].Acm Sigplan Notices,2002, 37(7):223-232.
[63]Fishkin A, Jansen K, Sevastyanov S,et al. Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays[J].Algorithms-Esa 2005,2005, 3669:580-591.
[64]Kang C, Kim T, Kim J. Adaptive delay threshold-based priority queuing scheme with opportunistic packet scheduling for integrated service in mobile broadband wireless access systems[J].Ieee Communications Letters,2008,12(4):241-243.
[65]Kim D, Kang C. Delay threshold-based priority queueing packet scheduling for integrated services in mobile broadband wireless access system[C].Proceedings of High Performance Computing and Communications,2005:305-314.
[66]Yang Y, Lee S, Jung H, et al. Inter-ONU bandwidth scheduling by using threshold reporting and adaptive polling for QoS in EPONs[J].Etri Journal,2005,27(6):802-805.
[67]Lee D, Vassiliadis V, Park J. A novel threshold accepting meta-heuristic for the job-shop scheduling problem[J].Computers & Operations Research,2004,31(13):2199-2213.
[68]Pande S, Agrawal D, Mauney J. A threshold scheduling strategy for sisal on distributed-memory machines[J].Journal of Parallel and Distributed Computing,1994,21(2):223-236.
[69]Tsaur D, Tang C, Wu C, et al. A threshold-based matching algorithm for photonic Clos network switches[J].Proceedings of High Performance Computing and Communications,2005:166-179.
[70]Nam S, Alouini M, Yang H, et al. Threshold-based parallel multiuser scheduling[J].IEEE Transactions on Wireless Communications,2009,8(4):2150-2159.
[71]Tarantilis C, Kiranoudis C. A list-based threshold accepting method for job shop scheduling problems[J].International Journal of Production Economics,2002,77(2):159-171.
[72]Chang C, Lin P C, Chen J. Study on optimal queue-length-threshold scheduling policy for an atm multiplexer with finite buffers and batch poisson arrivals[J].Computer Networks and Isdn Systems,1994,26(5):525-540.
[73]Kim Y, Hwang G.Threshold-based opportunistic scheduling for ergodic rate guarantees in wireless networks[J].IEEE Transactions on Wireless Communications,2009,8(1):84-89.
[74]Krishnamurthy V, Djonin D. Structured threshold policies for dynamic sensor scheduling-A partially observed Markov decision process approach[J].Ieee Transactions on Signal Processing, 2007,55(10):4938-4957.
[75]Nelson R, Towsley D. Approximating the Mean Time in System in a Multiple-Server Queue That Uses Threshold Scheduling[J].Operations Research,1987,35(3):419-427.
[76]Weber S, Andrews J, Jindal N. The effect of fading, channel inversion, and threshold scheduling on ad hoc networks[J].Ieee Transactions on Information Theory,2007,53(11):4127-4149.
[77]Adan I, Wessels J, Zijm W. The effect of varying routing probability in 2 parallel queues with dynamic routing under a threshold-type scheduling[J].Ieice Transactions on Communications, 1993,E76b(1):29-31.
[78]Ngo M, Krishnamurthy V. Optimality of threshold policies for transmission scheduling in correlated fading channels[J].Ieee Transactions on Communications,2009,57(8):2474-2483.
[79]Nam S, Yang H, Alouini M, et al. Performance evaluation of threshold-based power allocation algorithms for down-link switched-based parallel scheduling[J].IEEE Transactions on Wireless Communications,2009,8(4):1744-1753.
[80]Wang Y, Saksena M. Scheduling fixed-priority tasks with preemption threshold[C].Proceeding of IEEE International Conference on Real-Time Computing Systems and Applications, Hongkong,1999:328-357.
[81]He D-Z, Wang F-Y, Li W. Dynamic preemption threshold scheduling for specific real-time control systems[C].Proceeding of 2005 Networking, Sensing and Control,2005:395-400.
[82]Saksena M, Wang Y. Scalable real-time system design using preemption thresholds[C]. Proceeding of the 21st IEEE Real-Time Systems Symposium, Los Alamitos,2000:25-34.
[83]Liu M, Chen D, Wu C, et al. Approximation theorem of the fuzzy transform in fuzzy reasoning and its application to the scheduling problem[J].Computer and Mathematics with Applications, 2006,51:515-526.
[84]Sabeghi M, Naghibzadeh M, Taghavi T. Scheduling non-preemptive periodic tasks in soft real-time systems using fuzzy inference[C].Proceeding of 9th IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing,2006:27-32.
[85]The concise handbook of linux for embedded real-time systems version 1.1 [M]:Timesys Corporation,2002.
[86]Harbour M. Real-Time POSIX:An overview[C].Proceeding of the VVConex'93 Int'l Conference,1993.
[87]Lam S, Xie G. Group priority scheduling[J].IEEE-ACM Transactions on Networking,1997, 5(2):205-218.
[88]Lehoczky J, Sha L. Performance of real-time bus scheduling algorithm[C].Proceeding of the 86 ACM SIGMETRICS Joint Int'l Conference on Computer Performance Modeling, New York, 1986:44-53.
[89]Katcher D, Sathaye S, Strosnider J. Fixed priority scheduling with limited priority levels[J].IEEE Tans on Computers,1995,44(9):1140-1144.
[90]Bin X, Yang Y, Jin S.Optimal fixed priority assignment with limited priority levels[J].Lecture Notes in Computer Science,2003,2834:194-203.
[91]Cayssial R, Orozco J, Santos J, et al. Rate monotonic scheduling of real-time control systems with the minimum number of priority levels[C].Proceeding of the 11th Euromicro Conference on Real Time Systems, Oakland:IEEE Computer Society Press,1999:54-59.
[92]宾雪莲,杨玉海,金士尧.一种有限优先级的静态优先级分配算法[J].软件学报,2004,15(6)：815-822.
[93]Hansen J, Zhu H, Lehoczky J, et al.Quantized EDF scheduling in a stochastic environment[C]. Proceedings of the international parallel and distributed processing symposium,2002.
[94]Doytchinov B, Lehoczky J, Shreve S.Real-time queues in heavy traffic with earliest-deadline-first queue discipline[J].The Annals of Applied Probability,2001, 11(2):332-378.
[95]Li W, Kavi K, Robert A.A non-preemptive scheduling algorithm for soft real-time systems[J]. Computer & Electrical Engineering,2007,33(1):12-29.
[96]Davari S, Dhall S K. An online algorithm for real-time tasks allocation[C].IEEE Real-time Systems Symposium,1986:194-200.
[97]Oh Y, Son S.Allocating fixed-priority periodic tasks on multiprocessor systems[J].Real-Time Systems,1995,9(3):207-239.
[98]Mark J, Ng S.Coding scheme for conflict-free multiaccess using global scheduling[J].Ieee Transactions on Communications,1979,27(9):1353-1360.
[99]Yang S,Shi M. Global scheduling in learning assessment grid[J].Computer Supported Cooperative Work in Design Ii,2006,3865:151-162.
[100]Rim M, Farm Y, Jain R. Global scheduling with code-motions for high-level synthesis applications[J].Ieee Transactions on Very Large Scale Integration (Vlsi) Systems,1995, 3(3):379-392.
[101]刘伍颖,卢宇彤,沈志宇.面向异构多域环境的全局资源调度研究与实现[J].计算机工程与应用,2006,42(18)：61-64.
[102]Bertogna M, Cirinei M, Lipari G. Schedulability analysis of global scheduling algorithms on multiprocessor platforms[J].Ieee Transactions on Parallel and Distributed Systems,2009, 20(4):553-566.
[103]Lundberg L, Lennerstad H. Guaranteeing response times for aperiodic tasks in global multiprocessor scheduling[J].Real-Time Systems,2007,35(2):135-151.
[104]Aida K, Takefusa A, Nakada H, et al. Performance evaluation model for scheduling in global computing systems [J].International Journal of High Performance Computing Applications,2000, 14(3):268-279.
[105]Hou Y, Zhang S, Zhong Y. Scheduling model in global real-time high performance computing with network calculus[J].Grid and Cooperative Computing, Pt 2,2004,3033:195-198.
[106]Baruah S,Cohen N, Plaxton C, et al. Proportionate progress:a notion of fairness in resource allocation[J].Algorithmica,1994,15:600-625.
[107]Anderson J, Srinivasan A. Early-release fair scheduling[C].Proceedings of the 12th Euromicro Conference on Real-Time Systems,2000:35-43.
[108]Block A, Anderson J, Devi U. Task reweighting under global scheduling on multiprocessors [J]. Real-Time Systems,2008,39(1-3):123-167.
[109]Zhang A, Nodine M, Bhargava B.Global scheduling for flexible transactions in heterogeneous distributed database systems[J].Ieee Transactions on Knowledge and Data Engineering,2001, 13(3):439-450.
[110]Gareym R, Johnson D. Computers and Intractability:a guide to the theory of NP-completenss[M]. New York:W H Freeman,1979.
[111]Zhao D, Upadhyaya S.Dynamically partitioned test scheduling with adaptive TAM configuration for power-constrained SoC testing[J].Ieee Transactions on Computer-Aided Design of Integrated Circuits and Systems,2005,24(6):956-965.
[112]Teich J, Thiele L, Zhang L. Partitioning processor arrays under resource constraints[J].Journal of Vlsi Signal Processing Systems for Signal Image and Video Technology,1997,17(1):5-20.
[113]Naik V, Setia S, Squillante M. Processor allocation in multiprogrammed distributed-memory parallel computer systems[J].Journal of Parallel and Distributed Computing,1997,46(1):28-47.
[114]Guha R, Bagherzadeh N, Chou P. Resource management and task partitioning and scheduling on a run-time reconfigurable embedded system[J].Computers & Electrical Engineering,2009, 35(2):258-285.
[115]Chaturvedi A, Choubey A, Roan J. Scheduling the allocation of data fragments in a distributed database environment-a machine learning approach[J].Ieee Transactions on Engineering Management,1994,41(2):194-207.
[116]Danneberg D, Tautenhahn T, Werner F. A comparison of heuristic algorithms for flow shop scheduling problems with setup times and limited batch size[J].Mathematical and Computer Modelling,1999,29(9):101-126.
[117]Johnson D.Near-optimal bin packing algorithms[D].(Ph.D. Dissertation). Cambridge: Massachusetts Institute of Technology,1973.
[118]Teich J, Thiele L. Exact partitioning of affine dependence algorithms[J].Embedded Processor Design Challenges,2002,2268:135-153.
[119]Laskowski E. Fast scheduling and partitioning algorithm in the multi-processor system with redundant communication resources[J].Parallel Processing Applied Mathematics,2002, 2328:97-106.
[120]Dion M, Risset T, Robert Y. Resource-constrained scheduling of partitioned algorithms on processor arrays[J].Integration-the Vlsi Journal,1996,20(2):139-159.
[121]Yang T, Fu C.Heuristic algorithms for scheduling iterative task computations on distributed memory machines[J].Ieee Transactions on Parallel and Distributed Systems,1997,8(6):608-622.
[122]Crauwels H, Potts C, VanWassenhove L. Local search heuristics for single machine scheduling with batch set-up times to minimize total weighted completion time[J].Annals of Operations Research,1997,70:261-279.
[123]Baruah S, Fisher N. The partitioned dynamic-priority scheduling of sporadic task systems[J]. Real-Time Systems,2007,36:199-226.
[124]Baruah S, Fisher N. The partitioned multiprocessor scheduling of deadline-constrained sporadic task systems[J].IEEE Transactions on Computers,2006,55(7):918-923.
[125]Fisher N, Baruah S, Baker T. The partitioned scheduling of sporadic tasks according to static-priorities[C].Proceedings of the 18th Euromicro Conference on Real-Time Systems, 2006:118-127.
[126]Fisher N, Baruah S. The partitioned, static-priority scheduling of sporadic real-time tasks with constrained deadlines on multiprocessor platforms[C].Proceeding of the 9th International Conference on Principles of Distributed Systems,2005:291-305.
[127]Kim J, Shivle S,Siegel H, et al. Dynamic mapping in a heterogeneous environment with tasks having priorities and multiple deadlines[M].Nice, France:Heterogeneous Computing Workshop, 2003.
[128]Braun T, Siegel H, Maciejewski A.heterogeneous computing:goals, methods, and openproblems[J].Lecture Notes in Computer Science,2001,2228/2001:307-318.
[129]Baruah S.Feasibility analysis of preemptive real-time systems upon heterogeneous multiprocessor platforms[C].Proceedings of the 25th IEEE International Real-Time Systems Symposium,2004:37-46.
[130]Baruah S.Task partitioning upon heterogeneous multiprocessor platforms[C].Proceedings of the 10th IEEE Real-Time and Embedded Technology and Applications Symposium,2004: 536-543.
[131]宾雪莲.实时系统中的任务调度技术研究[D].(博士论文).长沙：国防科学技术大学,2004.
[132]Kasztenny B,Hatziadoniu C, Wiszniewski A. Real-Time modeling and digital implementation of fuzzy logic controllers[C].International Conference on Digital Power System Simulators, 1995:323-328.
[133]金宏,王宏安,王强,等.模糊动态抢占调度算法[J].计算机学报,2004,27(6)：812-818.
[134]Kasztenny B,Hatziadoniu C, Wiszniewski A.A real-time modeling and digital implementation of fuzzy logic controllers[C].The First International Conference on Digital Power System Simulators,1995:323-328.
[135]Sirichuenwichit J, Thumthawatworn T, Santiprabhob P.Adaptive fuzzy rule-based processes scheduling in distributed computing environment[C].Proceeding of 2004 IEEE Aerospace Conference 2004:2249-2262.
[136]Hoang H, Buttazzo G, Jonsson M, et al. Computing the minimum EDF feasible deadline in periodic systems[C].Proceedings of the 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Application,2006:125-134.
[137]Baruah S K, Rosier L E, Howell R R. Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor[J].Real-Time Systems,1990,2:301-324.
[138]王重钢,隆克平,龚向阳,等.分组交换网络中队列调度算法的研究及其展望[J].电子学报,2001,29(4)：553-559.
[139]Buttazzo G. Rate Monotonic vs. EDF:Judgment day[J].Real-Time Systems,2005,29(1):5-26.
[140]陈英革,王小英,赵海,等.任务调度过程中就绪队列的优化研究[J].系统仿真学报,2006,18(4)：877-882.
[141]Swiderski J. Approximate performance analysis of heavily loaded slotted downlink channel in a wireless CDMA system supporting integrated voice/data services[J].IEEE Transactions on Wireless Communications,2005,4(2):484-494.
[142]Meschi A, Di N, Spuri M. Earliest deadline message scheduling with limited priority inversion[C]. Proceedings of the 4th International Workshop on Parallel and Distributed Real-Time Systems, 1996 15-16 April 87-94
[143]Bidoki A M Z, Yazdani N, Azhari S V. A logarithmic scheduling algorithm for high speed input-queued switches[J].Computer Communications,2008,31(1):5-18.
[144]Erbas C, Pimentel A, Cerav-Erbas S.Static priority scheduling of event-triggered real-time embedded systems[J]:Formal Methods in System Design,2007,30(1):29-47.
[145]Baker T P. Stack-based scheduling of realtime processes[J].Journal of Real-Time Systems,1991, (3):67-99.
[146]Lehoczky J P. Fixed priority scheduling of periodic task sets with arbitrary deadlines[C]. Proceedings of the 1 lth Real-Time Systems Symposium,1990:201-209.
[147]Krishnamurti R, Ma E. An approximation algorithm for scheduling tasks on varying partition sizes in partitionable multiprocessor systems[J].IEEE Transactions on Computers,1992, 41(12):1572-1579.
[148]Baker T, Cirinei M. Brute-force determination of multiprocessor schedulability for sets of sporadic hard-daadline tasks[J].Leture Notes in Computer Science,2007,4878/2007:62-75.
[149]Baruah S, Fisher N. Global deadline-monotonic scheduling of arbitrary-deadline sporadic task systems[J].Leture Notes in Computer Science,2007,4878/2007:204-216.
[150]Baruah S, Fisher N. Global fixed-priority scheduling of arbitrary-deadline sporadic task systems[J].Leture Notes in Computer Science,2008,4904/2008:215-226.
[151]Park S, Cho K. Real-time preemptive scheduling of sporadic tasks based on supervisory control of discrete event systems[J].Information Sciences,2008,178:3393-3401.
[152]Dubernard J, Genjet D. Scheduling hard sporadic tasks by means of finite automata and generating functions[C].Proceeding of the 6th International Conference on Implementation and Application of Automata,2001:87-100.
[153]Baruah S, Mok A, Rosier L. Preemptively scheduling hard-real-time sporadic tasks on one processor[C].Proceedings of the 1 lth Real-Time Systems Symposium,1990:182-190.
[154]Baruah S,Chen D, Gorinsky S,et al.Generalized multiframe tasks[J].The International Journal of Time-Critical Computing Systems,1999,15:5-22.
[155]Devi M. An improved schedulability test for uniprocessor periodic task systems[C].Proceeding of the 15th Euromicro Conference on Real-Time Systems,2003:23-30.
[156]Albers K, Slomka F. An event stream driven approximation for the analysis of Real-Time systems[C].Proceeding of the 16th Euromicro Conference on Real-Time Systems,2004: 187-195.
[157]Albers K, Slomka F. Efficient feasibility analysis for real-time systems with EDF scheduling[C]. Proceedings of the Design, Automation and Test in Europe Conference and Exhibition,2005: 492-497.
[158]Papadimitriou H. On the complexity of integer programming[J].Journal of the ACM,1981, 28(4):765-768.
[2]Daponte P, Grimaldi D, Marinov M. Real-time measurement and control of an industrial system over a standard network:Implementation of a prototype for educational purposes[J].Ieee Transactions on Instrumentation and Measurement,2002,51(5):962-969.
[3]Morelli E, Smith M. Real-time dynamic modeling:data information requirements and flight-test results[J].Journal of Aircraft,2009,46(6):1894-1905.
[4]Marjanovic O, Lennox B,Sandoz D, et al. Real-time monitoring of an industrial batch process[J]. Computers & Chemical Engineering,2006,30(10-12):1476-1481.
[5]Keller M, Kolb A.Real-time simulation of time-of-flight sensors[J].Simulation Modelling Practice and Theory,2009,17(5):967-978.
[6]Steenburgh W J. Using real-time mesoscale modeling in undergraduate education[J].Bulletin of the American Meteorological Society,2002,83(10):1447-1451.
[7]Neves P, Fontes F, Sargento S,et al.Broadband wireless real-time communications[J].Ieee Vehicular Technology Magazine,2008,3(4):39-47.
[8]胡天亮,张承瑞,刘日良,等.功能分离的嵌入式实时系统设计方法及应用[J].计算机集成制造系统,2008,14(3)：431-437.
[9]Stankovic J. Misconceptions about real-time computing:a serious problem for next-generation systems[J].IEEE Computer,1988,10:10-19.
[10]Krishna C, Shin K. Real-time systems[M].New York:The McGraw-Hill Companies, Inc,1997.
[11]The authorized guide to version 3 of the single UNIX specification[M]:The Open Group,2002.
[12]Liu C, Layland J. Scheduling algorithms for multiprogramming in real-time systems.[J].Journal of ACM,1973,20(1):46-61.
[13]张杰.最早截止期优先实时调度算法的研究[D].(博士论文).武汉：华中科技大学,2009.
[14]周立,赵然,于航,等.航空电子WDM网络的实时性能分析[J].北京航空航天大学学报,2009,35(11)：1408-1412.
[15]谢文涛.略论航空电子在空中力量建设中的作用和地位[J].航空电子技术,2004,35(3)：1-5.
[16]王卫东.面向第四代战斗机航空电子系统应用的分布式计算机系统[D].(博士论文).西安：西北工业大学,2001.
[17]Lu W, Hsieh H, Shin W, et al. A faster exact schedulability analysis for fixed-priority scheduling[J].Journal of Systems and Software,2006,79(12):1744-1753.
[18]王立刚.开放式混合实时系统中的调度方法研究[D].(博士论文).合肥：中国科学技术大学,2006.
[19]Bertossi A, Mancini L. Fault-tolerant rate-monotonic first-fit scheduling in hard-real-time systems[J].IEEE Transactions on Parallel and System,1999,10(9):934-945.
[20]Shaw A. Real-time systems and software[M].New York:John Wiley&Sons, Inc.,2001.
[21]Nissanke N. Real-time systems[M]:Prentice Hall,1997.
[22]Liu J. Real-time systems[M].Beijing:Higher Education Press,2000.
[23]Bernat G, Burns A.Specification and analysis of weakly hard real-time systems[D].(Ph.D. Dissertation):Universitat de les Illes Balears,1998.
[24]Zhao W, Ramamritham K, Stankovic J. Preemptive scheduling under time and resource constraints[J].IEEE Transactions on Computers,1987,36(8):949-960.
[25]Lu C. Feedback control real-time scheduling[D].(Ph.D. Dissertation):University of Virginia 2001.
[26]Han C, Lin K, Hou C.Distance-constrained scheduling and its applications to real-time systems[J].IEEE Transactions on Computers,1996,45(7):814-826.
[27]Jones M, Regehr J. CPU reservations and time constraints:implementation experience on Windows NT[C].Proceedings of the 3rd USENIX Windows NT Symposium,1999:93-102.
[28]Kopetz H. The time-triggered model of computation[C].Proceedings of the 19th IEEE Real-Time Systems Symposium,1998:168-177.
[29]Leung J, Whitehead J. On the complexity of fixed-priority scheduling of periodic real-time tasks[J].Performance Evaluation,1982,2:237-250.
[30]Mok A.Fundamental design problems of distributed systems for the hard real-time environment[D].(Ph.D.Dissertation). Cambridge:Massachusetts Institute of Technology,1983.
[31]Locke C. Best-effort decision making for real-time scheduling[D].(Ph.D. Dissertation). Pittsburgh:Carnegie-Mellon University,1986.
[32]Tari Z, Broberg J, Zomaya A, et al. A least flow-time first load sharing approach for distributed server farm[J].Journal of Parallel and Distributed Computing,2005,65(7):832-842.
[33]Guo J, Bhuyan L. Load balancing in a cluster-based web server for multimedia applications[J]. Ieee Transactions on Parallel and Distributed Systems,2006,17(11):1321-1334.
[34]Cheng A, Rao S.Real-time traffic scheduling and routing in packet-switched networks using a least-laxity-first strategy[J].Journal of Vlsi Signal Processing Systems for Signal Image and Video Technology,2003,34(1-2):139-148.
[35]Dertouzos M, Mok A. Multiprocessor online scheduling of hard-real-time tasks[J].IEEE Trans on Software Engineering,1989,15:1497-1506.
[36]Abbott R, Garcia-Molina H. Scheduling real-time transactions:a performance evaluation[J]. ACM Transactions on Database Systems,1992,17(3):513-560.
[37]Hildebrandt J, Golatowski F, Timmemann D. Scheduling coprocessor for enhanced least-laxity-first scheduling in hard real-time systems[C].Proceeding of the 11th Euromicro Conference on Real-Time System, Los Alamitos,1999:208-215.
[38]Oh S,Yang S.A modified least-laxity first scheduling algorithm for real-time tasks[C]. Proceeding of the 5th international Conference on Real-Time Computer Systems and Applications, Los Alamitos,1998:31-36.
[39]金宏,王宏安,王强,等.改进的最小空闲时间优先调度算法[J].软件学报,2004,15(8)：1116-1123.
[40]Lee J, Tiao A, Yen J. A fuzzy rule-based approach to real-time scheduling[C].Proceedings of the 3rd IEEE International Conference on Fuzzy Systems, Orlando, Florida, USA,1994: 1394-1399.
[41]Uthaisombut P. Generalization of EDF and LLF:Identifying all optimal online algorithms for minimizing maximum lateness[J].Algorithmica,2008,50(3):312-328.
[42]Narlikar G, Wilfong G, Zhang L. Designing multihop wireless backhaul networks with delay guarantees[J].Wireless Networks,2010,16(1):237-254.
[43]Hei X, Tsang D. Earliest deadline first scheduling with active buffer management for real-time traffic in the Internet[J].Telecommunication Systems,2002,19(3-4):349-359.
[44]Pedreiras P, Almeida L. EDF message scheduling on controller area network[J].Computing & Control Engineering Journal,2002,13(4):163-170.
[45]Zhu Y, Mueller F. Exploiting synchronous and asynchronous DVS for feedback EDF scheduling on an embedded platform[J].Acm Transactions on Embedded Computing Systems,2006,5:1-24.
[46]Choi Y, Kim H. A new scheduling scheme for high-speed packet networks: Earliest-virtual-deadline-first[J].Computer Communications,2007,30(10):2291-2300.
[47]Jeffay K, Stanat D, Martel C. On non-preemptive scheduling of periodic and sporadic tasks[C]. Proceeding of the 12th IEEE Symposium on Real-Time Systems,1991:129-139.
[48]Kargahi M, Movaghar A. A method for performance analysis of earliest-deadline-first scheduling policy[J].Journal of Supercomputing,2006,37(2):197-222.
[49]Elsayed K, Ayad A, El-Hadidi M. Performance evaluation of resource reservation policies for rate-controlled earliest-deadline-first scheduling in multi-service packet networks[J]. Telecommunication Systems,2004,26(1):69-91.
[50]Zhang F, Burns A. Schedulability analysis for real-time systems with EDF scheduling[J].IEEE Transactions on Computers,2009,58(9):1250-1258.
[51]Sivaraman V, Chiussi F. Statistical analysis of delay bound violations at an earliest deadline first (EDF) scheduler[J].Performance Evaluation,1999,36-7:457-470.
[52]Hanada M, Nakazato H. An approximation analysis of nonpreemptive EDF scheduling[J]. Electronics and Communications in Japan Part Iii-Fundamental Electronic Science,2006, 89(2):13-23.
[53]Guan N, Deng Q, Gu Z, et al. Schedulability analysis of preemptive and nonpreemptive EDF on partial runtime-reconfigurable FPGAs[J].Acm Transactions on Design Automation of Electronic Systems,2008,13(4):56:51-56:43.
[54]Danne K, Platzner M. An EDF schedulability test for periodic tasks on reconfigurable hardware devices[J].Acm Sigplan Notices,2006,41(7):93-102.
[55]Abdelzaher T, Sharma V, Lu C. A utilization bound for aperiodic tasks and priority driven scheduling[J].IEEE Transactions on Computers,2004,53(3):334-350.
[56]Baker T. Stack-based scheduling of realtime processes[J].Journal of Real-Time Systems,1991, (3):67-99.
[57]Sivaraman V, Chiussi F, Gerla M. Deterministic end-to-end delay guarantees with rate controlled EDF scheduling[J].Performance Evaluation,2006,63(4-5):509-519.
[58]Zhu Y, Mueller F. Feedback EDF scheduling exploiting hardware-assisted asynchronous dynamic voltage scaling[J].Acm Sigplan Notices,2005,40(7):203-212.
[59]Xiong M, Wang Q, Ramamritham K. On earliest deadline first scheduling for temporal consistency maintenance[J].Real-Time Systems,2008,40(2):208-237.
[60]Spuri M, Buttazzo G. Scheduling aperiodic tasks in dynamic priority systems[J].Real-Time Systems,1996,10(2):179-210.
[61]Lamie W. Preemption-threshold[M]:White Paper, Express Logic Inc.
[62]Kim S,Hong S, Kim T. Perfecting preemption threshold scheduling for object-oriented real-time system design:From the perspective of real-time synchronization[J].Acm Sigplan Notices,2002, 37(7):223-232.
[63]Fishkin A, Jansen K, Sevastyanov S,et al. Preemptive scheduling of independent jobs on identical parallel machines subject to migration delays[J].Algorithms-Esa 2005,2005, 3669:580-591.
[64]Kang C, Kim T, Kim J. Adaptive delay threshold-based priority queuing scheme with opportunistic packet scheduling for integrated service in mobile broadband wireless access systems[J].Ieee Communications Letters,2008,12(4):241-243.
[65]Kim D, Kang C. Delay threshold-based priority queueing packet scheduling for integrated services in mobile broadband wireless access system[C].Proceedings of High Performance Computing and Communications,2005:305-314.
[66]Yang Y, Lee S, Jung H, et al. Inter-ONU bandwidth scheduling by using threshold reporting and adaptive polling for QoS in EPONs[J].Etri Journal,2005,27(6):802-805.
[67]Lee D, Vassiliadis V, Park J. A novel threshold accepting meta-heuristic for the job-shop scheduling problem[J].Computers & Operations Research,2004,31(13):2199-2213.
[68]Pande S, Agrawal D, Mauney J. A threshold scheduling strategy for sisal on distributed-memory machines[J].Journal of Parallel and Distributed Computing,1994,21(2):223-236.
[69]Tsaur D, Tang C, Wu C, et al. A threshold-based matching algorithm for photonic Clos network switches[J].Proceedings of High Performance Computing and Communications,2005:166-179.
[70]Nam S, Alouini M, Yang H, et al. Threshold-based parallel multiuser scheduling[J].IEEE Transactions on Wireless Communications,2009,8(4):2150-2159.
[71]Tarantilis C, Kiranoudis C. A list-based threshold accepting method for job shop scheduling problems[J].International Journal of Production Economics,2002,77(2):159-171.
[72]Chang C, Lin P C, Chen J. Study on optimal queue-length-threshold scheduling policy for an atm multiplexer with finite buffers and batch poisson arrivals[J].Computer Networks and Isdn Systems,1994,26(5):525-540.
[73]Kim Y, Hwang G.Threshold-based opportunistic scheduling for ergodic rate guarantees in wireless networks[J].IEEE Transactions on Wireless Communications,2009,8(1):84-89.
[74]Krishnamurthy V, Djonin D. Structured threshold policies for dynamic sensor scheduling-A partially observed Markov decision process approach[J].Ieee Transactions on Signal Processing, 2007,55(10):4938-4957.
[75]Nelson R, Towsley D. Approximating the Mean Time in System in a Multiple-Server Queue That Uses Threshold Scheduling[J].Operations Research,1987,35(3):419-427.
[76]Weber S, Andrews J, Jindal N. The effect of fading, channel inversion, and threshold scheduling on ad hoc networks[J].Ieee Transactions on Information Theory,2007,53(11):4127-4149.
[77]Adan I, Wessels J, Zijm W. The effect of varying routing probability in 2 parallel queues with dynamic routing under a threshold-type scheduling[J].Ieice Transactions on Communications, 1993,E76b(1):29-31.
[78]Ngo M, Krishnamurthy V. Optimality of threshold policies for transmission scheduling in correlated fading channels[J].Ieee Transactions on Communications,2009,57(8):2474-2483.
[79]Nam S, Yang H, Alouini M, et al. Performance evaluation of threshold-based power allocation algorithms for down-link switched-based parallel scheduling[J].IEEE Transactions on Wireless Communications,2009,8(4):1744-1753.
[80]Wang Y, Saksena M. Scheduling fixed-priority tasks with preemption threshold[C].Proceeding of IEEE International Conference on Real-Time Computing Systems and Applications, Hongkong,1999:328-357.
[81]He D-Z, Wang F-Y, Li W. Dynamic preemption threshold scheduling for specific real-time control systems[C].Proceeding of 2005 Networking, Sensing and Control,2005:395-400.
[82]Saksena M, Wang Y. Scalable real-time system design using preemption thresholds[C]. Proceeding of the 21st IEEE Real-Time Systems Symposium, Los Alamitos,2000:25-34.
[83]Liu M, Chen D, Wu C, et al. Approximation theorem of the fuzzy transform in fuzzy reasoning and its application to the scheduling problem[J].Computer and Mathematics with Applications, 2006,51:515-526.
[84]Sabeghi M, Naghibzadeh M, Taghavi T. Scheduling non-preemptive periodic tasks in soft real-time systems using fuzzy inference[C].Proceeding of 9th IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing,2006:27-32.
[85]The concise handbook of linux for embedded real-time systems version 1.1 [M]:Timesys Corporation,2002.
[86]Harbour M. Real-Time POSIX:An overview[C].Proceeding of the VVConex'93 Int'l Conference,1993.
[87]Lam S, Xie G. Group priority scheduling[J].IEEE-ACM Transactions on Networking,1997, 5(2):205-218.
[88]Lehoczky J, Sha L. Performance of real-time bus scheduling algorithm[C].Proceeding of the 86 ACM SIGMETRICS Joint Int'l Conference on Computer Performance Modeling, New York, 1986:44-53.
[89]Katcher D, Sathaye S, Strosnider J. Fixed priority scheduling with limited priority levels[J].IEEE Tans on Computers,1995,44(9):1140-1144.
[90]Bin X, Yang Y, Jin S.Optimal fixed priority assignment with limited priority levels[J].Lecture Notes in Computer Science,2003,2834:194-203.
[91]Cayssial R, Orozco J, Santos J, et al. Rate monotonic scheduling of real-time control systems with the minimum number of priority levels[C].Proceeding of the 11th Euromicro Conference on Real Time Systems, Oakland:IEEE Computer Society Press,1999:54-59.
[92]宾雪莲,杨玉海,金士尧.一种有限优先级的静态优先级分配算法[J].软件学报,2004,15(6)：815-822.
[93]Hansen J, Zhu H, Lehoczky J, et al.Quantized EDF scheduling in a stochastic environment[C]. Proceedings of the international parallel and distributed processing symposium,2002.
[94]Doytchinov B, Lehoczky J, Shreve S.Real-time queues in heavy traffic with earliest-deadline-first queue discipline[J].The Annals of Applied Probability,2001, 11(2):332-378.
[95]Li W, Kavi K, Robert A.A non-preemptive scheduling algorithm for soft real-time systems[J]. Computer & Electrical Engineering,2007,33(1):12-29.
[96]Davari S, Dhall S K. An online algorithm for real-time tasks allocation[C].IEEE Real-time Systems Symposium,1986:194-200.
[97]Oh Y, Son S.Allocating fixed-priority periodic tasks on multiprocessor systems[J].Real-Time Systems,1995,9(3):207-239.
[98]Mark J, Ng S.Coding scheme for conflict-free multiaccess using global scheduling[J].Ieee Transactions on Communications,1979,27(9):1353-1360.
[99]Yang S,Shi M. Global scheduling in learning assessment grid[J].Computer Supported Cooperative Work in Design Ii,2006,3865:151-162.
[100]Rim M, Farm Y, Jain R. Global scheduling with code-motions for high-level synthesis applications[J].Ieee Transactions on Very Large Scale Integration (Vlsi) Systems,1995, 3(3):379-392.
[101]刘伍颖,卢宇彤,沈志宇.面向异构多域环境的全局资源调度研究与实现[J].计算机工程与应用,2006,42(18)：61-64.
[102]Bertogna M, Cirinei M, Lipari G. Schedulability analysis of global scheduling algorithms on multiprocessor platforms[J].Ieee Transactions on Parallel and Distributed Systems,2009, 20(4):553-566.
[103]Lundberg L, Lennerstad H. Guaranteeing response times for aperiodic tasks in global multiprocessor scheduling[J].Real-Time Systems,2007,35(2):135-151.
[104]Aida K, Takefusa A, Nakada H, et al. Performance evaluation model for scheduling in global computing systems [J].International Journal of High Performance Computing Applications,2000, 14(3):268-279.
[105]Hou Y, Zhang S, Zhong Y. Scheduling model in global real-time high performance computing with network calculus[J].Grid and Cooperative Computing, Pt 2,2004,3033:195-198.
[106]Baruah S,Cohen N, Plaxton C, et al. Proportionate progress:a notion of fairness in resource allocation[J].Algorithmica,1994,15:600-625.
[107]Anderson J, Srinivasan A. Early-release fair scheduling[C].Proceedings of the 12th Euromicro Conference on Real-Time Systems,2000:35-43.
[108]Block A, Anderson J, Devi U. Task reweighting under global scheduling on multiprocessors [J]. Real-Time Systems,2008,39(1-3):123-167.
[109]Zhang A, Nodine M, Bhargava B.Global scheduling for flexible transactions in heterogeneous distributed database systems[J].Ieee Transactions on Knowledge and Data Engineering,2001, 13(3):439-450.
[110]Gareym R, Johnson D. Computers and Intractability:a guide to the theory of NP-completenss[M]. New York:W H Freeman,1979.
[111]Zhao D, Upadhyaya S.Dynamically partitioned test scheduling with adaptive TAM configuration for power-constrained SoC testing[J].Ieee Transactions on Computer-Aided Design of Integrated Circuits and Systems,2005,24(6):956-965.
[112]Teich J, Thiele L, Zhang L. Partitioning processor arrays under resource constraints[J].Journal of Vlsi Signal Processing Systems for Signal Image and Video Technology,1997,17(1):5-20.
[113]Naik V, Setia S, Squillante M. Processor allocation in multiprogrammed distributed-memory parallel computer systems[J].Journal of Parallel and Distributed Computing,1997,46(1):28-47.
[114]Guha R, Bagherzadeh N, Chou P. Resource management and task partitioning and scheduling on a run-time reconfigurable embedded system[J].Computers & Electrical Engineering,2009, 35(2):258-285.
[115]Chaturvedi A, Choubey A, Roan J. Scheduling the allocation of data fragments in a distributed database environment-a machine learning approach[J].Ieee Transactions on Engineering Management,1994,41(2):194-207.
[116]Danneberg D, Tautenhahn T, Werner F. A comparison of heuristic algorithms for flow shop scheduling problems with setup times and limited batch size[J].Mathematical and Computer Modelling,1999,29(9):101-126.
[117]Johnson D.Near-optimal bin packing algorithms[D].(Ph.D. Dissertation). Cambridge: Massachusetts Institute of Technology,1973.
[118]Teich J, Thiele L. Exact partitioning of affine dependence algorithms[J].Embedded Processor Design Challenges,2002,2268:135-153.
[119]Laskowski E. Fast scheduling and partitioning algorithm in the multi-processor system with redundant communication resources[J].Parallel Processing Applied Mathematics,2002, 2328:97-106.
[120]Dion M, Risset T, Robert Y. Resource-constrained scheduling of partitioned algorithms on processor arrays[J].Integration-the Vlsi Journal,1996,20(2):139-159.
[121]Yang T, Fu C.Heuristic algorithms for scheduling iterative task computations on distributed memory machines[J].Ieee Transactions on Parallel and Distributed Systems,1997,8(6):608-622.
[122]Crauwels H, Potts C, VanWassenhove L. Local search heuristics for single machine scheduling with batch set-up times to minimize total weighted completion time[J].Annals of Operations Research,1997,70:261-279.
[123]Baruah S, Fisher N. The partitioned dynamic-priority scheduling of sporadic task systems[J]. Real-Time Systems,2007,36:199-226.
[124]Baruah S, Fisher N. The partitioned multiprocessor scheduling of deadline-constrained sporadic task systems[J].IEEE Transactions on Computers,2006,55(7):918-923.
[125]Fisher N, Baruah S, Baker T. The partitioned scheduling of sporadic tasks according to static-priorities[C].Proceedings of the 18th Euromicro Conference on Real-Time Systems, 2006:118-127.
[126]Fisher N, Baruah S. The partitioned, static-priority scheduling of sporadic real-time tasks with constrained deadlines on multiprocessor platforms[C].Proceeding of the 9th International Conference on Principles of Distributed Systems,2005:291-305.
[127]Kim J, Shivle S,Siegel H, et al. Dynamic mapping in a heterogeneous environment with tasks having priorities and multiple deadlines[M].Nice, France:Heterogeneous Computing Workshop, 2003.
[128]Braun T, Siegel H, Maciejewski A.heterogeneous computing:goals, methods, and openproblems[J].Lecture Notes in Computer Science,2001,2228/2001:307-318.
[129]Baruah S.Feasibility analysis of preemptive real-time systems upon heterogeneous multiprocessor platforms[C].Proceedings of the 25th IEEE International Real-Time Systems Symposium,2004:37-46.
[130]Baruah S.Task partitioning upon heterogeneous multiprocessor platforms[C].Proceedings of the 10th IEEE Real-Time and Embedded Technology and Applications Symposium,2004: 536-543.
[131]宾雪莲.实时系统中的任务调度技术研究[D].(博士论文).长沙：国防科学技术大学,2004.
[132]Kasztenny B,Hatziadoniu C, Wiszniewski A. Real-Time modeling and digital implementation of fuzzy logic controllers[C].International Conference on Digital Power System Simulators, 1995:323-328.
[133]金宏,王宏安,王强,等.模糊动态抢占调度算法[J].计算机学报,2004,27(6)：812-818.
[134]Kasztenny B,Hatziadoniu C, Wiszniewski A.A real-time modeling and digital implementation of fuzzy logic controllers[C].The First International Conference on Digital Power System Simulators,1995:323-328.
[135]Sirichuenwichit J, Thumthawatworn T, Santiprabhob P.Adaptive fuzzy rule-based processes scheduling in distributed computing environment[C].Proceeding of 2004 IEEE Aerospace Conference 2004:2249-2262.
[136]Hoang H, Buttazzo G, Jonsson M, et al. Computing the minimum EDF feasible deadline in periodic systems[C].Proceedings of the 12th IEEE International Conference on Embedded and Real-Time Computing Systems and Application,2006:125-134.
[137]Baruah S K, Rosier L E, Howell R R. Algorithms and complexity concerning the preemptive scheduling of periodic, real-time tasks on one processor[J].Real-Time Systems,1990,2:301-324.
[138]王重钢,隆克平,龚向阳,等.分组交换网络中队列调度算法的研究及其展望[J].电子学报,2001,29(4)：553-559.
[139]Buttazzo G. Rate Monotonic vs. EDF:Judgment day[J].Real-Time Systems,2005,29(1):5-26.
[140]陈英革,王小英,赵海,等.任务调度过程中就绪队列的优化研究[J].系统仿真学报,2006,18(4)：877-882.
[141]Swiderski J. Approximate performance analysis of heavily loaded slotted downlink channel in a wireless CDMA system supporting integrated voice/data services[J].IEEE Transactions on Wireless Communications,2005,4(2):484-494.
[142]Meschi A, Di N, Spuri M. Earliest deadline message scheduling with limited priority inversion[C]. Proceedings of the 4th International Workshop on Parallel and Distributed Real-Time Systems, 1996 15-16 April 87-94
[143]Bidoki A M Z, Yazdani N, Azhari S V. A logarithmic scheduling algorithm for high speed input-queued switches[J].Computer Communications,2008,31(1):5-18.
[144]Erbas C, Pimentel A, Cerav-Erbas S.Static priority scheduling of event-triggered real-time embedded systems[J]:Formal Methods in System Design,2007,30(1):29-47.
[145]Baker T P. Stack-based scheduling of realtime processes[J].Journal of Real-Time Systems,1991, (3):67-99.
[146]Lehoczky J P. Fixed priority scheduling of periodic task sets with arbitrary deadlines[C]. Proceedings of the 1 lth Real-Time Systems Symposium,1990:201-209.
[147]Krishnamurti R, Ma E. An approximation algorithm for scheduling tasks on varying partition sizes in partitionable multiprocessor systems[J].IEEE Transactions on Computers,1992, 41(12):1572-1579.
[148]Baker T, Cirinei M. Brute-force determination of multiprocessor schedulability for sets of sporadic hard-daadline tasks[J].Leture Notes in Computer Science,2007,4878/2007:62-75.
[149]Baruah S, Fisher N. Global deadline-monotonic scheduling of arbitrary-deadline sporadic task systems[J].Leture Notes in Computer Science,2007,4878/2007:204-216.
[150]Baruah S, Fisher N. Global fixed-priority scheduling of arbitrary-deadline sporadic task systems[J].Leture Notes in Computer Science,2008,4904/2008:215-226.
[151]Park S, Cho K. Real-time preemptive scheduling of sporadic tasks based on supervisory control of discrete event systems[J].Information Sciences,2008,178:3393-3401.
[152]Dubernard J, Genjet D. Scheduling hard sporadic tasks by means of finite automata and generating functions[C].Proceeding of the 6th International Conference on Implementation and Application of Automata,2001:87-100.
[153]Baruah S, Mok A, Rosier L. Preemptively scheduling hard-real-time sporadic tasks on one processor[C].Proceedings of the 1 lth Real-Time Systems Symposium,1990:182-190.
[154]Baruah S,Chen D, Gorinsky S,et al.Generalized multiframe tasks[J].The International Journal of Time-Critical Computing Systems,1999,15:5-22.
[155]Devi M. An improved schedulability test for uniprocessor periodic task systems[C].Proceeding of the 15th Euromicro Conference on Real-Time Systems,2003:23-30.
[156]Albers K, Slomka F. An event stream driven approximation for the analysis of Real-Time systems[C].Proceeding of the 16th Euromicro Conference on Real-Time Systems,2004: 187-195.
[157]Albers K, Slomka F. Efficient feasibility analysis for real-time systems with EDF scheduling[C]. Proceedings of the Design, Automation and Test in Europe Conference and Exhibition,2005: 492-497.
[158]Papadimitriou H. On the complexity of integer programming[J].Journal of the ACM,1981, 28(4):765-768.