Потенциал условий гонки в Reader/Writer Pseudocode

Question

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

Автор Тема

r = 0; w = 1; l = 2; //assign start slot numbers 
while(1) { 
    write_slot(w); 
    l = w; //last written slot is w 
    w = not(r,l) //assigns next slot so that w is neither r or l 
} 

Считыватель Thread

while(1) { 
r = l; //read from latest write 
read(r); 
} 

возможности коррупционных условий/гонки я нашел до сих пор являются, если переменные чтения/записи не являются атомарными, и поэтому, например, автор мог бы изменить значение l, в то время как читатель находится на полпути через чтение (может привести к бессмысленному значению r через разрывы чтения/записи). Есть ли какие-либо условия гонки, которые могут потенциально привести к тому, что читатель и писатель попытаются получить доступ к одному слоту?

Answer 1

Основная проблема заключается в том, что даже назначение переменных не является атомной операцией. Трудность заключается в том, как ваш псевдокод будет выполняться на аппаратном уровне. Большинство компьютеров используют архитектуру «загрузка/хранение», где значения из памяти должны быть перемещены в регистр перед перемещением в другое место памяти (то есть нет прямых операций с памятью для памяти). Это вводит промежуточное состояние (регистр), которое могло бы смешивать вещи в многопоточной ситуации, такой как это.

Я предполагаю, что вы бы реализовать r, w и l в качестве переменных в памяти, что будет видна как нитками. Глобалы и память кучи разделяются между потоками одного и того же процесса, поэтому эта часть проста. Тем не менее, потоки должны иметь свой собственный стек и регистровые состояния, иначе они просто не сработают.

Присваивание, такие как линии читателя r = l; бы сначала загрузить значение из некоторого места памяти (везде, где хранятся l) в регистр, а затем сохранить это значение в память (везде, где хранятся r). Таким образом, назначение r = l будет что-то вроде «псевдо-сборки»:

load r1,addr(l)  ; load l from memory into register r1 
    store addr(r),r1  ; store register r1 to wherever r is kept 

где r1 некоторый регистр, addr(l) является адрес памяти, где хранится l и addr(r) это адрес r.

Проблема в вашем случае состоит в том, что регистр одного потока (скажем, читателя) может сохранять промежуточное значение, в то время как другой поток (писатель) изменяет память. Первый поток (считыватель) будет перезаписывать эту память при сохранении из регистра в память.

Учитывайте следующую последовательность событий. В обозначениях [writer] и [reader] укажите, какой поток выполняет что. Назначение читателя r = l дается как выше сборочных операций, для которых автор выполняет проблемные операции между ними:

[writer] r=0; w=1; l=2; // (given starting conditions) 
    [writer] write_slot(w)  // w==1 
    [reader] load r1,addr(l) // load l (value 2) into register r1 
    [writer] l = w;   // l gets w, which is 1 
    [writer] w = not(r,l)  // since r *in memory* is still 0, 
           // and l in memory is 1, 
           // this picks 2 for w. 
    [reader] store addr(r),r1 // stores 2 to r *in memory* 
    [reader] read(r)   // read(2) since r==2 
    [writer] write_slot(w)  // write(2) since w==2 

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

Один из способов исправить что-то вроде этого: принудительное выполнение взаимного исключения: обеспечение того, чтобы некоторый сегмент кода был бесперебойным, заставляя другие потоки ждать. Существуют специальные аппаратные инструкции (например, «сравнить & exchange» CMPXCHG) и функции операционной системы (например, приостановление выполнения потоков), используемые для реализации взаимного исключения. Как правило, вы должны использовать некоторую библиотеку для синхронизации, и не пытайтесь писать свою собственную технику. Например, см. pthread_mutex_lock() и pthread_mutex_unlock() библиотеки потоков POSIX для C.