Zámek (informatika)

Z Wikipedie, otevřené encyklopedie

Zámek je v informatice označení synchronizačního primitiva pro zajištění výhradního přístupu k systémovým prostředkům (místo v operační paměti, vstupně-výstupní porty nebo jiný hardware připojený k počítači) ve víceúlohovém prostředí, kde tak brání souběhu. Zámky jsou používány jak v případě, že dochází k cyklickému přepínání mezi běžícími úlohami, tak při skutečně paralelním běhu úloh ve víceprocesorových systémech. Typické je použití v multithreadových programech, například v Javě.

Druhy

Obecně, zámky jsou dobrovolné zámky, kde každé vlákno spolupracuje tím, že získá zámek před přístupem do příslušných dat. Některé systémy také zavádějí povinné zámky, kde se k zamčenému zdroji pokouší neoprávněný přístup a kde se bude entita snažit získat výjimku (zvláštní podmínky, které mění normální běh programu) pro přístup.

Binární semafor je nejjednodušším typem zámku. Pokud jde o přístup k datům, nerozlišuje se mezi sdílenými (pouze pro čtení) nebo exkluzivními (čtení i zápis) režimy. Ostatní typy poskytují sdílený režim, kde několik vláken může získat sdílený zámek pro přístup k datům, která jsou určena pouze pro čtení. Jiné druhy, které jsou exkluzivní, intend-to-exclude (v úmyslu vyloučit), a intend-to-upgrade (v úmyslu aktualizovat) jsou také široce uplatňovány.

Nezávisle na druhu výše zvoleného zámku, zámky mohou být klasifikovány podle toho, co se stane, když strategie zámku brání vláknu v postupu. Většina zámkem blokovaných vláken se dožaduje zámku, dokud není povolen přístup k zamčenému zdroji. Spinlock je zámek, kde vlákno jednoduše čeká ("točí se"), dokud nebude zámek k dispozici. Toto je velmi efektivní, pokud jsou vlákna blokována jen na krátkou dobu, protože tak se vyhne režii operačního systému, procesu přeplánování. Je plýtvání, když se zámek používá dlouhou dobu.

Zámky typicky vyžadují hardwarovou podporu pro účinnou realizaci. Tohle obvykle má podobu jednoho nebo více atomických (nedělitelných) instrukcí jako je "test-and-set", "fetch-and-add" nebo "compare-and-swap". Tyto instrukce umožňují jedinému procesu otestovat, zda je zámek volný a pokud volný je, proces získá zámek v jedné atomické (nedělitelné) operaci.

Jednoprocesorové architektury mají možnost využít nepřetržitou sekvenci instrukcí, pomocí speciálních instrukcí nebo instrukční předpony mohou dočasně zakázat přerušení, tato technika ale nefunguje pro víceprocesorový systém se sdílenou pamětí. Patřičná podpora pro zámky ve víceprocesorových prostředích může vyžadovat poměrně komplexní hardwarovou a nebo softwarovou podporu, která může mít značné problémy se synchronizací.

Důvodem nedělitelné operace je z důvodu nutné souběžnosti, kde více než jednu úlohu vykoná stejnou logikou. Například tento následující kód v C:

if (lock == 0) lock = myPID; /* pokud je zámek prázdný – nastaví se */

U výše uvedeného příkladu není záruka, že úkol měl zámek k dispozici, protože více než jeden úkol může testovat zámek ve stejnou dobu. Vzhledem k tomu, že úlohy zjistí, že je zámek prázdný, budou se oba úkoly snažit nastavit zámek, aniž by věděly, že druhý se ho pokouší nastavit také. Dekkrův nebo Petersonův algoritmus je možná náhrada, pokud operace nedělitelného zámku není k dispozici.

Neopatrné používání zámků může mít za následek deadlock (mrtvý bod) nebo livelock. Deadlock nastane, když proces drží zámek a pak se pokusí získat zámek druhý. Pokud je druhý zámek už používán jiným procesem, bude první proces zablokován. Pokud se druhý proces pokusí získat zámek v držení prvního procesu, vznikne systémový „deadlock“: oba procesy čekají a další výpočet se neprovádí. Několik strategií lze použít k zabránění nebo k navrácení se z deadlocku, a to jak při návrhu systému, tak při běhu. (Nejběžnější je standardizovat zámek pořízením sekvence tak, že kombinace vzájemně závislých zámků jsou vždy získávány a uvolňovány v přesně vymezeném "kaskádovém" pořadí.)

Granularita

Ještě před představením granularity zámku je třeba pochopit tři pojmy o zámku.

  • režie zámku: Zvláštní zdroje pro používání zámků, jako paměťový prostor přidělený pro zámky, procesorový čas pro inicializaci a ničení zámků a čas pro získání nebo uvolnění zámků. Čím více zámků program používá, tím větší je režie spojená s užíváním.
  • kolize zámku: K tomu dochází vždy, když se jeden proces nebo vlákno pokusí získat zámek v držení jiného procesu nebo vlákna. Podrobnější dostupnost zámků, méně pravděpodobné, že proces/vlákno bude žádat zámek v držení jiného procesu. (Například zamykání jednoho řádku nikoli celé tabulky nebo zamykání buňky spíš než celý řádek.)
  • deadlock: Situace, kdy každý ze dvou (nebo více) úkolů čeká na zámek, který drží jiný úkol. Pokud se něco neudělá, budou dva úkoly čekat věčně.

