Ei-esto synkronointi on lähestymistapa rinnakkaiseen ohjelmointiin symmetrisissä moniprosessorijärjestelmissä, joka eroaa perinteisistä estoprimitiiveistä , kuten semaforeista , mutexeista ja tapahtumista . Pääsyn jakaminen säikeiden välillä tapahtuu atomioperaatioiden ja tiettyä tehtävää varten kehitettyjen erityisten lukitusmekanismien kustannuksella.
Ei-esto-algoritmien etuna on parempi skaalautuvuus prosessorien lukumäärän suhteen. Lisäksi, jos käyttöjärjestelmä katkaisee yhden säikeistä taustatehtävällä, loput tekevät työnsä ilman joutoaikaa tai jopa ottavat hoitaakseen erinomaisen työn.
Heikoimmasta vahvimpaan:
Ilman esteitä ( esim. esteetön ) Takuista heikoin. Säie etenee, jos se ei kohtaa esteitä muista säikeistä. Algoritmi toimii ilman esteitä, jos milloin tahansa käynnissä oleva säie (olettaen, että kaikki estävät säikeet on keskeytetty) suorittaa työnsä deterministisenä määränä vaiheita. Synkronointi mutexien kanssa ei edes täytä tätä vaatimusta: jos säie pysähtyy mutexin hankinnan jälkeen, muut mutexia tarvitsevat säikeet ovat valmiina. Ilman lukkoja ( eng. lock-free ) Lukitsemattomissa algoritmeissa järjestelmän eteneminen vähintään yhden säikeen taataan. Esimerkiksi säie, joka suorittaa " vertaa vaihtoon " -operaation silmukassa, voisi teoriassa toimia loputtomiin, mutta jokainen sen iteraatio tarkoittaa, että jokin muu säie on edistynyt, mikä tarkoittaa, että järjestelmä kokonaisuudessaan edistyy. Ilman odotuksia ( eng. wait-free ) Vahvin tae edistymiselle. Algoritmi toimii odottamatta, jos jokainen operaatio suoritetaan tietyssä määrässä vaiheita muista säikeistä riippumatta.Monisäikeisiä sovelluksia luotaessa on usein tarpeen jakaa pääsy jaettuun resurssiin. Perinteinen lähestymistapa mahdollistaa peräkkäisen pääsyn myöntämisen synkronointimekanismin, kuten lukkojen , avulla . Synkronointiprimitiivit, kuten mutexit , semaforit ja kriittiset osat , antavat sinun kirjoittaa koodinpätkän, jota ei taatusti suoriteta samanaikaisesti, kun sitä käytetään rinnakkaisista säikeistä - samanaikainen pääsy jaettuun muistiin voi johtaa sisällön vioittumiseen. Yhden säikeen yritys hankkia lukko, jota toinen lanka jo pitää, aiheuttaa ensimmäisen langan suorittamisen keskeytyksen, kunnes lukko vapautetaan toisessa langassa.
Yksinkertaisin mutex [1] on toteutettu käyttämällä ns. spinlock 'a - tyhjää sykliä atomioperaatioineen. Monimutkaisemmat jonoprimitiivit tehdään kalliilla toiminnoilla, joita kutsutaan " kontekstikytkimeksi " ja samalla spinlockilla ytimessä ( KiDispatcherLockWindowsissa ), joka suojaa prioriteettijonon . Kun synkronointiprimitiivien kuormitus on alhainen (käyttöliittymä tulostaa toisen säikeen yleisen edistymisen; yksi säie antaa tehtäviä verkon kautta ladattavaksi, toinen latautuu...), tyhjien silmukoiden ja kytkimien ylimääräinen kustannus on pieni.
Jos ne käsittelevät suuren määrän tietoa moniytimisessä prosessorissa, säikeiden välinen vuorovaikutus kasvaa. Tavalliset tietorakenteet, kuten hakupuu , voidaan rajata vain mutexilla kokonaisuudessaan, ja jos säikeet pääsevät siihen jatkuvasti, työ muuttuu lähes peräkkäiseksi. Lisäksi tavallinen henkilökohtainen tietokone, jossa on yleiskäyttöinen käyttöjärjestelmä, suorittaa muita tehtäviä - esimerkiksi käyttäjä, joka odottaa suoritusta, avaa selaimen - ja osa prosessorin ajasta annetaan hänelle, ja laskennalliset säikeet keskeytetään satunnaisina hetkinä . Ei-estoalgoritmit takaavat, että tällaiset yhden säikeen pysäyttämiset eivät johda muiden joutoaikaan. Joutoajan puuttuminen on erityisen tärkeää, jos jokin säikeistä suorittaa korkean prioriteetin tehtävää tai reaaliaikaista tehtävää .
Estoimattoman synkronoinnin avulla voit päästä kokonaan eroon umpikujasta . Ei-estävillä algoritmeilla on kuitenkin omat virheensä - silmukka ( livelock ) ja " kilpailut ".
Ei-esto-algoritmit rakentuvat atomioperaatioille , esimerkiksi lue-muokkaa-kirjoita ja niistä merkittävin on vertailu vaihtoon (CAS). Kriittisen osan toteutus perustuu yleensä jonkin primitiivin käyttöön. Viime aikoihin asti kaikki ei-esto-algoritmien toteutukset oli tehtävä "matalalla" laitteistotasolla hyväksyttävän suorituskyvyn varmistamiseksi. Tapahtumamuistimekanismien kehitys tarjoaa kuitenkin standardinmukaisia abstraktioita tehokkaan ei-estokoodin kirjoittamiseen.
Myös perustietorakenteita , kuten pino , jono , joukko ja hash-taulukko , on kehitetty . Tällaiset rakenteet mahdollistavat asynkronisen tiedonvaihdon yksinkertaistamisen ohjelmasäikeiden välillä. Jotkut tietorakenteet ovat melko yksinkertaisia ja niitä voidaan käyttää ilman erityisiä atomilukkoja, esimerkiksi: