Чудя се тука. Възможно ли е да се направи добавяне на елементи в списък/опашка от няколко нишки, без да се използва mutex или друго подобно заключване, а само с използване на атомарни инструкции?
Някакви идеи/предложения?
Атомарно вкарване на елемент в опашка – възможно ли е?
Само ще добавяш ли ?
https://stackoverflow.com/questions/24563000/concurrently-appending-to-list-tail-without-a-mutex-lock
Delegate Само ще добавяш ли ?
https://stackoverflow.com/questions/24563000/concurrently-appending-to-list-tail-without-a-mutex-lock
Да, това и аз току що го четох. Но не, за съжаление искам и да вадя – дефакто FIFO. Но ще вади само една нишка гарантирано, а една или повече ще добавят.
Но тъй като в 99% от случаите и на ваденето и на вкарването ще работи дефакто само една и съща нишка, то не ми се иска да използвам мютекси за 1% от случаите. Но и не ми се иска да се отказвам от този 1%. 
Ако ползваше нормален език за кодене тия неща са ти направени на готово.
#83795
ТояДетВиНабиКанчето
Последно редактирано на 05.01.2023 от ТояДетВиНабиКанчето, видяно: 454 пъти.
Радетелю на свободата и справедливостта, заповядай имплементация подобна на линка от делегата от лошите микрософтци :
https://referencesource.microsoft.com/#mscorlib/system/Collections/Concurrent/ConcurrentDictionary.cs,5d24b6df7d0ea599.
Речник е, ама и за списък може да си го реализираш. С моето дебъгване на CQRS в продъкшън срещу една торба пари само с това мога да ти помогна :(
johnfound Чудя се тука. Възможно ли е да се направи добавяне на елементи в списък/опашка от няколко нишки, без да се използва mutex или друго подобно заключване, а само с използване на атомарни инструкции?
Някакви идеи/предложения?
Не е възможно. Дори всичко да ти е статично, ти трябват мин. 2 операции - преместване на опашката и поставяне на елемента.
ами правиш си мутекс със "атомарни инструкции" и това е. навремето ни казваха че не е възможно ако няма инструкция от типа атомарна размяна на стойности (xchg), после четох някъде че било възможно, но всъщост не ме интересува сериозно и не съм се задълбавал.
Дон Реба ами правиш си мутекс със "атомарни инструкции" и това е. навремето ни казваха че не е възможно ако няма инструкция от типа атомарна размяна на стойности (xchg), после четох някъде че било възможно, но всъщост не ме интересува сериозно и не съм се задълбавал.
Ами не искам с мютекс, защото мютекса първо означава една същност повече в кода. И второ, трябва да го чакаш, ако някой го е прихванал.
Е, аз всъщност го направих за вкарването на елементи в опашката.
; това се вкарва в опашката.
struct Element
.p_next dd ?
.data db 'тука са полезните данни на елемента'
ends
; алокейтваме елемента
stdcall GetMem, sizeof.Element
mov edi, eax
; запълваме полетата му.
xor eax, eax
mov [edi+Element.p_next], eax
; заместваме указателя към последния елемент в главната структура.
xor eax, eax
lock cmpxchg [esi+MainStructure.pLastElement], edi
je .element_ok ; ако там е било 0 значи това е последния елемент и завършваме.
; Ако вече е имало последен елемент/и ги проследяваме и се записваме след последния.
; На този етап, възможно след нашият елемент вече има записани други елементи.
.loop_last:
mov ecx, eax
xor eax, eax
lock cmpxchg [ecx+Element.p_next], ebx
jne .loop_last
.element_ok:
Тука интересното е, че във всеки един момент, указателя към последния елемент в главната структура [esi+MainStructure.pLastElement] може и да не сочи точно към последния елемент, но сочи някъде близо до него. Но самият списък винаги е коректен.
Сега трябва да измисля и как да махам елементи от списъка и всичко ще е супер.
lock cmpxchg esi+MainStructure.pLastElement, edi
ето ти го "мутекса", какво е това "не искам да вкарвам нови същности" . разликата с "истински" мутекс е че ползваш самия указател а не отделен флаг.
Дон Реба lock cmpxchg esi+MainStructure.pLastElement, edi
ето ти го "мутекса", какво е това "не искам да вкарвам нови същности" . разликата с "истински" мутекс е че ползваш самия указател а не отделен флаг.
М-м-м, не е точно така. Това не е мютекс, а атомарна инструкция. Малко по-различен синхронизиращ елемент и работи различно.
ТояДетВиНабиКанчето Радетелю на свободата и справедливостта, заповядай имплементация подобна на линка от делегата от лошите микрософтци :
https://referencesource.microsoft.com/#mscorlib/system/Collections/Concurrent/ConcurrentDictionary.cs,5d24b6df7d0ea599.
Речник е, ама и за списък може да си го реализираш. С моето дебъгване на CQRS в продъкшън срещу една торба пари само с това мога да ти помогна :(
Трябва да си изясниш какво е конкурентно, какво е паралелно и разликите между тях.
Rabin Ако ползваше нормален език за кодене тия неща са ти направени на готово.
Всъщност няма "нормален" език с подобна имплементация.
johnfound Чудя се тука. Възможно ли е да се направи добавяне на елементи в списък/опашка от няколко нишки, без да се използва mutex или друго подобно заключване, а само с използване на атомарни инструкции?
Някакви идеи/предложения?
Може, но проблемът е race condition. Има 2 положения, които трябва да решиш:
Data race - това е ситуация, при която достъпваш споделен ресурс конкурентно за четене и запис - това се решава с атомична операция
Race condition - това е ситуация, при която имаш достъпване на повече от една операция конкурентно, т.е. искаш да промениш стойността на повече от една атомична променлива с атомична такава.
johnfound Дон Реба lock cmpxchg esi+MainStructure.pLastElement, edi
ето ти го "мутекса", какво е това "не искам да вкарвам нови същности" . разликата с "истински" мутекс е че ползваш самия указател а не отделен флаг.
М-м-м, не е точно така. Това не е мютекс, а атомарна инструкция. Малко по-различен синхронизиращ елемент и работи различно.
да, затова сложих кавички. истинския мутекс обаче е по-добро решение, защото няма да го сбъркаш без да искаш. няма гаранция че хитрото ти решение няма дупка и тоя подход е оправдан само в специални случаи. аргумента "ама така не цикля върху флага" не е валиден, защото в добавянето имаш алокация, където бъди сигурен пада много по-яко циклене. ако толкова те е грижа за перформанса, слагаш нормален мутекс , алокираш чрез сингъл тред алокатор, и така с едно локване защитаваш както добавянето, така и алокацията, което предполагам ще е по-бърз вариант.
Само като видя че работата е linked list...
Stilgar Само като видя че работата е linked list...
На мене също не ми харесва да алокирам малки парчета. Мисля за вариант с организация на опашката в обикновен масив. Но тогава ще имам ограничение по броя на елементите. Което впрочем, може и да не ми пречи. Ще видим.
ако се откажеш от комунистическата обсесия за Справедливост, няма нужда от фифо и следователно от опашка изобщо. тогава става и с обикновен динамичен масив без лимит на размера. аз никога през живота си не съм ползвал фифо, може и да е затова
Дон Реба ако се откажеш от комунистическата обсесия за Справедливост, няма нужда от фифо и следователно от опашка изобщо. тогава става и с обикновен динамичен масив без лимит на размера. аз никога през живота си не съм ползвал фифо, може и да е затова
Еми ако не си писал на асемблер или на стеков език е нормално, асемблера тренира определени модели на мислене изключително добре но после влизаш образно казано в конфликт с хора на които моделирането е тренирано от езици на по-високо ниво.
Това се преживява и в преходите от процедурно програмиране към ООП и т.н., особено интересно става при патерните които имат основната заслуга за сравнително бавното израстване на масовия програмист.
абе писал съм и на асемблер, ама не виждам нещо различно. според мен няма употреба на ФИФО в която пряко или косвено да не е замесена думата "справедливост" , тя самата дума "опашка" си навява асоциации достатъчно
Начи с атомарна инструкция ще стане, ако проблема може да се реши от една такава инструкция. Но ако проблема е съставен, т.е. за решението му трябват повече от една инструкция (без значение атомарна или не), ще трябва да локнеш поредицата от тези инструкции.