Summary of the talk by Prof. Ted Baker

Summary of the talk by Prof. Ted Baker

Alan Lupsha

Professor Ted Baker’s area of research is real-time systems. He focuses on real-time runtime systems, real-time scheduling and synchronization and real-time software standards.

Real-time scheduling for multiprocessors involves finding ways to guarantee deadlines for tasks which are scheduled on multiprocessor systems. A main problem with scheduling is that it is very difficult to meet constraints, given specific computational workloads. As workloads vary, meeting given constraints can be achieved with different guarantees. For example, the guarantee of execution differs when given constraints for fault tolerance, window of execution or energy usage. The quality of scheduling can vary as well, as this quality can quantify how well the schedule guarantees the meeting of deadlines or how late the task will complete over the deadline. Once an algorithm is able to schedule a workload, a schedule can also vary in sensitivity in proportionality with the variation in the parameters of the execution.

Professor Baker looks at workload models which involve jobs, tasks and task systems. Jobs are units of computation that can be scheduled with a specific arrival time, worst-case execution time, or deadline. Tasks are sequences of jobs, and can depend on other tasks. Sporadic tasks have two specific qualities: they have a minimum inter-arrival time, and they have a worst case execution time. Task systems are sets of tasks, where tasks can be related or they can be independent (scheduled without consideration of interactions, precedence or coordination).

Scheduling involves models, which can be defined as having a set of (identical) processors, shared memory, and specific algorithms. These algorithms can be preemptive or non-preemptive, on-line (decisions are made on the fly as instructions arrive) or off-line, and global or partitioned (split amongst processors where they can predict in advance the workload for each processor). There are three typical scheduling algorithms and tests. The first one is “fixed task-priority scheduling”, where the highest priority tasks run first. The second is “earliest deadline first”, where higher loads are handled without missing the deadline (these algorithms are easier to implement). The third type of algorithms (which are not used in single processing systems but only in multi-processor systems) are “earliest deadline zero laxity”, where the execution of a job can be delayed without missing the given deadline.

The difficulty of scheduling is that there is no practical algorithm for scheduling a sporadic task. One example of a scheduling test is the density test, where one can analyze what fraction of the processor is needed to serve a given task. Professor Baker researches task scheduling and is looking for acceptable algorithms which are practical, given specific processing constraints.