Можно ли атомарно прочитать двойное слово с помощью однословных операций? - PullRequest
Новая
       6

Можно ли атомарно прочитать двойное слово с помощью однословных операций?

2 голосов
/ 26 января 2012

Я помню, что в какой-то момент я столкнулся с проблемой программирования, когда людей просили атомарно прочитать двойное слово с помощью операций, состоящих из одного слова.

Теперь, прежде чем мы продолжим, несколько пояснений:

  • A single word - это единица измерения, имеющая натуральное количество бит, которое может быть обработано некоторым процессором (например, 32 бита для 32-битных процессоров);
  • A двойное слово - это единица измерения, которая в два раза больше отдельного слова (и поэтому не может быть обработана сразу по инструкциям процессора);
  • By atomic , я имею в виду, что данные результата должны соответствовать значению, которое было в какой-то момент, и мы можем предположить, что никакие детали реализации или аппаратного обеспечения не будут мешать.

Насколько я помнюРешение состояло в том, чтобы прочитать самое высокое слово, а затем прочитать самое низкое слово.Затем прочитайте снова самое высокое слово, и если оно не изменилось, то значение можно считать непротиворечивым.

Однако я больше не уверен.Предположим, что у нас есть две цифры: 01.

  1. . Затем алгоритм считывает старшую часть (и получает 0).
  2. Теперь другой актер меняет значение на22 до того, как наш алгоритм прочитает следующую часть.
  3. Затем мы читаем младшую цифру, 2;
  4. , но затем надоедливый нарушитель спокойствия снова меняет значение и делает его 03.
  5. Мы читаем верхнюю часть, и это 0.Мы читаем 02, и алгоритм считает значение непротиворечивым ;но на самом деле это никогда не было 02.

Правильно ли мое воспоминание о головоломке?Это решение, которое я не помню правильно?

1 Ответ

5 голосов
/ 26 января 2012

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

Считывая максимум / минимум / максимум в системе, где значение увеличивается, выможно быть уверенным, что значение не перенесено, например (для однозначного слова) 0,9 становится 1,0.Код будет выглядеть примерно так: 

read high into reg2                 # Get high value.
set reg0 to reg2 minus 1            # Force entry in to loop.
while reg0 is not equal to reg2:    # Repeat until consecutive highs are same.
    set reg0 to reg2                    # Transfer high.
    read low into reg1                  # Read low.
    read high into reg2                 # Read next high.

# Now reg0/reg1 contains high/low.

В любой другой ситуации, когда значение может произвольно измениться, вам понадобится какая-то операция test-and-set для отдельного слова, эффективно реализующая мьютекс низкого уровнязащитить двойное слово.

...