Здравствуйте, Философ, Вы писали:

S>>Речь о lock-free алгоритмах, где нету никаких примитивов синхроиназии, используются cas инструкции,
S>>т.е. атомарные.
Ф>Вот кто-нибудь бы ещё в мануалы к процессорам заглядывал, например в интеловский, где английским по белому написано про эти инструкции, что чтобы они были атомарными, нужно использовать LOCK prefix — оно lock на шину выставляет.
Ф>Вот, например CMPXCHG
Ф>

Ф>This instruction can be used with a LOCK prefix to allow the instruction to be executed atomically. To simplify the
Ф>interface to the processor’s bus, the destination operand receives a write cycle without regard to the result of the
Ф>comparison. The destination operand is written back if the comparison fails; otherwise, the source operand is
Ф>written into the destination. (The processor never produces a locked read without also producing a locked write.)

Благодарю, но это уже детали реализации. Я имел в виду под примитивами структуры данных, которые находятся в памяти,
типа мьюетксов\семафоров\мониторов и чего только не. Соотв. из-за них всяческие задержки при переключении контекстов
и т.п., что в эпоху многоядерности не очень чтобы очень. Сделали free-lock, точнее, наверное, переоткрыли.

Цитата выше хороша, но это делати реализации этих самых free-lock инструкций.

Здравствуйте, Евгений Музыченко, Вы писали:

ЕМ>Почему бы и нет, если требования разумны? Вполне логично было бы, например, использовать "десктоп общего назначения" для воспроизведения музыки и показа картинок в клубе.

Это не тот реалтайм.
Через буферирование до 1-2 сек требования к "реалтаймовости" снижаются до примерно этих значений. ))


ЕМ>Но та же винда без специального допиливания и жесткого контроля всего софта имеет свойство запинаться в случайные моменты времени.

Это только обновления, плановое обслуживание дисков (если HD) и проверка на вирусы/трояны.
Всё это отключается через политики простым скриптом.


ЕМ>Если умудрится обходиться без общих ресурсов системы (например, файлов).

Ну, когда разговор о реалтаймовых системах, то обычно подразумевают малый порядок времени отклика...
Какие там уже файлы? ))
Шаренная память, конечно.


V>>Там всей разницы, что ожидающий на семафоре или HEVENT такой поток получает тики проца в Windows сразу же при установке примитива сигнализации
ЕМ>Не "получает", а может получать

Не, в случае наивысшего приоритета потока — получает железно 100%-но! ))


ЕМ>и не "тики проца", а временное повышение приоритета, а до тиков проца в этот момент еще очень далеко.

Если проц не был занят другим потоком с этим наивысшим приоритетом, то без разговоров привязанный через affinity проц тут же переключается на ожидающий на примитиве сигнализации реалтаймовый поток. Стоимость переключения контекста — чуть более сотни наносекунд на современном железе, это примерно нижний предел отзывчивости такой схемы.

Я с этим одно время плотно экспериментировал с дровами ASIO, добивался задержки обработки звука 2 мс, где комп представлял из себя гитарную самописную примочку.


V>>>>стоит использовать lock-free техники.
ЕМ>>>Стоит, но кто бы это делал в той же винде...
V>>Там это делали отродясь, по крайней мере в дровах от самой MS.
ЕМ>Э-э-э... В каких именно драйверах от MS Вы видели "lock-free техники"? Может, конечно, и есть отдельные примеры, которых я не видел, но "отродясь" там все тупо на спинлоках, мьютексах и событиях.

Там lock-free очереди.
Причём, что забавно, примерно такие же (вернее, почти в точности такие же) очереди я "изобрел" и вылизал в нулевые, пока MS однажды не открыла исходники своей библиотеки для построения межпотоковой обработки данных. Причём, все годы до этого я несколько переживал насчёт своей схемы (многократно мысленно и в тестах трассировал, там достаточно много было тонкостей), но, увидев практически один-в-один реализацию, вздохнул с облегчением.

В общем, в этой схеме при высокой нагрузке примитив сигнализации практически не дергается (или не дёргается вовсе).
Он дёргается только при низкой нагрузке, т.е. когда система находится большую часть времени в режиме ожидания.

В любом случае, не проблема дёрнуть HEVENT или семафор из разных потоков, бо там lock-free в цикле унутре ядра на этих примитивах.
Проблема может быть, например, с мьютексом или другими ресурсами, доступ к которым организован как исключительный.
Так вот, этого исключительного одновременного доступа из драйвера и из юзерского кода быть не должно.


V>>RAII требует реакции на исключения.
ЕМ>Сам по себе — не требует, и никогда не требовал, он вообще ничего не знает о существовании исключений.

Дык, в случае исключений вызывается таблица деструкторов на каждом уровне исключений.


V>>дело только за вызовами деструкторов по выходу из scope.

ЕМ>Именно.

ЕМ>>>А что такое "динамическая инициализация глобальных объектов"?
V>>Это когда у глобальных/статических переменных вызывается конструктор и в конце работы модуля деструктор.
ЕМ>Это ж всегда называлось статической инициализацией

Фаза статической инициализации — это загрузка модуля загрузчиком ОС.
Это инициализация глобальных переменных константами времени компиляции или константами времени загрузки модуля (например, физическими адресами ф-ий и глобальных переменных).


ЕМ>ибо программа в этом не участвует, за нее это делает CRT.

Эта часть называется динамической инициализацией, т.к. уже исполняется пользовательский код (тела конструкторов).
В фазе статической инициализации пользовательский код не исполняется.


ЕМ>Тоже элементарно реализуется в ядерном коде, я такое давно использую.

Это ты линковался с подменой каких-нить конкретных кишок CRT конкретного компилятора своими хелперами?

Или речь о самописной подсистеме, эмулирующей происходящее, но заставляющей оформлять глобальные переменные неким особым образом (т.е. не обеспечивающей гарантии языка)?
Второе я делал банально для TLS-объектов, бо в прошлых стандартах оно не работало. ))

Здравствуйте, Sharov, Вы писали:

S>Не понял, одно дело некий объект (мьютекс), а другое дело инструкция "атомарно считать и обновить".

Сама по себе команда не реализует никакого механизма синхронизации — они все строятся на основе атомарных команд.

S>Мне казалось, что lock-free алгоритмы не предполагают примитивов.

"Примитивом" нередко называют вообще любой механизм/алгоритм, достаточно простой на фоне программы, которая его использует, это не обязательно готовая функция ОС.

Здравствуйте, пффф, Вы писали:

П>много вопросов, как настроить входные/выходные пины LPT-порта

То есть, Вас никогда не удивляло, что для стабильной работы программаторов, напрямую выводящих сигналы на линии COM/LPT, в любой системе с многозадачностью, виртуальной памятью и прочими блэкджеками, часто требуются пляски с бубном, а Mach3 волшебным образом обходится без них?

П>Mach3 ставит в систему какой-то свой драйвер, и по этой причине не совместима с вистой и семёркой.

Вот Вам и ответ. Скорее всего, установкой драйвера, который патчит ядро, перехватывает функции ОС и т.п., дело не ограничивается — наверняка и установщик модифицирует параметры загрузки/работы ядра, планировщика, виртуальной памяти и прочего.

Здравствуйте, Евгений Музыченко, Вы писали:

П>>Mach3 ставит в систему какой-то свой драйвер, и по этой причине не совместима с вистой и семёркой.

