Space-efficient scheduling of stochastically generated tasks
| Autoři | |
|---|---|
| Rok publikování | 2010 |
| Druh | Článek ve sborníku |
| Konference | Proceedings of 37th International Colloquium on Automata, Languages and Programming (ICALP 2010) |
| Fakulta / Pracoviště MU | |
| Citace | |
| Doi | http://dx.doi.org/10.1007/978-3-642-14162-1_45 |
| Obor | Informatika |
| Klíčová slova | infinite-state stochastic models; process creation; probabilistic verification |
| Popis | V článku studujeme problém plánování stochasticky generovaných úloh. Úlohy mohou být různého typu přičemž každý typ má fixní pravděpodobnost generování dalších úloh. V článku prezentujeme výsledky týkající se náhodné proměnné S^sigma, která modeluje maximální prostor, který procesor potřebuje k uložení aktivních úloh v závislosti na plánovači sigma. Prezentujeme odhady na distribuci proměnné S^sigma pro offline a online plánovače a studujeme očekávanou hodnotu proměnné S^sigma. 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 of S^sigma. |
| Související projekty: |