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 );
}
Синхронизация. Монитор Хансена
Есть каноническая задача о мониторной синхронизации:
Читатели (Исключают писателей, не исключают друг друга).
Писатели (Исключают всех).
Задача довольно проста, но есть небольшая тонкость: семафор `R` разрешает доступ чтения неограниченному количеству читателей, запрещая при этом запись. Может так выйти, что при плотном потоке читателей, писатели будут ожидать непозволительно долго (да к черту - вечно).
Исходя из этих соображений, полагаю, разумно будет использовать следующую стратегию: как только один из писателей лочит мютекс `W`, новые читатели уже не присоединяются к активным и не войдут в свои крит.секции до тех пор, пока писатель не отпустит `W`.
Писатель залочил мютекс `W`, новые читатели курят в сторонке, а старых нужно подождать, пока они все не выйдут сбросив счётчик семафора `R` в ноль. Писатель должен как-то отследить это событие (WAIT_WHILE(R > 0)), но тут утверждают, что узнать состояние счётчика можно только при помощи Native Api, что не есть комильфо в контексте.
Самое людское решение из тех, что навскидку приходят - реализовать семафор самостоятельно при помощи Interlocked* функций.
Есть идеи?
Вопрос сформулирую так: Есть ли тривиальное решение? Какое?
Псевдокод:
Код:
это, проще говоря, Multiple Read Single Write Synchronizer ?
Используйте метод передачи эстафеты (passing the baton) и будьте счастливы.
Цитата: Phodopus
это, проще говоря, Multiple Read Single Write Synchronizer ?
Именно.
Цитата: Ramon
Используйте метод передачи эстафеты (passing the baton) и будьте счастливы.
Почитаю, - отпишусь.
Моё видение:
Код:
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 );
}
}
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 );
}
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` не имеют смысла.