ЕМ>Вот Вам и ответ. Скорее всего, установкой драйвера, который патчит ядро, перехватывает функции ОС и т.п., дело не ограничивается — наверняка и установщик модифицирует параметры загрузки/работы ядра, планировщика, виртуальной памяти и прочего.

Ну и отлично — легким движением руки брюки превращаются...простой установкой своего драйвера ОС становится вполне себе риалтаймовой

Здравствуйте, vdimas, Вы писали:

ЕМ>>использовать "десктоп общего назначения" для воспроизведения музыки и показа картинок в клубе.

V>Это не тот реалтайм.

Если тупо проигрывать MP3 и отображать картинки из файлов — да. Но в клубах часто используют диджейские станции, которые смешивают разные звуки, добавляют звуковые эффекты в музыку и голос, визуальные — в изображения, и т.п. Там очень плотные вычисления, и задержки даже в десяток миллисекунд могут быть слышны.

ЕМ>>Но та же винда без специального допиливания и жесткого контроля всего софта имеет свойство запинаться в случайные моменты времени.

V>Это только обновления, плановое обслуживание дисков (если HD) и проверка на вирусы/трояны.

Не, это может происходить при подключении/отключении устройств, при обработке потоков не слишком правильными видеодрайверами, и в ряде других ситуаций.

V>Всё это отключается через политики простым скриптом.

Неважно, насколько просто это делается — важно то, что это приходится знать и делать.

V>Ну, когда разговор о реалтаймовых системах, то обычно подразумевают малый порядок времени отклика...
V>Какие там уже файлы? ))

Если время доступа к файлу технически укладывается в требуемое время отклика, ничто не мешает использовать файлы в системе хоть жесткого реального времени. Лишь бы не тормозило сверх меры.

V>Шаренная память, конечно.

Да никакой разницы. Это все компоненты системы, имеющие каждая собственные рамки. Медленное ОЗУ ничем не лучше медленного диска.

V>Не, в случае наивысшего приоритета потока — получает железно 100%-но! ))

Мамой клянетесь?

ЕМ>>и не "тики проца", а временное повышение приоритета, а до тиков проца в этот момент еще очень далеко.

V>Если проц не был занят другим потоком с этим наивысшим приоритетом, то без разговоров привязанный через affinity проц тут же переключается на ожидающий на примитиве сигнализации реалтаймовый поток. Стоимость переключения контекста — чуть более сотни наносекунд на современном железе, это примерно нижний предел отзывчивости такой схемы.

Угу, только столь радужная картина будет только в случае, когда нужный процессор в это время висит в аппаратном ожидании. Если на нем вдруг выполняется обработчик обычного и/или отложенного прерывания, то до переключения контекста дойдет лишь после того, как все эти обработчики завершатся. А время их выполнения далеко не всегда ничтожно мало, поскольку их все чаще пишут из соображений "компилятор все оптимизирует", "процессор все разрулит", "и вообще, кого волнует лишняя сотня микросекунд".

V>Я с этим одно время плотно экспериментировал

А я с этим работаю уже больше двадцати лет. И хорошо вижу, где какие задержки.

V>с дровами ASIO

Это вообще чистый код пользовательского режима, работающий поверх любых ядерных средств, и довольно примитивный, неудобный и кривой. Но, поскольку этот интерфейс принято поддерживать в любых "профессиональных" устройствах, в соответствующей среде он считается верхом совершенства и эффективности, даже если работает через какой-нибудь тормозной драйвер ядра.

V>добивался задержки обработки звука 2 мс

Если железо позволяет, и драйвер хороший, то через KS (через который чаще всего и работает ASIO) можно и до 500-700 мкс допинать. Но с приседаниями.

V>Там lock-free очереди.

В каких именно драйверах ядра Вы их видели, и для чего они там?

V>исключительного одновременного доступа из драйвера и из юзерского кода быть не должно.

Не должно, но не всегда получается их корректно развести без ограничения функциональности.

V>Это ты линковался с подменой каких-нить конкретных кишок CRT конкретного компилятора своими хелперами?

Ага. У меня вообще свой простейший CRT, я пользуюсь только "независимыми" библиотечными функциями, которым не нужна определенная среда.

Здравствуйте, ArtDenis, Вы писали:

AD>Лично для меня realtime в ОС в первую очередь означает гарантированное время, от прихода события, до момента, когда начали выполняться первые инструкции обработчика события.
AD>Например, устройство по DMA заполнило буфер и вызвало аппаратное событие, которое в свою очередь вызвало прерывание, внутри которого ОС было уведомлено, что данные готовы, после чего (уже не в прерывании, а в задаче ОС в пользовательском коде) начали обрабатываться данные. В данном случае, если от момента, когда железо вызвало событие, до момента обработки данных в пользовательском коде, промежуток детерминирован, то это realtime, если не детерминирован и зависит от фазы Луны, то не realtime

Это необходимое условие, но не достаточное. Есть и другие подобные места в системе.

Здравствуйте, Евгений Музыченко, Вы писали:

V>>Не, в случае наивысшего приоритета потока — получает железно 100%-но! ))
ЕМ>Мамой клянетесь?

Обычные тесты из миллиардов итераций в течении десятков минут и плотной работы других приложений, в т.ч. с HD-дисками, что классически вызывает торможения порой даже мышки.
Есть два реалтаймовых потока, разнесённых через affinity по разным ядрам, кроме нулевого.
Обмениваются сигналом с одного семафора поочерёдно, замеряется время реакции.

Укладывалось до менее микросекунды, вычти еще отсюда стоимость вызова QPC и вычти стоимость принудительного вытеснения потока из-за захода в блокирующее ожидание.
На технике из 2009-го укладывалось в полторы микросекунды.

И ни разу не пролабало.

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


ЕМ>>>и не "тики проца", а временное повышение приоритета, а до тиков проца в этот момент еще очень далеко.
V>>Если проц не был занят другим потоком с этим наивысшим приоритетом, то без разговоров привязанный через affinity проц тут же переключается на ожидающий на примитиве сигнализации реалтаймовый поток. Стоимость переключения контекста — чуть более сотни наносекунд на современном железе, это примерно нижний предел отзывчивости такой схемы.
ЕМ>Угу, только столь радужная картина будет только в случае, когда нужный процессор в это время висит в аппаратном ожидании.

Не процессор, а ядро, у меня в непосредственном распоряжении были только однопроцессорные машинки.
И откуда там аппаратное ожидание на семафоре?

Блокирующее ожидание на семафоре или HEVENT всегда приводит к вытеснению потока и постановке ожидающего потока в сортированную по приоритетам очередь ожидающих потоков на примитиве синхронизации.

Т.е., в момент установки семафора ОС проверяет очередь ожидающих потоков и их приоритет (в сортированной очереди проверяется только голова списка), затем, в случае привязки affinity, всё происходит достаточно прямолинейно — проверяется текущий поток только указанного ядра и, если приоритет исполняющегося потока оказался ниже приоритета ожидающего потока (да, ты прав, после некоторого ожидания "виртуальный" приоритет ожидающего потока поднимается в этих расчётах, но в случае реалтаймового потока мы уже имеем наивысший приоритет из всех возможных), затем тому ядру посылается соотв. софтовое прерывание для переключения контекста исполнения на другой софтовый поток.

Выглядит всё это достаточно дорогостояще, но в сотни наносекунд на современном железе укладывается.

