The task of reader-writers is one of the most important tasks of parallel programming . It is formulated like this:
There is a memory area that can be read and written. Several threads have access to it, while at the same time they can read as many streams as they wish, but only one can write. How to provide such access mode? |
You can get by with the usual mutex , but this is not optimal - computer memory, as a rule, is designed so that several threads can read and write it freely (the only problem is that there is no guarantee that the variable will not suddenly change during processing). This problem has several options, different and solutions. To give priority to the reader or writer remains for the programmer.
Content
The first task is about reader-writers (reader priority)
The task is formulated as follows:
While the memory is open for reading, give readers unhindered access. Writers can wait any time. |
The second task is about reader-writers (priority of the writer)
The task is formulated as follows:
As soon as at least one writer appeared, no more readers would be allowed. In this case, readers can stand idle. |
Approximate solution [1] :
Global integers readcount = 0, writecount = 0; Global mutexes mutex1, mutex2, w, r READER r.enter mutex1.enter readcount = readcount + 1 if readcount = 1 then w.enter mutex1.leave r.leave ... read ... mutex1.enter readcount = readcount - 1 if readcount = 0 then w.leave mutex1.leave WRITER mutex2.enter writecount = writecount + 1 if writecount = 1 then r.enter mutex2.leave w.enter ... write ... w.leave mutex2.enter writecount = writecount - 1 if writecount = 0 then r.leave mutex2.leave
The third task is about reader-writers (fair allocation of resources).
Avoid downtime. In other words: regardless of the actions of other streams, the reader or writer must pass the barrier in a finite time. |
Global Mutexes: no_writers, no_readers, counter_mutex Global integers: nreaders = 0 Local Integers: prev, current WRITER: no_writers.enter no_readers.enter no_writers.leave ... write ... no_readers.leave READER: no_writers.enter counter_mutex.enter prev: = nreaders nreaders: = nreaders + 1 if prev = 0 then no_readers.enter counter_mutex.leave no_writers.leave ... read ... counter_mutex.enter nreaders: = nreaders - 1; current: = nreaders; if current = 0 then no_readers.leave counter_mutex.leave;
C code for gcc gcc -o rw -lpthread -lm rewr.c
#include <pthread.h>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <semaphore.h>
#define M 4 // num of WR
#define N 3 // num of RE
unsigned int iter ; // iteration
sem_t accessM , readresM , orderM ; // sem.
unsigned int readers = 0 ; // Number of readers accessing the resource
void * reader ( void * prm )
{
int num1 = * ( int * ) prm ;
int i = 0 , r ;
for ( i ; i < iter ; i ++ )
{
if ( sem_wait ( & orderM ) == 0 ) printf ( "% d Reader% d in queue __________% d \ n " , i , num1 , num1 ); // Remember our order of arrival
sem_wait ( & readresM ); // We will manipulate the readers counter
if ( readers == 0 ) // If there are currently no readers (we came first) ...
sem_wait ( & accessM ); // ... requests exclusive access to the resource for readers
readers ++ ; // Note that there is now one more reader
sem_post ( & orderM ); // Release order of arrival semaphore (we have been served)
sem_post ( & readresM ); // We are done accessing the number of readers for now
printf ( "% d Reader% d ________________ H% d \ n " , i , num1 , num1 ); // Here you can read the resource
r = 1 + rand () % 4 ;
sleep ( r );
sem_wait ( & readresM ); // We will manipulate the readers counter
readers - ; // We are leaving, there is one less reader
if ( readers == 0 ) // If there are no more readers currently reading ...
sem_post ( & accessM ); // ... release exclusive access to the resource
sem_post ( & readresM ); // We are done accessing the number of readers for now
}
}
void * writer ( void * prm )
{
int num2 = * ( int * ) prm ;
int j = 0 , r ;
for ( j ; j < iter ; j ++ )
{
if ( sem_wait ( & orderM ) == 0 ) printf ( "% d Writer% d in queue __________ P% d \ n " , j , num2 , num2 ); // Remember our order of arrival
sem_wait ( & accessM ); // Request exclusive access to the resource
sem_post ( & orderM ); // Release order of arrival semaphore (we have been served)
printf ( "% d Writer% d ________________ P% d \ n " , j , num2 , num2 ); // Here you can write
r = 1 + rand () % 4 ;
sleep ( r );
sem_post ( & accessM ); // Release exclusive access to the resource
}
}
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 ( "Enter the number of iterations:" );
scanf ( "% d" , & iter );
printf ( "Iter QUEENING / PERFORMANCE \ n " );
int i ;
for ( i = 0 ; i < M ; i ++ )
{
pthread_create ( & ( threadWR [ i ]), NULL , writer , ( void * ) & i );
}
for ( i = 0 ; i < N ; i ++ )
{
pthread_create ( & ( threadRE [ i ]), NULL , reader , ( void * ) & i );
}
for ( i = 0 ; i < N ; i ++ )
{
pthread_join ( threadRE [ i ], NULL );
}
for ( i = 0 ; i < M ; i ++ )
{
pthread_join ( threadWR [ i ], NULL );
}
sem_destroy ( & accessM );
sem_destroy ( & readresM );
sem_destroy ( & orderM );
}
Programming Application
Often, a simple memory protection mutex is not optimal. For example, in an online game, the list of game rooms changes infrequently - when one of the players decides to open a new room, for example, every few seconds. It is read in one second dozens of times, and it does not make sense to line up clients for this.
Similar mechanisms (the so-called read-write lock ) exist in many programming languages and libraries. For example.
- Embarcadero Delphi :
IMultiReadExclusiveWrite
. - POSIX :
pthread_rwlock_t
. - Java :
ReadWriteLock
,ReentrantReadWriteLock
. - .NET Framework :
System.Threading.ReaderWriterLockSlim
. - C ++ :
std::shared_mutex
(starting from C ++ 17 [2] , before that - boost :: shared_mutex).
See also
- Consumer problem
- The problem of dining philosophers
- The problem of a sleeping hairdresser
- The problem of smokers
Notes
- ↑ Communications of the ACM: Concurrent Control with "Readers" and "Writers" PJ Courtois, * F. H, 1971 [1]
- ↑ std :: shared_mutex - cppreference.com (eng.) . en.cppreference.com. The appeal date is April 13, 2018.