Scheduling of Real-Time Distributed Systems
Real-time system is required to complete its work and deliver its services on a timely basis. The results of real-time systems are judged based on the time at which the results are produced in addition to the logical results of computations. Therefore, real-time systems have well defined, fixed time constraints i.e. processing must be done within the defined constraints otherwise the system will fail.
Real-time computing systems play a vital role in our society and spectrum of complexity of such systems vary widely from the very simple to extremely complex systems e.g. patient monitoring system in an ICU, flight control system to nuclear power plants. Some other examples of current real-time computing systems are the control of laboratory experiments, the control of engines in automobiles, command and control systems, process control plants, flight control systems, space shuttle and aircraft avionics, robotics, etc.
The distributed system can be defined as a collection of computing nodes interconnected by a high speed local and wide area networks. Utilization of distributed operating system in the provision of distributed parallel environment allows the execution of processes in parallel as well as traditional concurrent execution (Paoli, et al, 1996). There are one or more processors and a certain amount of memory in each node. The nodes don’t share memory; message exchange across the network is the only mechanism for communication between them.
There are two strategies for scheduling real-time tasks on multiprocessor and distributed systems: global and partitioning (Oh & Son, 1995). A centralized scheduler will take care of different jobs in case of global scheme but specific jobs are allocated to specific processor in partition scheme. Partitioning schemes are less complex since the overhead of multiprocessor scheduling merely consists in assigning tasks to processors (Thai, 2002). The assignment is performed only once, thereafter well-known uniprocessor scheduling algorithms can be used for each processor.
In client/server distributed systems, the server is often the bottleneck. For example, the growth rate of traffic at the World Wide Web servers has increased exponentially (Yongcheng & Roy, 1995). The same problem is affected to digital library systems also. Improving the server performance is thus crucial for improving the overall performance of distributed information systems.
Priority based scheduling algorithms have been widely applied in real-time systems and scheduling decisions are made immediately upon job releases and completions. These algorithms include Rate-Monotonic (RM), Deadline Monotonic (DM) (Liu & Layland, 1973), Earliest deadline first (EDF), Least Laxity First (LLF) (Mok, 1983), Highest Value First (HVF), Highest Value Density First (HVDF) (Buttazzo, et al, 1995) etc. In these algorithms, priorities of tasks are all calculated based on deadline, laxity time, criticalness, etc. RM and DM algorithms are fixed priority algorithms and priority is decided off-line. In EDF and LLF algorithms, priority changes as time changes and therefore called dynamic algorithms. EDF and LLF are proved to be optimal scheduling algorithm when the system is preemptive, underloaded and having only one processor (Dertouzos & Ogata, 1974; Mok, 1983). But the same is not true for multiprocessor systems. Moreover, in overload conditions, EDF or LLF algorithm will result in rapidly decreasing of the system performance, even bringing on the domino effect (Buttazzo, et al, 1995; Chengyang, et al,1999).