A Real Time Scheduler/Dispatcher

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 scheduling, and finding the next task to be run, or 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 mod- est background processing load is also imposed. The new algorithm is compared to other popular real-time scheduler/dispatcher strategies.