Lotteri schemaläggning
Lotterischemaläggning är en probabilistisk schemaläggningsalgoritm för processer i ett operativsystem . Processer tilldelas var och en ett antal lotter och schemaläggaren drar en slumpmässig lott för att välja nästa process. Fördelningen av biljetter behöver inte vara enhetlig; att bevilja en process fler biljetter ger den en relativt högre chans att väljas. Den här tekniken kan användas för att approximera andra schemaläggningsalgoritmer, till exempel Shortest job next och Fair-share scheduling .
Lotteri schemaläggning löser problemet med svält . Att ge varje process minst en lott garanterar att den har en sannolikhet som inte är noll att väljas vid varje schemaläggningsoperation.
Genomförande
Implementering av lotterischemaläggning bör ta hänsyn till att det kan finnas miljarder lotter fördelade på en stor pool av trådar. Att ha en array där varje index representerar en biljett, och varje plats innehåller tråden som motsvarar den biljetten, kan vara mycket ineffektivt. Lotterischemaläggning kan vara förebyggande eller icke-förebyggande.
externa länkar
- Lotterischemaläggning: Flexibel proportionell resurshantering av Carl A. Waldspurger och William E. Weihl. Konferensen för design och implementering av operativsystem 1994 (OSDI '94). November 1994. Monterey, Kalifornien.
- Lotteri- och stegplanering: Flexibel resurshantering med proportionell andel av Carl A. Waldspurger. Ph.D. avhandling, Massachusetts Institute of Technology. september 1995.
- Operativsystem: Three Easy Pieces av Remzi H. Arpaci-Dusseau och Andrea C. Arpaci-Dusseau. Arpaci-Dusseau Books, 2014. Relevant kapitel: Proportional-Share Scheduling .
- Implementera lotterischemaläggning - Matcha specialiseringen på traditionella schemaläggare - Papper av David Petrou et al.
- Stokastisk prioritetsbaserad uppgift Scheduler av Robert V. Welland och Walter R. Smith. USA-patentnummer US 5247677 A