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: |