Генератор идентификаторов с локальной статической переменной - потокобезопасен? - PullRequest
6 голосов
/ 24 апреля 2010

Будет ли следующий фрагмент кода работать как ожидается в многопоточном сценарии?

int getUniqueID()  
{  
    static int ID=0;  
    return ++ID;  
}

Нет необходимости, чтобы идентификаторы были смежными - даже если он пропускает значение, это нормально. Можно ли сказать, что когда эта функция вернется, возвращаемое значение будет уникальным для всех потоков?

Ответы [ 6 ]

18 голосов
/ 24 апреля 2010

Нет, не будет. Ваш процессор должен будет выполнить следующие шаги для выполнения этого кода:

  • Получить значение идентификатора из памяти в регистр
  • Увеличить значение в регистре
  • Сохранить увеличенное значение в памяти

Если переключение потока происходит во время этой (не атомарной) последовательности, может произойти следующее:

  • Поток извлекает значение 1 в регистр
  • Thread a увеличивает значение, поэтому регистр теперь содержит 2
  • Переключение контекста
  • Поток b извлекает значение 1 (которое все еще находится в памяти)
  • Переключение контекста
  • Записывает данные из памяти 2 в память и возвращает
  • Переключение контекста
  • Поток b увеличивает значение, которое он сохранил в своем регистре, до 2
  • Поток b (также) сохраняет значение 2 в памяти и возвращает 2

Итак, оба потока возвращают 2.

5 голосов
/ 24 апреля 2010

Нет, у гонок все еще есть потенциал, потому что приращение не обязательно атомарное. Если вы используете атомарную операцию для увеличения ID, это должно сработать.

4 голосов
/ 25 апреля 2010

++ не обязательно атомарный, так что нет, это не потокобезопасно. Однако многие среды выполнения C предоставляют атомарные версии, например, __sync_add_and_fetch() для gcc и InterlockedIncrement() для Windows.

3 голосов
/ 24 апреля 2010

Если вам просто нужны монотонно увеличивающиеся (или очень близкие к ним) числа в N потоках, учтите это (k - это такое число, что 2 ^ k> N):

int getUniqueIDBase()  
{  
    static int ID=0;  
    return ++ID;  
}

int getUniqueID()
{
    return getUniqueIDBase() << k + thread_id;
}
2 голосов
/ 25 апреля 2010

getUniqueID имеет как минимум два условия гонки. При инициализации ID и при увеличении ID. Я переписал функцию, чтобы показать гонки данных более четко.

int getUniqueID()  
{
   static bool initialized = false;
   static int ID;
   if( !initialized )
   {
      sleep(1);
      initialized = true;

      sleep(1);
      ID = 1;      
   }

   sleep(1);
   int tmp = ID;

   sleep(1);
   tmp += 1;

   sleep(1);
   ID = tmp;

   sleep(1);
   return tmp;
}

Инкремент обманчив, выглядит настолько маленьким, что можно предположить, что он атомарный. Однако это операция загрузки-изменения-хранения. Загрузить значение из памяти в регистр процессора. inc регистр. Сохраните регистр обратно в память.

Используя новый c ++ 0x, вы можете просто использовать тип std::atomic.

int getUniqueID()  
{  
    static std::atomic<int> ID{0};  
    return ++ID;  
}

ПРИМЕЧАНИЕ: технически я солгал. Инициализированные нулями глобальные переменные (включая статические функции) могут быть сохранены в памяти bss и не требуют инициализации после запуска программы. Тем не менее, приращение по-прежнему является проблемой.

0 голосов
/ 25 апреля 2010

Примечание. Слово почти используется, поскольку глобальная переменная будет инициализирована при запуске процесса (т. Е. Ее конструктор будет вызываться до ввода main), тогда как статическая переменная внутри функции будет быть инициализированным при первом выполнении оператора.

Ваш вопрос неверен с самого начала:

Генератор идентификаторов с локальной статической переменной - потокобезопасен?

В C / C ++ переменная, которая является статической внутри функции или внутри объявления класса / структуры, ведет себя (почти) как глобальная переменная, а не как локальная, основанная на стеке.

Следующий код:

int getUniqueID()  
{  
    static int ID=0;  
    return ++ID;  
}

