Scheduling in Hard Real Time Systems: The Response Time Approach

Operating systems such as windows and Linux coordinate the execution of hundreds of concurrent tasks by dynamically assigning shared resources such as CPU and memory to them. In real-time systems, tasks are typically periodic, following repeated execution of a sense-compute-actuate cycle for each task type. There are stringent deadlines on how soon each invocation of a task must be completed. The operating system can interrupt the computation of one task to give the CPU to another task to ensure the meeting of deadlines of all tasks. Such adequate scheduling is a critical requirement for sensitive applications like aerospace and reactor control. 

The classical model of Hard Real Systems with priority-based preemptive scheduling was defined and analysed by Liu and Layland in their paper in 1973. It posed two questions: (a) how to assign priorities to tasks (priority assignment), and (b) how to check that all the deadlines are met under a given priority assignment (feasibility). An exact solution to the feasibility question was proposed in a paper from TIFR in 1986. The solution involved characterising the worst-case response time of a task using a recursive equation, and a method for solving this equation. This response time approach has, since then, found wide applicability and it has been generalised to much more complex situations involving dependencies and locking between tasks with priority inheritance, and multi-processor executions. 

Very recently, some of these works were recognized for their continued impact by conferring the inaugural “test of time award” to 4 papers by the IEEE technical committee on real-time systems. This talk gives a retrospective on these papers and their continued impact on the field of real-time scheduling.

About the Speaker:

Paritosh Pandya is a computer scientist whose areas of interest include logic, automata, mathematics of program construction and embedded systems. He is a retired professor and former Dean of the School of Technology and Computer Science at the Tata Institute of Fundamental Research (TIFR). He is currently an adjunct professor in the computer science department at IIT Bombay. Paritosh Pandya did his B.Tech in Electronics at M. S. University, Baroda, M.Tech in Computer Science at IIT Kanpur and PhD in Computer Science at TIFR. He has worked as a research officer in Oxford University Computing Laboratory under Prof C.A.R. Hoare and also as a visiting scientist at the United Nation University's International Institute of Software Technology in Macau. Paritosh Pandya loves Indian classical music and he is trying to teach the same to his computer.