Problém čtenář-zapisovatel je jedním z nejdůležitějších problémů paralelního programování . Je to formulováno takto:
Existuje paměťová oblast , kterou lze číst a zapisovat. Má k němu přístup několik vláken , zatímco tolik vláken, kolik chtějí, může současně číst, ale pouze jedno může zapisovat. Jak zajistit takový přístupový režim?
Vystačíte si s obyčejným mutexem , ale to není optimální - paměť počítače je obvykle navržena tak, aby ji mohlo volně číst a zapisovat několik vláken (jediný problém je, že není zaručeno, že se během zpracování proměnná náhle nezmění) . Tento problém má několik možností, různých a řešení. Komu dát přednost – čtenáři nebo spisovateli – zůstává na programátorovi.
Když je paměť otevřena pro čtení, poskytněte čtenářům neomezený přístup. Spisovatelé mohou čekat, jak dlouho chtějí.
Jakmile se objevil alespoň jeden spisovatel, nikdo další dovnitř nesměl. Všechny ostatní mohou být nečinné.
Ukázkové řešení [1] :
Globální celá čísla readcount=0, writecount=0; Globální mutexy mutex1, mutex2, w, r ČTENÁŘ nájemce mutex1.enter readcount = readcount + 1 pokud readcount=1 pak w.enter mutex1.nechat r.opustit ...čtení... mutex1.enter readcount = readcount - 1 pokud readcount = 0 pak w.leave mutex1.nechat SPISOVATEL mutex2.enter počet zápisů = počet zápisů + 1 pokud počet zápisů=1, pak r.zadejte mutex2.opustit w.enter ...píšeme... w.opustit mutex2.enter writecount = writecount - 1 pokud writecount = 0, pak r.leave mutex2.opustitVyhněte se prostojům. Jinými slovy: bez ohledu na akce ostatních vláken musí čtenář nebo pisatel překonat bariéru v konečném čase.
Jinými slovy, žádné vlákno (čtenář nebo zapisovač) by nemělo čekat příliš dlouho na získání zámku; funkce zachycení zámku by se měla po nějaké době, pokud selže zámek, vrátit s příznakem selhání zámku , aby vlákno nebylo nečinné a mohlo dělat jiné věci. Často je tento čas nulový: funkce zachycení, pokud zachycení není možné právě teď, se okamžitě vrátí.
Globální mutexy: no_writers, no_readers, counter_mutex Globální celá čísla: nreaders=0 Místní celá čísla: předchozí, aktuální SPISOVATEL: no_writers.enter no_readers.enter ... psaní .... no_writers.opustit no_readers.leave ČTENÁŘ: no_writers.enter counter_mutex.enter preve:= nreaders nreaders := nreaders + 1 pokud předchozí = 0, pak no_readers.enter counter_mutex.leave no_writers.opustit ...čtení... counter_mutex.enter nreaderst:= nreaders - 1; currente:= nreaders; pokud aktuální = 0, pak no_readers.leave counter_mutex.leave;C kód pro gcc gcc -o rw -lpthread -lm rewr.c
#include <pthread.h> #include <stdio.h> #include <math.h> #include <stdlib.h> #include <semafor.h> #define M 4 //počet WR #define N 3 //počet RE unsigned int iter ; //iterace sem_t accessM , readresM , orderM ; //sem. unsigned int čtenáři = 0 ; // Počet čtenářů přistupujících ke zdroji void * čtenář ( void * prem ) { int cislo1 =* ( int * ) prm ; int i = 0 , r ; pro ( i ; i < iter ; i ++ ) { if ( sem_wait ( & orderM ) == 0 ) printf ( "%d Reader %d ve frontě___________W%d \n " , i , num1 , num1 ); // Zapamatujte si naše pořadí příchodu sem_wait ( & readresM ); // Budeme manipulovat s čítačem čtenářů if ( čtenáři == 0 ) // Pokud aktuálně nejsou žádní čtenáři (jsme první)... sem_wait ( & accessM ); // ...žádá o výhradní přístup ke zdroji pro čtenáře čtenáře ++ ; // Všimněte si, že nyní existuje ještě jeden čtenář sem_post ( & orderM ); // Uvolnění pořadí příchodu semaforu (byli jsme obslouženi) sem_post ( & readresM ); // Pro tuto chvíli jsme dokončili přístup k počtu čtenářů printf ( "%d Reader %d________________W%d funguje \n " , i , num1 , num1 ); // Zde může čtenář libovolně číst zdroj r = 1 + rand () % 4 ; spánek ( r ); sem_wait ( & readresM ); // Budeme manipulovat s čítačem čtenářů čtenáři -- ; // Odcházíme, je o jednoho čtenáře méně if ( čtenáři == 0 ) // Pokud aktuálně nečte více čtenářů... sem_post ( & accessM ); // ...uvolněte exkluzivní přístup ke zdroji sem_post ( & readresM ); // Pro tuto chvíli jsme dokončili přístup k počtu čtenářů } } void * spisovatel ( void * prem ) { int num2 =* ( int * ) prm ; int j = 0 , r ; for ( j ; j < iter ; j ++ ) { if ( sem_wait ( & orderM ) == 0 ) printf ( "%d Writer %d ve frontě__________P%d \n " , j , num2 , num2 ); // Zapamatujte si naše pořadí příjezdu sem_wait ( & accessM ); // Žádost o výhradní přístup ke zdroji sem_post ( & orderM ); // Uvolnění pořadí příchodu semaforu (byli jsme obslouženi) printf ( "%d Writer %d________________P%d \n " , j , num2 , num2 ); // Zde může autor libovolně upravit zdroj r = 1 + rand () % 4 ; spánek ( r ); sem_post ( & accessM ); // Uvolnění výhradního přístupu ke zdroji } } void main () { pthread_t threadRE [ N ]; pthread_t threadWR [ M ]; sem_init ( & accessM , 0 , 1 ); sem_init ( & readresM , 0 , 1 ); sem_init ( & orderM , 0 , 1 ); printf ( "Zadejte počet iterací: " ); scanf ( "%d" , & iter ); printf ( "FRONTA/PROVEDENÍ Iter \n " ); int i ; pro ( i = 0 ; i < M ; i ++ ) { pthread_create ( & ( threadWR [ i ]), NULL , Writer , ( void * ) & i ); } pro ( i = 0 ; i < N ; i ++ ) { pthread_create ( & ( threadRE [ i ]), NULL , reader , ( void * ) & i ); } pro ( i = 0 ; i < N ; i ++ ) { pthread_join ( threadRE [ i ], NULL ); } pro ( i = 0 ; i < M ; i ++ ) { pthread_join ( threadWR [ i ], NULL ); } sem_destroy ( & accessM ); sem_destroy ( & readresM ); sem_destroy ( & orderM ); }Mnoho čtenářů XOR jeden spisovatel (XOR-exkluzivní nebo ) je často považován za invariantu tohoto problému . To není pravda, protože situace, kdy nejsou čtenáři ani spisovatelé, je také správná.
Invariant lze vyjádřit následujícím výrokem:
autoři == 0 NEBO autoři == 1 A čtenáři == 0kde spisovatelé je počet spisovatelů, čtenáři je počet čtenářů.
Jednoduchý mutex chránící paměť často není optimální. Například v online hře se seznam herních místností mění jen zřídka – když se některý z hráčů rozhodne otevřít novou místnost, například jednou za pár sekund. Během jedné sekundy se to čte desítkykrát a nemá smysl k tomu řadit klienty .
Podobné mechanismy (tzv. zamykání čtení a zápisu ) existují v mnoha programovacích jazycích a knihovnách. Například.