DESIGN PROBLEMS OF DISTRIBUTED COMPUTING

Fundamental Design Problems of Distributed Computing in Real Time Environment

Fundamental Design Problems of Distributed Computing in Real Time Environment

Real-time task scheduling on a multiprocessor architecture is characterized as sequencing a set of tasks and assigning them to processors of the system such that each task's time constraints are satisfied. Based on the time at which scheduling is performed, real-time scheduling algorithms have been divided into two categories, namely static and dynamic. In this paper, our focus is on dynamic algorithms. These algorithms (Mok, 1983; Sprunt et al., 1989; Zhao et al., 1987a; Zhao et al., 1987b; Sha et al., 1988; Schwan and Zhou, 1992 and Shen et al., 1993) produce schedules on line in hope of using more comprehensive and up-to-date information about the tasks and the environment. Due to the on-line nature of their problem solving, dynamic algorithms must be efficient, since their complexity directly affects the overall system performance (Ramamritham and Stankovic, 1984 and Stankovic et al., 1995).

Sequencing and assignment of real-time and non- real-time tasks on multiprocessor architectures has been formulated in the past as a search for a schedule in a search space. Many of the existing techniques for scheduling ordinary tasks on a multiprocessor architecture adopt an assignment-oriented search representation (Hamidzadeh et al., 1995; Ma et al., 1982 and Shen and Tsai, 1985). Techniques for scheduling real-time tasks on uniprocessor and multiprocessor architectures have generally adopted a sequence-oriented search representation (Shen et al., 1993; Huang et al., 1989; Zhao et al., 1987a and Zhao et al., 1987b. An assignment-oriented representation emphasizes the choice of processors to which tasks are assigned, in order to satisfy the problem objectives. A sequence-oriented representation emphasizes the order in which tasks should be scheduled, in order to satisfy the problem objectives. Assignment-oriented representations are naturally suitable for task assignment in multiprocessor architectures. The sequence-oriented representations are commonly chosen for real-time scheduling, since they emphasize the ordering of the tasks considering task characteristics such as deadlines.

Dynamic techniques for scheduling real-time tasks on a multiprocessor architecture using an assignment-oriented representation have rarely been discussed. Performance implications of using such techniques and their comparison with sequence-oriented techniques have not been fully studied. This is a major issue that we address in this paper. Many of the existing dynamic algorithms for scheduling real-time tasks ignore the direct effect of factors such as when scheduling is performed, where scheduling is performed and the scheduling duration, on schedule quality. This issue is also addressed in this paper.

The algorithms proposed in the literature are either static, thus lacking the ability to adapt their performance to the changes in the environment or dynamic, thus requiring a time -complexity control. Time -control complexity has up to our knowledge not been addressed explicitly. Implicitly, however, some algorithms do try to minimize the time -complexity by limiting the search space but at the expense of limiting - also - the solution space. Our algorithm's objective is to explicitly control the time ...