bvbfan
Последно редактирано на 08.01.2023 от bvbfan, видяно: 642 пъти. #83943
Не е добър, race condition все още присъства, поне на 2 места.
Нека покажа единият:
xor eax, eax
lock cmpxchg [pLast], edi
; Ако вече е имало последен елемент/и ги проследяваме и се записваме след последния.
.loop_last:
mov ecx, eax
xor eax, eax
lock cmpxchg [ecx + Element.pNext], ebx
jne .loop_last
Между 2-те атомични операции присъства възможността за race condition, а именно last e обновен преди next.
Ето го и моят окончателен вариант. Мисля, че се получи красиво.
Не е добър, race condition все още присъства, поне на 2 места.
Нека покажа единият:
xor eax, eax
lock cmpxchg [pLast], edi
; Ако вече е имало последен елемент/и ги проследяваме и се записваме след последния.
.loop_last:
mov ecx, eax
xor eax, eax
lock cmpxchg [ecx + Element.pNext], ebx
jne .loop_last
Между 2-те атомични операции присъства възможността за race condition, а именно last e обновен преди next.
Това е без значение. След първият запис, който е атомарен, ако се появят нови елементи, те ще се заместват в [pLast] и нищо лошо няма да се случи. И след това коректно ще си проследят опашката и ще се запишат след последният, пак атомарно.
Записът в [pFirst] ще се случи само един единствен път, когато [pLast] == pFirst.
При всички комбинации опашката остава в коректно състояние.
Ето го и моят окончателен вариант. Мисля, че се получи красиво.
При това и вкарването и изкарването са атомарни, тоест в опашката могат да вкарват няколко нишки и да изкарват няколко нишки:
Малко код с доста коментари
struct Element
.pNext dd ?
.pData:
ends
pFirst dd ?
pLast dd ?
proc InitQueue
begin
lea eax, [pFirst]
mov [pLast], eax ; Тук е половината магия. Ако опашката е празна,
; [pLast] съдържа указател към pFirst.
xor eax, eax
mov [pFirst], eax
return
endp
proc AddToQueue
begin
; алокейтваме елемента
stdcall GetMem, sizeof.Element
mov edi, eax
; запълваме полетата му.
xor eax, eax
mov [edi+Element.pNext], eax
; атомарно заместваме указателя към последния елемент в главната структура.
; Да се отбележи, че [pLast] никога не е равно на 0.
; Долната инструкция ще запише edi в [pLast] и ще върне в eax указател към
; предишния последен елеемнт, или указател към pFirst ако опашката е празна.
xor eax, eax
lock cmpxchg [pLast], edi
; Ако вече е имало последен елемент/и ги проследяваме и се записваме след последния.
.loop_last:
mov ecx, eax
xor eax, eax
lock cmpxchg [ecx + Element.pNext], ebx
jne .loop_last
return
endp
proc FetchElement
begin
xor esi, esi
xchg [pFirst], esi ;xchg е винаги атомарен и без lock.
test esi, esi
jz .exit_empty
; разкачаме елемента от опашката
mov eax, esi ; 2 варианта: Или това е последния елемент в опашката (esi == [pLast])
lea edx, [pFirst] ; тогава нулираме до начално състояние, или има друг елемент и тогава е
lock cmpxchg [pLast], edx ; безопасно да манипулираме ListElement.pNext полето.
je .exit_ok ; това е било последния елемент и опашката е в начално състояние.
; Тук е възможно race condition. Ако нов елемент е записан в [pLast], но не е успял
; да се закачи още към съответния [Element.next]. Просто чакаме и ще се закачи:
xor eax, eax
.wait:
pause xchg [esi+Element.next], eax
test eax, eax
jz .wait
mov [pFirst], eax ; Това е новият първи елемент.
.exit_ok:
mov eax, esi ; връщаме разкачения елемент
clc
return
.exit_empty:
stc
return
endp
Edit: Добавих една забравена инструкция във FetchElement: mov eax, [esi+Element.next]
Edit2: Все пак имаше на едно място race condition и си иска малко изчакване за синхронизация (етикета FetchElement.wait).
Не ти разбирам кода много. Как така слагаш фалшиви елементи като адреса на pFirst.
; атомарно заместваме указателя към последния елемент в главната структура.
; Да се отбележи, че [pLast] никога не е равно на 0.
; Долната инструкция ще запише edi в [pLast] и ще върне в eax указател към
; предишния последен елеемнт, или указател към pFirst ако опашката е празна.
xor eax, eax
lock cmpxchg [pLast], edi
Доколкото разбирам тая инструкция не прави нищо повече от това да зареди eax с pLast. Няма промяна на pLast защото eаx е 0.
Не ти разбирам кода много. Как така слагаш фалшиви елементи като адреса на pFirst.
; атомарно заместваме указателя към последния елемент в главната структура.
; Да се отбележи, че [pLast] никога не е равно на 0.
; Долната инструкция ще запише edi в [pLast] и ще върне в eax указател към
; предишния последен елеемнт, или указател към pFirst ако опашката е празна.
xor eax, eax
lock cmpxchg [pLast], edi
Доколкото разбирам тая инструкция не прави нищо повече от това да зареди eax с pLast. Няма промяна на pLast защото eаx е 0.
ПС: В следващия цикъл от къде идва ebx?
Всъщност тази инструкция е грешна. Трябва да е просто xchg.
Регистърът ebx не се използва. Трябва да е edi. Просто това е адаптирана версия за по-лесно разбиране, а кода от който копирам е по-сложен (и неясен) и използва ebx.
Ето това излиза последната версия:
struct Element
.pNext dd ?
.pData:
ends
pFirst dd ?
pLast dd ?
proc InitQueue
begin
lea eax, [pFirst]
mov [pLast], eax ; Тук е половината магия. Ако опашката е празна,
; [pLast] съдържа указател към pFirst.
xor eax, eax
mov [pFirst], eax
return
endp
proc AddToQueue
begin
; алокейтваме елемента
stdcall GetMem, sizeof.Element
mov edi, eax
; запълваме полетата му.
xor eax, eax
mov [edi + Element.pNext], eax
; атомарно заместваме указателя към последния елемент в [pLast].
; Да се отбележи, че [pLast] никога не е равно на 0.
; Долните инструкции ще запишат edi в [pLast] и ще върне в eax указател към
; предишния последен елеемнт, или указател към pFirst ако опашката е празна.
mov eax, edi
xchg [pLast], eax
; Ако вече е имало последен елемент/и ги проследяваме и се записваме след последния.
.loop_last:
mov ecx, eax
xor eax, eax
lock cmpxchg [ecx + Element.pNext], edi
jne .loop_last
return
endp
proc FetchElement
begin
xor esi, esi
xchg [pFirst], esi ;xchg е винаги атомарен и без lock.
test esi, esi
jz .exit_empty
; разкачаме елемента от опашката
mov eax, esi ; 2 варианта: Или това е последния елемент в опашката (esi == [pLast])
lea edx, [pFirst] ; тогава нулираме до начално състояние, или има друг елемент и тогава е
lock cmpxchg [pLast], edx ; безопасно да манипулираме ListElement.pNext полето.
je .exit_ok ; това е било последния елемент и опашката е в начално състояние.
; Тук е възможно race condition. Ако нов елемент е записан в [pLast], но не е успял
; да се закачи още към съответния [Element.next]. Просто чакаме и ще се закачи:
xor eax, eax
.wait:
pause xchg [esi+Element.next], eax
test eax, eax
jz .wait
mov [pFirst], eax ; Това е новият първи елемент.
.exit_ok:
mov eax, esi ; връщаме разкачения елемент
clc
return
.exit_empty:
stc
return
endp
waldorf
Създадено на 08.01.2023, видяно: 578 пъти. #83962
Виж тук как се прави:
https://enqueuezero.com/lock-free-queues.html
Последния ти сорс въобще не е thread safe и си е направо бъглив. Ще пиша после детайли, че жената ме тормози да ме води на МОЛа ...
struct Element
.pNext dd ?
.pData:
ends
pFirst dd ?
pLast dd ?
proc InitQueue
begin
lea eax, [pFirst]
mov [pLast], eax ; Тук е половината магия. Ако опашката е празна,
; [pLast] съдържа указател към pFirst.
xor eax, eax
mov [pFirst], eax
return
endp
proc AddToQueue
begin
; алокейтваме елемента
stdcall GetMem, sizeof.Element
mov edi, eax
; запълваме полетата му.
xor eax, eax
mov [edi + Element.pNext], eax
; атомарно заместваме указателя към последния елемент в [pLast].
; Да се отбележи, че [pLast] никога не е равно на 0.
; Долните инструкции ще запишат edi в [pLast] и ще върне в eax указател към
; предишния последен елеемнт, или указател към pFirst ако опашката е празна.
mov eax, edi
xchg [pLast], eax
; Ако вече е имало последен елемент/и ги проследяваме и се записваме след последния.
.loop_last:
mov ecx, eax
xor eax, eax
lock cmpxchg [ecx + Element.pNext], edi
jne .loop_last
return
endp
proc FetchElement
begin
xor esi, esi
xchg [pFirst], esi ;xchg е винаги атомарен и без lock.
test esi, esi
jz .exit_empty
; разкачаме елемента от опашката
mov eax, esi ; 2 варианта: Или това е последния елемент в опашката (esi == [pLast])
lea edx, [pFirst] ; тогава нулираме до начално състояние, или има друг елемент и тогава е
lock cmpxchg [pLast], edx ; безопасно да манипулираме ListElement.pNext полето.
je .exit_ok ; това е било последния елемент и опашката е в начално състояние.
; Тук е възможно race condition. Ако нов елемент е записан в [pLast], но не е успял
; да се закачи още към съответния [Element.next]. Просто чакаме и ще се закачи:
xor eax, eax
.wait:
pause xchg [esi+Element.next], eax
test eax, eax
jz .wait
mov [pFirst], eax ; Това е новият първи елемент.
.exit_ok:
mov eax, esi ; връщаме разкачения елемент
clc
return
.exit_empty:
stc
return
endp
Споко де, да не мислиш, че е по приятно да обикаляш 4 часа в МОЛа вместо да ловиш бъгове?!
Значи, в FetchElement зануляваш pFirst докато не излезеш от тази функция (процедура по асемблерски) т.е. ако друга нишка се опита да работи с този списък ще се омота, че списъка е празен. Отделен проблем е, че стила ти на писане е прекалено усложнен което е предпоставка за лесно вкарване и трудно оправяне на бъгове. Също така факта, че пропускаш такива бъгове
е симптом, че е по добре да не се занимаваш с многонишково програмиране - и то както и асемблера не е за всеки. Това са ми изводите от диагонално поглеждане на кода, 6-то ми чувство нашепва, че ако задълбая ще изленат и още проблеми.
От гледна точка на алгоритми + структури от данни това да имаш указатели към главата и опашката на single linked queue не е добра идея. По удачно е да използваш ring вместо queue. Преди няколко години се бях заиграл да пиша RTOS и този проблем го реших с ring като указателя към него беше към последния елемент а не към първия - това позволява много бързо добавяне и изваждане тип FIFO.
Значи, в FetchElement зануляваш pFirst докато не излезеш от тази функция (процедура по асемблерски) т.е. ако друга нишка се опита да работи с този списък ще се омота, че списъка е празен.
Естествено, че ако друга нишка се опита да вади елементи от опашката, тя ще ѝ се стори празна. Това е така по дизайн, а не по недоглеждане.
Отделен проблем е, че стила ти на писане е прекалено усложнен което е предпоставка за лесно вкарване и трудно оправяне на бъгове. Също така факта, че пропускаш такива бъгове
е симптом, че е по добре да не се занимаваш с многонишково програмиране - и то както и асемблера не е за всеки.
За стила на писане – в тоя код има 34 инструкции и купчина коментари. AddToQueue има 11 инструкции, а FetchElement има 18 инструкции. Ако за толкова код ти трябва някакъв специален стил на писане, може би това е симптом, че е по-добре да не се занимаваш с четене на асемблерски код.
Това са ми изводите от диагонално поглеждане на кода, 6-то ми чувство нашепва, че ако задълбая ще изленат и още проблеми.
А моето шесто чувство ми подсказва, че познах, като написах в предишният пост, че нищо конкретно няма да представиш. Просто защото кода е правилен.
waldorf
Създадено на 08.01.2023, видяно: 509 пъти. #83976
Значи, в FetchElement зануляваш pFirst докато не излезеш от тази функция (процедура по асемблерски) т.е. ако друга нишка се опита да работи с този списък ще се омота, че списъка е празен.
Естествено, че ако друга нишка се опита да вади елементи от опашката, тя ще ѝ се стори празна. Това е така по дизайн, а не по недоглеждане.
Ако подобна глупост е по дизайн то е редно най малкото да има коментар. Между другото ако това наистина си го предвидил като функционалност то си направил пишман мутекс без да ползваш мутекс. Отстрани погледнато си е просто бъг.
Отделен проблем е, че стила ти на писане е прекалено усложнен което е предпоставка за лесно вкарване и трудно оправяне на бъгове. Също така факта, че пропускаш такива бъгове
е симптом, че е по добре да не се занимаваш с многонишково програмиране - и то както и асемблера не е за всеки.
За стила на писане – в тоя код има 34 инструкции и купчина коментари. AddToQueue има 11 инструкции, а FetchElement има 18 инструкции. Ако за толкова код ти трябва някакъв специален стил на писане, може би това е симптом, че е по-добре да не се занимаваш с четене на асемблерски код.
Това признавам беше провокация. Не, че не е истина де. Но това е субективно и в края на краищата всеки има право на лош вкус по отношение на кода пък и не само.
Това са ми изводите от диагонално поглеждане на кода, 6-то ми чувство нашепва, че ако задълбая ще изленат и още проблеми.
А моето шесто чувство ми подсказва, че познах, като написах в предишният пост, че нищо конкретно няма да представиш. Просто защото кода е правилен.
Еми явно си тънък познавач, евала!
waldorf
Създадено на 08.01.2023, видяно: 504 пъти. #83978
Направих си труда да ти погледна малко по задълбочено кода. Ми, човек, зле е, направо си е смешка.
AddToQueue също е бъглива. Въобще не е thread safe. Като запишеш ново алокирания елемент в pLast на практика си разрушил queue-то за всички останали нишки които също се опитват да добавят конкурентно в него. Не се прави така. Погледни хубаво линка който ти пратих и виж как се прави.
А най големия майтап е, че никъде не записваш в pFirst като добавяш първия елемент и той ще си остане винаги нула. Ако на това му казваш работещ и правилен код по добре въобще не се занимавай с програмиране. Или пак ще ме убеждаваш, че то това е по дизайн ...
Направих си труда да ти погледна малко по задълбочено кода. Ми, човек, зле е, направо си е смешка.
AddToQueue също е бъглива. Въобще не е thread safe. Като запишеш ново алокирания елемент в pLast на практика си разрушил queue-то за всички останали нишки които също се опитват да добавят конкурентно в него. Не се прави така. Погледни хубаво линка който ти пратих и виж как се прави.
А най големия майтап е, че никъде не записваш в pFirst като добавяш първия елемент и той ще си остане винаги нула. Ако на това му казваш работещ и правилен код по добре въобще не се занимавай с програмиране. Или пак ще ме убеждаваш, че то това е по дизайн ...
Само ще кажа, че нищо не си разбрал. В pFirst, разбира се, се записва и то само и единствено първият елемент. Както си му е редът.
И хем коментари съм писал как точно става и пак нищо не си разбрал.
Същото касае и записът в pLast. Точно там всичко си е наред.
Иди прочети пак кода, дано го разбереш. Може да задаваш и въпроси.
loop_last ще направи null pointer exception на втората итерация.
pFirst "видях" как го инициализираш - не ми харесва, прекалено tricky и неочевадно е. Хем го ползваш за sentinel за край на опашката, хем разчиташ, че указателя към следващата структура е винаги първи в елемента - за какво въобще тогава пишеш това [...+Elemnt.next] като то никога няма да работи ако не е нула?
Как се ескейпват квадратните скоби?
waldorf
Създадено на 08.01.2023, видяно: 484 пъти. #83981
Пиша глупости и аз ... не знаех, че cmpxchg работи само с eax - егати безумието.
loop_last ще направи null pointer exception на втората итерация.
pFirst "видях" как го инициализираш - не ми харесва, прекалено tricky и неочевадно е. Хем го ползваш за sentinel за край на опашката, хем разчиташ, че указателя към следващата структура е винаги първи в елемента - за какво въобще тогава пишеш това [...+Elemnt.next] като то никога няма да работи ако не е нула?
Как се ескейпват квадратните скоби?
loop_last няма да направи null pointer exception никога. Чети още малко и това ще го "видиш". (подсказка – как работи cmpxchg?) Виждам, че си го забелязал.
[+Element.next] го пиша за яснота на кода. Ако е 0, това просто е удобно. Но съвсем не е задължително. Просто ще изисква друга дефиниция на pFirst.
Инлайн кода се огражда със "backtick" символа: "`". Тогава квадратните скоби не се приемат за форматиране на връзка.
waldorf
Създадено на 08.01.2023, видяно: 466 пъти. #83983
Бравос, взимам си думите назад. Кода ти е ОК. Конкурентно добавяне ще накъса опашката на парчета но след известно време ще ги залепи всички в правилния ред. Омотването ми дойде, че първо не знаех как работи cmpxchg и второ не обърнах внимание, че pFirst се попълва при създаване на списъка и се ползва като sentinel + не на последно място неоправдана арогантност за което се извинявам. Доста елегантно се е получило но все пак това, че не може конкурентно да се вадят елементи си е проблем.
Бравос, взимам си думите назад. Кода ти е ОК. Конкурентно добавяне ще накъса опашката на парчета но след известно време ще ги залепи всички в правилния ред. Омотването ми дойде, че първо не знаех как работи cmpxchg и второ не обърнах внимание, че pFirst се попълва при създаване на списъка и се ползва като sentinel + не на последно място неоправдана арогантност за което се извинявам. Доста елегантно се е получило но все пак това, че не може конкурентно да се вадят елементи си е проблем.
Ехе за пръв път някой в тоя форум да деескалира и да адмитне грешка.
...но все пак това, че не може конкурентно да се вадят елементи си е проблем.
Вкарването на елементи в опашката е еднозначно понятие – вкарваш ги и толкова. Затова и много нишки могат да вкарват едновременно и без проблеми елементи. И за елементите и за опашката е все едно кой вкарва елементите, важното е в какъв ред.
Изваждането на елементи обаче е съвършено друга бира. Тука важното е какво точно смяташ да правиш с тези елементи.
В моят случай нишката, която ги тегли може да извади един или няколко последователни елемента, докато си свърши работата. До този момент, другите нишки ще виждат списъка като празен, за да не развалят реда на елементите нужни на първата нишка. След това, като им дойде реда, те ще видят опашката пак пълна и ще могат да изтеглят своите един или няколко последователни елемента.
Но всъщност реално в проекта, в който ще използвам това, ще има само една нишка, която ще тегли елементи от опашката. Тегленето го направих thread-safe, просто защото частично се пресича с вкарването на елементи при обновяването на указателите.