Hatékony ütemezés változó erőforrások mellett: új algoritmusok a felhőben
A modern felhőalapú számítástechnika egyik legnagyobb kihívása, hogy az erőforrások nem állandóak, hanem idővel változnak. Egy szerver nem mindig ugyanannyi processzormagot kínál, és egy gépelosztott klaszter kapacitása is ingadozhat például karbantartás, hardverhibák vagy energiahatékonysági korlátok miatt. Ez a dinamikus környezet alapjaiban változtatja meg a hagyományos algoritmikus feladatütemezés megközelítését, ahol eddig gyakran fix erőforrásokkal számoltunk.
Az ütemezési probléma kihívásai változó kapacitás mellett
Képzeljünk el egy olyan rendszert, ahol a számítási kapacitás időről időre változik, és a feladatoknak szigorú határidejük van. Ezek a feladatok különböző súlyokkal bírhatnak, vagyis nem mindegy, melyik teljesül. A feladatok nem megszakíthatók, tehát ha egyszer elkezdjük őket, akkor folyamatosan kell futniuk a megadott időablakon belül, különben elveszik az addigi munka eredménye. Ilyen környezetben az ütemező algoritmusnak meg kell hoznia a döntést: mikor érdemes egy hosszabb feladatot elindítani, vagy inkább várjunk egy stabilabb időszakra, hogy maximalizáljuk a teljesített és értékes feladatok számát.
Ez a probléma különösen bonyolult úgy, hogy a magas prioritású feladatok bármikor igénybe vehetik az erőforrásokat, így a maradék kapacitás változó és kiszámíthatatlan lehet. Olyan ez, mintha egy étteremben a VIP vendégek asztalait bármikor lefoglalhatnák, és nekünk kellene a fennmaradó helyeket úgy kiosztani, hogy minél több vendég elégedetten távozzon.
Innovatív algoritmusok az offline és online környezetekben
A közelmúltban bemutatott kutatás, amelyet a SPAA 2025 konferencián ismertettek, új megközelítéseket kínál ezen összetett ütemezési problémára. A tanulmány két környezetet vizsgál: az offline esetet, amikor előre ismerjük az összes feladatot és a kapacitás változásait, illetve az online esetet, ahol a feladatok érkezése valós időben történik, és az algoritmusnak azonnali, visszavonhatatlan döntéseket kell hoznia.
Az offline esetben egy egyszerű, úgynevezett mohó (Greedy) stratégia is meglepően hatékony: egységes értékű feladatok esetén garantáltan legalább a felét tudja teljesíteni annak, amit az optimális megoldás kínálna. Ha a feladatok értéke eltérő, egy bonyolultabb, úgynevezett primal-duális módszer biztosít egy negyed akkora teljesítményt, ami szintén jelentős eredmény az NP-nehéz problémák között.
Az online kihívások és a megszakítási modellek
Az igazi nehézséget az online helyzet jelenti, ahol a jövőbeli feladatokat nem ismerjük előre. Itt a hagyományos, megszakítás nélküli algoritmusok szinte teljesen megbuknak, mert egy rosszul időzített hosszú feladat elindítása miatt elveszhet sok kisebb, de összességében értékesebb feladat végrehajtási lehetősége. Ezért a kutatók két új modellt javasoltak, amelyek megengedik a futó feladatok megszakítását, de eltérő feltételekkel.
Az első modellben a megszakított feladat később újraindítható, így a korábbi munka elveszhet ugyan, de a feladat nem vész el végleg. Ez a rugalmasság lehetővé teszi, hogy az algoritmus a változó kapacitás és feladatbeérkezés mellett is legalább a feladatok felét hatékonyan kezelje, azaz megtartsa a 1/2 versenyképességi arányt.
A második, szigorúbb modellben a megszakított munkát nem lehet újrakezdeni, ami jelentősen megnehezíti a helyzetet, és ennek a kutatásnak az eredményei különösen fontosak lehetnek a valódi rendszerek tervezésénél.
Ez a kutatás tehát nemcsak elméleti szinten járul hozzá a változó kapacitású rendszerek jobb megértéséhez, hanem konkrét, alkalmazható algoritmusokat is kínál, amelyek segítségével a felhőszolgáltatók és nagy adatközpontok hatékonyabban kezelhetik az erőforrásaikat, maximalizálva az elvégzett munka értékét. Ha mélyebben érdekel a téma, érdemes megtekinteni a hivatalos kutatási blogot, ahol részletesebben is olvashatsz az algoritmusokról és az eredményekről.
