Алгоритм циклического планирования с примером

Автор: Натаниэль Брукс Натаниэль Брукс
Hours обновлено

⚡ Умное резюме

Алгоритм циклического планирования (Round-Robin Scheduling) — это самый старый и простейший алгоритм вытеснения ЦП, при котором каждый готовый процесс выполняется в течение фиксированного промежутка времени в циклической очереди, обеспечивая справедливое выполнение без «голодания» при многозадачности.

  • 🔄 Определение: Каждая готовая задача выполняется по очереди в течение фиксированного промежутка времени.
  • 🇧🇷 Квант времени: Процессор переключается между процессами через фиксированный интервал времени, называемый квантом времени.
  • ️ Корректность: Каждому процессу выделяется одинаковое процессорное время, что позволяет избежать «голодания» ресурсов.
  • 🧮 Превентивные меры: Прерванный процесс перемещается в конец очереди.
  • ✅ Преимущества: Справедливое распределение ресурсов, отсутствие эффекта конвоя, предсказуемое время реагирования.
  • ⚠️ Недостатки: Производительность зависит от временного кванта и добавляет накладные расходы на переключение контекста.
Читать

Алгоритм кругового планирования

Что такое циклическое планирование?

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

В алгоритме циклического планирования каждая готовая задача выполняется по очереди только в циклической очереди в течение ограниченного промежутка времени. Этот алгоритм также обеспечивает выполнение процессов без возникновения «голодания» (зависания задач).

Характеристики циклического планирования

Вот важные характеристики циклического планирования:

  • Алгоритм Round Robin — это алгоритм с вытеснением.
  • Процессор переключается на следующий процесс через фиксированный промежуток времени, который называется временным квантом/временным срезом.
  • Вытесняемый процесс добавляется в конец очереди.
  • Модель циклического распределения нагрузки (Round Robin) — это гибридная модель, работающая на основе тактового сигнала.
  • Временной интервал должен быть минимальным и выделяться для конкретной задачи, которую необходимо обработать. Однако он может отличаться в зависимости от операционной системы.
  • Это алгоритм реального времени, который реагирует на событие в течение определенного временного интервала.
  • Алгоритм кругового распределения — один из старейших, самых справедливых и простых алгоритмов.
  • Это широко используемый метод планирования в традиционных операционных системах.

Пример циклического планирования

Рассмотрим следующие три процесса:

Очередь процесса Время взрыва
P1 4
P2 3
P3 5

Круговое планирование

Шаг 1) Выполнение начинается с процесса P1, время пакета которого равно 4. Здесь каждый процесс выполняется в течение 2 секунд. P2 и P3 все еще находятся в очереди ожидания.

Круговое планирование

Шаг 2) В момент времени = 2, P1 добавляется в конец очереди, и P2 начинает выполнение.

Круговое планирование

СТАТЬИ ПО ТЕМЕ

Шаг 3) В момент времени = 4, выполнение задачи P2 прерывается, и задача P3 добавляется в конец очереди.

Круговое планирование

Шаг 4) В момент времени = 6, выполнение задачи P3 прерывается, и задача P1 добавляется в конец очереди.

Круговое планирование

Шаг 5) В момент времени = 8, время выполнения P1 составляет 4. Выполнение завершено. P2 начинает выполнение.

Круговое планирование

Шаг 6) P2 имеет время выполнения 3. Он уже выполнился в течение 2 интервалов. В момент времени = 9 P2 завершает выполнение. Затем P3 начинает выполнение до своего завершения.

Круговое планирование

Шаг 7) Давайте рассчитаем среднее время ожидания для приведенного выше примера.

Wait time
P1 = 0 + 4 = 4
P2 = 2 + 4 = 6
P3 = 4 + 3 = 7

Преимущества циклического планирования

Вот преимущества и достоинства метода планирования по принципу «кругового распределения»:

  • Она не сталкивается с проблемами голода или эффекта конвоя.
  • Все задания получают справедливое распределение ресурсов ЦП.
  • Она рассматривает все процессы без указания приоритетов.
  • Если вы знаете общее количество процессов в очереди выполнения, вы также можете предположить наихудшее время ответа для того же процесса.
  • Этот метод планирования не зависит от времени выполнения задачи. Именно поэтому его легко реализовать в системе.
  • Как только процесс выполняется в течение определенного периода времени, процесс вытесняется, и в течение этого заданного периода времени выполняется другой процесс.
  • Позволяет операционной системе использовать метод переключения контекста для сохранения состояний вытесненных процессов.
  • Он обеспечивает наилучшую производительность с точки зрения среднего времени отклика.

Недостатки циклического планирования

Вот недостатки/минусы использования алгоритма циклического планирования:

  • Если время обработки данных операционной системой невелико, производительность процессора снизится.
  • Этот метод уделяет больше времени переключению контекста.
  • Его производительность во многом зависит от кванта времени.
  • Для процессов невозможно установить приоритеты.
  • Круговое планирование не отдает приоритет более важным задачам.
  • Это снижает понимание.
  • Меньший временной квант приводит к увеличению накладных расходов на переключение контекста в системе.
  • Определение корректного временного кванта в этой системе — довольно сложная задача.

Задержка в худшем случае

Этот термин используется для обозначения максимального времени, затраченного на выполнение всех задач.

  • dt = Обозначает время обнаружения, когда задача добавляется в список.
  • st = Обозначает время переключения с одной задачи на другую
  • et = Обозначает время выполнения задачи

Формула:

Tworst = {(dti+ sti + eti ), + (dti+ sti + eti )2 +...+ (dti+ sti + eti )N., + (dti+ sti + eti  + eti) N} + tISR
tISR = sum of all execution times

Часто задаваемые вопросы (FAQ)

Квант времени, или временной интервал, — это фиксированное время работы процессора до момента его прерывания. Слишком большой квант времени ведет себя как алгоритм «первым пришел — первым обслужен»; слишком маленький добавляет значительные накладные расходы на переключение контекста.

FCFS (First First Species — сначала первый обработчик) выполняет каждый процесс до завершения в порядке поступления и не является вытесняющим. Round Robin (раунд-роботизация) является вытесняющим: он выделяет каждому процессу фиксированный временной интервал и циклически проходит по очереди, улучшая время отклика и предотвращая блокировку других длительных заданий.

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

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

Да. Модели ИИ могут анализировать прошлые периоды пиковой нагрузки и системную нагрузку, чтобы предложить оптимальный временной интервал и корректировать его по мере изменения условий. Это позволяет лучше сбалансировать затраты на переключение контекста и время отклика, чем использование одного фиксированного значения.

Подведем итог этой публикации следующим образом: