Plánování loterie - Lottery scheduling

Plánování loterie je pravděpodobnostní plánovací algoritmus pro procesy v operační systém. Procesům je každému přiřazen určitý počet loterijní lístky a plánovač nakreslí náhodný lístek a vybere další postup. Distribuce vstupenek nemusí být jednotná; udělení procesu více lístků mu poskytuje relativně vyšší šanci na výběr. Tuto techniku ​​lze použít k aproximaci jiného plánování algoritmy, jako Nejkratší práce další a Fair-share plánování.

Plánování loterie řeší problém hladovění. Poskytnutí každého procesu alespoň jedné loterie zaručuje, že má nenulovou pravděpodobnost, že bude vybrán při každé plánovací operaci.

Implementace

Implementace plánování loterií by měla vzít v úvahu, že mezi velkou skupinou vláken mohou být distribuovány miliardy tiketů. Mít pole, kde každý index představuje lístek a každé umístění obsahuje vlákno odpovídající tomuto lístku, může být vysoce neefektivní. Plánování loterie může být preventivní i nepreventivní.

Viz také

• Plánování (výpočet)

externí odkazy

• Loterie Scheduling: Flexibilní proporcionální sdílení zdrojů Carl A. Waldspurger a William E. Weihl. Konference o návrhu a implementaci operačních systémů z roku 1994 (OSDI '94). Listopad 1994. Monterey, Kalifornie.
• Loterie a plánování kroků: Flexibilní správa zdrojů proporcionálním sdílením Carl A. Waldspurger. Ph.D. disertační práce, Massachusetts Institute of Technology. Září 1995.
• Operační systémy: Tři snadné kousky předložili Remzi H. Arpaci-Dusseau a Andrea C. Arpaci-Dusseau. Arpaci-Dusseau Books, 2014. Relevantní kapitola: Plánování proporcionálního sdílení.
• Implementace loterijního plánování - sladění se specializací na tradiční plánovače - Příspěvek Davida Petrou a kol.
• Plánovač úloh se stochastickou prioritou Robert V. Welland a Walter R. Smith. Patent USA číslo 5247677 A