Что такое планирование самого короткого задания?
Shortest Job First (SJF) - это алгоритм, в котором процесс, имеющий наименьшее время выполнения, выбирается для следующего выполнения. Этот метод планирования может быть упреждающим или не вытесняющим. Это значительно сокращает среднее время ожидания для других процессов, ожидающих выполнения. Полная форма SJF - сначала кратчайшая работа.
Существует два основных типа методов SJF:
- Непредвиденный SJF
- Превентивный SJF
В этом руководстве по операционной системе вы узнаете:
- Что такое планирование самого короткого задания?
- Характеристики SJF Scheduling
- Непредвиденный SJF
- Превентивный SJF
- Преимущества SJF
- Недостатки / минусы SJF
Характеристики SJF Scheduling
- Он связан с каждой работой как единица времени для завершения.
- Этот метод алгоритма полезен для пакетной обработки, когда ожидание завершения задания не критично.
- Это может повысить пропускную способность процесса, убедившись, что в первую очередь выполняются более короткие задания, следовательно, возможно, они имеют короткий срок выполнения.
- Это улучшает объем работ, предлагая более короткие задания, которые должны быть выполнены в первую очередь, у которых обычно более короткий срок выполнения.
Непредвиденный SJF
При планировании без вытеснения, как только цикл ЦП выделяется процессу, процесс удерживает его до тех пор, пока он не достигнет состояния ожидания или не завершится.
Рассмотрим следующие пять процессов, каждый из которых имеет свое уникальное время пачки и время прибытия.
| Очередь процесса | Время взрыва | Время прибытия |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Шаг 0) В момент времени = 0 прибывает P4 и начинает выполнение.
Шаг 1) В момент времени = 1 наступает процесс P3. Но для завершения P4 все еще требуется 2 исполнительных блока. Он продолжит выполнение.
Шаг 2) В момент времени = 2 прибывает процесс P1 и добавляется в очередь ожидания. P4 продолжит выполнение.
Шаг 3) В момент времени 3 процесс P4 завершит свое выполнение. Сравнивается время пакета P3 и P1. Процесс P1 выполняется, потому что его время пакета меньше по сравнению с P3.
Шаг 4) В момент времени = 4 прибывает процесс P5 и добавляется в очередь ожидания. P1 продолжит выполнение.
Шаг 5) В момент времени = 5 прибывает процесс P2, который добавляется в очередь ожидания. P1 продолжит выполнение.
Шаг 6) В момент времени = 9 процесс P1 завершит свое выполнение. Сравнивается время пакета P3, P5 и P2. Процесс P2 выполняется, потому что у него наименьшее время пакета.
Шаг 7) В момент времени = 10 P2 выполняется, а P3 и P5 находятся в очереди ожидания.
Шаг 8) В момент времени = 11 процесс P2 завершит свое выполнение. Сравнивается время пакета P3 и P5. Процесс P5 выполняется, потому что его время пакета меньше.
Шаг 9) В момент времени = 15 процесс P5 завершит свое выполнение.
Шаг 10) В момент времени = 23 процесс P3 завершит свое выполнение.
Шаг 11) Рассчитаем среднее время ожидания для приведенного выше примера.
Wait timeP4= 0-0=0P1= 3-2=1P2= 9-5=4P5= 11-4=7P3= 15-1=14
Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2
Превентивный SJF
При упреждающем планировании SJF задания помещаются в очередь готовности по мере их поступления. Начинается выполнение процесса с самым коротким временем пакета. Если поступает процесс с даже более коротким временем пакетной передачи, текущий процесс удаляется или прерывается из выполнения, а более короткому заданию выделяется цикл ЦП.
Рассмотрим следующие пять процессов:
| Очередь процесса | Время взрыва | Время прибытия |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Шаг 0) В момент времени = 0 прибывает P4 и начинает выполнение.
| Очередь процесса | Время взрыва | Время прибытия |
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Шаг 1) В момент времени = 1 наступает процесс P3. Но у P4 более короткое время всплеска. Он продолжит выполнение.
Шаг 2) В момент времени = 2 прибывает процесс P1 с временем пакета = 6. Время пакета больше, чем у P4. Следовательно, P4 продолжит выполнение.
Шаг 3) В момент времени 3 процесс P4 завершит свое выполнение. Сравнивается время пакета P3 и P1. Процесс P1 выполняется, потому что его пакетное время меньше.
Шаг 4) В момент времени = 4 прибудет процесс P5. Сравнивается время пакета P3, P5 и P1. Процесс P5 выполняется, потому что у него наименьшее время пакета. Процесс P1 выгружен.
| Очередь процесса | Время взрыва | Время прибытия |
| P1 | Осталось 5 из 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Шаг 5) В момент времени = 5 прибудет процесс P2. Сравнивается время пакета P1, P2, P3 и P5. Процесс P2 выполняется, потому что у него наименьшее время пакета. Процесс P5 выгружен.
| Очередь процесса | Время взрыва | Время прибытия |
| P1 | Осталось 5 из 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | Осталось 3 из 4 | 4 |
Шаг 6) В момент времени = 6 выполняется P2.
Шаг 7) В момент времени = 7 P2 завершает свое выполнение. Сравнивается время пакета P1, P3 и P5. Процесс P5 выполняется, потому что его пакетное время меньше.
| Очередь процесса | Время взрыва | Время прибытия |
| P1 | Осталось 5 из 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | Осталось 3 из 4 | 4 |
Шаг 8) В time = 10 P5 завершит свое выполнение. Сравнивается время пакета P1 и P3. Процесс P1 выполняется, потому что его пакетное время меньше.
Шаг 9) В момент времени = 15 P1 завершает свое выполнение. P3 - единственный оставшийся процесс. Начнется выполнение.
Шаг 10) В момент времени = 23 P3 завершает свое выполнение.
Шаг 11) Рассчитаем среднее время ожидания для приведенного выше примера.
Wait timeP4= 0-0=0P1= (3-2) + 6 =7P2= 5-5 = 0P5= 4-4+2 =2P3= 15-1 = 14
Average Waiting Time = 0+7+0+2+14/5 = 23/5 =4.6
Преимущества SJF
Вот преимущества / преимущества использования метода SJF:
- SJF часто используется для долгосрочного планирования.
- Это сокращает среднее время ожидания по алгоритму FIFO (First in First Out).
- Метод SJF дает наименьшее среднее время ожидания для определенного набора процессов.
- Это подходит для заданий, выполняемых в пакетном режиме, время выполнения которых известно заранее.
- Для пакетной системы долгосрочного планирования оценка времени пакета может быть получена из описания работы.
- Для краткосрочного планирования нам необходимо спрогнозировать значение времени следующего пакета.
- Вероятно оптимально по среднему сроку выполнения работ.
Недостатки / минусы SJF
Вот некоторые недостатки / минусы алгоритма SJF:
- Время выполнения задания должно быть известно раньше, но его трудно предсказать.
- Он часто используется в пакетной системе для долгосрочного планирования.
- SJF не может быть реализован для планирования работы ЦП в краткосрочной перспективе. Это связано с тем, что не существует специального метода для прогнозирования продолжительности предстоящего всплеска ЦП.
- Этот алгоритм может вызвать очень долгое время обработки или голодание.
- Требуется знание того, как долго будет выполняться процесс или задание.
- Это приводит к голоданию, что не сокращает средний срок выполнения работ.
- Трудно узнать длину предстоящего запроса ЦП.
- Прошедшее время должно быть записано, что приведет к увеличению нагрузки на процессор.
Резюме
- SJF - это алгоритм, в котором для следующего выполнения выбирается процесс с наименьшим временем выполнения.
- Планирование SJF связано с каждым заданием как единица времени для выполнения.
- Этот метод алгоритма полезен для пакетной обработки, когда ожидание завершения задания не критично.
- Существует два основных типа методов SJF: 1) Non-Preemptive SJF и 2) Preemptive SJF.
- При планировании без вытеснения, как только цикл ЦП выделяется для процесса, процесс удерживает его до тех пор, пока он не достигнет состояния ожидания или не завершится.
- При упреждающем планировании SJF задания помещаются в очередь готовности по мере их поступления.
- Хотя начинается процесс с коротким пакетным временем, текущий процесс удаляется или прерывается из выполнения, а задание, которое короче, выполняется первым.
- SJF часто используется для долгосрочного планирования.
- Это сокращает среднее время ожидания по алгоритму FIFO (First in First Out).
- При планировании SJF время завершения задания должно быть известно раньше, но его трудно предсказать.
- SJF не может быть реализован для планирования работы ЦП в краткосрочной перспективе. Это связано с тем, что не существует специального метода для прогнозирования продолжительности предстоящего всплеска ЦП.