Space-Efficient Scheduling of Stochastically Generated Tasks
Stefan Kiefer ( Technische Universität München )
- 11:30 29th April 2009 ( week 1, Trinity Term 2009 )Room 478, Oxford University Computing Laboratory
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.