Space-Efficient Scheduling of Stochastically Generated Tasks

Stefan Kiefer (Technische Universität München)

Info

Date	29th April 2009 (week 1, Trinity Term 2009)
Time	11:30
Place	Room 478, Oxford University Computing Laboratory

Abstract

We study the problem of scheduling tasks for execution by a processor when the tasks can stochastically generate new tasks. Tasks can be of different types, and each type has a fixed, known probability of generating d tasks for each number d. We present results on the random variable S^sigma modeling the maximal space needed by the processor to store the currently active tasks when acting under the scheduler sigma. We obtain tail bounds for the distribution of S^sigma for both offline and online schedulers, and also bounds on the expectation of S^sigma.