زمانبندی گراف چند وظیفه ای در سیستم های زمان واقعی ناهمگن توزیع شده با بهره برداری از حفره های برنامه زمانبندی با تکنیک های بسته بندی Bin

The most crucial aspect of distributed real-time systems is the scheduling algorithm, which must guarantee that every job in the system will meet its deadline. In this paper, we evaluate by simulation the performance of strategies for the dynamic scheduling of composite jobs in a heterogeneous distributed real-time system. Each job that arrives in the system is a directed acyclic graph of component tasks and has an end-to-end deadline. For each scheduling policy, we provide alternative versions which allow the insertion of tasks into idle time slots, using various bin packing techniques. The comparison study, based on different workloads and system heterogeneity levels, shows that the alternative versions of the algorithms outperform their respective counterparts.

The inherent need of many scientific and commercial applications for completion within strict timing constraints, has led to the widespread use of distributed real-time systems. These systems are employed in various critical areas, such as the control of nuclear power plants, financial markets, radar systems, telecommunication networks, intensive care monitoring and multimedia applications. In a real-time system, the jobs have deadlines that must be met. The correctness of the system does not depend only on the logical results of the computations, but also on the time at which the results are produced. If a real-time job fails to meet its deadline, then its results will be useless, or even worse, this may lead to disastrous consequences for the system and the environment that is under control [2]. With the advent of increasingly powerful and cost-effective computing components, many of today’s distributed real-time systems are heterogeneous. That is, they comprise different types of processors and networks. The major challenge in such a real-time heterogeneous environment, is the employment of effective scheduling techniques, in order to guarantee that every real-time job will finish its execution within the imposed timing constraints. The scheduling algorithm is responsible for the allocation of processors to jobs and determines the order in which jobs will be executed on processors. In distributed real-time systems, a job may be represented by a directed acyclic graph (DAG or task graph), where the nodes represent the component tasks of the job and the edges represent the data dependencies between the tasks. Each job has an end-to-end deadline that must be met. That is, the tasks of a job do not have any specific individual deadlines, but there is an end-to-end timing constraint over all the tasks of the job. In order for a task to start execution, all of its predecessor tasks must have been completed. A task with no predecessors is called an entry task, whereas a task with no successors is called an exit task. The immediate predecessors of a task are called parents of the particular task, while the immediate successors of a task are called children of the particular task. In order for a job to meet its deadline, i.e. to be guaranteed, all of its exit tasks must finish execution before the job’s deadline is reached.

In this paper, we evaluated by simulation the performance of a list scheduling heuristic, for the scheduling of multiple task graphs with end-to-end deadlines in a heterogeneous distributed real-time system. The task selection phase is either based on the EDF, HLF or the LSTF policy. The processor selection phase, is implemented either without the exploitation of possible schedule holes, or by exploiting idle time slots, with the employment of the FF, BF or WF bin packing technique. The performance of the scheduling policies was evaluated by simulation, under various workloads and system heterogeneity levels. Our simulation results show that in this case study, the alternative versions of the algorithms, that exploit schedule holes, perform better than their respective counterparts that do not. Moreover, the BF policy, when used for the exploitation of idle time slots, exhibits better performance than FF and WF. The combination of EDF in the task selection phase with BF in the processor selection phase, outperforms all the other examined heuristics. In real-time systems, it is often more desirable for a job to produce an approximate, imprecise result by its deadline, than to produce an exact result late. Therefore, our scheduling policies could be further enhanced, by incorporating imprecise computations techniques that would allow them to trade off result precision for timeliness. Moreover, we could investigate the case where the processors exhibit different heterogeneity levels from the communication links, as well as the impact of transient hardware failures on the system performance. Consequently, further research is needed in order to address these issues.