Понятно, что можно использовать spin-wait техники и или есть еще техники для межпоточных очередей (через доп. interlocked trigger), чтобы не обращаться лишний раз к примитиву синхронизации уровня ядра и не тратить тики процессорных ядер на достаточно дорогостоящий решедуллинг с переключением контекста.


ЕМ>Если на нем вдруг выполняется обработчик обычного и/или отложенного прерывания

На 3-м пинг-понге, когда каждый раз говорилось, что потоки насильно привязываются к ядрам, не участвующем в обработке аппаратных прерываний, а только реагирующих на сигналы (программные прерывания), это уже как спекуляция. ))


ЕМ>то до переключения контекста дойдет лишь после того, как все эти обработчики завершатся.

Да там единственный непрерываемый сигнал софтовый сигнал — это смена текущего контекста исполнения.
Т.е. плюс-минус до сотни наносекунд примерно потенциальное "дрожание фронта". ))
И то, событие достаточно редкое по меркам систем, где рассуждают о реалтайме.


ЕМ>А время их выполнения далеко не всегда ничтожно мало, поскольку их все чаще пишут из соображений "компилятор все оптимизирует", "процессор все разрулит", "и вообще, кого волнует лишняя сотня микросекунд".

Большинство софтовых сигналов могут прерваны более приоритетными сигналами — я в самом первом сообщении ветки уже упомянул это, что такие обработчики не несут с собой нерешаемой проблемы.

для "длинных" софтовых прерываний в этих ОС никогда не было проблем одновременной их обработки.

"Длинными прерываниями" называют софтовые прерывания, чьи обработчики могут быть достаточно тяжеловесными.


V>>Я с этим одно время плотно экспериментировал

ЕМ>А я с этим работаю уже больше двадцати лет. И хорошо вижу, где какие задержки.

V>>с дровами ASIO
ЕМ>Это вообще чистый код пользовательского режима, работающий поверх любых ядерных средств

Верно, ответная часть работает в пользовательском режиме.
ASIO — это своеобразная "дыра" на дравейрный уровень аудиокарты, где с этой дырой общаешься в стримовом режиме — через порции данных.

В том числе есть чисто софтовая эмуляция интерфейса https://asio4all.org/, удобная для разработки и отладки.
Но профессиональные аудиокарты, в т.ч. внешние USB 3.0 уже идут со своими дровами ASIO, с чем я тоже одно время несколько лет плотно работал. ))


ЕМ>и довольно примитивный, неудобный и кривой.

ХЗ, насчёт примитивный.
В этом и был смысл, наверно, чтобы миновать всевозможные этапы конвейеров аудиокарт и соотв. их драйверов, т.е. стрим идёт мимо микшеров, мимо посаженных эффектов картейки (шумоподавление, эхо и т.д.), мимо вообще всего тупо на выход или тупо со входа.


ЕМ>Но, поскольку этот интерфейс принято поддерживать в любых "профессиональных" устройствах, в соответствующей среде он считается верхом совершенства и эффективности, даже если работает через какой-нибудь тормозной драйвер ядра.

Дык, в случае внешней USB-картейки принципиально нет возможности реализовать эту схему иначе, чем через ядерный драйвер.
(Поправь, если я не прав)


V>>добивался задержки обработки звука 2 мс
ЕМ>Если железо позволяет, и драйвер хороший, то через KS (через который чаще всего и работает ASIO) можно и до 500-700 мкс допинать. Но с приседаниями.

Это на полный круг со своими эффектами звука уже.
"Без приседаний" нижний предел был в районе 8-10 ms.


V>>Там lock-free очереди.
ЕМ>В каких именно драйверах ядра Вы их видели, и для чего они там?

Это в открытом однажды их фреймворке для эффективной многопоточной обработки данных.
Их реализация на Си, моя "типизированная" с шаблонами — на С++.
Но суть происходящего была идентична, что меня и улыбнуло, и успокоило. ))


V>>исключительного одновременного доступа из драйвера и из юзерского кода быть не должно.
ЕМ>Не должно, но не всегда получается их корректно развести без ограничения функциональности.

Прям уж не всегда?
Мне как раз любопытны такие задачи, бо много возился с задачами как раз избегания столкновения потоков.


V>>Это ты линковался с подменой каких-нить конкретных кишок CRT конкретного компилятора своими хелперами?
ЕМ>Ага. У меня вообще свой простейший CRT, я пользуюсь только "независимыми" библиотечными функциями, которым не нужна определенная среда.

Мне вообще странно, почему подобное не идёт изкаробки. ))
Сам я тоже когда-то давно обнаружил, что придётся разбираться с кишками CRT компилятора и пилить под себя нечто подобное, бо на чистых сях писать, таки, ощутимая боль. ))
Но т.к. довольно много не писал в этой области, то время на это решил не тратить, а потом полностью ушёл в юзверскую разработку.

Здравствуйте, vdimas, Вы писали:

V>Обычные тесты из миллиардов итераций в течении десятков минут и плотной работы других приложений, в т.ч. с HD-дисками, что классически вызывает торможения порой даже мышки.

Как раз плотная работа HDD должна вызывать меньше торможений (если в коде нет косяков), чем столь же плотная работа SSD. Драйвер заряжает передачу по DMA и сразу возвращает управление. А вот некоторые драйверы SSD, судя по всему, "оптимизируют" не слишком длинные операции, не возвращая управления до их завершения, чтобы получить более высокие результаты в тестах за счет ресурсов процессора.

V>На технике из 2009-го укладывалось в полторы микросекунды.

Сколько сочетаний железа/ОС Вы таким образом тестировали, и какие телодвижения предшествовали получению таких результатов?

По моему опыту, получение подобной стабильной реактивности "искаропки" — скорее исключение, чем правило. Как минимум, требуется настройка железа и винды, и даже после этого не всегда удается получить стабильную реактивность.

V>Не процессор, а ядро

В этом контексте нет никакой разницы, терминология допускает. "Логический процессор", если уж совсем точно.

V>И откуда там аппаратное ожидание на семафоре?

Ну а что еще делать процессору/ядру, когда у него нет кода, готового к исполнению? Коль уж Вы упоминаете affinity, назначенный тестовому потоку, то возникает логичное предположение, что все остальные процессы/потоки на данный процессор/ядро не допускаются, и на нем исполняется только служебный код ОС (привязанные прерывания, DPC и прочее). Иначе нет почти никакого смысла в привязывании потока к определенным ядрам — большее значение имеет отвязывание его от наиболее загруженных ядер (того же нулевого).

V>когда каждый раз говорилось, что потоки насильно привязываются к ядрам, не участвующем в обработке аппаратных прерываний

А Вы проверяли, что эти ядра действительно не участвуют? Ну и не забывайте про DPC affinity — это вполне себе годный способ распределения нагрузки. Смотрели распределение DPC по ядрам?

V>только реагирующих на сигналы (программные прерывания)

Что именно Вы называете "программными прерываниями"? Чтобы известить другие процессоры/ядра о событии, используется аппаратное IPI, оно не бесплатное.

ЕМ>>то до переключения контекста дойдет лишь после того, как все эти обработчики завершатся.

V>Да там единственный непрерываемый сигнал софтовый сигнал — это смена текущего контекста исполнения.

Так на каком основании Вы предполагаете, что нужное ядро всегда будет готово к переключению контекста?

V>Большинство софтовых сигналов могут прерваны более приоритетными сигналами

Что Вы называете "сигналами" применительно к Windows? Документация MS по ядру Windows использует только глагол to signal, и прилагательное signaled.

V>"Длинными прерываниями" называют софтовые прерывания, чьи обработчики могут быть достаточно тяжеловесными.

Где именно они так называются? Если Вы об общей теории прерываний, то она допускает различные реализации. А конкретно в Windows термин interrupt используется только в отношении аппаратного прерывания. "Долгая" обработка реализуется через DPC, к ним существительное interrupt не применяется. У DPC есть приоритеты, но они влияют только на размещение в очереди. Если на ядре/процессоре начал выполнение обработчик DPC, то прервать его может только аппаратное прерывание, после завершения которого он продолжит работу, принудительно вытеснить его другим DPC или потоком невозможно.

V>ASIO — это своеобразная "дыра" на дравейрный уровень аудиокарты, где с этой дырой общаешься в стримовом режиме — через порции данных.

Знаю, я делал и драйверы ASIO, и клиенты для них. Редкостное убожество. Даже в 90-х оно годилось максимум в качестве временного наколенного решения, но тащить его тридцать лет — знатное извращение.

V>Но профессиональные аудиокарты, в т.ч. внешние USB 3.0 уже идут со своими дровами ASIO

За редким исключением, там нет никаких особых "дров ASIO". Есть общий драйвер WDM/KS, а прилагаемая ASIO DLL работает либо через сам KS (как ASIO4ALL), либо через специальные функции ядерного драйвера, чтоб не заморачиваться с KS-протоколами.

V>В этом и был смысл, наверно, чтобы миновать всевозможные этапы конвейеров аудиокарт и соотв. их драйверов, т.е. стрим идёт мимо микшеров, мимо посаженных эффектов картейки (шумоподавление, эхо и т.д.), мимо вообще всего тупо на выход или тупо со входа.

В те времена, когда Steinberg его выкатила, не было никаких "конвейеров", "микшеров" и "эффектов". Тогда в винде просто был тормозной (и еще более примитивный) звуковой интерфейс, и любой драйвер ASIO работал с железом напрямую, вообще никак не контактируя с виндовой звуковой подсистемой. Но уже в Win2k это привели в порядок (KS был даже в Win98), и с тех пор для того, чтобы любить ASIO, нужно слепо верить в его крутизну и превосходство, иначе никак.

V>в случае внешней USB-картейки принципиально нет возможности реализовать эту схему иначе, чем через ядерный драйвер.

Для любого устройства иначе нельзя. Но необходимость прикручивать что-то сбоку отпала минимум 25 лет назад, а воз и ныне там.

V>"Без приседаний" нижний предел был в районе 8-10 мкс.

Микросекунд? Не верю. Может, милли-?

V>>>Там lock-free очереди.
ЕМ>>В каких именно драйверах ядра Вы их видели, и для чего они там?

V>Это в открытом однажды их фреймворке для эффективной многопоточной обработки данных.

V>>>исключительного одновременного доступа из драйвера и из юзерского кода быть не должно.
ЕМ>>Не должно, но не всегда получается их корректно развести без ограничения функциональности.

V>Прям уж не всегда?

Понятно, что в итоге-то "можно всегда", вопрос лишь в цене. Чтобы полностью исключить неопределенно долгое ожидание, инверсию приоритетов и прочие неприятности, нужно наворотить приличное количество кода, сильно потеряв в его прозрачности, расширяемости, удобстве поддержки. Поэтому на практике обычно исключают только самые вероятные затыки, а оставшиеся и создают те самые внезапные эффекты, что мешают "истинному реалтайму".

V>Мне как раз любопытны такие задачи, бо много возился с задачами как раз избегания столкновения потоков.

Когда все механизмы взаимодействия проектируются с нуля, и потом ничего не добавляется и не переделывается, то гораздо проще. Сложнее, когда нужно обеспечить синхронизацию с уже готовой библиотекой, использующей не самые удачные решения. В случае с виндой одной из таких библиотек является Port Class Driver для звуковых устройств. Его фреймворк заточен под то, чтоб минидрайвер мог написать даже весьма средний программист, поэтому с разведением возможных блокировок выходит очень грустно.

V>Мне вообще странно, почему подобное не идёт изкаробки. ))

Мне тоже странно, только многим ли оно надо? Большинство жрет, что дают, и просит еще.

Здравствуйте, Sharov, Вы писали:

S>Благодарю, но это уже детали реализации.

Без блокировок совсем не выходит, название "lock-free" — это обман.

S>Я имел в виду под примитивами структуры данных, которые находятся в памяти,
S>типа мьюетксов\семафоров\мониторов и чего только не. Соотв. из-за них всяческие задержки при переключении контекстов
S>и т.п., что в эпоху многоядерности не очень чтобы очень. Сделали free-lock, точнее, наверное, переоткрыли.

Проблема в переключении контекстов, в том что они долгие/медленные?


S>Цитата выше хороша, но это делати реализации этих самых free-lock инструкций.

Без блокировок совсем не выходит: другое ядро или другой процессор никаким другим способом не может синхронизировать работу с участком памяти, только блокировки, только сигнал LOCK. "lock-free" — это обман.
А это просто цитата из документации.

Здравствуйте, Философ, Вы писали:

S>>Я имел в виду под примитивами структуры данных, которые находятся в памяти,
S>>типа мьюетксов\семафоров\мониторов и чего только не. Соотв. из-за них всяческие задержки при переключении контекстов
S>>и т.п., что в эпоху многоядерности не очень чтобы очень. Сделали free-lock, точнее, наверное, переоткрыли.
Ф>Проблема в переключении контекстов, в том что они долгие/медленные?

Типа того. Собственно, из-за этого в процессах появлись потоки. На уровне потоков все шустрее.

S>>Цитата выше хороша, но это делати реализации этих самых free-lock инструкций.
Ф>Без блокировок совсем не выходит: другое ядро или другой процессор никаким другим способом не может синхронизировать работу с участком памяти, только блокировки, только сигнал LOCK. "lock-free" — это обман.
Ф>А это просто цитата из документации.

Ну кстати, как оно на уровне процессов, а не потоков я не в курсе. Возможно дейстивительно поэтому в ядре
lock-free и не взлетает, т.к. на уровне процессов это крайне сложно, если вообще возможно.

Здравствуйте, Sharov, Вы писали:

S>Не понял, одно дело некий объект (мьютекс), а другое дело инструкция "атомарно считать и обновить".

Мьютекс именно такими инструкциями и обслуживается.
Сначала CAS на юзверском уровне, а если надо уйти в спячку — то CAS на ядерном семафоре, т.к. к мьютексу привязан (вернее, создаётся в ленивой CAS манере) семафор ОС, на котором можно ожидать готовности.

Но сам этот составной объект считается примитивом синхронизации, эдаким самодостаточным крипичиком с собственной функцией.


S>Мне казалось, что lock-free алгоритмы не предполагают примитивов.

Запросто предполагают.

Например, поток-читатель обнаруживает конец очереди, ну покрутил в spin-wait сколько-то там...
А потом надо уходить в честную спячку, освобождать ресурсы.

А из спячки как возвращаться? ))
Вот, на семафорах или событиях (или условных переменных, что наихудший вариант) и возвращаются.


S>Тут согласен, поток по идее всегда что-то делает, а не ждет чего-то. Точнее ждет активно.

Это оправдано только если нагрузка гарантирована.
А если нет, то так делать нельзя.

Здравствуйте, Философ, Вы писали:

