Přeskočit na obsah

Tato stránka byla automaticky přeložena z angličtiny, jediného jazyka, ve kterém se tento web píše. Číst originál.

Vlny provádění se počítají z grafu a úkoly v jedné vlně, které sahají na stejné cesty, se hlásí jako serializované

Vlna je množina úkolů, jejichž závislosti jsou všechny splněny ve stejné hloubce. Vlna nula je každý kořen; úkol leží o vrstvu za svou nejhlubší závislostí. Vlny se odvozují při každém čtení a nikde se neukládají, takže žádný plán provedení nemůže zastarat. Společná vlna je pro souběžný běh dvou úkolů nutná, ale ne postačující: pokud se jejich deklarované cesty rozsahu překrývají, překryv se ohlásí a úkoly se serializují.

deklarovaný stavdeklarovaný stav: zaručeno Deklarováno jako deterministické a blokující, implementováno a s uvedeným behaviorálním testem, který to má dokázat. Zda to zaznamenaný běh podporuje, říká verdikt důkazů zobrazený vedle.

zaznamenané důkazyzaznamenané důkazy: nespuštěno Deklarováno jako zaručené, ale nepodložené zaznamenaným během: test je pojmenován, ale žádný úspěšný běh nad současnými vstupy zaznamenán není. jak se zaznamenávají důkazy

Sdílení vlny je pro souběžnost nutné, ale nestačí. Překrývající se deklarovaný rozsah se serializuje konzervativně, protože falešná serializace stojí čas a falešná paralelnost stojí konflikt.

Co to znamená

Vlna je množina úkolů, jejichž závislosti jsou všechny splněny ve stejné hloubce. Vlna nula je každý kořen; úkol leží o vrstvu za svou nejhlubší závislostí. Vlny se odvozují při každém čtení a nikde se neukládají, takže žádný plán provedení nemůže zastarat. Sdílení vlny je nutné, aby dva úkoly běžely souběžně, ale nestačí: pokud se jejich deklarované cesty scope překrývají, překryv se ohlásí a úkoly se serializují.

Princip

Stejné vrstvení podle Kahna, které odhaluje cykly, přiřazuje vlny. Konflikt rozsahu je test obsažení na deklarovaných cestách dvou úkolů ve stejné vlně, které jsou oba READY nebo ACTIVE; cesta rovná jiné, uvnitř ní nebo ji obsahující se počítá jako překryv.

Jak to vidět

majordomus plan waves
# Wave 1
#   I0002   READY     …
#   I0003   READY     …
#
# serialised by scope overlap:
#   I0002 shares lib/project.awk with I0003; they may not run concurrently

Co nepokrývá

Rozsah je to, co úkol deklaruje, ne čeho se dotýká. Dva úkoly, které oba upravují soubor, který žádný nenárokoval, budou v konfliktu a toto nenahlásí nic — stejné omezení má check.

Proč existuje

Falešná serializace stojí čas. Falešná paralelizace stojí konflikt při merge a dva workery, kteří to zjistí po dokončení práce. Konzervativní směr je ten levný.

Detail vykreslený z docs/claims/execution-waves.md.

Od tvrzení k důkazu

  1. 1 · veřejné tvrzení

    Vlny provádění se počítají z grafu a úkoly v jedné vlně, které sahají na stejné cesty, se hlásí jako serializované

    Učiněno na Planning, Plan.

  2. 2 · kanonické tvrzení

    execution-wavesdeklarovaný stav: zaručeno v docs/CLAIMS.yaml

    Definováno v přečtěte si to na tomto webu · docs/PLANNING.md

  3. 3 · implementace

    lib/project.awk

  4. 4 · test a scénáře

    Test: test/cases/42_dag_waves.sh

    Provedeno v Dodávejte úkoly ve vlnách, které graf spočítá, a vezměte další, Veďte plán jako milníky a úkoly, které nástroj umí validovat.

  5. 5 · zaznamenané běhy

    zaznamenané důkazy: nespuštěno jak se zaznamenávají důkazy

Ověřte si to sami

Test běží v jednorázovém dočasném repozitáři a ověřuje chování, ne řetězec ve zdrojovém kódu.

z klonu repozitáře
bash test/run.sh 42_dag_waves

Kde se toto tvrzení používá

Související tvrzení stejná implementace

Okamžiky, na které to odpovídá

Prohledává názvy a popisy všech stránek, které tento web publikuje.