Resource Management for Real-Time Environments

The design of real-time systems is an activity that involves meticulous planning and management of multiple resources. These resources need to function predictably and in concert with one another to ensure that tasks executing on the system will meet stringent timing requirements and provide the desired performance to the application. Architecting a real-time system is an offline process but the architect needs to consider all the task characteristics and requirements before synthesizing a system. This activity can be aided by design techniques that explore a huge system space and identify suitable designs. Resources need to be allocated with considerations to the functional and non-functional aspects (timing) of the system and the cost of the design. Online resource management of a real-time system requires fast reaction to changing workload and efficient tests for schedulability, even when there are several constraints to deal with. Both online and offline activities are concerned with performance or utility optimization. Optimization is performed within a parameter space; the space is defined by the capabilities of the resource and the ability of the system to meet timing requirements. From this viewpoint, many real-time systems make use of utilization bounds to define a feasibility region. The traditional bounds have been conservative and are such that as long as the task set does not exceed the utilization bound, all jobs will meet their deadlines. Alternatively, if a set of tasks violates the utilization bound, jobs may miss their deadlines. We observe that while traditional utilization bounds exist for many systems and scheduling algorithms, they are hard to derive for complex systems and they are often more conservative than they need to be. We make use, instead, of phase transitions in resource management and scheduling problems to derive a slightly different utilization-based test that is almost surely correct. By this, we mean that resource allocation may be infeasible even if the task set satisfies the utilization test but the probability of doing so is very small. Similarly, if a task set exceeds the utilization threshold suggested, it almost certainly does not have a feasible resource allocation. We make connections with random graph theory and statistical physics in our work and show specific instances where we can solve problems that were hitherto hard to solve or improve the results for some well-studied problems. The specific instances that we study are: phased-array radar dwell scheduling, multiprocessor scheduling and multidimensional resource management. We believe that exploiting phase transitions is a simple and sufficient design approach for most real-time systems. In the resource management problem for radar systems, we have also developed a new algorithm for finite horizon scheduling that is of great use in dynamic environments and is efficient despite the many constraints imposed on the scheduler by the requirements of the radar system