Ф>Без блокировок совсем не выходит, название "lock-free" — это обман.

Всё-таки, взаимных блокировок не происходит, и это важно, бо взаимные блокировки в вытесняющей многозадачности — это злейшее зло, как выяснилось. ))
В кооперативной-однопроцессорной (одноядерной) многозадачности оно таким злом не было за невозможностью.

Вот там мьютексы были паиньками, что ими всё засрали нахрен в 80-е до 95-го, а потом как ужаснулись, когда пошло более одного ядра + вытесняющая многозадачность...


Ф>Проблема в переключении контекстов, в том что они долгие/медленные?

Да. Переключение контекстов заставляет перепрошивать внутренние таблицы виртуальной памяти, т.е. подтягивать эти таблицы, считай, в кеш 0-го уровня.
Помимо этого, переключение потока дорогое еще для потока, который вытесняют, потому что его ставят в очередь потоков, а это приоритетная очередь, операции в которой относительно затратны. А если поток вытесняется из-за блокирующего ожидания на примитиве синхронизации, то еще поток ставят в очередь к примитиву синхронизации.

Итого, который поток уходит — его дорого убирать из-за решедуллинга в очередях потоков.
Который поток ставят — его дорого ставить из-за переобновления таблиц виртуальной памяти.


Ф>Без блокировок совсем не выходит: другое ядро или другой процессор никаким другим способом не может синхронизировать работу с участком памяти, только блокировки, только сигнал LOCK. "lock-free" — это обман.

Никакого обмана. ))
CAS не блокирует ни один из потоков, выполняющих эту операцию над одним и тем же словом в памяти.
Просто гонку на CAS выиграет только один из потоков.

Т.е., lock-free гарантирует, что в каждый момент времени хотя бы один поток продвигается в своём исполнении.
Сравнить со столкновением потоков, где поток захватывает мьютексом или семафором ресурс, а потом ОС вытесняет этот поток и даёт тики потокам, которые этот ресурс в какой-то момент начинают ожидать. Да еще зачастую через spin-wait (как оно есть в мьютексах), а ждать там можно хоть до седьмого пришествия, только бесполезно. ))

Напротив, в lock-free алгоритмах ушедший в спячку поток никак не затормозит конкурирующие за ресурс потоки, а ровно наоборот.

Здравствуйте, vdimas, Вы писали:

Ф>>Без блокировок совсем не выходит, название "lock-free" — это обман.

V>Всё-таки, взаимных блокировок не происходит, и это важно...
V>Вот там мьютексы были паиньками...

Я таки настаиваю, что название "lock-free" крайне кривое и не отражает сути вещей. Дело не в мьютексах потому что блокировка вполне может быть на spin-wait'е. Посмотри:

 private static bool CAS(
    ref Node<T> location, Node<T> comparand, Node<T> newValue) {
    return 
      comparand == Interlocked.CompareExchange<Node<T>>(
                     ref location, newValue, comparand);
  }

  public void Push(T item) {
    Node<T> node = new Node<T>();
    node.Item = item;
    do {
      node.Next = head.Next;
    } while (!CAS(ref head.Next, node.Next, node));
  }

lock-free stack — классический пример, но тут мы видим модифицированный spin-wait. Цикл в методе Push равнозначен spin-wait'у и может быть им заменён.

Ф>>Проблема в переключении контекстов, в том что они долгие/медленные?
V>Да. Переключение контекстов заставляет перепрошивать внутренние таблицы виртуальной памяти, т.е. подтягивать эти таблицы, считай, в кеш 0-го уровня.
V>Помимо этого, переключение потока дорогое еще для потока, который вытесняют, потому что его ставят в очередь потоков, а это приоритетная очередь, операции в которой относительно затратны. А если поток вытесняется из-за блокирующего ожидания на примитиве синхронизации, то еще поток ставят в очередь к примитиву синхронизации.

Я в общем-то знал, что поход в ядро — дорогое удовольствие, просто хотел намекнуть, что это необязательно: во многих случаях вполне можно обойтись spin-wait'ом. Притом многие это понимают, и я юзал такие интерфейсы, вот пример:
https://github.com/scumware/RTSS_time_reader/blob/87d6308bec5c5e0a6e8c1b89392f1c21b899906c/RTSS_interop/OSD.cs#L415

 Thread.SpinWait(100);

Там было вставлено только затем, чтобы в цикл ожидания впихнуть инструкцию PAUSE. В шарпе такой вызов это наиболее простой способ. Это способ экономить электричество: эта инструкция — хинт процессору о том, что тут цикл активного ожидания, она специально для этого создавалась.

Однако о виндовом шедуллере всерьёз не задумывался. Мне всегда хватало твёрдого знания того, что поход в ядро — дорого.

Ф>>..."lock-free" — это обман.
V>Никакого обмана. ))

Я про название.

V>Просто гонку на CAS выиграет только один из потоков.

Ужасная терминология.

Здравствуйте, Философ, Вы писали:

Ф>Я таки настаиваю, что название "lock-free" крайне кривое и не отражает сути вещей. Дело не в мьютексах потому что блокировка вполне может быть на spin-wait'е. Посмотри:

Ф>

Ф> private static bool CAS(
Ф>    ref Node<T> location, Node<T> comparand, Node<T> newValue) {
Ф>    return 
Ф>      comparand == Interlocked.CompareExchange<Node<T>>(
Ф>                     ref location, newValue, comparand);
Ф>  }

Ф>  public void Push(T item) {
Ф>    Node<T> node = new Node<T>();
Ф>    node.Item = item;
Ф>    do {
Ф>      node.Next = head.Next;
Ф>    } while (!CAS(ref head.Next, node.Next, node));
Ф>  } 
Ф>

Ф>lock-free stack — классический пример, но тут мы видим модифицированный spin-wait. Цикл в методе Push равнозначен spin-wait'у и может быть им заменён.

Странно рассуждаешь. ))
В Spin-wait не происходит ничего, кроме удержания ресурсов процессора, а тут в очередь достоверно ставятся элементы, пока крутится цикл, просто они ставятся в других потоках. Т.е., блокировки очереди нет, именно поэтому lock-free.

И если конкурирующий поток уйдёт в спячку через вытеснение, то очередь не останется надолго заблокированной, как оно было бы при защите обычной очереди мьютексом, если бы перед вытеснением поток завладел бы ресурсом.


Ф>Я в общем-то знал, что поход в ядро — дорогое удовольствие, просто хотел намекнуть, что это необязательно: во многих случаях вполне можно обойтись spin-wait'ом.

Зачастую это плохая практика.
При нужной расстановке приоритетов потоков выгодней уходить в спячку, чем крутить 10 GOTO 10.

Тут банально стоит в тестах смотреть, куда и сколько тратиться больше бесполезных тиков — на лишние переключения контекстов или на 10 GOTO 10.
В моих тестах, если данные идут с задержками более ~5 микросекунд (5 миллионных секунды!), то выгодней уходить в спячку, освобождая ресурсы для других задач, чем крутить бесполезный spin-wait.

Например, в твоём цикле указан код писателя.
А что делать читателю в отсутствии данных?

Ну вот покрутил сколько-то spin-wait, дальше что? ))


Ф>Там было вставлено только затем, чтобы в цикл ожидания впихнуть инструкцию PAUSE. В шарпе такой вызов это наиболее простой способ. Это способ экономить электричество: эта инструкция — хинт процессору о том, что тут цикл активного ожидания, она специально для этого создавалась.

