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

Question

У меня есть пул потоков с некоторыми потоками (например, числом ядер), которые работают со многими объектами, скажем, тысячами объектов. Обычно я предоставляю каждому объекту мьютекс для защиты доступа к его внутренним объектам, блокирую его, когда я делаю работу, а затем освобождаю его. Когда два потока пытаются получить доступ к одному и тому же объекту, один из потоков должен ждать.

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

Теперь идет часть программирования, где я хочу перенести этот дизайн в код, но не знаю, с чего начать. Я программирую на C ++ и хочу использовать классы Boost, где это возможно, но самостоятельно написанные классы, которые обрабатывают эти специальные требования, в порядке. Как бы я это реализовал?

Моей первой идеей было создание объекта boost :: mutex для каждого потока, и каждый объект имеет boost :: shared_ptr, который изначально не установлен (или равен NULL). Теперь, когда я хочу получить доступ к объекту, я блокирую его, создав объект scoped_lock и назначив его для shared_ptr. Когда shared_ptr уже установлен, я жду на текущую блокировку. Эта идея звучит как куча полных гоночных условий, поэтому я как бы отказался от нее. Есть ли другой способ выполнить этот дизайн? Совершенно другой путь?

Edit: Приведенное выше описание немного абстрактно, поэтому позвольте мне добавить конкретный пример. Представьте себе виртуальный мир со многими объектами (думаю,> 100 000). Пользователи, движущиеся по миру, могут перемещаться по миру и изменять объекты (например, стрелять стрелами в монстров). Когда я использую только один поток, я хорошо работаю с рабочей очередью, где изменения в объектах стоят в очереди. Я хочу более масштабируемый дизайн, хотя. Если доступно 128 ядерных процессоров, я хочу использовать все 128, так что используйте это количество потоков, каждое с рабочими очередями. Одним из решений будет использование пространственного разделения, например, используйте замок для области. Это может уменьшить количество используемых блокировок, но меня больше интересует, есть ли дизайн, который экономит как можно больше блокировок.

Answer 1

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

Answer 2

Не зная этого, вы искали Software Transactional Memory (STM).

Системы STM управляют внутренними необходимыми блокировками, чтобы обеспечить свойства ACI (атомарные, согласованные, изолированные). Это исследовательская деятельность. Вы можете найти много библиотек 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.

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

Answer 3

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

Answer 4

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

 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, чтобы минимизировать количество времени, затрачиваемого на получение замки. Если ваш набор данных увеличивается или кодируется по номеру, вы можете выполнить любое количество отдельных данных, чтобы свести к минимуму блокировку.

Answer 5

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

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

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

Answer 6

Ответьте на следующий вопрос под постом @ JohnDibling.

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

@ LeonardoBernardini

---

Я сейчас пытаюсь решить такую ​​же проблему. Мой подход заключается в создании собственной структуры мьютекса (назовите ее counterMutex) с полем счетчика и полем мьютекса реального ресурса. Поэтому каждый раз, когда вы пытаетесь заблокировать counterMutex, сначала вы увеличиваете счетчик, а затем блокируете базовый мьютекс. Когда вы закончите с ним, вы уменьшите coutner и разблокируете мьютекс, после этого проверьте счетчик, чтобы увидеть, равен ли он нулю, что означает, что никакой другой поток не пытается получить блокировку. Если это так, положите counterMutex обратно в пул. Есть ли условия гонки при манипулировании счетчиком? Вы можете спросить. Ответ - нет. Помните, что у вас есть глобальный мьютекс, который гарантирует, что только один поток может одновременно получить доступ к coutnerMutex.

Answer 7

У нас тут интерес к подобной модели. Решение, которое мы рассмотрели, состоит в том, чтобы иметь глобальную (или общую) блокировку, но используемую следующим образом:

• Флаг, который можно атомарно установить на объекте. Если вы установите флаг, то вы владеете объектом.
• Вы выполняете свое действие, затем сбрасываете переменную и сигнализируете (передаете) переменную условия.
• Если получение не удалось, вы ждете переменную условия. Когда оно транслируется, вы проверяете его состояние, чтобы узнать, доступно ли оно.

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

С «общей» блокировкой у вас есть одна блокировка, применяемая к нескольким элементам. Вы бы использовали какую-то хеш-функцию, чтобы определить, какая переменная мьютекса / условия применяется к этой конкретной записи.

Answer 8

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

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 ().

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

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