Deadlock prevention voor dummies – met annotaties

 
31 oktober 2007

Vorige week werd mijn aandacht voor het eerst serieus getrokken door het probleem van deadlock. Twee threads die allebei een lock op dezelfde twee objecten willen hebben, en dus op elkaar wachten totdat de ander zijn lock vrijgeeft. Iets dat je niet wilt omdat je programma in elk geval deels tot stilstand komt, en waar je dus best wat hulp mee kan gebruiken.

Voor zover ik als junior weet, is het voorkomen en het detecteren van deadlock vooralsnog een onuitgemaakte zaak: er bestaat geen algoritme dat naar een willekeurig stuk code kijkt en met zekerheid kan zeggen of er wel of geen deadlocks in kunnen optreden. Maar er zijn wel vuistregels die deadlock uitsluiten voor deelgebieden van dit probleem: dus voor code die op een bepaalde manier gestructureerd is. Eén van die regels is: zorg dat je te allen tijde ten hoogste één lock nodig hebt. Volgens mij moet het niet al te moeilijk zijn om zo’n policy met compiler-ondersteuning te faciliteren.

In de loop van de informatica-geschiedenis is de computer de programmeur steeds meer gaan helpen bij het programmeren; bijvoorbeeld via garbage collection om geheugenbeheer uit handen te nemen, of -in Java- met checked exceptions om ervoor te zorgen dat de computer de programmeur waarschuwt als er dingen mis kunnen gaan. De compiler kan er zo voor zorgen dat de programmeur zich beter kan concentreren op wàt er moet gebeuren, in plaats van hòe dat moet gebeuren.

Conor McBride schrijft in de eerste twee alinea’s van zijn proefschrift:

Computer programs are not expected to make sense. In fact, they are seldom expected to work, which is as much as to say that computer programmers are not expected to make sense either. This is understandable – programming is primarily a form of giving orders.

Nonetheless, there are grounds for optimism. This is because programmers do not really want genuinely stupid orders to be obeyed, and we understand that the more sense we are able to make, the shorter our orders need be. The benefit comes by taking the sense within the programmer’s mind and manifesting it explicitly in the program.

Een van de senses within this programmer’s mind is nu deadlock-vrijheid. Ik wil nu graag het concept “deadlock-vrij zijn” in de code uitdrukken. Hoe? Met annotaties. Deadlock-vrijheid is metadata van een programma, en annotaties zijn uitgevonden om metadata uit te drukken.

Een van de problemen met locking is dat je aan de buitenkant van een methode-aanroep niet makkelijk kan zien of er in
de implementatie van die methode locking plaatsvindt, en hoeveel locks er zijn. Wat ik dus wil is een aantal annotaties om (gebrek aan) locking mee te beschrijven: bijvoorbeeld

@Nonlocking // of [Nonlocking] in C#
public void Mymethod() { ... }

om aan te geven dat er in die methode geen locking plaats vindt. Als er wel locking plaatsvindt kunnen we een annotatie @SinglyLocking maken. We kunnen in een annotatie niet aangeven wèlk object gelockt wordt, maar we kunnen wel alvast een type meegeven:

@SinglyLocking(MyClass)         // of [SinglyLocking(typeof(MyClass))]
public void MyMethod() {
  MyClass myObj = ...;
  synchronize(myObj) {          // of lock(myObj) in C#
    ...
  }
}

Op soortgelijke manier kan je met meerdere synchronize-blokken denken aan

@SeriallyLocking(MyFirstClass, MySecondClass)
public void MyMethod() {
  MyFirstClass myFirstObj = ...;
  MySecondClass mySecondObj = ...;
  synchronize(myFirstObj) {
    ...
  }
  synchronize(mySecondObj) {
    ...
  }
}

terwijl geneste blokken een algemene Locking-annotatie krijgen, met de types in volgorde:

