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

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

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

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

Применение

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

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

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

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

См. также

• FIFO
• SJN

К:Википедия:Статьи без источников (тип: не указан)

Отрывок, характеризующий Round-robin (алгоритм)

Был осенний, теплый, дождливый день. Небо и горизонт были одного и того же цвета мутной воды. То падал как будто туман, то вдруг припускал косой, крупный дождь.
На породистой, худой, с подтянутыми боками лошади, в бурке и папахе, с которых струилась вода, ехал Денисов. Он, так же как и его лошадь, косившая голову и поджимавшая уши, морщился от косого дождя и озабоченно присматривался вперед. Исхудавшее и обросшее густой, короткой, черной бородой лицо его казалось сердито.
Рядом с Денисовым, также в бурке и папахе, на сытом, крупном донце ехал казачий эсаул – сотрудник Денисова.
Эсаул Ловайский – третий, также в бурке и папахе, был длинный, плоский, как доска, белолицый, белокурый человек, с узкими светлыми глазками и спокойно самодовольным выражением и в лице и в посадке. Хотя и нельзя было сказать, в чем состояла особенность лошади и седока, но при первом взгляде на эсаула и Денисова видно было, что Денисову и мокро и неловко, – что Денисов человек, который сел на лошадь; тогда как, глядя на эсаула, видно было, что ему так же удобно и покойно, как и всегда, и что он не человек, который сел на лошадь, а человек вместе с лошадью одно, увеличенное двойною силою, существо.
Немного впереди их шел насквозь промокший мужичок проводник, в сером кафтане и белом колпаке.
Немного сзади, на худой, тонкой киргизской лошаденке с огромным хвостом и гривой и с продранными в кровь губами, ехал молодой офицер в синей французской шинели.
Рядом с ним ехал гусар, везя за собой на крупе лошади мальчика в французском оборванном мундире и синем колпаке. Мальчик держался красными от холода руками за гусара, пошевеливал, стараясь согреть их, свои босые ноги, и, подняв брови, удивленно оглядывался вокруг себя. Это был взятый утром французский барабанщик.
Сзади, по три, по четыре, по узкой, раскиснувшей и изъезженной лесной дороге, тянулись гусары, потом казаки, кто в бурке, кто во французской шинели, кто в попоне, накинутой на голову. Лошади, и рыжие и гнедые, все казались вороными от струившегося с них дождя. Шеи лошадей казались странно тонкими от смокшихся грив. От лошадей поднимался пар. И одежды, и седла, и поводья – все было мокро, склизко и раскисло, так же как и земля, и опавшие листья, которыми была уложена дорога. Люди сидели нахохлившись, стараясь не шевелиться, чтобы отогревать ту воду, которая пролилась до тела, и не пропускать новую холодную, подтекавшую под сиденья, колени и за шеи. В середине вытянувшихся казаков две фуры на французских и подпряженных в седлах казачьих лошадях громыхали по пням и сучьям и бурчали по наполненным водою колеям дороги.