Расписание лотереи

лотереи — это вероятностный алгоритм планирования процессов Планирование в операционной системе . Каждому процессу назначается некоторое количество лотерейных билетов , и планировщик вытягивает случайный билет для выбора следующего процесса. Распределение билетов не обязательно должно быть равномерным; Предоставление процессу большего количества билетов дает ему относительно более высокие шансы на выбор. Этот метод можно использовать для аппроксимации других алгоритмов планирования , таких как Следующая короткая работа и справедливое распределение .

Планирование лотерей решает проблему голода . Предоставление каждому процессу хотя бы одного лотерейного билета гарантирует, что он имеет ненулевую вероятность быть выбранным при каждой операции планирования.

Выполнение

Реализации планирования лотереи должны учитывать, что миллиарды билетов могут быть распределены по большому пулу потоков . Иметь массив , в котором каждый индекс представляет билет, а каждое место содержит поток, соответствующий этому билету, может оказаться крайне неэффективным. Планирование лотереи может быть упреждающим или неупреждающим.

Внешние ссылки

• Планирование лотереи: гибкое пропорциональное управление ресурсами, Карл А. Вальдспургер и Уильям Э. Вейль. Конференция по проектированию и внедрению операционных систем 1994 года (OSDI '94). Ноябрь 1994 года. Монтерей, Калифорния.
• Лотерея и планирование шагов: гибкое пропорциональное управление ресурсами, Карл А. Вальдспургер. доктор философии диссертация, Массачусетский технологический институт. Сентябрь 1995 года.
• Операционные системы: три простых пьесы Ремзи Х. Арпачи-Дюссо и Андреа К. Арпачи-Дюссо. Arpaci-Dusseau Books, 2014. Соответствующая глава: Планирование пропорционального распределения акций .
• Реализация планирования лотереи – соответствие специализации традиционных планировщиков – статья Дэвида Петру и др.
• Планировщик задач на основе стохастического приоритета Роберта В. Велланда и Уолтера Р. Смита. Номер патента США US 5247677 A.