Providing predictable scheduling of programs using a repeating precomputed schedule

Abstract

The present invention provides predictable scheduling of programs using a repeating precomputed schedule. In a preferred embodiment, a scheduler accesses an activity scheduling graph. The activity scheduling graph is comprised of nodes each representing a recurring execution interval, and has one root, one or more leaves, and at least one path from the root to each leaf. Each node is on at least one path from the root to a leaf, and the number of times the execution interval represented by each node occurs during the traversal of the graph is equal to the number of paths from the root to a leaf that the node is on. Each node has associated with it an execution interval length, and is adapted to being dedicated to executing the threads of a single activity. The scheduler first selects a current node within the accessed scheduling graph. When the processor becomes available to execute threads, the scheduler advances from the current node to a new current node in accordance with a root-to-leaf traversal of the scheduling graph. After advancing to the new current node, the scheduler executes one or more threads of the activity to which the new current node is dedicated for the execution interval length associated with the new current node. In a further preferred embodiment, the scheduler allocates specific iterations through specific nodes to satisfy the constraints submitted by threads.