Comments 14
Спасибо за статью, LFS всегда интересовали.
Хотя на самом деле увидев картинку, первым делом подумал, что это перевод старой статьи Эрика. Однако обознался.
Хотя на самом деле увидев картинку, первым делом подумал, что это перевод старой статьи Эрика. Однако обознался.
Большое спасибо за очередную статью! Жаль, за карму можно только один раз голосовать.
Спасибо за статью.
Я правильно понимаю что упомянутый Hazard Pointer нужен для предотвращения ABA? Существует ли стандартная/оптимальная имплементация?
Я правильно понимаю что упомянутый Hazard Pointer нужен для предотвращения ABA? Существует ли стандартная/оптимальная имплементация?
Да, Hazard Pointer нужен для предотвращения ABA-проблемы.
Стандартная/оптимальная имплементация (видимо, имеется в виду стека?): о стандартной не слышал, о оптимальности можно говорить применительно к конкретной задаче. Приведенные алгоритмы — Treiber stack, back-off, elimination back-off, flat combining, — хороши каждый по своему при определенных нагрузках на конкурентный стек. Даже наличие нескольких алгоритмов намекает на то, что алгоритма на все случаи жизни пока (или вовсе) не существует.
Стандартная/оптимальная имплементация (видимо, имеется в виду стека?): о стандартной не слышал, о оптимальности можно говорить применительно к конкретной задаче. Приведенные алгоритмы — Treiber stack, back-off, elimination back-off, flat combining, — хороши каждый по своему при определенных нагрузках на конкурентный стек. Даже наличие нескольких алгоритмов намекает на то, что алгоритма на все случаи жизни пока (или вовсе) не существует.
Извиняюсь за невнятный вопрос. Я имел ввиду имплементацию Hazard Pointer и способы предотвращения ABA в целом. В будущем не собираетесь об этом написать подробнее?
Уже писал: Схемы управления памятью, RCU.
Стандартной/общепринятой реализации Hazard Pointer я не знаю. Многих пугает то, что это патентованный IBM алгоритм.
Стандартной/общепринятой реализации Hazard Pointer я не знаю. Многих пугает то, что это патентованный IBM алгоритм.
Глупый вопрос, а почему в pop() мы пишем в top с std::memory_order_acquire, а не release?
На самом деле, вопрос далеко не глупый. На него есть два ответа.
Первый — чисто технический: release/acquire всегда идут парами. Если в push() мы делаем release-CAS, то в pop — acquire-CAS.
Второй — точнее. Memory order задают семантику атомарных RMW-операций. Метод push() — это метод записи данных в стек, а раз запись — значит, из пары «acquire или release» мы можем выбрать только release. Метод pop() — это чтение данных из стека, а для чтения подходящим memory order является acquire.
Первый — чисто технический: release/acquire всегда идут парами. Если в push() мы делаем release-CAS, то в pop — acquire-CAS.
Второй — точнее. Memory order задают семантику атомарных RMW-операций. Метод push() — это метод записи данных в стек, а раз запись — значит, из пары «acquire или release» мы можем выбрать только release. Метод pop() — это чтение данных из стека, а для чтения подходящим memory order является acquire.
Спасибо за быстрый ответ!
Я просто поясню, что взрывает мозг — то, что в обоих случаях мы _пишем_ (и читаем) в top. Аргумент про семантику более-менее понятен, но ведь процессор работает не в терминах чтения\записи в стек, а в терминах чтения\записи конкретных адресов (top). И как происходит этот переход, не очень ясно (ведь уровень команд синхронизации процессора весьма далек от семантики конкретного контейнера).
С точки зрения записи в top, парой к release мог бы быть guard.protect( m_Top ), если бы он использовал acquire семантику (но это, вероятно, не так, и он использует relaxed).
Верно я понимаю, что рассматривая семантику мы как бы говорим, что если происходит push/pop, то менять их местами нельзя (ведь стек может быть пуст), а pop/push — пожалуйста (ну вытолкнем мы 2й элемент, а не 1й, ну бывает).
Я просто поясню, что взрывает мозг — то, что в обоих случаях мы _пишем_ (и читаем) в top. Аргумент про семантику более-менее понятен, но ведь процессор работает не в терминах чтения\записи в стек, а в терминах чтения\записи конкретных адресов (top). И как происходит этот переход, не очень ясно (ведь уровень команд синхронизации процессора весьма далек от семантики конкретного контейнера).
С точки зрения записи в top, парой к release мог бы быть guard.protect( m_Top ), если бы он использовал acquire семантику (но это, вероятно, не так, и он использует relaxed).
Верно я понимаю, что рассматривая семантику мы как бы говорим, что если происходит push/pop, то менять их местами нельзя (ведь стек может быть пуст), а pop/push — пожалуйста (ну вытолкнем мы 2й элемент, а не 1й, ну бывает).
Я просто поясню, что взрывает мозг — то, что в обоих случаях мы _пишем_ (и читаем) в top
Да, и не только у вас. RMW-операции могут обладать как acquire, так и release семантикой. К сожалению, стандарт довольно подробно описывает атомарные чтение/запись, и только вскользь — атомарные RMW, типа, «они могут обладать как acquire, так и release семантикой». А ведь это — самое главное, ИМХО: без RMW atomic'и довольно бесполезны. Мы сами наделяем RMW-операции нужной семантикой: одни становятся «операциями acquire-чтения», другие — «операциями release-записи», хотя на самом деле они операции и чтения, и записи.
С точки зрения записи в top, парой к release мог бы быть guard.protect( m_Top ), если бы он использовал acquire семантику (но это, вероятно, не так, и он использует relaxed).
Мог бы, но здесь как раз и проявляется семантика: операции с контейнером и с Hazard Pointer'ом — это разные семантические уровни (HP на уровень глубже и играет вспомогательную роль). На самом деле в глубине HP есть m_Top.load( acquire ). Но я не уверен, что этот acquire-load обеспечит нам синхронизацию push и pop.
Верно я понимаю, что рассматривая семантику мы как бы говорим, что если происходит push/pop, то менять их местами нельзя (ведь стек может быть пуст), а pop/push — пожалуйста (ну вытолкнем мы 2й элемент, а не 1й, ну бывает).
Да, можно сказать и так.
Sign up to leave a comment.
Lock-free структуры данных. Эволюция стека