| Name: | Description: | Size: | Format: | |
|---|---|---|---|---|
| 391.7 KB | Adobe PDF |
Advisor(s)
Abstract(s)
Consider the problem of scheduling a set of implicit-deadline sporadic tasks to meet all deadlines on a uniform
multiprocessor platform where each task may access at most one of |R| shared resources and at most once by each job of
that task. The resources have to be accessed in a mutually exclusive manner. We propose an algorithm, GIS-vpr, which
offers the guarantee that if a task set is schedulable to meet deadlines by an optimal task assignment scheme that allows
a task to migrate only when it accesses or releases a resource, then our algorithm also meets the deadlines with the same
restriction on the task migration, if given processors 4 + 6|R| times as fast. The proposed algorithm, by design, limits the
number of migrations per job to at most two. To the best of our knowledge, this is the first result for resource sharing on
uniform multiprocessors with proven performance guarantee.
Description
Keywords
Real-time scheduling Resource sharing Uniform multiprocessors