Round Robin ütemezési algoritmus példával

By: Nathaniel Brooks Nathaniel Brooks
Hours korszerűsített

⚡ Okos összefoglaló

A körforgásos ütemezés a legrégebbi és legegyszerűbb preemptív CPU-algoritmus, ahol minden kész folyamat egy ciklikus sorban álló, rögzített időtartamig fut, biztosítva a korrekt, kimerülésmentes végrehajtást a multitaskinghoz.

  • 🔄 Meghatározás: Minden kész feladat felváltva fut egy rögzített időtartamig.
  • ⏱️ Időkvantum: A CPU egy fix intervallum, az időkvantum után vált folyamatokat.
  • 🇧🇷 Méltányosság: Minden folyamat azonos CPU-időt kap, elkerülve az éhezést.
  • 🧮 Elővásárlási: Egy előzetesen kiválasztott folyamat a sor végére kerül.
  • ✅ Előnyök: Igazságos elosztás, konvojhatás hiánya, kiszámítható válaszidő.
  • ⚠️ Hátrányai: A teljesítmény az időkvantumtól függ, és kontextusváltási többletterhelést jelent.
További információk

Round Robin ütemezési algoritmus

Mi az a Round-Robin ütemezés?

Ennek az algoritmusnak a neve a körmérkőzés elvéből származik, ahol minden ember felváltva egyenlő részt kap valamiből. Ez a legrégebbi, legegyszerűbb ütemezési algoritmus, amelyet többnyire többfeladatos munkavégzésre használnak.

A körforgásos ütemezésben minden kész feladat egy ciklikus sorban, korlátozott ideig, sorról sorra fut. Ez az algoritmus a folyamatok kimerülésmentes végrehajtását is biztosítja.

A Round-Robin ütemezés jellemzői

Íme a Round-Robin ütemezés fontos jellemzői:

  • A körmérkőzéses algoritmus egy preemptív algoritmus.
  • A CPU egy rögzített időintervallum után átáll a következő folyamatra, ezt időkvantumnak/időszeletnek nevezzük.
  • Az előlegezett folyamat hozzáadódik a sor végéhez.
  • A körmérkőzéses egy hibrid modell, amely óravezérelt.
  • Az időszeletnek minimálisnak kell lennie, amelyet egy adott, feldolgozandó feladathoz rendelnek. Ez azonban operációs rendszerenként eltérő lehet.
  • Ez egy valós idejű algoritmus, amely egy adott időkorláton belül reagál az eseményekre.
  • A körmérkőzéses algoritmus az egyik legrégebbi, legigazságosabb és legegyszerűbb.
  • Ez egy széles körben használt ütemezési módszer a hagyományos operációs rendszerekben.

Példa a körmérkőzéses ütemezésre

Vegyük figyelembe a következő három folyamatot:

Feldolgozási sor Burst time
P1 4
P2 3
P3 5

Körmérkőzés ütemezése

Step 1) A végrehajtás a P1 folyamattal kezdődik, amelynek sorozatideje 4. Itt minden folyamat 2 másodpercig fut. A P2 és P3 még mindig várakozó sorban áll.

Körmérkőzés ütemezése

Step 2) A 2-es időpontban P1 hozzáadódik a sor végéhez, és a P2 megkezdi a végrehajtását.

Körmérkőzés ütemezése

KAPCSOLÓDÓ CIKKEK

Step 3) A 4-es időpontban a P2-t kiiktatják és a sor végére adják. A P3 végrehajtása megkezdődik.

Körmérkőzés ütemezése

Step 4) A 6-es időpontban a P3-t kiiktatják és a sor végére adják. A P1 végrehajtása megkezdődik.

Körmérkőzés ütemezése

Step 5) A 8-as időpontban P1 burst ideje 4. A végrehajtás befejeződött. A P2 elindítja a végrehajtást.

Körmérkőzés ütemezése

Step 6) A P2 burst ideje 3. Már 2 intervallumon keresztül futása lezajlott. A 9-es időpontban a P2 befejezi a végrehajtást. Ezután a P3 folytatja a végrehajtást, amíg be nem fejeződik.

