Task-based Asynchronous Pattern – Az új Thread Pool

A motiváció

A korábbiakban azt láttuk, hogy több szál együttes futására akkor van szükség, ha biztosítani akarjuk logikai folyamatok függetlenségét. Azt is megtanultuk, hogy jó, ha minél kevesebb szál fut egyszerre, legalábbis nem több, mint ahány processzor/mag van a számítógépen. Az egymagos számítógépek idejében egy logikai folyamatot több szálra tördelni nem volt értelme. A többmagos gépek esetében azonban már megéri ezen gondolkodni, hogy a feladaton egyszerre több mag dolgozhasson. A feladatok széttördelése és hatékony kezelése azonban nem olyan egyértelmű feladat.

A granularitás buktatói

Granularitás alatt azt értjük, hogy a feladatokat milyen mértékben tördeljük szét. Egyik könnyen adódó ötlet, hogy törjük szét a feladatot annyi részre, ahány mag van a rendszerben. Egy négymagos rendszer esetén például megpróbáljuk úgy átrendezni a programot, hogy az négy, egymástól független szálon tudjon futni. Ez bizonyos feladatoknál egyszerű, bizonyos feladatoknál bonyolultabb, de ettől most tekintsünk el. Maga az alapötlet vajon működik?

Ha feltételezzük, hogy a processzor nem foglalkozik semmi mással, illetve jól sikerült szétosztani négyfele a műveleteket – azaz jól el tudtuk találni, hogy körülbelül mind a négy ugyanannyi ideig fusson – akkor igen. Ez azonban nem mindig teljesül.

A számítógépen nem egy program fut egyszerre. Elég megnyitni a Windows Task Manager-t, hogy látszódjon, 50-60 procesz, és több száz szál alap konfigurációkon is “fut” egyszerre. A futás azért idézőjeles, mert legtöbb csak várakozik. Ha a Task Managerben bekapcsoljuk a CPU time oszlopot, vagy a Process Explorerben a Context Switch Delta oszlopot, akkor látszik, hogy némi időt ezek is elvesznek. Ha valaki zenét hallgat, vagy ott felejt egy weboldalt flash-es reklámokkal, esetleg a mi saját programunk csinál egyéb háttérszámításokat, akkor az egy-két mag munkaidejét megosztja a részfeladatunk, és az egyéb teendők között. Ennek az lesz az eredménye, hogy egy-két szál később végez a többinél. Hogy ez hogyan dönti meg a jónak tűnő ötletünket, az a következő ábrán látszik:

Az ábra 1) pontja azt mutatja, amikor körülbelül sikerült eltalálni, hogy a négy részmunka körülbelül ugyanannyi ideig fusson, és a processzor nem is foglalkozott mással. A 2) rész azt mutatja, hogy egyrészt a feladatokat nem sikerült jól elosztani négy részre, ráadásul ezt a torzítást a processzoron végzett egyéb műveletek tovább rontják. A zöld sávok a mi feladatunkat, a sárga sávok az egyéb feladatokat mutatják. A sárga beékelődések miatt az egyik részfeladatunk végrehajtási ideje annyira megnőtt, hogy a többi részfeladat már régen elkészült. Ha a feladat több kisebb, blokkra lett volna szétosztva, és ezek mondjuk a Thread Pool-on keresztül lettek volna feldolgozva, akkor a nem terhelt magokon futó Thread Pool szálak ezeket fel tudták volna venni, és a feladat egésze hamarabb készült volna el:

A tördelés ára

Az eddigiek alapján azt látjuk, hogy érdemes a feladatokat apró darabokra tördelni. Könnyű belátni azonban, hogy minél kisebbek a darabok, a Thread Pool szervezésének a plusz költsége annál nagyobb mértékben adódik a hasznos munkához. Hogy ez mit jelent, kipróbálhatjuk a következő szélsőséges példaprogrammal. Fontos a tesztet legfeljebb 3.5-ös .NET alatt futtatni, mivel a 4.0 Thread Pool pont azon igények alapján lett optimalizálva, amelyekhez most közeledünk, többek között az alábbi kóddal:

