A számítógép-programozásban, az Ütemező (angolul scheduler) minta egy programtervezési minta. Ez egy párhuzamossági minta, melyet akkor használunk, amikor a szálak egyszálú kódokat hajtanak végre, mint például egy fájlírási művelet. Szálakat, folyamatokat, adatfolyamokat kezel, amelyeket processzorokra, hálózati kapcsolatokra és kiegészítő kártyákra (grafikus kártya, memóriakártya) ütemez.
Az ütemező egy objektum, amely szekvenciálisan várakozik a szálakra. Ez mechanizmust biztosít egy ütemezési szabályrendszer implementálására, de független bármilyen más konkrét ütemezési szabálytól – A szabály egységbe van zárva a saját osztályába, és újrafelhasználható. Gyakran úgy van kialakítva, hogy lefoglalja az összes erőforrást. Az ütemező mintával olyan számítógép is működhet virtuálisan párhuzamosan, aminek csak egy processzora van.
Az olvas / ír záró (Lock) minta általában az ütemező minta által is megvalósítható, a tisztességes feltételek biztosítása érdekében. Az Ütemező minta jelentősen növeli a feldolgozási időt, és hívásához szinkronizált metódus szükséges. Az Ütemező minta nem teljesen ugyanaz, mint a Feladat-ütemező minta, melyet a valós-idejű (Real-Time) rendszereknél használunk.
Az ütemező alkalmazásának több célja lehet. Maximalizálhatja az időegység alatt elvégzett munkát, minimalizálhatja az átfutási időt (latency, egy feladat engedélyezése és befejezése között eltelt időtartam), minimalizálhatja a válaszidőt, maximalizálhatja a korrektséget. Ezek a célok gyakran ellentmondanak egymásnak, ezért az ütemezőnek a megfelelő egyensúlyt kell megvalósítania. A felhasználó és a rendszer igényeinek és céljainak megfelelően kell dönteni arról, hogy melyik cél a fontosabb.
Valós idejű környezetekben az ütemezőnek a határidők betartását is biztosítania kell. Ilyenek a robotok és az automata vezérlésű beágyazott rendszerek. Erre feltétlenül szükség van a rendszer stabilitásának érdekében. Az ütemező hálózaton keresztül is eloszthatja a feladatokat egy adminisztratív központból.
Időzítési algoritmusok Az ütemezési algoritmusok a forrásokat olyan folyamatok között osztják szét, amelyek aszinkron módon igényelnek néhányat az erőforrások közül. Használják a routerekben a csomagok irányításához, operációs rendszerekben a folyamatok időmegosztására, lemezmeghajtókban író-olvasó ütemezésre, nyomtatókhoz, beágyazott rendszerekhez.
Az ütemezők fő célja az, hogy megelőzzék a kiéheztetést, és korrektséget biztosítsanak az erőforrások elosztásában. Az ütemező osztja el az erőforrásokat, ő dönt arról, hogy ha több folyamat igényli ugyanazokat az erőforrásokat, akkor melyik kapja meg.
Hálózati kommunikációban az ütemező az először be, először ki elvének alternatíváját jelenti.
Egyszerű de hatékony algoritmusok a round robin, a max-min fair sor, az arányos fair időzítés és az időegység alatt elvégzett feladatok maximalizálása. Ha a szolgáltatás minőségét is megkülönböztetik, és szembeállítják a legjobb erőfeszítésű kommunikációval, a súlyozott fair sor ajánlható.
A vezeték nélküli rádióhálózatban mint a HSDPA (High-Speed Downlink Packet Access) 3.5G sejtrendszerben a csatornafüggő ütemezés használható arra, hogy a csatorna állapotáról információhoz jussunk. Megfelelő esetben növelhetjük az időegység alatt elvégzett feladatok számát, és a rendszer spektrális hatékonyságot. Fejlettebb rendszerekben, mint az LTE, az ütemezés kombinálható a csatornafüggő csomagonkénti dinamikus csatornaallokációval, vagy az OFDMA multihordozók allokálásával vagy más frekvenciatartományi kiegyenlítésével, olyan komponensekkel, amiket a felhasználó a legjobban tud hasznosítani.
A munkakonzervatív ütemező arra törekszik, hogy a beütemezett folyamatoknak mindig legyen feladatuk. Az ütemező preemptív, ha megszakíthatja az éppen futó folyamatot, és helyette egy másikat indíthat el.
Először érkező először Az először érkező először (ismert úgy is, mint FIFO vagy FCFS) egy egyszerű, sort használó ütemezési algoritmus. A szálkészlet programtervezési minta is ezen alapul. Az érkező folyamatokat az ütemező beteszi a várakozási sorba, ha pedig lehet, akkor elindítja a legrégibb feladatot. Mivel kontextusváltás csak akkor történik, amikor véget ér egy feladat, és a folyamatsor nem igényel átrendezést, az ütemezés kevés adminisztrációs költséggel jár. Az egyszerre végzett feladatok száma kevés lehet, mivel a hosszú folyamatok feltarthatják a rövideket. Erre példa az, hogy a teli kosarú vásárló megelőzi azt, aki csak egy cikket akar venni; ez utóbbi több időt veszít, mint amennyit az elöl álló nyer. Ez konvoj hatásként is ismert. Nincs kiéheztetés, mivel a folyamatok meghatározott idő után sorra kerülnek. A teljes végrehajtási idő, a várakozási és a válaszadási idő nagy lehet, függően a beérkező feladatok sorrendjétől. Nincs priorizálás, így ez a módszer nem alkalmas a határidők betartatására.
Legkorábbi határidő először A legkorábbi határidő először (EDF) egy dinamikus ütemezési algoritmus, amit valós idejű operációs rendszereken használnak. A folyamatok határidejük alapján prioritási sorba kerülnek, Ütemezési esemény (feladat vége, feladat indítása) esetén az ütemező megkeresi a sorban azt a feladatot, aminek a legközelebbi a határideje. A következő alkalommal ennek kell elindulnia. Legrövidebb hátralevő idejű először Hasonló a legrövidebb feladat először (SJF) ütemezéshez. Az ütemező úgy rendezi a feladatokat, hogy az kerül előre, aminek a legrövidebb a becsült hátralevő ideje. Ez azt igényli, hogy ezt az időt meg lehessen becsülni. Ha a beérkező feladat becsült végrehajtási ideje rövidebb, mint az éppen futó feladat hátralevő ideje, akkor az ütemező megszakítja, és a rövid feladatot indítja el. A kontextusváltás és a sor rendezgetése miatt az adminisztrációs költség nagy. A legtöbb esetben biztosítja, hogy időegység alatt minél több feladat hajtódjon végre. A várakozási és a válaszadási idő együtt nő a folyamat számítási igényével. Mivel a teljes időbe beleszámít a várakozás is, ez megérződik a hosszabb folyamatoknál. Azonban az átlagos várakozási idő rövidebb, mint a FIFO esetén, hiszen nem kell a leghosszabb folyamat befejezésére várni. Magukat a határidőket nem figyeli az ütemező. A programozóknak kell arra ügyelniük, hogy a feladatoknak olyan határidejük legyen, amennyi idő alatt éppen végre tudjanak hajtódni. Az ennél hosszabb határidőket a rendszer bünteti. A módszer használatához különböző prioritású folyamatokra van szükség. Például a rendszerfeladatoknak lehet nagyobb a prioritása. 2014-ben ezt a módszert ritkán használták. Rögzített prioritású preemptív ütemezés A folyamatok ütemezése prioritásukon alapul. Ha nincs prioritás, akkor az FPPS a FIFO algoritmusba megy át. A sorban a feladatokat az ütemező prioritásuk szerint rendezi. Az alacsony prioritású folyamatokat megszakítja a beérkező magas prioritású feladat. Az adminisztrációs költség alacsony. Ha a kiosztható prioritások korlátosak, akkor minden prioritáshoz külön FIFO tartozik. Az alacsonyabb prioritású sorokból akkor jöhet feladat, ha a magasabb prioritású sorok üresek. A FIFO-val szemben nincs időegység alatt elvégzett feladatok számában előnye. A várakozási és a válaszadási idő függ a feladat prioritásától. A nagyobb prioritásúaké kisebb. A prioritás meghatározza, hogy a folyamat be tudja-e tartani a feladat határidejét. Kiéheztetés előfordulhat, ha sorra jönnek a nagy prioritású feladatok. Round-robin ütemezés Az időzítő a CPU-időt szeletekre osztja. A folyamatokat ciklikusan járja végig. Ha egy folyamat véget ért, akkor törli a ciklusból, és az időszeletet a következő folyamat kaphatja meg. Az adminisztrációval töltött idő nagy, különösen, ha az időszeletek rövidek. Az időegység alatt végrehajtott feladatok száma az FCFS/ FIFO és az SJF/SRTF közötti. A rövid folyamatok hamarabb véget érnek, mint a FIFO esetén, és a hosszú folyamatok előbb végeznek, mint SJF esetén. Az átlagos várakozási idő a folyamatok számától függ, hosszuktól nem; az átlagos válaszadási idő kicsi. Nem lehet prioritást használni. Ezért kiéheztetés sincs. Az idő allokálása az érkezési sorrendtől függ. A várakozási idők hosszúak, ezért határidőket nem lehet betartani. Ha az időszelet hosszú, illetve sok a rövid feladat, akkor FCFS /FIFO, ha rövid, akkor SJF/SRTF lesz. Többszintű sor ütemezés A feladatokat és a folyamatokat csoportokra osztják, például előtérben és háttérben futó folyamatok. A különböző csoportokra különböző ütemezési módszereket használnak, mivel mások az elvárások a válaszadási időt illetően. Megosztott memória kezeléséhez hasznos.
Kézi ütemezés A kézi ütemezés gyakran alkalmazott módszer, amit például idő-multiplexeléssel érnek el. Néha a kernelt három részre osztják: Kézi ütemezés, preemptív és megszakítási szint. Az ütemezőt gyakran kereskedelmi könyvtár nyújtja. Nincs kiéheztetés Megjósolhatóság: a határidők betarthatók. Nincs adminisztrációs költség. Nem mindig optimális. A hatékonyság az optimalizációtól függ. Az ütemező kiválasztása Ha ütemezőt kell választania, akkor a programozónak mérlegelnie kell, hogy milyen tulajdonságokat tart fontosnak, és melyekről tud lemondani. Sok operációs rendszerben több ütemezési algoritmus keverékét használja.
Például a Windows NT/XP/Vista többszintű visszacsatolásos sort használ, ami kombinálja a következőket: rögzített prioritású preemptív ütemezés, round robin, és a FIFO. Ebben a rendszerben a folyamatok prioritása változhat, attól függően, hogy mióta vár, vagy hogy mit végzett eddig. Minden szintet külön sor reprezentál, a magasabb prioritású szálaknál round robin, és az alacsonyabb prioritásúaknál FIFO. Ebben a rendszerben a válaszadási idő a legtöbb folyamatnál alacsony, és a rövid, de kritikus fontosságú rendszerfeladatok hamar véget érhetnek. Azonban a magas prioritású, de hosszú feladatok várakozási ideje hosszú, kiéheztetés előfordulhat.
Példa kód (C#)
using System;
namespace Digital_Patterns.Concurrency.Sheduler { class Printer
private static Int32 mID = 0;
private Scheduler _scheduler = new Scheduler();
public void Print(JournalEntry journalEntry)
Int32 id = ++mID; try
Console.WriteLine(String.Format(@"{0}: enter scheduler", id)); // вызов не выполнится до тех пор, пока объект Scheduler не решит, // что подошла очередь распечатать этот объект JournalEntry _scheduler.Enter(journalEntry); Console.WriteLine(String.Format(@"{0}: start printing", id)); try
//TODO Something journalEntry.Do(id);
finally
// вызов метода Done говорит Scheduler о том, что объект JournalEntry // распечатан, и может подойти очередь вывода на печать другого объекта // JournalEntry _scheduler.Done(); Console.WriteLine(String.Format(@"{0}: done scheduler", id));
catch (Exception) {}
using System; using System.Collections.Generic; using System.Threading;
namespace Digital_Patterns.Concurrency.Sheduler { /// <summary> /// Экземпляры классов в этой роли управляют обработкой объектов Request <see cref="JournalEntry"/>, /// выполняемой объектом Processor <see cref="Printer"/>. Чтобы быть независимыми от типов /// запросов, класс <see cref="Scheduler"/> не должен ничего знать об управляемом им классе Request. /// Вместо этого он осуществляет доступ к объектам Request через реализуемый ими интерфейс <see cref="ISchedulerOrdering"/> /// </summary> class Scheduler
/// <summary> /// Объект синхронизации потоков /// </summary> private AutoResetEvent _event = new AutoResetEvent(false);
/// <summary> /// Устанавливается в null, если управляемый объектом Scheduler ресурс не занят. /// </summary> private Thread _runningThread;
/// <summary> /// Потоки и их запросы ожидающие выполнения /// </summary> private Dictionary<Thread, ISchedulerOrdering> _waiting = new Dictionary<Thread, ISchedulerOrdering>();
/// <summary> /// Метод <see cref="Enter"/> вызывается перед тем, как поток начнет использовать управляемый ресурс. /// Метод не выполняется до тех пор пока управляемый ресурс не освободится и объект <see cref="Sheduler"/>