@Locking (MyFirstClass, MySecondClass)
public void MyMethod() {
  MyFirstClass myFirstObj = ...;
  MySecondClass mySecondObj = ...;
  synchronize(myFirstObj) {
    ...
    synchronize(mySecondObj) {
      ...
    }
    ...
  }
}

Maar waarom tiep ik hier nu een artikel over, in plaats van het te implementeren? Omdat ik compiler-ondersteuning wil. Ik kan op zich deze locking-attributen wel definiëren, maar zolang de compiler daar niet zo veel mee doet, is het net als documentatie: als de code verandert, zijn ze mogelijk verouderd.

Ik wil dus van de compiler op zijn minst een waarschuwing (maar liever nog een error) horen als ik mijn klasse @Nonlocking maak, terwijl er een methode-aanroep instaat waar wel locking in gebeurt. In mijn eigen code weet ik wel of ik ergens synchronize(obj) {…} heb staan, maar ik kan niet zomaar in de implementaties kijken van de methodes die ik aanroep. Maar de compiler kan de metadata daarvan wel makkelijk opzoeken, en mij dus waarschuwen als ik denk dat mijn methode (met die aanroep erin) @Nonlocking is. Daarnaast kan de compiler waarschuwen als er meer dan een draad is die twee locks tegelijk heeft, op dezelfde (of via inheritance gerelateerde) types.

Het lijkt me een interessant onderwerp van studie om te kijken hoe ruim je de policy kan maken die de compiler kan implementeren: als je alleen @Nonlocking threads hebt, is er geen deadlock mogelijk. Ook als alle threads maar een enkele lock tegelijkertijd nodig hebben, of meerdere tegelijkertijd, maar op incompatibele types. Een enkele thread die er meer dan een tegelijkertijd nodig heeft zou (geloof ik) ook goed moeten gaan. Hoe ver kan je gaan?

Maar eigenlijk is er dus maar een ding dat ik echt mis: de mogelijkheid om met annotaties compiler-waarschuwingen te genereren.

Er zitten natuurlijk nog wat haken en ogen aan dit voorstel. Ten eerste krijg je met deze methode best een aantal false positives – waarschuwingen voor deadlock die niet kloppen – maar in elk geval kan je wel zorgen dat er geen false negatives zijn (geen waarschuwing als er wel deadlock kan optreden). Daarnaast is er met name in C# het probleem dat je daar, via Monitor.Enter() en Monitor.Exit(), in de ene methode een Lock kan verkrijgen en die in een andere methode weer vrijgeven. Ongetwijfeld zijn er nog meer dingen waar ik nog niet aan heb gedacht, maar het lijkt me alvast een begin.

–update 8 nov.: in afwachting op de mogelijkheid tot reageren op deze blog maakte mijn collega Jaap me alvast attent op de situatie waarin je locking uitvoert op een variabele die getypeerd is dmv. een interface. Je zou dan dus ook in de interface moeten bepalen wat het locking-gedrag van de te implementeren methode is.


Werken met ?
Kijk dan bij onze mogelijkheden voor starters en/of ervaren IT'ers.


Categorieën: Development

Tags: , ,


Reacties (2)

  • Jasper Stein schreef:

    …een zeer late reactie op mezelf: ik zei hierboven dat als er maar een enkel object per thread gelockt werd, er geen deadlock mogelijk is. MAAR… dat kan dus wel! In Effective Java (2nd ed.), item 67 staat een mooi voorbeeld. Thread A start een synchronized block, start binnen dat block een nieuwe thread B, en wacht synchroon totdat die klaar is. Als B nu ook synchroniseert op hetzelfde object heb je je probleem…

    Geplaatst op 24 oktober 2011 om 13:51 Permalink

  • Erik Visser schreef:

    Leuk geschreven stuk! Van mij mag je dat junior wel weglaten voor je functie hoor ;-) Qua inzicht ben je veel verder dan menig “senior” ontwikkelaar.

    Geplaatst op 25 december 2007 om 13:24 Permalink