Elosztott zármentes feladatütemezés

A feladatümezés napjaink számítógépes rendszereinek egyik fontos alkotóeleme. A legalsó, hardverközeli szinten a processzorok egy ütemezőhöz hasonló algoritmus szerint osztják szét a feladatokat különböző feldolgozási egységeik között. Ehhez hasonló működés figyelhető meg a heterogén rendszerek világában is, ahol az egyes segédprocesszorok között válogatjuk szét a beérkező feladatok úgy, hogy azokat a lehető leghatékonyabb módon tudjuk végrehajtani. A feladatütemezés ugyancsak meghatározó a szoftveres rendszerekben is: az operációs rendszerek a felhasználói és rendszerfolyamatok, míg a szerveralkalmazások a bejövő kérések ütemezésére használják őket. A koncepció hasonló módon megállja a helyét az elosztott - és különös módon a grid - rendszerek világában is.

A többmagos processzorok térnyerésével a hagyományos, szekvenciális programozási módszerek egyre kevésbé használhatók nagy teljesítményű alkalmazások implementálásához. Az új, párhuzamos programozási módszerek közül kitűnnek a zármentes algoritmusok, mivel nem várt szálhibák és késleltetések mellett is jó teljesítményt biztosítanak. A kedvező skálázódás mellett védenek a deadlock és livelock jelenségek kialakulásától, melyek a hagyományos, zárakat alkalmazó megoldások legsúlyosabb problémái közé tartoznak.

A dolgozatban két új algoritmust mutatok be, amelyek képesek a feladatok elosztott, zármentes ütemezésére úgy, hogy közben a feladattípusok szintjén kölcsönös kizárást is megvalósítanak. Ez a jó skálázódás és teljesítmény mellett lehetővé teszi azt is, hogy az algoritmusokat akár alacsony, hardver-közeli, akár magas, az elosztott rendszerek szintjén valósítsuk meg. Mindkét megoldás legfontosabb eleme egy round-robin ütemező - esetleges particionálással -, amelyet olyan fogyasztó szálak vesznek igénybe, amik bizonyos szabályokat követnek a feladatok magukhoz rendelésekor. A dolgozatban bemutatok egy kísérleti implementációt, amely teljesítményének növelése érdekében a szálankénti memóriaterület kihasználásával csökkenti a termelői és fogyasztói szálak versengését. Ez a megoldás csak egy szóhosszú compare-and-swap utasításokat használ, ezért a legtöbb modern architektúrán implementálható. Végül egy életszerű példán mutatom be mérési eredményeimet, melyeken látható, hogy az új, zármentes algoritmusok nagyobb megbízhatóság mellett is képesek hasonló teljesítményt nyújtani mint a hagyományos, zárakat alkalmazó megoldások.

szerző

• 
  Paral Zsolt
  Mérnök informatikus szak, alapképzés
  alapképzés (BA/BSc)

konzulens

• 
  Dr. Dudás Ákos
  docens, Automatizálási és Alkalmazott Informatikai Tanszék

helyezés