最早截止期优先实时调度算法研究
|
摘要
实时系统具有及时响应、高可靠性、专用性、少人工干预等特征,被广泛应用于工业控制、军事防御、信号处理、航空航天技术等方面。在实时系统研究和应用的各个领域中,实时调度算法都是其中的一个基础问题,针对各种实时问题的解决,都需要在采用某种实时调度算法的基础上,结合该实时调度算法的性质才能更好的证明其可行性,并且实时调度算法的研究也可以很好的启发各种实时问题的解决,因此实时调度算法的研究对实时系统的研究和应用有重要的意义。最早截止期优先(earliest deadline first,简称EDF)调度算法作为最优的动态优先级调度算法,调度策略简单,并且周期任务集的总负载可以达到100%,其研究具有重要的理论和实际意义。
EDF算法调度周期任务集的最大可挪用时间在非周期任务调度、软实时任务调度和多处理器容错调度等方面都有重要的应用。通过对最大可挪用时间的性质进行分析,得出了最大可挪用时间等于系统中所有任务的最小可延迟时间且具有最小可延迟时间的任务发生在超周期的第一个繁忙区间等结论。在此基础上,提出一种可延迟时间逼近(delay time approximation,简称DTA)算法,利用EDF算法调度的最优性,通过最小周期任务的可延长执行时间逐次逼近,快速准确的计算最大可挪用时间。该算法的时间复杂度函数只和周期任务集的总负载、周期任务数有关,不需要在整个超周期中计算。
现有的硬实时周期任务和非周期任务混合调度算法的目标是为了缩短非周期任务的响应时间,不能判断该调度能否满足非周期任务的时限要求,所以它们都只适用于软实时任务的调度,而不适用于偶发任务的调度。因为EDF算法根据实时任务的截止期进行调度,所以可以直接用EDF算法来统一调度硬实时周期任务和偶发任务,并且具有最优的可调度性。通过计算EDF算法调度过程中的空闲时间和可挪用时间,以及调度偶发任务后对空闲时间和可挪用时间的影响,提出一种空闲挪用时间(idle slack stealing,简称ISS)算法来进行偶发任务的可调度性判定。
在多个实时任务之间有共享资源访问时,采用资源访问控制协议可以防止实时任务被无限期的阻塞,但是避免不了优先级反转引起的直接阻塞,还会导致继承阻塞。这些阻塞的过程都是低优先级的任务抢占高优先级的任务运行,打乱了EDF算法的正常调度。通过证明阻塞不会改变EDF调度时的空闲时间分布,并且在一个繁忙区间内,所有周期任务的每次运行最多都只会因为同一个资源的阻塞被推迟一次,然后把阻塞时间看成是挪用时间,根据最大可挪用时间的定义和性质提出了一种阻塞挪用时间(blocking translate stealing time,简称BTS)的可调度性判定条件:只要所有共享资源的最大临界区的长度之和不大于最大可挪用时间,硬实时周期任务集就是可以被调度的。
The real-time system has some characters such as responsing in time, high dependability, dedication and less artificial interference, so it is widely applied in the industrial control, military defense, signal processing, and aerospace technology. In the real-time systems research and applications in various fields, real-time scheduling algorithms are one of the basic problems, For a variety solution of real-time problem, it need on the basis adopt some kind of real-time scheduling algorithm, testifying whose feasibility combining with owing real time scheduling algorithmic character ability more well. Therefore, real-time scheduling algorithm is important for the real-time systems research and popularization. The EDF (earliest deadline first) scheduling algorithm as the optimal dynamic priority scheduling algorithm, the scheduling strategy is simple and periodic task sets can reach 100% of the total load, so there are a very attractive prospect.
The maximum stealing time of the EDF algorithm for scheduling periodic task has important application in many fields such as the non-periodic tasks scheduling, soft real-time tasks scheduling and multi-processor fault-tolerant scheduling, etc. Analysing of the nature of the maximum stealing time, giving the result that the maximum stealing time is equal to the minimum delayed time appears in the first busy time interval of the hyperperiod, presents the DTA (delay time approximation) algorithm. Using the optimal nature of EDF scheduling algorithm, and apporathing gradually by the delayed time of the task with the minimum period time, DTA algorithm can rapidly and accurate calculate the maximum stealing time. The algorithm's time complexity is only related to the total load of the periodic task set and the number of periodic tasks.
The existing hard real-time periodic tasks and non-periodic task scheduling algorithm aims to shorten the response time of aperiodic tasks and can not determine whether the task can meet the deadline tiem. So they are only suitable for soft real-time task scheduling, does not apply to sporadic task scheduling. Because EDF algorithm is based on the deadling time of each real-time task, so can use EDF scheduling algorithm to unified schedule real-time periodic tasks and sporadic tasks, and has the best schedulability. By calculating the idle time and the stealing time in the scheduling procedure with EDF algorithm, propose the ISS (idle slack stealing) algorithm to determine the schedulability of sporadic tasks.
When there are mutual exclusion resources sharing between some real-time tasks, using resource access control protocol can prevent real-time task has been indefinitely blocked, but can not prevent the direct blocking caused by priority inversion. In blocking time, the low-priority task seizes the high-priority task to run, disrupting the normal EDF scheduling procedure. By proving that blocking time does not change the distribution of idle time, and in a busy time interval, all periodic tasks will only be postponed once due to the same mutual exclusion resource. Then the blocking time as steal time and according to the definition and nature of maximum steal time, put forward the BTS (blocking translate stealing time) algorithm, witch can determine the conditions for schedulability. As long as the sum of the most critical areas of resources is more than the length of the maximum steal time, the real-time periodic task set is to be scheduled with EDF algorithm.
EDF算法调度周期任务集的最大可挪用时间在非周期任务调度、软实时任务调度和多处理器容错调度等方面都有重要的应用。通过对最大可挪用时间的性质进行分析,得出了最大可挪用时间等于系统中所有任务的最小可延迟时间且具有最小可延迟时间的任务发生在超周期的第一个繁忙区间等结论。在此基础上,提出一种可延迟时间逼近(delay time approximation,简称DTA)算法,利用EDF算法调度的最优性,通过最小周期任务的可延长执行时间逐次逼近,快速准确的计算最大可挪用时间。该算法的时间复杂度函数只和周期任务集的总负载、周期任务数有关,不需要在整个超周期中计算。
现有的硬实时周期任务和非周期任务混合调度算法的目标是为了缩短非周期任务的响应时间,不能判断该调度能否满足非周期任务的时限要求,所以它们都只适用于软实时任务的调度,而不适用于偶发任务的调度。因为EDF算法根据实时任务的截止期进行调度,所以可以直接用EDF算法来统一调度硬实时周期任务和偶发任务,并且具有最优的可调度性。通过计算EDF算法调度过程中的空闲时间和可挪用时间,以及调度偶发任务后对空闲时间和可挪用时间的影响,提出一种空闲挪用时间(idle slack stealing,简称ISS)算法来进行偶发任务的可调度性判定。
在多个实时任务之间有共享资源访问时,采用资源访问控制协议可以防止实时任务被无限期的阻塞,但是避免不了优先级反转引起的直接阻塞,还会导致继承阻塞。这些阻塞的过程都是低优先级的任务抢占高优先级的任务运行,打乱了EDF算法的正常调度。通过证明阻塞不会改变EDF调度时的空闲时间分布,并且在一个繁忙区间内,所有周期任务的每次运行最多都只会因为同一个资源的阻塞被推迟一次,然后把阻塞时间看成是挪用时间,根据最大可挪用时间的定义和性质提出了一种阻塞挪用时间(blocking translate stealing time,简称BTS)的可调度性判定条件:只要所有共享资源的最大临界区的长度之和不大于最大可挪用时间,硬实时周期任务集就是可以被调度的。
The real-time system has some characters such as responsing in time, high dependability, dedication and less artificial interference, so it is widely applied in the industrial control, military defense, signal processing, and aerospace technology. In the real-time systems research and applications in various fields, real-time scheduling algorithms are one of the basic problems, For a variety solution of real-time problem, it need on the basis adopt some kind of real-time scheduling algorithm, testifying whose feasibility combining with owing real time scheduling algorithmic character ability more well. Therefore, real-time scheduling algorithm is important for the real-time systems research and popularization. The EDF (earliest deadline first) scheduling algorithm as the optimal dynamic priority scheduling algorithm, the scheduling strategy is simple and periodic task sets can reach 100% of the total load, so there are a very attractive prospect.
The maximum stealing time of the EDF algorithm for scheduling periodic task has important application in many fields such as the non-periodic tasks scheduling, soft real-time tasks scheduling and multi-processor fault-tolerant scheduling, etc. Analysing of the nature of the maximum stealing time, giving the result that the maximum stealing time is equal to the minimum delayed time appears in the first busy time interval of the hyperperiod, presents the DTA (delay time approximation) algorithm. Using the optimal nature of EDF scheduling algorithm, and apporathing gradually by the delayed time of the task with the minimum period time, DTA algorithm can rapidly and accurate calculate the maximum stealing time. The algorithm's time complexity is only related to the total load of the periodic task set and the number of periodic tasks.
The existing hard real-time periodic tasks and non-periodic task scheduling algorithm aims to shorten the response time of aperiodic tasks and can not determine whether the task can meet the deadline tiem. So they are only suitable for soft real-time task scheduling, does not apply to sporadic task scheduling. Because EDF algorithm is based on the deadling time of each real-time task, so can use EDF scheduling algorithm to unified schedule real-time periodic tasks and sporadic tasks, and has the best schedulability. By calculating the idle time and the stealing time in the scheduling procedure with EDF algorithm, propose the ISS (idle slack stealing) algorithm to determine the schedulability of sporadic tasks.
When there are mutual exclusion resources sharing between some real-time tasks, using resource access control protocol can prevent real-time task has been indefinitely blocked, but can not prevent the direct blocking caused by priority inversion. In blocking time, the low-priority task seizes the high-priority task to run, disrupting the normal EDF scheduling procedure. By proving that blocking time does not change the distribution of idle time, and in a busy time interval, all periodic tasks will only be postponed once due to the same mutual exclusion resource. Then the blocking time as steal time and according to the definition and nature of maximum steal time, put forward the BTS (blocking translate stealing time) algorithm, witch can determine the conditions for schedulability. As long as the sum of the most critical areas of resources is more than the length of the maximum steal time, the real-time periodic task set is to be scheduled with EDF algorithm.
引文
[1]Burchard A,Liebeherr J,Oh YF,Son SH.New strategies for assigning real-time tasks to multiprocessor systems.IEEE Trans.On Computers,1995,44(12):1429-1442
[2]Kieckhafer RM,Walter CJ,Finn AM et al.The MAFT architecture for distributed fault_tolerance.IEEE Transactions on Computers,1988,37(4):398-405
[3]庞丽萍.操作系统原理(第三版).华中科技大学出版社,2000,110-150
[4]Kartik,Gopalan.Real-Time Support in General Purpose Operating Systems.Tech Report.Experimental Computer Systems Labs,Computer Science Dept,Stony Brook University,2001,63-71
[5]Damir Isovic.Handling Sporadic Tasks in Real-time Systems-Combined Offline and Online Approach.Licentiate Thesis,Mardalen University Press,2001.
[6]Damir Isovic,Gerhard Fohler.Efficient Scheduling of Sporadic,Aperiodic,and Periodic Tasks with Complex Constraints.In Proc.of the 21st IEEE Real-Time Systems Symposium.Walt Disney World,Orlando,Florida,USA,2000,1153-1161
[7]Liu CL,Layland JW.Scheduling algorithms for multiprogramming in a hard-real-time environment.Journal of ACM,1973,20(1):174-189
[8]G.Bernat,A.Burns.Specification and Analysis of Weakly Hard Real-Time Systems.PhD thesis.Department de Ciencies Matematiques Informatica,Universitat de les Illes Balears,Spain,1998
[9]G.Bernat,A.Burns.Combining(n,m)-hard deadlines with dual priority scheduling.In Proc.18th IEEE Real-Time Systems Symposium.San Francisco USA,1997,46-57
[10]M.Hamdaoui,P.Ramanathan.A dynamic priority assignment technique for streams with (m,k)-firm deadlines. IEEE Transactions on Computers, 1995, 44(12): 1443-1451
[11] Shanwei Cen, Calton Pu, Richard Staehli. A Distributed Real-Time MPEG Video Audio Player. In Fifth International Workshop on Network and Operating System Support of Digital Audio and Video (NOSSDAV'95). Durham, New Hampshire, USA, 1995,18(21):142-153
[12] David K.Y.Yau, Simon S.Lam. Adaptive Rate-Controlled Scheduling for Multimedia Applications. IEEE/ACM Transactions on Networking, 1997, 5(4):475-488
[13] Jason Nieh, Monica S.Lam. Integrated Processor Scheduling for Multimedia. In Proceedings of the Fifth International Workshop on Network and Operating System Support for Digital Audio and Video. Durham, NH, 1995, 215-218
[14] Katcher DI, Arakawa H, Strosnider JK. Engineering and analysis of fixed priority schedulers. IEEE Trans. on Software Engineering, 1993,19(9):920-934
[15] J.A. Stankovic, M. Spuri, K. Ramamritham, G. Buttazzo. Deadline Scheduling for Real-Time System:EDF and Related Algorithms. Kluwer Academic, 1998
[16] Raj Rajkumar, Kanaka Juvva, Anastasio Molano. Resource Kernels: A Resource-Centric Approach to Real-Time Systems. In Proceedings of the SPIE/ACM Conference on Multimedia Computing and Networking. San Jose, CA, USA, 1998.1,1233-1237
[17] J.Blazewiez. Deadline Scheduling of Tasks - A Survey. Foundation Contr. Eng, 1977,203-216
[18] Dertouzos, M. L. Control robotics: The procedural control of physical processes. Information Processing, 1974,74
[19] Mok, A. K. Fundamental Design Problems of Distributed Systems for the Hard Real-Time Environment. Ph.D. Thesis, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, Cambridge, MA, 1983.
[20] Lehoczky, J.P.Sha, L.Strosnider. Enhanced aperiodic responsiveness in hard real-time environments. In Proceedings of the Real-Time Systems Symposium. 1987,1(3): 261-270
[21] B.Sprunt, J.Lehoczky, L.Sha. Exploiting unused periodic time for aperiodic service using the extended priority exchange algorithm. In Real-Time Systems Symposium. Huntsville, Alabama, USA, 1988,251-258
[22] Sha, L., Lehoczky, J. P., and Rajkumar, R. Solutions for some practical problems in prioritizing preemptive scheduling. In Proceedings of the 7th IEEE Real-Time Sytems Symposium, 1986,181-191
[23] Sprunt B. Aperiodic task scheduling for real-time systems. Ph.D. Thesis. Carnegie Mellon University, 1990
[24] Strosnider, J., Lehoczky, J. P., and Sha, L. The deferrable server algorithm for enhanced aperiodic responsiveness in real-time environments. IEEE Transactions on Computers, 1995,44(1): 73-91.
[25] Sprunt, B., Sha, L., and Lehoczky, L. Aperiodic task scheduling for hard real-time systems. Real-Time Systems, 1989,1(1): 27- 60.
[26] PASC. Portable Operating System Interface for Computer Environments (POSIX): Additional Realtime Extensions. 1003.1d, USA, 1999,155-158
[27] Information technology Portable Operating System Interface (POSIX)Part 2: System In. IEEE Portable Applications Standards Committee. 2003. ISO/IEC 9945-2: 2003(E)
[28] B.Sprunt, L.Sha, J.Lehocsky. Aperiodic Task Scheduling for Hard Real-Time Systems. The Journal of Real-Time Systems, 1989, 27-60
[29] Guillem Bernat, Alan Burns. Multiple Servers and Capacity Sharing for Implementing Flexible Scheduling. Real-Time Systems, 2002, 221(2): 49-75
[30] M. Caccamo, G. Lipari, and G. Buttazzo. Sharing Resources among Periodic and Aperiodic Tasks With Dynamic Deadlines. Proc. of the IEEE Real-Time In Systems Symposium. Phoenix, Arizona, 1999,284 293
[31] Lehoczky, J. P., and Thuel, S. R. An optimal algorithm for scheduling soft-aperiodic tasks in fixed-priority preemptive systems. In Proceedings of the 13th IEEE Real-Time Systems Symposium. Phoenix, AZ, USA, 1992,110-123.
[32] Ramos-Thuel, S., and Lehoczky, J. P. On-line scheduling of hard deadline aperiodic tasks in fixed-priority systems. In Proceedings of the 14th IEEE Real-Time Systems Symposium, 1993,160-171.
[33] Ramos-Thuel, S., and Lehoczky, J. P. Algorithms for scheduling hard aperiodic tasks in fixed priority systems using slack stealing. In Proceedings of the 15th IEEE Real-Time Systems Symposium. San Juan, Puerto Rico, 1994,22-35.
[34] T.S. Tia, J.W.S. Liu, M. Shankar. Algorithms and Optimality of Scheduling Aperiodic Requests in Fixed-Priority Preemptive Systems. The Journal of Real-Time Systems, 1995,10(1): 23-43
[35] G.C.Buttazzo, F.Sensini. Optimal Deadline Assignment for Scheduling Soft Aperiodic Tasks in Hard Real-Time Environments. IEEE Transactions on Computers, 1999.10,48(10):1035-1052
[36] I Ripoll, A Crespo, A Garcia, Fornes. An optimal algorithm for scheduling soft aperiodic tasks in dynamic priority preemptive systems. IEEE Trans on Software Engineering, 1997,23(6): 388-400
[37] J.Lehoczky, L.Sha, Y.Ding. The rate monotonic scheduling algorithm: exact characterization and average case behavior. In Real Time Systems Symposium. Santa Monica, California, USA, 1989, 166-171
[38] GC.Buttazzo, F.Sensini. Optimal Deadline Assignment for Scheduling Soft Aperiodic Tasks in Hard Real-Time Environments. IEEE Transactions on Computers, 1999.10,48(10): 1035-1052
[39] Ripoll, A.Crespo, A.Garcia-Fornes. An optimal algorithm for scheduling soft aperiodic tasks in dynamic-priority preemptive systems.IEEE Transactions on Software Engineering,1997.7,23(6):388-400
[40]M.Spuri,G.C.Buttazzo.Efficient aperiodic service under earliest deadline scheduling.In Real-Time Systems Symposium.San Juan,Puerto Rico,1994,2-11
[41]M.Spuri,G.C.Buttazzo.Scheduling Aperiodic Tasks in Dynamic Priority Systems.The Journal of Real-Time Systems,1996,10(2):3-8
[42]H.Chetto,M.Chetto.Some Results of the Earliest Deadline Scheduling Algorithm.IEEE Transactions on Software Engineering,1989.10,15(10):1261-1269
[43]Jingquan Li,Fei-Yue Wang.An Adaptive Algorithm for Processing both Periodic and Aperiodic Messages in Intelligent Home Gateway.In Proceedings of the 2001 IEEE International Conference on Systems.Man&Cybernetics,Tucson,Arizona,2001.10,126-134
[44]Lehoczky J P,Thuel S R.An optimal algorithm for scheduling soft-aperiodic tasks in fixed-priority preemptive systems.In Proceedings of IEEE Real-Time System Symposium,December 1992,110-123
[45]何军,孙玉方.提高软非周期任务相应性能的调度算法.软件学报,1998,9(10):721-727
[46]涂刚,阳富明,卢炎生.基于动态优先级策略的最优软非周期任务调度算法.计算机研究与发展,2004,41(21):2026-2034
[47]Chetto H,Chetto M.Some results of the earliest deadline scheduling algorithm.IEEE Trans.on software engineering,1989,15(10):1261-1269
[48]Spuri,M.,and Buttazzo,G.1994.Efficient aperiodic service under the earliest deadline scheduling.In Proceedings of the IEEE Real-Time Systems Symposium.
[49]Spuri,M.,and Buttazzo,G.Scheduling aperiodic tasks in dynamic priority systems.Real-Time Systems,1996,10(2):179-210.
[50]Buttazzo,G.,and Sensini,F.Optimal deadline assignment for scheduling soft aperiodic tasks in hard real-time environments.IEEE Transactions on Computers, 1999,48(10): 1035-1052.
[51] Ghazalie, T. M., and Baker, T. P. Aperiodic servers in a deadline scheduling environment. Real-Time Systems, 1995,9: 31-67
[52] Abeni, L., and Buttazzo, G. Integrating multimedia applications in hard real-time systems. In Proceedings of the 19th IEEE Real-Time Systems Symposium. Madrid, Spain, 1998.
[53] Abeni, L., and Buttazzo, G. Resource reservations in dynamic real-time systems. Real-Time Systems, 2004,27(2): 123-165
[54] L.Sha, L.R.Rajkumar, J.P.Lehoczky. Priority inheritance protocols: An approach to real-time synchronization. IEEE Transactions on Computers, 1990,39(9): 1175-1185
[55] Baker, T. P., and Pazy, O. Real-time features for Ada 9X. In Proceedings of the 12th IEEE Real-Time Systems Symposium, 1991,172-180.
[56] Sha, L., and Goodenough, J. Real-time scheduling theory and Ada. IEEE Computer, 1990,23(4): 53-62.
[57] Sha, L., Rajkumar, R., and Lehoczky, J. P. Priority inheritance protocols: an approach to real-time synchronization. IEEE Transactions on Computers, 1990, 39(9): 1175-1185.
[58] Sha, L., Rajkumar, R., Son, S., and Chang, C.-H. A real-time locking protocol. IEEE Transactions on Computers, 1991,40(7): 793-800.
[59] Rajkumar, R., Sha, L., and Lehoczky, J. P. Real-time synchronization protocols for shared memory multiprocessors. In Proceedings of the 10th International Conference on Distributed Computing, 1990,116-125.
[60] Rajkumar, R., Sha, L., Lehoczky, J. P., and Ramamritham, K. An optimal priority inheritance policy for synchronization in real-time systems. In S. H. Son, (ed.), Advances in Real-Time Systems. Englewood Cliffs, NJ: Prentice-Hall, 1994, 249-271.
[61]Rajkumar,R.,Sha,L.,and Lehoczky,J.P.Real-time synchronization protocols for multiprocessors.In Proceedings of the 9th IEEE Real-Time Systems Symposium,1988,259-269.
[62]Chen,M.,and Lin,K.Dynamic priority ceilings:A concurrency control protocol for real-time systems.Real-Time Systems 2,1990.
[63]Jeffay,K.Scheduling sporadic tasks with shared resources in hard-real-time systems.In Proceedings of the 13th IEEE Real-Time Systems Symposium.Phoenix,AZ,USA,1992,89-99.
[64]Stankovic,J.A.,Ramamritham,K.,Spuri,M.,and Buttazzo,G.Deadline scheduling for real-time systems.Boston-Dordrecht-London:Kluwer,1998.
[65]Baker,T.P.Stack-based scheduling of real-time processes.Real-Time Systems,1991,3(1):67-100.
[66]张拥军,张怡,彭宇行,陈福接.一种基于多处理机的容错实时任务调度算法.计算机研究与发展,2000,37(4)
[67]刘怀,费树岷.基于EDF的分布式控制系统容错调度算法.软件学报,2003,14(8)
[2]Kieckhafer RM,Walter CJ,Finn AM et al.The MAFT architecture for distributed fault_tolerance.IEEE Transactions on Computers,1988,37(4):398-405
[3]庞丽萍.操作系统原理(第三版).华中科技大学出版社,2000,110-150
[4]Kartik,Gopalan.Real-Time Support in General Purpose Operating Systems.Tech Report.Experimental Computer Systems Labs,Computer Science Dept,Stony Brook University,2001,63-71
[5]Damir Isovic.Handling Sporadic Tasks in Real-time Systems-Combined Offline and Online Approach.Licentiate Thesis,Mardalen University Press,2001.
[6]Damir Isovic,Gerhard Fohler.Efficient Scheduling of Sporadic,Aperiodic,and Periodic Tasks with Complex Constraints.In Proc.of the 21st IEEE Real-Time Systems Symposium.Walt Disney World,Orlando,Florida,USA,2000,1153-1161
[7]Liu CL,Layland JW.Scheduling algorithms for multiprogramming in a hard-real-time environment.Journal of ACM,1973,20(1):174-189
[8]G.Bernat,A.Burns.Specification and Analysis of Weakly Hard Real-Time Systems.PhD thesis.Department de Ciencies Matematiques Informatica,Universitat de les Illes Balears,Spain,1998
[9]G.Bernat,A.Burns.Combining(n,m)-hard deadlines with dual priority scheduling.In Proc.18th IEEE Real-Time Systems Symposium.San Francisco USA,1997,46-57
[10]M.Hamdaoui,P.Ramanathan.A dynamic priority assignment technique for streams with (m,k)-firm deadlines. IEEE Transactions on Computers, 1995, 44(12): 1443-1451
[11] Shanwei Cen, Calton Pu, Richard Staehli. A Distributed Real-Time MPEG Video Audio Player. In Fifth International Workshop on Network and Operating System Support of Digital Audio and Video (NOSSDAV'95). Durham, New Hampshire, USA, 1995,18(21):142-153
[12] David K.Y.Yau, Simon S.Lam. Adaptive Rate-Controlled Scheduling for Multimedia Applications. IEEE/ACM Transactions on Networking, 1997, 5(4):475-488
[13] Jason Nieh, Monica S.Lam. Integrated Processor Scheduling for Multimedia. In Proceedings of the Fifth International Workshop on Network and Operating System Support for Digital Audio and Video. Durham, NH, 1995, 215-218
[14] Katcher DI, Arakawa H, Strosnider JK. Engineering and analysis of fixed priority schedulers. IEEE Trans. on Software Engineering, 1993,19(9):920-934
[15] J.A. Stankovic, M. Spuri, K. Ramamritham, G. Buttazzo. Deadline Scheduling for Real-Time System:EDF and Related Algorithms. Kluwer Academic, 1998
[16] Raj Rajkumar, Kanaka Juvva, Anastasio Molano. Resource Kernels: A Resource-Centric Approach to Real-Time Systems. In Proceedings of the SPIE/ACM Conference on Multimedia Computing and Networking. San Jose, CA, USA, 1998.1,1233-1237
[17] J.Blazewiez. Deadline Scheduling of Tasks - A Survey. Foundation Contr. Eng, 1977,203-216
[18] Dertouzos, M. L. Control robotics: The procedural control of physical processes. Information Processing, 1974,74
[19] Mok, A. K. Fundamental Design Problems of Distributed Systems for the Hard Real-Time Environment. Ph.D. Thesis, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, Cambridge, MA, 1983.
[20] Lehoczky, J.P.Sha, L.Strosnider. Enhanced aperiodic responsiveness in hard real-time environments. In Proceedings of the Real-Time Systems Symposium. 1987,1(3): 261-270
[21] B.Sprunt, J.Lehoczky, L.Sha. Exploiting unused periodic time for aperiodic service using the extended priority exchange algorithm. In Real-Time Systems Symposium. Huntsville, Alabama, USA, 1988,251-258
[22] Sha, L., Lehoczky, J. P., and Rajkumar, R. Solutions for some practical problems in prioritizing preemptive scheduling. In Proceedings of the 7th IEEE Real-Time Sytems Symposium, 1986,181-191
[23] Sprunt B. Aperiodic task scheduling for real-time systems. Ph.D. Thesis. Carnegie Mellon University, 1990
[24] Strosnider, J., Lehoczky, J. P., and Sha, L. The deferrable server algorithm for enhanced aperiodic responsiveness in real-time environments. IEEE Transactions on Computers, 1995,44(1): 73-91.
[25] Sprunt, B., Sha, L., and Lehoczky, L. Aperiodic task scheduling for hard real-time systems. Real-Time Systems, 1989,1(1): 27- 60.
[26] PASC. Portable Operating System Interface for Computer Environments (POSIX): Additional Realtime Extensions. 1003.1d, USA, 1999,155-158
[27] Information technology Portable Operating System Interface (POSIX)Part 2: System In. IEEE Portable Applications Standards Committee. 2003. ISO/IEC 9945-2: 2003(E)
[28] B.Sprunt, L.Sha, J.Lehocsky. Aperiodic Task Scheduling for Hard Real-Time Systems. The Journal of Real-Time Systems, 1989, 27-60
[29] Guillem Bernat, Alan Burns. Multiple Servers and Capacity Sharing for Implementing Flexible Scheduling. Real-Time Systems, 2002, 221(2): 49-75
[30] M. Caccamo, G. Lipari, and G. Buttazzo. Sharing Resources among Periodic and Aperiodic Tasks With Dynamic Deadlines. Proc. of the IEEE Real-Time In Systems Symposium. Phoenix, Arizona, 1999,284 293
[31] Lehoczky, J. P., and Thuel, S. R. An optimal algorithm for scheduling soft-aperiodic tasks in fixed-priority preemptive systems. In Proceedings of the 13th IEEE Real-Time Systems Symposium. Phoenix, AZ, USA, 1992,110-123.
[32] Ramos-Thuel, S., and Lehoczky, J. P. On-line scheduling of hard deadline aperiodic tasks in fixed-priority systems. In Proceedings of the 14th IEEE Real-Time Systems Symposium, 1993,160-171.
[33] Ramos-Thuel, S., and Lehoczky, J. P. Algorithms for scheduling hard aperiodic tasks in fixed priority systems using slack stealing. In Proceedings of the 15th IEEE Real-Time Systems Symposium. San Juan, Puerto Rico, 1994,22-35.
[34] T.S. Tia, J.W.S. Liu, M. Shankar. Algorithms and Optimality of Scheduling Aperiodic Requests in Fixed-Priority Preemptive Systems. The Journal of Real-Time Systems, 1995,10(1): 23-43
[35] G.C.Buttazzo, F.Sensini. Optimal Deadline Assignment for Scheduling Soft Aperiodic Tasks in Hard Real-Time Environments. IEEE Transactions on Computers, 1999.10,48(10):1035-1052
[36] I Ripoll, A Crespo, A Garcia, Fornes. An optimal algorithm for scheduling soft aperiodic tasks in dynamic priority preemptive systems. IEEE Trans on Software Engineering, 1997,23(6): 388-400
[37] J.Lehoczky, L.Sha, Y.Ding. The rate monotonic scheduling algorithm: exact characterization and average case behavior. In Real Time Systems Symposium. Santa Monica, California, USA, 1989, 166-171
[38] GC.Buttazzo, F.Sensini. Optimal Deadline Assignment for Scheduling Soft Aperiodic Tasks in Hard Real-Time Environments. IEEE Transactions on Computers, 1999.10,48(10): 1035-1052
[39] Ripoll, A.Crespo, A.Garcia-Fornes. An optimal algorithm for scheduling soft aperiodic tasks in dynamic-priority preemptive systems.IEEE Transactions on Software Engineering,1997.7,23(6):388-400
[40]M.Spuri,G.C.Buttazzo.Efficient aperiodic service under earliest deadline scheduling.In Real-Time Systems Symposium.San Juan,Puerto Rico,1994,2-11
[41]M.Spuri,G.C.Buttazzo.Scheduling Aperiodic Tasks in Dynamic Priority Systems.The Journal of Real-Time Systems,1996,10(2):3-8
[42]H.Chetto,M.Chetto.Some Results of the Earliest Deadline Scheduling Algorithm.IEEE Transactions on Software Engineering,1989.10,15(10):1261-1269
[43]Jingquan Li,Fei-Yue Wang.An Adaptive Algorithm for Processing both Periodic and Aperiodic Messages in Intelligent Home Gateway.In Proceedings of the 2001 IEEE International Conference on Systems.Man&Cybernetics,Tucson,Arizona,2001.10,126-134
[44]Lehoczky J P,Thuel S R.An optimal algorithm for scheduling soft-aperiodic tasks in fixed-priority preemptive systems.In Proceedings of IEEE Real-Time System Symposium,December 1992,110-123
[45]何军,孙玉方.提高软非周期任务相应性能的调度算法.软件学报,1998,9(10):721-727
[46]涂刚,阳富明,卢炎生.基于动态优先级策略的最优软非周期任务调度算法.计算机研究与发展,2004,41(21):2026-2034
[47]Chetto H,Chetto M.Some results of the earliest deadline scheduling algorithm.IEEE Trans.on software engineering,1989,15(10):1261-1269
[48]Spuri,M.,and Buttazzo,G.1994.Efficient aperiodic service under the earliest deadline scheduling.In Proceedings of the IEEE Real-Time Systems Symposium.
[49]Spuri,M.,and Buttazzo,G.Scheduling aperiodic tasks in dynamic priority systems.Real-Time Systems,1996,10(2):179-210.
[50]Buttazzo,G.,and Sensini,F.Optimal deadline assignment for scheduling soft aperiodic tasks in hard real-time environments.IEEE Transactions on Computers, 1999,48(10): 1035-1052.
[51] Ghazalie, T. M., and Baker, T. P. Aperiodic servers in a deadline scheduling environment. Real-Time Systems, 1995,9: 31-67
[52] Abeni, L., and Buttazzo, G. Integrating multimedia applications in hard real-time systems. In Proceedings of the 19th IEEE Real-Time Systems Symposium. Madrid, Spain, 1998.
[53] Abeni, L., and Buttazzo, G. Resource reservations in dynamic real-time systems. Real-Time Systems, 2004,27(2): 123-165
[54] L.Sha, L.R.Rajkumar, J.P.Lehoczky. Priority inheritance protocols: An approach to real-time synchronization. IEEE Transactions on Computers, 1990,39(9): 1175-1185
[55] Baker, T. P., and Pazy, O. Real-time features for Ada 9X. In Proceedings of the 12th IEEE Real-Time Systems Symposium, 1991,172-180.
[56] Sha, L., and Goodenough, J. Real-time scheduling theory and Ada. IEEE Computer, 1990,23(4): 53-62.
[57] Sha, L., Rajkumar, R., and Lehoczky, J. P. Priority inheritance protocols: an approach to real-time synchronization. IEEE Transactions on Computers, 1990, 39(9): 1175-1185.
[58] Sha, L., Rajkumar, R., Son, S., and Chang, C.-H. A real-time locking protocol. IEEE Transactions on Computers, 1991,40(7): 793-800.
[59] Rajkumar, R., Sha, L., and Lehoczky, J. P. Real-time synchronization protocols for shared memory multiprocessors. In Proceedings of the 10th International Conference on Distributed Computing, 1990,116-125.
[60] Rajkumar, R., Sha, L., Lehoczky, J. P., and Ramamritham, K. An optimal priority inheritance policy for synchronization in real-time systems. In S. H. Son, (ed.), Advances in Real-Time Systems. Englewood Cliffs, NJ: Prentice-Hall, 1994, 249-271.
[61]Rajkumar,R.,Sha,L.,and Lehoczky,J.P.Real-time synchronization protocols for multiprocessors.In Proceedings of the 9th IEEE Real-Time Systems Symposium,1988,259-269.
[62]Chen,M.,and Lin,K.Dynamic priority ceilings:A concurrency control protocol for real-time systems.Real-Time Systems 2,1990.
[63]Jeffay,K.Scheduling sporadic tasks with shared resources in hard-real-time systems.In Proceedings of the 13th IEEE Real-Time Systems Symposium.Phoenix,AZ,USA,1992,89-99.
[64]Stankovic,J.A.,Ramamritham,K.,Spuri,M.,and Buttazzo,G.Deadline scheduling for real-time systems.Boston-Dordrecht-London:Kluwer,1998.
[65]Baker,T.P.Stack-based scheduling of real-time processes.Real-Time Systems,1991,3(1):67-100.
[66]张拥军,张怡,彭宇行,陈福接.一种基于多处理机的容错实时任务调度算法.计算机研究与发展,2000,37(4)
[67]刘怀,费树岷.基于EDF的分布式控制系统容错调度算法.软件学报,2003,14(8)