Я пытаюсь понять низкоуровневую механику CAS на x86 / x64, и я очень признателен за помощь / понимание.
Причина, по которой я думал об этом, заключается в том, что я пытаюсь рассуждать об экспоненциальном откате и в принципе выясняю, какой должна быть правильная единица задержки отката.
Если я посмотрю на эталонный тест freelist без блокировок, без экспоненциального отката, я увижу, как увеличивается число потоков, производительность быстро падает.
Release 7 Lock-Free Freelist Benchmark #1
M
N
S
L3U
L2U L2U
L1D L1D
L1I L1I
P P
L L L L total ops,mean ops/sec per thread,standard deviation,scalability
0 0 0 1 310134488,31013449,0,1.00
0 1 0 1 136313300,6815665,38365,0.22
0 1 0 1 136401284,6820064,50706,0.22
1 1 1 1 111134328,2778358,23851,0.09
0 0 1 1 334747444,16737372,2421,0.54
1 1 1 1 111105898,2777647,40399,0.09
Как мы знаем, live-lock может происходить, когда каждый поток препятствует продвижению других.
Мой оригинал - и я считаю теперь ошибочным - думал, что CAS вмешивался в CAS. Под этим я подразумеваю, что сама инструкция CAS деструктивно сталкивается с другой CAS, если они происходят одновременно. Оба потерпят неудачу. (Пролил, потому что я в глубине души думал о Ethernet).
Это «очевидно» объясняет результаты - все эти инструкции CAS, работающие одновременно, очень немногие имеют шанс полностью выполнить до того, как их разрушительно разрушат.
Подумав об этом еще немного, я считаю, что теперь этого не может быть. Инструкция CAS фактически не имеет режима отказа. Он скажет вам, что пункт назначения равен или не равен сравниваемому. Это все. Он не возвращается и не говорит «о, извините, столкнулся с кем-то другим».
Разрушающее вмешательство происходит, но оно происходит на более высоком уровне, в самом алгоритме структуры данных. Когда мы нажимаем или выдвигаемся из / в список freelist, мы на самом деле пытаемся поменяться местами. Нам нужно, чтобы место назначения было стабильным достаточно долго, чтобы мы могли читать его, выполнять любую работу, которую нам нужно делать, а затем находить его неизменным, чтобы мы могли завершить пуш / поп.
Если другие потоки поддерживают CASing, назначение не является стабильным - оно постоянно меняется - и нам по-прежнему приходится повторять нашу операцию.
Но теперь я в замешательстве.
Мы видим, что один поток выполняет около 30 миллионов операций push / pop. Место назначения должно быть стабильным на протяжении одной из этих операций, чтобы операция была успешной, поэтому мы видим, что имеется 30 миллионов «слотов». Если у нас есть два потока, то максимальная теоретическая производительность, которую мы можем иметь, составляет 15 миллионов операций на поток; каждая нить использует половину слотов.
Теперь давайте вернемся к CAS. CAS не имеет режима отказа. Так что же происходит, когда второй поток пытается выполнить CAS, когда другой поток уже выполняет CASing? хорошо, второй поток завершится с ошибкой на уровне структуры данных, поскольку своп не может произойти, поэтому он попытается своп снова.
Но теперь представьте, что у нас много потоков. Первый поток, запускающий CAS, будет успешным (если предположить, что каждый CAS занимает ровно одно и то же время - не так, но это предположение не меняет ничего фундаментального, так что с аргументом все в порядке). Все остальные потерпят неудачу.
Но как только первый поток завершит свою работу, следующий поток, который считывает новое целевое значение, получит успешное завершение своего CAS (и все остальные потоки, все еще выполняющие свои CAS или теперь начинающие новые CAS, потерпят неудачу).
Так почему же мы не видим идеальное масштабирование? потому что каждый «слот» должен быть использован!
Я думаю, поэтому я не понимаю CAS должным образом.
Читая Руководство разработчика программного обеспечения для архитектуры Intel, я обнаружил, что если все данные присутствуют в кэше (что меня интересует), протокол когерентности кэша заботится о CAS.
Дреппер в своем официальном документе описывает LL / SC и как это работает с использованием MESI.
Мне кажется разумным, чтобы CAS работал аналогичным образом.
Давайте рассмотрим случай с двумя потоками. Первый поток начинает свой CAS. Строка кэша с адресатом находится в своем кэше и помечена как исключающая.
Второй поток начинается с CAS. Первое ядро отправляет свою строку кэша второму ядру, и у обоих ядер эта строка кэша помечена как общая.
Первый поток завершает CAS и записывает в строку кэша (запись всегда происходит на x86 / x64, даже если сравнение было ложным; он просто записывает исходное значение).
Акт написания метокстрока кеша с изменениями;происходит RFO, в результате чего второе ядро помечает свою строку кэша как недопустимую.
Второй поток завершает свою CAS и замечает, что его строка кэша недействительна ... и что тогда?Мне трудно поверить, что инструкция внутри процессора зациклена, пока она не завершится успешно, хотя мне интересно, потому что LL / SC на ARM требует you в вашей сборке для выполнения этого цикла.Но инструкция CAS знает, что значение пункта назначения изменилось, поэтому результаты его сравнения недопустимы.Но с CAS нет никакой ошибки;он всегда возвращает истину или ложь для сравнения.Но даже если инструкции будут повторяться до полного выполнения, я все равно ожидаю идеального масштабирования.Каждый слот все еще должен использоваться.
Так что же происходит?Что происходит с CAS?
Что я вижу, так это то, что с увеличением количества потоков выполняется все меньше и меньше - все доступные «слоты», безусловно, не используются.Что-то вызывает это.Это разрушительное вмешательство между инструкциями CAS?или это большое количество RFO, загружающих шину CPU-> northbridge?
Что я отмечаю с большим интересом, так это то, что два потока в одном физическом ядре отлично масштабируются.В этом случае происходит нечто особенное и другое - два потока на отдельных физических ядрах также масштабируются наполовину.Но этого недостаточно, чтобы объяснить все это.