будет (почти) похож на псевдокод:

private_to_the_next_function int ID = 0 ;

int getUniqueID()  
{  
    return ++ID;  
}

с псевдоключевым словом private_to_the_next_function, делающим переменную невидимой для всех других функций, но getUniqueId ...

Здесь static только скрывает переменную, делая невозможным ее доступ из других функций ...

Но даже скрытый, идентификатор переменной остается глобальным: если getUniqueId вызывается несколькими потоками, ID будет таким же потокобезопасным, как и другие глобальные переменные, то есть не является потокобезопасным вообще .

Редактировать: время жизни переменных

После прочтения комментариев я почувствовал, что не совсем ясно с моим ответом. Я не использую глобальные / локальные понятия для их значения смысла, но для их значения жизни:

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

Добавьте к нему ключевое слово static, которое имеет различные значения в зависимости от контекста (поэтому использование static для глобальных переменных и для функций в C ++ не рекомендуется в пользу анонимных пространств имен, но я отказываюсь).

Когда квалифицируется локальная переменная, эта локальная перестает вести себя как локальная. Он становится глобальным, скрытым внутри функции. Таким образом, он ведет себя так, как будто значение локальной переменной магически запоминается между вызовами функций, но это не волшебство: переменная является глобальной и останется «живой» до конца программы.

Вы можете «увидеть» это, зарегистрировав создание и уничтожение объекта, объявленного статическим внутри функции. Построение произойдет, когда будет выполнено заявление объявления, и уничтожение произойдет в конце процесса:

bool isObjectToBeConstructed = false ;
int iteration = 0 ;

struct MyObject
{
   MyObject() { std::cout << "*** MyObject::MyObject() ***" << std::endl ; }
   ~MyObject() { std::cout << "*** MyObject::~MyObject() ***" << std::endl ; }
};

void myFunction()
{
   std::cout << "   myFunction() : begin with iteration " << iteration << std::endl ;

   if(iteration < 3)
   {
      ++iteration ;
      myFunction() ;
      --iteration ;
   }
   else if(isObjectToBeConstructed)
   {
      static MyObject myObject ;
   }

   std::cout << "   myFunction() : end with iteration " << iteration << std::endl ;
}


int main(int argc, char* argv[])
{
   if(argc > 1)
   {
      std::cout << "main() : begin WITH static object construction." << std::endl ;
      isObjectToBeConstructed = true ;
   }
   else
   {
      std::cout << "main() : begin WITHOUT static object construction." << std::endl ;
      isObjectToBeConstructed = false ;
   }

   myFunction() ;

   std::cout << "main() : end." << std::endl ;
   return 0 ;
}

Если вы запустите исполняемый файл без параметров, выполнение никогда не пройдет через объявление статического объекта, и поэтому оно никогда не будет построено или разрушено, как показано в журналах:

main() : begin WITHOUT static object construction.
   myFunction() : begin with iteration 0
   myFunction() : begin with iteration 1
   myFunction() : begin with iteration 2
   myFunction() : begin with iteration 3
   myFunction() : end with iteration 3
   myFunction() : end with iteration 2
   myFunction() : end with iteration 1
   myFunction() : end with iteration 0
main() : end.

Но если вы запустите его с параметром, то объект будет создан при третьем рекурсивном вызове myFunction и уничтожен только в конце процесса, как видно из журналов:

main() : begin WITH static object construction.
   myFunction() : begin with iteration 0
   myFunction() : begin with iteration 1
   myFunction() : begin with iteration 2
   myFunction() : begin with iteration 3
*** MyObject::MyObject() ***
   myFunction() : end with iteration 3
   myFunction() : end with iteration 2
   myFunction() : end with iteration 1
   myFunction() : end with iteration 0
main() : end.
*** MyObject::~MyObject() ***

Теперь, если вы играете с одним и тем же кодом, но вызываете myFunction через несколько потоков, у вас будут условия гонки на конструкторе myObject. И если вы вызываете методы myObject или используете переменные myObject в myFunction, вызываемой несколькими потоками, у вас тоже будут условия гонки.

Таким образом, статическая локальная переменная myObject - это просто глобальный объект, скрытый внутри функции.

...