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

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

Есть область памяти, допускающая чтение и запись. Несколько потоков имеют к ней доступ, при этом одновременно могут читать сколько угодно потоков, но писать — только один. Как обеспечить такой режим доступа?

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

Первая задача о читателях-писателях (приоритет читателя)

Пока память открыта на чтение, давать читателям беспрепятственный доступ. Писатели могут ждать сколько угодно.

Вторая задача о читателях-писателях (приоритет писателя)

Как только появился хоть один писатель, никого больше не пускать. Все остальные могут простаивать.

Примерное решение:

Глобальные целые 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, до этого — boost::shared_mutex).

См. также

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