Russian Qt Forum

Добрый день

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

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

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

Спасибо

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

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

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

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


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

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

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

У меня 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;
}

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

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

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

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

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

По теории, есть такая проблема ABA (http://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_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 = temp = CData::mDataFirst;
 

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

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

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

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

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

- как же так, 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 читаем после

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

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

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

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

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

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

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

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

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

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

Поскольку даже по стеку у нас с вами нет понимания (и ни у кого из читающих, я думаю), то бессмысленно обсуждать. Загуглите Michael Maged hazard pointers, это серебряная пуля в своём роде, любой контейнер можно на их основе сделать локфри и любой алгоритм. По сути ваш подход, кстати. Но ИМХО это непрактично для реального кода, слишком сложно.

Да, про альтернативный подход SimpleSunny хорошую ссылку на rsdn постил ещё в прошлой теме, где remark (кажется) рассказывает о своей идее.

Я имел в виду не стек. Я предлогал механизм, который бы позволил сократить (не полностью избавиться) затраты от простоя потоков при работе с данными. Идея была в создании внутреннего буфера данных (конечного) и в соответствующей корреляции читающих и пишующих потоков.
Короче lockfree, но чуть более эффективный.   

Помню (давно) читал фантастику сына, запомнилась одна - автор(ы) Олди (точно). название "Маг в законе" (это помню уже смутно, могу напутать). Действие происходит в дореволюционной России, "маги" набирают себе "учеников", которые в конце-концов тоже становятся магами. Обаятельный полицейский с ними борется и все такое. Помимо приключений авторы доказывают что "копия всегда слабее оригинала", ученик никогда не достигает уровня учителя. не говоря уже о том чтобы превзойти его (конечно с ними можно соглашаться или нет).

Зная все больше и больше, изучая все большее число ссылок, мы конечно "растем". Но в то же время - утрачиваем непосредственность, непредвзятость, и слишком часто пытаемся выехать на достигнутом (по существу на запомненном). Не становимся ли мы (бледнеющей) копией "учителей"?

Ладно, это просто так, не воспринимайте всерьез  :)

Я тож один рассказ тут вспомнил...
Жил да был один математик. Он не читал современных статей, книг и всё прочее. И как то решил создать машинку (метод) позволяющий очень просто решать очень широкий круг задач. Заперся в четырёх стенах, закинулся бумагой и начал писать, решать, выводить...
Прошло много времени и в один прекрасный день ему всё же удалось это сделать. Он был очень счастлив и горд собой. И вот решил показать свой замечательный труд современникам (коллегам).
Коллеги посмотрели и сказали:
-Круто, чувак, дифференциальное исчисление это реально полезная машинка, вот только известна со времён Ньютона, который и заложил эти основы.

К чему это я? Весь прогресс, который мы не можем сегодня не заметить обязан именно доступностью и открытостью информации, многочисленным статьям, конференциям, обмену опытом.

 
Не согласен категорически с тем, что:


Хорошо, что Вы теор. физикой не занимаетесь)) А то бы жили сейчас в 17 веке))

Ладно, и Вы не воспринимайте всерьёз)) просто моё имхо)

Ну и кто выиграл и кто проиграл? Чувак был счастлив/горд? Сами сказали что был. А тот что просто прочитал Ньютона? Да никогда не был. А сравнивать понимание достигнутое через свой опыт (пусть всегда с кучей ошибок, это нормально) с "просто освоенным" вообще нелепо.

Моя специальность 3D, поэтому я живу где-то в 15-м(?)  :)

Это да)) А теперь представте, как бы он был счастлив, если бы в его арсенале были современные методы и теории и потратив своё время он бы открыл нечто новое и гениальное)) За что бы получил Нобелевскую премию (хотя по математике её не дают, но ему бы дали)))
 ;)

если "чужие" знания это второй сорт, тогда что вы делаете на форуме? это типо признание себя троллём? :D

Мне это казалось привлекательным, но когда стал обдумывать как запостить - обнаружилось что ничего конкретного/внятного сказать не могу  :) В самом деле, что мы хотим? Пусть напр первые 100 элементов контейнера "читаются" а следующие 100 "пишутся" - в принципе нет проблем но надо ставить локер на "какие 100". Др. случай - читающий может захватить данные надолго - напрашивается пусть он сделает копию и занимается с ней, а потом обновит как писатель. Словом, нет разумной постановки

Может кому пригодится пара линков: http://www2.research.att.com/~bs/lock-free-vector.pdf
http://houndsblog.blogspot.com/2009/04/1.html
http://www.1024cores.net/