Follow my new blog

Montag, 30. Januar 2012

TDD im Flow – Teil 3

Was bisher geschah:

Test #4: Blockierte Entnahme

Nun geht es an den Kern meines Abstrakten Datentyps: die Sequentialisierung.

image[42]_thumb

Ich muss die Entnahme aus den Queues nach Round Robbin einschränken. Es darf nur entnommen werden, wenn eine Queue nicht gerade blockiert wird. Die Blockierung beginnt, wenn ein Worker aus einer unblockierten Queue entnimmt – und wird automatisch aufgehoben, wenn er wieder nach Arbeit fragt.

Anders als im Datenmodell entworfen, implementiere ich die Sperren für Queues in einem Dictionary. Die Einträge darin sind die Flags des Datenmodells. Ich finde es jedoch besser, sie von der Liste der Queues zu trennen. Die Blockade der Entnahme ist ein anderer Aspekt als die Entnahme nach Round Robbin. Beide durch Verwaltung in unterschiedlichen Datenstrukturen zu trennen, scheint mir konsequente Anwendung des SRP.

Falls sich etwas an der Blockadestrategie ändert, muss ich nicht die Datenstruktur für die Entnahme anfassen. Es ist auch nur TryDequeue() betroffen.

internal class NotifyingMultiQueue<T>
{
    …
    readonly Dictionary<string, string> _readLocks =
        new Dictionary<string,string>(); 

    …
    public bool TryDequeue(string workerId, out T message)
    {
        message = default(T);

        var namedQueue = _queues[0];
        _queues.RemoveAt(0);
        _queues.Add(namedQueue);

        if (_readLocks.ContainsKey(namedQueue.Key) &&
            _readLocks[namedQueue.Key] != workerId)
            return false;

        message = namedQueue.Value.Dequeue();
        _readLocks[namedQueue.Key] = workerId;

        return true;
    }
    …

Diese Implementation erreicht das Ziel natürlich noch nicht ganz. Sie dient nur der Erfüllung eines Tests, ohne die vorherigen zu brechen.

Bevor ich aber den nächsten Test beschreibe: Haben Sie meine TDD Sünde entdeckt?

Ich habe mehr Code geschrieben, als für den Test nötig ist. Die Prüfung, ob der “arbeitsuchende” Worker derjenige ist, der eine Queue bisher blockiert hat, kommt nicht zum Tragen. Dafür müsste ich einen weiteren Test schreiben. Aber das ist nicht nötig, weil der nächste Test dafür sorgen wird, dass diese Prüfung gar nicht mehr nötig ist.

Warum habe ich dann aber _readLocks[namedQueue.Key] != workerId geschrieben? Weil es mir in dem Moment cool vorkam, an diese Feinheit gedacht zu haben. Da hab ich mich von der Idee davontragen lassen… Erst später beim nächsten Test ist mir die Überflüssigkeit der Bedingung aufgefallen.

Ich hatte sie aber nach erfolgreichem Test eingecheckt. Deshalb zeige ich sie Ihnen hier auch. So kann es halt kommen, auch wenn man sich bemüht. Mit Pair Programming wäre das vielleicht nicht passiert. Am Ende ists aber auch kein Beinbruch. Mir ist es ja aufgefallen. Wichtig ist, daraus zu lernen. Nobody is perfect – but everybody should strive for improvement. Oder so ähnlich ;-)

Test #5: Blockierte Queue wieder freigeben

Bisher wurde eine Queue bei Entnahme nur gesperrt. Jetzt muss sie wieder entsperrt werden. Das geschieht, wenn der Worker, der sie gesperrt hat, wieder frei ist. Der ADT bemerkt, wann ein Worker seine Arbeit an einer Nachricht beendet hat daran, dass der Worker wieder um eine Nachricht bittet:

image[47]_thumb

Beim ersten Aufruf von TryDequeue() sperrt w1 die Queue q1. Bei zweiten Aufruf sperrt er q2 – und gibt damit implizit q1 wieder frei, so dass w2 daraus entnehmen kann.

In der Implementation erreiche ich das, indem ich einfach bei Aufruf immer eine eventuell durch den anfragenden Worker gesetzte Sperre lösche:

internal class NotifyingMultiQueue<T>
{
    …