const int testSize = 10000000;  
Stopwatch sw = Stopwatch.StartNew();
int counter = testSize;                    // tesztérték csökkentése 
for (int i = 0; i < testSize; i++)         // közvetlenül egy szálból
{
  if (Interlocked.Decrement(ref counter) == 0)   // Itt nem kell Interlocked, de
  {                                              // a másik tesztben igen, 
    Console.WriteLine(sw.ElapsedMilliseconds);   // az összehasonlíthatóság miatt használjuk
  } // if
} // for
            
sw = Stopwatch.StartNew();
counter = testSize;                        // tesztérték csökkentése
for (int i = 0; i < testSize; i++)         // Thread Pool-on keresztül
{
  ThreadPool.QueueUserWorkItem(            // Minden apró lépésnek külön Work Item
    o => {
           if (Interlocked.Decrement(ref counter) == 0)
           {
             Console.WriteLine(sw.ElapsedMilliseconds);
           } // if
         });
} // for            

A teszt első felének futásideje átlagos, kétmagos PC-n 200ms, a második pedig átlagban 20 másodperc. (bár a munkahelyi, szintén két magos, nem sokkal gyorsabb gép furcsamódon 5 másodperc alatt végez). Ez ugyan egy kisarkított példa, de érezhető belőle, hogy problémák vannak.

Mik ezek a problémák? Az egyik, hogy a Thread Pool a Work Item-eket egy láncolt listába teszi, azaz minden Work Item részére foglal egy Node-ot. A másik, és jelentősebb probléma, hogy a listát a QueueUserWorkItem() hívásnak úgy kell kezelnie, hogy több szálból a listát elérve, az lista adatszerkezet konzisztens állapotot mutasson.

Ennek egyik módszere, hogy a kritikus részeket egyszerre csak egy szál érheti el – a Windows operációs rendszer lehetőséget biztosít erre, és ezt a lehetőséget .NET alatt a Monitor osztállyal vagy a lock kulcsszóval ki is lehet használni. A Thread Pool-t kevés és nagy méretű feladattal ellátva ez a szinkronizálás nem okoz nagy problémát, a példaprogram a kicsi feladatok miatt azonban a Thread Pool szálait folyamatosan a védett programkódra irányítja, ahol azok az operációs rendszert folyamatosan a szinkronizációval túráztatják. Ez már kevés mag és kevés szál esetén is jelentős műveletigénnyel jár. A magok számának növekedésével viszont még egy új probléma jön elő: a védet programrészen a sok párhuzamos szál feltorlódik, mint a többsávos úton az autók sávlezáráskor. Ezt a jelenséget Lock Convoy-nak hívják. A jelenségre jellemző, hogy ha a fenti tesztprogram futása közben a gépen az egyik magot a BIOS-ban kikapcsolom, akkor a futásidő 14 másodpercre rövidül.

Eddig láttunk tehát indokot arra, hogy érdemes lenne minél jobban széttördelni a feladatokat a kiegyensúlyozott processzor/mag terhelés miatt. Másik oldalról arra is láttunk példát, hogy a .NET 3.5 Thread Pool-ja az ilyen feladatoknál jelentős hátráltató tényező.

Részfeladatok közötti függőségek

Van azonban más probléma is a hagyományos .NET Thread Pool-lal, ami nem hogy lassulást, de teljes leállást eredményezhet. Az alap probléma itt az, hogy a ThreadPool.QueueUserWorkItem() nem ad lehetőséget arra, hogy a feladatok között függőségeket adjunk meg. Emiatt a Thread Pool a feladatokat az elküldés sorrendjében hajtja végre, a feladatsor tehát FIFO működésű. Ezt a logikát Fair-nek mondják, a feladatok nem előzik be egymást, mindegyik kivárja a sorát. Nézzük azonban a következő programot:

ThreadPool.SetMaxThreads(2, 500);
using (var dependency = new ManualResetEvent(false))
{
  ThreadPool.QueueUserWorkItem(o => dependency.WaitOne());
  ThreadPool.QueueUserWorkItem(o => dependency.WaitOne());
  ThreadPool.QueueUserWorkItem(o => dependency.Set());
  dependency.WaitOne();
} // using