Это работает только в многопоточных ядрах, т.к. отдаёт ресурсы ядра процессору другому потоку (гипер-потоку в терминах Интел, например).
Если же ядра унутре однопоточные, то PAUSE не делает аж ничего, это аналог NOP.


Ф>>>..."lock-free" — это обман.
V>>Никакого обмана. ))
Ф>Я про название.

Я тоже.
См. пример своей очереди выше.

У тебя писатели не блокируют очередь взаимно, и читатели могу читать конкурентно (правда, там за раз можно безопасно забрать только всю накопленную очередь, а не один элемент, но это уже тонкости... зато по этой порции можно уже итерироваться без interlocked-операций)


V>>Просто гонку на CAS выиграет только один из потоков.
Ф>Ужасная терминология.

Сорри, у нас много кальки с английского. ))
В данном случае "a thread that won the race".

В русской терминологии "состязание потоков", конечно.

Здравствуйте, vdimas, Вы писали:

V>Странно рассуждаешь. ))
V>В Spin-wait не происходит ничего, кроме удержания ресурсов процессора, а тут в очередь достоверно ставятся элементы, пока крутится цикл, просто они ставятся в других потоках. Т.е., блокировки очереди нет, именно поэтому lock-free.

Классический spin-wait — активное ожидание ресурса: в цикле проверяешь, когда же тебе наконец-то что-то станет доступно.

while ((local_i = atomic_load(&i)) == 0) {
        /* do nothing - just keep checking over and over */
    }

Посмотри внимательнее:

 do {
    node.Next = head.Next;
   } while (!CAS(ref head.Next, node.Next, node));

Здесь CAS — это просто оптимизация того, насколько времени блокируется голова стека. Сама блокировка потока исполнения и блокировка элемента никуда не исчезает, просто хорошо оптимизирована за счёт реализации "в железе". Искренее считаю что это реализуемо и без аппаратного CAS (допустим префикс lock не работает и нет способа выставить сигнал lock на шину) — сами значения в памяти могут быть соответствующим "сигналом". Алгоритм Деккера и Решение Петтерсона вроде бы именно про это.



V>И если конкурирующий поток уйдёт в спячку через вытеснение, то очередь не останется надолго заблокированной, как оно было бы при защите обычной очереди мьютексом, если бы перед вытеснением поток завладел бы ресурсом.

Ты как будто про мьютекс пишешь: это его можно захватить, это он может принадлежать какому-то потоку после чего-нибудь типа WaitForSingleObject(). Многие вот так и попадают в эту ловушку мышления, рассуждая в парадигме "захватить ресурс". Однако задача-то в другом: выполнить участок кода атомарно, какое-то действие сделать атомарно. Если ты отбрасываешь парадигму "ресурс принадлежит потоку", стремясь только к тому чтобы выполнять отдельные действия атомарно (что есть изначальная цель), то такие алгоритмы получаются сами собой.


V>Зачастую это плохая практика.
V>При нужной расстановке приоритетов потоков выгодней уходить в спячку, чем крутить 10 GOTO 10.

Вот нифига подобного, не согласен: почти во всех гайдлайнах, и Best practсies говорится о том, что блокировка должна выставляться на минимально возможное время. Это то самое время, чтобы что-то атомарно сделать — чтоб данные консистентными оставались. Если строго следовать этим рекомендациям, то большая часть блокировок будет на время порядка десятка тактов процессора — именно столько действительно требуется чтобы обновить несколько участков памяти.

V>Например, в твоём цикле указан код писателя.
V>А что делать читателю в отсутствии данных?

В моём коде читателю при отсутствии данных не надо делать ничего: там речь про OnScreenDisplay — пока я не закончу формирование данных, показывать нечего — или предыдущее значение, или ничего. Мусор показывать бессмысленно.

Речь ведь про этот код, правильно?

            try
            {
                LockMemory();
                p_osdSlot.UpdateOSDslotText(p_newText);
            }
            finally
            {
                UnlockMemory();
            }

Читатель, увидев m_rtssMemory->dwBusy, может идти дальше ничего не обновляя на экране — данные ещё не готовы.

V>Если же ядра унутре однопоточные, то PAUSE не делает аж ничего, это аналог NOP.

ВСЕ(!) ядра у современных интеловских процессоров МНОГОпоточные. Это проистекает из того, что все современные интеловские (и АМД'шные) процессоры суперскалярные — они имеют несколько конвейров (pipelines), и исполняют инструкции параллельно.
А кроме того, современные процессоры имеют блок предсказания ветвлений и спекулятивное исполнение — параллельно выполняют инструкции, которые теоретически могут оказаться следующими в потоке.
Тащемта это официальная рекомендация от Intel:

	1
	13.5.3 Spin-Wait Loops Use the PAUSE instruction in all spin wait loops. The PAUSE instruction de-pipelines the spin-wait loop to prevent it from consuming execution resources excessively and consuming power needlessly. When executing a spin-wait loop, the processor can suffer a severe performance penalty when exiting the loop because it detects a possible memory order violation and flushes the core processor's pipeline. The PAUSE instruction provides a hint to the processor that the code sequence is a spin-wait loop. The processor uses this hint to avoid the memory order violation and prevent the pipeline flush. However, you should try to keep spin-wait loops with PAUSE short.

	2
	3.4.1 Branch Prediction Optimization Branch optimizations have a significant impact on performance. By understanding the flow of branches and improving their predictability, you can increase the speed of code significantly. Optimizations that help branch prediction are: • Keep code and data on separate pages. This is very important; see Section 3.6, “Optimizing Memory Accesses,” for more information. • Eliminate branches whenever possible. • Arrange code to be consistent with the static branch prediction algorithm. • Use the PAUSE instruction in spin-wait loops. • Inline functions and pair up calls and returns. • Unroll as necessary so that repeatedly-executed loops have sixteen or fewer iterations (unless this causes an excessive code size increase). • Separate branches so that they occur no more frequently than every three micro-ops where possible.

	3
	8.4.2 Synchronization for Short Periods The frequency and duration that a thread needs to synchronize with other threads depends application characteristics. When a synchronization loop needs very fast response, applications may use a spin-wait loop. A spin-wait loop is typically used when one thread needs to wait a short amount of time for another thread to reach a point of synchronization. A spin-wait loop consists of a loop that compares a synchronization variable with some pre-defined value. See Example 8-4(a). On a modern microprocessor with a superscalar speculative execution engine, a loop like this results in the issue of multiple simultaneous read requests from the spinning thread. These requests usually execute out-of-order with each read request being allocated a buffer resource. On detection of a write by a worker thread to a load that is in progress, the processor must guarantee no violations of memory order occur. The necessity of maintaining the order of outstanding memory operations inevitably costs the processor a severe penalty that impacts all threads. This penalty occurs on the Pentium M processor, the Intel Core Solo and Intel Core Duo processors. However, the penalty on these processors is small compared with penalties suffered on the Pentium 4 and Intel Xeon processors. There the performance penalty for exiting the loop is about 25 times more severe. On a processor supporting HT Technology, spin-wait loops can consume a significant portion of the execution bandwidth of the processor. One logical processor executing a spin-wait loop can severely impact the performance of the other logical processor.

Это из Intel® 64 and IA-32 Architectures Optimization Reference Manual. Советую туда заглянуть — там много любопытного написано.

Да, я тут "многопоточность ядер" понимаю не как в Pentium-4, не про Hyper-Threading, не про SMT. Тем не менее исполнительных блоков у современных ядер процессоров более одного — в этом плане они "многопоточные".

Здравствуйте, Философ, Вы писали:

V>>В Spin-wait не происходит ничего, кроме удержания ресурсов процессора, а тут в очередь достоверно ставятся элементы, пока крутится цикл, просто они ставятся в других потоках. Т.е., блокировки очереди нет, именно поэтому lock-free.

Ф>Классический spin-wait — активное ожидание ресурса: в цикле проверяешь, когда же тебе наконец-то что-то станет доступно.
Ф>

Ф>while ((local_i = atomic_load(&i)) == 0) {
Ф>        /* do nothing - just keep checking over and over */
Ф>    }
Ф>

Здесь простое ожидание.
Конкурирующий поток, захвативший ресурс, может быть вытеснен, и еще "долго" не получит тиков процессора, в этом и заключается потенциальная неэффективность блокирующих схем.


Ф>Посмотри внимательнее:
Ф>

Ф> do {
Ф>    node.Next = head.Next;
Ф>   } while (!CAS(ref head.Next, node.Next, node));
Ф>

А здесь попытка конкурентной модификации, разница принципиальная — если конкурирующий поток будет вытеснен, то цикл сразу же исполнится.

На деле же, с большой вероятностью он исполнится за единицы итераций (т.е. за несколько десятков наносекунд) даже если конкурирующий поток не будет вытеснен.
А с ~99% вероятностью (для случая двух случайно пишущих в очередь потоков) этот цикл исполняется с первого раза.

Не веришь — напиши простой тест, да погоняй.
Надо примерно так:

var top = _top;
node._next = top;

while(!CAS(ref _top, /* new */ node, /* old */ top)) {
    top = _top;
    node._next = top;
}

PAUSE тут не нужен, т.к., наоборот, после конфликта надо как можно скорее сделать новую попытку.

Я когда-то много гонял именно этот сценарий, собирал статистику происходящего (по кол-ву оборотов цикла).
Она весьма радует. ))