    public bool TryDequeue(string workerId, out T message)
    {
        message = default(T);

        if (_readLocks.ContainsValue(workerId))
            _readLocks.Remove(
                 _readLocks.Where(kvp => kvp.Value == workerId)
                           .Select(kvp => kvp.Key)
                           .First());

        var namedQueue = _queues[0];
        _queues.RemoveAt(0);
        _queues.Add(namedQueue);

        if (_readLocks.ContainsKey(namedQueue.Key))
            return false;

        message = namedQueue.Value.Dequeue();
        _readLocks[namedQueue.Key] = workerId;

        return true;
    }
    …

Damit entfällt dann auch die Prüfung, ob eine Sperre durch den aktuellen Worker gesetzt worden ist. Der Fall kann nicht mehr eintreten.

Leider ist das Löschen eines Dictionary-Eintrags über den Wert statt dem Key nicht so leicht. Ich muss erst den Key (Queue-Name) aus dem Wert (Worker-ID) ermitteln. Die Linq-Query liest sich etwas umständlich.

Alternativ hätte ich ein zweites Dictionary aufsetzen können, in dem die Worker-ID als Key steht und über den Queue-Namen auf _readLocks zeigt. Aber das würde zusätzlichen Pflegeaufwand bedeuten. So scheint mir der hier eingeschlagene Weg KISS-konform.

Test #6: Blockierte Queue überspringen

Es ist merkwürdig, aber bisher bin ich ohne eine Schleife bei der Entnahme ausgekommen. Wäre ich nicht nach TDD vorgegangen, hätte ich die wahrscheinlich schon gleich am Anfang eingebaut – und die Lösung damit komplexer gemacht.

Mit TDD habe ich dagegen einige Schwierigkeiten schon aus dem Weg geräumt. Anweisungssequenzen sind leichter zu verstehen und zu testen als Schleifen.

Jetzt hilft es aber nichts mehr. Eine Schleife muss sein, wenn blockierte Queues übersprungen werden sollen. Es müssen bei TryDequeue()-Aufruf potenziell ja mehrere Queues geprüft werden.

image_thumb[23]_thumb

TDD besteht aus 3 Phasen: roter Test, grüner Test und Refactoring. Bisher habe ich die letzte Phase übersprungen. Es gab nicht viel zu refaktorisieren. Jetzt wird es mir aber zuviel, was da alles in TryDequeue() passiert. Und auch KeyValuePair ist mir zu wenig aussagekräftig; mehr Domänensprache darf sein.

Zur Befriedigung des neuen Tests füge ich deshalb nicht nur Code hinzu, sondern ziehe auch Code raus in eigene Methoden. Das Listing unterscheidet Änderungen im Rahmen des Refactoring und Änderungen zur Erfüllung der neuen Anforderungen.

internal class NotifyingMultiQueue<T>
{
 
   readonly List<NamedQueue> _queues =
        new List<NamedQueue>();
    readonly Dictionary<string, string> _readLocks =
        new Dictionary<string,string>();

    class NamedQueue
    {
        public string Name;
        public Queue<T> Queue;
    }


    public void Enqueue(T message, string queueName)
    {
        var queue = _queues.Where(nq => nq.Name == queueName)
                           .Select(nq => nq.Queue)
                           .FirstOrDefault();
        if (queue == null)
        {
            queue = new Queue<T>();
            _queues.Add(new NamedQueue{Name=queueName, Queue=queue});
        }
        queue.Enqueue(message);
    }


