johnfound

palavrov

...но все пак това, че не може конкурентно да се вадят елементи си е проблем.

Вкарването на елементи в опашката е еднозначно понятие – вкарваш ги и толкова. Затова и много нишки могат да вкарват едновременно и без проблеми елементи. И за елементите и за опашката е все едно кой вкарва елементите, важното е в какъв ред.

Изваждането на елементи обаче е съвършено друга бира. Тука важното е какво точно смяташ да правиш с тези елементи.

В моят случай нишката, която ги тегли може да извади един или няколко последователни елемента, докато си свърши работата. До този момент, другите нишки ще виждат списъка като празен, за да не развалят реда на елементите нужни на първата нишка. След това, като им дойде реда, те ще видят опашката пак пълна и ще могат да изтеглят своите един или няколко последователни елемента.

Но всъщност реално в проекта, в който ще използвам това, ще има само една нишка, която ще тегли елементи от опашката. Тегленето го направих thread-safe, просто защото частично се пресича с вкарването на елементи при обновяването на указателите.

Ами осира се читавата имплементация заради частен случай. Напъни се малко и може да те осени как да направиш и ваденето на елементи да се усеща, че има някой който добавя и да се изчаква.

Мисля, че също може да не ползваш pFirst за sentinel от което хем кода ще стане по ясен, хем ще може да се развържеш от изискването .next да е винаги на на отместване нула.

realinformatik

palavrov

Бравос, взимам си думите назад. Кода ти е ОК. Конкурентно добавяне ще накъса опашката на парчета но след известно време ще ги залепи всички в правилния ред. Омотването ми дойде, че първо не знаех как работи cmpxchg и второ не обърнах внимание, че pFirst се попълва при създаване на списъка и се ползва като sentinel + не на последно място неоправдана арогантност за което се извинявам. Доста елегантно се е получило но все пак това, че не може конкурентно да се вадят елементи си е проблем.

Ехе за пръв път някой в тоя форум да деескалира и да адмитне грешка.

Еми никога не е късно да станеш за резил, кой ми е крив, че не внимавам и се заяждам без да съм разбрал кое как работи ...

Накарах аи-то да направи лок фрee имплементация.

chatgpt

Sure, here is an example of a lock-free FIFO queue implemented using a linked list in x86 assembly language:

; Linked list element
struc element {
	.next	dd ?
	.data	dd ?
}

; FIFO queue
struc queue {
	.head		dd ?
	.tail		dd ?
}

; Initialize a queue
queue_init:
	xor	eax,eax
	mov	[ecx.queue.head],eax
	mov	[ecx.queue.tail],eax
	ret

; Push an element onto the queue
queue_push:
	mov	eax,[ecx.queue.tail]
	mov	[eax.element.next],edx
	
	@@:
	mov	ecx,[ecx.queue.tail]
	mov	eax,[ecx.element.next]
	lock cmpxchg [ecx.queue.tail],edx
	jne	@b
	
	ret

; Pop an element from the queue
queue_pop:
	mov	ecx,[ecx.queue.head]
	mov	eax,[ecx.element.next]
	
	test	eax,eax
	jz	.exit
	
	mov	[ecx.element.next],0
	lock cmpxchg [ecx.queue.head],eax
	jne	.exit
	
	.exit:
	mov	eax,ecx
	ret

This implementation uses the lock cmpxchg instruction to atomically update the head and tail pointers of the queue. The queue_push function uses a spinloop to retry the update until it succeeds, while the queue_pop function checks whether the queue is empty before attempting to remove an element.

One potential issue with this implementation is that the queue_pop function does not wait for an element to be added to the queue if it is empty. If you need to block until an element becomes available, you could consider using a different synchronization primitive, such as a semaphore or a condition variable, to wait for the queue to become non-empty.

Харесало ми е синтаксиса. Тва след една две версии ще го направят частно. Няма да има достъп за простосмъртни.

Иване, до обяд да си изтрил тролските коментари или ще ви еба майката на жалкия форум завинаги този път и дори забрани за писане няма да ме спрат.

ЩеВиЕбаМайката

