Dynamische Erkennung von Datenrennen mit O(1) Proben

Die bevorstehende dynamische Analyse ist die bevorzugte Technik zur Erkennung von Datenrennen in groß angelegten Softwareprojekten aufgrund des Fehlens von falschen Positiven. Solche Analysen sind jedoch teuer, da sie bei jedem Ereignis kostspielige Vektoruhrenaktualisierungen durchführen, was sie nur für interne Tests nutzbar macht. In diesem Papier präsentieren wir einen stichprobenbasierten, zufälligen Rennendetektor, der selbst im schlimmsten Fall nur konstant viele Ereignisse der Eingabespur verarbeitet. Dies ist der erste Sub-linear-Zeit (d.h. läuft in o(n)-Zeit, wobei n die Länge der Spur ist) Algorithmus zur dynamischen Erkennung von Datenrennen; frühere stichprobenbasierte Ansätze laufen in linearer Zeit (d.h. O(n)). Unser Algorithmus ist ein Eigenschaftsprüfer zur -Rennen-Erkennung – er ist valider, da er niemals falsche Positive meldet, und bei Spuren, die bezüglich der Hamming-Distanz weit von einer rennfreien Spur entfernt sind, erkennt der Algorithmus mit hoher Wahrscheinlichkeit ein -Rennen. Unsere experimentelle Bewertung des Algorithmus und sein Vergleich mit modernsten deterministischen und stichprobenbasierte Rennendetektoren zeigt, dass der Algorithmus tatsächlich eine signifikant niedrige Laufzeit hat und recht oft Rennen erkennt.