Space-efficient scheduling of stochastically generated tasks
| Authors | |
|---|---|
| Year of publication | 2012 |
| Type | Article in Periodical |
| Magazine / Source | Information and Computation |
| MU Faculty or unit | |
| Citation | |
| Doi | http://dx.doi.org/10.1016/j.ic.2011.10.005 |
| Field | Informatics |
| Keywords | Stochastic models; Space-efficient scheduling; Multithreaded programs; Branching processes |
| Description | 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]. |
| Related projects: |