Ütemező programtervezési minta

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. Jegyezzük meg, hogy az Ütemező minta jelentősen növeli a feldolgozási időt azontúl, hogy előhívásához szükséges egy szinkronizált metódus. Az Ütemező minta nem teljesen ugyan az, mint a Feladat-ütemező minta, melyet a valós-idejű (Real-Time) rendszereknél használunk.

Az ütemezőnek több célja lehet. Maximalizálhatja az időegység alatt elvégzett munkát, minimalizálhatja a latenciát (egy feladat engedélyezése és befejezése közötti időt), 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 igényelnek néhányat az erőforrások között. 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. Ezekből majd bemutatunk néhányat.

Hálózati kommunikációban az ütemező az először be, először ki elvének alternatíváját jelenti.

A legegyszerűbb legjobb erőfeszítésű 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 idejke 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"/>
        /// не примет решение, что подошла очередь выполнения этого запроса
        /// </summary>
        /// <param name="s"></param>
        public void Enter(ISchedulerOrdering s)
        {
            var thisThread = Thread.CurrentThread;

            lock(this)
            {
                // Определяем не занят ли планировщик
                if(_runningThread == null)
                {
                    // Немедленно начинаем выполнение поступившего запроса
                    _runningThread = thisThread;
                    return;
                }
                _waiting.Add(thisThread, s);
            }
            
            lock(thisThread)
            {
                //Блокируем поток до тех пор, пока планировщик не решит сделать его текущим
                while(thisThread != _runningThread)
                {
                    _event.WaitOne();
                    _event.Set();   // даем возможность другим потокам проверить своё состояние
                    Thread.Sleep(1);
                }
                _event.Reset();
            }

            lock (this)
            {
                _waiting.Remove(thisThread);
            }
        }

        /// <summary>
        /// Вызов метода <see cref="Done"/> указывает на то, что текущий поток завершил работу
        /// и управляемый ресурс освободился
        /// </summary>
        public void Done()
        {
            lock (this)
            {
                if (_runningThread != Thread.CurrentThread)
                    throw new ThreadStateException(@"Wrong Thread");

                Int32 waitCount = _waiting.Count;
                if (waitCount <= 0)
                {
                    _runningThread = null;
                }
                else if (waitCount == 1)
                {
                    _runningThread = _waiting.First().Key;
                    _waiting.Remove(_runningThread);
                    _event.Set();
                }
                else
                {
                    var next = _waiting.First();
                    foreach (var wait in _waiting)
                    {
                        if(wait.Value.ScheduleBefore(next.Value))
                        {
                            next = wait;
                        }
                    }

                    _runningThread = next.Key;
                    _event.Set();
                }
            }
        }
    }

    /// <summary>
    /// Вспомогательный класс
    /// </summary>
    static partial class ConvertTo
    {
        /// <summary>
        /// Получить первый элемент коллекции
        /// </summary>
        /// <param name="collection"></param>
        /// <returns></returns>
        public static KeyValuePair<Thread, ISchedulerOrdering> First(this Dictionary<Thread, ISchedulerOrdering> collection)
        {
            foreach (var item in collection)
            {
                return item;
            }
            throw new ArgumentException();
        }
    }

}

using System;

namespace Digital_Patterns.Concurrency.Sheduler
{
    /// <summary>
    /// Если несколько операций ожидают доступа к ресурсу, класс<see cref="Scheduler"/> использует
    /// данный интерфейс для определения порядка выполнения операций.
    /// </summary>
    interface ISchedulerOrdering
    {
        Boolean ScheduleBefore(ISchedulerOrdering s);
    }
}

using System;
using System.Threading;

namespace Digital_Patterns.Concurrency.Sheduler
{
    /// <summary>
    /// Примерный код класса <see cref="JournalEntry"/>, который должен быть
    /// распечатан классом <see cref="Printer"/>
    /// </summary>
    class JournalEntry : ISchedulerOrdering
    {
        private static DateTime mTime = DateTime.Now;

        private DateTime _time;

        /// <summary>
        /// Возвращает время создания этого объекта
        /// </summary>
        public DateTime Time { get { return _time; } }

        private String _msg;

        public JournalEntry(String msg)
        {
            mTime = mTime.AddSeconds(1);
            _time = mTime;
            _msg = msg;
        }

        public void Do(Int32 id)
        {
            Console.WriteLine(String.Format(@"{0}: Start doing : {1} : {2}", id, _time, _msg));
            Thread.Sleep(1000);
            Console.WriteLine(String.Format(@"{0}: Finish do : {1} : {2}", id, _time, _msg));
        }

        /// <summary>
        /// Возвращает true, если данный запрос должен
        /// обрабатываться перед этим запросом.
        /// </summary>
        /// <param name="s"></param>
        /// <returns></returns>
        public Boolean ScheduleBefore(ISchedulerOrdering s)
        {
            if(s is JournalEntry)
            {
                var otherJournalEntry = (JournalEntry) s;
                return (this.Time < otherJournalEntry.Time);
            }
            return false;
        }
    }
}

using System;
using System.Threading;

