Как синхронизировать доступ ко многим объектам

Мне кажется, вам нужна рабочая очередь. Если бы блокировка рабочей очереди стала узким местом, вы могли бы переключить ее так, чтобы каждый поток имел свою собственную рабочую очередь, тогда какой-то планировщик передал бы входящий объект потоку с наименьшим объемом работы. Следующий уровень выше - это кража работы, когда неработающие потоки просматривают рабочие очереди других потоков. (См. Библиотеку строительных блоков потоков Intel.)

Если я правильно следую за вами ....

struct table_entry {
    void *   pObject;     // substitute with your object
    sem_t    sem;         // init to empty
    int      nPenders;    // init to zero
};

struct table_entry *  table;

object_lock (void * pObject) {
    goto label;                   // yes it is an evil goto

    do {
        pEntry->nPenders++;
        unlock (mutex);
        sem_wait (sem);
label:
        lock (mutex);
        found = search (table, pObject, &pEntry);
    } while (found);

    add_object_to_table (table, pObject);
    unlock (mutex);
}

object_unlock (void * pObject) {
    lock (mutex);
    pEntry = remove (table, pObject);   // assuming it is in the table
    if (nPenders != 0) {
        nPenders--;
        sem_post (pEntry->sem);
    }
    unlock (mutex);
}

Вышесказанное должно работать, но у него есть некоторые потенциальные недостатки, такие как ...

1. Возможное узкое место в поиске.
2. Нитевой голод. Нет гарантии, что какой-либо данный поток выйдет из цикла do-while в object_lock ().

Однако, в зависимости от вашей настройки, эти потенциальные недостатки могут не иметь значения.

Надеюсь, это поможет.

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

Лично я думаю, что то, что вы пытаетесь вылечить, скорее всего, вообще не проблема. Прежде чем я потратил много времени на попытки исправить это, я бы провел небольшое тестирование, чтобы увидеть, что (если что-либо) вы потеряете, просто включив мьютекс в каждый объект и покончив с ним. Я сомневаюсь, что вам нужно пойти дальше этого.

Если вам нужно сделать больше, я бы подумал о потокобезопасном пуле объектов, и каждый раз, когда поток хочет работать с объектом, он должен получить право владения из этого пула. Вызов для получения права собственности освободит любой объект, который в настоящее время принадлежит запрашивающему потоку (во избежание тупиковых ситуаций), а затем предоставит ему право владения запрошенным объектом (блокировка, если объект в настоящее время принадлежит другому потоку). Диспетчер пула объектов, вероятно, будет работать в потоке сам по себе, автоматически сериализуя весь доступ к управлению пулом, поэтому код управления пулом может избежать необходимости блокировать доступ к переменным, сообщая ему, кто в настоящее время владеет каким объектом и тому подобное.

Лично я бы сделал вот что. У вас есть несколько объектов, у всех, вероятно, есть какой-то ключ, скажем, имена. Возьмем следующий список имен людей:

 Bill Clinton
 Bill Cosby 
 John Doe
 Abraham Lincoln 
 Jon  Stewart 

Теперь вы создадите несколько списков: по одному на каждую букву алфавита, скажем. Билл и Билл вошли бы в один список, Джон, Джон, Джон Абрахам - в другой.

Каждый список будет назначен определенному потоку - доступ должен проходить через этот поток (вы должны будете передавать операции над объектом в этот поток - отличное использование функторов). Тогда у вас будет только два места для блокировки:

 thread() { 
      loop { 
         scoped_lock lock(list.mutex); 
         list.objectAccess(); 
      }
 } 

 list_add() { 
       scoped_lock lock(list.mutex); 
       list.add(..); 
 } 

Сведите количество блокировок к минимуму, а если вы все еще выполняете много блокировок, вы можете оптимизировать количество итераций, выполняемых над объектами в ваших списках, от 1 до 5, чтобы минимизировать количество времени, затрачиваемого на получение блокировок. Если ваш набор данных растет или имеет ключ по числу, вы можете сделать любое количество разделения данных, чтобы свести блокировки к минимуму.

Сами того не зная, то, что вы искали, - это программная транзакционная память (STM).

Системы STM управляют необходимыми блокировками внутри системы для обеспечения свойств ACI (Atomic, Consistent, Isolated). Это исследовательская деятельность. Вы можете найти множество библиотек STM; в частности, я работаю над Boost.STM (библиотека еще не предназначена для бета-тестирования, и документация не совсем актуальна, но вы можете поиграть с ней). Есть также некоторые компиляторы, которые внедряют TM (как компиляторы Intel, IBM и SUN). Вы можете получить проект спецификации из здесь

Идея состоит в том, чтобы определить критические области следующим образом

transaction {
  // transactional block
}

и позволить системе STM управлять необходимыми блокировками, насколько это обеспечивает свойства ACI.

Подход Boost.STM позволяет вам писать вещи вроде

int inc_and_ret(stm::object<int>& i) {
  BOOST_STM_TRANSACTION {
    return ++i;
  } BOOST_STM_END_TRANSACTION 
}

Вы можете увидеть пару BOOST_STM_TRANSACTION/BOOST_STM_END_TRANSACTION как способ определения масштабируемой неявной блокировки.

Стоимость этой псевдопрозрачности составляет 4 байта метаданных для каждого stm::object.

Даже если это далеко от вашего первоначального дизайна, я действительно думаю, что это то, что стояло за вашей целью и первоначальным дизайном.