Най-къс-Job-Първи (SJF)
При разглеждане на алгоритми FCFS и RR видяхме колко е важно за тях е от порядъка на процесите в опашката на процесите, готови за изпълнение. Ако късите задачите са подредени в една линия по-близо до началото на цялостната ефективност на тези алгоритми се увеличава значително. Ако знаехме, че следващия път, CPU разрушаване на процесите в състояние на готовност, можем да изберем да не се извършва процес на опашката, както и процеса с минимална продължителност CPU разрушаване. Ако тези процеси са две или повече, за да изберете една от тях, можете да използвате познатия FCFS алгоритъм. Отрязък от време не се използва. Описаният алгоритъм се нарича "най-краткия работата на първо място", или Най-кратък Job First (SJF).
SJF-алгоритъм за краткосрочно планиране може да бъде превантивен. и не-превантивен. Когато не-превантивен SJF а - се предоставя на процеса на планиране избрал процесор за всички необходимото време за него, независимо от събитията, настъпили в една компютърна система. Когато превантивен SJF - планиране отчита появата на нови процеси в опашката готов за обработка (броят на новородените или освободен) по време на работата на избрания процес. Ако CPU спукването на новия процес е по-малко от процесора на остатъка се спука, за да изпълни, тогава изпълним процес е принуден ново.
Вземем примера на работата на не-превантивен SJF алгоритъм. Да предположим, че в състояние на готовност са четири процеса, P0. p1. p2 и p3. за които определено време на следващото си CPU спука. Тези времена са показани в Таблица 3.4. Както и преди, ние приемаме, че всички дейности на процеси са ограничени да използват само един период от CPU разрушаване. че процесите не изпълняват входно-изходни операции, както и това, че превключването на контекста време е незначителен.
Както можем да видим, средно време на изчакване за алгоритъм SJF е (4 + 1 + 9 + 0) / 4 = 3.5 единици от време. Лесно е да се изчисли, че за алгоритъма FCFS на ред P0 процеси. p1. p2. p3 тази стойност ще бъде равна на (0 + 5 + 8 + 15) / 4 = 7 единици от време, т. е. е два пъти по-голяма от SJF алгоритъм. Може да се покаже, че за даден набор от процеси (ако не е на опашката, нови процеси) алгоритъм SJF е оптимално от гледна точка на минимизиране на средното време за изчакване между класа на не-превантивни алгоритми.
Например, като се има предвид изместване SJF насрочването на ние ще предприемем редица процеси p0. p1. Р2 и Р3 с различно време на CPU разрушаване и различни моменти от появата им в опашката на процесите, готови за изпълнение (вж. Таблица 3.6.)..
Време на възникване на взрив опашката за следващия CPU
В началния време в състояние на готовност са само два процеси, p0 и P3. По-малко време за следващата поредица CPU се появява в процеса на стр.3. защо той избира за изпълнение (вж. Таблица 3.7.). След две единици време системата приема процес p1. времето си CPU разрушаване е по-малко от остатъка на CPU взрив в процес P3. който се премества от състоянието на изпълнение и се превръща в състояние на готовност. След още две единици за време на процеса завършва P1 и P3 за изпълнението на процеса е избран отново. В момент Т = 6 опашка обработва готов за изпълнение, се появява процес p2. но тъй като е необходимо в продължение на 7 единици за време, а процес, стр.3 оставен да работи само една единица време, процесът продължава p3 състояние изпълнение. След приключване на по време Т = 7 опашката процеси са p0 и p2. е избран p0 на който процес. Накрая, последният ще бъде в състояние да се извършва процес p2.
Основната трудност при изпълнението на алгоритъма е неспособността SJF усъвършенства следващия CPU разрушаване знания продължителност за изпълнение на процесите. При периодичните системи в размер на процесорно време, необходимо за извършване на задачата, потребителят определя при формиране на работни места. Ние можем да използваме тази стойност за дългосрочно SJF - планиране. Ако посочите повече време, отколкото той се нуждае, той ще изчака резултата за по-дълго, отколкото можеше, като работата ще бъде качен в системата по-късно. Ако той казва, по-малък период от време, задачата не може да се брои до края. По този начин, на процесорни системи на решения пакет използват време задача за оценка да бъдат прехвърляни върху рамото на потребителя. Когато краткосрочно планиране, което можем да направим само продължителността прогноза за следващата поредица на процесора. въз основа на историята на работата на инсталацията. Да - стойността на п-то CPU разрушаване. Т (п + 1) - прогнозира стойност за п + 1-ия CPU пакета. - количество, вариращо от 0 до 1.
Определяне на рецидив
T (0), ние се произволна константа. Първият план взема предвид неотдавнашното поведение на процеса, а вторият план взема предвид неговата история. Когато престане да следва поведението на последния процес, действително вярва
т. е. оценката на цялата CPU избухна еднакво, на базата на някои първоначални предположения.
Да предположим, че ние забравяме за праисторията на процеса. В този случай, ние вярваме, че по време на следващата поредица CPU ще съвпадне с времето на последния взрив CPU:
Обикновено се откажете за последната счетоводна еквивалент поведение и историята. Трябва да се отбележи, че този избор е подходящ за бързо организация на изчислителна оценка Т (п + 1). За да се изчисли нова оценка е необходимо да се вземат старата оценка, за да се установят измерената процесорно време се спука и получената сума, разделена на 2. Например, чрез преместването му в едно малко в дясно. Получената оценки T (N + 1) се използват като продължителността на последователни периоди от продължителна употреба на процесорно време за кратко SJF - планиране.
Свързани статии