Fixed-Priority Multiprocessor Scheduling with Liu and Layland's Utilization Bound

Abstract

Liu and Layland discovered the famous utilization bound for fixed-priority scheduling on single processor systems in the 1970's. Since then, it has been a long standing open problem to find fixed-priority scheduling algorithms with the same bound for multiprocessor systems. In this paper, we present a partitioning-based fixed-priority multiprocessor scheduling algorithm with Liu and Layland's utilization bound.