Introductory Seminar on Research (CIS 5935)

Fall Term 2005


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:

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 Scheduling Terms

Seminal 1970's results of Liu & Layland

Fixed priority is widely implemented by OS's and widely used. Deadline is theoretically better in most respects but less widely used.

Hot debate: Why is deadline scheduling less used? Is it really superior to fixed priority for all applicaitions?

Real-Time Device Driver Architecture

Example: Jitter of Periodic Tasks under Linux

jitter without disk and network activity
jitter with disk activity
jitter with network traffic


  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

Possible Testbed Project - Video Surveillance System

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 as bad as 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

Schedulabity Test Based on Demand Analysis

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

  2. Find an upper bound β on the workload 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.

Utilization Test, Generalized

A system of N sporadic tasks can be scheduled to meet all deadlines on M processors using global EDF scheduling if (not only if)

∑ ci/min(Ti,di) < M - (M - 1)*max(ci/min(Ti,di))

This is one of several results, which have gradually provided better techniques for verifying schedulability of task systems on multiprocessors. It is an upublished but "obvious" generalization to arbitrary deadlines of a result for the special case where deadline=period that was published by Goosens, Baruah, and Funk.

Comparision of Basic Fixed-Priority Rules

Comparision of Hybrid Deadline Monotonic Schemees

Comparision of Hybrid EDF Schemees

Comparision of Hybrid FP Partitioning Schemees

Comparision of Hybrid EDF Partitioning Schemees

Comparision of Global vs. Partioned

Upper Bounds by Simulation

© 2002, 2003, 2004, 2005 T. P. Baker. ($Id)