Алгоритм приоритетного планирования: упреждающий, невытесняющий ПРИМЕР

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

Приоритетное планирование — это метод планирования процессов, основанный на приоритете. В этом алгоритме планировщик выбирает задачи для работы в соответствии с приоритетом.

Сначала должны выполняться процессы с более высоким приоритетом, тогда как задания с равным приоритетом выполняются на основе циклического перебора или FCFS. Приоритет зависит от требований к памяти, времени и т. Д.

Типы приоритетного планирования

Приоритетное планирование делится на два основных типа:

Упреждающее планирование

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

Невытесняющее планирование

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

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

  • Алгоритм ЦП, который планирует процессы на основе приоритета.
  • Он использовался в Operaсистемы для выполнения пакетных процессов.
  • Если два задания с одинаковым приоритетом ГОТОВЫ, оно работает ПЕРВЫМ ПРИБЫЛ - ПЕРВЫМ ОБСЛУЖЕН ЭКВИВАЛЕНТ В РУССКОМ ЯЗЫКЕ: ПОЗДНИЙ ГОСТЬ ГЛОЖЕТ И КОСТЬ основа.
  • При планировании приоритетов каждому процессу присваивается номер, указывающий его уровень приоритета.
  • Чем меньше число, тем выше приоритет.
  • В этом типе алгоритма планирования, если прибывает новый процесс, имеющий более высокий приоритет, чем текущий процесс, то текущий процесс вытесняется.

Пример планирования приоритетов

Рассмотрим следующееwing пять процессов от P1 до P5. Каждый процесс имеет свой уникальный приоритет, время пакета и время прибытия.

Обработка приоритет Время взрыва Время прибытия
P1 1 4 0
P2 2 3 0
P3 1 7 6
P4 3 4 11
P5 2 2 12

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

Приоритетное планирование

Шаг 1) В момент времени = 1 новый процесс не поступает. Выполнение продолжается с P1.

Приоритетное планирование

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

Приоритетное планирование

Шаг 3) В момент времени 3 новый процесс не поступает, поэтому вы можете продолжить с P1. Процесс P2 все еще находится в очереди ожидания.

Приоритетное планирование

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

Приоритетное планирование

Шаг 5) В момент времени = 5 новый процесс не поступает, поэтому мы продолжаем с P2.

Приоритетное планирование

Шаг 6) В момент времени=6 прибывает P3. P3 имеет более высокий приоритет (1) по сравнению с P2, имеющим приоритет (2). P2 вытесняется, и P3 начинает свое выполнение.

Обработка приоритет Время взрыва Время прибытия
P1 1 4 0
P2 2 1 из 3 на рассмотрении 0
P3 1 7 6
P4 3 4 11
P5 2 2 12

Приоритетное планирование

Шаг 7) В время 7, новый процесс не поступает, поэтому мы продолжаем с P3. P2 находится в очереди ожидания.

Приоритетное планирование

Шаг 8) В момент времени = 8 новый процесс не поступает, поэтому мы можем продолжить с P3.

Приоритетное планирование

Шаг 9) В момент времени = 9 новых процессов не происходит, поэтому мы можем продолжить с P3.

Приоритетное планирование

Шаг 10) На интервале времени 10 новых процессов не происходит, поэтому мы продолжаем с P3.

Приоритетное планирование

Шаг 11) В момент времени = 11 P4 прибывает с приоритетом 4. P3 имеет более высокий приоритет, поэтому он продолжает выполнение.

Обработка приоритет Время взрыва Время прибытия
P1 1 4 0
P2 2 1 из 3 на рассмотрении 0
P3 1 2 из 7 на рассмотрении 6
P4 3 4 11
P5 2 2 12

Приоритетное планирование

Шаг 12) В момент времени = 12 прибывает P5. P3 имеет более высокий приоритет, поэтому он продолжает выполнение.

Приоритетное планирование

Шаг 13) В момент времени = 13 P3 завершает выполнение. У нас есть P2,P4,P5 в очереди готовности. P2 и P5 имеют одинаковый приоритет. Время прибытия P2 раньше P5. Итак, P2 начинает выполнение.

Обработка приоритет Время взрыва Время прибытия
P1 1 4 0
P2 2 1 из 3 на рассмотрении 0
P3 1 7 6
P4 3 4 11
P5 2 2 12

Приоритетное планирование

Шаг 14) В момент времени =14 процесс P2 завершил свое выполнение. P4 и P5 находятся в состоянии ожидания. P5 имеет наивысший приоритет и начинает выполнение.

Приоритетное планирование

Шаг 15) В момент времени =15 P5 продолжает выполнение.

Приоритетное планирование

Шаг 16) В момент времени = 16 выполнение P5 завершается. P4 — единственный оставшийся процесс. Он начинает выполнение.

Приоритетное планирование

Шаг 17) В момент времени =20 P5 завершил выполнение, и ни одного процесса не осталось.

Приоритетное планирование

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

Время ожидания = время начала – время прибытия + время ожидания следующего пакета.

P1 = o - o = o
P2 =4 - o + 7 =11	
P3= 6-6=0
P4= 16-11=5
Average Waiting time = (0+11+0+5+2)/5 = 18/5= 3.6

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

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

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

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

Вот минусы/недостатки приоритетного планирования.

  • Если система в конечном итоге выйдет из строя, все процессы с низким приоритетом будут потеряны.
  • Если процессы с высоким приоритетом занимают много процессорного времени, то процессы с более низким приоритетом могут «зависнуть» и будут отложены на неопределенное время.
  • Этот алгоритм планирования может оставить некоторые процессы с низким приоритетом ожидающими на неопределенный срок.
  • Процесс будет заблокирован, когда он будет готов к запуску, но ему придется ждать процессора, поскольку в данный момент выполняется какой-то другой процесс.
  • Если новый процесс с более высоким приоритетом продолжает поступать в очередь готовности, то процессу, находящемуся в состоянии ожидания, возможно, придется ждать в течение длительного времени.

Итого

  • Приоритетное планирование — это метод планирования процессов, основанный на приоритете. В этом алгоритме планировщик выбирает задачи для работы в соответствии с приоритетом.
  • При приоритетном упреждающем планировании задачам в основном назначаются их приоритеты.
  • В методе приоритетного невытесняющего планирования процессор выделяется конкретному процессу.
  • Процессы выполняются на основе приоритета, поэтому высокий приоритет не требует длительного ожидания, что экономит время.
  • Если процессы с высоким приоритетом занимают много процессорного времени, то процессы с более низким приоритетом могут «зависнуть» и будут отложены на неопределенное время.