Задача о читателях-писателях

Задача о читателях-писателях — одна из важнейших задач параллельного программирования. Формулируется она так:

Можно обойтись обычным мьютексом, но это не оптимально — компьютерная память, как правило, устроена так, что несколько потоков могут свободно читать и писать её (единственная проблема — нет гарантии, что в процессе обработки переменная внезапно не изменится). У этой проблемы есть несколько вариантов, разные и решения. Кому отдавать приоритет — читателю или писателю — остаётся за программистом.

Первая задача о читателях-писателях (приоритет читателя)[править | править код]

Вторая задача о читателях-писателях (приоритет писателя)[править | править код]

Примерное решение^[1]:

Глобальные целые readcount=0, writecount=0; Глобальные мьютексы mutex1, mutex2, w, r  ЧИТАТЕЛЬ     r.enter       mutex1.enter         readcount = readcount + 1         if readcount=1 then w.enter       mutex1.leave     r.leave    ...читаем...    mutex1.enter     readcount = readcount - 1     if readcount = 0 then w.leave   mutex1.leave  ПИСАТЕЛЬ   mutex2.enter     writecount = writecount + 1     if writecount=1 then r.enter   mutex2.leave    w.enter     ...пишем...   w.leave    mutex2.enter     writecount = writecount - 1     if writecount = 0 then r.leave   mutex2.leave 

Третья задача о читателях-писателях (честное распределение ресурсов)[править | править код]

Иначе говоря, ни один поток (читатель или писатель) не должен ожидать захвата блокировки слишком долго; функция захвата блокировки должна по истечении некоторого времени, если захват не удался, вернуться с признаком захват не удался, чтобы поток не простаивал и мог заняться другими делами. Зачастую это время равно нулю: функция захвата, если захват невозможен прямо сейчас, сразу возвращается.

  Глобальные мютексы: no_writers, no_readers, counter_mutex   Глобальные целые: nreaders=0   Локальные целые:  prev, current  ПИСАТЕЛЬ:   no_writers.enter   no_readers.enter    ...пишем....   no_writers.leave   no_readers.leave  ЧИТАТЕЛЬ:   no_writers.enter     counter_mutex.enter       preve:= nreaders       nreaders := nreaders + 1       if prev = 0  then no_readers.enter     counter_mutex.leave   no_writers.leave      ...читаем...    counter_mutex.enter     nreaderst:= nreaders - 1;     currente:= nreaders;     if current = 0 then no_readers.leave   counter_mutex.leave; 

Код на C для 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 Читатель %d в очереди__________Ч%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 Работает читатель %d________________Ч%d\n",i,num1,num1);				// Here the reader can read the resource at will 		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 Писатель %d в очереди__________П%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 Работает писатель %d________________П%d\n",j,num2,num2);				 // Here the writer can modify the resource at will 		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("Введите количество итераций: "); 	scanf("%d",&iter); 	printf("Iter                         ОЧЕРЕДЬ/ВЫПОЛНЕНИЕ\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); } 

Инвариант[править | править код]

Зачастую инвариантом этой задачи считают Много читателей XOR один писатель (XOR — исключающее или). Это неверно, поскольку ситуация, когда нет ни читателей, ни писателей, также является корректной.

Инвариант можно выразить следующим утверждением:

writers == 0 OR writers == 1 AND readers == 0

где writers — число писателей, readers — число читателей.

Применение в программировании[править | править код]

Часто простой мьютекс, защищающий память, неоптимален. Например, в онлайн-игре список игровых комнат изменяется нечасто — когда кто-то из игроков решает открыть новую комнату, например, раз в несколько секунд. Считывается же он за одну секунду десятки раз, и выстраивать клиентов в очередь для этого не имеет смысла.

Подобные механизмы (так называемая блокировка чтения-записи) существуют во многих языках программирования и библиотеках. Например.

• Embarcadero Delphi: IMultiReadExclusiveWrite.
• POSIX: pthread_rwlock_t.
• Java: ReadWriteLock, ReentrantReadWriteLock.
• .NET Framework: System.Threading.ReaderWriterLockSlim.
• C++: std::shared_mutex (начиная с C++17^[2], до этого — boost::shared_mutex).

См. также[править | править код]

• Задача потребителя
• Задача об обедающих философах
• Задача о курильщиках
• Проблема спящего парикмахера

Примечания[править | править код]