Accession Number : ADA598400


Title :   Competitive On-Line Scheduling for Overloaded Real-Time Systems


Descriptive Note : Doctoral thesis


Corporate Author : NEW YORK UNIV NY DEPT OF COMPUTER SCIENCE


Personal Author(s) : Koren, Gilad


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a598400.pdf


Report Date : Sep 1993


Pagination or Media Count : 132


Abstract : We study competitive on-line scheduling in uniprocessor and multiprocessor real-time environments. In our model, tasks are sporadic and preemptible. Every task has a deadline and a value that the system obtains only if the task completes its execution by its deadline. The aim of a scheduler is to maximize the total value obtained from all the tasks that complete before their deadline. An on-line scheduler has no knowledge of a task until it is released. The problem is to design an on-line scheduler with worst case guarantees even in the presence of overloaded periods. The guarantee is given in terms of a positive competitive factor. We say that an on-line algorithm has a competitive factor of r, 0 less than r 1, when under all possible circumstances (i.e, task sets) the scheduler will get at least r times the best possible value. The best value is the value obtained by a clairvoyant algorithm. In contrast to an on-line scheduler, the clairvoyant algorithm knows the entire task set a priori at time zero. When a uniprocessor system is underloaded there exist several optimal on-line algorithms that will schedule all tasks to completion (e.g., the Earliest Deadline First algorithm). However, under overload, these algorithms perform poorly. Heuristics have been proposed to deal with overloaded situations but these give no worst case guarantees. We present an optimal on-line scheduling algorithm for uniprocessor overloaded systems called D-over. D-over is optimal in the sense that it has the best competitive factor possible. Moreover, while the system is underloaded, D-over will obtain 100% of the possible value. In the multiprocessor case, we study systems with two or more processors. We present an inherent limit (lower bound) on the best competitive guarantee that any on-line parallel real-time scheduler can give.


Descriptors :   *COMPETITION , *OVERLOAD , *REAL TIME , *SCHEDULING , ALGORITHMS , MULTIPROCESSORS


Subject Categories : Administration and Management
      Psychology
      Electric Power Production and Distribution
      Computer Systems


Distribution Statement : APPROVED FOR PUBLIC RELEASE