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]

Dannenberg, “Time-Flow Concepts and Architectures For Music and Media Synchronization,” in Proceedings of the 43rd International Computer Music Conference, International Computer Music Association, 2017, pp. 104-109.

ABSTRACT. Modern real-time media-processing systems increasingly rely on software processing. Increasing speed and parallelism in multi-core and graphics processors has opened the possibility of interconnecting and running multiple applications to process audio, video, graphics, and other data. However, latency can accumulate as media move through multiple stages of processing, timing can be unpredictable, and synchronization is difficult. One solution to many of these problems is explicit and precise timing in which data and sample streams are organized and coordinated by logical time. This decouples media consistency and synchronization from real time. We call this “time flow” by analogy to data-flow systems, and describe several levels of sophistication and capability in time-flow architectures.

[Adobe Acrobat (PDF) Version]

See also “Time in Distributed Real-Time Systems.”