Round-robin (алгоритм)

Round-robin — алгоритм распределения нагрузки распределённой вычислительной системы методом перебора её элементов по круговому циклу.

Суть алгоритма

Пусть имеется N объектов, способных выполнить заданное действие, и M задач, которые должны быть выполнены этими объектами. Подразумевается, что объекты n равны по своим свойствам между собой, задачи m имеют равный приоритет. Тогда первая задача (m = 1) назначается для выполнения первому объекту (n = 1), вторая — второму и т. д., до достижения последнего объекта (m = M). Тогда следующая задача (m = N+1) будет назначена снова первому объекту и т. п. Проще говоря, происходит перебор выполняющих задания объектов по циклу, или по кругу (round), и по достижении последнего объекта следующая задача будет также назначена первому объекту. Решение задач может быть дополнительно разбито на кванты времени, причем для продолжения решения во времени нумерация объектов (и, соответственно, назначенные задачи) сдвигается по кругу на 1, то есть задача первого объекта отдается второму, второго — третьему, и т. д., а первый объект получает задачу последнего, либо освобождается для приема новой задачи. Таким образом, алгоритм Round-robin становится алгоритмом распределения времени или балансировки нагрузки.

Применение

• балансировка нагрузки вычислительных сетей (см. Round robin DNS)
• управление задачами в системах с распределением времени (см. Round-robin scheduling)
• коллективная игра в написании книг, вышивке и иных хобби (см. Round-robin (игра))

История термина

Подробнее см. английский текст.

Термин Round-robin обозначает письмо к одному адресату, подписанное несколькими корреспондентами, к примеру, общественное обращение к должностному лицу. Название произошло, видимо, в XVII столетии, от французского выражения «ruban rond» (round ribbon, переплетенные в обруч ленты). Таким образом определялся порядок подписания коллективных петиций и ходатайств без соблюдения иерархии подписавшихся, при котором подписи располагались кружком, с тем, чтобы было невозможно найти автора или зачинщика, подписавшегося первым, своеобразная круговая порука.

Часто выражение round-robin приобретает противоположный смысл, то есть письмо от одного автора ко многим адресатам, однако такое письмо правильнее называть циркуляром.