A program első lépésben beállítja a worker thread-ek maximális számát kettőre. Lehetne hagyni default értéken, de így egyszerűbb példaprogramot lehet készíteni. Ezután belehelyez a feladatsorba két munkaelemet, amelyek esetleg számolhatnának valamit, de a számítás közben egy ponton szükségük van egy információra, amit egy másik párhuzamosan futó művelet szolgáltat. Ezeknek a munkaelemeknek tehát van egy függősége. A függőséget most egy Event objektum testesíti meg, amire a munkaelem várakozik.

Közben a feladatsorba kerül az a feladat is, amelyik azt a műveletet végzi el, amelyikre a másik két szálnak szüksége van a lefutáshoz. Mivel a 3.5 .NET Thread Pool Fair, sorban veszi a munkaelemeket, és a rendelkezésre álló két szál elkezdi futtatni a két, függőséggel bíró elemet. Ezzel nem marad több szabad szál, így a harmadik munkaelemet soha senki nem fogja elvégezni, a program futása leáll.

A fentihez hasonlóan egyszerű esetben persze a programozó észreveszi a veszélyt, egy komplexebb algoritmus esetén azonban ez már nem olyan könnyű. A jó megoldás az lenne, ha a Thread Pool valamilyen módon támogatná a munkaelemek közötti összefüggések megadását, és ezt figyelembe venné a végrehajtási sorrendnél.

Hardver architekturális tényezők

Egy program futásidejét jórészt a kiválasztott algoritmusok határozzák meg. Az iskolában, amikor az algoritmusokat elemeztük, a lépések általában egyenköltséggel rendelkeztek – néha előfordult, hogy külön költséggel számoltuk az összeadásokat, szorzásokat vagy a memória mozgatást. Az elmúlt két évtized hardvereinél azonban van még egy tényező, amit figyelembe kell venni az algoritmusok tervezésénél. Ismert egy jelenség, amit “lokalitás elvének” hívnak. Ez röviden arról szól, hogy ha a program futásának egy rövid intervallumát vizsgáljuk, azt láthatjuk, hogy az többnyire ugyanazt, vagy legalább egymáshoz közel levő memóriaterületeket ér el. Erre a megfigyelésre építenek a processzor cache-ek, és részben .NET memóriakezelőjének generációkra épülő szervezése is.

Bár eredetileg a hardvert módosították a szoftverek lokalitás elvéhez, olyan mértékű optimalizációt értek el ezzel, hogy ha egy program egy részére nem jellemző az elv, nagyságrendekkel lassabb végrehajtási idővel kell számolni. Emiatt, ha a sebesség számít, a szoftvereknek is figyelembe kell venni a hardverek optimalizációs mechanizmusait. Hogy miről van szó, kipróbálható a következő programmal:

class Valami
{
  public int Tulajdonsag { get; set; }
} // class Value

class Program
{
  static void Main(string[] args)
  {
    Valami[] v = new Valami[50000000];             
    for (Int64 i = 0; i < v.Length; i++)            // Tömb feltöltése értékekkel
      // v[100001 * i % 50000000] = new Valami();   // össze-vissza, vagy
      v[i] = new Valami();                          // egyenletesen

    Stopwatch sw = Stopwatch.StartNew();

    int cntr = 0;
    for (Int64 i = 0; i < v.Length; i++)            // A referenciák vagy egyenletesek,
      cntr += v[i].Tulajdonsag;                     // vagy össze-vissza mutatnak a memóriába

    Console.WriteLine(sw.ElapsedMilliseconds); 
    
    return;
  } // Main()
} // class Program

A program futásideje, ha a “Valami” példányokat sorban rendezzük el, akkor 258ms. Ha azonban a kikommentezett sort használjuk inicializálásra, akkor a két szomszédos index által mutatott példány távolsága a memóriában több száz kilóbyte. Az értékeket összeadó ciklus emiatt össze-vissza hivatkozza a memóriát, ezt a helyzetet pedig nem tudja gyorsítani a cache. Emiatt a futásidő közel tízszeresére, 2266ms-re növekszik.

