Space-efficient scheduling of stochastically generated tasks

作者：Brazdil Tomas; Esparza Javier^*; Kiefer Stefan; Luttenberger Michael

来源：Information and Computation, 2012, 210: 87-110.

DOI：10.1016/j.ic.2011.10.005

• Stochastic models
• Space-efficient scheduling
• Multithreaded programs
• Branching processes

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. other tasks. 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 investigate the expected value E[S-sigma].

• 出版日期2012-1