Just as a note as to where the idea of 'deadlines' came up in my work.
I've been working on a Scheme version of the RAP System, which is a
(high level) task execution scheduler, where tasks can be annotated with
priorities, deadlines, start times, and different methods for achieving
the same goal (and other good stuff like constraints and preconditions).
Anyway, the RAP System is not a 'real time system' in the sense that
real time people use the term.

The default procedure for choosing which task to execute in the RAP
System is something like:

-- choose ones which are runnable,
-- of these, choose ones with highest priority
-- of these, choose ones with earlier deadlines
-- of these, choose ones with earlier start times
-- of these, choose ones (within the same 'family' of tasks) that have
failed the fewest number of times

I started building the RAP System on top of MzScheme's thread system,
but this failed--MzScheme's threads don't have priorities, and also I
found inconsistent behavior among the platforms MzScheme runs on (not
surprising, since MzScheme uses the native thread system where
possible). I was also trying to map RAP tasks a little too closely to
threads, and remain compatible to a Common Lisp version, etc. etc. So,
I've been porting the original CL scheduler code to Scheme.