Introductory Seminar on Research (CIS 5935)

Fall Term 2007


Elements of good CS research:

  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, do simulations:

Past work

Examples of past projects

Examples of student involvements

What is my main current research area?

     "real-time systems"

What is "real time"?

Examples of real time systems

Real-time systems research

Goal: Designing and implementing systems with control over execution timing
-- i.e., over when certain steps of a computation are executed, relative to events in the real world.

Ideal: should be able to design and code a system with as much confidence that timing will be correct as that output values will be correct

Order of importance:

  1. predictability
  2. reliability
  3. speed, efficiency

 X + predictable/controllable timing = real-time X

Core problems

Current research projects

  1. real-time multiprocessor scheduling
  2. real-time device driver architecture

Real-time device driver architecture

Approach to research

  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


Example: Effect of I/O activity on real-time response

Response time distributions of a task with 100 msec. period and 10 msec. execution time, with interference from network and disk drivers.

Example: Empirical estimation of interference due to network driver

Interfering load = maximum % of CPU time consumed by higher priority activities over time all intervals of a given length.

Example: A model for observed interference

Empirical upper bounds on interfering load due to device drivers can be fittedhave similar shape to periodic task.

Permits combining device driver interference with analysis of periodic tasks

Research on Real-Time Disk I/O Drivers - Mark Stanovich

SMP Schedulability Analysis


Real-Time Scheduling Terms

``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 Tests - 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.

Example: 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.

Example simulation experiment:
BC Test for Deadline Monotonic Scheduling 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)

Some directions for research



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