Competitive Analysis of Static-Priority Partitioned Scheduling on Uniform Multiprocessors
Ref: HURRAY-TR-070802 Publication Date: 21 to 24, Aug, 2007
Competitive Analysis of Static-Priority Partitioned Scheduling on Uniform Multiprocessors
Ref: HURRAY-TR-070802 Publication Date: 21 to 24, Aug, 2007Abstract:
Consider the problem of scheduling a set of sporadically arriving tasks on a uniform multiprocessor with the goal of meeting deadlines. A processor p has the speed Sp. Tasks can be preempted but they cannot migrate between processors. On
each processor, tasks are scheduled with rate-monotonic. We propose an algorithm which can schedule all task sets that any other possible algorithm can schedule assuming that our algorithm is given processors that are √2/(√2−1) ≈ 3.41 times faster. No such guarantees are previously known for partitioned static-priority scheduling on uniform multiprocessors.
Björn Andersson
Eduardo TovarDocument:
View
Download13th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA'07), IEEE, pp 111-119.
Daegu, South Korea.
DOI:10.1109/RTCSA.2007.31.
WOS ID: 000250109000014.
Notes:
Record Date: 21, Aug, 2007
Short links for this page: www.cister.isep.pt/docs/10_1109_rtcsa_2007_31 www.cister.isep.pt/docs/000250109000014 www.cister.isep.pt/docs/hurray_tr_070802 www.cister.isep.pt/docs/329