Problema cititorilor și a scriitorilor (Readers - Writers)

Avem o zonă de memorie asupra căreia au loc mai multe acțiuni de citire și de scriere. Această zonă de memorie este partajată de mai multe thread-uri, care sunt de două tipuri: cititori (care execută acțiuni de citire din zona de memorie) și scriitori (care execută acțiuni de scriere în zona de memorie).

În această privință avem niște constrângeri:

• un scriitor poate scrie în zona de memorie doar dacă nu avem cititori care citesc din zona respectivă în același timp și dacă nu avem alt scriitor care scrie în același timp în aceeași zonă de memorie.
• un cititor poate să citească în zona de memorie doar dacă nu există un scriitor care scrie în zona de memorie în același timp, însă putem să avem mai mulți cititori care citesc în paralel în același timp din aceeași zonă de memorie.

Pentru această problemă avem două soluții:

• folosind excludere mutuală, cu prioritate pe cititori
• folosind sincronizare condiționată, cu prioritate pe scriitori

Soluția cu excludere mutuală

Folosind această soluție, un cititor nu va aștepta ca ceilalți cititori să termine de citit zona de memorie, chiar dacă avem un scriitor care așteaptă. Un scriitor poate să aștepte foarte mult, în caz că sunt foarte mulți scriitor, fapt ce poate duce la un fenomen numit writer's starvation.

De asemenea, nu poate să intre un scriitor cât timp există deja un scriitor care scrie în zona de memorie partajată.

Pseudocod:

// numărul de cititori care citesc simultan din resursa comună
int readers = 0; 

// mutex (sau semafor) folosit pentru a modifica numărul de cititori
mutex mutexNumberOfReaders; // sau semaphore mutexNumberOfReaders(1);

// semafor (sau mutex) folosit pentru protejarea resursei comune
semaphore readWrite(1); // sau mutex readWrite

reader (int id) {
    while (true)
        mutexNumberOfReaders.lock();
	    readers = readers + 1;
        // dacă e primul cititor, atunci rezervăm zona de memorie încât să nu intre niciun scriitor
	    if (readers == 1) {
	        readWrite.acquire(); 
        };
	    mutexNumberOfReaders.unlock();
	
        // citește din resursa comună;
		
	    mutexNumberOfReaders.lock();
	    readers = readers - 1;
        // dacă e ultimul cititor, eliberăm zona de de memorie din care s-a citit
	    if (readers == 0) {
	        readWrite.release();
	    }

	    mutexNumberOfReaders.unlock();
    }
}

writer (int id) {
    while (true) {
        // intră scriitorul în resursa comună
        readWrite.acquire();
        
        // scrie în resursa comună;
	
        // scriitorul eliberează resursa
        readWrite.release();
    }
}

Soluția cu sincronizare condiționată

Folosind această soluție, niciun cititor nu va intra în zona de memorie partajată cât timp există un scriitor care scrie în zona de memorie. De asemenea, nu poate să intre alt scriitor cât timp există un scriitor care se află în zona de memorie partajată.

Pseudocod:

// cititori care citesc din zona de memorie
int readers = 0;
// scriitori care scriu în zona de memorie
// (va fi doar unul, nu pot fi mai mulți scriitori care scriu simultan)
int writers = 0;

int waiting_readers = 0; // cititori care așteaptă să intre în zona de memorie
int waiting_writers = 0; // scriitori care așteaptă să intre în zona de memorie

// semafor folosit pentru a pune scriitori în așteptare, dacă avem un scriitor
// sau unul sau mai mulți cititori în zona de memorie (zona critică)
semaphore sem_writer(0);

// semafor folosit pentru a pune cititori în așteptare dacă avem un scriitor care scrie în zona de memorie
// sau dacă avem scriitori în așteptare (deoarece ei au prioritate față de cititori)
semaphore sem_reader(0);

// semafor folosit pe post de mutex pentru protejarea zonei de memorie (zona critică)
semaphore enter(1); 

reader (int id) {
    while(true) {
        enter.acquire();

        // dacă avem cel puțin un scriitor care scrie în resursa comună
        // sau dacă avem un scriitor în așteptare, cititorul așteaptă
	    if (writers > 0 || waiting_writers > 0) {
	        waiting_readers++;
	        enter.release();
	        sem_reader.acquire();
	    }

        readers++;
	    
        if (waiting_readers > 0) {
            // a venit încă un cititor în resursa comună,
            // ieșind din starea de așteptare
	    
            waiting_readers--;
	        sem_reader.release();
	    } else if (waiting_readers == 0) {
	        enter.release();
	    }

	    // citește din zona partajată
	    enter.acquire();
        readers--;
        
        if (readers == 0 && waiting_writers > 0) {
	        waiting_writers--;
	        sem_writer.release();
	    } else if (readers > 0 || waiting_writers == 0) {
	        enter.release();
	    }
    }
}

writer (int id) {
    while(true) {
        enter.acquire();
		
	    if (readers > 0 || writers > 0) {
	        waiting_writers++;
	        enter.release();
	        sem_writer.acquire();
	    }

	    writers++;

	    enter.release();
	
        // scrie în zona partajată
	
        enter.acquire();

	    writers--;
	    if (waiting_readers > 0 && waiting_writers == 0) {
	        waiting_readers--;
	        sem_reader.release();
	    } else if (waiting_writers > 0) {
	        waiting_writers--;
	        sem_writer.release();
	    } else if (waiting_readers == 0 && waiting_writers == 0) {
	        enter.release();
	    }
    }
}