Să spunem că vrei să implementezi un algoritm de planificare automată a unui set de pași, parte a unui workflow, în care fiecare pas poate depinde de unul sau mai mulți pași din acesta. Bineînțeles că algoritmul pe care dorim să îl implementăm, se dorește a fi cât mai optim, în așa fel încât să genereze cea mai bună variantă de planificare a tuturor pașilor (unii pași pot fi în paralel executați), în așa fel încât să se minimizeze timpul de rulare al întreg workflow-ului.
O să dau și un exemplu pentru a face lucrurile și mai clare. Să zicem că ai un workflow alcătuit din 5 pași: p1, p2, p3, p4, p5 și următoarea listă de dependințe între aceștia:
- p3 -> p1 și p2 (Înterpretare: p3 depinde de p1 și p2)
- p4 -> p3 (Înterpretare: p4 depinde de p3)
- p5 -> p1 (Înterpretare: p5 depinde de p1)
Nice. Ce ar însemna în realitatea de zi cu zi ca un pas să depinde de altul? Păi foarte simplu. Ar însemna că pentru a executa un pas din workflow, vei avea nevoie de outputul altuia.
Având în vedere aceste constrângeri, algoritmul de planificare ar trebui să scoată următorul output pentru executarea cât mai optimă a workflow-ului:
- [(p1, p2), (p3, p5), p4], unde (*) înseamnă un set de pași executați în paralel iar [*] înseamnă un set de pași executați secvențial.
Se cere să se implementeze un algoritm prin care să se obțină cel mai bun mod de planificare posibil.
O posibilă implementare
Putem construi un graf, nodurile fiind pașii, iar arcele dependințele dintre acestea. Graful îl putem reprezenta ca și o matrice, în care atât pe linii cât și pe coloane avem pașii. Mai departe, în matrice putem pune 1 dacă există o dependință sau 0 dacă nu există. Având în vedere toate aceste observații, vom avea următoarea matrice:
| p1 | p2 | p3 | p4 | p5 | |
|---|---|---|---|---|---|
| p1 | 0 | 0 | 0 | 0 | 0 |
| p2 | 0 | 0 | 0 | 0 | 0 |
| p3 | 1 | 1 | 0 | 0 | 0 |
| p4 | 0 | 0 | 1 | 0 | 0 |
| p5 | 1 | 0 | 0 | 0 | 0 |
Ce înseamnă să am pe o linie 0, în matricea de mai sus? Simplu. Înseamnă că pasul respectiv (dat de linia asociată) nu depinde de niciun alt pas. Asta este ideal pentru noi, pentru că înseamnă că putem extrage pasul respectiv și îl putem planifica spre execuție. Cu alte cuvinte, putem extrage pașii p1 și p2. O dată ce am extras toți pașii în care există 0 pe linii, pot să merg mai departe și să marchez aceste linii cu -1 și totadată să pun 0 pe toate coloanele de unde am extras diverși pași.
Matricea după prima rundă de extrageri:
| p1 | p2 | p3 | p4 | p5 | |
|---|---|---|---|---|---|
| p1 | -1 | -1 | -1 | -1 | -1 |
| p2 | -1 | -1 | -1 | -1 | -1 |
| p3 | 0 | 0 | 0 | 0 | 0 |
| p4 | 0 | 0 | 1 | 0 | 0 |
| p5 | 0 | 0 | 0 | 0 | 0 |
Continuăm cu runda 2, prin a extrage alți pași care au pe linie numai 0. În acest caz, vorbim de pașii p3 și p5. Acești pași pot fi executați în paralel. Cu aceste modificări, matricea devine:
| p1 | p2 | p3 | p4 | p5 | |
|---|---|---|---|---|---|
| p1 | -1 | -1 | -1 | -1 | -1 |
| p2 | -1 | -1 | -1 | -1 | -1 |
| p3 | -1 | -1 | -1 | -1 | -1 |
| p4 | 0 | 0 | 0 | 0 | 0 |
| p5 | -1 | -1 | -1 | -1 | -1 |
Ultimul pas este să extragem p4. Algoritmul se oprește când toate matricea conține numai -1.
Planul cel mai optim de execuție este: [(p1, p2), (p3, p5), p4]
Ce facem cu dependințele ciclice?
Să spunem că avem doar 3 pași în workflow, pași care depind unul de altul în modul următor:
- p2 -> p1
- p3 -> p2
- p1 -> p3
Aici avem o dependință ciclică indirectă. Cum ar arăta matricea noastră:
| p1 | p2 | p3 | |
|---|---|---|---|
| p1 | 0 | 0 | 1 |
| p2 | 1 | 0 | 0 |
| p3 | 0 | 1 | 0 |
După cum se poate observa, în cazul în care nu se poate extrage nicio linie completă cu 0, atunci algoritmul se va opri pentru că vom avea cu siguranță o dependință ciclică directă sau indirectă.
Acestea fiind spuse, vă urez un călduros: spor la implementat! 🙂
