Introductory Seminar on Research (CIS 5935)

Fall Term 2006


What is my main research theme/topic?

     "real-time computing"

My ideal work product combines:

  1. a problem or application that people care about and are likely to use
  2. a new algorithm, idea, or question
  3. a sound abstract model, with analysis pushed to the limit of what theory can do
  4. an implementation study, to:
  5. if full-scale implementation is not practical, simulations:

Past work

Examples of Specific Past Projects

Examples of Student Involvements

Current Resarch Areas

What is Real Time?

Examples of Real Time Systems

 X + predictable/controllable timing = real-time X

Real-Time Device Driver Architecture


  1. study some real drivers in Linux
  2. look at how the OS schedules them
  3. try to analyze the drivers interactions with real-time threads
  4. look for ways to improve analyzability/performance

Testbed Project - Video Surveillance System

Real-Time Scheduling Terms

SMP Schedulability Analysis

``Dhall Effect'' with EDF/DM Scheduling on MP

This is only a problem when we have some tasks with very high local utilization.

This example shows worst-case achievable multiprocessor utilization can be arbitrarily close to 1, compared to ideal value of m. Until recently, it was used as an excuse for using partitioned scheduling on multiprocessors. However, the example depends on mixing tasks with extremely low and extremely high utilization (or ratio of compute time to deadline). Intuitively, we know we can achieve higher utilization when we have only smaller tasks.

Global Schedulability Test - Basic Idea

Load-Based Schedulabity Analysis

  1. Find a lower bound μ on the load of a window leading up to a deadline that is necessary for the deadline to be missed.

  2. Find an upper bound β on the load of such a window that can be generated by a given task set.

  3. If β < μ the task set must be schedulable.

There are several variations as to how we define "load" that allow different refinements in analysis.

Generalized Fixed-Priority Density Test

A system of N independent sporadic tasks can be scheduled to meet all deadlines on M processors using preemptive global fixed task-priority scheduling if (but not necessarily only if), for every task τk there exists λ≥λk such that one of the following criteria is satisfied


min(βλk(i), 1 - λ) < m (1- λ)

min(βλk(i), 1 - λ) = m (1- λ) and i βλk(i) (1- λ) ⇒ βλk(i) = 0


βλk(i)    def
0  if  i k
ui(1 + max(0, pi-ei
))  if  ui≤λ and i < k
ui(1 + max(0, pi-ei+di(1- λ/ui)
))  if  ui and i < k

This is one of several results, which have gradually provided better techniques for verifying schedulability of task systems on multiprocessors.

Unfortunately, they do not cover all the cases. When it comes to evaluating how well they do, we look at performance in simulations on large numbers of task sets.

Experiment with BC Test for Deadline Monontonic Scheduilng on 4 CPUs

How many of the task sets that could not be proven schedulable are not schedulable?

Hierarchy of Possibilities for a Task Set

  1. schedulable to meet all deadlines by given method
  2. feasible (there exists a schedule that meets deadlines) but not schedulable by given method
  3. infeasible (there is an arrival sequence for which no schedule can meet all deadlines)
© 2002, 2003, 2004, 2005, 2006 T. P. Baker. ($Id)