Иване, до обяд да си изтрил тролските коментари или ще ви еба майката на жалкия форум завинаги този път и дори забрани за писане няма да ме спрат.

стиви, бягай в бегемама, там като се изпокарат кокошките трият не само тролските коментари, ами цели теми, много ще ти хареса

johnfound

Записът в [pFirst] ще се случи само един единствен път, когато [pLast] == pFirst.

При всички комбинации опашката остава в коректно състояние.

Не е вярно, това трябва да става всеки път, когато опашката е празна, т.е. при премахване. Да не говорим, че pFirst и pLast репрезентират само 1 опашка.

bvbfan

johnfound

Записът в [pFirst] ще се случи само един единствен път, когато [pLast] == pFirst.

При всички комбинации опашката остава в коректно състояние.

Не е вярно, това трябва да става всеки път, когато опашката е празна, т.е. при премахване. Да не говорим, че pFirst и pLast репрезентират само 1 опашка.

Ами тя тогава е празна опашката, когато [pLast] == pFirst. (Обърни внимание на квадратните скоби). И да, всеки път, когато е празна опашката, първият вкаран елемент се записва в pFirst.

ЩеВиЕбаМайката

Иване, до обяд да си изтрил тролските коментари или ще ви еба майката на жалкия форум завинаги този път и дори забрани за писане няма да ме спрат.

Ся пък от какво изперка? Малко по-конкретно не може ли, ами всеки път трябва да гадая какво е искал да каже автора...

johnfound

bvbfan

johnfound

Записът в [pFirst] ще се случи само един единствен път, когато [pLast] == pFirst.

При всички комбинации опашката остава в коректно състояние.

Не е вярно, това трябва да става всеки път, когато опашката е празна, т.е. при премахване. Да не говорим, че pFirst и pLast репрезентират само 1 опашка.

Ами тя тогава е празна опашката, когато [pLast] == pFirst. (Обърни внимание на квадратните скоби). И да, всеки път, когато е празна опашката, първият вкаран елемент се записва в pFirst.

Именно, може да се изпразни между двете атомични операции.

bvbfan

johnfound

bvbfan

johnfound

Записът в [pFirst] ще се случи само един единствен път, когато [pLast] == pFirst.

При всички комбинации опашката остава в коректно състояние.

Не е вярно, това трябва да става всеки път, когато опашката е празна, т.е. при премахване. Да не говорим, че pFirst и pLast репрезентират само 1 опашка.

Ами тя тогава е празна опашката, когато [pLast] == pFirst. (Обърни внимание на квадратните скоби). И да, всеки път, когато е празна опашката, първият вкаран елемент се записва в pFirst.

Именно, може да се изпразни между двете атомични операции.

В смисъл? Кое да се изпразни? Как? Човек, четеца на мисли ми е ремонт, няма части и скоро няма да стане.

Дон Реба

ЩеВиЕбаМайката

Иване, до обяд да си изтрил тролските коментари или ще ви еба майката на жалкия форум завинаги този път и дори забрани за писане няма да ме спрат.

стиви, бягай в бегемама, там като се изпокарат кокошките трият не само тролските коментари, ами цели теми, много ще ти хареса

Реба, това е психично болния Един от многото, бахти и тъпаците сте да не му различавате 100-те му акаунта. Чорбар и други никове. Съберете пари и го пратете да се лекува.

ТояДетВиНабиКанчето

Дон Реба

ЩеВиЕбаМайката

Иване, до обяд да си изтрил тролските коментари или ще ви еба майката на жалкия форум завинаги този път и дори забрани за писане няма да ме спрат.

стиви, бягай в бегемама, там като се изпокарат кокошките трият не само тролските коментари, ами цели теми, много ще ти хареса

Реба, това е психично болния Един от многото, бахти и тъпаците сте да не му различавате 100-те му акаунта. Чорбар и други никове. Съберете пари и го пратете да се лекува.

Чей бе - ЩеВиЕбаМайката и Чорбар не са мои акаунти. Аз съм честен лаладжия.

Пак ли требе да показвам снимки на всичките си акаунти? 🙄