Space-efficient scheduling of stochastically generated tasks

Logo poskytovatele

Varování

Publikace nespadá pod Filozofickou fakultu, ale pod Fakultu informatiky. Oficiální stránka publikace je na webu muni.cz.
Autoři

BRÁZDIL Tomáš ESPARZA Javier KIEFER Stefan LUTTENBERGER Michael

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

Fakulta informatiky

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:

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.