A Thread Pool és a lokalitás elve

Miért érdekes a Thread Pool szempontjából a lokalitás elve? Amennyiben törekszünk a programunk folyamatokra darabolására, akkor könnyen a következő ábrán látható helyzetben találjuk magunkat:

Egy Thread Pool szál éppen végrehajtott egy műveletet (1), amelynek eredményeképpen előállt valamilyen adat, az ábrán Részeredmény néven (2). Ez a Részeredmény valahol elhelyezkedik a memóriában (3), és mivel éppen most foglalkozott vele a program, a végrehajtó mag cache-ében is megtalálható (4). Az algoritmus olyan, hogy az előszámítás után, ami a Részeredmény értékét adta, a folyamat több, párhuzamos szálon folytatható. Ha bízunk abban, hogy több szabad mag akad a rendszeren, akkor például három részre törve a feladatot, azokat a Thread Pool feladatsorába helyezhetjük. (5)

Mi volna most teljesítmény szempontjából az optimális lépés? Az lenne a legjobb, ha az a szál, amely éppen most végzett a Részeredmény előállítását végző feladat végrehajtásával, a három új feladat közül felvenné az egyiket. Ez azonban ellene megy a FIFO logikának, amivel a 3.5 Thread Pool rendelkezik.

Egy másik megfontolandó ötlet, hogy amennyiben a többi mag szintén leterhelt, tehát van mivel foglalkozniuk, úgy a legjobb lenne, ha mind a három új munkaelemet ugyanaz a szál tudná feldolgozni, hiszen a lokalitás elve miatt a szükséges adatok jó eséllyel a szálat futtató mag cache-ében vannak.

Hol tartunk most?

A 3.5 Thread Pool több hátrányára rámutattunk, ami akadályoz abban, hogy a feladatainkat nagy mértékben tördeljük alfeladatokra. A feladatsor sok apró feladat és mag esetén nem hatékony. A feladatok végrehajtási sorrendje mindig FIFO jellegű, pedig bizonyos esetekben a végrehajtási sorrendet vagy a feladatok függőségei szerint, vagy a lokalitás elvének fenntartása miatt módosítani kellene. Mivel a többmagos rendszerek már itt vannak, és a magok számának növekedése egy tapasztalható trend, a .NET fejlesztőinek ezeket a problémákat meg kellett oldaniuk.

A .NET 4 által megvalósított Thread Pool jelentős átalakításon ment keresztül. Ezeket a változtatásokat vesszük most sorra.

Lock-Free listák

A Thread Pool feladatsora egy láncolt lista. A láncolt listáknak van egy kellemes tulajdonsága, mégpedig az, hogy a számunkra most fontos műveletei úgynevezett blokkolás mentes algoritmusok (Non-blocking algorithm). Hogy mit jelent ez, nézzük a következő ábrát egy új elem beszúrásáról:

Az ötlet alapja, hogy a lista bővítése két szakaszra osztható. Van egy előkészítési rész, amikor az új elem node lefoglalásra és inicializálásra kerül. Ez a lépés az igazán erőforrás igényes a lista bővítésénél, és ez idő alatt nincs szükség az adatszerkezet lock-olására. A kritikus rész a hármas pont, amikor a Head elem mutatóját rá kell állítani az új node-ra. Ez egy memóriaírás, ami egyébként önmagától atomi, ehhez ezért nincs szükség lockolásra. De várjunk csak, ez így biztos, hogy jó? Mi van, ha két konkurens szál egyszerre kezdi meg az előkészítési fázist? Nézzük a következő ábrát:

A probléma az, hogy a konkurens szálak mindkettője a jelenlegi Head elemre állítja az új node láncolását, hiszen mind a kettő azt feltételezi, hogy az ő új node-juk lesz a Head elem, ami pedig az eddigi Head elemre mutat. Az új Head beállítását ezután mind a két szál a saját új node-jára állítja be, de csak a másodjára írt érték marad meg.

