Entwerfen Sie eine Klasse, die nur dann eine Sperre bereitstellt, wenn keine Deadlocks möglich sind
Ich bin vor kurzem auf diese Interviewfrage gestoßen (die in einem Forum gepostet wurde, wo es irgendwas gibt ... sieht so aus, als wäre das eine echte Interviewfrage):
Entwerfen Sie eine Klasse, die nur dann eine Sperre bereitstellt, wenn keine Deadlocks möglich sind.
Es sind keine weiteren Informationen angegeben. Ich bin mir nicht sicher, wie ich das interpretieren soll. Angenommen, das pthreads-Modell sucht den Interviewer nach einer Lock-Manager-Klasse? Irgendwelche Ideen werden helfen.
3 Antworten
Ein Deadlock tritt nur dann mit einer Sperre auf, wenn die Sperren in einer kreisförmigen Weise gehalten werden können; das heißt, wenn Sie eine Bestellung definieren & lt; auf Sperren, so dass A & lt; B nur wenn Schloss A gehalten werden kann und Schloss B ebenfalls gehalten wird, dann & lt; ist keine strikte Teilbestellung. Wenn zum Beispiel Thread 1 versucht, die Sperre A zu erhalten und dann B zu sperren, während der Thread 2 versucht, die Sperre B zu erhalten und dann die Sperre A, dann wird A & lt; B und B & lt; A, so & lt; ist keine strikte Teilbestellung. Tatsächlich kann ein Deadlock auftreten, wenn die Threads 1 und 2 jeweils die Sperren A und B erhalten und dann versuchen, die andere Sperre zu übernehmen.
Um diese Art von Bedingung dynamisch zu erkennen, besteht eine Option darin, einen gerichteten Graphen der Sperren im System beizubehalten. Immer wenn ein Thread versucht, eine Sperre zu erhalten, fügen Sie eine Kante aus jeder Sperre, die er enthält, zu der Sperre hinzu, die er zu erfassen versucht. Wenn diese Aktion einen Zyklus bildet, wird ein Deadlock auftreten, da ein anderer Thread die Sperre besitzt, auf die Sie zeigen, und versucht, eine andere Sperre zu erlangen. Diese Struktur wäre global und Sie müssen die entsprechenden Vorkehrungen treffen, um sicherzustellen, dass sie korrekt synchronisiert wurde. Es würde Ihnen jedoch eine sehr direkte Möglichkeit geben, zu erkennen, ob ein Deadlock auftreten würde oder nicht.
BEARBEITEN: Hier ist eine Skizze eines einfachen Implementierungsschemas. Ich nehme an, dass Sie als primitive eine naive Mutex-Sperre haben, die Deadlock nicht verhindert, zusammen mit der Möglichkeit, einige Daten pro Thread zu speichern.
Erstellen Sie innerhalb der Smart Lock-Klasse einen statischen Mutex, der von allen Instanzen der Sperre gemeinsam genutzt wird und den Zugriff auf das Eigentumsdiagramm verhindert. Erstellen Sie außerdem eine Zuordnung, die jede Sperre mit der Gruppe von Sperren verknüpft, an die sie Kanten hat. Richten Sie schließlich eine pro-Thread-Gruppe aller Sperren ein, die diesem Thread gehören.
Wenn ein Thread versucht, eine intelligente Sperre zu erhalten, muss zuerst der statische Mutex abgerufen werden, um exklusiven Zugriff auf die Graphenstruktur zu gewährleisten. Fügen Sie für jede der Sperren, die diesem Thread gehören, eine Kante im statischen Diagramm von dieser Sperre zu der Sperre hinzu, die erworben wird. Führen Sie nun eine Tiefensuche über das Diagramm durch, beginnend mit jeder der Sperren, die vom aktuellen Thread auf der Suche nach Zyklen gehalten werden. Dies erfordert eine lineare Zeit in der Größe des Graphen, die im schlimmsten Fall quadratisch in der Anzahl der Sperren im System ist (obwohl dies extrem unwahrscheinlich ist, da dies bedeuten würde, dass ein großer Bruchteil der Sperren irgendwie von den Threads erreichbar ist Schlösser). Wenn ein Zyklus gefunden wird, wird ein Deadlock auftreten und Sie sollten eine Art von Korrekturmaßnahmen ergreifen. Andernfalls geben Sie die statische Sperre frei, damit andere Threads auf das Diagramm zugreifen können.
Wenn ein Thread tatsächlich eine Sperre erwirbt, fügen Sie diese Sperre der Gruppe der Sperren des Threads hinzu.
Wenn ein Thread eine Sperre aufgibt, erfasse die statische Grafiksperrung und entferne alle ankommenden Kanten auf den Knoten für diese Sperre, die anderen Sperren entsprechen, die vom aktuellen Thread gehalten werden, und lasse dann die Sperre los.
Hoffe, das hilft!
Nun, ich würde sagen, dass die wichtigste Erkenntnis darin besteht, dass die einzige Möglichkeit, die eine Klasse orchestrieren kann, darin besteht, die gesamte Menge der zugehörigen Sperren zu kontrollieren, die an solchen Deadlocks beteiligt sein könnten. Es kann dann beispielsweise erfordern, dass sie in einer bestimmten Reihenfolge ausgeführt werden (z. B. alphabetische Reihenfolge basierend auf einem Namen, der mit jeder Sperre verknüpft ist, beliebigen eindeutigen Ganzzahlen, die in der Quelle fest codiert sind).
