Article Preview
TopA multiprocessor system is tightly coupled so that global status and workload information on all processors can be kept current at a low cost. The system has shared memory and generally uses centralized scheduler. If system uses separate scheduler for each processor, the decisions and actions of the schedulers of all the processors are coherent. Multiprocessor systems are divided in two basic types, homogeneous and heterogeneous. In homogeneous system, processors can be used interchangeably and in contrast, heterogeneous processors cannot be used interchangeably. Homogeneous processors can be subdivided in two types: identical and uniform. In identical processors, it is assumed that all processors are equally powerful whereas uniform multiprocessor machine is characterized by a speed (Baruah, Funk, & Goossens, 2003).
There are two main strategies when dealing with the problem of multiprocessor scheduling: partitioning strategy and global strategy (Oh & Son, 1995). In a partitioning strategy, once a task is allocated to a processor, all of its instances are executed exclusively on that processor. In a global strategy, any instance of a task can be executed on any processor, or even be preempted and moved to a different processor before it is completed (Lopez, Diaz, & Garcia. 2004).
EDF (Earliest Deadline First) and LLF (Least Laxity First) algorithms are proved optimal under the condition that tasks are preemptive, there is only one processor and it is not overloaded (Dertouzos & Ogata, 1974; Mok, 1983). EDF is appropriate algorithm to use for on-line scheduling on uniform multiprocessors (Funk, Goossens, & Baruah, 2001). However, many practical instances of multiprocessor real-time system are NP-complete, i.e. it is believed that there is no optimal polynomial-time algorithm for them (Ramamritham, Stankovik, & Shiah, 1990; Ullman, 1973).