    public bool TryDequeue(string workerId, out T message)
    {
        message = default(T);

        Free_queue_locked_for_worker(workerId);

        NamedQueue namedQueue = null;
        for (var i = 0; i < _queues.Count(); i++)
        {
            namedQueue = Get_next_queue();
            if (Queue_not_locked(namedQueue)) break;
            namedQueue = null;
        }
        if (namedQueue == null) return false;

        message = namedQueue.Queue.Dequeue();
        Lock_queue_for_worker(workerId, namedQueue);
        return true;
    }
    …


Hier zeigt es sich jetzt, dass TDD letztlich kein Verfahren ist, das zu Unit Tests führt. TryDequeue() ruft jetzt andere Methoden auf, d.h. es integriert. Noch sind diese Methoden einfach und wurden 1:1 aus Code, der eben noch in TryDequeue() stand erzeugt. Bei der Weiterentwicklung des ADT kann es aber jederzeit passieren, dass Änderungen an diesen Methoden nötig werden. Und dann stellt sich die Frage, wie diese Änderungen getestet werden.

Klar, ich kann dafür dann gezielte Tests schreiben. Doch beim Refactoring mit ReSharper sind die “Hilfsmethoden” automatisch als private deklariert worden. Es kostet dann schon einige Überwindung, die auf internal zu setzen und als Units für sich zu testen. Deshalb wird in den meisten Fällen weiter durch das Interface getestet, d.h. mit Integrationstests gearbeitet. Die testen dann natürlich auch immer noch alles andere mit. Vorteil: Black Box Tests sind unabhängig von interner Struktur. Nachteil: Black Box Tests können aufwändig werden, wenn für Kleinigkeiten das Drumherum mit getestet werden muss. Das wird besonders auffallend, sobald Attrappen ins Spiel kommen. Dazu kommt, dass bei Integrationstests eine Fehlerquelle nicht so leicht lokalisiert werden kann.

Fazit

Mit diesem Artikel wollte ich Ihnen zeigen, dass ein expliziter Entwurf von Software mittels Flow-Design nicht bedeutet, alles über Bord zu werfen, was Ihnen lieb und teuer geworden ist: Ich finde, der Abstrakte Datentyp NotifyingMultiQueue<T> ist ein solider Vertreter der Objektorientierung. Und seine Entwicklung ist eine solide Anwendung von TDD.

Darüber hinaus wollte ich Ihnen an einem realen Beispiel zeigen, wie TDD funktionieren kann: mit expliziter Testplanung, in kleinen Schritten. Nicht perfekt, aber good enough.

Schließlich haben Sie gesehen, dass selbst ich als Verfechter von Nachdenken vor dem Codieren nicht dogmatisch bin ;-) Wenn die Codierungsrealität es nahelegt, dann kann ich von meinem Entwurf auch abweichen. Erkenntnisse sind jederzeit willkommen.

Wenn Sie mögen, verfolgen Sie meine TDD-Fortschritte auch im Code. Hier die relevanten Changesets (insb. 43..50) im Mercurial Repository npantarhei.codeplex.com.

image_thumb[24]_thumb

Und nun kommen Sie mit TDD und FD.

Spendieren Sie mir doch einen Kaffee, wenn Ihnen dieser Artikel gefallen hat...

Kommentare:

Frank hat gesagt…

Komisch, dass bisher überhaupt noch keine Kommentare gekommen sind. Ich finde, hier gibt es besonders viel zu sagen. Doch der Reihe nach.

Der Artikel heißt "TDD im Flow." Anwenden tust du TDD aber auf einen Baustein, von dem du selbst sagst "dazu fällt mir [...] gerade kein sinniger Flow ein" und "der Abstrakte Datentyp NotifyingMultiQueue ist ein solider Vertreter der Objektorientierung". Du hast also TDD auf eine rein objektorientierte Komponente angewendet und gerade nicht auf Flow Design. "Pragmatisches TTD" (einer Sequentialize-Komponente) o.ä. wäre wohl ein passender Titel gewesen. Das aber nur am Rande, denn mich interessiert die Komponente selbst viel mehr als Flow Design und/oder TTD.

"Meine Lösungsidee für die Datenstruktur sieht erst einmal so aus"

Grundsätzlich habe ich nichts dagegen, sich zuerst eine Datenstruktur auszudenken. Die ist in vielen Fällen sogar wichtiger als der Algorithmus. Nur hättest du spätestens bei der Erstellung der Test stutzig werden sollen. Warum bekommt man bei Test 3, also dem mehrfachen TryDequeue mit genau einem Worker, die Elemente nicht in der Reihenfolge, in der sie eingequeued worden? Das ist doch, was man als unbedarfter Benutzer ohne Kenntnis der Implementierung erwarten würde. Du hast die Tests so geschrieben, dass sie zu der angestrebten Implementierung (zumindest zur Datenstruktur) passen. Insofern finde ich dein Beispiel ziemlich in die Hose gegangen. Das ist gerade nicht TTD. Pragmatismus hin oder her. "Pragmatische Tests" o.ä. wäre wohl ein passender Titel gewesen. :-)

Was man braucht, sind eine gemeinsame Queues und je eine pro Worker, also nicht (direkt) pro Port. Alle Aufträge kommen erstmal in die gemeinsame Queue. Kommt jetzt der erste Worker w1, holt er sich den ersten anstehenden Auftrag aus der gemeinsamen Queue. Sagen wir, der Auftrag hat den Port p1. Das vermerken wir bei dem Worker w1. Der zweite Worker schaut nun wieder in die gemeinsame Queue. Hat der Auftrag einen anderen Port, also keinen, der schon von einem anderer Worker belegt ist, schnappt er sich den Auftrag. Hat der Auftrag einen in Benutzung befindlichen Port, packt er den Auftrag in die Queue des betreffenden Workers. Das gleiche macht er für alle Aufträge in der gemeinsamen Queue, solange bis er einen Auftrag gefunden hat, dessen Port nicht in Benutzung ist, oder die gemeinsame Queue leer ist. Ein Worker, der nach einem beendeten Auftrag wiederkommt, schaut zuerst in seine eigene Queue. Wenn dort ein Auftrag enthalten ist, nimmt er sich diesen. Wenn nicht, setzt er den zuletzt benutzen Port auf unbesetzt. Dann geht er auf die gemeinsame Queue, in der eben beschriebenen Weise. Das ist natürlich nur einen grobe Beschreibung. Ich hoffe, dass das Prinzip trotzdem klar geworden ist. Um schnell die passende Queue zum Worker bzw. zum Port zu finden, kann man zwei Dictionaries verwenden.

Im Ergebnis warten nur die Aufträge, die warten müssen. Und auch die nur so lange wie unbedingt nötig. Kein Auftrag wird von anderen unnötig überholt. Alles wird - wenn möglich - in der Reihenfolge des Einqueuens abgearbeitet.

Frank hat gesagt…

...

Aber selbst wenn du am Round Robin festhalten willst, ist deine Implementierung nicht korrekt, zumindest, wenn man davon ausgeht, dass Enqueue zu beliebigen Zeitpunkten von beliebigen Threads aufgerufen werden kann. Zum Beispiel könnten zwei Threads Enqueue für die gleiche noch nicht existierende Queue gleichzeitig aufrufen. Dann kann es passieren, dass beide Thread zu dem Ergebnis kommen, dass die Queue noch nicht existiert und beide in den queue == null Block hineinlaufen und beide die Queue (also doppelt) hinzufügen. Aber selbst für unterschiedliche Queuenamen kann es passieren, dass zwei Threads gleichzeitig das nicht threadsichere Queue.Add aufrufen. Peng! Auch TryDeqeue glänzt durch die Abwesenheit von Synchronisierung. Zum Beispiel kann es passieren, dass sich der Wert von _queues.Count() während der Ausführung ändert und dadurch evtl. nicht alle Queues geprüft werden, z.B. wenn gegen Ende der Schleife die neue Queue an einer Stelle kurz vor der von Get_next_queue() gelieferten Queue eingefügt wurde. Es kann also an verschiedenen Stellen knallen. Und ich gehe davon aus, dass es noch weitere Situationen gibt, die zu Fehlern führen.

Daran sieht man sehr schön, dass man Korrektheit von nebenläufigen Programmen nur sehr schwer durch Testen sicherstellen kann. Insofern ist die Komponente ein schlechtes Beispiel für Tests im allgemeinen und für TDD im speziellen. "Vom Scheitern des pragmatischen Testens" o.ä. wäre wohl ein passender Titel gewesen. :-)

Nochmal zur der leeren Queue: Statt TryDequeue + Wait (int milliseconds) würde ich ein Dequeue vorziehen, das einfach solange wartet, bis ein ausführbarer Auftrag ansteht. Warum soll der Worker ein TryDequeue probieren, sich dann eine zufällige Zeit schlafen legen, um es auf gut Glück nochmal zu probieren? Da ist es doch besser, wenn Dequeue automatisch exakt in dem Moment zurückkehrt, wenn ein ausführbarer Auftrag ansteht.

Ralf Westphal - One Man Think Tank hat gesagt…

@Frank: Tut mir leid, wenn ich anscheinend meine Intention nicht klar gemacht habe. Mir ging es nicht darum "Pragmatisches TDD" zu zeigen, sondern TDD innerhalb (d.h. "im") eines ansonsten durch FD entstandenen Entwurfs.

Auch ging es mir nicht darum, einen API oder eine Implementation zu entwickeln, die alle Leser glücklich macht und elegant ist. Nein, mir ging es im Grunde gar nicht um den resultierenden Code, sondern um das Vorgehen.

Wenn du also meine Datenstruktur kritisierst, dann kritisierst du am Punkt vorbei. Natürlich kann man das Problem anders lösen. Mach das gern. Ich habe es so gelöst - aber auf eine Weise, auf einem Weg, den ich offengelegt habe.

Sollte der Weg dir nicht gefallen, wenn du also meinst, der sei so gar nicht TDDlike, dann wäre das angebrachte Kritik.

Wenn du sagst, dass meine Tests in die Hose gegangen seien, dann geht das in die aus meiner Sicht richtige Richtung. Da sprichst du TDD an.

Sind sie aber in die Hose gegangen? Nein, ich folge deiner Kritik nicht. Ich habe sie nämlich nicht der (entworfenen innneren) Datenstruktur angelehnt, sondern dem API und der Semantik des ADT, um den es hier geht.

Dass in den Tests "Worker" und "Queues" auftauchen, hat nichts mit der internen Datenstruktur zu tun, sondern mit dem Problem, das ich lösen musste. Und die Reihenfolge der Tests hat auch nichts mit der internen Datenstruktur zu tun, sondern spiegelt mein Bemühen wider, in kleinen Schritten von einfach nach komplizierter fortzuschreiten.

Wenn du nun ausführlich beschreibst, "was man braucht", dann ist eine interessant zu lesen - aber betrifft den Ansatz des Artikels nicht. Deine Lösung ist nicht besser als meine. Sie ist nur eben deine Lösung - auf die ich auch gar nicht näher eingehen will, ob sie wirklich irgendetwas vereinfacht. Allemal sehe ich nicht, dass noch TDDmäßigeres Vorgehen notwendig zu deiner Lösung geführt hätte. (Das wäre übrigens eine berechtigte Kritik, die du allerdings nicht angebracht hast.)

Wenn du dir die Mühe gemacht hättest, ins Repo zu schauen, dann hättest du auch gesehen, dass meine Lösung sehr wohl korrekt ist. Deine pauschale Kritik an fehlender Threadsicherheit ist unberechtigt, da sie annimmt, meine Artikel hätten alle Tests und die vollständige Implementation gezeigt. Das habe ich aber nicht behauptet - allerdings das Gegenteil auch nicht deutlich hervorgehoben. Warum? Weil es mir darum ja nicht ging. Die Demonstration des Vorgehens brauchte keine Vollständigkeit. Im Repo wirst du sehen, dass alle Methoden mit Locks gesichert sind. (Auch das mag nicht optimal sein - macht aber nichts. Es war ganz einfach gemacht und hat den gewünschten Effekt. Wenn das am Ende zu langsam sein sollte, optimiere ich. Alles andere wäre Premature Optimization.)