Körmérkőzés ütemezése

Step 7) Számítsuk ki az átlagos várakozási időt a fenti példára.

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

A körmérkőzéses ütemezés előnyei

Íme a körforgásos ütemezési módszer előnyei/haszna:

  • Nem szembesül az éhezés vagy a konvojhatás problémáival.
  • Minden feladat méltányos CPU-elosztást kap.
  • Minden folyamattal foglalkozik, prioritás nélkül.
  • Ha ismeri a futási sorban lévő folyamatok teljes számát, akkor ugyanannak a folyamatnak a legrosszabb válaszidejét is feltételezheti.
  • Ez az ütemezési módszer nem függ a löketidőtől. Ezért könnyen megvalósítható a rendszeren.
  • Ha egy folyamatot végrehajtanak az időszak egy meghatározott készletére, a folyamat megelőzi, és egy másik folyamat fut le az adott időtartamra.
  • Lehetővé teszi az operációs rendszer számára a kontextusváltási metódus használatát az előzetesen aktivált folyamatok állapotának mentéséhez.
  • Az átlagos válaszidő tekintetében a legjobb teljesítményt nyújtja.

A körmérkőzéses ütemezés hátrányai

Íme a körforgásos ütemezés használatának hátrányai/hátrányai:

  • Ha az operációs rendszer szeletelési ideje alacsony, a processzor teljesítménye csökken.
  • Ez a módszer több időt tölt a kontextusváltással.
  • A teljesítménye erősen függ az időkvantumtól.
  • A folyamatokhoz nem lehet prioritásokat beállítani.
  • A körforgásos ütemezés nem ad különleges prioritást a fontosabb feladatoknak.
  • Csökkenti a megértést.
  • Az alacsonyabb időkvantum nagyobb kontextusváltási többletterhelést eredményez a rendszerben.
  • A megfelelő időkvantum megtalálása ebben a rendszerben meglehetősen nehéz feladat.

Legrosszabb eset késleltetése

Ez a kifejezés az összes feladat végrehajtásához szükséges maximális időre vonatkozik.

  • dt = Az észlelési időt jelöli, amikor egy feladatot felvesznek a listába
  • st = Az egyik feladatról a másikra való váltási időt jelöli
  • et = A feladat végrehajtási idejét jelöli

képlet:

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

GYIK

Az időkvantum, vagy időszelet az a fix CPU-idő, amelyet minden folyamat lefut, mielőtt a folyamat idő előtti felügyelet alá kerülne. A túl nagy érték az FCFS-hez hasonlóan viselkedik; a túl kicsi pedig jelentős kontextusváltási terhelést okoz.

Az FCFS minden folyamatot érkezési sorrendben futtat a befejezésig, és nem preemptív. A Round Robin preemptív: minden folyamatnak fix időszeletet ad, és végighalad a sorban, javítva a válaszidőt és megakadályozva, hogy a hosszú feladatok másokat blokkoljanak.

Mivel minden folyamat egy ciklikus várakozási sorba kerül, és sorban egy fix időszeletet kap. Egyetlen folyamatot sem hagynak ki, és nem késleltetnek határozatlan időre, így végül mindegyik CPU-időt kap, függetlenül a hosszától vagy az érkezési sorrendjétől.

A mesterséges intelligencia és a gépi tanulás képes megjósolni a folyamatok viselkedését és a munkaterhelési mintákat, hogy valós időben finomhangolhassa az ütemezési döntéseket. A fix szabályzatok helyett a rendszer dinamikusan képes adaptálni a prioritásokat és az időszeleteket, javítva a CPU-kihasználtságot, az átviteli sebességet és a válaszidőt.

Igen. A mesterséges intelligencia modellek képesek elemezni a múltbeli löketidőket és a rendszer terhelését, hogy optimális időkvantumot javasoljanak, és azt a körülmények változásával módosítsák. Ez jobban kiegyensúlyozza a kontextusváltási terhelést a válaszidővel szemben, mint egyetlen fix érték.

Foglald össze ezt a bejegyzést a következőképpen: