Я занимался некоторыми исследованиями реализации STM (программной транзакционной памяти), в частности, с алгоритмами, использующими блокировки и не зависящими от наличия сборщика мусора, чтобы поддерживать совместимость с не управляемыми языками, такими как C/С++, Я прочитал главу STM в Herlihy и Shavit "Искусство многопроцессорного программирования" , а также прочитал пару статей Шавита, которые описывают его "Блокировка транзакций" и "Транзакционная блокировка II" STM-реализации. Их основной подход заключается в использовании хеш-таблицы, в которой хранятся значения глобальной версии-часов и блокировки, чтобы определить, была ли затронута ячейка памяти другой записью потока. Поскольку я понимаю алгоритм, когда выполняется транзакция записи, часы-версии считываются и сохраняются в потоковой локальной памяти, а набор записей и набор записей также создаются в потоковой локальной памяти. Затем выполняются следующие шаги:
- Значения всех прочитанных адресов сохраняются в наборе read-set. Это означает, что транзакция проверяет, что все прочитанные местоположения не заблокированы, и они равны или меньше, чем локально сохраненное значение часов версии.
- Значения любых записанных адресов сохраняются в наборе записи вместе со значениями, которые должны быть записаны в эти местоположения.
- Как только полная транзакция записи завершена (и это может включать чтение и запись в несколько местоположений), транзакция пытается заблокировать каждый адрес, который должен быть записан, с использованием блокировки в хеш-таблице, которая хеширована против значения адреса.
- Когда все адреса записываемого набора блокируются, часы глобальной версии атомарно увеличиваются и новое добавочное значение локально сохраняется.
- Снова выполняется транзакция записи, чтобы убедиться, что значения в read-set не были обновлены с новым номером версии или не заблокированы другим потоком.
- Транзакция записи обновляет штамп версии для этой ячейки памяти с новым значением, которое она хранит с шага 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. Не будет ли причиной возможной аварии или сбоя сегментации? Если это так, как можно избежать этого, не блокируя ячейки памяти для чтения (то, что и текстовая книга, и документы означает ненужное)?
