Two scheduling problems
Donald Varvel · 1994
Scheduling involves assigning resources to activities or tasks. Abstract scheduling problems typically involve a set of constraints cast as deadlines. The two problems addressed here are shown to have efficient on-line schedulers. The first is the single-server pinwheel problem restricted to two distinct periods. In the pinwheel problem, a task must be scheduled a certain number of times (often one) in every window of a given size. The window size is the period. The correctness proof of the scheduler, which introduces the idea of place functions, constitutes the proof of schedulability. The second problem is the multiple-resource periodic scheduling problem. Here each task is characterized by a resource-use requirement e and a period p. At each time $k\cdot p$ the task must have received $k\cdot e$ units of service, $k\in \bf N$. The solution involves the new notion of p-fairness, a proof that a p-fair schedule exists, an algorithm that produces a p-fair schedule, and a fast implementation of that algorithm.