ACO Based Dynamic Scheduling Algorithm for Real-Time Multiprocessor Systems

ACO Based Dynamic Scheduling Algorithm for Real-Time Multiprocessor Systems

Apurva Shah (G H Patel College of Engg & Tech, India) and Ketan Kotecha (Nirma University, India)
DOI: 10.4018/978-1-4666-2065-0.ch006
OnDemand PDF Download:
No Current Special Offers


The Ant Colony Optimization (ACO) algorithms are computational models inspired by the collective foraging behavior of ants. The ACO algorithms provide inherent parallelism, which is very useful in multiprocessor environments. They provide balance between exploration and exploitation along with robustness and simplicity of individual agent. In this paper, ACO based dynamic scheduling algorithm for homogeneous multiprocessor real-time systems is proposed. The results obtained during simulation are measured in terms of Success Ratio (SR) and Effective CPU Utilization (ECU) and compared with the results of Earliest Deadline First (EDF) algorithm in the same environment. It has been observed that the proposed algorithm is very efficient in underloaded conditions and it performs very well during overloaded conditions also. Moreover, the proposed algorithm can schedule some typical instances successfully which are not possible to schedule using EDF algorithm.
Chapter Preview

A 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).

Complete Chapter List

Search this Book: