Алгоритъм за кръгово планиране с пример
Натаниел Брукс
⚡ Умно обобщение
Планирането по кръгов процес (Round-Robin Scheduling) е най-старият и най-прост превантивен алгоритъм за процесора, при който всеки готов процес се изпълнява за фиксиран времеви интервал в циклична опашка, осигурявайки справедливо изпълнение без гладуване за многозадачност.
Какво е Round-Robin Scheduling?
Името на този алгоритъм идва от кръговия принцип, при който всеки човек получава равен дял от нещо на свой ред. Това е най-старият и прост алгоритъм за планиране, който се използва най-вече за многозадачност.
При кръговото планиране (Round-robin) всяка готова задача се изпълнява само на свой ред в циклична опашка за ограничен времеви интервал. Този алгоритъм предлага и изпълнение на процеси без гладуване.
Характеристики на Round-Robin Scheduling
Ето важните характеристики на Round-Robin Scheduling:
- Кръговият алгоритъм е превантивен алгоритъм.
- Процесорът се прехвърля към следващия процес след фиксиран интервал от време, който се нарича времеви квант/времеви срез.
- Процесът, който е изтеглен, се добавя в края на опашката.
- Кръговият модел е хибриден модел, който се управлява от часовник.
- Времевият интервал трябва да е минимален и се определя за конкретна задача, която трябва да бъде обработена. Той обаче може да се различава от операционна система до операционна система.
- Това е алгоритъм в реално време, който реагира на събитие в рамките на определен период от време.
- Кръговият алгоритм е един от най-старите, най-справедливите и най-лесните алгоритми.
- Това е широко използван метод за планиране в традиционните операционни системи.
Пример за кръгово планиране
Разгледайте следните три процеса:
| Опашка за обработка | Време на избухване |
|---|---|
| P1 | 4 |
| P2 | 3 |
| P3 | 5 |
Стъпка 1) Изпълнението започва с процес P1, който има време на избухване 4. Тук всеки процес се изпълнява за 2 секунди. P2 и P3 все още са в опашката за чакане.
Стъпка 2) В момент = 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
Предимства на кръговото планиране
Ето са плюсовете/ползите от метода на кръгово планиране:
- Не се сблъсква с проблемите на глада или ефекта на конвоя.
- Всички задачи получават справедливо разпределение на процесора.
- Той обработва всички процеси без никакъв приоритет.
- Ако знаете общия брой процеси в опашката за изпълнение, тогава можете също да приемете най-лошото време за реакция за същия процес.
- Този метод на планиране не зависи от времето за пакетно изпълнение. Ето защо е лесно приложим в системата.
- След като даден процес се изпълни за определен набор от периоди, процесът се изпреварва и друг процес се изпълнява за този даден период от време.
- Позволява на операционната система да използва метода за превключване на контекста, за да запазва състоянията на предварително зададените процеси.
- Дава най-добра производителност по отношение на средно време за реакция.
Недостатъци на кръговия график
Ето недостатъците/минусите на използването на кръгово-робинно планиране:
- Ако времето за нарязване на операционната система е ниско, производителността на процесора ще бъде намалена.
- Този метод отделя повече време за превключване на контекста.
- Неговото представяне силно зависи от времето.
- Не могат да се задават приоритети за процесите.
- Кръговото планиране не дава специален приоритет на по-важните задачи.
- Това намалява разбираемостта.
- По-ниският квант на времето води до по-високи разходи за превключване на контекста в системата.
- Намирането на правилния квант на времето е доста трудна задача в тази система.
Латентност в най-лошия случай
Този термин се използва за максималното време, необходимо за изпълнение на всички задачи.
- dt = Означава времето за откриване, когато задача е добавена в списъка
- st = Означава време за превключване от една задача към друга
- et = Означава времето за изпълнение на задачата
Формула:
Tworst = {(dti+ sti + eti ), + (dti+ sti + eti )2 +...+ (dti+ sti + eti )N., + (dti+ sti + eti + eti) N} + tISR
tISR = sum of all execution times
