Problém čitateľa-zapisovateľa

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

V informatike, prvý a druhý problém čitatela-zapisovateľa sú príklady všeobecných výpočtových problémov. Dva problémy zaoberajúce sa situáciami v ktorom mnoho vlákien musí pristupovať v rovnaký okamih do spoločnej zdieľanej pamäti, niektoré čítanie a niektorého písania, s prirodzenou obmedzujúcou podmienkou, že proces nemôže pristúpiť k čítaniu alebo písaniu pokiaľ iný proces práve zapisuje. (Povolené pre dvoch čitateľov súčasne pristupujúcich do zdieľanej pamäte.) Zámka čitateľa-zapisovateľa je dátová štruktúra, ktorá rieši jeden alebo viacej problémov čitateľa-zapisovateľa.

Prvý problém čitateľa-zapisovateľa[upraviť | upraviť zdroj]

Predstavme si, že máme oblasť zdieľanej pamäte s obmedzujúcimi podmienkami popísanými vyššie. Zdieľané dáta je možné chrániť za pomoci mutex, z ktorých jasne žiadne vlákno nemôže pristúpiť k dátam v rovnaký čas ako iný zapisovateľ. Avšak, toto riešenie je suboptimálne, pretože nie je vylúčené, že čitateľ R1 mohol mať zámok a iný čitateľ R2 požiadal o prístup. To by mohlo byť zbytočné pre R2 čakať, dokým R1 dokončí čítanie aby R2 mohol sám čítať namiesto toho, aby čítal okamžite. Toto je motivácia prvého problému čitateľ-zapisovateľa, v ktorom je pridaná podmienka, že žiadny čitateľ by nemal čakať pokiaľ je zdieľanie práve otvorené pre čítanie. Toto sa tiež volá preferencia čitateľa.

Druhý problém čitateľa-zapisovateľa[upraviť | upraviť zdroj]

Predpokladajme, že máme oblasť zdieľanej pamäte chránenú pomocou mutex, ako je uvedené vyššie. Toto riešenie je tiež suboptimálne, pretože sa môže stať, že čitateľ R1 má zámok, zapisovateľ W čaká na zámok a čitateľ R2 žiada o prístup. To môže byť nevýhodné pre R2 preskočiť pred W a čítať okamžite, lebo ak sa to bude stávať dosť často, W sa nedostane k slovu a nebude zapisovať. Namiesto toho, W by mal začať čo najskôr. Toto je motivácia druhého problému čitateľ-zapisovateľa, v ktorom je pridaná podmienka, že žiaden zapisovateľ, ktorý už bol pridaný do radu nebude čakať dlhšie, než je to nevyhnutne potrebné. Toto sa tiež volá preferencia zapisovateľa.

Tretí problém čitateľ-zapisovateľa[upraviť | upraviť zdroj]

V skutočnosti, riešenia oboch problémov vedú k hladovaniu — v prvom probléme čitateľ-zapisovateľa môže hladovať zapisovateľ v rade, v druhom probléme čitateľ-zapisovateľa môže hladovať čitateľ. Z toho dôvodu, tretí problém čitateľ-zapisovateľa sa používa vtedy, keď je pridaná podmienka, že žiadne vlákno nesmie hladovať, teda operácia získavania zámku na zdieľané dáta bude vykoná v konečnom čase. Riešením tretieho problému čitateľ-zapisovateľa je občas nutnosť vyžadovať od čitateľa čakať napriek tomu, že je povolené čítanie dát a občas žiadať zapisovateľa čakať dlhšie, než je nevyhnutne nutné.

Pozri aj[upraviť | upraviť zdroj]