Bottom line: Ich sehe nicht, das hier großartig etwas in die Hose gegangen ist.

Anonym hat gesagt…

Why not just use ConcurrentQueue / ConcurrentDictionary instead of implementing own locking?

Frank hat gesagt…

"Sollte der Weg dir nicht gefallen, wenn du also meinst, der sei so gar nicht TDDlike, dann wäre das angebrachte Kritik."

Das habe ich durchaus gesagt:

"Nur hättest du spätestens bei der Erstellung der Test stutzig werden sollen. Warum bekommt man bei Test 3, also dem mehrfachen TryDequeue mit genau einem Worker, die Elemente nicht in der Reihenfolge, in der sie eingequeued worden? Das ist doch, was man als unbedarfter Benutzer ohne Kenntnis der Implementierung erwarten würde. Du hast die Tests so geschrieben, dass sie zu der angestrebten Implementierung (zumindest zur Datenstruktur) passen. Insofern finde ich dein Beispiel ziemlich in die Hose gegangen."

Mit Beispiel habe ich Beispiel für TDD gemeint. Mit anderen Worten: nach TDD wäre m.E. tatsächlich etwas anderes herausgekommen.

Ok, die Behauptung, dass man eine gemeinsame Queue braucht, war unbedacht und ging an der Sache vorbei. Ich habe jedoch dran fest, dass es eine übliche und wichtige Forderung ist, dass die Aufträge beim Dequeue - so weit möglich - in der Reihenfolge geliefert werden, in der die eingequeued wurden. Im Grunde ist das die Definition von Queue: First-In-First-Out. Überholen sollten sich Aufträge nur da, wo es aufgrund der Sequentialisierungsanforderungen unausweichlich ist.

Soweit ich das überblicke, stellt mein Vorschlag das sicher. Ob nun meine Idee für eine Datenstruktur und mein Vorschlag für eine Implementierung am Ende herausgekommen wäre oder eine andere Lösung mit den gleichen Eigenschaften der Schnittstelle, ist tatsächlich unerheblich. Da gebe ich dir Recht.

"Und die Reihenfolge der Tests hat auch nichts mit der internen Datenstruktur zu tun"

Die Reihenfolge der Tests vielleicht nicht, aber die Reihenfolge der Rückgabewerte spiegeln die Datenstruktur bzw. ihre Eigenschaften wieder. Wie ist es sonst zu erklären, dass (a, q1) (b,q1) (x,q2) (y,q2) bei der Entnahme durch einen einzigen Worker in der Reihenfolge a, x, b, y herausgegeben werden (sollen). Das würde doch niemand ohne Kenntnis der Datenstruktur oder der Implementierung erwarten. Da es hier nur einen Worker gibt, wird eh alles sequentiell ausgeführt. Es gibt also keine Anforderung, die die Änderung der Reihenfolge bedingt oder begründet. Die Queue sollte sich daher rein FIFO verhalten.

"Deine Lösung ist nicht besser als meine."

Doch, ich denke, sie ist objektiv besser. Auf Ebene der Schnittstelle. Aus den genannten Gründen.

Ob deine Lösung in deinem Kontext ausreichend ist und ihren Zweck erfüllt, steht auf einem anderen Blatt.

"Wenn du dir die Mühe gemacht hättest, ins Repo zu schauen, ..."

Um Mühe geht es doch hier nicht. Ich beziehe mich auf den Artikel. Und der sagt, dass der am Ende gezeigte Code (ohne Locks) alle Tests erfolgreich durchlaufen hat. Ich gehe davon aus, dass das tatsächlich so war. Da der Code fehlerhaft ist, ist gezeigt, dass die Tests nicht ausreichend waren, um alle vorhandenen Fehler aufzudecken. Ich bleibe also dabei, dass Testen bei nebenläufigen Komponenten noch viel weniger geeignet ist, um Fehler aufzudecken, als das in sequentiellem Code der Fall ist.

Frank hat gesagt…

"Ich sehe nicht, das hier großartig etwas in die Hose gegangen ist."

Nochmal zusammengefasst:

- Das TDD wird auf eine objektorientierte Komponente angewendet, die man zwar in FD verwenden kann, genauso wie man sie in jeder anderen Programmart verwenden kann, die also nichts speziell mit FD zu tun hat. Der im Titel hergestellte Bezug zwischen TDD und FD ist also nicht oder nur marginal vorhanden.
- Der pragmatische Ansatz, mit einer Datenstrukturidee zu beginnen, hat zu einer Schnittstelle mit objektiv schlechteren Eigenschaften geführt, als er durch reines TDD entstanden wäre.
- Die Tests waren (bei weitem) nicht ausreichend, um Fehler im nebenläufigen Code zu finden. Der Code, der am Ende des Artikels steht, ist wegen fehlender Synchronisation fehlerhaft. Die Tests haben das nicht aufgedeckt.

