Utilization Bounds for Multiprocessor Rate-Monotonic Scheduling |
| |
Authors: | López J M García M Díaz J L García D F |
| |
Affiliation: | (1) Departamento de Informática, Universidad de Oviedo, Gijón, 33204, Spain |
| |
Abstract: | In this paper, we extend Liu and Layland's utilization bound for fixed priority scheduling on uniprocessors to homogeneous multiprocessor systems under a partitioning strategy. Assuming that tasks are pre-emptively scheduled on each processor according to fixed priorities assigned by the Rate-Monotonic policy, and allocated to processors by the First Fit algorithm, we prove that the utilization bound is (n–1)(21/2–1)+(m–n+1)(21/(m–n+1)–1), where m and n are the number of tasks and processors, respectively. This bound is valid for arbitrary utilization factors. Moreover, if all the tasks have utilization factors under a value , the previous bound is raised and the new utilization bound considering is calculated. Finally, simulation provides the average-case behavior. |
| |
Keywords: | hard real-time multiprocessor scheduling partitioning rate monotonic scheduling utilization bound |
本文献已被 SpringerLink 等数据库收录! |
|