From: rlarowe@chpc.org (Rick LaRowe)
Subject: CHPC Colloquim
Organization: Center For High Perf. Computing of WPI; Marlboro Ma
Distribution: ne
Date: Thu, 1 Oct 1992 13:46:51 GMT


                    Center for High Performance Computing
                                  Colloquium

                                 Fuxing Wang
                        Department of Computer Science
                    University of Massachusetts at Amherst 


                   Dynamic Scheduling in Real-Time Systems
                       --- Algorithms and Analysis

      Dynamic scheduling in real-time environments involves dynamically
      making a sequence of decisions concerning the assignment of system
      resources to real-time tasks. System resources include processors,
      memory, and shared data structures.  Tasks may be independent or have
      precedence constraints and could be preemptable or non-preemptable.
      They may differ in their arrival times, computation times, deadlines,
      and importance values. Our goal is to design dynamic scheduling
      algorithms under different task parameter settings and to evaluate
      their performance. We focus on the study of efficient algorithms,
      specifically, on the worst-case analysis of these algorithms based on
      certain measures and performance evaluation via simulation.
      
      For independent tasks, we provide a competitiveness analysis of
      dynamic algorithms. We assume that tasks have different values, and
      the performance bound is the ratio of the total value obtained by a
      dynamic scheduling algorithm to the total value obtained by an ideal
      optimal off-line ``clairvoyant'' algorithm.  Based on this
      competitiveness analysis, some good algorithms are found, which are
      better than the popular Earliest Deadline First algorithm.
      
      For scheduling tasks with additional resources, we study scheduling
      algorithms based on the ability to generate feasible schedules and the
      quality of the generated feasible schedules, expressed in terms of the
      schedule length.  By analyzing two known algorithms, list scheduling
      and the Spring heuristic scheduling algorithm, new algorithms with
      better performance have been developed.
      
      For scheduling tasks with precedence and fault-tolerance constraints,
      we have investigated practical issues in constructing predictable and 
      dependable real-time systems and developed new scheduling algorithms. 
      First, generic  fault-tolerance support is provided via a system 
      description language. Second, many fault-tolerance requirements are 
      satisfied using a dynamic scheduler. Third,  dynamic configuration 
      and scheduling are integrated to reduce overheads and to increase 
      performance. We have constructed a testbed to conduct a simulation 
      study of these approaches. 
------------------------------------------------------------------------------
 Date:  Thursday, October 8, 1992
 Time:  10:30 AM
Place:  Center for High Performance Computing 
	Worcester Polytechnic Institute
	293 Boston Post Road West,  Marlborough, MA
 Info:  Contact Rick LaRowe @ (508) 624-7400 x610 or rlarowe@chpc.org
------------------------------------------------------------------------------