Låsfria samtidiga algoritmer garanterar att vissa samtidiga operationer alltid kommer att göra framsteg i ett begränsat antal steg. Ändå föredrar programmerare att behandla samtidig kod som om den vore vänta-fri, vilket garanterar att alla operationer alltid gör framsteg. Tyvärr, designa vänta-fria algoritmer är i allmänhet en mycket komplex uppgift, och de resulterande algoritmer är inte alltid effektiva. Samtidigt som effektiva vänta-fria algoritmer har varit ett långvarigt mål för teorigemenskapen, de flesta icke-blockerande kommersiella kod är bara lås-fri. I detta dokument föreslås en enkel lösning på detta problem. Vi visar att, för en stor klass av låsfria algoritmer, under schemaläggningsförhållanden som ungefär motsvarar de som finns i kommersiella hårdvaruarkitekturer, låsfria algoritmer beter sig som om de är vänta-fria. Med andra ord kan programmerare fortsätta att utforma enkla låsfria algoritmer istället för komplexa väntefria algoritmer, och i praktiken kommer de att få vänta-fria framsteg. Vårt huvudsakliga bidrag är ett nytt sätt att analysera en allmän klass av låsfria algoritmer under en stokastisk schemaläggare. Vår analys relaterar processernas individuella prestanda med systemets globala prestanda med hjälp av Markov-kedjelyftning mellan en komplex per-processkedja och en enklare systemutvecklingskedja. Vi visar att låsfria algoritmer inte bara är vänta-fria med sannolikhet 1, men att i själva verket en allmän delmängd av lås-fria algoritmer kan nära avgränsas i termer av det genomsnittliga antalet steg som krävs tills en operation avslutas. Såvitt vi vet är detta det första försöket att analysera utvecklingsförhållanden, typiskt uttryckt i förhållande till en värsta fall motståndare, i en stokastisk modell fånga deras förväntade asymptotiskt beteende.
Alistarh m.fl. REF bevisar att förutsatt att en stokastisk schemaläggare som bestämmer beställningen av åtkomst till en minnesplats, låsfria algoritmer beter sig praktiskt taget vänta-fri.
Are lock-free concurrent algorithms practically wait-free?
{'venue': "STOC '14", 'journal': None, 'mag_field_of_study': ['Computer Science']}