A faster exact multiprocessor schedulability test for sporadic tasks

Details A faster exact multiprocessor schedulability test for sporadic tasks A faster exact multiprocessor schedulability test for sporadic tasks

2011-05-25

arxiv.org/abs/1105.5055v2

Computer Science

Operating Systems

10 pages

Scientific paper

Baker and Cirinei introduced an exact but naive algorithm, based on solving a state reachability problem in a finite automaton, to check whether sets of sporadic hard real-time tasks are schedulable on identical multiprocessor platforms. However, the algorithm suffered from poor performance due to the exponential size of the automaton relative to the size of the task set. In this paper, we successfully apply techniques developed by the formal verification community, specifically antichain algorithms, by defining and proving the correctness of a simulation relation on Baker and Cirinei's automaton. We show our improved algorithm yields dramatically improved performance for the schedulability test and opens for many further improvements.

Affiliated with

Also associated with

No associations

Rating

A faster exact multiprocessor schedulability test for sporadic tasks does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A faster exact multiprocessor schedulability test for sporadic tasks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A faster exact multiprocessor schedulability test for sporadic tasks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-191745