Programação de loteria - Lottery scheduling
A programação de loteria é um algoritmo de programação probabilística para processos em um sistema operacional . Cada processo recebe um certo número de bilhetes de loteria , e o agendador tira um bilhete aleatório para selecionar o próximo processo. A distribuição de ingressos não precisa ser uniforme; conceder a um processo mais tickets fornece a ele uma chance relativamente maior de seleção. Essa técnica pode ser usada para aproximar outros algoritmos de programação , como Shortest job next e Fair-share scheduling .
A programação da loteria resolve o problema da fome . Dar a cada processo pelo menos um bilhete de loteria garante que ele tenha probabilidade diferente de zero de ser selecionado em cada operação de agendamento.
Implementação
As implementações de agendamento de loteria devem levar em consideração que pode haver bilhões de bilhetes distribuídos entre um grande conjunto de threads. Ter uma matriz em que cada índice representa um tíquete e cada local contém o encadeamento correspondente a esse tíquete pode ser altamente ineficiente. A programação da loteria pode ser preemptiva ou não preemptiva.
links externos
- Programação da loteria: Gerenciamento de recursos de compartilhamento proporcional flexível, de Carl A. Waldspurger e William E. Weihl. A conferência de Desenho e Implementação de Sistemas Operacionais de 1994 (OSDI '94). Novembro de 1994. Monterey, Califórnia.
- Lottery and Stride Scheduling: Gerenciamento de recursos de compartilhamento proporcional flexível por Carl A. Waldspurger. Ph.D. dissertação, Massachusetts Institute of Technology. Setembro de 1995.
- Sistemas operacionais: Three Easy Pieces de Remzi H. Arpaci-Dusseau e Andrea C. Arpaci-Dusseau. Arpaci-Dusseau Books, 2014. Capítulo relevante: Programação de Compartilhamento Proporcional .
- Implementing Lottery Schedulers - Matching the Specialization in Traditional Schedulers - Artigo de David Petrou et al.
- Agendador de tarefas baseado em prioridade estocástica por Robert V. Welland e Walter R. Smith. Patente dos Estados Unidos Número US 5247677 A