A categorization of real-time multiprocessor scheduling problems and algorithms

Abstract

Introduction Real-time multiprocessor systems are now commonplace. Designs range from single-chip architectures, with a modest number of processors, to large-scale signal-processing systems, such as synthetic-aperture radar systems. For uniprocessor systems, the problem of ensuring that deadline constraints are met has been widely studied: e#ective scheduling algorithms that take into account the many complexities that arise in real systems (e.g., synchronization costs, system overheads, etc.) are well understood. In contrast, researchers are just beginning to understand the trade-o#s that exist in multiprocessor systems. In this chapter, we analyze the trade-o#s involved in scheduling independent, periodic real-time tasks on a multiprocessor. Research on real-time scheduling has largely focused on the problem of scheduling of recurring processes, or tasks. The periodic task model of Liu and Layland is the simplest model of a recurring process [16, 17]. In this model, a task T is cha