Първа най-кратка работа (SJF): превантивен, непревантивен пример
Какво представлява най-краткият график за първа работа?
Първа най-кратка работа (SJF) е алгоритъм, при който процесът с най-малко време за изпълнение се избира за следващо изпълнение. Този метод на планиране може да бъде изпреварващ или неизпреварващ. Това значително намалява средното време на изчакване за други процеси, чакащи изпълнение. Пълната форма на SJF е Shortest Job First.
Основно има два типа SJF методи:
- Непредварителен SJF
- Превантивен SJF
Характеристики на планирането на SJF
- Свързва се с всяка работа като единица време за изпълнение.
- Този метод на алгоритъм е полезен за обработка от партиден тип, където изчакването за завършване на задания не е критично.
- Може да подобри пропускателната способност на процеса, като се увери, че по-кратките задания се изпълняват първо, следователно е възможно да има кратко време за изпълнение.
- Той подобрява резултатите от работата, като предлага по-кратки задачи, които трябва да бъдат изпълнени първи, които обикновено имат по-кратко време за изпълнение.
Непредварителен 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 time P4= 0-0=0 P1= 3-2=1 P2= 9-5=4 P5= 11-4=7 P3= 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) В момент =10 P5 ще завърши своето изпълнение. Сравнява се времето на разпръскване на P1 и P3. Процесът P1 се изпълнява, защото времето за импулс е по-малко.
Стъпка 9) В момент =15 P1 завършва своето изпълнение. P3 е единственият останал процес. Ще започне изпълнението.
Стъпка 10) В момент =23 P3 завършва своето изпълнение.
Стъпка 11) Нека изчислим средното време на изчакване за горния пример.
Wait time P4= 0-0=0 P1= (3-2) + 6 =7 P2= 5-5 = 0 P5= 4-4+2 =2 P3= 15-1 = 14
Average Waiting Time = 0+7+0+2+14/5 = 23/5 =4.6
Предимства на SJF
Ето ползите/плюсовете от използването на SJF метода:
- SJF често се използва за дългосрочно планиране.
- Намалява средното време на изчакване по алгоритъма FIFO (първи влязъл, първи излязъл).
- Методът SJF дава най-ниското средно време на изчакване за определен набор от процеси.
- Подходящо е за задания, изпълнявани в пакет, където времето за изпълнение е известно предварително.
- За пакетната система за дългосрочно планиране, оценка на времето за избухване може да бъде получена от описанието на длъжността.
- За краткосрочно планиране трябва да предвидим стойността на следващото време на импулс.
- Вероятно оптимално по отношение на средното време за изпълнение.
Недостатъци/против на SJF
Ето някои недостатъци/минуси на SJF алгоритъма:
- Времето за завършване на работата трябва да се знае по-рано, но е трудно да се предвиди.
- Често се използва в пакетна система за дългосрочно планиране.
- SJF не може да се внедри за График на процесора за краткосрочен план. Това е така, защото няма конкретен метод за предсказване на продължителността на предстоящия взрив на процесора.
- Този алгоритъм може да причини много дълго време за изпълнение или глад.
- Изисква знания за това колко дълго ще се изпълнява процес или работа.
- Това води до гладуване, което не намалява средното време за изпълнение.
- Трудно е да се знае дължината на предстоящата заявка за процесора.
- Изминалото време трябва да се записва, което води до повече натоварване на процесора.
Oбобщение
- SJF е алгоритъм, при който процесът с най-малко време за изпълнение се избира за следващо изпълнение.
- SJF Scheduling се свързва с всяка работа като единица време за изпълнение.
- Този метод на алгоритъм е полезен за обработка от партиден тип, където изчакването за завършване на задания не е критично.
- Основно има два типа SJF методи 1) Non-Preemptive SJF и 2) Preemptive SJF.
- При планиране без изпреварване, след като цикълът на процесора бъде разпределен за обработка, процесът го задържа, докато достигне състояние на изчакване или бъде прекратен.
- При превантивното планиране на SJF заданията се поставят в опашката за готовност, когато пристигнат.
- Въпреки че започва процес с кратко време на импулс, текущият процес се премахва или се изключва от изпълнение и задачата, която е по-кратка, се изпълнява първа.
- SJF често се използва за дългосрочно планиране.
- Намалява средното време на изчакване по алгоритъма FIFO (първи влязъл, първи излязъл).
- При планирането на SJF времето за завършване на заданието трябва да бъде известно по-рано, но е трудно да се предвиди.
- SJF не може да се внедри за планиране на CPU за краткосрочен план. Това е така, защото няма конкретен метод за предсказване на продължителността на предстоящия взрив на процесора.