Сообщение Re[17]: Что такое realtime? от 08.01.2025 10:10
Изменено 08.01.2025 11:40 vdimas
Re[17]: Что такое realtime?
Здравствуйте, Философ, Вы писали:
V>>В Spin-wait не происходит ничего, кроме удержания ресурсов процессора, а тут в очередь достоверно ставятся элементы, пока крутится цикл, просто они ставятся в других потоках. Т.е., блокировки очереди нет, именно поэтому lock-free.
Ф>Классический spin-wait — активное ожидание ресурса: в цикле проверяешь, когда же тебе наконец-то что-то станет доступно.
Ф>
Здесь простое ожидание.
Конкурирующий поток, захвативший ресурс, может быть вытеснен, и еще "долго" не получит тиков процессора, в этом и заключается потенциальная неэффективность блокирующих схем.
Ф>Посмотри внимательнее:
Ф>
А здесь попытка конкурентной модификации, разница принципиальная — если конкурирующий поток будет вытеснен, то цикл сразу же исполнится.
На деле же, с большой вероятностью он исполнится за единицы итераций (т.е. за несколько десятков наносекунд) даже если конкурирующий поток не будет вытеснен.
А с ~99% вероятностью (для случая двух случайно пишущих в очередь потоков) этот цикл исполняется с первого раза.
Не веришь — напиши простой тест, да погоняй.
Надо примерно так:
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? ))
Не лучше ли насильно уйти в спячку в ожидание сигнала, т.е. отдать процессор другим задачам?
Ф>Речь ведь про этот код, правильно?
Ф>
Ф>Читатель, увидев m_rtssMemory->dwBusy, может идти дальше ничего не обновляя на экране — данные ещё не готовы.
Куда "идти"-то? ))
V>>Если же ядра унутре однопоточные, то PAUSE не делает аж ничего, это аналог NOP.
Ф>ВСЕ(!) ядра у современных интеловских процессоров МНОГОпоточные.
Не у "современных", а у "новых".
Актуальное десктопное и ноутбучное железо сегодня работает по 10 лет с лишним. ))
И у ARM этого тоже пока нет.
Да и, PAUSE хороша в мат.вычислениях, когда надо освободить умножители/делители (в т.ч. с плавающей точкой) для конкурирующего гиперпотока, а в показанном цикле CAS эта инструкция лишь повышает вероятность повторного столкновения потоков, бо в том цикл нечего освобождать — там лишь пересылки и простые сравнения, которые исполняются в современных процах без специального аккумулятора-сумматора, т.е. прямо в регистрах через схемы сравнения.
Ф>А кроме того, современные процессоры имеют блок предсказания ветвлений и спекулятивное исполнение — параллельно выполняют инструкции, которые теоретически могут оказаться следующими в потоке.
На это PAUSE не влияет, бо эти блоки "личные" у каждого гиперпотока.
Собсно, эти блоки и образуют "гиперпоток". ))
Ф>Тащемта это официальная рекомендация от Intel:
Ф>[cut=1]
Ф>
Это возвращаясь к твоей реакции:
У тебя теоретизирование, а у меня тщательные исследования на разном железе в своё время...
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:
Ф>[cut=1]
Ф>
Ф>
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 алгоритмам. ))
И да, похоже, что ты сам не читаешь, что цитируешь:
[q]
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.
Ф>Вот нифига подобного, не согласен
У тебя теоретизирование, а у меня тщательные исследования на разном железе в своё время...
Re[17]: Что такое realtime?
Здравствуйте, Философ, Вы писали:
V>>В Spin-wait не происходит ничего, кроме удержания ресурсов процессора, а тут в очередь достоверно ставятся элементы, пока крутится цикл, просто они ставятся в других потоках. Т.е., блокировки очереди нет, именно поэтому lock-free.
Ф>Классический spin-wait — активное ожидание ресурса: в цикле проверяешь, когда же тебе наконец-то что-то станет доступно.
Ф>
Здесь простое ожидание.
Конкурирующий поток, захвативший ресурс, может быть вытеснен, и еще "долго" не получит тиков процессора, в этом и заключается потенциальная неэффективность блокирующих схем.
Ф>Посмотри внимательнее:
Ф>
А здесь попытка конкурентной модификации, разница принципиальная — если конкурирующий поток будет вытеснен, то цикл сразу же исполнится.
На деле же, с большой вероятностью он исполнится за единицы итераций (т.е. за несколько десятков наносекунд) даже если конкурирующий поток не будет вытеснен.
А с ~99% вероятностью (для случая двух случайно пишущих в очередь потоков) этот цикл исполняется с первого раза.
Не веришь — напиши простой тест, да погоняй.
Надо примерно так:
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? ))
Не лучше ли насильно уйти в спячку в ожидание сигнала, т.е. отдать процессор другим задачам?
Ф>Речь ведь про этот код, правильно?
Ф>
Ф>Читатель, увидев m_rtssMemory->dwBusy, может идти дальше ничего не обновляя на экране — данные ещё не готовы.
Куда "идти"-то? ))
V>>Если же ядра унутре однопоточные, то PAUSE не делает аж ничего, это аналог NOP.
Ф>ВСЕ(!) ядра у современных интеловских процессоров МНОГОпоточные.
Не у "современных", а у "новых".
Актуальное десктопное и ноутбучное железо сегодня работает по 10 лет с лишним. ))
И у ARM этого тоже пока нет.
Да и, PAUSE хороша в мат.вычислениях, когда надо освободить умножители/делители (в т.ч. с плавающей точкой) для конкурирующего гиперпотока, а в показанном цикле CAS эта инструкция лишь повышает вероятность повторного столкновения потоков, бо в том цикл нечего освобождать — там лишь пересылки и простые сравнения, которые исполняются в современных процах без специального аккумулятора-сумматора, т.е. прямо в регистрах через схемы сравнения.
Ф>А кроме того, современные процессоры имеют блок предсказания ветвлений и спекулятивное исполнение — параллельно выполняют инструкции, которые теоретически могут оказаться следующими в потоке.
На это PAUSE не влияет, бо эти блоки "личные" у каждого гиперпотока.
Собсно, эти блоки и образуют "гиперпоток". ))
Ф>Тащемта это официальная рекомендация от Intel:
Ф>
CAS — это не spin-wait ни в одном из мест.
Твоё заблуждение уже малость неприлично.
Это похоже на spin-wait, но разница принципиальная.
Spin-wait на практике крутят десятки-сотни микросекунд, это в 1-10 тыс раз дольше твоего цикла CAS.
Это несравнимые порядки величин, поэтому рекомендации по spin-wait неприменимы к lock-free алгоритмам. ))
И да, похоже, что ты сам не читаешь, что цитируешь:
Это возвращаясь к твоей реакции:
У тебя теоретизирование, а у меня тщательные исследования на разном железе в своё время...
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.
Ф>Вот нифига подобного, не согласен
У тебя теоретизирование, а у меня тщательные исследования на разном железе в своё время...