Неблокируемый список

[Igors]

Добрый день

"Неблокируемый" - значит N ниток могут добавлять/удалять элементы списка не прибегая к мутексам или др. локерам
"Список" - просто список, (а не контейнер). Т.е. элемент содержит указатель на следующий, напр.

Код

C++ (Qt)
struct CData {
 ...
 CData * mNext;  // следующий в списке
 
 static volatile CData * mDataFirst;  // указатель на первый элемент списка (голова)
 static volatile CData * mDataLast;  // указатель на последний элемент списка (хвост)
};
 

Извлечение элемента из списка продвигает голову, помещение в список - хвост. Т.е. "запросы обрабатываются в порядке поступления" (FIFO). Заметим что в случае LIFO (стек, push/pop, хвоста нет) "неблокируемость" достигается очень легко. А как сделать здесь?

Спасибо

[m_ax]

Я так понимаю, потоки - писатели пишут с одного конца, а читатели с другова конца читают и потом удаляют то что прочли?
Или я не так всё представляю?
Формулировка расплывчата малость)

[Igors]

Я так понимаю, потоки - писатели пишут с одного конца, а читатели с другова конца читают и потом удаляют то что прочли?
Или я не так всё представляю?
Формулировка расплывчата малость)

Что расплывчатого в термине FIFO? И читатели/писатели здесь ни при чем. Если "потом удаляют" - то какие же они "читатели"?    Вернее, сначала элемент извлекается из списка, а что там дальше с ним (читается или пишется) уже дело извлекшего

[Fat-Zer]

[оффтоп]
про то как "неблокируемый" стек сделать можно поподробнее?

[brankovic]

Извлечение элемента из списка продвигает голову, помещение в список - хвост.

"неблокируимая очередь" было бы точнее. Список ассоциируется с итерацией, сплайсами.

Заметим, что в случае LIFO (стек, push/pop, хвоста нет) "неблокируемость" достигается очень легко.

Непонятно, как сделать, не прокомментируете?

[Igors]

про то как "неблокируемый" стек сделать можно поподробнее?

Код

C++ (Qt)
void Push( CData * data )
{
 while (true) {
  CData * temp = CData::mDataFirst;
  data->mNext = temp;
  if (CompareAndSwap(&CData::mDataFirst, temp, data)) 
   break;
 }
}
 

Pop аналогично. Но если есть еще и хвост (mDataLast), то он провисает  

[brankovic]

про то как "неблокируемый" стек сделать можно поподробнее?

Pop аналогично. Но если есть еще и хвост (mDataLast), то он провисает  

У меня Pop аналогично не получается Там надо почитать вперёд CData::mDataFirst->mNext, а оно к тому времени могло попасть по free и unmap.

[Igors]

У меня Pop аналогично не получается Там надо почитать вперёд CData::mDataFirst->mNext, а оно к тому времени могло попасть по free и unmap.

А могло и под новый блок с тем же адресом но уже другим mNext. Значит перед удалением надо проверить не сидит ли указатель в стеке одной из ниток. Предлагается такая реализация

Данные нитки

Код

C++ (Qt)
struct CThread {
	CData * Pop( void );
 
	CData * mStackData;
	CData * mDoomedList;	
	CData * mFreeList;	
	size_t mNumDoomed, mNumFree;
};

Процедура проверки

Код

C++ (Qt)
bool ShouldDelete( CData * doomedData, const vector <CThread *> & thr )
{
	for (size_t i = 0; i < thr.size(); ++i)
		if (thr[i]->mStackData == doomedData)
			return false;
 
	return true;				
}

Если ShouldDelete вернула false, то элемент помещается в mDoomedList который просматривается при каждом новом удалении.

Ну и сам Pop

Код

C++ (Qt)
CData * CThread::Pop( void )
{
	CData * temp;
	while (true) {
		mStackData = CData::mDataFirst;
		temp = CData::mDataFirst;
		if (mStackData != temp) continue;
 
		if (!temp) break;		// stack is empty
 
		bool Ok = CompareAndSwap(&CData::mDataFirst, temp, temp->mNext);
		mStackData = 0;
		if (Ok) break;	
	}
 
	return temp;
}

Критикуем, опровергаем  
 

[maxxant]

Критикуем, опровергаем  
 

чего тут опровергать. представленный здесь код не будет корректно работать с множеством потоков.

одновременное выполнение push из двух потоков может привести к потере помещаемых данных.
ShouldDelete() вообще непонятно что делает. проверяет указатель mStackData который изменяться в Pop()

вот это условие в pop всегда невыполняется:

Код:

	mStackData = CData::mDataFirst;
	temp = CData::mDataFirst;
	if (mStackData != temp) continue;   /// всегда равно

если читает только один поток.
а если читают несколько - то содержимое mStackData вообще трудно предсказать и что-то с ним сделать.