Mag sein, dass meine Kritik recht unverblümt formuliert war. Konstruktiv war sie trotz allem gemeint. In dem Sinne, dass ich gleichzeitig eine Anregung gegeben habe, wie man eine bessere Komponente erstellen kann. Besser zum einen Hinsichtlich der Schnittstelle (also inbesondere bezüglich der Reihenfolge, in der die Aufträge bei DeQueue geliefert werden), also auch hinsichtlich der Vermeidung von unnötige Wait-Operationen (blockierendes Dequeue statt TryDequeue+Wait). Ich würde mich freuen, wenn du das aufgreifst.

Um die Kritik jetzt auch noch konstruktiv hinsichtlich der Sicherstellung der Korrektheit von nebenläufigen Komponenten zu machen, empfehle ich den Code nicht nur zu testen, sondern vor allem einer sehr kritischen und ausdauernden Analyse zu unterziehen. Stichwort: böswillige Schreibtischtests; böswillig in dem Sinne, dass man die (gedanklichen) Thread-Wechsel immer an die Stellen legt, wo sie potenziell den größten Schaden anrichten.

Ralf Westphal - One Man Think Tank hat gesagt…

@Anonym: A threadsafe queue does not help much to get rid of the locks, since I need to make access to more than one data structure threadsafe.

Ralf Westphal - One Man Think Tank hat gesagt…

@Frank: Mit TDD kommt raus, was zu den Tests passt. Wenn ich meine Tests also in einer für dich unpassenden Weise formuliere, dann kann auch nur für dich Unpassendes herauskommen.

Die Diskussion, ob der ADT die Semantik haben sollte, die ich ihm gegeben habe oder eine andere, ist also eine andere Diskussion als die, ob ich bei meiner Idee von einer Semantik das "falsche" Ergebnis erzielt habe.

"Warum bekommt man bei Test 3, also dem mehrfachen TryDequeue mit genau einem Worker, die Elemente nicht in der Reihenfolge, in der sie eingequeued worden?"

Weil das die Semantik ist, die ich für angemessen halte. Ganz einfach. Für mich steht Round Robin höher als exakte Reihenfolge des Enqueue. Wie gesagt: Darüber lässt sich streiten - nur das hat nichts mit TDD zu tun. TDD zwingt mich nicht in eine semantische Richtung. Ich benutze vielmehr TDD, um in eine semantische Richtung zu gehen.

"die Reihenfolge der Rückgabewerte spiegeln die Datenstruktur bzw. ihre Eigenschaften wieder."

Nein, die Reihenfolge der Rückgabewerte spiegelt die angepeilte Semantik wider - der auch eine bestimmte Datenstruktur dient.

"Da der Code fehlerhaft ist, ist gezeigt, dass die Tests nicht ausreichend waren, um alle vorhandenen Fehler aufzudecken."

Und in welcher Hinsicht ist der Code fehlerhaft? Weil er nicht deiner Semantik folgt? Die ist ja aber kein Maßstab. Nicht weil es deine Semantik ist, sondern weil es nicht die ist, die sich in den Tests widerspiegelt. Fehlerhaft ist der Code nur, wenn er meine Tests nicht erfüllt. Oder wenn er zwar meine Tests erfüllt, die aber nicht ausreichend sind, um meine Vorstellung von der Semantik zu beschreiben.

"Das TDD wird auf eine objektorientierte Komponente angewendet, die man zwar in FD verwenden kann, genauso wie man sie in jeder anderen Programmart verwenden kann, die also nichts speziell mit FD zu tun hat."

Genau! Denn ich wollte zeigen, dass FD einen wechsel zu TDD nicht ausschließt. Also TDD im (!) FD oder zusätzlich zu FD.

"Der pragmatische Ansatz, mit einer Datenstrukturidee zu beginnen, hat zu einer Schnittstelle mit objektiv schlechteren Eigenschaften geführt, als er durch reines TDD entstanden wäre."

Das ist falsch. Am Anfang steht die Beschreibung der Semantik. Erst dann entwickle ich eine Idee für eine Datenstruktur. Und ein API entsteht nie durch TDD. Der erste Test, den ich hinschreibe, muss eine Idee von einem API haben, sonst könnte ich ihn nicht hinschreiben.

"Die Tests waren (bei weitem) nicht ausreichend, um Fehler im nebenläufigen Code zu finden. Der Code, der am Ende des Artikels steht, ist wegen fehlender Synchronisation fehlerhaft. Die Tests haben das nicht aufgedeckt."

Sorry, auch das ist falsch. Es wäre nur richtig, wenn ich den Anspruch gehabt hätte, alle Tests im Artikel zu beschreiben. Wie gesagt: Wenn du mir ankreidest dass ich nicht ausdrücklich am Ende gesagt habe, es gäbe noch mehr Tests und Code, dann nehme ich die Kritik an. Hätte ich besser machen können.

Frank hat gesagt…

"ich wollte zeigen, dass FD einen wechsel zu TDD nicht ausschließt."

Gezeigt hast du das allerdings nicht. Dass man dass im FD auch objektorientierte Komponenten als Blätter einsetzen kann, war schon vorher klar. Dass man objektorientierte Komponenten per TDD erstellen kann, erst recht. Und wem das nicht klar war, dem hast du nur gezeigt, dass FD einen Wechsel zu OOP nicht ausschließt und dass OOP TDD nicht ausschließt. Der ganz überwiegende Teil des Artikel behandelt jedenfalls nur die Anwendung von TDD auf eine objektorientierte Komponente.

"Für mich steht Round Robin höher als exakte Reihenfolge des Enqueue."

Ich kann mir nicht helfen. Das kommt mir wie ein Ausflucht vor. Wobei ich zugeben musst, dass du die Klasse NotifyingMultiQueue genannt hast. Selbstverständlich kann man unterschiedlicher Meinung sein, welche Semantik man haben möchte. Nur finde ich persönlich wirklich schwer nachvollziehbar, dass (a, q1) (b,q1) (x,q2) (y,q2) bei der Entnahme durch einen einzigen Worker in der Reihenfolge a, x, b, y herausgegeben werden (sollen). Das wäre mir nicht nur nie in den Sinn gekommen, sondern ich sehe darin auch keinen Vorteil.

"Und in welcher Hinsicht ist der Code fehlerhaft?"

In der Hinsicht, dass er - so wie er in dem Artikel steht - nicht thread-safe ist.

" 'Die Tests waren (bei weitem) nicht ausreichend, um Fehler im nebenläufigen Code zu finden.'
Sorry, auch das ist falsch. "

Ich behaupte, auch mit weiteren Tests wäre es dir schwergefallen, in dem Code ohne lock die dann vorhanden Fehler zu finden. Mir kommt es deshalb mehr auf die Aussage an, dass Tests alleine bei nebenläufigen Komponenten weniger als die halbe Miete sind.

Ralf Westphal - One Man Think Tank hat gesagt…

@Frank: Tut mir leid, dass du nicht sehen kannst, dass es ersten unterschiedliche Semantiken geben kann, jenachdem, wie der gewünschte Effekt aussehen soll.

Und dass du dann nicht anerkennen kannst, dass Code, der eine andere als deine implementiert, deshalb nicht falsch ist.

Was die Threadsafety angeht: Natürlich testen die gezeigten Tests die nicht. Das habe ich auch nicht behauptet - aber auch nicht deutlich hervorgehoben, dass die Threadsafety-Aspekte noch nicht berücksichtigt werden sollten.

Es tut mir leid, dass du nicht sehen kannst, dass es mir nicht um eine bestimmte Implementation geht, sondern um einen Weg. Und dann auch noch einen Weg innerhalb von TDD.

Ich denke, nun sollten wir unsere Diskussion aber ruhen lassen. An dem Punkt der unterschiedlichen Semantik kommen wir nicht weiter.

Danke für deinen Gedanken.

Frank hat gesagt…

Ich muss doch noch einmal antworten, weil du mir - sicher nicht in böser Absicht - gleich drei Punkte unterstellt, die nicht stimmen.



"Tut mir leid, dass du nicht sehen kannst, dass es ersten unterschiedliche Semantiken geben kann, jenachdem, wie der gewünschte Effekt aussehen soll."

Doch, das sehe ich. Sicher!

Ich sehe nur nicht, warum du diese Semantik willst und welche Vorteile du siehst. Du schreibst "Kein Port darf bevorzugt werden". Gut, was das genau bedeutet, hängt natürlich davon ab, was genau man unter "bevorzugen" versteht. Folgende Situation: Drei Ports, zwei Worker. Für die ersten beiden Ports stehen schon ja 100 Aufträge in der Queue (bzw. in den Queues). Ganz zum Schluss kommt ein Auftrag für Port 3. Das Round Robin würde maximal noch je eine Anfrage für die ersten beiden Ports bearbeiten und spätestens dann die von Port 3. Obwohl ganz viele Anfragen, die alle bearbeitet werden könnten, vorher eingestellt wurden. Das nenne ich bevorzugen. Obwohl sich Port 3 erst ganz, ganz hinten angestellt hat, wird er ohne Not vorgezogen.

Natürlich kann es unterschiedliche Semantiken geben, je nachdem, was man will, nur warum willst du die Round-Robin-Semantik? In meinen Augen werden gerade dadurch Ports bevorzugt, für die es wenige Aufträge gibt, gegenüber welchen, für die es viele Aufträge gibt.

Bei meinem Vorschlag würde ein Auftrag für Port 3 möglicherweise auch von ganz hinten vorgezogen, aber nur dann, wenn ein Worker frei ist, der wegen der Sequentialisierungsanforderungen momentan keinen der Aufträge davor bearbeiten kann. Das würde bezogen auf das Szenario allerdings nur eintreten, wenn es so geändert wird, dass es mindestens drei Worker gibt. Dann würde aber Port 3 nicht bevorzugt, denn der dritte Worker kann eh keine der anderen wartenden Aufträge vor dem für Port 3 bearbeiten.



