Article Preview
Top1. Introduction
Distributed real time system (DRTS) consists of a set of nodes (computer) interconnected by a real-time communication network in some fashion so that a program or procedure runs on a system with multiple processors. DRTS has many applications in various fields such as telephone networks, cellular networks, computer games, image processing, cryptography, industrial process monitoring simulation of nuclear reactor, air- plane, banking system, transportation problems and network flow problem etc. Tasks allocation is a process of partitioning a program into a number of tasks where each task executes on a separate processor. Tasks partitioning and tasks allocation are two major steps in the formation of DRTS. In order to make best use of the resources, it becomes essential to maximize the overall throughput by allocating the tasks to processors in such a way that the allocated load on all the processors should be balanced and also minimize the inter-tasks communication by assigning tasks to same processor as much as possible. These conditions contrary to each other as an increase in the number of processors may actually decrease the total throughput of the system. This degradation effect is known as saturation effect, which occurs due to heavy communication traffic induced by data transfers between tasks that reside on separate processors. An allocation policy can be static or dynamic, depending upon the time at which the allocation decisions are made. In static allocation once a task is assigned to a processor, it remains there statically during the execution of a distributed program.
It is found that if the fulfillments of these steps are not properly completed then an increase in the number of processors may result in a decrease of total throughput of the system (Chu et al., 1978; Crespo et al., 2016). Graph theoretic approach is widely used for tasks allocation problem with the objective of minimizing total execution and communication costs (Ma et al., 1982; Bokhari, 1987; Shen and Tsai, 1985). A heuristic algorithm (Lo, 1988) has been developed for stone’s classic model to minimize the total execution and communication costs. In recent years, several heuristic models have been developed (Efe, 1982; Tindell et al., 1992; Woodside and Monforton, 1993; Sharma et al., 2011; Martinez et al., 2015; Akbari and Rashidi, 2016; Kumar et al., 2018) for tasks allocation with the goal of minimizing system cost and maximizing the system throughput. Branch and bound method technique are efficiently used for optimal tasks assignments to minimize the sum of task execution and communication costs (Peng et al., 1997). A heuristic algorithm has been derived from well-known simulated annealing (SA) technique with the goal of maximizing the system reliability (Attiya and Hamam, 2006). Artificial Neural Network has been used for finding the optimal assignment of the tasks in DRTS (Yadav et al., 2011). In order to make the best use of resources in a DRTS, it is necessary to reassign tasks dynamically during program execution (Kong et al., 2011; Kumar et al., 2016). Recently, a two-phase scheduling technique is presented for DRTS in which it has two distinct phases; the first phase is in charge of producing a scheduling sequence whereas the second phase aims to dispatch tasks to computing nodes of a DRTS (Jiang et al., 2017).
Clustering is one of the standard workhorse techniques in field of DRTS. Its intention is to systematize a dataset into a set of groups or clusters, which contain similar data items, as measured by some distance function. Clustering algorithms are developed to solve a particular problem in a specialized field (Jain et al., 1999). Fuzzy clustering technique has been used by many researchers (Yadav et al., 2011; Lemos et al., 2013; Velmurugan et al., 2014; Zhou et al., 2014; Nayak, 2016).