多处理器全局FP调度算法的研究
|
摘要
实时系统与人们的生活联系越来越密切,它被广泛应用于工业控制,网络传输,多媒体处理,以及军事等领域。对实时系统的研究最初围绕单处理器平台进行；随着多处理器技术的诞生,以及多处理器应用的广泛,多处理器平台受到越来越多的关注；然而,单处理器平台上得到的结果无法简单地扩展到多处理器平台,因此有必要对多处理器平台的情形进行研究。可调度性判定理论是实时系统高可靠性的理论保障,它确保满足可调度性条件的任务集不错过任何的截止期。可调度性判定一直是实时系统研究的热点问题,在本文中,我们对多处理器平台中,使用全局FP(Fixed Priority)调度算法调度实时周期任务的可调度性判定问题进行了研究,并且分别对截止期受限与任意截止期任务集的情况进行了研究。
首先,研究了全局RM调度截止期受限的周期任务的情形,基于Bertogna等的全局FP调度截止期受限的周期任务的可调度性判定思想对这个问题进一步进行了研究,证明当系统中最高优先级任务数量不多于处理器数量时,使用Bertogna等给出的最坏情况来计算任务受到最高优先级任务的干涉上界将过于悲观。通过分析RM调度的最高优先级周期任务的特征,得到了任务受到的最高优先级任务干涉的更小上界,由此得到了一个更紧的全局RM调度周期任务的可调度性判定条件
接着,研究了全局RM调度任意截止期周期任务的情形,基于Baruah等的全局DM调度任意截止期偶发任务的思想,以及Baker的EDF调度任意截止期偶发任务的分析方法,从任意截止期周期任务错过截止期的角度出发,通过分析RM调度的活动任务的特征,得到了任意截止期周期任务集错过截止期的必要条件,只要周期任务集不满足这个错过截止期的必要条件,就能保证任意截止期周期任务集是可调度的。
最后,设计并实现了一个任务集可调度性测试的平台；基于这个实验平台,我们使用多组数据(测试方式,处理器数量,以及任务平均利用率),对我们改进的RM测试与Bertogna等的FP测试进行了测试,得到的结果表明,我们改进的RM测试比Bertogna等的FP测试检测到更多的可调度任务集。
Real-time systems and people's lives becoming closer and closer, it is widely used in industrial control, network transmission, multimedia processing, and military and other fields. Initially people focus on real-time system of single-processor platform, an important reason for the high cost of the processor. With the emergence of the technology that integrate multiple processors on a single chip, more and more multi-processor applications is becoming popular; However, the theory that run correctly on a single processor platform can not simply be extended to multi-processor platform, so it is necessary to study the situation of multi-processor platform. Determine the schedulability of real-time systems reliability theory is the key theory of security, it ensures that any task set which meet the schedulability conditions will not miss their deadline. In this paper, we study the problem how to determine the schedulability of periodic task on real-time multi-processor platform.
First, based on the Bertogna etc's thought to address the schedulability problem of periodic task with deadline-constrained scheduled by the global FP, further studies was made, we demonstrate that when the amount of the highest priority task was not more than the number of processors in the system, using the worst-case presented by Bertogna to compute the interference of the task with highest priority is too pessimistic,by analyzing characteristics of the highest priority periodic task scheduled by FP, a smaller upper bound of interference suffered from highest priority task was attained; then a tighter schedulability condition in which period task was scheduled with RM was attained.
Then, based on the Baruah etc's thought of schedulability determination for arbitrary deadline sporadic task scheduled by DM, and the Baker's thought of schedulability determination for arbitrary deadline sporadic task scheduled by EDF, the schedulability problem of periodic task with arbitrary deadline scheduled by RM was studied. From the point of task missing deadline, analyzing the characteristics of active tasks, the necessary condition in which periodic task with arbitrary deadline must miss its deadline was attained. As long as the task set do not meet this necessary condition, we can guarantee arbitrary deadline periodic task set is schedulable.
Finally, we design and implement the multi-processor platform, with which schedulability of deadline constrained periodic task set scheduled by RM could be compared; based on this experimental platform, we are using multiple sets of data (test mode, the number of processors, and the average task efficiency) to compare our improved test and FP test put forward by Bertogna etc, the results show that ours improved RM test detected more scheduled tasks set than Bertogna etc's test.
首先,研究了全局RM调度截止期受限的周期任务的情形,基于Bertogna等的全局FP调度截止期受限的周期任务的可调度性判定思想对这个问题进一步进行了研究,证明当系统中最高优先级任务数量不多于处理器数量时,使用Bertogna等给出的最坏情况来计算任务受到最高优先级任务的干涉上界将过于悲观。通过分析RM调度的最高优先级周期任务的特征,得到了任务受到的最高优先级任务干涉的更小上界,由此得到了一个更紧的全局RM调度周期任务的可调度性判定条件
接着,研究了全局RM调度任意截止期周期任务的情形,基于Baruah等的全局DM调度任意截止期偶发任务的思想,以及Baker的EDF调度任意截止期偶发任务的分析方法,从任意截止期周期任务错过截止期的角度出发,通过分析RM调度的活动任务的特征,得到了任意截止期周期任务集错过截止期的必要条件,只要周期任务集不满足这个错过截止期的必要条件,就能保证任意截止期周期任务集是可调度的。
最后,设计并实现了一个任务集可调度性测试的平台；基于这个实验平台,我们使用多组数据(测试方式,处理器数量,以及任务平均利用率),对我们改进的RM测试与Bertogna等的FP测试进行了测试,得到的结果表明,我们改进的RM测试比Bertogna等的FP测试检测到更多的可调度任务集。
Real-time systems and people's lives becoming closer and closer, it is widely used in industrial control, network transmission, multimedia processing, and military and other fields. Initially people focus on real-time system of single-processor platform, an important reason for the high cost of the processor. With the emergence of the technology that integrate multiple processors on a single chip, more and more multi-processor applications is becoming popular; However, the theory that run correctly on a single processor platform can not simply be extended to multi-processor platform, so it is necessary to study the situation of multi-processor platform. Determine the schedulability of real-time systems reliability theory is the key theory of security, it ensures that any task set which meet the schedulability conditions will not miss their deadline. In this paper, we study the problem how to determine the schedulability of periodic task on real-time multi-processor platform.
First, based on the Bertogna etc's thought to address the schedulability problem of periodic task with deadline-constrained scheduled by the global FP, further studies was made, we demonstrate that when the amount of the highest priority task was not more than the number of processors in the system, using the worst-case presented by Bertogna to compute the interference of the task with highest priority is too pessimistic,by analyzing characteristics of the highest priority periodic task scheduled by FP, a smaller upper bound of interference suffered from highest priority task was attained; then a tighter schedulability condition in which period task was scheduled with RM was attained.
Then, based on the Baruah etc's thought of schedulability determination for arbitrary deadline sporadic task scheduled by DM, and the Baker's thought of schedulability determination for arbitrary deadline sporadic task scheduled by EDF, the schedulability problem of periodic task with arbitrary deadline scheduled by RM was studied. From the point of task missing deadline, analyzing the characteristics of active tasks, the necessary condition in which periodic task with arbitrary deadline must miss its deadline was attained. As long as the task set do not meet this necessary condition, we can guarantee arbitrary deadline periodic task set is schedulable.
Finally, we design and implement the multi-processor platform, with which schedulability of deadline constrained periodic task set scheduled by RM could be compared; based on this experimental platform, we are using multiple sets of data (test mode, the number of processors, and the average task efficiency) to compare our improved test and FP test put forward by Bertogna etc, the results show that ours improved RM test detected more scheduled tasks set than Bertogna etc's test.
引文
[1]C. L. Liu, and J. W. Layland. Scheduling algorithms for multi-programming in a hard real-time environment[J]. Journal of the Association for Computing Machinery,1973.1,20(1): 46-61
[2]Jane W S.Liu(著),姬孟洛,李军,王馨,路现立,秦杰(译).实时系统[M].北京：高等教育出版社,2003.12
[3]S.K.Dhall, C.L.Liu, On a real-time scheduling problem. Operations Research,1978,26(1): 127-140
[4]J P Lehoczky, L Sha, and Y Ding. The rate monotonic scheduling algorithm:Exact characterization and average case behavior[C]. In Proceedings of 10th IEEE Real-Time Systems Sysposium,1989:166-171
[5]Han CC,Lin KJ,Hou CJ.Distance-Constrained scheduling and its anplcations to real-time systems[J].IEEE Trans.on Computers,1996,45(7):814～826
[6]Han CC,Tyan H.A better polynomial-time schedulability test for real-time fixed-priority scheduling algorithms[C].In:Proc.of the 18th IEEE Real-Time Systems Symp.San Francisco:IEEE Computer Society Press,1997.36～45
[7]J.Y-T Leung and J Whitehead. On the complexity of fixed-priority scheduling of periodic real-time tasks[J]. Performances Evaluation,1982,2:237-250
[8]K Jeffay, D.F Stanat, and C.U Martel. On non-preemptive scheduling of periodic and sporadic task[C]. In Proceedings of IEEE real-time systems sysposium,1991:129-139
[9]J P Lehoczky,L Sha,J K Stronsnider. Enhanced aperiodic responsiveness in hard real-time environments[C]. In:Proc of the 8th IEEE Real-Time System Symposium San Jose, California:IEEE Computer Society Press,1987:210～217
[10]B Sprunt,L Sha,J P Lehoczky. Aperiodic task scheduling for hard real-time systems[J]. Journal of Real-Time Systems,1989,1(1):27～60
[11]Jay K Strosnider,J P Lehoczky,Lui Sha. The deferrable server algorithm for Enhanced aperiodic responsiveness in hard real-time environments[J]. IEEE Transactions on computers, 1995,44(1):73～91
[12]T M Ghazalie,T P Baker. Aperiodic servers in a deadline scheduling environment[J]. Journal of Real-Time Systems,1995,9(1):31-67
[13]M Spuri,G C Buttazzo. Scheduling aperiodic tasks in dynamic priority systems[J]. Journal of Real-Time Systems,1996,10(2):179～210
[14]J P Lehoczky,S Ramos-Thuel. An optimal algorithm for scheduling soft-aperiodic tasks in fixed-priority preemptive systems[C]. In:Proc of the 13th IEEE Real-Time Systems Symposium. Phoenix,Arizona:IEEE Computer Society Press,1992:110～123
[15]T S Tia,J W S Liu,M Shankar. Algorithms and optimality of scheduling aperiodic requests in fixed priority preemptive systems[J]. Journal of Real-Time Systems,1995,10(1):23～43
[16]G C Buttazzo,F Sensini. Optimal deadline assignment for scheduling soft aperiodic tasks in hard real-time enviroments[J], IEEE Trans on computers.1999,48(10):1035-1052
[17]Ismael Ripoll, Alfons Crespo, Ana Garcia-Fornes. An Optimal Algorithm for Scheduling Soft Aperiodic Tasks in Dynamic-Priority Preemptive Systems[J]. IEEE Transactions on Software Engineering,1996,23(6):388-399
[18]M Spuri,G C Buttazzo. Efficient aperiodic service under earliest deadline scheduling[C]. In:Proc of the 15th Real-Time Systems Symposium.1994:2～11
[19]H Chetto,M Chetto. Some results of the earliest deadline scheduling algorithm. IEEE Trans on Software Engineering,1989,15(10):1261～1269
[20]何军,孙玉方.提高软非周期任务相应性能的调度算法[J].软件学报,1998,9(10)：721～727
[21]涂刚,阳富民,卢炎生.基于动态优先级策略的最优软非周期任务调度算法[J].计算机研究与发展,2004,41(11)：2026～2034
[22]王强,王宏安,金宏,戴国忠.实时系统中的非定期任务调度算法综述[J].计算机研究与发展,2004,41(3)：385～391
[23]邢建生,刘军祥,王永吉.RM及其扩展可调度性判定算法性能分析[J].计算机研究与发展,2005,42(11)：2025～2032
[24]王永吉,陈秋萍.单调速率及其扩展算法的可调度性判定[J].软件学报,2004,15(6)：799～814
[25]谢拴勤,牛云,林文.基于RMS调度周期、非周期混合任务集的一种新方法[J].计算机应用研究,2006,8：76～79
[26]Maryline Silly. The EDL Server for Scheduling Periodic and Soft Aperiodic Tasks with Resource Constraints[C]. The International Journal of Time-Critical Computing Systems,1999,17:87～111
[27]Tarek F.Abdelzaher, Vivek Sharma, Chenyang Lu, A Utilization Bound for Aperiodic Tasks and Priority Driven Scheduling[J]. IEEE Transactions on Computers,2004,53(3):334～349
[28]Audrey Marchand,Maryline Silly-Chetto. Dynamic Real-time Scheduling of Firm Periodic Tasks with Hard and Soft Aperiodic Tasks[J]. Real-Time Systems,2006,32:21-47
[29]Giuseppe Lipari, Giorgio Buttazzo. Schedulability analysis of periodic and aperiodic tasks with resource constraints[J]. Journal of Systems Architecture,2000,46:327～338
[30]Damir Isovic. Handling mixed sets of tasks in combined offline and online scheduled real-time systems[J]. Real-Time System,2009,43:296～325
[31]S.K.Baruah,N.K.Cohen,C.G.Plaxton,D.A.Varvel. Proportionate Progress:A Notion of Fairness in Resource Allocation[J]. Algorithmica,1996,15:600-625
[32]C.A.Phillips,C.Stein,E.Torng,J.Wein. Optimal Time-Critical Scheduling via Resource Augmentation[J]. Algorithmica,2002,32:163-200
[33]Sanjoy Baruah,Nathan Fisher. The Partitioned Scheduling of Sporadic real-time Task System on Multiprocessor Platforms[C]. Proceedings of the International Conference on Parallel Processing Workshops,2005,346-353
[34]Sanjoy Baruah,Nathan Fisher.The Partitioned Multiprocessor Scheduling of Deadline-Constrained Sporadic Task Systems[J]. IEEE Transactions on Computers,2006,55(7):918-923
[35]Sanjoy K.Baruah,Nathan Fisher. The partitioned dynamic-priority scheduling of sporadic task systems[J].Real-Time System,2007:199-226
[36]Nathan Fisher,Sanjoy Baruah.The Partitioned Scheduling of Sporadic Tasks According to Static-Priorities[C]. Proceedings-Euromicro Conference on Real-Time Systems. 2006:118-127
[37]Bjorn Andersson,Eduardo Tovar. Competitive Analysis of Partitioned Scheduling on Uniform Multiprocessors[C]. Proceedings-21st International Parallel and Distributed Processing Symposium,2007
[38]Shelby Funk,Joel Goossens,Sanjoy Barual. On-line Scheduling on Uniform Multiprocessors[C]. Proceedings-Real-Time Systems Symposium,2001:183-192
[39]Joel Goossens,Shelby Funk.Sanjoy Baruah. Priority-Driven Scheduling of Periodic Task Systems on Multiprocessors[J]. Real-Time Systems:2003,25:187-205
[40]B.Andersson,S.Baruah,J.Jonsson. Static-priority scheduling on multiprocessors[C]. Proceedings of the IEEE Real-Time Systems Symposium,2003:120-129
[41]Sanjoy K.Baruah, Joel Goossens. Rate-Monotonic Scheduling on Uniform Multiprocessor[J]. IEEE Transactions on Computers:2003,52(7):966-970
[42]Sanjoy K.Baruah. Optimal Utilization Bounds for the Fixed-Priority Scheduling of Periodic Task Systems on Identical Multiprocessors[J]. IEEE transactions on computers: 2004,53(6),781-784
[43]Theodore P.Baker. Multiprocessor EDF and Deadline Monotonic Schedulability Analysis[C]. Proceedings-Real-Time Systems Symposium,2003:120-129
[44]Theodore P.Baker. An Analysis of Fixed-Priority Schedulability on a Multiprocessor[J]. Real-Time Systems:2006.32:49-71
[45]Theodore P.Baker, Michele Cirinei. A unified analysis of global edf and fixed-task-priority schedulability of sporadic task systems on multiprocessors[EB OL]. http:// www.cs.fsu.edu/research/reports/TR-060401.pdf
[46]Theodore P.Baker.Michele Cirinei. A necessary and sometimes sufficient condition for the feasibility of sets of sporadic hard-deadline[C]. Proceedings-Real-Time Systems Symposium,2006:178-187
[47]Marko Bertogna.Michele Cirinei, Giuseppe Lipari. Improved schedulability analysis of EDF on multiprocessor platforms[C]. Proceedings-Euromicro Conference on Real-Time Systems, 2005:209-218
[48]Marko Bertogna,Michele Cirinei, Giuseppe Lipari. An analysis of EDF Schedulability on Multiprocessor Platforms[J]. IEEE Transactions on Parallel and Distributed Systems, 2005,16(8):760-768
[49]Marko Bertogna.Michele Cirinei,Giuseppe Lipari. New schedulability tests for real-time tasks sets scheduled by deadline monotonic on multiprocessors[C]. Proceedings of the 9th International Conference on Principles of Distributed Systems,2005:306-321
[50]Marko Bertogna,Michele Cirinei, Giuseppe Lipari. Schedulability analysis of global scheduling algorithms on multiprocessor platforms[J]. IEEE transactions on parallel and distributed systems:2008,20(4):553-566
[51]Marko Bertogna,Michele Cirinei. Response-Time Analysis for globally scheduled Symmetric Multiprocessor Platforms[C]. Proceedings-Real-Time Systems Symposium,2007:149-158
[52]Nathan Fisher,Sanjoy Baruah. The Global Feasibility and Schedulability of General Task Models on Multiprocessor Platforms[C]. Proceedings-Euromicro Conference on Real-Time Systems,2007:51-60
[53]Liliana Cucu, Joel Goossens. Feasibility Intervals for Fixed-Priority Real-Time Scheduling on Uniform Multiprocessors[C]. IEEE Symposium on Emerging Technologies and Factory Automation,2006:397-404
[54]Michele Cirinei, Theodore P.Baker. EDZL scheduling analysis[J]. Real-Time Systems, 2008,40(3):264-289
[55]Sanjoy Baruah,Joel Goossens.The EDF scheduling of sporadic task systems on uniform multiprocessors[C].Proceedings-Real-Time Systems Symposium.2008:367-374
[56]Sanjoy Baruah,Theodore Baker. Schedulability analysis of global EDF[J]. Real-Time System, 2008,38:223-235
[57]Sanjoy Baruah. The Non-preemptive Scheduling of Periodic Tasks upon Multiprocessors[J]. Real-Time System.2006,32:9-20
[58]Vivek N Darera,Lawrence Jenkins. Utilization Bounds for RM Scheduling on Uniform Multiprocessors[C]. Proceedings-12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications,2006:315-321
[59]Sanjoy Baruah,Nathan Fisher. Global Deadline-Monotonic Scheduling of Arbitrary-Deadline Sporadic Task System[C]. Lecture Notes in Computer Science,2007:204-216
[60]Sanjoy Baruah,Nathan Fisher. Global Fixed-Priority Scheduling of Arbitrary-Deadline Sporadic Task Systems[C]. Lecture Notes in Computer Science,2008:215-226
[61]Sanjoy Baruah, Joel Goossens. Deadline Monotonic Scheduling on Uniform Multiprocessors[C]. Lecture Notes in Computer Science,2008:89-104
[62]Sanjoy Baruah,Theodore Baker. Global EDF schedulability analysis of arbitrary sporadic task systems[C]. Proceedings-Euromicro Conference on Real-Time Systems,2008:3-12
[63]Theodore P.Baker, Sanjoy Baruah.An analysis of global EDF schedulability for arbitrary-deadline sporadic task systems[J].Real-time system:2009,43:3-24
[2]Jane W S.Liu(著),姬孟洛,李军,王馨,路现立,秦杰(译).实时系统[M].北京：高等教育出版社,2003.12
[3]S.K.Dhall, C.L.Liu, On a real-time scheduling problem. Operations Research,1978,26(1): 127-140
[4]J P Lehoczky, L Sha, and Y Ding. The rate monotonic scheduling algorithm:Exact characterization and average case behavior[C]. In Proceedings of 10th IEEE Real-Time Systems Sysposium,1989:166-171
[5]Han CC,Lin KJ,Hou CJ.Distance-Constrained scheduling and its anplcations to real-time systems[J].IEEE Trans.on Computers,1996,45(7):814～826
[6]Han CC,Tyan H.A better polynomial-time schedulability test for real-time fixed-priority scheduling algorithms[C].In:Proc.of the 18th IEEE Real-Time Systems Symp.San Francisco:IEEE Computer Society Press,1997.36～45
[7]J.Y-T Leung and J Whitehead. On the complexity of fixed-priority scheduling of periodic real-time tasks[J]. Performances Evaluation,1982,2:237-250
[8]K Jeffay, D.F Stanat, and C.U Martel. On non-preemptive scheduling of periodic and sporadic task[C]. In Proceedings of IEEE real-time systems sysposium,1991:129-139
[9]J P Lehoczky,L Sha,J K Stronsnider. Enhanced aperiodic responsiveness in hard real-time environments[C]. In:Proc of the 8th IEEE Real-Time System Symposium San Jose, California:IEEE Computer Society Press,1987:210～217
[10]B Sprunt,L Sha,J P Lehoczky. Aperiodic task scheduling for hard real-time systems[J]. Journal of Real-Time Systems,1989,1(1):27～60
[11]Jay K Strosnider,J P Lehoczky,Lui Sha. The deferrable server algorithm for Enhanced aperiodic responsiveness in hard real-time environments[J]. IEEE Transactions on computers, 1995,44(1):73～91
[12]T M Ghazalie,T P Baker. Aperiodic servers in a deadline scheduling environment[J]. Journal of Real-Time Systems,1995,9(1):31-67
[13]M Spuri,G C Buttazzo. Scheduling aperiodic tasks in dynamic priority systems[J]. Journal of Real-Time Systems,1996,10(2):179～210
[14]J P Lehoczky,S Ramos-Thuel. An optimal algorithm for scheduling soft-aperiodic tasks in fixed-priority preemptive systems[C]. In:Proc of the 13th IEEE Real-Time Systems Symposium. Phoenix,Arizona:IEEE Computer Society Press,1992:110～123
[15]T S Tia,J W S Liu,M Shankar. Algorithms and optimality of scheduling aperiodic requests in fixed priority preemptive systems[J]. Journal of Real-Time Systems,1995,10(1):23～43
[16]G C Buttazzo,F Sensini. Optimal deadline assignment for scheduling soft aperiodic tasks in hard real-time enviroments[J], IEEE Trans on computers.1999,48(10):1035-1052
[17]Ismael Ripoll, Alfons Crespo, Ana Garcia-Fornes. An Optimal Algorithm for Scheduling Soft Aperiodic Tasks in Dynamic-Priority Preemptive Systems[J]. IEEE Transactions on Software Engineering,1996,23(6):388-399
[18]M Spuri,G C Buttazzo. Efficient aperiodic service under earliest deadline scheduling[C]. In:Proc of the 15th Real-Time Systems Symposium.1994:2～11
[19]H Chetto,M Chetto. Some results of the earliest deadline scheduling algorithm. IEEE Trans on Software Engineering,1989,15(10):1261～1269
[20]何军,孙玉方.提高软非周期任务相应性能的调度算法[J].软件学报,1998,9(10)：721～727
[21]涂刚,阳富民,卢炎生.基于动态优先级策略的最优软非周期任务调度算法[J].计算机研究与发展,2004,41(11)：2026～2034
[22]王强,王宏安,金宏,戴国忠.实时系统中的非定期任务调度算法综述[J].计算机研究与发展,2004,41(3)：385～391
[23]邢建生,刘军祥,王永吉.RM及其扩展可调度性判定算法性能分析[J].计算机研究与发展,2005,42(11)：2025～2032
[24]王永吉,陈秋萍.单调速率及其扩展算法的可调度性判定[J].软件学报,2004,15(6)：799～814
[25]谢拴勤,牛云,林文.基于RMS调度周期、非周期混合任务集的一种新方法[J].计算机应用研究,2006,8：76～79
[26]Maryline Silly. The EDL Server for Scheduling Periodic and Soft Aperiodic Tasks with Resource Constraints[C]. The International Journal of Time-Critical Computing Systems,1999,17:87～111
[27]Tarek F.Abdelzaher, Vivek Sharma, Chenyang Lu, A Utilization Bound for Aperiodic Tasks and Priority Driven Scheduling[J]. IEEE Transactions on Computers,2004,53(3):334～349
[28]Audrey Marchand,Maryline Silly-Chetto. Dynamic Real-time Scheduling of Firm Periodic Tasks with Hard and Soft Aperiodic Tasks[J]. Real-Time Systems,2006,32:21-47
[29]Giuseppe Lipari, Giorgio Buttazzo. Schedulability analysis of periodic and aperiodic tasks with resource constraints[J]. Journal of Systems Architecture,2000,46:327～338
[30]Damir Isovic. Handling mixed sets of tasks in combined offline and online scheduled real-time systems[J]. Real-Time System,2009,43:296～325
[31]S.K.Baruah,N.K.Cohen,C.G.Plaxton,D.A.Varvel. Proportionate Progress:A Notion of Fairness in Resource Allocation[J]. Algorithmica,1996,15:600-625
[32]C.A.Phillips,C.Stein,E.Torng,J.Wein. Optimal Time-Critical Scheduling via Resource Augmentation[J]. Algorithmica,2002,32:163-200
[33]Sanjoy Baruah,Nathan Fisher. The Partitioned Scheduling of Sporadic real-time Task System on Multiprocessor Platforms[C]. Proceedings of the International Conference on Parallel Processing Workshops,2005,346-353
[34]Sanjoy Baruah,Nathan Fisher.The Partitioned Multiprocessor Scheduling of Deadline-Constrained Sporadic Task Systems[J]. IEEE Transactions on Computers,2006,55(7):918-923
[35]Sanjoy K.Baruah,Nathan Fisher. The partitioned dynamic-priority scheduling of sporadic task systems[J].Real-Time System,2007:199-226
[36]Nathan Fisher,Sanjoy Baruah.The Partitioned Scheduling of Sporadic Tasks According to Static-Priorities[C]. Proceedings-Euromicro Conference on Real-Time Systems. 2006:118-127
[37]Bjorn Andersson,Eduardo Tovar. Competitive Analysis of Partitioned Scheduling on Uniform Multiprocessors[C]. Proceedings-21st International Parallel and Distributed Processing Symposium,2007
[38]Shelby Funk,Joel Goossens,Sanjoy Barual. On-line Scheduling on Uniform Multiprocessors[C]. Proceedings-Real-Time Systems Symposium,2001:183-192
[39]Joel Goossens,Shelby Funk.Sanjoy Baruah. Priority-Driven Scheduling of Periodic Task Systems on Multiprocessors[J]. Real-Time Systems:2003,25:187-205
[40]B.Andersson,S.Baruah,J.Jonsson. Static-priority scheduling on multiprocessors[C]. Proceedings of the IEEE Real-Time Systems Symposium,2003:120-129
[41]Sanjoy K.Baruah, Joel Goossens. Rate-Monotonic Scheduling on Uniform Multiprocessor[J]. IEEE Transactions on Computers:2003,52(7):966-970
[42]Sanjoy K.Baruah. Optimal Utilization Bounds for the Fixed-Priority Scheduling of Periodic Task Systems on Identical Multiprocessors[J]. IEEE transactions on computers: 2004,53(6),781-784
[43]Theodore P.Baker. Multiprocessor EDF and Deadline Monotonic Schedulability Analysis[C]. Proceedings-Real-Time Systems Symposium,2003:120-129
[44]Theodore P.Baker. An Analysis of Fixed-Priority Schedulability on a Multiprocessor[J]. Real-Time Systems:2006.32:49-71
[45]Theodore P.Baker, Michele Cirinei. A unified analysis of global edf and fixed-task-priority schedulability of sporadic task systems on multiprocessors[EB OL]. http:// www.cs.fsu.edu/research/reports/TR-060401.pdf
[46]Theodore P.Baker.Michele Cirinei. A necessary and sometimes sufficient condition for the feasibility of sets of sporadic hard-deadline[C]. Proceedings-Real-Time Systems Symposium,2006:178-187
[47]Marko Bertogna.Michele Cirinei, Giuseppe Lipari. Improved schedulability analysis of EDF on multiprocessor platforms[C]. Proceedings-Euromicro Conference on Real-Time Systems, 2005:209-218
[48]Marko Bertogna,Michele Cirinei, Giuseppe Lipari. An analysis of EDF Schedulability on Multiprocessor Platforms[J]. IEEE Transactions on Parallel and Distributed Systems, 2005,16(8):760-768
[49]Marko Bertogna.Michele Cirinei,Giuseppe Lipari. New schedulability tests for real-time tasks sets scheduled by deadline monotonic on multiprocessors[C]. Proceedings of the 9th International Conference on Principles of Distributed Systems,2005:306-321
[50]Marko Bertogna,Michele Cirinei, Giuseppe Lipari. Schedulability analysis of global scheduling algorithms on multiprocessor platforms[J]. IEEE transactions on parallel and distributed systems:2008,20(4):553-566
[51]Marko Bertogna,Michele Cirinei. Response-Time Analysis for globally scheduled Symmetric Multiprocessor Platforms[C]. Proceedings-Real-Time Systems Symposium,2007:149-158
[52]Nathan Fisher,Sanjoy Baruah. The Global Feasibility and Schedulability of General Task Models on Multiprocessor Platforms[C]. Proceedings-Euromicro Conference on Real-Time Systems,2007:51-60
[53]Liliana Cucu, Joel Goossens. Feasibility Intervals for Fixed-Priority Real-Time Scheduling on Uniform Multiprocessors[C]. IEEE Symposium on Emerging Technologies and Factory Automation,2006:397-404
[54]Michele Cirinei, Theodore P.Baker. EDZL scheduling analysis[J]. Real-Time Systems, 2008,40(3):264-289
[55]Sanjoy Baruah,Joel Goossens.The EDF scheduling of sporadic task systems on uniform multiprocessors[C].Proceedings-Real-Time Systems Symposium.2008:367-374
[56]Sanjoy Baruah,Theodore Baker. Schedulability analysis of global EDF[J]. Real-Time System, 2008,38:223-235
[57]Sanjoy Baruah. The Non-preemptive Scheduling of Periodic Tasks upon Multiprocessors[J]. Real-Time System.2006,32:9-20
[58]Vivek N Darera,Lawrence Jenkins. Utilization Bounds for RM Scheduling on Uniform Multiprocessors[C]. Proceedings-12th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications,2006:315-321
[59]Sanjoy Baruah,Nathan Fisher. Global Deadline-Monotonic Scheduling of Arbitrary-Deadline Sporadic Task System[C]. Lecture Notes in Computer Science,2007:204-216
[60]Sanjoy Baruah,Nathan Fisher. Global Fixed-Priority Scheduling of Arbitrary-Deadline Sporadic Task Systems[C]. Lecture Notes in Computer Science,2008:215-226
[61]Sanjoy Baruah, Joel Goossens. Deadline Monotonic Scheduling on Uniform Multiprocessors[C]. Lecture Notes in Computer Science,2008:89-104
[62]Sanjoy Baruah,Theodore Baker. Global EDF schedulability analysis of arbitrary sporadic task systems[C]. Proceedings-Euromicro Conference on Real-Time Systems,2008:3-12
[63]Theodore P.Baker, Sanjoy Baruah.An analysis of global EDF schedulability for arbitrary-deadline sporadic task systems[J].Real-time system:2009,43:3-24