Minneshanteringsstöd för låsfria datastrukturer är känt för att vara ett svårt problem. Den senaste tidens arbete har framgångsrikt minskat omkostnaderna för sådana system. Att använda stöd för minneshantering till en datastruktur är dock fortfarande komplicerat och kräver i många fall en ny utformning av datastrukturen. I detta dokument presenterar vi det första låsfria minneshanteringssystemet som är tillämpligt på generella (arbiträra) låsfria datastrukturer och som kan tillämpas automatiskt via en kompilatorplug-in. Förutom enkelheten i att införliva datastrukturer ger detta system låga omkostnader och förlitar sig inte på låsfriheten för alla OS-tjänster. Detta verk är licensierat under en Creative Commons Erkännande 4.0 internationell licens. Nachshon Cohen a (eventuellt icke-expert) utövare att tillämpa ett minne-reklamation system när införliva datastrukturen i en verklig ansökan. Emellertid, state-of-the-art minne reklamation system kräver datastrukturen för att uppfylla vissa algoritmiska egenskaper som inte uppfylls av många praktiska data-strukturer. Om en datastruktur inte uppfyller de nödvändiga egenskaperna, finns det inget tydligt recept för att ändra den så att den skulle vara mottaglig för minne reklamation. I allmänhet kan det krävas expertis som inte är tillgänglig för alla utövare, kan ändra egenskaperna hos datastrukturen eller inte alls. Tänk till exempel på Harris länkade lista [Harris 2001] som står i centrum för många låsfria datastrukturer. Den ursprungliga riskpekarpapper [Michael 2002a ] anger att Harris länkade lista är łinherent inkompatibelž med riskpekarschema 1. I stället utformade de en variation av denna datastruktur — den länkade listan Harris-Michael [Michael 2002b] — på vilken riskpekaren kan användas. Skillnaderna mellan dessa datastrukturer är subtila och därför är det lätt att förvirra dem. Sådan förvirring kan leda till att även erfarna forskare tillämpar riskindikationer på fel datastruktur, vilket resulterar i en felaktig design. Dessutom visades det senare att den länkade listan Harris-Herlihy-Shavit [Herlihy och Shavit 2012] också är oförenlig med systemet med riskvärderingar. Denna datastruktur ger starkare framstegsgarantier (dvs. vänta-fria sökningar) och bättre prestanda än Harris-Michael länkade listan [Cohen och Petrank 2015a]. Andra färska minnes-reklamation system [Alistarh et al. År 2015; Balmau m.fl. År 2016; Braginsky m.fl. 2013; Brown 2015; Cohen och Petrank 2015b; Dice et al. 2016] är på liknande sätt oförenliga med datastrukturerna Harris och Harris-Herlihy-Shavit. I detta dokument presenterar vi Free Access: det första minnes-reklamation systemet som står upp mot förväntningarna hos data-strukturdesigners. Free Access-systemet kräver inte att datastrukturen uppfyller några algoritmiska egenskaper, vilket gör den allmänt tillämplig för befintliga och framtida låsfria datastrukturer. I stället krävs det bara att ingen undervisning samtidigt läser en ny pekare och skriver till det delade minnet. Alla låsfria datastrukturer vi är medvetna om uppfyller denna egenskap utan någon ändring. Vi kan inte utesluta en framtida ny design som använder en ostödd instruktion, men även en sådan design kan enkelt ändras genom att ersätta den ostödda instruktionen med en Jämför-And-Swap (CAS) loop, vilket gör det möjligt att tillämpa Free Access 2. Den största effekten av systemet med fri tillgång är frikopplingen av utformningen av låsfria datastrukturer från minnesåterhämtningen. Denna frikoppling gör det möjligt för konstruktörer av låsfria datastrukturer att koncentrera sig på att utforma datastrukturen utan att oroa sig för om deras utformning är mottaglig för minnesåterhämtning. Systemet med fri tillgång bygger på begreppet datastrukturspecifik sophämtning, som infördes av Cohen och Petrank [2015a]. Under genomförandet av programmet, bestämmer Free Access automatiskt uppsättningen ouppnåeliga data-struktur noder och återtar dem för framtida tilldelningar. Reklamationsalgoritmen för fri tillgång är mycket lik systemet Automatic Optimistic Access (AOA) [Cohen och Petrank 2015a] och är löst baserad på tekniken för att samla in mark & sweep sopor. Den börjar med att samla ihop de globala rötterna, datastrukturnoder som kan nås av alla trådar (t.ex. huvudet på en länkad lista), och de lokala rötterna, datastrukturnoder som finns i registren och stacken av varje tråd. Sedan spårar den dessa rötter och markerar alla datastrukturnoder som kan nås från en av rötterna. Slutligen återtar det alla datastrukturer noder som är omärkta. (Mer bakgrundsinformation finns i avsnitt 2). Även om återställningsalgoritmen för fri tillgång är mycket lik AOA-systemet, finns det en stor skillnad mellan de två. AOA-systemet är endast tillämpligt för datastrukturer skrivna 1 Avsnitt 2.2.1 ger mer bakgrund till denna inkompatibilitet 2 Avsnitt 6 diskuterar denna ounderstödda instruktion och presenterar ersättningsalgoritm.
Fri tillgång REF ] automatiserar tillämpningen av Automatic Optimistic Access.
Every data structure deserves lock-free memory reclamation
{'venue': 'PACMPL', 'journal': None, 'mag_field_of_study': ['Computer Science']}