Problém čtenářů a písařů

Problém čtenářů a písařů, také známý jako problém sdíleného a exkluzivního zamykání, patří ke klasickým výpočetním problémům při řešení souběžnosti, kterými se zabývá informatika. Tento problém se vyskytuje v situacích, kdy více vláken v roli čtenáře nebo písaře musí přistupovat ke stejné sdílené paměti, aby do ní zapisovaly nebo z ní četly. Přitom je potřeba zaručit integritu dat, která může být porušena souběhem čtenáře a písaře nebo dvou písařů. Čtenářům a písařům tedy nesmí být umožněno, aby si měnili data „pod rukama“.

Řešení problému

Triviální řešení

Sdílená data je možné ochránit jedním binárním zámkem (například mutexem) tak, aby žádná dvě vlákna nemohla přistupovat k datům ve stejný okamžik. Toto řešení však není optimální, protože pokud čtenář Č₂ zažádá o přístup k paměti v dobu, kdy čtenář Č₁ přístup již má, bylo by hloupé nechat čtenáře Č₂ čekat, než Č₁ dočte, protože čtenáři data nemění, a jejich integrita tedy porušena být nemůže.

Řešení s preferencí čtenářů

Triviální řešení lze vylepšit o omezení, že pokud je čtenáři umožněno číst, žádný další příchozí čtenář nesmí být nechán čekat. Čtenářům je tak umožněno, aby četli zároveň.

Řešení s preferencí písařů

Pokud může být požadavků na čtení mnoho a jejich vyřizování trvá dlouho, není řešení s preferencí čtenářů optimální. Čtenáři totiž mohou svými časově překrývajícími se požadavky udržovat paměť stále zamčenou pro čtení a písařům se ji nemusí nikdy podařit uzamknout pro zápis. Tak může dojít k takzvanému hladovění písařů.

Hladovění písařů je možné vyloučit tím, že se požadavky na zamknutí pro zápis budou preferovat před požadavky na zamknutí pro čtení. Pokud se objeví požadavky pro zápis, pozdrží se všechny požadavky pro čtení tak, aby paměť byla zamčena pro zápis ihned po odemčení zámku.

Vyřešením problému hladovění písařů však vznikl problém možného hladovění čtenářů. Pokud přichází mnoho písařů, kteří zapisují dlouho, čtenáři se nemusí nikdy dostat na řadu.

Kompromisní řešení

Pro odstranění problémů s hladověním čtenářů nebo písařů lze udělat kompromis. Přidá se omezení, že žádné vlákno by nemělo být necháno hladovět. To znamená, že čekání na uzamčení sdílených dat skončí v omezeném čase. To se dá vyřešit tak, že někdy budou zdrženi čtenáři, i když je zámek zamčen pro čtení, nebo písaři budou zdrženi více, než je opravdu nutné.

Související články

Externí odkazy