Werkplaats / De werkplaats
In jouw eigen tempo
← Agents en MCP
MODULE 01 · LES 03

Hervat een plan zonder geslaagd werk te herhalen

Bereken afhankelijkheden, kies herhaalbare taken en vergelijk totale werklast met het kritieke pad.

75 min3 checkpoints
DIT GA JE ONTDEKKEN
  • Je weigert cyclische of onvolledige plannen en kiest een deterministische topologische volgorde.
  • Je onderscheidt wachten, uitvoeren, slagen en falen, en begrenst retries.
Voorkennis: Bind toestemming aan de exacte handeling

Een assistent heeft gegevens gelezen en een berekening voltooid, maar de laatste stap faalt. Alles opnieuw uitvoeren verspilt werk en kan bij schrijfacties een tweede effect veroorzaken. Een hervatbaar plan bewaart daarom afhankelijkheden én uitvoeringstoestand.

Zie een plan als een recept met voorbereidingen: het antwoord kan pas nadat de berekening en het opzoekwerk klaar zijn. De pijlen zeggen wat eerst moet gebeuren. Ze bewijzen niet dat de taken nuttig of toegestaan zijn.

1. Maak de afhankelijkheden zichtbaar

Een gerichte acyclische graaf (DAG) heeft pijlen zonder kringloop. Ons plan bestaat uit lezen a, rekenen b, opzoeken c en antwoorden d. De getallen zijn aangenomen duren in werkeenheden:

       +--> b (4) --+
a (2) -+            +--> d (1)
       +--> c (3) --+

Taken b en c wachten op a; d wacht op b én c. Alleen a heeft geen voorgangers. Bouw ditzelfde plan in code; de invoerlijst staat expres niet in uitvoervolgorde.

def task(key, needs, duration):
    return {
        'id': key, 'needs': needs,
        'duration': duration,
        'retry_safe': True
    }

plan = [
    task('d', ['b', 'c'], 1),
    task('c', ['a'], 3),
    task('b', ['a'], 4),
    task('a', [], 2)
]
print(topological_plan(plan))
# ['a', 'b', 'c', 'd']

Schrijf topological_plan met de begrensde taakvorm uit de opdracht. Kies telkens één alfabetisch kleinste beschikbare ID en voeg die aan done toe. De volgende ronde beoordeelt opnieuw welke taken beschikbaar zijn.

RondeBeschikbaarGekozen
1aa
2b, cb
3cc
4dd

Alle beschikbare taken als één alfabetisch blok toevoegen lijkt logisch, maar voldoet niet aan ons contract. Na a kan een nieuwe kleinere kandidaat klaarstaan vóór de eerder beschikbare z:

small = [
    task('z', [], 1),
    task('b', ['a'], 1),
    task('a', [], 1)
]
print(topological_plan(small))
# ['a', 'b', 'z']

Andere topologische volgordes kunnen wiskundig geldig zijn. Onze keuze maakt precies deze oefening reproduceerbaar, ook bij een anders geordende invoerlijst.

01
CHECKPOINTLaat afhankelijkheden de volgorde bepalen

2. Bewaar status én pogingenteller

Een gekozen volgorde is nog geen uitvoerlog. Bewaar pending, running, done of failed plus het aantal begonnen pogingen. Pending betekent nul; alle andere statussen betekenen minstens één poging en vereisen voltooide voorgangers.

Stel dat a en c klaar zijn, b eenmaal faalde en d nog niet gestart is. b mag opnieuw als retry_safe waar is en het pogingenbudget ruimte heeft. d blijft wachten, ook wanneer zijn eigen teller nog nul is.

states = {
    'a': 'done', 'b': 'failed',
    'c': 'done', 'd': 'pending'}
attempts = {
    'a': 1, 'b': 1, 'c': 1, 'd': 0}
r = schedulable_plan(
    plan, states, attempts)
print(r['ready'], r['blocked'])
attempts['b'] = 2
r = schedulable_plan(
    plan, states, attempts, 3)
print(r['ready'])
r = schedulable_plan(
    plan, states, attempts, 2)
print(r['exhausted'], r['blocked'])
# ['b'] ['d']
# ['b']
# ['b'] ['d']

Schrijf schedulable_plan met de vijf alfabetische categorieën uit de opdracht. Running en done behouden hun categorie; een mislukte taak zonder veilige herhaling of resterende pogingen wordt exhausted. De uitvoerder verhoogt zelf de teller bij starten en bewaart het latere resultaat.

Een exception kan optreden ná een effect. Failed bewijst dus niet dat niets veranderde; retry_safe moet uit vertrouwde kennis van de handeling komen. Geslaagde taken terugzetten naar pending vernietigt juist de informatie die hervatten mogelijk maakt.

