Първа най-кратка работа (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 (First In First Out - Първи влязъл, първи излязъл).
• Методът SJF дава най-ниското средно време на изчакване за специфичен набор от процеси.
• Подходящо е за задания, изпълнявани в пакет, където времето за изпълнение е известно предварително.
• За пакетната система за дългосрочно планиране, оценка на времето за избухване може да бъде получена от описанието на длъжността.
• За краткосрочно планиране трябва да предвидим стойността на следващото време на импулс.
• Вероятно е оптимално по отношение на средното време за изпълнение.

Недостатъци/против на SJF

Ето някои недостатъци/минуси на алгоритъма SJF:

• Времето за завършване на работата трябва да се знае по-рано, но е трудно да се предвиди.
• Често се използва в пакетна система за дългосрочно планиране.
• SJF не може да бъде приложен за График на процесора за краткосрочен план. Това е така, защото няма конкретен метод за предсказване на продължителността на предстоящия взрив на процесора.
• Този алгоритъм може да причини много дълго време за изпълнение или глад.
• Изисква знания за това колко дълго ще се изпълнява процес или работа.
• Това води до гладуване, което не намалява средното време за изпълнение.
• Трудно е да се знае дължината на предстоящата заявка за процесора.
• Изминалото време трябва да се записва, което води до по-голямо натоварване на процесора.

Въпроси и Отговори