Dynamic scheduling for real-time distributed systems using ant colony optimization. (English) Zbl 1214.68084
Summary: In client/server distributed systems, the server is often the bottleneck. Improving the server performance is thus crucial for improving the overall performance of distributed information systems. Real-time system is required to complete its work and deliver its services on a timely basis. The purpose of this paper is to propose a new scheduling algorithm for real-time distributed system (client/server model) to achieve the above-mentioned goal.
The Ant Colony Optimization (ACO) algorithms are computational models inspired by the collective foraging behavior of ants. They provide inherent parallelism and robustness. Therefore, they are appropriate for scheduling of tasks in soft real-time systems. During simulation, results are obtained with periodic tasks, measured in terms of success ratio and effective CPU utilization; and compared with results of Earliest Deadline First (EDF) algorithm in the same environment.
Analysis and experiments show that the proposed algorithm is equally efficient during underloaded conditions. The performance of EDF decreases as the load increases, but the proposed algorithm works well in overloaded conditions also. Because of this type of property, the proposed algorithm is more suitable for the situation when future workload of the system is unpredictable.
The application of ACO algorithms for scheduling of client/server real-time distributed system, never found before in the literature. The new concept proposed in this paper will be of great significance to both theoretical and practical research in scheduling of distributed systems in the years to come.
The Ant Colony Optimization (ACO) algorithms are computational models inspired by the collective foraging behavior of ants. They provide inherent parallelism and robustness. Therefore, they are appropriate for scheduling of tasks in soft real-time systems. During simulation, results are obtained with periodic tasks, measured in terms of success ratio and effective CPU utilization; and compared with results of Earliest Deadline First (EDF) algorithm in the same environment.
Analysis and experiments show that the proposed algorithm is equally efficient during underloaded conditions. The performance of EDF decreases as the load increases, but the proposed algorithm works well in overloaded conditions also. Because of this type of property, the proposed algorithm is more suitable for the situation when future workload of the system is unpredictable.
The application of ACO algorithms for scheduling of client/server real-time distributed system, never found before in the literature. The new concept proposed in this paper will be of great significance to both theoretical and practical research in scheduling of distributed systems in the years to come.
MSC:
| 68M14 | Distributed systems |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
References:
| [1] | DOI: 10.1109/TC.2003.1214344 · doi:10.1109/TC.2003.1214344 |
| [2] | DOI: 10.1109/REAL.1995.495199 · doi:10.1109/REAL.1995.495199 |
| [3] | DOI: 10.1145/1391469.1391667 · doi:10.1145/1391469.1391667 |
| [4] | Chenyang, L., Stankovic, J.A., Gang, T. and Sang, H.S. (1999), ”Design and evaluation of a feedback control EDF scheduling algorithm”,Proceedings of the 20th IEEE Real-Time Systems Symposium, Phoenix, AZ, USA, pp. 56-67. |
| [5] | Dertouzos, M. and Ogata, K. (1974), ”Control robotics: the procedural control of physical process”,Proceeding of IFIP Congress, Stockholm, Sweden, August 5-10. |
| [6] | DOI: 10.1109/4235.585892 · doi:10.1109/4235.585892 |
| [7] | DOI: 10.1109/3477.484436 · doi:10.1109/3477.484436 |
| [8] | DOI: 10.1109/REAL.2001.990609 · doi:10.1109/REAL.2001.990609 |
| [9] | DOI: 10.1137/S0097539792236882 · Zbl 0834.68037 · doi:10.1137/S0097539792236882 |
| [10] | Kotecha, K. and Shah, A. (2008a), ”Ant colony optimization based dynamic scheduling algorithm for real-time operating system”,Proceedings of International Conference on Artificial. Intelligence and Pattern Recognition (AIPR08), Orlando, FL, USA, pp. 70-4. |
| [11] | Kotecha, K. and Shah, A. (2008b), ”Efficient dynamic scheduling algorithms for real-time multiprocessor system”,Proceedings of the High Performance Computing, Networking and Communication Systems (HPCNCS 08) International Conference, Orlando, FL, USA, pp. 21-5. |
| [12] | DOI: 10.1145/321738.321743 · Zbl 0265.68013 · doi:10.1145/321738.321743 |
| [13] | DOI: 10.1007/BF01088806 · doi:10.1007/BF01088806 |
| [14] | DOI: 10.1109/ICDCS.1996.508005 · doi:10.1109/ICDCS.1996.508005 |
| [15] | DOI: 10.1109/71.80146 · doi:10.1109/71.80146 |
| [16] | Ramos, V., Muge, F. and Pina, P. (2002), ”Self-organized data and image retrieval as a consequence of inter-dynamic synergistic relationships in artificial ant colonies”,Second International Conference on Hybrid Intelligent Systems (HIS’02), Santiago, Chile, December 1-4, pp. 500-12. |
| [17] | Saad, E.M., Adawy, M.E. and Habashy, S.M. (2006), ”Reconfigurable parallel processing system based on a modified ant colony system”,Proceedings of the National Radio Science Conference (NRSC 2006), Menofia, Egypt, March. |
| [18] | Saini, G. (2005), ”Application of fuzzy-logic to real-time scheduling”,14th IEEE-NPSS Real-Time Conference, AlbaNova University Centre, Stockholm, pp. 60-3. · doi:10.1109/RTC.2005.1547449 |
| [19] | Stutzle, T. (1998), ”An ant approach for the flow shop problem”,Proceedings of European Congress on Intelligent Techniques and Soft Computing (EUFIT’98), Aachen, Germany, September 7-10, pp. 1560-4. |
| [20] | DOI: 10.1109/PCEE.2002.1115229 · doi:10.1109/PCEE.2002.1115229 |
| [21] | Turneo, A., Pilato, C., Frrandi, F., Sciuto, D. and Lanzi, P.L. (2008), ”Ant colony optimization for mapping and scheduling in heterogeneous multiprocessor systems”,Proceedings of IEEE International Conference on SAMOS VIII: Embedded Computer Systems: Architectures, Modeling, and Simulation, Samos, Greece, July 21-24, pp. 142-9. |
| [22] | Yongcheng, L. and Roy, C. (1995), ”A dynamic priority based scheduling method in distributed systems”,Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications, Urbana, IL, USA, August 14-18, pp. 177-86. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
