Какво е първото планиране на най-късата работа?
Най-краткото задание първо (SJF) е алгоритъм, при който процесът с най-малко време за изпълнение се избира за следващото изпълнение. Този метод на планиране може да бъде превантивен или непредвидителен. Това значително намалява средното време за изчакване за други процеси, които очакват изпълнение. Пълната форма на SJF е „Най-кратката работа на първо място“.
По принцип има два типа SJF методи:
- Непретенциозен SJF
- Превантивен SJF
В този урок за операционната система ще научите:
- Какво е първото планиране на най-късата работа?
- Характеристики на SJF планиране
- Непретенциозен SJF
- Превантивен SJF
- Предимства на SJF
- Недостатъци / минуси на SJF
Характеристики на SJF планиране
- Той е свързан с всяка работа като единица време за завършване.
- Този метод на алгоритъм е полезен за пакетна обработка, където изчакването на завършване на заданията не е критично.
- Той може да подобри пропускателната способност на процеса, като се увери, че първо се изпълняват по-къси задачи, поради което е възможно да има кратко време за изпълнение.
- Той подобрява резултатите от работата, като предлага по-кратки работни места, които трябва да бъдат изпълнени първо, които имат предимно по-кратко време за изпълнение.
Непретенциозен SJF
При непредварително планиране, след като цикълът на процесора е разпределен за процес, процесът го задържа, докато достигне състояние на изчакване или прекрати.
Помислете за следните пет процеса, всеки от които има свое уникално време за избухване и време на пристигане.
| Опашка за обработка | Време за спукване | Час на пристигане |
| P1 | 6 | 2 |
| Р2 | 2 | 5 |
| P3 | 8 | 1 |
| Р4 | 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
В Preemptive SJF Scheduling заданията се поставят в опашката за готовност, когато идват. Процес с най-кратко време за избухване започва изпълнението. Ако пристигне процес с дори по-кратко време на избухване, текущият процес се премахва или се изважда от изпълнение и по-късата задача се разпределя на процесорен цикъл.
Обмислете следните пет процеса:
| Опашка за обработка | Време за спукване | Час на пристигане |
| P1 | 6 | 2 |
| Р2 | 2 | 5 |
| P3 | 8 | 1 |
| Р4 | 3 | 0 |
| P5 | 4 | 4 |
Стъпка 0) По време = 0, P4 пристига и започва изпълнение.
| Опашка за обработка | Време за спукване | Час на пристигане |
| P1 | 6 | 2 |
| Р2 | 2 | 5 |
| P3 | 8 | 1 |
| Р4 | 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 |
| Р2 | 2 | 5 |
| P3 | 8 | 1 |
| Р4 | 3 | 0 |
| P5 | 4 | 4 |
Стъпка 5) В момент = 5, процес P2 ще пристигне. Сравнява се времето за избухване на P1, P2, P3 и P5. Процес P2 се изпълнява, тъй като времето за избухване е най-малко. Процесът P5 е изпреварен.
| Опашка за обработка | Време за спукване | Час на пристигане |
| P1 | Остават 5 от 6 | 2 |
| Р2 | 2 | 5 |
| P3 | 8 | 1 |
| Р4 | 3 | 0 |
| P5 | Остават 3 от 4 | 4 |
Стъпка 6) По време = 6, P2 се изпълнява.
Стъпка 7) По време = 7, P2 завършва изпълнението си. Времето на пръскане на P1, P3 и P5 се сравнява. Процес P5 се изпълнява, тъй като времето за избухване е по-малко.
| Опашка за обработка | Време за спукване | Час на пристигане |
| P1 | Остават 5 от 6 | 2 |
| Р2 | 2 | 5 |
| P3 | 8 | 1 |
| Р4 | 3 | 0 |
| P5 | Остават 3 от 4 | 4 |
Стъпка 8) По време = 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) Непревентивен SJF и 2) Превантивен SJF.
- При непредварително планиране, след като цикълът на процесора е разпределен за процес, процесът го задържа, докато достигне състояние на изчакване или прекрати.
- В Preemptive SJF Scheduling заданията се поставят в опашката за готовност, когато идват.
- Въпреки че започва процес с кратко време на избухване, текущият процес се премахва или изпречва от изпълнение, а работата, която е по-кратка, се изпълнява 1-ва.
- SJF често се използва за дългосрочно планиране.
- Намалява средното време за изчакване по алгоритъма FIFO (First in First Out).
- При SJF планирането, времето за завършване на заданието трябва да се знае по-рано, но е трудно да се предвиди.
- SJF не може да бъде внедрен за планиране на процесора за краткосрочен план. Това е така, защото няма конкретен метод за предсказване на продължителността на предстоящия процесор.