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

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

12 голосов
/ 02 марта 2011

В памяти 0x100 и 0x104 находятся два 32-битных счетчика.Они представляют собой 64-разрядный таймер и постоянно увеличиваются.

Как правильно считывать данные с двух адресов памяти и сохранять время как 64-разрядное целое число?

Одно неверное решение: 

x = High
y = Low
result =  x << 32 + y

(Программа может быть выгружена, а тем временем Низкие переполнения ...)

Дополнительные требования:
Использовать только C, без сборки
Шина 32-битная, поэтому невозможно прочитать их в одной инструкции.
Ваша программа может переключаться в любой момент.
Нет мьютекса или блокировки.

С некоторыми объяснениями на высоком уровне все в порядке.Код не нужен.Спасибо!

Ответы [ 6 ]

21 голосов
/ 02 марта 2011

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

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

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

2 голосов
/ 03 марта 2011

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

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

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

2 голосов
/ 02 марта 2011

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

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

2 голосов
/ 02 марта 2011

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

  1. образец Высокий
  2. образец Низкий
  3. снова прочитайте Высокий - если он отличается отпример из шага 1, вернитесь к шагу 1

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

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

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

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

2 голосов
/ 02 марта 2011

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

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

1 голос
/ 02 марта 2011

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

...