A nem blokkoló szinkronizálás a szimmetrikus többprocesszoros rendszerek párhuzamos programozásának olyan megközelítése, amely elszakad a hagyományos blokkoló primitívektől , például a szemaforoktól , mutexektől és eseményektől . A hozzáférés megosztása a szálak között az atomműveletek és az adott feladatra kifejlesztett speciális reteszelő mechanizmusok rovására megy.
A nem blokkoló algoritmusok előnye a jobb skálázhatóság a processzorok számát tekintve. Ráadásul, ha az OS megszakítja valamelyik szálat háttérfeladattal, a többiek üresjárat nélkül végzik a dolgukat, vagy akár át is veszik a kiemelkedő munkát.
A leggyengébbtől a legerősebbig:
Akadályok nélkül ( eng. akadálymentes ) A leggyengébb garancia. Egy szál akkor halad előre, ha más szálaktól nem ütközik akadályba. Az algoritmus akadályok nélkül működik, ha egy bármikor futó szál (feltételezve, hogy minden akadályozó szál fel van függesztve) meghatározott számú lépésben befejezi a munkáját. A mutexekkel való szinkronizálás még ennek a követelménynek sem felel meg: ha egy szál a mutex megszerzése után leáll, a többi szál, amelyeknek szüksége van a mutexre, tétlen lesz. Zárak nélkül ( eng. lock-free ) Zárolásmentes algoritmusok esetén legalább egy szál rendszer előrehaladása garantált. Például egy ciklusban az " összehasonlítás a cserével " műveletet végrehajtó szál elméletileg korlátlan ideig futhat, de minden iterációja azt jelenti, hogy egy másik szál előrehaladt, vagyis a rendszer egésze halad. Elvárások nélkül ( eng. wait-free ) A haladás legerősebb garanciája. Az algoritmus várakozás nélkül működik, ha minden műveletet bizonyos számú lépésben hajtanak végre, függetlenül a többi száltól.Többszálú alkalmazások létrehozásakor gyakran meg kell osztani a hozzáférést egy megosztott erőforráshoz. A hagyományos megközelítés lehetővé teszi szekvenciális hozzáférés biztosítását szinkronizálási mechanizmusok, például zárak használatával . A szinkronizálási primitívek, mint például a mutexek , szemaforok és kritikus szakaszok , lehetővé teszik olyan kódrészlet megírását, amely garantáltan nem fut egyidejűleg, ha párhuzamos szálakról éri el – a megosztott memóriarészhez való egyidejű hozzáférés tartalomsérüléshez vezethet. Ha az egyik szál megpróbálja megszerezni a zárolást, amelyet egy másik szál már tart, az első szál végrehajtását felfüggeszti, amíg a második szálban fel nem oldja a zárat.
A legegyszerűbb mutex [1] az úgynevezett spinlock 'a - egy üres ciklus atomi műveletekkel valósítható meg. Az összetettebb sorbanállási primitívek egy költséges, " környezetkapcsolónak " nevezett művelettel és ugyanazzal a kernelben lévő spinlock-al valósulnak meg ( Windows rendszeren ) , amely biztosítja a prioritási sort . Ha a szinkronizálási primitívek terhelése alacsony (a felhasználói felület egy másik szál általános előrehaladását írja ki; az egyik szál a hálózaton keresztül letöltendő feladatokat ad, a második letölti...), az üres hurkok és kapcsolók többletköltsége kicsi. KiDispatcherLock
Ha nagy mennyiségű adatot dolgoznak fel egy többmagos processzoron, és a szálak közötti interakció nagyobb lesz. A közönséges adatstruktúrákat, például a keresőfát , csak teljes egészében lehet bekeríteni egy mutex-szel, és ha a szálak folyamatosan hozzáférnek hozzá, a munka szinte szekvenciálissá válik. Ezenkívül egy általános célú operációs rendszerrel rendelkező közönséges személyi számítógép más feladatokat is ellát - például egy felhasználó, aki a végrehajtásra vár, megnyit egy böngészőt -, és a processzoridő egy részét megkapja, és a számítási szálakat véletlenszerű pillanatokban felfüggesztik. . A nem blokkoló algoritmusok garantálják, hogy az egyik szál ilyen leállítása nem vezet a többi tétlenségéhez. A tétlenség hiánya különösen fontos, ha az egyik szál magas prioritású vagy valós idejű feladatot hajt végre .
A nem blokkoló szinkronizálás lehetővé teszi a holtpontok teljes megszabadulását . A nem blokkoló algoritmusoknak azonban megvannak a maguk hibái - hurok ( livelock ) és " verseny ".
A nem blokkoló algoritmusok atomi műveletekre épülnek , például olvasás-módosítás-írás , és ezek közül a legjelentősebb a cserével való összehasonlítás (CAS). Egy kritikus szakasz megvalósítása általában az egyik primitív használatán alapul. Egészen a közelmúltig a nem blokkoló algoritmusok minden megvalósítását "alacsony" hardverszinten kellett végrehajtani, hogy az elfogadható teljesítményt biztosítsák. A tranzakciós memóriamechanizmusok fejlődése azonban szabvány absztrakciókat biztosít a hatékony, nem blokkoló kód írásához.
Olyan alapvető adatstruktúrákat is kifejlesztettek , mint a verem , a sor , a halmaz és a hash tábla . Az ilyen struktúrák lehetővé teszik a programszálak közötti aszinkron adatcsere egyszerűsítését. Néhány adatstruktúra meglehetősen egyszerű, és speciális atomzárak nélkül is használható, például: