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