вторник, 14 февраля 2012 г.

Много читателей и один писатель

В много-поточном приложении довольно часто возникает необходимость синхронизировать обращение к разделяемому ресурсу, который могут одновременно читать несколько потоков "читателей", а производить запись в этот ресурс может только один поток "писатель". Когда читатели читают данные, то писатель не может писать и должен ждать, пока все читатели не закончат чтение. Когда писатель пишет, то все читатели должны ждать, пока он не запишет все данные и не освободит ресурс.

Ниже приведена моя реализация "читателя" и "писателя". В этой реализации есть допущение о том, что нам известно максимальное количество читателей MAX_READERS.


LONG gCounter = 0;

//алгоритм читателя

for (;;) //бесконечный цикл ожидания освобождения ресурса
{
  LONG n = InterlockedIncrement(&gCounter); 
  //в n - значение gCounter после инкремента
  if (n <= MAX_READERS) break; //писатель ничего не пишет - можно читать
  InterlockedDecrement(&gCounter);
}
// здесь читаем данные
...
//
InterlockedDecrement(&gCounter); //освобождаем блокировку читателем

// алгоритм писателя

for (;;) //бесконечный цикл освобождения ресурса читателями/писателями
{
  LONG n = InterlockedCompareExchange(&gCounter, (MAX_READERS+1), 0); 
  //в n - предыдущее значение gCounter, которое было ДО попытки заменить его на MAX_READERS+1 в InterlockedCompareExchange; 
  //если там был 0, то никаких читателей/писателей не было, новое значение в gCounter будет MAX_READERS+1; 
  //если в gCounter был не 0, то это значение НЕ будет заменено на MAX_READERS+1, а останется прежним
  if (n == 0) break;
}
// здесь пишем данные
...
//
InterlockedExchangeAdd(&gCounter, -(MAX_READERS+1)); //освобождаем блокировку писателем


Обращаю внимание на использование Interlocked-функций. Это такие функции, которые обеспечивают атомарность.
Например, InterlockedIncrement(&gCounter) - это атомарное увеличение на 1 (инкремент) значения gCounter.
Вообще, операция инкремента gCounter не атомарна, она состоит из следующих 3-х операций:

1. прочитать значение из памяти по адресу &gCounter
2. увеличить значение на 1
3. записать результат в память по адресу &gCounter

Если выполняется параллельно 2 потока, то возможна такая ситуация :

[поток 1] читает gCounter, прочитан 0
[поток 2] читает gCounter, прочитан 0
[поток 1] увеличивает значение на 1, получается 1
[поток 2] увеличивает значение на 1, получается 1
[поток 1] записывает 1 в gCounter
[поток 2] записывает 1 в gCounter

В итоге в gCounter будет 1, а не 2, как можно было бы предположить.

UPD. LockLib - классы C++ для блокировки разделяемых ресурсов: http://blog.coolsoftware.ru/2013/12/locklib.html

===
Перепечатка материалов блога разрешается с обязательной ссылкой на blog.coolsoftware.ru

четверг, 9 февраля 2012 г.

Свой ГСЧ

Стандартный генератор случайных чисел (ГСЧ) в C++ - функция rand(). Он работает по так-называемому конгруэнтному линейному алгоритму. Для инициализации генератора используется srand(seed).
У этого генератора есть несколько неприятных особенностей.
1. Он более-менее сносно работает, когда в своей программе вы генерируете небольшое количество независимых между собой случайных величин. Но когда с помощью одного и того же датчика генерируется с десяток различных переменных (A, B, C, D, E, F, G, H, I, J), то последовательность псевдослучайных значений, например, переменной A: A1, A2, A3, A4, A5, ... уже не будет выглядеть как случайная.
2. Требуется производить инициализацию счетчика с помощью функции srand(seed) в каждом потоке, в котором вызывается rand().
В общем, столкнувшись на практике со странностями работы стандартного ГСЧ, я решил написать свой. Основные требования - скорость работы и возможность обращаться к одному и тому же ГСЧ из разных потоков. И вот, что у меня получилось:


class CRnd
{
  private:
    unsigned long m_iran;
  public:
    void Init(unsigned long seed);
    unsigned long Rand();
}

void CRnd::Init(unsigned long seed)
{
  m_iran = seed;
}

unsigned long CRnd::Rand()
{
  unsigned long old_iran = m_iran;
  unsigned long new_iran, cur_iran;
  for (;;)
  {
    new_iran = 1664525L*old_iran+1013904223L;
    cur_iran = InterlockedCompareExchange((volatile long*)&m_iran, new_iran, old_iran);
    if (cur_iran == old_iran) break;
    old_iran = cur_iran;
  }
  return new_iran;
}

UPD. Множитель a = 1664525 и слагаемое c = 1013904223 были взяты из статьи в вики. На практике, однако, выяснилось, что получаемая последовательность чисел имеет короткий период, поэтому имеет смысл использовать другие параметры:
a = 1103515245, c = 12345, m = 2^31.

unsigned long CRnd::Rand()
{
  unsigned long old_iran = m_iran;
  unsigned long new_iran, cur_iran;
  for (;;)
  {
    new_iran = 1103515245L*old_iran+12345L;
    cur_iran = InterlockedCompareExchange((volatile long*)&m_iran, new_iran, old_iran);
    if (cur_iran == old_iran) break;
    old_iran = cur_iran;
  }
  return ((new_iran >> 16) & 32767L);
}

===
Перепечатка материалов блога разрешается с обязательной ссылкой на blog.coolsoftware.ru