An efficient heuristic scheduler for hard real-time systems
Levine, John Glenn
MetadataShow full item record
The requirement for efficient scheduling algorithms for the development of hard real-time systems resulted in much effort directed toward the development of high performance scheduling algorithms. The algorithms developed up to this point for the Computer Aided Prototyping System (CAPS) do not satisfy the requirements for a efficient static scheduling algorithm. The existing static scheduler neither performs efficiently nor produces correct results for all input cases. The thesis represents the research conducted to develop a fast heuristic static scheduling algorithm based on the principles of simulated annealing. In addition, this thesis describes the development of new data structures that simplify the static scheduler and maximize system resources. Several of the existing scheduling algorithms were re-implemented to make use of the new data structures and provide correct results. Any feasible schedule produced by these scheduling algorithms guarantees that both timing and precedence constraints are met. The primary goal of this thesis was to produce an efficient and effective scheduler to support the CAPS system.
Approved for public release; distribution is unlimited
Showing items related by title, author, creator and subject.
Janson, Dorothy M. (Monterey, California. Naval Postgraduate School, 1988-03);As demand for hard real-time and embedded computer systems increases, a new approach to software development is critical. Software engineers and users would benefit from an automated methodology allowing validation of ...
Chang, Tzu-Chiang (Monterey, California. Naval Postgraduate School, 1992-09);Task scheduling is one of the most important issues in a hard real-time system, because it is the schedule that ensures tasks meet their deadlines and precedence constraints. Given a set of hard real-time tasks, to determine ...
Xie, Geoffrey G.; Lam, Simon S. (1996-10);For many service disciplines that provide delay guarantees, the scheduler of a channel repeatedly searches for the smallest element in a set of priority values (or deadlines). It is required that each search finishes ...