7.1 & 7.2 & 7.3 - System Model & Deadlock Charicterization & Methods for Handeling Deadlocks (p.313, 315, 320)

System Model

• Deadlock = Wanneer een process niet meer uit de waiting state komt omdat de benodigde resources worden vast gehouden door andere wachtende processen.

• Onder resources valt:

  • Logical resources zijn oa bestanden en semaphores.
  • Fysieke resouces zijn oa CPU cycles, printers, geheugen ruimte oa.
  • Elke resource kan meerdere instanties (instances) hebben.
  • Een instantie is niet goed geprogammeerd wanneer er verschil is tussen meerdere instanties.
• Een resource wordt door een process gebruikt in de volgende volgorde:
  1. Request
     • Het process vraagt de resource aan.
     • Wanneer de resouce niet direct beschikbaar is moet het systeem wachten tot de resource vrijgekomen is.
  2. Use
     • Het process gebruikt de resource.
  3. Release
     • Het process geeft de resource terug aan het systeem.
• Een deadlock komt voor wanneer process 1 de printer heeft, en process 2 de DVD drive. Maar process 1 ook nog de DVD nodig heeft.
  • Multithreaded applicaties moeten hier goed op letten, vanwege meerdere threads die om diezelfde resources vragen.

Deadlock Characterization

• Een deadlock komt voor wanneer de volgende vier condities waar zijn:
  1. Mutual Exclusion
     • Een resource moet niet deelbaar zijn. Dat is dat maar een process tegelijk gebruik kan maken van de resource.
     • En dat een ander process pas gebruik kan maken van de resource wanneer het vorige process deze heeft vrijgegeven.
  2. Hold and wait
     • Een process moet al een resource hebben, en wachten op een ander resource die in gebruik is door een ander process.
  3. No preemption
     • Een resource kan alleen vrijwillig worden vrijgegeven door het process dat er gebruik van maakt, wanneer het process is afgerond.
  4. Circular wait
     • Een set van wachtende processen, waarbij een process wacht op de resource(s) van het process na hem in de queue.

Resource Allocation Graph (RAG)

NB. Voor verduidelijking check pagina 316 voor uitleg en meerdere tekeningen.

• Resource Allocation Graph (RAG) = Een tekening waarbij de verdeling van resources onder processen wordt duidelijk gemaakt.
  • Sets met P (processes),R (resources),E (edges)
• Request Edge = Pijl wijzend van process naar resource (P -> R)
  • Het process doet een verzoek om de resource te krijgen, en wacht hierop.
• Assignment Edge = Pijl wijzend van resource naar process. (R -> P)
  • Een resource is toegewezen aan een process.
• Claim Edge = Pijl met stippellijn dat wijst van process naar resource.
  • Een process dat het resource in de toekomst mogelijk nodig heeft.
• Zolang er geen cycle (of cirkel van pijlen) te zien is in de graph, betekent dat geen van de processen in een deadlock zit.
  • Wanneer er wel een cycle in de graph zit, hangt het af van het aantal resources om te bepalen of het ook daadwerlijk een deadlock betreft.

Methods for Handeling Deadlocks

• Drie generieke methodes voor omgaan met deadlocks
  1. Deadlock Prevention = Gebruik maken van een protocol waarbij het systeem niet een deadlocked staat terecht kan komen.
  2. Deadlock Avoidance = Toestaan dat het systeem in een deadlocked staat terecht kan komen, maar deze kan detecteren en oplossen.
  3. Negeren van het probleem, en doen alsof deadlocks niet voorkomen in het systeem
• De 3e oplossing wordt toegepast in UNIX, Windows en de JVM. Het is aan de programmeur om dit op te lossen.

NB. Handeling deadlocks in JVM heb in niet meegenomen in deze samenvatting.