Takže je tam kompromis mezi klesající režií zámku a klesající kolizí zámku při výběru počtu zámků v synchronizaci.

Důležitou vlastností zámku je jeho granularita. Granularita je míra množství dat, které zámek chrání. Obecně platí, že výběr hrubé granularity (malé množství zámků z nichž každý chrání velký segment dat) vede k menší režii zámku když jeden proces přistupuje k chráněným datům, ale horší výkon když běží více procesů zároveň. To je z důvodu zvýšené kolize zámku. Čím hrubší zámek, tím vyšší je pravděpodobnost, že zámek bude zastaven nezávislým procesem od postupu. Naopak použitím jemné granularity (větší množství zámků z nichž každý chrání poměrně malé množství dat) se zvyšuje režie samotného zámku, ale snižuje se kolize zámku. Více zámků také zvýší riziko deadlocku.

V databázovém systému zámek může například chránit: pořadí rostoucí granularity, část z pole, pole, záznam, datovou stránku nebo celou tabulku. Hrubá granularita, jako při použití tabulkových zámků má tendenci dát nejlepší výkon jednomu uživateli, zatímco jemná granularita jako je záznam zámků má tendenci dát nejlepší výkon více uživatelům.

Databáze zámků

Databáze zámků může být použita jako prostředek k zajištění transakce synchronicity. To je při souběžném zpracování transakcí (prokládání transakcí), použitím 2 fází zámků se zajišťuje, že souběžné provádění transakcí odpovídá některým sériově řazeným transakcím. Alternativa k zamykání pro databázi synchronicity a zároveň zamezení deadlock vyžaduje využití úplně uspořádané časové značky.

Jsou tam mechanismy zaměstnané řízením činnosti více současných uživatelů v databázi – účelem je zabránit ztracení aktualizací a špatnému čtení. Tyto 2 typy zamykání jsou Pesimistické a Optimistické zamykání.

  • Pesimistické zamykání: Uživatel, který čte záznam s úmyslem jeho aktualizace, na záznam umístí exkluzivní zámek, aby se ostatním uživatelům zabránilo manipulování s ním. To znamená, že se souborem nemůže nikdo manipulovat, dokud ho zámek neuvolní. Nevýhodou je, že uživatelé mohou být uzamčeny po velmi dlouhou dobu, čímž se zpomaluje celková odezva systému a způsobuje frustraci.
    • Kde se používá Pesimistické zamykání: Toto se používá hlavně v prostředích, kde přístup k datům (mnoho uživatelů žádá přístup do databáze ve stejnou dobu) je velký; Tam, kde jsou náklady na ochranu dat přes zámky menší než náklady na vrácení transakcí, když souběžně dojde ke konfliktu. Pesimistickou souběžnost je nejlépe implementovat, když časy zámku budou krátké, stejně jako programové zpracování záznamů. Pesimistická souběžnost vyžaduje trvalé připojení k databázi, není možnost škálování, když uživatelé upravují data, protože záznamy mohou být uzamčeny po relativně dlouhou dobu. Není vhodné pro použití při vývoji webových aplikací.
  • Optimistické zamykání: Umožňuje více uživatelům přístup k databázi zároveň, zatímco systém udržuje původní kopii pro každého uživatele. Když chce uživatel aktualizovat záznam, aplikace zjistí, jestli jiný uživatel změnil záznam od posledního čtení. Aplikace porovná původní kopii uloženou v paměti a záznam v databázi a ověří všechny změny provedené v záznamu. Jakékoli rozdíly mezi původní kopií a databázovým záznamem naruší souběžnost pravidla a tím způsobí, že systém nepřihlédne k žádné žádosti aktualizace. Je vygenerována chybová zpráva a uživatel je vyzván k procesu znovu aktualizace. Zlepšuje výkon databáze tím, že redukuje množství požadovaných zamknutí, čímž se sníží zátěž na databázový server. Pracuje efektivně s tabulkami, které vyžadují omezené aktualizace od uživatelů, které jsou blokovány. Nicméně, některé aktualizace mohou selhat. Nevýhodou je neustálá aktualizace nedostatků z důvodu vysokého množství aktualizací ze strany několika uživatelů současně – to může být pro uživatele frustrující.
    • Kde se používá Optimistické zamykání: Používá se v prostředích, kde je nízký spor o data nebo tam, kde je přístup k datům pouze pro čtení. Také udržování zamknutých záznamů vyžaduje trvalé připojení k databázovému serveru, který není možné odpojit aplikačně.

Reference

V tomto článku byl použit překlad textu z článku Lock (computer science) na anglické Wikipedii.