<bgdev />^free

Дон Реба

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

Не е по-добре, мутекса е системно извикване.

Дон Реба

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

Точно тука "справедливостта" и в най-широкият ѝ смисъл няма нищо общо. Имам 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. Всичко това разбира се на теория.

Spinlock

Чакай да изплющя това тук :

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.

Това е коментар с малко повече контекст към последната версия.

А бе, за ИИ е много добре! Още не съм отишъл да го пробвам, но много го хвалят.

Оставете го AI, той греши и то много.

Попитах го за повече подробности относно проверката за празен списък. Явно не осъзнава, че със спинлока си гарантирам съществуващ елемент. Призна си грешката и почна да ме убеждава как спинлока е лошо нещо. Ще стане чуек от него.

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]