Алгоритм планирования с приоритетами: вытесняющий, невытесняющий
Натаниэль Брукс
⚡ Умное резюме
Приоритетное планирование — это метод планирования ЦП, который выбирает процессы на основе приоритета, выполняя в первую очередь задачи с более высоким приоритетом. Оно может быть вытесняющим или невытесняющим, а процессы с одинаковым приоритетом обрабатываются по принципу «кто первый, тот и получает» или по круговой схеме.
Что такое приоритетное планирование?
Приоритетное планирование — это метод планирования процессов, основанный на приоритете. В этом алгоритме планировщик выбирает задачи для работы в соответствии с приоритетом.
Сначала должны выполняться процессы с более высоким приоритетом, тогда как задания с равным приоритетом выполняются на основе циклического перебора или FCFS. Приоритет зависит от требований к памяти, времени и т. Д.
Типы приоритетного планирования
Приоритетное планирование делится на два основных типа:
Упреждающее планирование
При упреждающем планировании задачам в основном назначаются приоритеты. Иногда важно запустить задачу с более высоким приоритетом перед другой задачей с более низким приоритетом, даже если задача с более низким приоритетом все еще выполняется. Задача с более низким приоритетом удерживается в течение некоторого времени и возобновляется, когда задача с более высоким приоритетом завершает свое выполнение.
Невытесняющее планирование
При таком методе планирования процессор выделяется конкретному процессу. Процесс, который занимает процессор, освобождает его либо путем переключения контекста, либо путем завершения работы. Это единственный метод, который может использоваться на различных аппаратных платформах, поскольку он не требует специального оборудования (например, таймера), как вытесняющее планирование.
Характеристики приоритетного планирования
- Алгоритм ЦП, который планирует процессы на основе приоритета.
- Используется в Operaсистемы для выполнения пакетных процессов.
- Если два задания с одинаковым приоритетом ГОТОВЫ, оно работает ПЕРВЫМ ПРИБЫЛ - ПЕРВЫМ ОБСЛУЖЕН ЭКВИВАЛЕНТ В РУССКОМ ЯЗЫКЕ: ПОЗДНИЙ ГОСТЬ ГЛОЖЕТ И КОСТЬ основа.
- При планировании приоритетов каждому процессу присваивается номер, указывающий его уровень приоритета.
- Чем меньше число, тем выше приоритет.
- В алгоритмах планирования такого типа, если появляется более новый процесс с более высоким приоритетом, чем текущий выполняющийся процесс, то текущий выполняющийся процесс прерывается.
Пример планирования приоритетов
Рассмотрим следующие пять процессов 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 процесс P4 завершился, и никаких процессов не осталось.
Шаг 18) Давайте рассчитаем среднее время ожидания для приведенного выше примера.
Время ожидания = время начала – время прибытия + время ожидания следующего пакета.
P1 = 0 - 0 = 0 P2 = 4 - 0 + 7 = 11 P3 = 6 - 6 = 0 P4 = 16 - 11 = 5 Average Waiting time = (0 + 11 + 0 + 5 + 2)/5 = 18/5 = 3.6
Преимущества приоритетного планирования
Вот преимущества использования метода приоритетного планирования:
- Простой в использовании метод планирования.
- Процессы выполняются в порядке приоритета, поэтому задачам с высоким приоритетом не приходится долго ждать, что экономит время.
- Этот метод предоставляет эффективный механизм, позволяющий точно определить относительную важность каждого процесса.
- Подходит для приложений с меняющимися требованиями ко времени и ресурсам.
Недостатки приоритетного планирования
Вот минусы и недостатки планирования с приоритетами:
- Если система в конечном итоге выйдет из строя, все процессы с низким приоритетом будут потеряны.
- Если процессы с высоким приоритетом занимают много процессорного времени, то процессы с более низким приоритетом могут «зависнуть» и будут отложены на неопределенное время.
- Этот алгоритм планирования может оставить некоторые процессы с низким приоритетом ожидающими на неопределенный срок.
- Процесс будет заблокирован, когда он будет готов к запуску, но ему придется ждать процессора, поскольку в данный момент выполняется какой-то другой процесс.
- Если новый процесс с более высоким приоритетом продолжает поступать в очередь готовности, то процессу, находящемуся в состоянии ожидания, возможно, придется ждать в течение длительного времени.
