Clever Geek Handbook
📜 ⬆️ ⬇️

The task of the reader-writers

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

  1. ↑ Communications of the ACM: Concurrent Control with "Readers" and "Writers" PJ Courtois, * F. H, 1971 [1]
  2. ↑ std :: shared_mutex - cppreference.com (eng.) . en.cppreference.com. The appeal date is April 13, 2018.
Source - https://ru.wikipedia.org/w/index.php?title=Task_readers-writers&oldid=99380314


More articles:

  • Rhea's Rings
  • Amundson, Lou
  • Putu Philippe
  • Delphic TV (Internet TV channel)
  • Smeul (destroyer)
  • Balandin, Sergey Alexandrovich
  • Ersen-Cupigny
  • Ilic, Brana
  • Match for the title of World Chess Champion 2012
  • Larsson, Eric Auguste

All articles

Clever Geek | 2019