Как читать два 32-битных счетчика как 64-битное целое без состояния гонки

Ответ 1

Я узнал это из Дэвида Л. Миллса, который приписывает его Лесли Лампорту:

• Прочитайте верхнюю половину таймера в H.
• Прочитайте нижнюю половину таймера в L.
• Снова прочитайте верхнюю половину таймера в H.
• Если H == H ', то верните {H, L}, в противном случае вернитесь к 1.

Предполагая, что сам таймер обновляется атомарно, это гарантированно работает - если L переполняется где-то между этапами 1 и 2, тогда H будет увеличиваться между этапами 1 и 3, и тест на шаге 4 завершится неудачей.

Ответ 2

Учитывая характер памяти (таймер), вы должны иметь возможность читать A, читать B, читать A 'и сравнивать A с A', если они соответствуют вашему ответу. В противном случае повторите.

Это sortof зависит от других ограничений в этой памяти. Если это что-то похожее на системные часы, вышесказанное будет обрабатывать ситуацию, когда 0x0000FFFF переходит на 0x00010000, и, в зависимости от того, в каком порядке вы его читаете, в противном случае вы ошибочно закончили бы с 0x00000000 или 0x0001FFFF.

Ответ 3

Очевидный и предположительно намеченный ответ уже дан Хоббсом и Йккерием:

• образец Высокий
• образец Низкий
• read High снова - если он отличается от образца с шага 1, вернитесь к шагу 1

На каком-то многопроцессорном/ядерном оборудовании это действительно не работает должным образом. Если у вас нет барьера памяти, чтобы вы не читали High и Low из своего собственного кеша, то обновления с другого ядра - даже если 64-битные атомы и покраснели в какую-то разделяемую память - не гарантированно будут отображаться в вашем ядре своевременно. Если High и Low должны быть volatile -qualified, этого недостаточно.

Чем выше частота обновлений, тем вероятнее и значительны ошибки из-за этой проблемы.

Нет никакого переносного способа сделать это без некоторых C-оболочек для OS/CPU-специфических барьеров памяти, мьютексов, атомных операций и т.д.

В комментарии Brooks ниже упоминается, что это работает для некоторых процессоров, таких как современные AMD.

Ответ 4

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

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

Ответ 5

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

H1=High;L=Low;H2=High;
if (H2!=H1 && L < 0x7FFFFFF) { H1=H2;}
result= H1<<32+L;

Это позволяет избежать фазы повторения других решений.

Ответ 6

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