Suvremene računalne platforme rijetko funkcioniraju s idealiziranom pretpostavkom o fiksnoj količini računalne snage. Strojevi otkazuju, otvaraju se prozori za održavanje, a usluge s visokim prioritetom dinamički zauzimaju resurse, ostavljajući stalno promjenjiv skup kapaciteta za batch poslove niže važnosti. Kada su ti batch poslovi neprekidni – moraju se izvršiti do kraja bez prekida – problem raspoređivanja postaje posebno osjetljiv. Preuranjeno pokretanje dugog posla može dovesti do uzaludnog truda ako kapacitet padne, dok predugo čekanje može uzrokovati da posao propusti svoj rok.
Model raspoređivanja poslova u dinamičnom okruženju
U radu pod naslovom Maksimiziranje propusnosti neprekinutih poslova pri promjenjivom kapacitetu, predstavljenom na konferenciji SPAA 2025., istraživači su uveli prve algoritme s konstantnim faktorom aproksimacije za maksimiziranje propusnosti u takvim nestabilnim okruženjima. Istraživanje razlikuje između offline scenarija, gdje su cjelokupni skup poslova i vremenska crta kapaciteta poznati unaprijed, i online scenarija, gdje poslovi pristižu u stvarnom vremenu i odluke moraju biti neopozive. U nastavku sažimamo model, ključne teorijske rezultate i implikacije za stvarne raspoređivače u oblaku.
Autori modeliraju jedinstveni resurs – poslužitelj ili homogeni klaster – čiji se kapacitet mijenja kroz diskretne vremenske intervale. U bilo kojem trenutku, profil kapaciteta određuje koliko poslova može istovremeno raditi. Zadana je zbirka potencijalnih poslova, svaki opisan s četiri atributa:
- Vrijeme otpuštanja: najraniji trenutak kada posao postaje podoban za izvršavanje.
- Rok: tvrdi rez koji označava krajnji rok do kojeg posao mora biti završen.
- Vrijeme obrade: neprekidno trajanje potrebno za dovršetak posla.
- Vrijednost: vrijednost koja se ostvaruje ako posao završi unutar svog vremenskog okvira.
Cilj je odabrati podskup poslova i svakom dodijeliti neprekidni interval izvršavanja koji se u potpunosti nalazi unutar njegovog vremenskog prozora od otpuštanja do roka, a da se pritom nikada ne prekorači trenutačni kapacitet. Maksimizira se ukupna vrijednost uspješno dovršenih poslova – propusnost.
Offline i online scenariji raspoređivanja
Istražuju se dva okruženja:
- Offline okruženje: U ovom scenariju, svi podaci o poslovima (vrijeme otpuštanja, rok, vrijeme obrade, vrijednost) i cjelokupna vremenska crta promjene kapaciteta poznati su unaprijed. To omogućuje potpunu optimizaciju rasporeda prije početka izvršavanja. Algoritmi razvijeni za ovaj slučaj postižu rezultate unutar konstantnog faktora od optimalnog, što znači da je ostvarena propusnost zajamčeno blizu teoretskog maksimuma, bez obzira na složenost ulaznih podataka.
- Online okruženje: Ovdje poslovi pristižu postupno tijekom vremena, a odluke o njihovom raspoređivanju moraju se donijeti u trenutku dolaska posla, bez poznavanja budućih poslova ili promjena kapaciteta. Ove odluke su neopozive. Unatoč nedostatku potpunih informacija, istraživači su razvili algoritme koji također jamče konstantan faktor aproksimacije, osiguravajući učinkovitost čak i u uvjetima neizvjesnosti.
Ključni doprinos rada leži u razvoju prvih algoritama koji pružaju ovakva snažna jamstva performansi u oba scenarija. Prije ovog istraživanja, postizanje sličnih garancija u dinamičnim i nepredvidivim okruženjima bilo je izuzetno teško, ako ne i nemoguće.
Implikacije za računalne oblake i buduća istraživanja
Rezultati ovog istraživanja imaju značajne praktične implikacije za upravljanje resursima u velikim računalnim oblacima. Sposobnost pouzdanog raspoređivanja neprekinutih poslova, čak i kada su resursi dinamični i kapacitet varira, ključna je za