namespace Digital_Patterns.Concurrency.Sheduler
{
    public class Example01
    {
        private Printer _printer;

        public void Run()
        {
            Console.WriteLine(@"Press any key for start, and press again for finish");
            Console.ReadKey();
            
            _printer = new Printer();
            new Thread(Thread1).Start();
            new Thread(Thread2).Start();
            new Thread(Thread3).Start();

            Console.ReadKey();
        }

        private void Thread1()
        {
            var msg1 = new JournalEntry(@"Buy toll 5.45 USD");
            var msg2 = new JournalEntry(@"Buy candy 1.05 USD");
            var msg3 = new JournalEntry(@"Buy chocolate 3.25 USD");
            _printer.Print(msg1);
            _printer.Print(msg2);
            _printer.Print(msg3);
        }

        private void Thread2()
        {
            var msg4 = new JournalEntry(@"Buy postcard 2.05 USD");
            var msg5 = new JournalEntry(@"Buy gerland 37.78 USD");
            _printer.Print(msg4);
            _printer.Print(msg5);
        }

        private void Thread3()
        {
            var msg6 = new JournalEntry(@"Buy ball 30.06 USD");
            var msg7 = new JournalEntry(@"Buy pipe 1.83 USD");
            _printer.Print(msg6);
            _printer.Print(msg7);
        }
    }
}

using System;
using Digital_Patterns.Concurrency.Sheduler;

namespace Digital_Patterns
{
    class Program
    {
        static void Main(string[] args)
        {
            new Example01().Run();

            Console.WriteLine(@"Press any key for end");
            Console.ReadKey();
        }
    }
}

Operációs rendszerek időzítőinek típusai

Operációs rendszerekben az időzítő egy rendszermodul, ami kiválasztja a következő feladatot a rendszer számára, és a következő futtatandó folyamatot. Az operációs rendszerek különböző típusú időzítőket támogathatnak, úgy mint hosszú távú, közép távú és rövid távú időzítőket. Az elnevezések arra a gyakoriságra utalnak, amivel hívják őket.

A folyamatidőzítő az operációs rendszernek az a része, ami dönt arról, hogy egy adott időpontban mely folyamat fusson. Rendszerint fel is függesztheti egy folyamat futását, hátrateheti a várakozási sorban, és egy másik folyamatot indíthat el. Az ilyen ütemezőket preemptívnek nevezik, szemben a kooperatív ütemezőkkel.

A hosszú távú ütemező arról dönt, hogy mely folyamatok és feladatok kerülhessenek futásra kész állapotba. Ha egy programot elindítanak, akkor először a hosszú távú ütemező foglalkozik vele, késlelteti vagy feljogosítja a futásra. Ez az ütemező határozza meg, hogy mely folyamatok futhatnak a gépen, és ez dönt arról, hogy mekkora legyen a párhuzamosság, és ez határozza meg a multiprogramozás fokát. További feladata az is, hogy a számításintenzív (inkább számoló) és az I/O-intenzív (inkább írással-olvasással foglalkozó) folyamatok száma körülbelül azonos legyen. Egy programban a kétféle folyamat elkülöníthető a termelő-fogyasztó programtervezési mintával.

Általában a kétféle folyamat csak párhuzamosan tud hatékonyan futni, különösen, ha a tervmintából származnak. Az azonos típusú folyamatok akadályozzák egymást. Például, ha I/O folyamatból van sok sok, akkor a futásra kész sor majdnem mindig üres lesz, és a rövid távú ütemezőnek nincs sok tennivalója, pedig jönnek a feladatok. Hasonlóan, ha számításintenzív folyamatokat választ, akkor az I/O ütemezőnek nem lesz sok tennivalója, a perifériák kihasználatlanul maradnak, és a rendszer megint kiegyensúlyozatlan marad. A jó rendszer kombinálja a kétféle típust. Modern operációs rendszerek ezt használják ki, hogy a valós idejű folyamatok elég CPU-időt kapjanak, hogy betarthassák a határidőket.

Implementációk

Az algoritmus lehet olyan egyszerű, mint a round robin, ahol az ütemező ciklikusan kapcsolgat a folyamatok között, és mindegyik ugyanakkora időszeletet kap. Azaz, ha három folyamat van, A, B és C, akkor az A folyamat kap egy időszeletet, majd a B és a C jön, aztán újra az A, és így tovább.

Bonyolultabb algoritmusok használhatnak prioritást, vagy fontosságot. A rendszerfolyamatok például mindig fontosabbak a felhasználói folyamatoknál. SMP rendszerekben a processzoraffinitás a teljes rendszer teljesítményét növeli, még ha le is lassítja az adott folyamatot. Ez a cache trashing csökkentésével járul hozzá a rendszer felgyorsításához.

Kapcsolódó szócikkek

• Közvetítő programtervezési minta

Fordítás

Ez a szócikk részben vagy egészben a Scheduler pattern című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Forrás

• Mark Grand. Patterns in Java Volume 1: A Catalog of Reusable Design Patterns Illustrated with UML. — Wiley & Sons, 1998. — 480 с. — ISBN 0471258393.