M.J. Terstegge
Deadlocks in AGV-systemen.
Literatuuropdracht/scriptie,
Rapport 98.3.LT.5081, Transporttechnologie, Logistieke Techniek.
Op terreinen waar Automated Guided Vehicles (AGV's) actief zijn, wordt
vaak gebruik gemaakt van claimgebieden. Dit zijn gebieden waarin slechts
één AGV tegelijkertijd aanwezig mag zijn, bedoeld om
botsingen tussen AGV's te voorkomen. Het gebruik van deze claimgebieden
kan echter leiden tot deadlock. Dit is het fenomeen dat optreedt als elke
AGV in een groep AGV's wacht op een claimgebied dat door een andere AGV
uit de groep wordt bezet. Deze keten van wachtende voertuigen kan zonder
ingrijpen van buitenaf niet worden doorbroken, en brengt daardoor veel
tijdverlies met zich mee.
Er zijn in de literatuur veel methoden bekend om deadlock op te lossen of
te voorkomen. Deze methoden kunnen in drie categorieën worden
verdeeld. Deadlockdetectie is een strategie waarbij geen poging wordt
ondernomen om deadlock te voorkomen. In plaats daarvan probeert het
detectiealgoritme deadlocks te detecteren nadat deze zijn opgetreden. Als
er een deadlock wordt gedetecteerd zorgt een deadlockherstelmechanisme
ervoor dat het systeem weer in een deadlockvrije staat wordt
teruggebracht. Deze methode werkt goed in systemen waar deadlocks niet
vaak optreden, en waar de hieraan verbonden kosten acceptabel zijn.
Deadlockdetectiealgoritmen dienen ook als hulpmiddel bij
deadlockvermijding.
Deadlockpreventie en deadlockvermijding hebben beide tot doel het systeem
deadlockvrij te houden, maar bereiken dit op verschillende manieren.
Deadlockpreventie is een categorie van methoden die ervoor zorgen dat
één van de noodzakelijke voorwaarden voor het ontstaan van
deadlock nooit kan gelden. Deadlockvermijding wordt gevormd door een groep
algoritmen die, gebruik makend van de van de beschikbare kennis over de af
te leggen routes, deadlock op een dynamische manier voorkomen. Het alom
bekende bankiersalgoritme is hier een voorbeeld van. Dit is
één van de beste methoden om deadlocks in AGV-systemen te
voorkomen.
Een belangrijk hulpmiddel bij het bestuderen van deadlocks is de
resource-allocatiegrafiek. In deze grafiek wordt schematisch weergegeven
aan welke AGV's de bezette claimgebieden zijn toegewezen, en welke AGV's
wachten op bepaalde claimgebieden. Veel algoritmen voor deadlockdetectie,
-preventie en -vermijding maken gebruik van deze grafiek.
Rapporten studenten Logistieke Techniek
Gewijzigd: 1998.10.16;
logistics@3mE.tudelft.nl
, TU Delft
/ 3mE
/ TT
/ LT.