Ф>Здесь CAS — это просто оптимизация того, насколько времени блокируется голова стека.

Это состязательный аппаратный процесс длительностью около 15 тактов процессора.


Ф>Сама блокировка потока исполнения и блокировка элемента никуда не исчезает, просто хорошо оптимизирована за счёт реализации "в железе".

Ну, блин, стоимость операции в 15 тактов или в ~150 миллионов тактов в случае вытеснения конкурирующего потока, захватившего через мьютекс ресурс...


Ф>Искренее считаю что это реализуемо и без аппаратного CAS (допустим префикс lock не работает и нет способа выставить сигнал lock на шину) — сами значения в памяти могут быть соответствующим "сигналом". Алгоритм Деккера и Решение Петтерсона вроде бы именно про это.

Не-а, оно резко дороже.
Я тоже в студенчестве разрабатывал похожие алгоритмы на трёх флагах, оно примерно это же получилось. ))

Там одна-две записи и одно-два чтения (как повезёт).

Причём, запись и чтение происходят на расшаренной линейке кеша, где стоимость аппаратной синхронизации при одновременной записи и чтения в эту линейку кеша двумя ядрами составляет примерно десяток тактов на телодвижения по обеспечению когерентности на каждую операцию. Это почему данные разных потоков зачастую разносят на величину, заведомо большей величины линейки кеша.

Плюс, эти алгоритмы реализуют мьютекс, т.е. в случае вытеснения конкурирующего потока, захватившего ресурс, второй поток будет его "долго" ждать.
Плюс, эти алгоритмы работают только для двух одновременных потоков — для большего числа потоков необходимо добавлять флаги по одному на поток.

А показанный мною код обслуживает сколько угодно много потоков на запись и чтение.

Впрочем, кто тебе мешает самостоятельно провести тесты и сравнить?


V>>И если конкурирующий поток уйдёт в спячку через вытеснение, то очередь не останется надолго заблокированной, как оно было бы при защите обычной очереди мьютексом, если бы перед вытеснением поток завладел бы ресурсом.
Ф>Ты как будто про мьютекс пишешь: это его можно захватить, это он может принадлежать какому-то потоку после чего-нибудь типа WaitForSingleObject(). Многие вот так и попадают в эту ловушку мышления, рассуждая в парадигме "захватить ресурс". Однако задача-то в другом: выполнить участок кода атомарно, какое-то действие сделать атомарно. Если ты отбрасываешь парадигму "ресурс принадлежит потоку", стремясь только к тому чтобы выполнять отдельные действия атомарно (что есть изначальная цель), то такие алгоритмы получаются сами собой.

Если что-то надо выполнить "атомарно", например, записать последнюю отметку времени, где эта отметка представлена значением шириной в слово, то это можно сделать безо-всяких специальных алгоритмов вовсе. Просто пиши из разных потоков в эту ячейку и всё. ))

Но на практике мы совершаем неатомарные операции.
Например, в показанном мною коде есть две операции — инициализация node._next текущим значением _top и попытка записать этот новый _top=node.

В алгоритме Деккера необходимо будет захватить сначала некий "софтовый" этот мьютекс, потом выполнить эти две операции (уже без цикла), затем отпустить этот мьютекс.

Хрень получается. ))
И дорого в тактах (ведь CAS одновременно сравнивает и записывает в память в случае удачи, т.е. смотреть надо не на стоимость CAS, а на то, насколько он дороже обычной конкурирующей записи в линейку кеша — дороже на пяток тактов всего), и потенциальное столкновение потоков...


V>>Зачастую это плохая практика.
V>>При нужной расстановке приоритетов потоков выгодней уходить в спячку, чем крутить 10 GOTO 10.
Ф>Вот нифига подобного, не согласен: почти во всех гайдлайнах, и Best practсies говорится о том, что блокировка должна выставляться на минимально возможное время.

Это по результатам тестов систем, которые можно назвать СМО (системы массового обслуживания).
Spin-wait делает всю систему резко неэффективной. ))

Не зря же в серверной конфигурации Windows у мьютексов поле spin count обычно инициализируется нулём.
На деле, его надо инициализировать нулём и для ОЧЕНЬ многих сценариев клиентского кода.

И вообще, "родной" мьютекс использовать моветон, он очень дорогостоящий, там слишком много ветвлений, например, по значению поля SpinCount структуры.
Самописные мьютексы дешевле в разы.


V>>Например, в твоём цикле указан код писателя.
V>>А что делать читателю в отсутствии данных?
Ф>В моём коде читателю при отсутствии данных не надо делать ничего: там речь про OnScreenDisplay — пока я не закончу формирование данных, показывать нечего — или предыдущее значение, или ничего. Мусор показывать бессмысленно.

Ну вот я и спрашиваю — нафига ожидать готовность данных по spin wait? ))
Не лучше ли насильно уйти в спячку в ожидание сигнала, т.е. отдать процессор другим задачам?


Ф>Речь ведь про этот код, правильно?
Ф>

Ф>            try
Ф>            {
Ф>                LockMemory();
Ф>                p_osdSlot.UpdateOSDslotText(p_newText);
Ф>            }
Ф>            finally
Ф>            {
Ф>                UnlockMemory();
Ф>            }
Ф>

Ф>Читатель, увидев m_rtssMemory->dwBusy, может идти дальше ничего не обновляя на экране — данные ещё не готовы.

Куда "идти"-то? ))


