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.

lock(this) 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:

 Luku lisakulu : lukkude kasutamiseks vajalikud lisaressursid, näiteks lukkudele eraldatud mäluruum, protsessori aeg lukkude initsialiseerimiseks ja hävitamiseks ning aeg lukkude hankimiseks või vabastamiseks. Mida rohkem lukke programm kasutab, seda suurem on kasutamisega seotud üldkulu;
 Lukustusvaidlus : see juhtub alati, kui üks protsess või niit üritab hankida teise protsessi või niidi poolt hoitavat lukku. Mida peeneteralisemad on saadaolevad lukud, seda väiksem on tõenäosus, et üks protsess/lõim taotleb teise poolt hoitavat lukku. (Näiteks rea lukustamine kogu tabeli asemel või lahtri lukustamine kogu rea asemel);
 Pattiseis : olukord, kus vähemalt kaks ülesannet ootavad lukku, mida hoiab teine ülesanne. Kui midagi ette ei võeta, jäävad need kaks ülesannet igaveseks ootama.

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 .[ <span title="This claim needs references to reliable sources. (July 2011)">viide vajalik</span> ]

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 .

 Pessimistlik lukustus : kasutaja, kes loeb kirjet kavatsusega seda uuendada, paneb kirjele eksklusiivse luku, et takistada teistel kasutajatel sellega manipuleerimist. See tähendab, et keegi teine ei saa seda kirjet manipuleerida enne, kui kasutaja luku vabastab. Negatiivne külg on see, et kasutajad võivad olla väga pikaks ajaks lukustatud, mis aeglustab süsteemi üldist reageerimisvõimet ja põhjustab frustratsiooni.

 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.

 Optimistlik lukustus : see võimaldab mitmel samaaegsel kasutajal andmebaasile juurde pääseda, samal ajal kui süsteem säilitab iga kasutaja esialgse lugemise koopia. Kui kasutaja soovib kirjet värskendada, kontrollib rakendus, kas mõni teine kasutaja on kirjet pärast viimast lugemist muutnud. Rakendus teeb seda, võrreldes mälus olevat esialgset lugemist andmebaasi kirjega, et kontrollida kirjes tehtud muudatusi. Kõik lahknevused esialgse lugemise ja andmebaasi kirje vahel rikub samaaegsuse reegleid ja seetõttu ignoreerib süsteem kõiki värskendustaotlusi. Kuvatakse veateade ja kasutajal palutakse värskendusprotsessi uuesti alustada. See parandab andmebaasi jõudlust, vähendades vajaliku lukustuse hulka, vähendades seeläbi andmebaasiserveri koormust. See töötab tõhusalt tabelitega, mis vajavad piiratud värskendusi, kuna ükski kasutaja pole lukustatud. Siiski võivad mõned uuendused ebaõnnestuda. Negatiivne külg on pidevad uuenduste tõrked, mis on tingitud suurest hulgast uuendustaotlustest mitmelt samaaegselt kasutajalt – see võib kasutajatele olla frustreeriv.

 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:
