Vi tar upp problemet med automatisk verifiering och staketinferens i samtidiga program som körs under avslappnade minnesmodeller. Moderna arkitekturer implementerar avslappnade minnesmodeller där minnesoperationer kan ordnas om och utföras icke-atomiskt. Instruktioner som kallas minnesstängsel ges till programmeraren, vilket tillåter kontroll av detta beteende. För att säkerställa att många algoritmer är korrekta krävs det ofta att programmeraren uttryckligen infogar minnesstängsel i sitt program. Men hon måste använda så få staket som möjligt, eller fördelarna med den avslappnade arkitekturen kan gå förlorade. Det är vårt mål att hjälpa till att automatisera insättandet av stängslet. Vi presenterar en algoritm för automatisk slutledning av minne stängsel i samtidiga program, befria programmeraren från denna komplexa uppgift. Med tanke på ett ändligt tillståndsprogram, en säkerhetsspecifikation och en beskrivning av minnesmodellen beräknar vår algoritm en uppsättning beställningsbegränsningar som garanterar att programmet är korrekt under minnesmodellen. De beräknade begränsningarna är högst toleranta: att ta bort eventuella begränsningar från lösningen skulle tillåta en avrättning som bryter mot specifikationen. Dessa begränsningar realiseras sedan som ytterligare stängsel i inmatningsprogrammet. Vi implementerade vår strategi i ett par verktyg som kallas fender och mixer och använde dem för att dra rätt och effektiv placering av stängsel för flera icke-triviala algoritmer, inklusive praktisk ömsesidig uteslutning primitiver och samtidiga datastrukturer.
Med tanke på ett finitstate-program och en specifikation för korrekthet/säkerhet, drar Fender REF slutsatsen att det finns minst begränsade minnesstängsel som behövs för att uppfylla specifikationen.
Automatic inference of memory fences
{'venue': 'SIGA', 'journal': None, 'mag_field_of_study': ['Computer Science']}