Nyilván a fenti jelenség miatt volt lock az eredeti listakezelésben. De ha lock nélkül nem működik mégsem a lista bővítése, akkor mi ebben a Lock-Free? Valójában a Lock-Free elnevezésre kicsit úgy kell tekinteni, mint valami politikai nyilatkozatra. Amiről szó van, az annyi, hogy most kicsit más jellegű, úgynevezett atomi-lockkal oldható meg a feladat. A Head node átírásánál az okozza a gondot, hogy az új node előkészítése közben egy másik szál átírja a Head-et, a mi node-unk viszont még a régire mutat. Ez a probléma kiküszöbölhető, ha előkészítés után, de a Head átírása előtt ráellenőrzünk, hogy nem-e írták át a Head értéket, és ha nem, akkor történik meg az átírás általunk, ha pedig pechünk volt, megismételjük az eljárást az új értékekkel. Amire tehát szükség van, az a következőhöz hasonló ellenőrzés:

if (head == oldHead)
{
  head = newHead;
} // if

Ez az ellenőrzés több lépésből áll, és mint ilyen, továbbra is ki van téve a konkurens szálak problémáinak. Mi van, ha lefutott az ellenőrzés, és az ez utáni pillanatban egy másik szál mát át is írta a változót? Az kellene, hogy a fenti if-es szerkezet atomi módon fusson le. Itt megint visszajutnánk a Lock használatához, de szerencsére ehhez a speciális esethez már van más eszköz is.

Az intel processzorok a 486-os verzió óta rendelkeznek egy CMPXCHG gépi utasítással, ami pont a fenti if-es szerkezetet valósítja meg – atomi módon. Természetesen a processzornak valahogy le kell szinkronizálni a többi processzorral (maggal), hogy az ellenőrzés és az írás között az adott terület ne változzon meg, de ezt már hardveresen, régebben a memória, újabban a cache vezérlő segítségével megoldja. Ez ugyan némi időveszteséget okoz, de jóval kevesebbet, mint ha az operációs rendszer segítségével, a Monitor.Enter vagy lock kulcsszó mögötti critical section-ökön keresztül végeznénk ugyanezt (a critical section pont a CMPXCHG-t használja a kizárólagosság megszerzéséhez).

A CMPXCHG gépi utasítás, mivel igen hasznos, a .NET-en keresztül is elérhető az Interlocked.CompareExchange() függvényen keresztül, és ennek segítségével az új node felvétele a következőhöz hasonlóan működik:

var oldHead = head;    // eddigi head értékének tárolása
var newHead = new Node { Value = ..., Next = oldHead }
while (Interlocked.CompareExchange(ref head, newHead, oldHead) == false)
{
  oldHead = head;          // Helyzet változott, állapot frissítése
  newHead.Next = oldHead;
} // while

A “Lock-Free” megoldás sokat segít a sebességen, azonban ha a Thread Pool láncolt listát használ, akkor minden munkaelemhez külön node-ot kell foglalni. Ezzel egy munkaelem feladatsorba helyezése végigmegy a memóriakezelő függvényein, ráadásul ha ezrével készülnek node-ok, a Garbage Collector-t is jelentős munkával látják el. Ezek miatt a Thread Pool feladatsora a node-okat csoportokba (tömbökbe) szervezi, a tömbben pedig szintén “Lock Free” módon, atomi inkrementálással szerez magának node slot-ot az aktuális szál. Némileg vicces, hogy a “Lock Free” algoritmus itt a “LOCK INC” gépi utasítással van megvalósítva, ami pedig szintén elérhető .NET alatt az Interlocked.Increment() függvénnyel. Végül pedig, a most bemutatott, többszálú alkalmazásokhoz optimalizált sor adatszerkezet elérhető a ConcurrentQueue osztályt használva. Ez az adatszerkezet kicsit más, mint a hagyományos láncolt lista, de a láncolt listára esetünkben csak azért volt szükség, hogy O(1) idő alatt lehessen új elemet a sorba rakni, és elemet abból kiszedni. Ezt pedig tudja a módosított, hibrid lista is.

Hogy mennyit javít a teljesítményen az új feladatsor? .NET 4 alatt a korábbi, 3.5 alatt 20 másodpercig futó kód ugyanazon a számítógépen 2.8 másodperc alatt lefut.