De visualisatie gebruikt dezelfde afhankelijkheden en duren, met a als read, b als calculate, c als lookup en d als answer. Kies verschillende momentopnamen en volg welke taken nog mogen starten.

EIGEN DAG · GEEN ECHTE PARALLELLE WORKERSEen fout zet niet het hele plan terug naar nul

read voedt twee takken: calculate en lookup. answer wacht op beide. Bekijk welke taken in deze momentopname mogen starten.

readVereist: nietsdone → done
calculateVereist: readfailed → ready
lookupVereist: readpending → ready
answerVereist: calculate + lookuppending → blocked
Mag nu startencalculate, lookupMislukte calculate: 1 van maximaal 2 pogingen.
Seriële werklast10
Ideaal kritisch pad7

Duren: read 2, calculate 4, lookup 3, answer 1. Kosten gelden voor één volledige foutloze uitvoering; retries komen erbij. De ideale parallelle tijd veronderstelt onbeperkte workers, geen overhead en onafhankelijke effecten.

02
CHECKPOINTEen mislukte taak is niet hetzelfde als een ongestarte taak

3. Reken totale werklast en kritisch pad apart uit

Met één worker kost het plan 2+4+3+1=10 eenheden. Bij onbeperkt parallel werk eindigt a op 2; b eindigt op 2+4=6 en c op 2+3=5. d wacht tot beide voorgangers klaar zijn en eindigt op max(6,5)+1=7.

Noem de duur van taak v d_v en haar eindtijd F_v. P(v) bevat de voorgangers; het maximum van een lege verzameling eindtijden is hier nul:

Fv=dv+maxu∈P(v)Fu

De som van alle duren is T_s; de ideale parallelle tijd T_p is de grootste eindtijd. Het kritieke pad a→b→d bepaalt hier die ondergrens:

Ts=∑vdvTp=maxvFv
cost = plan_cost(plan)
for key in ['a', 'b', 'c', 'd']:
    print(key, cost['finish'][key])
print(cost['serial'],
      cost['parallel'])
# a 2
# b 6
# c 5
# d 7
# 10 7

Schrijf plan_cost in topologische volgorde. Dit rooster neemt vaste duren, onbeperkte workers en geen communicatie of retries aan. Het is geen gemeten versnelling; conflicterende effecten en beperkte middelen kunnen de echte tijd verhogen.

Een kringloop heeft geen geldige volledige volgorde. Ook ontbrekende of dubbele IDs en ongeldige taakvelden horen vóór uitvoering te falen:

cycle = [
    task('x', ['y'], 1),
    task('y', ['x'], 1)
]
try:
    topological_plan(cycle)
except ValueError:
    print('cyclus')
# cyclus
03
CHECKPOINTHet kritieke pad begrenst ideale parallelle tijd

Wat neem je mee?

  • Afhankelijkheden bepalen beschikbaarheid; ons contract kiest daarbinnen telkens één kleinste ID.
  • Toestand en pogingentellers voorkomen blind herhalen van eerder werk.
  • Parallelle tijd en totale werklast zijn verschillende grootheden.

Hierna bewaren we context met bronversies en vervaltijden, zodat hervatten ook op actuele informatie berust.

Verder lezen & bronnen

Inhoud gecontroleerd op 2026-10-29.
DE VOLGENDE STAPGeef geheugen een taak, bron en vervaldatum
JOUW EXPERIMENT

Probeer het zelf

Python
main.py

Python start zodra jij code uitvoert.

UITVOER

Je uitvoer verschijnt hier.
Alles rekent in je eigen browser.

Jouw checkpoints0 / 3
01
Laat afhankelijkheden de volgorde bepalen

Schrijf topological_plan(plan). 1..32 dictionaries met exact id,needs,duration,retry_safe. id: uniek [a-z][a-z0-9-]{0,31}; needs: lijst tot 32 unieke string-IDs die in plan bestaan; duration: gewone int 1..1000; retry_safe: bool. Geef de alfabetisch gekozen topologische volgorde. Weiger zelflussen, cycli, ontbrekende en dubbele IDs met ValueError. Wijzig plan niet.

Een hint

Gebruik done als verzameling. Zoek iedere ronde de beschikbare IDs, sorteer en neem de eerste. Geen kandidaat terwijl niet alles klaar is betekent cyclus.

02
Een mislukte taak is niet hetzelfde als een ongestarte taak

