Cluster formation techniques for hierarchical real time tasks allocation onmultiprocessor system

摘要

Real-time systems are nowadays extensively used in most time-critical embedded applications. The existing multiprocessor real-time scheduling algorithms are based on partitioned and global scheduling approaches. The partitioned-based algorithms suffer poor utilization bound, load balancing, not compatible for an open system environment, and the global scheduling approach faces problems like high scheduling, migration overhead. Cluster scheduling represents a hybrid scheduling approach which consists of a set of processors as clusters and tasks scheduled to each processor of clusters using a global scheduling approach. The different cluster formation heuristics are investigated for homogenous clusters. The main objective of this article is to propose task utilization-based cluster formation and harmonic period aware task allocation for a hierarchical real-time system on a multiprocessor platform. Tasks with high utilization, cluster size tune to a smaller value to achieve high utilization. Tasks with low utilization, the size of cluster tune to larger to reduce migration and scheduling overheads. Experimentation performed on multiprocessor real-time simulator with a different set of tasks, multiprocessor system, different tasks utilization, and cluster size. Simulation results show that cluster base approach increases the number of tasks scheduled on a multiprocessor system, system utilization, and reduces response time, migration, and preemption overheads.