Алгоритъм за кръгово планиране с пример

Характеристики на Round-Robin Scheduling

Ето важните характеристики на Round-Robin Scheduling:

• Round robin е изпреварващ алгоритъм
• Процесорът се прехвърля към следващия процес след фиксиран интервал от време, който се нарича времеви квант/времеви отрязък.
• Процесът, който е изтеглен, се добавя в края на опашката.
• Round robin е хибриден модел, който се задвижва от часовник
• Времевият отрязък трябва да бъде минимален, който е определен за конкретна задача, която трябва да бъде обработена. Въпреки това, може да се различава от ОС до ОС.
• Това е алгоритъм в реално време, който реагира на събитието в рамките на определен срок.
• Round robin е един от най-старите, най-справедливите и най-лесните алгоритъм.
• Широко използван метод за планиране в традиционната ОС.

Пример за кръгово планиране

Разгледайте това като следните три процеса

Опашка за обработка	Време на избухване
P1	4
P2	3
P3	5

Стъпка 1) Изпълнението започва с процес P1, който има време на избухване 4. Тук всеки процес се изпълнява за 2 секунди. P2 и P3 все още са в опашката за чакане.

Стъпка ) В момент =2, P1 се добавя към края на опашката и P2 започва да се изпълнява

Стъпка 3) Във време = 4, P2 се изтегля и се добавя в края на опашката. P3 започва да се изпълнява.

Стъпка 4) Във време = 6, P3 се изтегля и се добавя в края на опашката. P1 започва да се изпълнява.

Стъпка 5) Във време = 8, P1 има време на пакет от 4. Той е завършил изпълнението. P2 започва изпълнението

Стъпка 6) P2 има време за избухване 3. Той вече е изпълнен за 2 интервала. В момент = 9 P2 завършва изпълнението. След това P3 започва изпълнението, докато не завърши.

Стъпка 7) Нека изчислим средното време на изчакване за горния пример.

Wait time 
P1= 0+ 4= 4
P2= 2+4= 6
P3= 4+3= 7

Предимство на кръговия график

Ето плюсовете/предимствата на метода на кръгово планиране:

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

Недостатъци на кръговия график

Ето недостатъците/минусите на използването на Round-robin планиране:

• Ако времето за нарязване на ОС е малко, мощността на процесора ще бъде намалена.
• Този метод отделя повече време за превключване на контекста
• Неговото представяне силно зависи от времето.
• Не могат да се задават приоритети за процесите.
• Кръговият график не дава специален приоритет на по-важните задачи.
• Намалява разбирането
• По-малкият времеви квант води до по-високо натоварване на превключването на контекста в системата.
• Намирането на правилен времеви квант е доста трудна задача в тази система.

Латентност в най-лошия случай

Този термин се използва за максималното време, необходимо за изпълнение на всички задачи.

• dt = Означава времето за откриване, когато дадена задача е поставена в списъка
• st = Означава времето за превключване от една задача към друга
• et = Означава времето за изпълнение на задачата

Формула:

Tworst = {(dti+ sti + eti ), + (dti+ sti + eti )2 +...+ (dti+ sti + eti )N., + (dti+ sti + eti  + eti) N} + tISR	
t,SR = sum of all execution times

Oбобщение

• Името на този алгоритъм идва от кръговия принцип, при който всеки човек получава равен дял от нещо на свой ред.
• Round robin е един от най-старите, най-справедливите и най-лесните алгоритми и широко използвани методи за планиране в традиционните OS.
• Round robin е изпреварващ алгоритъм
• Най-голямото предимство на метода за кръгово планиране е, че ако знаете общия брой процеси в опашката за изпълнение, тогава можете да приемете и най-лошото време за отговор за същия процес.
• Този метод отделя повече време за превключване на контекста
• Закъснението в най-лошия случай е термин, използван за максималното време, необходимо за изпълнение на всички задачи.