Дон Реба да, затова сложих кавички. истинския мутекс обаче е по-добро решение, защото няма да го сбъркаш без да искаш.
Не е по-добре, мутекса е системно извикване.
Атомарно вкарване на елемент в опашка – възможно ли е?
Дон Реба ако се откажеш от комунистическата обсесия за Справедливост, няма нужда от фифо и следователно от опашка изобщо. тогава става и с обикновен динамичен масив без лимит на размера. аз никога през живота си не съм ползвал фифо, може и да е затова
Точно тука "справедливостта" и в най-широкият ѝ смисъл няма нищо общо. Имам X сървър, който обработва заявките по реда на подаването им. Съответно на някои от заявките връща отговор, но асинхронно, когато обработи заявката. Отговорите се приемат асинхронно от отделна нишка.
Съответно, този който изпраща заявката, регистрира и callback функция, която да обработи отговора, когато той дойде.
Няма проблем callback-а да се записва на произволно място в масив. Само че, когато нишката, която обработва отговорите от сървъра получи отговор, ще трябва да претърсва целият масив дали има в него callback точно за тази заявка. Което си е хамалогия. А когато callback функциите са във FIFO, то когато дойде отговорът, нужният запис е на изхода на опашката, готов да бъде обработен.
Тоест в случая, сървърът е който определя нужните структури данни, а не някакви идеологически съображения.
Освен това, според твоите представи излиза, че аз трябва да съм против използването на стек, поради безкрайно несправедливата му природа... А аз си умирам да използвам стекове във всякакви алгоритми. 
Имам X сървър, който обработва заявките по реда на подаването им.
да де, а защо си решил точно по тоя ред да бъде? ако някаква система не се справя със заявките, така или иначе ще се препълни и умре. ако се справя, голямо натрупване няма да има, дали ще обработваш "справедливо" по реда на заявките, или "несправедливо" хващайки за ушите произволна заявка, все тая, всички ще бъдат обработени и то бързо, някой ще получи 10 мс закъснение, голям праз.
realinformatik Начи с атомарна инструкция ще стане, ако проблема може да се реши от една такава инструкция. Но ако проблема е съставен, т.е. за решението му трябват повече от една инструкция (без значение атомарна или не), ще трябва да локнеш поредицата от тези инструкции.
Нещата първо се разделят на операции и чак тогава почваш да мислиш за инструкции и каквото и да е друго.
Сега си мисля следното извращение, за което, обаче, трябва да имаш RTOS. При това такава RTOS, която да ти позволява да скеджулваш код (в случая пъхането в опашката) точно в началото на тайм слайса. И ако:
1. Си наясно колко е тайм слайса за конкретната ОС
2. Успееш да вкараш необходимия код, така, че да не излиза извън тайм слайса при worst case scenario
то тогава може да не ти трябват синхронизационни примитиви
Дон Реба Имам X сървър, който обработва заявките по реда на подаването им.
да де, а защо си решил точно по тоя ред да бъде?
Сървъра не съм го писал аз. Нито Х протокола. Аз пиша клиент. Но ако си представям правилно проблема, реда на обработка е важен, защото иначе ще се получи неправилна картинка в някои случаи. При това рандомно неправилна.
Понеже не ти разбирам много кода, го пренаписах. В примера само една нишка чете и произволен брой нишки пишат.
format PE console
section ".code" code readable executable
struc L {
.next dd ?
.data dd ?
}
macro strucdef [s] {
forward
virtual at 0
s s
sizeof.#s:
end virtual
irps r, eax,ebx,ecx,edx,esi,edi,ebp,esp \{
virtual at r
r\#.#s s
end virtual
\}
}
strucdef L
thread_write:
sub esp,0x10
mov [esp + 0],sizeof.L
call [malloc]
mov ecx,eax
@@:
mov eax,[list]
mov [ecx.L.next],eax
pause
lock
cmpxchg [list],ecx
jne @b
add esp,0x10
ret
thread_read:
sub esp,0x10
xor ecx,ecx
.1:
mov eax,[list]
pause
test eax,eax
jz .1
mov edx,[eax.L.next]
test edx,edx
jz .remove
cmp ecx,[edx.L.next]
je .bottom
@@:
mov eax,edx
mov edx,[edx.L.next]
cmp ecx,[edx.L.next]
jnz @b
.bottom:
mov [eax.L.next],ecx
mov eax,edx
add esp,0x10
ret
.remove:
lock
cmpxchg [list],edx
jne .1
add esp,0x10
ret
section ".data" data writeable
list dd 0
Не съм го тествал, но на око би трябвало да работи. Също така хийпа ти трябва да е защитен. Ако е мислен еднонишков може да бъгне. Може да се ползва втори списък от който да се пушват и попват елементи при алокация/деалокация.
BIGBUGEX Понеже не ти разбирам много кода, го пренаписах. В примера само една нишка чете и произволен брой нишки пишат.
Скрит код на асемблер
format PE console section ".code" code readable executable struc L { .next dd ? .data dd ? } macro strucdef [s] { forward virtual at 0 s s sizeof.#s: end virtual irps r, eax,ebx,ecx,edx,esi,edi,ebp,esp \{ virtual at r r\#.#s s end virtual \} } strucdef L thread_write: sub esp,0x10 mov [esp + 0],sizeof.L call [malloc] mov ecx,eax @@: mov eax,[list] mov [ecx.L.next],eax pause lock cmpxchg [list],ecx jne @b add esp,0x10 ret thread_read: sub esp,0x10 xor ecx,ecx .1: mov eax,[list] pause test eax,eax jz .1 mov edx,[eax.L.next] test edx,edx jz .remove cmp ecx,[edx.L.next] je .bottom @@: mov eax,edx mov edx,[edx.L.next] cmp ecx,[edx.L.next] jnz @b .bottom: mov [eax.L.next],ecx mov eax,edx add esp,0x10 ret .remove: lock cmpxchg [list],edx jne .1 add esp,0x10 ret section ".data" data writeable list dd 0Не съм го тествал, но на око би трябвало да работи. Също така хийпа ти трябва да е защитен. Ако е мислен еднонишков може да бъгне. Може да се ползва втори списък от който да се пушват и попват елементи при алокация/деалокация.
Нещо ваденето ми се струва странно. Променливата list началото на опашката ли е или краят? Ако вкарваш всеки път в нея, излиза, че е краят. Но тогава как взимаш елементи от началото?
Един съвет: конструкциите от вида [edx.L.next] са рожба на желанието да накараш асемблера да прилича на "нормалните езици". Тогава по-добре пиши на тях.
В твоята конструкция, двете точки представляват две различни същности. Първата – обикновено събиране, а втората е просто част от етикета.
На асемблер е по-добре да напишеш [edx + L.next] тъй като това отразява същността на операцията, че адресът се получава като сума от регистъра и отместването.
johnfound Нещо ваденето ми се струва странно. Променливата
listначалото на опашката ли е или краят? Ако вкарваш всеки път в нея, излиза, че е краят. Но тогава как взимаш елементи от началото?
Обхождам всички елементи до началото и изрязвам първия. И го връщам през еах.
johnfound Един съвет: конструкциите от вида
[edx.L.next]са рожба на желанието да накараш асемблера да прилича на "нормалните езици". Тогава по-добре пиши на тях.В твоята конструкция, двете точки представляват две различни същности. Първата – обикновено събиране, а втората е просто част от етикета.
На асемблер е по-добре да напишеш
[edx + L.next]тъй като това отразява същността на операцията, че адресът се получава като сума от регистъра и отместването.
Аз съм адвенсед, чуек. Ползвам уникални синтаксиси щом става дума за флат асемблер. Имам типове с автоматично подравняване и пакетиране като в С++.
BIGBUGEX Обхождам всички елементи до началото и изрязвам първия. И го връщам през еах.
Е-е-е! Не, така не ме кефи. Трябва да си помни първият елемент и да си почва от него директно. Почти съм го направил, ще го постна като е готово...
BIGBUGEX Аз съм адвенсед, чуек. Ползвам уникални синтаксиси щом става дума за флат асемблер. Имам типове с автоматично подравняване и пакетиране като в С++.
А бе, както ти харесва. То на флат асемблер съм виждал реализирани практически езици от високо ниво. Но въпросът е – защо? Ако искаш език от високо ниво – компилатора на C++ ще се справи по-добре при всички случаи.
Също е вариант при четене да се отписва целия списък, след което да се обръща и записва на друга локация, от където вече да се попват и обработват елементите от първи към последен. Така се избягва излишното обхождане от последен към първи при всяко четене.
edit: Е това имам предвид.
format PE console
section ".code" code readable executable
struc L {
.next dd ?
.data dd ?
}
macro strucdef [s] {
forward
virtual at 0
s s
sizeof.#s:
end virtual
irps r, eax,ebx,ecx,edx,esi,edi,ebp,esp \{
virtual at r
r\#.#s s
end virtual
\}
}
strucdef L
thread_write:
sub esp,0x10
mov [esp + 0],sizeof.L
call [malloc]
mov ecx,eax
@@:
mov eax,[list]
mov [ecx.L.next],eax
lock
cmpxchg [list],ecx
jne @b
add esp,0x10
ret
thread_read:
sub esp,0x10
xor ecx,ecx
mov eax,[list_r]
cmp ecx,eax
jne .read
@@:
mov eax,[list]
pause
test eax,eax
jz @b
@@:
lock
cmpxchg [list],ecx
jne @b
mov edx,[eax.L.next]
mov [eax.L.next],ecx
test edx,edx
jz .read
@@:
mov ecx,[edx.L.next]
mov [edx.L.next],eax
mov eax,edx
mov edx,ecx
test ecx,ecx
jnz @b
.read:
mov edx,[eax.L.next]
mov [list_r],edx
add esp,0x10
ret
section ".data" data writeable
list dd 0
align 64
list_r dd 0
Така си проверява в list_r дали има обърнати данни, ако няма изтегля списък, обръща го, и си попълва list_r. Всичко това разбира се на теория.
Чакай да изплющя това тук :
Use the rep movsd instruction instead of looping over the elements of L one by one in the strucdef macro. This will copy the entire structure in one go, which will likely be faster than looping.
Avoid using the pause instruction in the thread_write and thread_read functions. The pause instruction is useful for reducing contention when spinning on a lock, but it is not necessary in this code because the lock is already held.
Consider using a different synchronization mechanism instead of the lock cmpxchg instruction. This instruction is relatively slow compared to other options such as atomic compare-and-swap (CAS) operations or spin locks.
Use registers more effectively to minimize memory accesses. For example, consider using a register to store the value of list instead of reloading it from memory every time it is needed.
Use the align directive to ensure that data is properly aligned in memory, which can improve performance on some processors.
Optimize the inner loop of the thread_read function. This loop currently compares ecx to edx.L.next and jumps back to the top of the loop if they are not equal. This can be made faster by using a loop counter and breaking out of the loop once the counter reaches a certain value.
Consider using the rep stosd instruction to clear the memory occupied by the L structure in the thread_read function when it is removed from the list. This will be faster than looping over the elements of L one by one.
Use the align 4 directive to ensure that the list variable is aligned on a 4-byte boundary. This may improve performance on some processors.
Delegate Чакай да изплющя това тук :
Use the rep movsd instruction instead of looping over the elements of L one by one in the strucdef macro. This will copy the entire structure in one go, which will likely be faster than looping.
Avoid using the pause instruction in the thread_write and thread_read functions. The pause instruction is useful for reducing contention when spinning on a lock, but it is not necessary in this code because the lock is already held.
Consider using a different synchronization mechanism instead of the lock cmpxchg instruction. This instruction is relatively slow compared to other options such as atomic compare-and-swap (CAS) operations or spin locks.
Use registers more effectively to minimize memory accesses. For example, consider using a register to store the value of list instead of reloading it from memory every time it is needed.
Use the align directive to ensure that data is properly aligned in memory, which can improve performance on some processors.
Optimize the inner loop of the thread_read function. This loop currently compares ecx to edx.L.next and jumps back to the top of the loop if they are not equal. This can be made faster by using a loop counter and breaking out of the loop once the counter reaches a certain value.
Consider using the rep stosd instruction to clear the memory occupied by the L structure in the thread_read function when it is removed from the list. This will be faster than looping over the elements of L one by one.
Use the align 4 directive to ensure that the list variable is aligned on a 4-byte boundary. This may improve performance on some processors.
Това пък какво е??? На места звучи безсмислено. ИИ?
Да, звучи безсмислено. Въпроса е, има ли поне един добър съвет в цялата плява ? Ти и БЪГЕКСА кажете, не съм по асемблера.
Примера е непълен. Ако имаше стартиране на нишки и реална обработка щеше да е по-компетентен.
johnfound Това пък какво е??? На места звучи безсмислено. ИИ?
chatgpt
chatgpt Based on the description you provided, it looks like the thread_write and thread_read functions are intended to implement a thread-safe FIFO queue using a linked list. However, there are a few potential issues with the code as written:
The thread_write function does not check whether the call to malloc succeeded in allocating memory. If the allocation fails, the function will still attempt to insert the element into the list, which could cause a crash.
The thread_read function does not check whether the list is empty before attempting to remove an element. If the list is empty, the function will dereference a null pointer, which could cause a crash.
The thread_read function uses a spinlock to wait for an element to be added to the list. However, spinlocks can be inefficient if the contention for the lock is high, as they can consume a lot of CPU time.
The thread_read function does not protect against multiple threads calling it simultaneously. If multiple threads try to read from the queue at the same time, it could lead to data corruption or a crash.
I would suggest adding checks for null pointers and empty lists in both functions, and also considering using a different synchronization primitive, such as a mutex or a semaphore, to protect against concurrent access.
Това е коментар с малко повече контекст към последната версия.
BIGBUGEX Примера е непълен. Ако имаше стартиране на нишки и реална обработка щеше да е по-компетентен.
johnfound Това пък какво е??? На места звучи безсмислено. ИИ?
chatgpt
chatgpt Based on the description you provided, it looks like the thread_write and thread_read functions are intended to implement a thread-safe FIFO queue using a linked list. However, there are a few potential issues with the code as written:
The thread_write function does not check whether the call to malloc succeeded in allocating memory. If the allocation fails, the function will still attempt to insert the element into the list, which could cause a crash.
The thread_read function does not check whether the list is empty before attempting to remove an element. If the list is empty, the function will dereference a null pointer, which could cause a crash.
The thread_read function uses a spinlock to wait for an element to be added to the list. However, spinlocks can be inefficient if the contention for the lock is high, as they can consume a lot of CPU time.
The thread_read function does not protect against multiple threads calling it simultaneously. If multiple threads try to read from the queue at the same time, it could lead to data corruption or a crash.
I would suggest adding checks for null pointers and empty lists in both functions, and also considering using a different synchronization primitive, such as a mutex or a semaphore, to protect against concurrent access.
Това е коментар с малко повече контекст към последната версия.
А бе, за ИИ е много добре! Още не съм отишъл да го пробвам, но много го хвалят.
Попитах го за повече подробности относно проверката за празен списък. Явно не осъзнава, че със спинлока си гарантирам съществуващ елемент. Призна си грешката и почна да ме убеждава как спинлока е лошо нещо. Ще стане чуек от него.
BIGBUGEX Попитах го за повече подробности относно проверката за празен списък. Явно не осъзнава, че със спинлока си гарантирам съществуващ елемент. Призна си грешката и почна да ме убеждава как спинлока е лошо нещо. Ще стане чуек от него.
Започни нова сесия, повтори въпросите си и ще повтори всички грешки.
Ето го и моят окончателен вариант. Мисля, че се получи красиво.
При това и вкарването и изкарването са атомарни, тоест в опашката могат да вкарват няколко нишки и да изкарват няколко нишки:
Малко код с доста коментари
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 ; това е било последния елемент и опашката е в начално състояние.
mov eax, [esi+Element.next]
mov [pFirst], eax ; това не е последния елемент, така че си го връщаме в pFirst
.exit_ok:
mov eax, esi ; връщаме разкачения елемент
clc
return
.exit_empty:
stc
return
endp
Edit: Добавих една забравена инструкция във FetchElement: mov eax, [esi+Element.next]