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

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

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

Реализация

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

Смотрите также

• Планирование (вычисление)

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

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