Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Синхронизация. Монитор Хансена

16K
22 ноября 2011 года
asmforce
186 / / 05.01.2010
Здравствуйте.

Есть каноническая задача о мониторной синхронизации:
Читатели (Исключают писателей, не исключают друг друга).
Писатели (Исключают всех).

Задача довольно проста, но есть небольшая тонкость: семафор `R` разрешает доступ чтения неограниченному количеству читателей, запрещая при этом запись. Может так выйти, что при плотном потоке читателей, писатели будут ожидать непозволительно долго (да к черту - вечно).

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

Писатель залочил мютекс `W`, новые читатели курят в сторонке, а старых нужно подождать, пока они все не выйдут сбросив счётчик семафора `R` в ноль. Писатель должен как-то отследить это событие (WAIT_WHILE(R > 0)), но тут утверждают, что узнать состояние счётчика можно только при помощи Native Api, что не есть комильфо в контексте.

Самое людское решение из тех, что навскидку приходят - реализовать семафор самостоятельно при помощи Interlocked* функций.

Есть идеи?
Вопрос сформулирую так: Есть ли тривиальное решение? Какое?

Псевдокод:
Код:
SEMAPHORE R(0, +INF);
MUTEX W(FALSE);




void Read( Data &data )
{
  // сначала проверим, не затребован ли ресурс писателем
  ENTER( W );
  // увеличим счётчик читателей
  ENTER( R );
  // разрешим другим читателям доступ к ресурсу
  // разрешим писателям устанавливать флаг востребования
  LEAVE( W );

  // ...
  // read data
  // ...

  // уменьшим счётчик читателей
  LEAVE( R );
}


void Write( const Data &data )
{
  // сначала проверим, занят ли ресурс другим писателем
  ENTER( W );
  // дождёмся, пока все читатели прекратят читать
  WAIT_WHILE( R > 0 );

  // ...
  // write data
  // ...

  // освободим ресурс для читателей и других писателей
  LEAVE( W );
}
14
23 ноября 2011 года
Phodopus
3.3K / / 19.06.2008
это, проще говоря, Multiple Read Single Write Synchronizer ?
260
23 ноября 2011 года
Ramon
1.1K / / 16.08.2003
Используйте метод передачи эстафеты (passing the baton) и будьте счастливы.
16K
23 ноября 2011 года
asmforce
186 / / 05.01.2010
Цитата: Phodopus
это, проще говоря, Multiple Read Single Write Synchronizer ?



Именно.

16K
23 ноября 2011 года
asmforce
186 / / 05.01.2010
Цитата: Ramon
Используйте метод передачи эстафеты (passing the baton) и будьте счастливы.



Почитаю, - отпишусь.

16K
23 ноября 2011 года
asmforce
186 / / 05.01.2010
Разобрался с методом передачи эстафеты. Не в восторге. Громоздко. Четыре счётчика и три двоичных семафора. Хотя, очевидно, решает поставленную задачу.

Моё видение:
Код:
MUTEX E(FALSE), R(TRUE), W(TRUE);
INT writers = 0, readers = 0;
INT dwriters = 0, dreaders = 0;


Read
{
  ENTER( E );
  if( writers > 0 )  {
    dreaders++;
    LEAVE( E );
    ENTER( R );
  }

  readers++;
  SIGNAL();

  // ...
  // read
  // ...

  ENTER( E );
  readers--;
  SIGNAL();
}


Write
{
  ENTER( E );
  if( writers > 0 || readers > 0 )  {
    dwriters++;
    LEAVE( E );
    ENTER( W );
  }

  writers++;
  SIGNAL();

  // ...
  // write
  // ...

  ENTER( E );
  writers--;
  SIGNAL();
}


SIGNAL
{
  if( writers == 0 && dreaders > 0 )
  {
    dreaders--;
    LEAVE( R );
  } else if( readers == 0 && writers == 0 && dwriters > 0 ) {
    dwriters--;
    LEAVE( W );
  } else {
    LEAVE( E );
  }
}



А если доработать собственный метод таким образом:

Код:
LONG Readers = 0;

MUTEX R(FALSE);
MUTEX W(FALSE);

MUTEX TotalLock(FALSE);



void Read( Data &data )
{
  ENTER( TotalLock );
  // сначала проверим, не затребован ли ресурс писателем
  ENTER( W );
  // увеличим счётчик читателей
  if( 1 == ++Readers )
    ENTER( R );
  // разрешим другим читателям доступ к ресурсу
  // разрешим писателям устанавливать флаг востребования
  LEAVE( W );
  LEAVE( TotalLock );

  // ...
  // read data
  // ...

  // уменьшим счётчик читателей
  ENTER( TotalLock );
  if( 0 == --Readers )
    LEAVE( R );
  LEAVE( TotalLock );
}


void Write( const Data &data )
{
  ENTER( TotalLock );
  // сначала проверим, занят ли ресурс другим писателем
  ENTER( W );
  // дождёмся, пока все читатели прекратят читать
  ENTER( R );
  LEAVE( R );
  LEAVE( TotalLock );

  // ...
  // write data
  // ...

  // освободим ресурс для читателей и других писателей
  LEAVE( W );
}


void Lock()
{
  ENTER( TotalLock );
  ENTER( W );
  ENTER( R );
  LEAVE( R );
  LEAVE( W );
}


void Unlock()
{
  LEAVE( TotalLock );
}


P.S. Я не говорил вначале, что общая блокировка как функция необходима, т.к. тогда это было ни к чему, а теперь говорю: это изначально было частью задания. Так что мютекс TotalLock был создан не как костыль, а выступает в роли костыля на пол ставки. ;)

UPD: Действительно накосячил. :facepalm:
Семафор `SReaders` там уже не нужен, а Interlocked'ы внутри критической секции `TotalLock` не имеют смысла.

Знаете кого-то, кто может ответить? Поделитесь с ним ссылкой.

Ваш ответ

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог