Lukk (arvutiteadus)

Arvutiteaduses on lukk või mutex ( vastastikku välistamiseks) sünkroniseerimisprimitiiv, mis takistab oleku muutmist või sellele juurdepääsu mitme lõimu poolt korraga. Lukud jõustavad vastastikuse välistamise samaaegsuse kontrolli poliitikaid ning mitmesuguste võimalike meetoditega on erinevate rakenduste jaoks olemas mitu unikaalset implementatsiooni.
Tüübid.
Üldiselt on lukud "nõuandelised lukud", kus iga niit teeb enne vastavatele andmetele juurdepääsu saamist koostööd, omandades luku. Mõned süsteemid rakendavad ka "kohustuslikke lukke", mille korral lukustatud ressursile volitamata juurdepääsu katse sunnib juurdepääsu proovivale üksusele erandi tegema.
Lihtsaim luku tüüp on binaarne semafor . See annab lukustatud andmetele eksklusiivse juurdepääsu. Ka teised skeemid pakuvad andmete lugemiseks jagatud juurdepääsu. Teised laialdaselt rakendatud juurdepääsurežiimid on eksklusiivne, kavatsusega välistada ja kavatsusega uuendada.
Teine viis lukkude liigitamiseks on see, mis juhtub siis, kui lukustusstrateegia takistab lõime edasiliikumist. Enamik lukustusdisainilahendusi blokeerib lukustust taotleva lõime täitmise seni, kuni sellel lubatakse lukustatud ressursile juurde pääseda. Spinlocki korral niit lihtsalt ootab ("keerutab"), kuni lukk kättesaadavaks muutub. See on efektiivne, kui lõimed on lühikeseks ajaks blokeeritud, kuna see väldib operatsioonisüsteemi protsesside ümberajastamise lisakoormust. See on ebaefektiivne, kui lukku hoitakse pikka aega või kui lukku hoidva lõime edenemine sõltub lukustatud lõime ennetavast blokeerimisest.
Lukud vajavad tõhusaks rakendamiseks tavaliselt riistvaralist tuge. See tugi toimub tavaliselt ühe või mitme aatomilise käsu vormis, näiteks " test-and-set ", " fetch-and-add " või " compare-and-swap ". Need juhised võimaldavad ühel protsessil kontrollida, kas lukk on vaba, ja kui see on vaba, siis see ühe aatomilise operatsiooniga hankida.
Üheprotsessorilistel arhitektuuridel on võimalus kasutada katkematuid käskude jadasid – kasutades spetsiaalseid käske või käskude eesliiteid katkestuste ajutiseks keelamiseks –, kuid see tehnika ei tööta mitmeprotsessoriliste jagatud mäluga masinate puhul. Mitmeprotsessorilises keskkonnas lukkude nõuetekohane tugi võib nõuda üsna keerukat riist- või tarkvaratuge, millega kaasnevad märkimisväärsed sünkroniseerimisprobleemid .
Aatomoperatsiooni vajaduse põhjuseks on samaaegsus, kus sama loogikat täidab rohkem kui üks ülesanne. Näiteks vaatleme järgmist C -koodi:
if (lock == 0) {
 // lock free, set it
 lock = myPID;
Ülaltoodud näide ei garanteeri, et ülesandel on lukk, kuna lukku saab korraga testida mitu ülesannet. Kuna mõlemad ülesanded tuvastavad luku vaba oleku, proovivad mõlemad lukku seadistada, teadmata, et teine ülesanne samuti lukku seadistab. Dekkeri või Petersoni algoritm on võimalikud asendajad, kui aatomilukustusoperatsioonid pole saadaval.
Lukkude hooletu kasutamine võib põhjustada ummikseise või otselukustuse . Ummikseisidest või reaalajas lukustustest vabanemiseks või neist taastumiseks saab kasutada mitmeid strateegiaid nii disaini kui ka käitusajal . (Kõige levinum strateegia on lukkude hankimise järjestuste standardiseerimine nii, et omavahel seotud lukkude kombinatsioonid hangitakse alati spetsiifiliselt määratletud "kaskaadi" järjekorras.)
public class Account // This is a monitor of an account
 // Use `object` in versions earlier than C# 13
 private readonly Lock _balanceLock = new();
 private decimal _balance = 0;
 public void Deposit(decimal amount)
 // Only one thread at a time may execute this statement.
 lock (_balanceLock)
 _balance += amount;
 public void Withdraw(decimal amount)
 // Only one thread at a time may execute this statement.
 lock (_balanceLock)
 _balance -= amount;
C# tutvustus  Keermestamine. Lukk C# 13-s peal . NET 9.
codice_1 võib probleeme tekitada, kui eksemplarile pääseb avalikult ligi. 
Sarnaselt Javaga saab ka C# sünkroniseerida terveid meetodeid, kasutades MethodImplOptions . Sünkroniseeritud atribuut. 
[MethodImpl(MethodImplOptions.Synchronized)]
public void SomeMethod()
 // do stuff
Detailsus.
Enne lukkude detailsusega tutvumist tuleb mõista kolme lukkude kontseptsiooni:
Sünkroniseeritavate lukkude arvu valimisel tuleb leida tasakaal lukustuskoormuse vähendamise ja lukustuskonkurentsi vähendamise vahel.
Luku oluline omadus on selle "detailsus" . Granulaarsus on mõõt andmete hulga kohta, mida lukk kaitseb. Üldiselt vähendab jämeda detailsuse valimine (väike arv lukke, millest igaüks kaitseb suurt andmesegmenti) "lukustuskoormust", kui kaitstud andmetele pääseb juurde üks protsess, kuid halvemat jõudlust, kui mitu protsessi töötab samaaegselt. See on tingitud suurenenud "lukustusvaidlusest" . Mida jämedam on lukk, seda suurem on tõenäosus, et see peatab mitteseotud protsessi jätkumise. Seevastu peene detailsuse kasutamine (suurem arv lukke, millest igaüks kaitseb üsna väikest andmemahtu) suurendab lukkude endi üldkulu, kuid vähendab lukkude omavahelist konkurentsi. Granuleeritud lukustus, kus iga protsess peab hoidma mitut lukku ühisest lukkude komplektist, võib luua peeneid lukusõltuvusi. See peensus võib suurendada võimalust, et programmeerija tekitab teadmatult "ummikseisu" .[ "viide vajalik" ]
Näiteks andmebaasi haldussüsteemis võib lukk kaitsta kahaneva detailsuse järjekorras osa väljast, välja, kirjet, andmelehte või tervet tabelit. Jämedateralisus, näiteks tabelilukkude kasutamine, annab tavaliselt parima jõudluse ühe kasutaja puhul, samas kui peeneteralisus, näiteks kirjete lukud, annab parima jõudluse mitme kasutaja puhul.
Andmebaasi lukud.
Andmebaasi lukke saab kasutada tehingute sünkroonsuse tagamise vahendina. st tehingute samaaegsel töötlemisel (tehingute põimimisel) tagab kahefaasiliste lukkude kasutamine, et tehingu samaaegne täitmine osutub samaväärseks tehingute järjestikuse järjestusega. Andmebaaside lukustamise kahetsusväärseks kõrvalmõjuks muutuvad aga ummikseisud. Pattiseisud ennetatakse kas tehingute vahelise lukustusjärjekorra eelnevalt määramisega või tuvastatakse ootegraafikute abil. Andmebaasi sünkroonsuse lukustamise alternatiiv ummikseisude vältimiseks hõlmab täielikult järjestatud globaalsete ajatemplite kasutamist.
Andmebaasis mitme samaaegse kasutaja toimingute haldamiseks kasutatakse mehhanisme – eesmärk on vältida kaduma läinud värskendusi ja määrdunud lugemisi. Lukustamist on kahte tüüpi: "pessimistlik" ja "optimistlik" .
 Kus pessimistlikku lukustust kasutada: seda kasutatakse peamiselt keskkondades, kus on suur andmekonkurents (kasutajate päringute arv andmebaasisüsteemile igal ajahetkel); kus andmete lukustuste abil kaitsmise kulud on väiksemad kui tehingute tagasipööramise kulud samaaegsuskonfliktide korral. Pessimistlikku samaaegsust on kõige parem rakendada siis, kui lukustusajad on lühikesed, näiteks kirjete programmilise töötlemise puhul. Pessimistlik samaaegsus nõuab püsivat ühendust andmebaasiga ja see ei ole skaleeritav valik, kui kasutajad andmetega suhtlevad, kuna kirjed võivad olla suhteliselt pikaks ajaks lukus. See ei sobi veebirakenduste arendamiseks.
 Kus kasutada optimistlikku lukustust: see sobib keskkondades, kus andmete pärast on vähe konkurentsi või kus on vaja ainult lugemisõigust andmetele. Optimistlikku samaaegsust kasutatakse laialdaselt. NET mobiilsete ja ühenduseta rakenduste vajaduste rahuldamiseks , kus andmeridade lukustamine pikemaks ajaks oleks teostamatu. Samuti nõuab kirjete lukkude haldamine püsivat ühendust andmebaasiserveriga, mis pole lahtiühendatud rakendustes võimalik.
Nendel peamistel lukustustüüpidel on mitu variatsiooni ja täiustust, millel on vastavad blokeerimiskäitumise variatsioonid. Kui esimene lukk blokeerib teise luku, nimetatakse kahte lukku "ühildumatuteks" ; vastasel juhul on lukud "ühilduvad" . Sageli esitatakse tehnilises kirjanduses interaktsioone blokeerivad lukutüübid "lukkude ühilduvuse tabelina" . Järgnev on näide levinumate ja peamiste lukutüüpide kohta:
Kommentaar: Mõnes publikatsioonis on tabeli kirjed lihtsalt märgitud kui „ühilduv“ või „ühildumatu“ või vastavalt „jah“ või „ei“. 
Puudused.
Lukustuspõhisel ressursikaitsel ja lõimede/protsesside sünkroniseerimisel on palju puudusi:
Mõned samaaegsuse kontrolli strateegiad väldivad mõnda või kõiki neid probleeme. Näiteks lehter või serialiseerivad märgid aitavad vältida suurimat probleemi: ummikseisu. Lukustamise alternatiivide hulka kuuluvad mitteblokeerivad sünkroniseerimismeetodid, näiteks lukuvabad programmeerimistehnikad ja tehingumälu . Sellised alternatiivsed meetodid nõuavad aga sageli, et tegelikud lukustusmehhanismid rakendataks operatsioonisüsteemi tarkvara fundamentaalsemal tasemel. Seega võivad need "rakendustasandi" vaid lukkude rakendamise üksikasjadest vabastada, kusjuures eespool loetletud probleemidega tuleb ikkagi rakenduse tasandil tegeleda.
Enamasti sõltub korrektne lukustamine sellest, kas protsessor pakub aatomikäskude voo sünkroniseerimise meetodit (näiteks elemendi lisamine või kustutamine torujuhtmesse nõuab, et kõik samaaegsed toimingud, mis vajavad teiste elementide lisamist või kustutamist torujuhtmes, peatataks mälusisu manipuleerimise ajal, mis on vajalik konkreetse elemendi lisamiseks või kustutamiseks). Seega võib rakendus olla sageli töökindlam, kui see tunneb ära operatsioonisüsteemile pandud koormuse ja suudab viisakalt ära tunda võimatute nõudmiste teatamise.[ "viide vajalik" ]
Kompositsiooni puudumine.
Üks lukupõhise programmeerimise suurimaid probleeme on see, et "lukud ei komponeeru ": väikeseid ja korrektseid lukupõhiseid mooduleid on raske ühendada sama korrektseteks suuremateks programmideks ilma mooduleid muutmata või vähemalt nende sisemust teadmata. Simon Peyton Jones ( tarkvara tehingumälu pooldaja) toob järgmise näite pangandusrakendusest: kujunda klass , mis võimaldab mitmel samaaegsel kliendil raha kontole sisse või välja kanda ning annab algoritmi raha ühelt kontolt teisele ülekandmiseks.
Probleemi esimese osa lukupõhine lahendus on:
 klassi konto:
 liikme saldo: täisarv
 liikme mutex: Lukusta
 meetod deposiit(n: täisarv)
 mutex.lock()
 tasakaal ← tasakaal + n
 mutex.unlock()
 meetod tagasivõtmine(n: täisarv)
 sissemakse(−n)
Probleemi teine osa on palju keerulisem. A "Järjestikuste programmide jaoks" õige oleks
 funktsiooniülekanne (from: Konto, to: Konto, summa: Täisarv)
 alates.väljamakse(summa)
 sissemakse(summa)
Samaaegses programmis on see algoritm vale, sest kui üks lõim on poole peal , teine võib täheldada olekut, kus  on esimeselt kontolt maha võetud, kuid teisele kontole mitte veel laekunud: raha on süsteemist kadunud. Selle probleemi saab täielikult lahendada ainult siis, kui enne kummagi konto muutmist lukustatakse need, kuid sel juhul tuleb lukud paigutada mingi suvalise globaalse järjestuse järgi, et vältida ummikseisu:
 funktsiooniülekanne (from: Konto, to: Konto, summa: Täisarv)
 kui alates &lt; kuni "// lukkude suvaline järjestus"
 alates.lukust()
 lukustama()
 muu
 lukustama()
 alates.lukust()
 alates.väljamakse(summa)
 sissemakse(summa)
 alates.unlock()
 avama()
See lahendus muutub keerulisemaks, kui kaasatud on rohkem lukke ja  peab teadma kõigi lukkude kohta, seega ei saa neid peita .
Keeletugi.
Programmeerimiskeeled erinevad sünkroonimise toe poolest:
Mutexid vs. semafoorid.
Mutex on lukustusmehhanism, mis mõnikord kasutab sama põhirakendust kui binaarne semafor. Need erinevad aga kasutusviisi poolest. Kui binaarset semafoori võib kõnekeeles nimetada mutexiks, siis tõelisel mutexil on spetsiifilisem kasutusjuhtum ja määratlus, kuna ainult see ülesanne, mis mutexi lukustas, peaks selle avama. Selle piirangu eesmärk on lahendada mõned semaforide kasutamise võimalikud probleemid:
Prioriteedi ümberpööramine: kui mutex teab, kes selle lukustas ja peaks selle avama, on võimalik selle ülesande prioriteetsust edendada alati, kui kõrgema prioriteediga ülesanne hakkab mutexil ootama.
Ülesande enneaegne lõpetamine: Muteksid võivad pakkuda ka kustutamise turvalisust, kui mutexi sisaldavat ülesannet ei saa kogemata kustutada. [vajalik tsitaat] (See on ka kulu; kui mutex võib takistada ülesande taaskasutamist, peab prügikorjaja mutexi jälgima.)
Lõpetamise ummikseisu: kui mutexi hoidmise ülesanne mingil põhjusel lõpeb, võib OS vabastada selle tingimuse mutexi ja signaali ooteülesanded.
Rekursiooni ummik: ülesandel on lubatud lukustada uuesti sisenev mutex mitu korda, kuna see avab selle sama palju kordi.
Juhuslik vabastamine: Mutexi vabastamisel tekib viga, kui vabastamisülesanne ei ole selle omanik.