A heuristic approach to scheduling hard real-time tasks with resource requirements in distributed systems
Wei Zhao · 1986
In the design of real-time computer systems, the scheduling problem is considered to be an important one and has been addressed by many researchers. However, most approaches have not dealt with tasks' resource requirements. In this dissertation, we will describe a heuristic algorithm to schedule hard real-time tasks, i.e. tasks that have deadlines, in a distributed system. Salient features of our algorithm are that it takes tasks' resource requirements into account, is dynamic, and is distributed. When a task arrives at a node, the scheduler component local to that node attempts to schedule the task on that node. If the attempt fails, the scheduling components on individual nodes cooperate to determine which node has sufficient resource surplus to finish the task before its deadline. This cooperation occurs through exchange of state information among nodes. Determination of a good destination node for a task is based on a technique that combines bidding and focused addressing. In the former, a good node is selected based on the bids that nodes send for the task; in the latter, a node that is estimated to have more than sufficient surplus to guarantee the task is said to be good. By properly combining these two schemes, we make use of their positive features while overcoming their shortcomings. Our heuristic algorithm is an attempt to overcome the exponential problem of scheduling. The algorithm for the local scheduler incorporates various factors that affect real-time scheduling to actively direct the scheduling process. The scheme for cooperation among nodes functions in spite of imprecise and incomplete global state information. Simulation studies show that our heuristic scheduling algorithm functions well in a wide range of application environments. The performance of our heuristic algorithm measured under various metrics is very close to that obtained via the algorithm though the optimal algorithm has been proved to be NP-hard.