Я проводил некоторые исследования реализаций STM (программной транзакционной памяти), в частности алгоритмов, которые используют блокировки и не зависят от наличия сборщика мусора, чтобы поддерживать совместимость с неуправляемыми языками, такими как C / C ++. Я прочитал главу STM в книге Херлихи и Шавит «Искусство Многопроцессорное программирование », а также прочитать пару статей Шавита, в которых описывается его " Transactional Locking " и " Transactional Locking II " Реализации STM. Их базовый подход заключается в использовании хеш-таблицы, в которой хранятся значения глобальных часов версии и блокировки, чтобы определить, была ли затронута область памяти при записи другого потока. Насколько я понимаю алгоритм, когда выполняется транзакция записи, часы версии считываются и сохраняются в локальной памяти потока, а набор чтения и записи также создаются в локальной памяти потока. Затем выполняются следующие шаги:
- Значения любых прочитанных адресов сохраняются в наборе чтения. Это означает, что транзакция проверяет, что любые считываемые ячейки не заблокированы, и что они равны или меньше локально сохраненного значения часов версии.
- Значения любых записанных адресов сохраняются в наборе для записи вместе со значениями, которые должны быть записаны в эти места.
- Как только вся транзакция записи завершена (и это может включать чтение и запись в несколько ячеек), транзакция пытается заблокировать каждый адрес, который должен быть записан, с помощью блокировки в хеш-таблице, которая хешируется по адресу ' ценность.
- Когда все адреса, установленные для записи, заблокированы, часы глобальной версии автоматически увеличиваются, а новое увеличенное значение сохраняется локально.
- Запись-транзакция снова проверяет, чтобы убедиться, что значения в наборе для чтения не были обновлены с новым номером версии или не заблокированы другим потоком.
- Транзакция записи обновляет отметку версии для этой ячейки памяти с новым значением, которое она сохранила с шага # 4, и фиксирует значения в наборе записи в память.
- Блокировки ячеек памяти снимаются.
Если какой-либо из вышеуказанных шагов проверки завершился неудачно (то есть шаги №1, №3 и №5), то транзакция записи прерывается.
Процесс чтения-транзакции намного проще. Согласно документам Шавита, мы просто
- Чтение и локальное сохранение глобального значения часов версии
- Убедитесь, что в ячейках памяти значение часов не превышает текущее сохраненное глобальное значение часов версии, а также убедитесь, что ячейки памяти в настоящее время не заблокированы.
- Выполните операции чтения
- Повторите шаг № 2 для проверки
Если один из шагов №2 или №4 терпит неудачу, то транзакция чтения прерывается.
Вопрос, который я, кажется, не могу решить, заключается в том, что происходит, когда вы пытаетесь прочитать область памяти внутри объекта, который находится в куче, а другой поток вызывает delete для указателя на этот объект? В статьях Шавита они подробно объясняют, как не может быть записи в область памяти, которая была переработана или освобождена, но кажется, что внутри транзакции чтения нет ничего, что препятствовало бы возможному сценарию синхронизации, который позволил бы вам для чтения из области памяти внутри объекта, освобожденной другим потоком. В качестве примера рассмотрим следующий код:
Thread A выполняет следующее внутри транзакции атомарного чтения: linked_list_node* next_node = node->next;
Thread B выполняет следующее: delete node;
Поскольку next_node является локальной переменной потока, это не транзакционный объект. Операция разыменования, необходимая для присвоения ему значения node->next, на самом деле требует двух отдельных чтений. В промежутках между этими чтениями delete может вызываться node, так что чтение из члена next фактически считывается из сегмента памяти, который уже был освобожден. Поскольку чтения оптимистичны, освобождение памяти, на которое указывает node в Thread B, не будет обнаружено в Thread A. Не вызовет ли это возможный сбой или ошибку сегментации? Если да, то как этого можно избежать без блокировки ячеек памяти для чтения (то, что отмечается как в учебнике, так и в документах, не является необходимым)?
