Алгоритм планирования "Round Robin" в вычислительных системах и сетях.
Round-robin scheduling
Планирование задач в компьютерах: алгоритм Round Robin (RR). Равномерное распределение времени между процессами, простота реализации, отсутствие "голода".
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Алгоритм, используемый планировщиками процессов и сетевыми планировщиками в вычислительных системах. Планирование в вычислительных системах.
Algorithm employed by process and network schedulers in computing
scheduling in computing
Round robin (RR) – один из алгоритмов, используемых планировщиками процессов и сетевыми планировщиками в вычислительных системах. В общем случае, каждому процессу выделяются временные интервалы (также известные как кванты времени) равной длительности в циклическом порядке, обрабатывая все процессы без приоритета (также известный как циклический режим работы). Планирование методом Round robin просто, легко реализуется и исключает ситуацию, когда процесс не получает ресурсов (предотвращает "голодание"). Этот метод может применяться для решения других задач планирования, например, планирования передачи пакетов данных в компьютерных сетях. Это концепция операционной системы. Название алгоритма происходит от принципа "каждому по очереди", известного из других областей, где каждый участник получает равную долю чего-либо поочередно.
Round robin (RR) is one of the algorithms employed by process and network schedulers in computing. As the term is generally used, time slices (also known as time quanta) are assigned to each process in equal portions and in circular order, handling all processes without priority (also known as cyclic executive). Round robin scheduling is simple, easy to implement, and starvation free. Round robin scheduling can be applied to other scheduling problems, such as data packet scheduling in computer networks. It is an operating system concept. The name of the algorithm comes from the round robin principle known from other fields, where each person takes an equal share of something in turn.
Планирование сетевых пакетов
В коммутации пакетов с наилучшими усилиями и других схемах статистического мультиплексирования, планирование методом "каждый получает по очереди" может использоваться как альтернатива очереди "первым пришел – первым обслужен". Мультиплексор, коммутатор или маршрутизатор, обеспечивающий планирование методом "каждый получает по очереди", имеет отдельную очередь для каждого потока данных, при этом поток данных может быть идентифицирован по адресам источника и назначения. Алгоритм позволяет каждому активному потоку данных, имеющему пакеты в очереди, поочередно передавать пакеты по общему каналу в периодически повторяющемся порядке. Планирование сохраняет загрузку, то есть, если в одном потоке нет пакетов, его место займет следующий поток данных. Таким образом, планирование стремится предотвратить простаивание ресурсов канала связи. Планирование методом "каждый получает по очереди" обеспечивает максимальную справедливость, если пакеты данных имеют одинаковый размер, поскольку приоритет в планировании отдается потоку данных, который ожидает дольше всего. Это может быть нежелательно, если размер пакетов данных существенно различается между разными заданиями. Пользователь, генерирующий большие пакеты, будет иметь преимущество перед другими пользователями. В этом случае предпочтительнее использовать справедливое планирование. Если предлагается гарантированное или дифференцированное качество обслуживания, а не только связь с наилучшими усилиями, следует рассмотреть планирование с дефицитом (DRR), взвешенное планирование методом "каждый получает по очереди" (WRR) или взвешенное справедливое планирование (WFQ). В сетях множественного доступа, где несколько терминалов подключены к общему физическому носителю, планирование методом "каждый получает по очереди" может обеспечиваться схемами доступа к каналу с передачей маркера, такими как Token Ring, или опросом/резервированием ресурсов с центральной станции управления. В централизованной беспроводной пакетной радиосети, где множество станций используют один частотный канал, алгоритм планирования в центральной базовой станции может резервировать временные слоты для мобильных станций методом "каждый получает по очереди", обеспечивая справедливость. Однако, если используется адаптация канала, передача определенного объема данных "дорогостоящим" пользователям займет значительно больше времени, чем другим, поскольку условия канала различаются. Было бы эффективнее подождать улучшения условий канала или, по крайней мере, отдать приоритет в планировании менее "дорогостоящим" пользователям. Планирование методом "каждый получает по очереди" не учитывает это. Более высокая пропускная способность и эффективность использования спектра системы могут быть достигнуты с помощью планирования, зависящего от канала, например, пропорционально справедливого алгоритма или планирования максимальной пропускной способности. Следует отметить, что последнее характеризуется нежелательным "голоданием" в планировании. Этот тип планирования является одним из самых базовых алгоритмов для операционных систем в компьютерах и может быть реализован с помощью структуры данных кольцевого буфера.
In best effort packet switching and other statistical multiplexing, round robin scheduling can be used as an alternative to first come first served queuing. A multiplexer, switch, or router that provides round robin scheduling has a separate queue for every data flow, where a data flow may be identified by its source and destination address. The algorithm allows every active data flow that has data packets in the queue to take turns in transferring packets on a shared channel in a periodically repeated order. The scheduling is work conserving, meaning that if one flow is out of packets, the next data flow will take its place. Hence, the scheduling tries to prevent link resources from going unused. Round robin scheduling results in max min fairness if the data packets are equally sized, since the data flow that has waited the longest time is given scheduling priority. It may not be desirable if the size of the data packets varies widely from one job to another. A user that produces large packets would be favored over other users. In that case fair queuing would be preferable. If guaranteed or differentiated quality of service is offered, and not only best effort communication, deficit round robin (DRR) scheduling, weighted round robin (WRR) scheduling, or weighted fair queuing (WFQ) may be considered. In multiple access networks, where several terminals are connected to a shared physical medium, round robin scheduling may be provided by token passing channel access schemes such as Token Ring, or by polling or resource reservation from a central control station. In a centralized wireless packet radio network, where many stations share one frequency channel, a scheduling algorithm in a central base station may reserve time slots for the mobile stations in a round robin fashion and provide fairness. However, if link adaptation is used, it will take a much longer time to transmit a certain amount of data to "expensive" users than to others since the channel conditions differ. It would be more efficient to wait with the transmission until the channel conditions are improved, or at least to give scheduling priority to less expensive users. Round robin scheduling does not utilize this. Higher throughput and system spectrum efficiency may be achieved by channel dependent scheduling, for example a proportionally fair algorithm, or maximum throughput scheduling. Note that the latter is characterized by undesirable scheduling starvation. This type of scheduling is one of the very basic algorithms for Operating Systems in computers which can be implemented through a circular queue data structure.