Лотерейное планирование

Выдача пользователям обещаний с последующим их выполнением — идея неплохая, но реализовать ее все же нелегко. Но есть и другой, более простой в реализации алгоритм, который можно использовать для получения столь же предсказуемых результатов.
Он называется лотерейным планированием (Waldspurger and Weihl, 1994).

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

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

Перефразируя Джорджа Оруэлла, можно сказать: «Все процессы равны, но некоторые из них равнее остальных». Более важным процессам, чтобы повысить их шансы на выигрыш, могут выдаваться дополнительные билеты. Если есть 100 неразыгранных билетов и один из процессов обладает двадцатью из них, то он будет иметь 20 %-ную вероятность выигрыша в каждой лотерее. В конечном счете он получит около 20 % процессорного времени. В отличие от приоритетного планирования, где очень трудно сказать, что на самом деле означает приоритет со значением 40, здесь действует вполне определенное правило: процесс, имеющий долю из / билетов, получит примерно / долей рассматриваемого ресурса.

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

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

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

<< | >>
Источник: Э. ТАНЕНБАУМ Х. БОС. СОВРЕМЕННЫЕ ОПЕРАЦИОННЫЕ СИСТЕМ Ы 4-е ИЗДАНИЕ. 2015

Еще по теме Лотерейное планирование:

  1. Планирование телепередач
  2. Планирование, а не планы
  3. 11. КРИМИНАЛИСТИЧЕСКИЕ ВЕРСИИ И ПЛАНИРОВАНИЕ РАССЛЕДОВАНИЯ
  4. § 2. ПЛАНИРОВАНИЕ И СОДЕРЖАНИЕ НАБЛЮДЕНИЯ
  5. 10.2. Планирование и организация следственных действий
  6. 5.4. Планирование упражнений
  7. Искусство планирования спонтанного
  8. 5.9. Планирование социальных контактов
  9. 5.2.9. Планирование сроков достижения уже определённой цели
  10. Статья 437. Планирование, подготовка, развязывание и ведение агрессивной войны
  11. 11.3. Понятие и основные принципы планирования расследования в зависимости от исходной информации (следственной ситуации)
  12. Требуется
  13. Вопросы для самопроверки