+Lukkude ühilduvuse tabel Luku tüüp lugemislukk kirjutuslukk lugemislukk ✔ X kirjutuslukk X X

 ✔ näitab ühilduvust
 X tähistab ühildumatust, st juhtumit, kus objektil olev esimest tüüpi lukk (vasakus veerus) blokeerib teist tüüpi luku (ülemises reas) omandamise samal objektil (teise tehingu poolt). Objektil on tavaliselt ootejärjekord (tehingutite kaupa) taotletud toiminguid koos vastavate lukkudega. Järjekorra esimene blokeeritud lukk toimingu jaoks saadakse kohe, kui olemasolev blokeeriv lukk objektilt eemaldatakse, ja seejärel käivitatakse vastav toiming. Kui järjekorras oleva toimingu lukk ei ole ühegi olemasoleva luku poolt blokeeritud (samal objektil võib samaaegselt olla mitu ühilduvat lukku), hangitakse see kohe.

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:

 Väide: mõned lõimed/protsessid peavad ootama, kuni lukk (või terve komplekt lukke) vabastatakse. Kui üks lukku hoidvatest lõimedest sureb, seiskub, blokeerub või satub lõpmatusse tsüklisse, võivad teised lukku ootavad lõimed lõputult oodata, kuni arvuti välja lülitatakse .
 Lisakulud: lukkude kasutamine lisab iga ressursile juurdepääsu puhul lisakulusid, isegi kui kokkupõrke tõenäosus on väga haruldane. (Siiski on igasugune selliste kokkupõrgete võimalus võidujooksu tingimus .)
 Silumine: lukkudega seotud vead on ajast sõltuvad ning võivad olla väga peened ja äärmiselt raskesti korratavad, näiteks ummikseisud .
 Ebastabiilsus: optimaalne tasakaal lukustuskulude ja lukustuskonkurentsi vahel võib olla probleemdomeenile (rakendusele) ainuomane ning tundlik disaini, teostuse ja isegi madala taseme süsteemiarhitektuuriliste muudatuste suhtes. Need saldod võivad rakenduse elutsükli jooksul muutuda ja kaasa tuua tohutuid muudatusi värskendamiseks (uuesti tasakaalustamiseks).
 Komponeeritavus: lukud on komponeeritavad (nt mitme samaaegse luku haldamine, et aatomiliselt kustutada objekt X tabelist A ja sisestada X tabelisse B) ainult suhteliselt keeruka (lisakoormusega) tarkvaratoe ja rakendusprogrammeerimise rangete konventsioonide täieliku järgimise korral.
 Prioriteedi inversioon : madala prioriteediga lõim/protsess, millel on ühine lukk, võib takistada kõrge prioriteediga lõimede/protsesside jätkamist. Prioriteedi pärimist saab kasutada prioriteedi inversiooni kestuse lühendamiseks. Prioriteedilae protokolli saab kasutada üheprotsessorilistes süsteemides, et minimeerida halvimal juhul prioriteedi inversiooni kestust ja vältida ummikseisu .
 Konvoeerimine : kõik teised lõimed peavad ootama, kui lukku hoidev lõim ajastuse tühistatakse ajalõigu katkestuse või lehekülje vea tõttu.

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.[ <span title="This claim needs references to reliable sources. (November 2013)">viide vajalik</span> ]

 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 < 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:

 Ada pakub kaitstud objekte, millel on nähtav kaitse alamprogrammidele või kirjetele lisaks ka kohtumiskokkuleppele.
 ISO/IEC C standard pakub standardset vastastikuse välistamise (lukud) rakenduste programmeerimisliidest (API) alates C11. Praegune ISO/IEC C++ standard toetab keermestamist alates C++11. OpenMP standardit toetavad mõned kompilaatorid ja see võimaldab kriitilisi sektsioone määrata pragmade abil. POSIX pthread API pakub lukutuge. Visual C++ pakub sünkroonitavate meetodite sünkroonimisatribuuti, kuid see on spetsiifiline Windowsi arhitektuuri ja Visual C++ kompilaatori COM-objektide jaoks. C ja C++ pääsevad hõlpsalt juurde mis tahes algse operatsioonisüsteemi lukustusfunktsioonile.
 C# pakub lock koodsõna lõimel, et tagada selle eksklusiivne juurdepääs ressursile.
 Visual Basic (.NET) pakub SyncLock koodsõna nagu C# lock koodsõna.
 Java pakub koodsõna synchronized, et lukustada koodiplokke, meetodeid või objekte ja teeke, mis sisaldavad samaaegsusekindlaid andmestruktuure.
 Objective-C pakub koodsõna @synchronized, et panna lukku koodiplokke ja lisaks pakub klasse NSLock, NSRecursiveLock, and NSConditionLock koos NSLocking protokolliga lukustamise jaoks.
 PHP pakub failidel põhinevat lukustamist lisaks Mutex klassile pthreads teegist.
 Python pakub madala tasemelist mutex mehhanismi koos Lock klassiga threading moodulist.
 ISO/IEC Fortran standard (ISO/IEC 1539-1:2010) pakub lock_type tuletatud tüüpi sisemises moodulis iso_fortran_env ja lock/unlock avaldusi alates Fortran 2008 versioonist.
 Ruby pakub madalatasemelist mutex objekti ja ei koodsõna.
 Rust pakub Mutex<T> struktuuri.
 x86 assembly language pakub LOCK eessõna teatud operatsioonides, et garanteerida nende aatomilisus.
 Haskell implementeerib lukustamist läbi muudetavate andmestruktuuride, mis on kutsutud nimega MVar, mis saab olla kas tühi või omada väärtust, tüüpiliselt viidet reussursile. Lõim, mis taha kasutada ressurssi ‘võtab’  MVar väärtuse, jättes selle tühjaks ning paneb selle tagasi kui ta on sellega lõpetanud . Kui proovite võtta tühjast MVar'ist ressurssi, blokeeritakse lõim, kuni ressurss on saadaval. Alternatiivina lukustamisele on olemas ka implementatsioon tarkvara tehingmälu rakendamisele.
 Go pakub madalatasemelist Mutex objekti tavateegis sync paketis. Seda saab kasutada koodiblokkide lukustamiseks, meetodide või objektide jaoks.

 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.

 Vaata ka 
 Kriitiline lõik
 Topeltkontrollitud lukustus
 Failide lukustamine
 Lukustus- ja ootamisvabad algoritmid
 Monitor (sünkroniseerimine)
 Vastastikune välistamine
 Lugemis-/kirjutamisluku muster

 Viited 

 Välislingid 
 Õpetus lüüside ja kriitiliste lõikude kohta

Kategooria:Ülevaatamata tõlgetega leheküljed
Kategooria:Informaatika