Lokális feladatsorok

Emlékezzünk rá, hogy mi volt a kiinduló probléma azzal kapcsolatban, hogy a feladatokat próbáljuk minél apróbb darabokra törni. Azért volt szükség rá, hogy egyfajta load balance-ot lehessen megvalósítani a különbözően terhelt magok között. Egy korábbi ábrán a Részeredmény számítása után azért lett a feladat három részre törve, mert egyrészt ez megoldható volt, másrészt pedig ha lett volna másik két szabad mag, a teljes számítás hamarabb végetér. Akkor viszont, ha a többi mag is dolgozik, az lett volna az optimális, ha a mostani szál dolgozza fel a részfeladatokat a lokalitás elve (és így a cache) miatt. Tegyük fel, hogy a program általánosságban olyan felépítésű, hogy a feladatokat részfeladatokra tördeli, és a rendszerben az összes szál ilyen jellegű feladatokon dolgozik. Ekkor a feladatok előállítják a részfeladataikat, és minden szál számára egyrészt van munka, másrészt pedig az az optimális, ha a részfeladatokat is ők oldják meg. Részfeladat átcsoportosításra elvileg csak akkor van szükség, ha az egyik szál kifutott a munkából.

Egyre inkább az bontakozik ki, hogy előnyös, ha egy Thread Pool szál saját, lokális feladatsorral rendelkezik. Egy a szál által végrehajtott feladat, amikor előállítja saját részfeladatait, akkor a részfeladatokat a lokális feladatsorba helyezi. A lokális feladatsornak megvan az a hatalmas előnye, hogy (többnyire) csak az a szál használja, amelyikhez tartozik. Ekkor kicsi az esélye, hogy a Lock Free részben bemutatott ComparedExchange köré szervezett ciklusnak tekernie kell. Másik előny, hogy a lokális feladatsorba a szál által végrehajtott feladat alfeladatai kerülnek. A feladat teljes egészében akkor lesz kész, ha az összes alfeladat kész van, az viszont mindegy, hogy milyen sorrendben van kész. Mivel feltételezhető, hogy a legújabban behelyezett alfeladat számára nagyobb eséllyel vannak még a cache-ben adatok (azt mondják a feladatra, hogy forró (hot)), emiatt a lokális feladatsorok LIFO működésűek (unfair-ek). Ezt a globális feladatsorral nem lehet megcsinálni, mivel ott egymástól esetleg független feladatok lehetnek a feladatsorban. Ha a globális sor LIFO elvű lenne, egy korábban a sorba került munkaelem végrehajtását egy később bekerült munkaelem hosszú időre megakadályozhatja, ha az folyamatosan új munkaelemeket helyez a globális feladatsorba. Ehhez hasonló jelenség a lokális feladatsoron most előfordulhat, de az a különbség, hogy most tudjuk, hogy egy logikai feladat alfeladatairól van szó, és most az egyik alfeladat akadályozza a másik alfeladat végrehajtását – ami pedig nem számít, mivel a főfeladat úgyis akkor lesz kész, ha az összes részfeladat elkészült – tekintet nélkül a sorrendre.

A .NET 4 Thread Pool-jának a fentieknek megfelelően van egy globális, és minden szálnak van egy lokális feladatsora. A globális feladatsor FIFO, a lokális pedig LIFO működésű. A lokális feladatsorba akkor kerülnek feladatok, a szálon végrehajtott programkód feladatokat küld a Thread Pool-nak.

Work Stealing

Végigtárgyaltuk azt az esetet, amikor a szálak dolgoznak, és olyan feladatokon, amelyek előállítják saját részfeladataikat. Az esetek egy részében ezután a szálak maguk feldolgozzák a részfeladatokat, szinte mintha eredetileg nem is történt volna meg a tördelés. Ha ez lenne az általános helyzet, akkor nem érné meg a tördelés, felesleges komplexitást vittünk a programba a semmiért. A helyzet azonban az, hogy nem olyan könnyű úgy szervezni a dolgokat, hogy a magok mindegyike végrehajtási idő tekintetében ugyanannyi feladatot kapjon. Ekkor lép életbe a feladatlopásnak (Work Stealing) nevezett mechanizmus. Ha egy Thread Pool szálnak nincs feladata, akkor több dolog történhet. Ha túl sok szál jött létre (például több, mint ahány mag van a rendszerben), akkor a szál megszűnhet. Ha azonban a szálak számát nem érdemes tovább csökkenteni, mert például az alámenne a rendszerben levő magok számának, akkor a szál számára feladatot érdemes keríteni, hogy legyen min dolgozni a szabad magoknak. A szál ilyenkor megnézi, hogy van-e felvehető feladat a globális feladatsorban. Ha nincs, van még egy utolsó esélye, hogy feladatot szerezzen.

Amikor nincs feladat a globális feladatsorban, akkor a szál elkezdi végigkutatni a többi szál lokális feladatsorát. Emlékezzünk a Thread Pool szálak LIFO jelleggel a legutóbb a feladatsorba helyezett munkaelemet fogják kivenni, arra számítva, hogy a cache több területet tartalmaz a szükséges feladathoz. A lopásra készülő szál emiatt illedelmesen a legrégebb óta várakozó munkaelemet fogja kivenni, tehát a feladatsor másik végével dolgozik, mint a feladatsor gazdája – várhatólag ezzel okozza a legkisebb törést a lokalitás elvében.

Egy lopási folyamat látható az alábbi ábrán, két szál feladatsorán szemléltetve.

Az (1) pontban mind a két szálnak van feladat a feladatsorában, ezeket fel is veszik, és elkezdik végrehajtani. A baloldali szál a “t” feladat végrehajtása után azonban nem rendelkezik több feladattal, míg a jobboldali szálon az “a” feladat két alfeladatot generált, “a1” és “a2” néven (2). A lokális feladatsorok logikája alapján a jobboldali szál a legkevésbé rég a sorba került “a1” feladatot fogja felvenni. A baloldali szál viszont kénytelen feladatot keresni magának. Ha a globális feladatsor üres, akkor a jobboldali szál feladatsorát fogja használni, és kiveszi belőle a legrégebben odakerült, “c”-bel jelölt feladatot (3). Amennyiben a “c” feladat új alfeladatokat fenerál, akkor ezek már a baloldali szál feladatsorába kerülnek (4).

A lokális feladatosorok a most leírt stratégiához tervezett adatszerkezetek, úgynevezett Work Stealing Queue-k. Ezek részben Lock-Free adatszerkezetek, LIFO műveletekhez nem igényelnek lockolást, de a sor végéről (FIFO pop) csak lock-ot használva lehet elemet levenni.

Inlining

A cikk elején volt egy példaprogram, ami 3.5-os Thread Pool azon hátránya miatt, mert nem lehet feladatok között összefüggéseket kifejezni, leblokkolt. A régi Thread Pool-lal kívülről nézve az a probléma, hogy lényegében csak egy delegate-et (rendben, korábbról tudjuk, hogy egy elég fajsúlyos ExectutionContext-et is) teszünk a feladatsorba. Az új Thread Pool azonban nem csak a korábbi QueueUserWorkItem() függvényhívással érhető el. Az új Thread Pool-lal együtt egy új koncepció is bevezetésre került, és ezek a Task-ok. A Task lényegében az a dolog, amit az eddigiekben kerülgettünk a feladatok részekre törése kapcsán. A Task-ot, mint koncepciót a Task osztály testesíti meg a .NET 4-ben. Maga a témakör olyan széles, hogy a Task osztály, és lehetőségei, illetve működése egy külön cikkben kerül nagyító alá. Most csak felületesen érintjük a Task osztályt, hogy az inlining lehetőségét láthassuk.

Ha a végrehajtandó feladatunkat olyan módon szeretnénk felépíteni, hogy a többmagos számítógépek lehetőségei ki legyenek használva, akkor az új koncepcióban, a Task-okban kell gondolkodnunk. A Task nem csak egyszerűen egy feladatot jelent. A Task egy olyan feladatot jelent, amit tovább lehet bontani egyéb Task-okra, ami lehetőséget ad arra, hogy a különböző Task-ok között összefüggéseket fejezzünk ki. A Task mint koncepció megvalósítása a .NET-ben a Task osztály. Amellett, hogy a Task osztály lehetőséget ad alfeladatok létrehozására és a Task-ok közötti kapcsolatok leírására, a Task-ok, illetve az őket kezelő TaskScheduler osztályok ismerik az új Thread Pool lehetőségeit, és ennek megfelelően kerülnek a Task-ok a globális, vagy a megfelelő szál lokális Thread Pool-jába.

A Task osztálynak van egy Wait függvénye, így ha egy Task végrehajtása egy másikétól függ, nem kell saját szinkronizációs mechanizmust kidolgoznunk, mint a korábbi példában a dependency nevű ManualResetEvent. Nem a megspórolt munka azonban a legnagyobb nyereség. A 3.5 NET alapokra épülő példának két hátránya volt. Egyrészt, amikor a feladatnak várakozni kellett, akkor a szál leállt, nem végzett hasznos munkát. Másrészt a szálkorlát miatt nem volt ami felvegye azt a feladatot, ami egyébként elvégezte volna azt a számítást, amire a várakozó szálaknak szüksége volt. Ez kicsit ellentmondásos helyzet, hogy egyrészt az egyik szál vár, másrészt a másik munkára nem marad, ami végrehajtsa.

A Task.Wait() függvény viszont tud egy trükköt, amire ebben a helyzetben pont szükség van. A Task.Wait() megvizsgálja, hogy az adott Task példány már lefutott-e. Ha igen, a szál futhat tovább. Ha még nem futott le a Task példány, de a futása elkezdődött, akkor a szál várakozási állapotba kerül, így ugyanaz történik, mint a régi Thread Pool esetében. Ekkor csak a kész szinkronizációs mechanizmusokat nyertük a .NET 4 használatával. Ha azonban a Task példány, amire várakozni kell, még a feladatsorban van, akkor az történik, hogy a Task.Wait() függvény előveszi a feladatot a feladatsorból, és végrehajtja azon a szálon, amelyik egyébként a Task példányra várakozna. Ezt a mechanizmust nevezzük inlining-nak.

Konklúzió

A .NET 3.5 és korábbi Thread Pool-ok nagyobb méretű feladatok elvégzésére lett tervezve. A többmagos rendszerek előretörésével azonban új igény jelentkezett a többszálú programok kiszolgálásában. A megnövekedett számú és kisméretű feladatokat a régi Thread Pool nem tudja hatékonyan kiszolgálni. A .NET 4 Thread Pool-ja az új igények figyelembevételével lett újraírva, illetve bevezetésre került a Task-ok fogalma, amin keresztűl az új Thread Pool hatékonyan kiaknázható.

A következő cikkben a Task-ok és a TaskScheduler-ek működésével ismerkedünk meg.

  1. #1 by x on 2011. February 28. - 14:29

    Szia,
    Nagyon jó cikkek, csak így tovább!
    Egy kérdés: ezt a sok tudást honnan, milyen könyvekből szedted össze?
    Tudsz ajánlani a témához kapcsolódó könyvet?

    • #2 by Tóth Viktor on 2011. February 28. - 14:56

      Szia,
      Nincsenek sajnos jó könyvek a témában, legalábbis én nem találkoztam velük. Pont ez volt az egyik indítékom, olyan cikkeket szerettem volna írni, amilyen információra én vágytam, amikor tanultam/tanulom ezeket. Általában blogokból, és a kód bogarászásából derítem ki, hogy mi hogyan működik, sok esetben jól jön az SSCLI, abból lehet következtetni az éles CLR működésére. Mondjuk a 4.0-as Thread Pool-nál pont nem, mert az nagyon megváltozott, de az eddigi cikkekhez az SSCLI-t használtam. 4.0-as thread dolgokban az egyik legjobb információforrás a pfxteam blogja:
      http://blogs.msdn.com/b/pfxteam/

  1. Aszinkron programozás – Áttekintés – Újdonságok a C# 5-ben « DotNetForAll

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: