Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АрхитектураБиологияГеографияДругоеИностранные языки
ИнформатикаИсторияКультураЛитератураМатематика
МедицинаМеханикаОбразованиеОхрана трудаПедагогика
ПолитикаПравоПрограммированиеПсихологияРелигия
СоциологияСпортСтроительствоФизикаФилософия
ФинансыХимияЭкологияЭкономикаЭлектроника

Атомарные операции

Оценка эффективности методов | Типы алгоритмов для неблокирующей синхронизации | Требования к разрабатываемой структуре данных и обоснование выбранных методов реализации | Разработка структуры данных | Разработка алгоритмов | Алгоритм записи | Алгоритм чтения | Алгоритм освобождения памяти | Алгоритм добавления и удаления опасных указателей | Особенности программной реализации |


Читайте также:
  1. Аддитивная и мультипликативная операции коммутативны
  2. Активные операции коммерческого банка
  3. Банковские операции.
  4. В дальнейшем изложении мы будем предполагать применение операции переименования во всех конфликтных случаях.
  5. Вложенные операторы If. Логические операции и выражения
  6. Вложенные операторы if. Сложное условие в операторе if. Логические операции

Атомарность означает неделимость операции. Это значит, что ни один поток не может увидеть промежуточное состояние операции, она либо выполняется, либо нет. Рассмотрим пример простой операции инкрементирования значения, описанный в работе [8]:

1 int x = 0;

2 ++x;

Даже такой простой код нужно синхронизировать в многопоточной среде. Если посмотреть ассемблерный код второй строки, то мы увидим, что она состоит из трех операций:

1 mov eax, dword ptr [x]; загрузка текущего значения из памяти в регистр eax

2 add eax, 1; инкрементирование значения регистра eax

3 mov dword ptr [x], eax; запись значения регистра eax обратно в память

Модификация встроенных C++ типов не является атомарной, то есть если два потока одновременно попытаются модифицировать переменную x, мы вполне можем получить ситуацию, где значение x станет 1 после двух инкрементов. Пример показан в таблице 1.1.

Таблица 1.1

Пример неверной модификации переменной х двумя потоками

Поток 1 Поток 2
исходно: x = 0  
прочитать 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].


Дата добавления: 2015-11-14; просмотров: 111 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
ГЛАВА 1. Обзор методов и средств многопоточного взаимодействия| Специальные методы управления памятью

mybiblioteka.su - 2015-2024 год. (0.006 сек.)