"Und dass du dann nicht anerkennen kannst, dass Code, der eine andere als deine implementiert, deshalb nicht falsch ist."

Das habe ich nie behauptet.

Im Gegenteil: Ich habe mit der Muttermilch (ok: Professorenmilch :-) eingesogen, dass ein Programm oder eine Komponente dann korrekt ist, wenn sie der Spezifikation genügt. Ich habe nur für einen andere Semantik geworben. Die unbedachte Behauptung, dass man "meine" Semantik braucht, habe auf deinen Hinweis sofort zurückgezogen.

Von Fehlern habe ich nur im Zusammengang mit den echten Fehlern bezüglich der Thread-Sicherheit gesprochen. Also da, wo dein Code deiner Spezifikation nicht entspricht. An keiner anderen Stelle. Du kannst gerne den Text durchsuchen. :-)



"Es tut mir leid, dass du nicht sehen kannst, dass es mir nicht um eine bestimmte Implementation geht, sondern um einen Weg. Und dann auch noch einen Weg innerhalb von TDD."

Doch, auch das habe ich gesehen.

Zwar habe ich für eine andere Semantik geworben, doch das ist ja nicht unangebracht, nur weil das nicht im Mittelpunkt des Artikels stand. Du willst diese Komponente doch real einsetzen. Da sollten dir Feedback willkommen sein. Auch wenn es am Ende vielleicht nur dazu dient, dich darin zu bestärken, dass die Komponente genau das tut, was du möchtest.

Außerdem habe ich ja nicht nur über die Semantik gesprochen, sondern bin auch auf andere Punkte eingegangen, die im Mittelpunkt des Artikels stehen.

Ralf Westphal - One Man Think Tank hat gesagt…

@Frank: Also gut, wenn es denn sein soll: nochmal und hoffentlich abschließend Semantik.

Dein Szenario greife ich auf. Du beschreibst ja korrekt meine Vorstellung der Semantik. Deine Urteil: bevorzugend.

Mein Urteil hingegen: gleichstellend :-)

Genau, ich empfinde meine Semantik als wünschenswert, weil sie eben nicht den Unterschied macht, den du für richtig hälst. Meine Semantik behandelt alle Ports gleich. Sie bevorzugt keinen Port nach dem Nachrichtenaufkommen.

Wir haben einfach unterschiedliche Prioritäten: für dich ist die Abarbeitung von Nachrichten wichtig, für mich ist die Bedienung von Ports wichtig.

Warum ziehe ich die Port-Sichtweise vor? Ports sind wie "Kunden" (K*) in einem Geschäft. Das Geschäft bietet unterschiedliche Leistungen (L*) an mit einer begrenzten Zahl von Ressourcen (R*).

Dein Modell behandelt alle Leistungen und Kunden gleich. Sobald eine Ressource frei wird, widmet sie sich dem nächsten Kunden in der einen Schlange. Das hört sich erstmal gerecht an. (Dass pro Leistung nur ein Kunden "in Arbeit" sein kann, ist im Augenblick ein Detail.)

Was aber, wenn die Leistungen unterschiedlich lange brauchen? Dann muss jmd, der eigentlich nur gaaanz kurz eine Sache erledigt bekommen will, gaaanz lange warten. Er kann an den anderen nicht vorbeiziehen.

Das mag irgendwie gerecht sein - aber in jedem Supermarkt sehe ich, dass Menschen sich anders verhalten. Da werden Kunden mit nur einer Milch in der Hand von den anderen mit vollen Einkaufskörben vor ihnen in der Schlange vorbeigelassen. Oder es gibt sogar Expresskassen.

Warum? Weil das den Durchfluss erhöht.

Niemand empfindet das als ungerecht.

In der Programmierung kann ein solcher Unterschied z.B. zwischen normalen Nachrichten und Fehlern bestehen. Warum soll eine Fehlernachricht (oder eine andere mit hoher Prio) darauf warten, dass Tausende andere erst verarbeitet werden, die vorher eingetroffen sind?

Mein Modell berücksichtigt das. Ohne den Zwang mit expliziten Prioritäten zu jonglieren, gibt es reihum jedem Port Aufmerksamkeit. An Ports im "Hauptfluss" werden da natürlich viele Nachrichten eingehen, an Fehlerports wenige. Solange keine Fehler anliegen, widmen sich die Threads den Nachrichten im "Hauptfluss". Wenn aber mal ein Fehler eintrifft, wird der bald behandelt.

Mein Modell erzwingt den Fokuswechsel nach jeder Nachricht. Dein Modell sorgt hingegen dafür, dass Ports mit hoher Nachrichtenzahl bevorzugt behandelt werden. Die können die Threads für andere Aufgaben blockieren. Wenn Windows nach deinem Modell arbeiten würde, hättest du nicht viel Spaß dran.

Anonym hat gesagt…

Es heißt "Round Robin", mit einem "b". Vielleicht solltest Du nicht soviel Tony lesen, es gibt da eh' Besseres als diesen ... ach, egal.