Introductory Seminar on Research (CIS 5935)
- What kinds of research I have done in the past?
- What is the main direction of my research?
- What, specifically, am I working on now?
- Some details on one area of current research
What is my main research theme/topic?
- 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
- requires cooperation of all levels of the computer/system
- application program
- programming language implementation
- operating system
- models of computation -- require simplifications
- scheduling algorithms, concurrency control/resource allocation algorithms
- analysis of schedulability (for each algorithm)
- performance testing
- trial applications
My ideal work product combines:
- a problem or application that people care about and
are likely to use
- a new algorithm, idea, or question
- a sound abstract model, with analysis pushed to the limit of
what theory can do
- an implementation study, to:
- verify feasibility
- resolve, empirically, issues that the theory cannot
- encourage use, by providing a working product
- theory: computability, computational complexity, P&NP
- algorithms: pattern matching, parsing, priority queues
- compilers: semantic analysis, parsing, code generation, Ada, worst-case execution time analysis, reducing context switches
- OS: real-time kernels, threads, multiprocessing, standards (POSIX/UNIX)
- real time: kernels, scheduling, programming languages
Examples of Specific Past Projects
- exploratory development -- OS's and PL's
- GNAT Ada compiler
→ Java bytecode target
→ RT Linux target
- GNARL runtime system (Ada) → optimization, portability
- Ada language standard → real-time extensions, AST, locking
- POSIX threads (C) -
FSU pthreads library
- POSIX Ada binding (Ada) → sockets, test suite
- Linux (C) → real time extensions
- theory - real-time schedulability analysis
- concurrency and resource control
- multiprocessor scheduling models
- timing analysis
Examples of Student Involvements
- Ada tasking optimizations (PhD, Oh)
- Real-time nested transactions (PhD, Moon)
- RT Linux Ada kernel (MS, Shen)
- RT Linux Sporadic Server (MS, Shi)
- Ada/RT Linux Priority Queue Performance Evaluation (MS, Nikhil Mhatre)
- RT Linux Network Driver (MS, Liu)
Current Resarch Areas
- real-time multiprocessor scheduling
- schedulability analysis (theory)
- partitioned and global models
- concurrency control
- implementation and performance studies
- applications (vision, tracking?)
- real-time systems course, and
- real-time device driver architecture
- 4-year NSF grant: with Kartik Gopalan & Andy Wang (co-PIs),
Mark Lewandowski & Mark Stanovich (RAs)
- objective: structure and schedule device drivers to make real-time scheduling
more predictable for applications
- device drivers course
- real-time image analysis/tracking (with CAVIS group)
- have equipment, via ARO DURIP grant
- looking for tie-in with device driver research
What is Real Time?
- Is achieving correct timing a primary consideration in the design?
- Does the computer system need to synchronize with external entities?
- Can a timing error cause the entire system to fail? e.g.
- if output is produced to early?
- if output is procued too late?
- if time between input and output is too long?
- Main objective: predictable timing, to meet requirements
- Secondary objective: fast execution
Examples of Real Time Systems
- nuclear reactor monitoring system
- chemical plant control system
- remotely piloted vehicle
- multi-media player
- washing machine, TV, automobile
- stock market analysis system
- video surveillance system
X + predictable/controllable timing = real-time X
Real-Time Scheduling Terms
- job = unit of schedulable work
- a procedure, and data on which it executes
- an execution time (generally not known exactly, but usually
with known upper bound)
- a deadline (hard or soft)
- task τi = sequence of jobs Ji,j
— a.k.a. "thread", "process"
- periodic task = job release times are separated by a constant (the task period)
- aperiodic task = not a periodic task
- some load limiting constraint needed to ensure schedulability
- e.g., strict minimum separation and maximum execution time constraints
- e.g., probabilistic model for arrivals and execution times
- utilization of a task is average execution time needed
per unit of real time = ci/Ti
(one of several metrics)
Seminal 1970's results of Liu & Layland
- EDF (earliest-deadline-first) scheduling - optimal for periodic tasks
- theorem: independent perodic task set schedulable iff total utilization
- original limitations:
- only applies to independent periodic tasks
- relies on accurate worst-case execution time bounds
- under overload, which task misses deadline is unpredictable
- there have been a number of extensions since
- fixed priority - rate-monotonic is optimal ordering for periodics
- theorem: indep. periodic task set scedulable iff U <=
n(21/n-1) - (>= 69%)
- similar original limitations to EDF, many addressed
by later extensions
- rate-monotonic generalizes to deadline-monotonic
Fixed priority is widely implemented by OS's and widely
used. Deadline is theoretically better in most respects but less
Hot debate: Why is deadline scheduling less used?
Is it really superior to fixed priority for all applicaitions?
Real-Time Device Driver Architecture
- solid body of theory on real-time scheduling exists
- based on workload fitting one of several abstract models
- based on scheduling according to one of several
well analyzed policies/algorithms
- allows proving timing constraints will always be met,
or determining frequency/probability of failure
- device drivers
- use special OS scheduling mechanisms
- can preempt and block application thread/processes
- scheduling is hierarchical, does not fit standard models
- drivers not designed to fit workload models
- real-time applications
- preempted and/or blocked by device drivers
- have little/no visibility or control over driver effects
Example: Jitter of Periodic Tasks under Linux
- study some real drivers in Linux
look at how the OS schedules them
- analyze their workload
- read driver code to see logic
- insert instrumentation code to get actual timings
- run benchmarks (tests) and gather data
- how to they compete with application threads for CPU time?
- how do they hold up applications waiting for I/O?
- try to match workload to abstract models
- what are the "jobs" and the "tasks"?
- what is their execution pattern (periodic, sporadic, what?)
- what are their scheduling requirements?
try to analyze the drivers interactions with real-time threads
- does it fit any analyzed formal models?
- if not, can we analyze it?
- if not, can we change kernel to fit a nicer model?
look for ways to improve analyzability/performance
- check predictions against actual performance
- in analysis techniques
- in driver design
- in OS support for drivers
- extend/modify kernel "API" for drivers
- provide application-level controls?
Possible Testbed Project - Video Surveillance System
SMP Schedulability Analysis
- multiprocessors, including multi-core becoming more common
- schedulability theory not well developed, relative to single processor
- core result on "critical instants" does not apply
- traditional method: partioned scheduling (queue per processor)
- apply single-processor scheduling on each CPU
- optimal partitioning is NP-hard
- first-fit comes within 50% of optimal, usually much better
- worst case: breakdown and 50% of optimal processor utilization
- global (single queue) scheduling
- originally deprecated, due to Dhalls' effect (see below)
- recently shown to be competitive with partitioning
- interactions with memory cache are subject to hot debate
``Dhall Effect'' with EDF/DM Scheduling on MP
This is only a problem when we have some tasks with very high local
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
Find a lower bound μ on the workload of a
window leading up to a deadline that is necessary for the deadline
to be missed.
Find an upper bound β on the workload of such a window
that can be generated by a given task set.
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
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