Алгоритми, базирани на квантуване

Много алгоритми за изпреварващо планиране се основават на концепцията заквантуване.В съответствие с тази концепция на всяка нишка се дава ограничен непрекъснат период от процесорно време за изпълнение на свой ред -квантово.

Промяна в активната нишка възниква, ако:

• нишката прекъсна и напусна системата;

• нишката е в състояние на изчакване;

• количеството процесорно време, определено за тази нишка, е изчерпано.

Нишка, която е изчерпала своя квант, се прехвърля в състояние на готовност и чака да й бъде предоставен нов квант процесорно време, а от опашката за готовност се избира нова нишка за изпълнение в съответствие с определено правило. Графиката на състоянието на потока, показана на фиг. 4, съответства на алгоритъм за планиране, базиран на квантуване.

Фиг. 4. Графика на състоянията на потока в система с квантуване.

Квантите, разпределени за нишки, могат да бъдат еднакви за всички нишки или различни. Да разгледаме например случая, когато на всички потоци са дадени кванти с еднаква дължина q (фиг. 5). Ако има n нишки в системата, тогава времето, което една нишка прекарва в очакване на следващия квант, може грубо да се оцени като q(n-l). Колкото повече нишки в системата, толкова по-дълго е времето за изчакване, толкова по-малка е възможността за провеждане на едновременна интерактивна работа за няколко потребители. Но ако стойността на кванта е избрана да бъде много малка, тогава стойността на продукта q(n-l) все пак ще бъде достатъчно малка, така че потребителят да не изпитва дискомфорт от присъствието на други потребители в системата. Типичната квантова стойност в системите за споделяне на време е десетки милисекунди.

Фиг. 5. Илюстрация на изчисляването на времето за изчакване на опашката.

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

Квантите, разпределени за една нишка, могат да бъдат фиксирана стойност или могат да се променят в различни периоди от живота на нишката. Нека, например, първоначално на всяка нишка се присвоява достатъчно голям квант и стойността на всеки следващ квант се намалява до някаква предварително определена стойност. В този случай кратките задачи, които имат време да бъдат изпълнени по време на първия квант, ще се възползват, а дългосрочните изчисления ще се извършват във фонов режим. Човек може да си представи алгоритъм за планиране, при който всеки следващ квант, разпределен за определена нишка, е по-голям от предишния. Този подход намалява разходите за превключване на задачи в случай, че няколко задачи извършват продължителни изчисления наведнъж.

Нишките получават времеви отрязък за изпълнение, но някои от тях не го използват напълно, например поради необходимостта от извършване на входни или изходни данни. Резултатът е ситуация, при която I/O-интензивните нишки използват само малка част от разпределеното им процесорно време. Алгоритъмът за планиране може да коригира тази "несправедливост". Като компенсация за непълно използвани кванти, нишките получават привилегии при последващо обслужване. За целта планировчикът създава две опашки от готови нишки (фиг. 6). Опашка 1 се формира от нишки, които са влезли в състояниетоготов в резултат на изчерпване на времеви отрязък, а опашка 2 - от нишки, които са завършили I/O операцията. Когато дадена нишка е избрана за изпълнение, втората опашка се разглежда първо и само ако е празна, се разпределя квант за нишката от първата опашка.

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

Алгоритмите, базирани на квантуване, независимо дали целта им е да предпочитат кратки или дълги задачи, да компенсират недостатъчно използваните кванти или да минимизират режийните разходи за превключване, не използват информация за предходна задача. Когато дадена задача пристигне за обработка, ОС няма информация дали е кратка или дълга, колко интензивни ще бъдат нейните заявки към I/O устройствата, колко важно е нейното бързо изпълнение и т.н. Разграничаването на услугата по време на квантуване се основава на „историята на съществуване“ на нишката в системата.

Фиг. 6. Квантуване с предпочитание за силно циркулиращи потоци

3.4.2 Алгоритми за планиране, базирани на приоритет

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

Приоритетът може да бъде изразен като цяло число или дроб, положителна или отрицателна стойност. В някои операционни системи се приема, че приоритетът на една нишка е толкова по-висок, колкото по-голямо (в аритметичен смисъл) е числото, обозначаващо приоритета. В други системи, напротив, колкото по-малко е числото, толкова по-висок е приоритетът.

В повечето операционни системи, които поддържат нишки, приоритетът на нишката е пряко свързан с приоритета на процеса, който изпълнява нишката.Приоритетът на даден процес се присвоява от операционната система при създаването му. Стойността на приоритета е включена в дескриптора на процеса и се използва при присвояване на приоритет на нишките на този процес.При присвояване на приоритет на новосъздаден процес, ОС взема предвид дали този процес е системен или приложен процес, какъв е статусът на потребителя, който е стартирал процеса, дали е имало изрична инструкция от потребителя да присвои определено ниво на приоритет на процеса. Нишката може да бъде инициирана не само от потребителска команда, но и в резултат на системно извикване, изпълнено от друга нишка. В този случай, когато присвоява приоритет на нова нишка, ОС трябва да вземе предвид стойността на параметрите на системното извикване.

Много операционни системи предоставят възможност за промяна на приоритетите по време на живота на нишката.

по инициатива на самата нишка, когато направи съответното извикване на операционната система,
иницииран от потребителя, когато той изпълни съответната команда.
Самата ОС може да се промениприоритети на нишките в зависимост от ситуацията в системата. В последния случай приоритетите се наричат динамичниза разлика от неизменните,фиксирани,приоритети.

Ефективността на цялата изчислителна система зависи значително от това какви приоритети са присвоени на нишките. В съвременните операционни системи, за да се избегне системен дисбаланс, който може да възникне при неправилно зададени приоритети,те се опитват да ограничат възможността на потребителите да влияят върху приоритетите на процесите и нишките.В същото време обикновените потребители, като правило, нямат право да повишават приоритетите на своите нишки, това е разрешено да правят (и дори тогава в определени граници) само администратори. В повечето случаи операционната система приоритизира нишките по подразбиране. Като пример, разгледайте схемата за приоритизиране на нишките, приета в операционната система Windows NT (фиг. 7). Системата дефинира 32 нива на приоритет и два класа нишки - нишки в реално време и нишки с променлив приоритет. Диапазонът от 1 до 15 включително е запазен за нишки с променливи приоритети, а от 16 до 31 е за по-критични за времето нишки в реално време (приоритет 0 е запазен за системни цели).

Фиг. 7. Схема за приоритизиране на Windows NT

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