A Categorization of Realtime Multiprocessor Scheduling Problems and Algorithms
(link)
Most known realtime scheduling algorithms are workconserving:
 At each instant, associate priority with each active job
 Job has arrive prior to instant
 Deadline occurs after instant
 Hasnâ€™t finished
 Highest priority jobs eligible to execute are selected for execution on available processors
Periodic task model
 Tasks are characterized by two parameters
 worstcase execution requirement e
 period p
 implied constraint (i.e., deadline is equal to p)

A collection of periodic tasks is referred to as a periodic task system
 Schedulable: task system is schedulable by an algorithm if that algorithm ensures that the timing constraints of all tasks in the system are met
 Feasible: task system is feasible under a class of scheduling algorithms if the system is schedule by some algorithm in the class

Optimal: an algorithm is optimal with respect to some class if the algorithm is in the class and correctly schedules every task system feasible under the class
 Workconserving: processor never left idle while active job exists unless migration constraints prevent task from executing on the idle processor
Scheduling approaches
 Partitioning: each periodic tasks is assigned to a single processor, on which each of its jobs will execute, reducing multiprocessor scheduling to a set of uniprocessor ones. However
 Optimal assignment of tasks to processors is binpacking problem (NPhard)
 Task systems exist that are schedulable if and only if tasks are not partitioned. Still, partitioning approaches are widely used.
 Global: all eligible tasks are stored in a single priorityordered queue; the global scheduler selects for execution the highest priority tasks from this queue. Unfortunately, optimal uniprocessor algorithms (RM, EDF) may result in arbitrarily low processor utilization in MP systems
 Hybrid: each job assigned to single processor, but task allowed to migrate at job boundaries
Classifying algorithms
 Complexity of priority scheme
 Static (rate monotonic)
 Dynamic, but fixed within a job (earliest deadline first)
 Fully dynamic (leastlaxityfirst)
 Degree of migration allowed
 No migration (task partitioning)
 Migration allowed, but only at job boundaries (dynamic partitioning at the job level)
 Unrestricted migration (jobs can migrate)