[brankovic]

А могло и под новый блок с тем же адресом но уже другим mNext. Значит перед удалением надо проверить не сидит ли указатель в стеке одной из ниток. Предлагается такая реализация

Интересно. Но я понимаю, как shouldDelete мог бы защитить от free и unmap, но как он защитит от того же блока с другим mNext?

По теории, есть такая проблема ABA, там как раз первая ваша реализация стека в качестве примера как не правильно.

опровергаем

A поставил mStackData = h, прочитал g = h->next
B захватил h
C захватил g
C вставил j
B вставил (вернул) h
A сделал CAS успешно, присвоив mDataFirst = g, но должно быть mDataFirst = j

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

Ещё из критики, загадки в коде:

Код

C++ (Qt)
		mStackData = CData::mDataFirst;
		temp = CData::mDataFirst;
		if (mStackData != temp) continue;
 

, почему не

Код

C++ (Qt)
mStackData = temp = CData::mDataFirst;
 

с тем же самым эффектом. Те строчки с continue ни зачем не нужны.

Edit: про загадки пропускаем, эту часть понял. Вы сами это придумали или почерпнули где-то?

[Igors]

A поставил mStackData = h, прочитал g = h->next
B захватил h
C захватил g
C вставил j
B вставил (вернул) h
A сделал CAS успешно, присвоив mDataFirst = g, но должно быть mDataFirst = j

"В" не может вернуть h, поскольку mStackData == h, значит не может быть др. блока h

Edit: про загадки пропускаем, эту часть понял. Вы сами это придумали или почерпнули где-то?

Нигде не черпал 

Пояснения (для широкого круга читателей):

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

- зачем нужно сравнение (mStackData != temp) ?
При выполнении mStackData = CData::mDataFirst может быть такая подлянка

1) mDataFirst принято на регистр
2) mStackData считано из регистра

Если нитка отрубилась между 1 и 2, то mDataFirst может быть изменено др. ниткой, а указатель на регистре уже удален, (ведь mStackData еще не заряжен). Тогда вылетим на temp->mNext, пресекаем это с помощью mStackData != temp. А если mDataFirst был перезаряжен (прошло ABA),то нас это устроит, mNext читаем после

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

Там прозрачный намек на оптимизацию (mFreeList) - вместо бестолковой беготни с custom allocator    А вообще можно использовать и обычное new/delete. Единственное что требуется - не мочить блоки для которых ShouldDelete вернула false, а добавлять их в mDoomedList и пытаться удалить на следующем заходе. В худшем случае общее число таких элементов (в mDoomedList'ах всех ниток) будет равно числу ниток.

[brankovic]

B захватил h
...
B вставил (вернул) h

"В" не может вернуть h, поскольку mStackData == h, значит не может быть др. блока h

т.е. объект CData нельзя удалить не посоветовавшись со стеком, где он лежал? А если он лежал в нескольких, то нельзя удалять, не посоветовавшись с каждым? Нельзя даже повторно вставить объект, если "стек не разрешит"? Это не стек, это какая-то фабрика тогда..

самое непонятное: каков интерфейс контейнера, если нельзя изъять элемент, а потом положить на место?

[Igors]

т.е. объект CData нельзя удалить не посоветовавшись со стеком, где он лежал? А если он лежал в нескольких, то нельзя удалять, не посоветовавшись с каждым? Нельзя даже повторно вставить объект, если "стек не разрешит"? Это не стек, это какая-то фабрика тогда..

самое непонятное: каков интерфейс контейнера, если нельзя изъять элемент, а потом положить на место?

Есть простая и очень популярная формулировка

нельзя удалить объект если хоть одна нитка его использует

И предложенная схема ей также следует. Просто обычно подразумевается что счетчик/stamp находится в самом объекте. А здесь делаем по-другому: проверяем "снапшот" каждой нитки на используемый объект. С интерфейсом проблем нет - ведь после извлечения мы работаем в рамках одной нитки. Не ожидаем же мы что данные по shared указателю будут удалены при вызове нашего деструктора.

Насколько я понял "в теории этого нет" (и значит это плохо  ). Или я ошибаюсь?

[brankovic]

самое непонятное: каков интерфейс контейнера, если нельзя изъять элемент, а потом положить на место?

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

А таки могу я взять объект из стека, поковыряться и вернуть обратно в стек, и чтобы всё lock-free?

[Igors]

А таки могу я взять объект из стека, поковыряться и вернуть обратно в стек, и чтобы всё lock-free?

Непонятно что значит "вернуть обратно в стек". Когда Вы напр делаете push_bаck (std::vector), то контейнер копирует в себя, эти расходы можно сократить используя указатели. То же самое и здесь, дополнительных приседаний не требуется, и никаких локов это не вызывает.

Ладно, а по FIFO есть идеи?