KNOW INTUIT, Лекция, Планиране на процеси

Многостепенни опашки (Multilevel Queue)

За системи, в които процесите могат лесно да бъдат сортирани в различни групи, е разработен друг клас алгоритми за планиране. За всяка група процеси се създава опашка от процеси, които са в състояние на готовност (вижте Фигура 3.5). На тези опашки са присвоени фиксирани приоритети. Например, приоритетът на опашката на системния процес е зададен по-висок от приоритета на опашката на потребителския процес. И приоритетът на опашката от процеси, стартирани от ученици, е по-нисък от този на опашката от процеси, стартирани от учители. Това означава, че нито един потребителски процес няма да бъде избран за изпълнение, докато има поне един готов системен процес, и нито един обучаващ процес няма да има процесор на свое разположение, ако има процеси на учител, готови за изпълнение. В тези опашки могат да се използват различни алгоритми за планиране. Така например за големи процеси на преброяване, които не изискват взаимодействие с потребителя (фонови процеси), може да се използва алгоритъмът FCFS, а за интерактивни процеси алгоритъмът RR. Този подход, наречен многостепенни опашки, увеличава гъвкавостта на планирането: за процеси с различни характеристики към тях се прилага най-подходящият алгоритъм.

Многостепенна опашка за обратна връзка

По-нататъшно развитие на алгоритъма за многостепенна опашка е добавянето на механизъм за обратна връзка към него. Тук процесът не е постоянно присвоен на конкретна опашка, но може да мигрира от една опашка в друга в зависимост от поведението си.

За простота разгледайте ситуацията, при която процесите в състояние на готовност са организирани в 4 опашки, както вфигура 3.6. Графикът на процесите между опашките се основава на механизъм за изпреварващ приоритет. Колкото по-висока е опашката на фигурата, толкова по-висок е нейният приоритет. Процесите в опашка 1 не могат да се изпълняват, ако има поне един процес в опашка 0. Процесите в опашка 2 няма да бъдат избрани за изпълнение, докато има поне един процес в опашки 0 и 1. И накрая, процесът в опашка 3 може да получи процесор само ако опашки 0, 1 и 2 са празни. Ако, докато даден процес се изпълнява, друг процес се появи в опашката с по-висок приоритет, изпълняваният процес се измества от нов. Графикът на процесите в опашки 0 - 2 се извършва с помощта на алгоритъма RR, планирането на процесите в опашка 3 се основава на алгоритъма FCFS.

Роденият процес влиза в опашка 0. Когато избере да екзекутира, той получава на свое разположение времеви квант от 8 единици. Ако неговата продължителност на CPU burst е по-малка от този времеви отрязък, процесът остава в опашка 0. В противен случай отива на опашка 1 . За процеси на опашка 1 времеви отрязък има стойност 16 . Ако процесът не се побере в това време, той отива на опашка 2. Ако се побере, остава в опашката 1 . В опашка 2 стойността на времевия отрязък е 32 единици. Ако това не е достатъчно за непрекъснатата работа на процеса, процесът влиза в опашка 3, за която не се прилага срязване на времето и при липса на готови процеси в други опашки може да се изпълнява до края на неговия CPU burst. Колкото по-голяма е стойността на CPU burst, толкова по-нисък е опашката с приоритет за процеса, но на толкова повече процесорно време може да разчита. Така след известно време всички процеси, които изискват кратко време за изпълнениепроцесорите ще бъдат поставени в опашки с висок приоритет, а всички процеси, които изискват голям акаунт и с малко заявки за време за реакция, ще бъдат поставени в опашки с нисък приоритет.

Миграцията на процесите в обратна посока може да се извърши по различни принципи. Например, след изчакване за въвеждане от клавиатурата, процесите в опашки 1, 2 и 3 могат да бъдат поставени в опашка 0, след като I/O на диска е завършен, процесите в опашки 2 и 3 могат да бъдат поставени в опашка 1 и след като изчакат всички други събития, те могат да бъдат поставени в опашка 3 в опашка 2. Преместването на процеси от опашки с нисък приоритет към опашки с висок приоритет ви позволява да отчитате по-добре промените в поведението на процеса във времето.

Многостепенните опашки за обратна връзка представляват най-общия подход за планиране на процеси сред подходите, които разгледахме. Те са най-трудни за изпълнение, но в същото време имат най-голяма гъвкавост. Ясно е, че има много други разновидности на този метод на планиране, в допълнение към опцията, дадена по-горе. За пълно описание на конкретното им изпълнение е необходимо да се уточнят:

Броят опашки за процеси, които са в състояние на готовност.
Алгоритъм за планиране, който работи между опашки.
Алгоритми за планиране, които работят в опашки.
Правила за поставяне на роден процес в една от опашките.
Правила за прехвърляне на процеси от една опашка в друга.

Променяйки някой от изброените елементи, можем значително да променим поведението на компютърната система.

Тук спираме да разглеждаме различни алгоритми за планиране на процеси, защото, както беше казано: "Не можете да схванете необятността."

Заключение

Един отНай-ограниченият ресурс на една изчислителна система е процесорното време. За да се разпредели между множество процеси в системата, трябва да се приложи процедура за планиране на процеси. Според степента на продължителност на влиянието на планирането върху поведението на компютърната система се разграничават краткосрочни, средносрочни и дългосрочни процеси на планиране. Специфичните алгоритми за планиране на процеси зависят от поставените цели, класа на решаваните задачи и се основават на статичните и динамичните параметри на процесите и компютърните системи. Има превантивни и непредварителни режими на планиране. При планиране без изпреварване, работещият процес отстъпва процесора на друг процес само по собствена воля; при планиране с изпреварване, изпълняващият се процес може да бъде принуден да излезе от състоянието на изпълнение против волята си.

Най-простият алгоритъм за планиране е алгоритъмът FCFS без изпреварване, който обаче може значително да забави кратки процеси, които не влизат в състояние на готовност навреме. В системите за споделяне на време, превантивна версия на този алгоритъм, RR, стана широко разпространена.

Сред всички непредварителни алгоритми, SJF алгоритъмът е оптимален по отношение на средното време на изчакване на процесите. Съществува и изместваща версия на този алгоритъм. Интерактивните системи често използват гарантиран алгоритъм за планиране, който предоставя на потребителите равни части от процесорното време.

Алгоритъмът SJF и алгоритъмът за гарантирано планиране са специални случаи на планиране с приоритет. По-общите методи за приоритетно планиране използват многостепенни опашки от процеси, готови за изпълнение, и многостепенни опашки за обратна връзка. Като най-трудновнедряване, тези методи за планиране осигуряват гъвкаво поведение на изчислителните системи и тяхната адаптивност към решаване на проблеми от различни класове.