[DUS | Prednáška] 8 - Workflow siete a problém uviaznutia 1

Zhrnutie prednášky

Prednáška predstavuje workflow siete ako podtriedu Petriho sietí s jednoznačným vstupným a výstupným miestom, pričom na začiatku je označené jedinou značkou len vstupné miesto. Zavádza pojem korektnosti (soundness) workflow siete – z každého dosiahnuteľného značkovania musí byť možné dosiahnuť stav so značkou len vo výstupnom mieste, a to musí byť jediné takéto dosiahnuteľné značkovanie. Na ilustratívnom príklade plánovania výpočtových úloh v cloude (pridelenie procesora a pamäte, beh úlohy, uvoľnenie zdrojov) sú demonštrované dva typy nekorektnosti – uviaznutie (deadlock) a predčasné/nesprávne ukončenie s pretrvávajúcimi neuzavretými vetvami. Ukazuje sa kľúčové tvrdenie, že korektná workflow sieť je vždy ohraničená, čo umožňuje na overenie korektnosti použiť graf dosiahnuteľnosti a klasický algoritmus na test ohraničenosti. Prednáška smeruje k budovaniu grafu dosiahnuteľnosti pre konkrétny príklad s cieľom overiť jeho korektnosť.

• - Workflow sieť je Petriho sieť s jedným vstupným a jedným výstupným miestom, na začiatku označené len vstupné miesto jednou značkou.
• - Korektnosť (soundness) workflow siete znamená, že z každého dosiahnuteľného značkovania sa dá dosiahnuť značkovanie so značkou vo výstupnom mieste, a je to jediné takéto dosiahnuteľné značkovanie.
• - Nekorektnosť môže vzniknúť dvomi spôsobmi: uviaznutím (deadlock) alebo dosiahnutím iného značkovania obsahujúceho značku vo výstupnom mieste popri neukončených vetvách.
• - Ilustratívny príklad: proces plánovania výpočtovej úlohy v cloude – pridelenie pamäte a procesora, beh výpočtu, uvoľnenie zdrojov a ukončenie úlohy.
• - Kľúčové tvrdenie: každá korektná workflow sieť je nutne ohraničená, teda neohraničená sieť je automaticky nekorektná.
• - Na overenie korektnosti možno využiť graf dosiahnuteľnosti a algoritmus na testovanie ohraničenosti siete.
• - Prezentácia demonštruje konkrétne príklady nekorektných sietí vrátane deadlocku a duplicitného dosiahnutia koncového značkovania.

Zhrnutie pripravené s pomocou AI z prepisu videa.