V>>Если же ядра унутре однопоточные, то PAUSE не делает аж ничего, это аналог NOP.
Ф>ВСЕ(!) ядра у современных интеловских процессоров МНОГОпоточные.

Не у "современных", а у "новых".
Актуальное десктопное и ноутбучное железо сегодня работает по 10 лет с лишним. ))

И у ARM этого тоже пока нет.

Да и, PAUSE хороша в мат.вычислениях, когда надо освободить умножители/делители (в т.ч. с плавающей точкой) для конкурирующего гиперпотока, а в показанном цикле CAS эта инструкция лишь повышает вероятность повторного столкновения потоков, бо в том цикл нечего освобождать — там лишь пересылки и простые сравнения, которые исполняются в современных процах без специального аккумулятора-сумматора, т.е. прямо в регистрах через схемы сравнения.


Ф>А кроме того, современные процессоры имеют блок предсказания ветвлений и спекулятивное исполнение — параллельно выполняют инструкции, которые теоретически могут оказаться следующими в потоке.

На это PAUSE не влияет, бо эти блоки "личные" у каждого гиперпотока.
Собсно, эти блоки и образуют "гиперпоток". ))


Ф>Тащемта это официальная рекомендация от Intel:
Ф>

13.5.3 Spin-Wait Loops

Ф>Use the PAUSE instruction in all spin wait loops.

CAS — это не spin-wait ни в одном из мест.
Твоё заблуждение уже малость неприлично.

Это похоже на spin-wait, но разница принципиальная.
Spin-wait на практике крутят десятки-сотни микросекунд, это в 1-10 тыс раз дольше твоего цикла CAS.

Это несравнимые порядки величин, поэтому рекомендации по spin-wait неприменимы к lock-free алгоритмам. ))

И да, похоже, что ты сам не читаешь, что цитируешь:

On a processor supporting HT Technology, spin-wait loops can consume a significant portion of the execution bandwidth of the processor. One logical processor executing a spin-wait loop can severely impact the performance of the other logical processor.

Это возвращаясь к твоей реакции:

V>>При нужной расстановке приоритетов потоков выгодней уходить в спячку, чем крутить 10 GOTO 10.
Ф>Вот нифига подобного, не согласен

У тебя теоретизирование, а у меня тщательные исследования на разном железе в своё время...

Здравствуйте, Философ, Вы писали:

Ф>Без блокировок совсем не выходит

В большинстве случаев выходит, но может потребоваться заметное усложнение алгоритма.

Ф>название "lock-free" — это обман.

Судя по всему, Вы не поняли принципиальной разницы между блокирующими и неблокирующими алгоритмами.

В блокирующих алгоритмах с разделяемым ресурсом работает только один поток, получивший к нему временный доступ (тот самый mutex). Остальные потоки, которым в это время требуется ресурс, не имеют другого выхода, как ждать его освобождения. Когда поток, захвативший ресурс, выполняется достаточно быстро, этот алгоритм работает хорошо. Но, если этот поток вдруг будет прерван на значительное время, эффективность алгоритма падает обвально.

В неблокирующих алгоритмах с разделяемым ресурсом может работать любой из конкурирующих потоков, и они все равноправны. Алгоритм строится так, что каждый поток на очередном шаге, с помощью атомарных команд, совершает какое-то действие, которое либо продвигает процесс обработки общего ресурса, либо не делает ничего, если этот процесс уже успел продвинуть один из других потоков. По сути, они в случайном порядке "тыкаются" в ресурс, пытаясь общими усилиями привести его в нужное состояние (например, вставить элемент в список). В среднем это может получиться более затратным, чем с блокирующими алгоритмами, зато верхний предел затрат вполне детерминирован, поскольку для выполнения операции требуется ограниченное число шагов. Если хоть один конкурирующих потоков будет выполняться — он гарантированно завершит операцию с общим ресурсом.

Есть также разновидность синхронизации, которую называют "lock-free" просто потому, что в ней ни один поток явно не ждет освобождения ресурса, а пытается получить к нему доступ при помощи атомарных команд типа test-and-set, и затем тот поток, которому удалось получить доступ, работает с ресурсом до его освобождения. Остальные потоки в это время, видя, что ресурс захвачен, просто занимаются другими делами. С точки зрения потоков, это действительно lock-free (ни один поток не блокируется в ожидании). Но с точки зрения ресурса, это по-прежнему блокирующий алгоритм, поскольку ресурс фактически зарезервирован за единственным потоком и, если тот будет прерван, то обработка ресурса затянется на неопределенное время.


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

Аппаратная блокировка шины — полностью детерминированная операция, она всегда гарантированно завершается за определенное количество тактов.

Здравствуйте, Sharov, Вы писали:

S>Собственно, из-за этого в процессах появлись потоки. На уровне потоков все шустрее.

Там разница лишь в том, что процесс выделен в качестве контейнера для потоков. Классическая модель UNIX просто совмещает процесс, как контейнер, с единственным потоком в нем. В отношении планирования/диспетчеризации никакой разницы нет.

S>как оно на уровне процессов, а не потоков я не в курсе.

Если мы про винду, то в ней в планировании участвуют исключительно потоки. Процесс представляет собой лишь "расширенный контекст" (адресное пространство, ресурсы, общие свойства и т.п.).

S>Возможно дейстивительно поэтому в ядре lock-free и не взлетает, т.к. на уровне процессов это крайне сложно, если вообще возможно.

В смысле? Что именно "не взлетает" и "крайне сложно"?

Здравствуйте, vdimas, Вы писали:

V>В кооперативной-однопроцессорной (одноядерной) многозадачности оно таким злом не было за невозможностью.
V>Вот там мьютексы были паиньками, что ими всё засрали нахрен в 80-е до 95-го, а потом как ужаснулись, когда пошло более одного ядра + вытесняющая многозадачность...

Не сгущайте красок. При любой многозадачности мьютексы прекрасно работают до определенного уровня загрузки, и лишь после нее начинается лавинообразный рост коллизий. Это ж, по сути, классическая система массового обслуживания — турникет, дорога, транспорт, телефонная сеть и прочее, она требует прежде всего оптимизации по ресурсам. Менять алгоритмы требуется лишь при специфических требованиях, вроде hard realtime. Soft realtime с любым разумным средним временем отклика достигается масштабированием.

V>переключение потока дорогое еще для потока, который вытесняют
V>Который поток ставят — его дорого ставить

Все эти оценки "дорого-дешево" имеют смысл только в отношении удельного веса в общей совокупности затрат. Если все остальное уже оптимизировано, и на первое место вылезли затраты на переключение — значит, их действительно пора оптимизировать. Но, если мы сейчас прикинем вес затрат на переключение на фоне веса затрат, создаваемых типичным современным софтом, нам потребуется неслабый микроскоп, чтоб их разглядеть.

Так что об этих затратах уместно говорить в контексте какой-нибудь специализированной промышленной системы, софт под которую или писан с нуля квалифицированными кадрами, или ими же переделан из софта общего назначения. Если же взять навскидку произвольную систему общего назначения, от которой ожидается realtime в плане той же мультимедии, то затраты на переходы в режим ядра, переключение контекста и подобное — одни из последних кандидатов на оптимизацию.

V>Т.е., lock-free гарантирует, что в каждый момент времени хотя бы один поток продвигается в своём исполнении.

Да, но только если это lock-free одновременно и для потоков, и для их общих ресурсов.