Schrijf schedulable_plan(plan,states,attempts,max_attempts=2). Gebruik topological_plan. states en attempts bevatten exact alle taak-IDs; max_attempts is gewone int 1..5, attempts gewone int 0..max_attempts. Valideer bovenstaande status/tellerrelatie en eis voor iedere niet-pending taak dat haar voorgangers done zijn. Geef alfabetisch gesorteerde lijsten ready,blocked,exhausted,running,done. Running/done behouden categorie; failed zonder veilig retrybeleid of zonder budget wordt exhausted; overige taken met onvoltooide voorgangers blocked; rest ready.

Een hint

Deze functie kiest werk maar voert niets uit. De uitvoerder moet bij starten running zetten en de teller verhogen, en later done/failed vastleggen. Een hervatting zet geslaagde taken niet terug naar pending.

03
Het kritieke pad begrenst ideale parallelle tijd

Schrijf plan_cost(plan). Gebruik dezelfde validatie en volgorde. Geef serial (som), parallel (maximum eindtijd) en finish (dictionary per ID met ideale eindtijd). Een taak zonder voorgangers start op 0. Alle duren zijn de vaste aannames uit het plan.

Een hint

Bereken in topologische volgorde. Een lege lijst voorgangers heeft maximum 0. Parallel is hier alleen de ideale makespan onder de beschreven aannames.

Vastgelopen? Bekijk de voorbeeldoplossing
import copy
import json
import math
import re
import hashlib

def topological_plan(plan):
    if not isinstance(plan, list) or not 1 <= len(plan) <= 32:
        raise ValueError('1..32 taken vereist')
    nodes = {}
    for row in plan:
        if not isinstance(row, dict) or set(row) != {'id', 'needs', 'duration', 'retry_safe'}:
            raise ValueError('Exact taakcontract vereist')
        key = row['id']
        if not isinstance(key, str) or not re.fullmatch(r'[a-z][a-z0-9-]{0,31}', key) or key in nodes:
            raise ValueError('Unieke taak-ID vereist')
        if not isinstance(row['needs'], list) or len(row['needs']) > 32 or any(not isinstance(x, str) for x in row['needs']) or len(set(row['needs'])) != len(row['needs']):
            raise ValueError('Unieke voorgangers vereist')
        if type(row['duration']) is not int or not 1 <= row['duration'] <= 1000 or type(row['retry_safe']) is not bool:
            raise ValueError('Duur 1..1000 en herhaalbeleid vereist')
        nodes[key] = row
    if any(dep not in nodes for row in plan for dep in row['needs']):
        raise ValueError('Ontbrekende voorganger')
    order, done = [], set()
    while len(done) < len(nodes):
        ready = sorted(key for key, row in nodes.items() if key not in done and set(row['needs']) <= done)
        if not ready:
            raise ValueError('Cyclus in het plan')
        chosen = ready[0]
        order.append(chosen); done.add(chosen)
    return order

def schedulable_plan(plan, states, attempts, max_attempts=2):
    order = topological_plan(plan)
    if type(max_attempts) is not int or not 1 <= max_attempts <= 5 or not isinstance(states, dict) or not isinstance(attempts, dict) or set(states) != set(order) or set(attempts) != set(order):
        raise ValueError('Volledige toestand en pogingentellers vereist')
    nodes = {row['id']: row for row in plan}
    for key in order:
        if states[key] not in ['pending', 'running', 'done', 'failed'] or type(attempts[key]) is not int or not 0 <= attempts[key] <= max_attempts:
            raise ValueError('Ongeldige taaktoestand')
        if (states[key] == 'pending') != (attempts[key] == 0):
            raise ValueError('Pending heeft nul pogingen, overige minstens een')
        if states[key] != 'pending' and any(states[dep] != 'done' for dep in nodes[key]['needs']):
            raise ValueError('Gestarte taak zonder voltooide voorgangers')
    result = {key: [] for key in ['ready', 'blocked', 'exhausted', 'running', 'done']}
    for key in sorted(order):
        status, node = states[key], nodes[key]
        if status in ['running', 'done']:
            category = status
        elif status == 'failed' and (not node['retry_safe'] or attempts[key] >= max_attempts):
            category = 'exhausted'
        elif any(states[dep] != 'done' for dep in node['needs']):
            category = 'blocked'
        else:
            category = 'ready'
        result[category].append(key)
    return result

def plan_cost(plan):
    order = topological_plan(plan)
    nodes, finish = {row['id']: row for row in plan}, {}
    for key in order:
        row = nodes[key]
        finish[key] = row['duration'] + max([finish[dep] for dep in row['needs']], default=0)
    return {'serial': sum(row['duration'] for row in plan), 'parallel': max(finish.values()), 'finish': finish}

Voer de code uit en verklaar voor jezelf waarom elke stap werkt.