Разработка структур данных с диiиплиной доступа один пишет - много читают для многопоточного взаимодействия в системах реального времени
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
? xпрочитать xинкрементировать xинкрементировать xзаписать xзаписать x
Ситуации подобные этой, в которых финальный результат зависит от очередности выполнения, называется data race. Можно исправить этот код и сделать его потокобезопасным добавив блокировку перед инкрементом и разблокировку после него, тем самым обеспечивая атомарность операции инкрементирования, но существует другой способ.
Некоторые операции, в том числе и операции чтения и записи, являются достаточно простыми и могут быть выполнены процессором атомарно, то есть он может реализовать их в виде специальных инструкций на аппаратном уровне. Поэтому, для того чтобы подменить оригинал узла на его измененную копию, применяется операция подмены указателя, в простейшем случае, используя обычную атомарную операцию записи. Однако неблокирующие алгоритмы более-менее сложных структур требуют наличия и более сложных атомарных операций.
В связи с этим, кроме атомарных операций чтения и записи, в число атомарных примитивов также должна входить такая операция, как сравнение с обменом или compare-and-swap (CAS), также известная, как compare exchange, или пара операций загрузка с пометкой/попытка записи или load linked/store conditional (LL/SC). Суть операции сравнение с обменом заключается в том, что она атомарно сравнивает значение одного объекта с другим и при удачном сравнении заменяет значение объекта.CAS принимает три аргумента: адрес области памяти, ожидаемое значение по этому адресу и вновь записываемое значение. Если и только если область памяти содержит ожидаемое значение, по этому адресу записывается новое значение. Операцией возвращается булево значение, определяющее произошла ли перезапись значения или нет. Иными словами, CAS(address, expected, new) атомарно выполняет следующую операцию (в псевдокоде):
Суть пары операций загрузка с пометкой/попытка записи аналогична сути операции CAS: LL атомарно сравнивает значение одного объекта с другим и при удачном сравнении SCзаменяет значение объекта.LL принимает один аргумент: адрес области памяти и возвращает ее содержимое. SC принимает два аргумента: адрес области памяти и новое значение. Если ни один другой поток не перезаписывал область памяти по адресу после того, как данный поток считал ее значение с помощью LL, только тогда по этому адресу записывается новое значение. Операция возвращает булево значение, определяющее произошла ли перезапись значения. Дополнительная инструкция validate (VL) принимает один аргумент: адрес области памяти, и возвращает булево значение, определяющее, происходила ли перезапись области памяти со стороны других потоков с того момента времени, как данный поток выполнил LL.
Большинство современных широко распространенных процессорных архитектур поддерживает либо CAS, либо пару LL/SC на выровненных однословных операндах. В некоторых 32-разрядных системах эти операции доступны и для двухсловных операндов (то есть доступна поддержка 64-разрядных инструкций), но на 64-битных архитектурах поддержки операций над двухсловными операндами нет (то есть 128-битные инструкции не поддерживаются). Пара LL/SC обычно используется в RISC-архитектурах (DEC Alpha, MIPS, PowerPC, ARM), тогда как на архитектурах x86 используется CAS в различных ее вариациях.
CAS легко выразить через пару LL/SC следующим образом:
Более подробное описание операций можно найти в работах [2,4].
Специальные методы управления памятью
Помимо проблемы образования несогласованных данных, которая решается вышеописанными принципами неблокирующего программирования, при разработке неблокирующих алгоритмов для работы с динамическими структурами возникает более сложная проблема: проблема управления освобождением памяти узлов или их повторного использования.
Главную заботу при работе с неблокирующими структурами представляет проблема освобождения памяти, занимаемой удаляемыми узлами. В случае работы со структурой, основанной на блокировках, легко гарантировать, что когда некий поток удаляет узел из динамической структуры, никакой другой поток впоследствии не обратится к памяти этого узла, до тех пор, пока она не будет заново перераспределена. В результате, для удаляющего потока обычно является вполне безопасным освобождение памяти, занимаемой узлом (например, с помощью delete) для последующего произвольного ее выделения в другом потоке (например, с помощью new).
В случае работы с типичной неблокирующей динамической структурой в многопоточной среде без поддержки автоматического сбора мусора это не так. Ведь для того, чтобы гарантировать прогресс выполнения операции, каждый поток должен иметь неограниченную возможность оперировать объектом в любой момент времени. Когда некий поток удаляет узел, является вполне возможным, что некий другой соперничающий поток уже ранее уже получил ссылку на этот узел и готовится получить доступ к его содержимому. Если удаляющий поток освободит память удаляемого узла для дальнейшего ее перераспределения, соперничающий поток в дальнейшем может либо повредить содержимое некоей другой структуры, которая займет место удаленного узла, либо вернуть неверный результат, либо пострадать от ошибки доступа к памяти. Более того, если перераспределенная память возвращена операционной системе, доступ к ней может повлечь еще более тяжкие последствия. Проще говоря, задача освобождения памяти в данном случае состоит в том, чтобы иметь возможность освобождать память удаляемых узлов (для дальнейшего перераспределения или возврата ОС), гарантируя