The Real Time Systems Laboratory has developed two novel techniques that solve scheduling and resource management problems critical to the development of autonomous navigating vehicles for space exploration as well as for command and control for air defense, surveillance/ reconnaissance radar systems, and multiphase array radars.
The Generic Utility Scheduling (GUS) algorithm is a scheduling algorithm for real-time computers. Timeliness is critical for real-time computers that interact with the physical world, such as those embedded in vehicles. Such computers typically process sensor data, such as speed or altitude, then initiate control actions, such as braking. The actions must be timely for correct operation such as staying on course or stopping before a crash.
Unlike conventional real-time scheduling algorithms that consider actions with “deadline” time constraints whose (anytime) completion before a deadline time is useful (and otherwise not), GUS handles more general time constraints such as completing actions whose utility varies (e.g., decreases, increases) with time. Further, GUS handles situations where competing requests on computing resources must be satisfied in a mutually exclusive manner for maintaining resource integrity. GUS orders actions to maximize their total accrued utility, while respecting resource mutual exclusion constraints.
The research team, headed by Binoy Ravindran, also has devised a mathematically verified software framework for implementing utility accrual algorithms such as GUS on commercial off-the-shelf real-time operating systems. Called the Meta Scheduler, the framework can be used without modifying the operating system.