Real-Time Scheduling/Dispatching

The problem is to schedule events, that is, procedure calls, at some time in the future by storing information in some data structure. When the time arrives, the record is removed from the structure and the procedure is called. A straight-forward implementation is a sorted list, which has O(N) insertion time, but these papers show how to do much better.


Back to Bibliography by Subject


Dannenberg, ``A Real Time Scheduler/Dispatcher,'' in Proceedings of the International Computer Music Conference, Computer Music Association, (September 1988), pp. 239-242.

A concise description of an algorithm for scheduling/dispatching using O(1) time. In other words, both scheduling and dispatching take constant time. These are the time-critical operations, but the algorithm also requires a certain amount of background processing. In the worst case, O(log N) background processing is required. Background processing can be preempted at any time for reasonable periods of time.

ABSTRACT: Real-time systems often spend an inordinate amount of time getting ready to do things in the future and deciding what to do next. Designating a task to be performed at some time in the future, or {\it scheduling}, and finding the next task to be run, or {\it dispatching}, typically take a total time which is linear in the number of waiting tasks. A new algorithm is presented in which the time for both scheduling and dispatching is bounded by a small constant. An additional constant load is placed on the processor, and a modest background processing load is also imposed. The new algorithm is compared to other popular real-time scheduler/dispatcher strategies.

[Postscript Version] [Adobe Acrobat (PDF) Version]


Dannenberg, ``Real-Time Scheduling and Computer Accompaniment,'' in Current Research in Computer Music, edited by Max Mathews and John Pierce, MIT Press, 1989.

This chapter is a more detailed presentation of the problems of scheduling and dispatching, including the case where you want to be able to modify a time-map against which events are scheduled. In practical terms, you want to schedule events on specified beats and then change the tempo. Finally, the chapter talks about the computer accompaniment problem, where tempo is changed to synchronize to a live performer. (See also Computer Accompaniment.)

[Adobe Acrobat (PDF) Version]


See also ``Time in Distributed Real-Time Systems.''