Планировщик процессов планирует различные процессы, которые должны быть назначены ЦПУ на основе определенных алгоритмов планирования. Существует шесть популярных алгоритмов планирования процессов, которые мы собираемся обсудить в этой главе:
- Планирование «первым пришел — первым обслужен» (FCFS)
- Планирование Shortest-Job-Next (SJN)
- Приоритетное планирование
- Самое короткое оставшееся время
- Круглый Робин (RR) Планирование
- Планирование многоуровневых очередей
Эти алгоритмы являются либо не вытесняющими, ни вытесняющими . Непрерывающие алгоритмы разработаны таким образом, что, как только процесс входит в рабочее состояние, он не может быть прерван до тех пор, пока не завершит свое выделенное время, тогда как упреждающее планирование основано на приоритете, когда планировщик может выгрузить процесс с низким приоритетом в любое время, когда высокий приоритет процесс переходит в состояние готовности.
First Come First Serve (FCFS)
- Задания выполняются в порядке поступления.
- Это не упреждающий, упреждающий алгоритм планирования.
- Легко понять и реализовать.
- Его реализация основана на очереди FIFO.
- Низкая производительность, так как среднее время ожидания велико.
Время ожидания каждого процесса выглядит следующим образом —
| Процесс | Время ожидания: Время обслуживания — Время прибытия |
|---|---|
| P0 | 0 — 0 = 0 |
| P1 | 5 — 1 = 4 |
| P2 | 8 — 2 = 6 |
| P3 | 16 — 3 = 13 |
Среднее время ожидания: (0 + 4 + 6 + 13) / 4 = 5,75
Кратчайшая работа следующая (SJN)
-
Это также называется первой короткой работой , или SJF
-
Это не упреждающий, упреждающий алгоритм планирования.
-
Лучший подход для минимизации времени ожидания.
-
Легко реализовать в пакетных системах, где необходимое время процессора известно заранее.
-
Невозможно реализовать в интерактивных системах, где необходимое время ЦП неизвестно.
-
Процессор должен заранее знать, сколько времени займет процесс.
Это также называется первой короткой работой , или SJF
Это не упреждающий, упреждающий алгоритм планирования.
Лучший подход для минимизации времени ожидания.
Легко реализовать в пакетных системах, где необходимое время процессора известно заранее.
Невозможно реализовать в интерактивных системах, где необходимое время ЦП неизвестно.
Процессор должен заранее знать, сколько времени займет процесс.
Дано: таблица процессов и время их прибытия, время выполнения
| Процесс | Время прибытия | Время исполнения | Время обслуживания |
|---|---|---|---|
| P0 | 0 | 5 | 0 |
| P1 | 1 | 3 | 5 |
| P2 | 2 | 8 | 14 |
| P3 | 3 | 6 | 8 |
Время ожидания каждого процесса выглядит следующим образом —
| Процесс | Время ожидания |
|---|---|
| P0 | 0 — 0 = 0 |
| P1 | 5 — 1 = 4 |
| P2 | 14 — 2 = 12 |
| P3 | 8 — 3 = 5 |
Среднее время ожидания: (0 + 4 + 12 + 5) / 4 = 21/4 = 5,25
Приоритетное планирование
-
Приоритетное планирование — это алгоритм без вытеснения и один из самых распространенных алгоритмов планирования в пакетных системах.
-
Каждому процессу назначается приоритет. Процесс с наивысшим приоритетом должен выполняться первым и так далее.
-
Процессы с одинаковым приоритетом выполняются по принципу «первым пришел — первым обслужен».
-
Приоритет может быть решен на основе требований к памяти, времени или любых других ресурсов.
Приоритетное планирование — это алгоритм без вытеснения и один из самых распространенных алгоритмов планирования в пакетных системах.
Каждому процессу назначается приоритет. Процесс с наивысшим приоритетом должен выполняться первым и так далее.
Процессы с одинаковым приоритетом выполняются по принципу «первым пришел — первым обслужен».
Приоритет может быть решен на основе требований к памяти, времени или любых других ресурсов.
Дано: таблица процессов, их время прибытия, время выполнения и приоритет. Здесь мы рассматриваем 1 является самым низким приоритетом.
| Процесс | Время прибытия | Время исполнения | приоритет | Время обслуживания |
|---|---|---|---|---|
| P0 | 0 | 5 | 1 | 0 |
| P1 | 1 | 3 | 2 | 11 |
| P2 | 2 | 8 | 1 | 14 |
| P3 | 3 | 6 | 3 | 5 |
Время ожидания каждого процесса выглядит следующим образом —
| Процесс | Время ожидания |
|---|---|
| P0 | 0 — 0 = 0 |
| P1 | 11 — 1 = 10 |
| P2 | 14 — 2 = 12 |
| P3 | 5 — 3 = 2 |
Среднее время ожидания: (0 + 10 + 12 + 2) / 4 = 24/4 = 6
Самое короткое оставшееся время
-
Наименьшее оставшееся время (SRT) является преимущественной версией алгоритма SJN.
-
Процессор выделяется для задания, наиболее близкого к завершению, но ему может предшествовать более новое готовое задание с более коротким временем до завершения.
-
Невозможно реализовать в интерактивных системах, где необходимое время ЦП неизвестно.
-
Он часто используется в пакетных средах, где короткие задания должны отдавать предпочтение.
Наименьшее оставшееся время (SRT) является преимущественной версией алгоритма SJN.
Процессор выделяется для задания, наиболее близкого к завершению, но ему может предшествовать более новое готовое задание с более коротким временем до завершения.
Невозможно реализовать в интерактивных системах, где необходимое время ЦП неизвестно.
Он часто используется в пакетных средах, где короткие задания должны отдавать предпочтение.
Круглый Робин Планирование
-
Round Robin — это алгоритм планирования вытесняющих процессов.
-
Каждому процессу предоставляется определенное время для выполнения, оно называется квантом .
-
Как только процесс выполняется в течение заданного периода времени, он прерывается, и другой процесс выполняется в течение заданного периода времени.
-
Переключение контекста используется для сохранения состояний вытесненных процессов.
Round Robin — это алгоритм планирования вытесняющих процессов.
Каждому процессу предоставляется определенное время для выполнения, оно называется квантом .
Как только процесс выполняется в течение заданного периода времени, он прерывается, и другой процесс выполняется в течение заданного периода времени.
Переключение контекста используется для сохранения состояний вытесненных процессов.
Время ожидания каждого процесса выглядит следующим образом —
| Процесс | Время ожидания: Время обслуживания — Время прибытия |
|---|---|
| P0 | (0 — 0) + (12 — 3) = 9 |
| P1 | (3 — 1) = 2 |
| P2 | (6 — 2) + (14 — 9) + (20 — 17) = 12 |
| P3 | (9 — 3) + (17 — 12) = 11 |
Среднее время ожидания: (9 + 2 + 12 + 11) / 4 = 8,5
Планирование многоуровневых очередей
Многоуровневые очереди не являются независимым алгоритмом планирования. Они используют другие существующие алгоритмы для группировки и планирования заданий с общими характеристиками.
- Для процессов с общими характеристиками поддерживается несколько очередей.
- Каждая очередь может иметь свои собственные алгоритмы планирования.
- Приоритеты присваиваются каждой очереди.
Например, задания, связанные с процессором, могут планироваться в одной очереди, а все задания, связанные с вводом / выводом, — в другой очереди. Затем планировщик процессов поочередно выбирает задания из каждой очереди и назначает их ЦПУ на основе алгоритма, назначенного очереди.