Mam tablicę
maks: array[0..9] of record
ileCyfr: integer;
liczba: int64
end;
zdefiniowaną przed pętlą Tparallel.For. Do tej tablicy wszystkie wątki zapisują jednocześnie. Jak zrobić, żeby w momencie zapisywania zablokować dostęp innych wątków do niej? Bez blokady dostaję nieprawidłowe niskie wartości. Interlocked.Add do tej tablicy nie ma zastosowania tutaj bo nie robię dodawania tylko dowolną wartość przypisuję do tablicy dzielonej.
Może coś takiego:
To samo w innych wątkach i już.
Tak się nie da bo mi pętla pójdzie do przodu i pominie obliczenie jeśli nie może mieć dostępu bo inny wątek go zablokował. Trzeba zatrzymać wątek do czasu gdy drugi go zwolni. Zwykle to się robi przez semafory, sekcje krytyczne itp. Myślałem że po to jest biblioteka system.threading, żeby to uprościć. Tablica temp jest lokalna zadeklarowana wewnątrz Tparaller.for
for k:= 0 to 9 do // tu dać wait i lock;
if temp[k]> maks[k].ileCyfr
then
begin
maks[k].ileCyfr:= temp[k];
maks[k].liczba:= i;
end; // end lock;
Sekcje krytyczne czyli TCriticalSection a kod pomiędzy Acquire a Release (najlepiej w bloku try finally)
lub zwykłe TThread.Synchronize To drugie to najprostsze ale znacznie gorsze rozwiązanie nie wiem co tam dokładnie robisz ale może nawet spowodować że kod mimo wątków wykona się wolniej niż bez.
Proponuję przeczytać najpierw:
https://pl.wikipedia.org/wiki/Sekcja_krytyczna
a następnie http://wwwold.fizyka.umk.pl/~jacek/dydaktyka/rad/rad4_watki.pdf (zwłaszcza str. 14 - sekcje krytyczne)
http://www.ii.uni.wroc.pl/~wzychla/ra2223/so2.html - pkt. 2 "synchronizacja". Wprawdzie przykłady są w C, ale artykuł dotyczy ogólnych mechanizmów oferowanych przez WinApi, w związku z czym tak samo to można odpalić równie dobrze na Delphi
i jeszcze coś z naszego forum - Jak w Delphi zrealizować obliczenia równoległe przy zastosowaniu wielowątkowości ?
Aczkolwiek przy prostej apce, moim zdaniem to, o czym pisze @robertz68 też się sprawdzi ;)
Nie sprawdzi się bo ogólnie zwykły kod byłby
if not zablokowany
//przełączy wątki
then
zablokuj (itd....)
Ale system operacyjny przełączy wątki między instrukcjami i spowoduje zapis nieprawidłowych wartości. Własnie po to sa te funkcje API windows żeby blokowac wątki i nie dopuścić do takich rzeczy.
Programowanie wątków istnieje od początku istnienia Delphi ale ja nie po to korzystam z " Tparallel.For" żeby się uczyć tego skomplikowanego mechanizmu użycia wątków z blokowaniem dostępu do wspólnych zmiennych. Musi być jakiś prosty sposób blokowania bo inaczej ta biblioteka "system.threading"nadpisująca API jest bezcelowa.
@Patryk27: pozwolisz że zamienię komentarz na zwykłą odpowiedź bo może komuś się to przyda?
Jak oflagować taką sytuację wg mnie mocno zależy w jakim celu używa się wątków.
Można na szybko opisać kilka scenariuszy dlaczego używa się wątków (na 100% znajdziecie dużo innych powodów):
Pierwszy przypadek prosty, nie uruchamiaj wątku gdy na coś jeszcze czekasz, jak już uruchomisz to w końcu dostaniesz jakiś wynik - lub błąd ale to też jest w końcu jakaś odpowiedź).
Drugi, o dziwo też prosty, uruchamiasz wątki i resztę zrzucasz na system operacyjny.
Trzeci scenariusz jednak może być mocno skomplikowany. Tak naprawdę jest to zwykłe wykonywanie kodu szeregowo ale "wciśnięte" w wątki. Wszystko jest ok, gdy następny wątek nie musi operować na danych poprzedniego lub sobie bez nich poradzi. Oczywiście są wait-y itp ale, przynajmniej w bibliotece PPL wydaje mi się że nie działają idealnie.
Ostatnio, właśni dzięki bibliotece PPL nastała duża moda na wątki i uważam że dobrze, bo programy w których się je używa działają zdecydowanie płynniej ale właśnie, nie zawsze działają dobrze.
Oczywiście, jest alternatywa, czyli zwykłe wątki. Niestety są dużo trudniejsze ale też mają dużo większe możliwości o czym wspominają koledzy.
Jako suplement (heh, suplement do postu - to chyba już przegięcie :) ) napiszę jak ostatnio walczyłem z wątkami.
Napisałem prostą aplikację FMX dla bardzo niedużej sieci sklepów. W każdym ze sklepów pracuje prościutki serwer REST z dostępem do bazy danych towarów i dokumentów zakupowych.
W sklepach pracownicy odpowiedzialni za zakupy mają prostą aplikację na androida gdzie skanują kod kreskowy towaru (są też wersje pod Windows). W odpowiedzi dostają informację ile towaru jest na innych sklepach, po ile te sklepy kupują towar i po ile sprzedają. Dodatkowo widzą także ostatnie 10 zakupów. Korzyści są niesamowite dla klienta, ale mniejsza z tym.
Idealnie pasowało mi aby poszczególne serwery pytać w wątkach, tak też to zrobiłem. Niestety - nie ma żadnych szans aby to dobrze działało. Kombinowałem w każdą stronę. Wszystko się zacinało.
Wg. mnie problemem jest Indy bo tego używa Delphi w komunikacji REST. Równoległe wywołanie kilku procedur wręcz miesza danymi miedzy sklepami. Normalnie jakby jakieś wycieki były.
Dla testu stworzyłem osobne zmienne dla każdego sklepu (bez sensu trochę) aby mieć pewność że to nie kwestia "przenikania" danych między zmiennymi w procedurach wątków. Nic nie pomogło. Zostało Indy.
No i najważniejsze, były to wątki PPL.
Oczywiście, wróciłem do procedur szeregowych i wszystko działa idealnie.
Jak już koledzy wspomnieli, nie zawsze wątki są najlepsze - niestety.
Ja bym to widział inaczej, moim zdaniem poniższy pseudokod powinien się sprawdzić (przy założeniu, że zmienna sterująca synchronizacją wątków będzie boolean wielkości 1 bajta. Jakby dać tam coś innego, np. integer, to jest ryzyko, że przełączenie wątków nastąpi w chwili, w której część zmiennej zostanie zmieniona, a część pozostanie w poprzedniej wartości, przez co powstanie kaszana. Tak czy siak - lepszą opcją od zmiennej, jest skorzystanie ze specjalnych mechanizmów synchronizacji wątków, o których @kAzek i ja wspomnieliśmy wcześniej.
while (blokada = TRUE) czekaj_az_sie_odblikuje;
blokada := TRUE;
wykonaj_niebezpieczne_operacje;
blokada:= FALSE;
EDIT - lepiej jednak tak nie rób, patrz następny post by @Patryk27
@cerrato: Twój kod jest podatny na data race nawet przy założeniu, że boolean jest atomowy:
while (blokada) {
// czekaj
}
// tutaj w międzyczasie (już po zakończeniu pętli, a przed przypisaniem) drugi wątek zmienia flagę na `true`
blokada := true;
// i boom, na tym etapie masz przynajmniej dwa wątki działające razem mimo semafora
Aby zrealizować to poprawnie, należałoby wykorzystać wspieraną hardware'owo instrukcję compare and swap, która wykonuje całą operację atomowo.
mogę zrobić test ale to jest tylko przypuszczenie, nie ma gwarancji że to będzie zawsze działać
while blokada do;
//tu system operacyjny może przełączyć wątki
blokada := TRUE;
(...blok danych)
blokada:= false
A pierwotny problem pozostał czyli jak łatwo zapisać blokadę zmiennych globalnych w wątku z użyciem "Tparallel.For" żeby nie wracać się do początku czyli użycia funkcji API jakie istnieją od kilkunastu lat.
Tak jak myślałem program zwrócił błędne wyniki
Zadanie jest takie
There are ten parts to the problem.
(a) Which ten-digit perfect square contains the most zeros?
(b) Which ten-digit perfect square contains the most ones?
(c) Which ten-digit perfect square contains the most twos?
And so on, up to:
(j) Which ten-digit perfect square contains the most nines?
Przy jednym wątku dostaję wynik prawidłowy
minuty=4
sekundy=1
milisekundy=752
najwięcej cyfr dla 0 wynosi 8 dla 1600000000
najwięcej cyfr dla 1 wynosi 6 dla 1101111489
najwięcej cyfr dla 2 wynosi 6 dla 1254222225
najwięcej cyfr dla 3 wynosi 6 dla 3333330225
najwięcej cyfr dla 4 wynosi 7 dla 4434494464
najwięcej cyfr dla 5 wynosi 6 dla 4555575025
najwięcej cyfr dla 6 wynosi 6 dla 4666665969
najwięcej cyfr dla 7 wynosi 6 dla 7907477776
najwięcej cyfr dla 8 wynosi 6 dla 3828886884
najwięcej cyfr dla 9 wynosi 6 dla 2909199969
przy użyciu blokowania wątków metodą zmiennej logicznej (program podaję niżej)
minuty=0
sekundy=7
milisekundy=605
najwięcej cyfr dla 0 wynosi 7 dla 1024000000
najwięcej cyfr dla 1 wynosi 6 dla 1101111489
najwięcej cyfr dla 2 wynosi 6 dla 1254222225
najwięcej cyfr dla 3 wynosi 5 dla 1333637361
najwięcej cyfr dla 4 wynosi 5 dla 1244043441
najwięcej cyfr dla 5 wynosi 4 dla 1045552225
najwięcej cyfr dla 6 wynosi 4 dla 1025664676
najwięcej cyfr dla 7 wynosi 4 dla 1005777796
najwięcej cyfr dla 8 wynosi 5 dla 1288881801
najwięcej cyfr dla 9 wynosi 4 dla 1019971969
bez blokowania zmiennej wspólnej
minuty=0
sekundy=17
milisekundy=630
najwięcej cyfr dla 0 wynosi 5 dla 1090980900
najwięcej cyfr dla 1 wynosi 3 dla 1011685249
najwięcej cyfr dla 2 wynosi 3 dla 1028292489
najwięcej cyfr dla 3 wynosi 3 dla 1368334081
najwięcej cyfr dla 4 wynosi 3 dla 1214034649
najwięcej cyfr dla 5 wynosi 4 dla 1345055625
najwięcej cyfr dla 6 wynosi 4 dla 1245666436
najwięcej cyfr dla 7 wynosi 4 dla 1326707776
najwięcej cyfr dla 8 wynosi 2 dla 1006983289
najwięcej cyfr dla 9 wynosi 3 dla 1063999161
program button1 to zwykły przebieg, button2 to przebieg równoległy, są dwa guziki i memo na formularzu
uses
system.threading;
function IdKw(liczba: int64): boolean;
var
p: int64;
begin
p:= round(sqrt(liczba));
IdKw:=p*p=liczba;
end;
procedure TForm1.Button1Click(Sender: TObject);
var
maks: array[0..9] of record
ileCyfr: integer;
liczba: int64
end;
temp: array[0..9] of integer;
i,k: int64;
c: integer;
s: string;
hours, minutes, seconds, millisec: word;
start,koniec,timeDiff: tdatetime;
begin
start:= now;
for i:=0 to 9 do
begin
maks[i].ileCyfr:= 0;
maks[i].liczba:= 0;
end;
for i := 1000000000 to 9999999999 do
begin
for k := 0 to 9 do
temp[k]:= 0;
if IdKw(i)
then
begin
s:=IntToStr(i);
for k:= 0 to 9 do
begin
c:= StrToInt(s[k+1]);
temp[c]:= temp[c]+1;
end;
for k:= 0 to 9 do
if temp[k]> maks[k].ileCyfr
then
begin
maks[k].ileCyfr:= temp[k];
maks[k].liczba:= i
end;
end;
end;
memo1.Lines.Add('koniec');
koniec:= now;
timeDiff:= koniec - start;
DecodeTime(timeDiff, hours, minutes, seconds, millisec);
memo1.Lines.Add('godziny='+IntToStr(hours));
memo1.Lines.Add('minuty='+IntToStr(minutes));
memo1.Lines.Add('sekundy='+IntToStr(seconds));
memo1.Lines.Add('milisekundy='+IntToStr(millisec));
for k:= 0 to 9 do
if maks[k].liczba > 0
then
memo1.Lines.Add('najwięcej cyfr dla '+IntToStr(k)+' wynosi '+
IntToStr(maks[k].ileCyfr)+' dla '+IntToStr(maks[k].liczba))
end;
procedure TForm1.Button2Click(Sender: TObject);
var
maks: array[0..9] of record
ileCyfr: integer;
liczba: int64
end;
i,k: int64;
hours, minutes, seconds, millisec: word;
start,koniec,timeDiff: tdatetime;
blokada: boolean;
begin
start:= now; blokada:= false;
for i:=0 to 9 do
begin
maks[i].ileCyfr:= 0;
maks[i].liczba:= 0;
end;
Tparallel.For(1000000000,9999999999, procedure (i:integer)
var
k,c : integer;
s: string;
temp: array[0..9] of integer;
begin
for k := 0 to 9 do
temp[k]:= 0;
if IdKw(i)
then
begin
s:=IntToStr(i);
for k:= 0 to 9 do
begin
c:= StrToInt(s[k+1]);
temp[c]:= temp[c]+1;
end;
while blokada do; //test lock
blokada:=true; // lock;
for k:= 0 to 9 do
if temp[k]> maks[k].ileCyfr
then
begin
maks[k].ileCyfr:= temp[k];
maks[k].liczba:= i;
end;
blokada:= false // end lock;
end;
end );
memo1.Lines.Add('koniec');
koniec:= now;
timeDiff:= koniec - start;
DecodeTime(timeDiff, hours, minutes, seconds, millisec);
memo1.Lines.Add('godziny='+IntToStr(hours));
memo1.Lines.Add('minuty='+IntToStr(minutes));
memo1.Lines.Add('sekundy='+IntToStr(seconds));
memo1.Lines.Add('milisekundy='+IntToStr(millisec));
for k:= 0 to 9 do
if maks[k].liczba > 0
then
memo1.Lines.Add('najwięcej cyfr dla '+IntToStr(k)+' wynosi '+
IntToStr(maks[k].ileCyfr)+' dla '+IntToStr(maks[k].liczba))
end;
end.
Ktoś sugerował na forum angielskim dawno temu, że w Delphi TParallel.For nie zadziała z żadną sekcją krytyczną i że trzeba wyprowadzić tablicę lokalną z obliczeniami dla każdego wątku a potem zrobić dodatkowe obliczenia już proste biorąc która z wyprowadzonych tablic ma maksimum dla danego indeksu. To jednak komplikuje, bo naprzód nie wiem jaka jest składnia żeby wątek wyprowadził tablicę. Potem nie wiem ile będzie wątków bo to zależy od komputera ile ma rdzeni procesor. Jak bym to wiedział to reszta jest prosta.
Jestem na wakacjach i siedzę na telefonie, nie chce analizować całego Twojego kodu i pomijając wielowątkowość to czy nie lepiej byłoby na początek zoptymalizować wyszukiwanie tych liczb?
Sprzątasz wszystkie liczby w zakresie a to trochę marnowanie czasu skoro interesują Ciebie tylko pierwiastki tej samej liczby. Znajdź min i Max (sqrt z zakresu) i sporządzają liczby
x*x;
Inc(x);
Przy wartościach tej wielkości pominiesz sprawdzanie wielu niepotrzebnych wartości.
Ps. To zerowanie wartości wektora temp powinno być po sprawdzeniu że liczba się nadaje. Kolejna strata czasu przy zerwaniu dla każdej iteracji.
Gotowego rozwiązania nie podam bo siedzę na telefonie ale do wątków pod Delphi proponowałbym Omni Thread Library. Ciężko mi teraz szukać ale jest masa przykładów i bogata dokumentacja. Zerknij tutaj
http://www.omnithreadlibrary.com/book/chap08.html
Clarc napisał(a):
Gotowego rozwiązania nie podam bo siedzę na telefonie ale do wątków pod Delphi proponowałbym Omni Thread Library. Ciężko mi teraz szukać ale jest masa przykładów i bogata dokumentacja. Zerknij tutaj
http://www.omnithreadlibrary.com/book/chap08.html
Ostatecznie zrezygnowałem z użycia Parallel.for bo zawiera błędy. Sekcje krytyczne też dawały nieprawidłowy wynik. Wynik udało mi się uzyskać z użyciem TThread. Każdy wątek dostał osobną zmienną globalną do wyprowadzenia wyników, następnie połączyłem wyniki z wątków. Dla czterech rdzeni przyspieszenie czasu przebiegu jest czterokrotne. Jeżeli już mamy program zoptymalizowany pod względem czasu wykonania, używamy najlepszego algorytmu (nie tak jak w moim przypadku kiedy się walnąłem o prostą rzecz i czas wykonania zwiększył się tysiąc razy), to możemy jeszcze użyć przyspieszenie kilkukrotnego w zależności od tego ile mamy rdzeni. Problem jest tylko z tym, że muszę powielać kod dla każdego wątku osobno. Po raz pierwszy mój program użył prawie 100% mocy procesora!! Wcześniej dochodził tylko do 25% bo działał na jednym wątku.** Ucieszyło mnie to**.
Tutaj jest ogólny schemat jak to zrobić. Podaję to bo może się komuś przydać.
procedure TForm1.MyButtonClick(Sender: TObject);
var
tasks: array of ITask;
i,k,: Integer;
wynikiRdzeni: array [1..4]of wynik; //cztery wątki
maks: wynik;
begin
Setlength (tasks ,4) //w zależności od ilości rdzeni procesora
tasks[0] := TTask.Create (procedure ()
begin
tu dać fragment pętli,
obliczenia i wyprowadzenie wartości do zmiennej globalnej wynikiRdzeni[1]
end);
tasks[0].Start;
tasks[1] := TTask.Create (procedure ()
begin
tu dac kolejny fragment pętli
obliczenia i wyprowadzenie wartości do zmiennej globalnej wynikiRdzeni[2]
end);
tasks[1].Start;
tasks[2] := TTask.Create (procedure ()
begin
tu dac kolejny fragment pętli
obliczenia i wyprowadzenie wartości do zmiennej globalnej wynikiRdzeni[3]
end);
tasks[2].Start;
tasks[3] := TTask.Create (procedure ()
begin
tu dac kolejny fragment pętli
obliczenia i wyprowadzenie wartości do zmiennej globalnej wynikiRdzeni[4]
end);
tasks[3].Start;
TTask.WaitForAll(tasks);
tu dokonujemy obliczeń połaczenia wyników tablic
a tu jest cały program
uses
system.threading, math;
type
podziałLiczby= array[0..9] of integer;
zakresy= array[1..4] of record
dół, góra: int64
end;
wynik= array[0..9] of record
ileCyfr: integer;
liczba: int64
end;
function podzielNaZakresy(a,b: int64): zakresy; //dzieli zakres pętli for dla rozłożenia na cztery rdzenie procesora
var
i, iloraz: int64;
wynik: zakresy;
begin
iloraz:= (b-a+1)div 4;
for i := 1 to 4 do
begin
wynik[i].dół:= (i-1)*iloraz+a;
if i<4
then
wynik[i].góra:= (i-1)*iloraz+a+iloraz-1
else
wynik[i].góra:= b;
end;
result:=wynik
end;
function rozłóżLiczbę(i: int64):podziałLiczby; //liczy wystąpienia cyfr w liczbie
var
k,c : integer;
s: string;
temp: podziałLiczby;
begin
for k := 0 to 9 do
temp[k]:= 0;
s:=IntToStr(i);
for k:= 0 to 9 do
begin
c:= StrToInt(s[k+1]);
temp[c]:= temp[c]+1;
end;
result:= temp;
end;
procedure TForm1.Button2Click(Sender: TObject);
var
maks: wynik;
wynikiRdzeni: array[1..4] of wynik;
zakresyRdzeni: zakresy;
tasks: array of ITask;
i,k: int64;
hours, minutes, seconds, millisec: word;
start,koniec,timeDiff: tdatetime;
begin
start:= now;
for i:=0 to 9 do
maks[i].ileCyfr:= 0;
for i := 1 to 4 do
for k := 0 to 9 do
wynikiRdzeni[i,k].ileCyfr:=0;
Setlength(tasks ,4);
zakresyRdzeni:= podzielNaZakresy(1000000000,9999999999);
tasks[0]:= TTask.Create (procedure ()
var
temp: podziałLiczby;
i,k: int64;
begin
For i:= zakresyRdzeni[1].dół to zakresyRdzeni[1].góra do
begin
if sqr(round(sqrt(i))) = i
then
begin
temp:= rozłóżLiczbę(i);
for k:= 0 to 9 do
if temp[k]> wynikiRdzeni[1,k].ileCyfr
then
begin
wynikiRdzeni[1,k].ileCyfr:= temp[k];
wynikiRdzeni[1,k].liczba:= i
end;
end;
end
end);
tasks[0].Start;
tasks[1]:= TTask.Create (procedure ()
var
temp: podziałLiczby;
i,k: int64;
begin
For i:= zakresyRdzeni[2].dół to zakresyRdzeni[2].góra do
begin
if sqr(round(sqrt(i))) = i
then
begin
temp:= rozłóżLiczbę(i);
for k:= 0 to 9 do
if temp[k]> wynikiRdzeni[2,k].ileCyfr
then
begin
wynikiRdzeni[2,k].ileCyfr:= temp[k];
wynikiRdzeni[2,k].liczba:= i
end;
end;
end
end);
tasks[1].Start;
tasks[2]:= TTask.Create (procedure ()
var
temp: podziałLiczby;
i,k: int64;
begin
For i:= zakresyRdzeni[3].dół to zakresyRdzeni[3].góra do
begin
if sqr(round(sqrt(i))) = i
then
begin
temp:= rozłóżLiczbę(i);
for k:= 0 to 9 do
if temp[k]> wynikiRdzeni[3,k].ileCyfr
then
begin
wynikiRdzeni[3,k].ileCyfr:= temp[k];
wynikiRdzeni[3,k].liczba:= i
end;
end;
end
end);
tasks[2].Start;
tasks[3]:= TTask.Create (procedure ()
var
temp: podziałLiczby;
i,k: int64;
begin
For i:= zakresyRdzeni[4].dół to zakresyRdzeni[4].góra do
begin
if sqr(round(sqrt(i))) = i
then
begin
temp:= rozłóżLiczbę(i);
for k:= 0 to 9 do
if temp[k]> wynikiRdzeni[4,k].ileCyfr
then
begin
wynikiRdzeni[4,k].ileCyfr:= temp[k];
wynikiRdzeni[4,k].liczba:= i
end;
end;
end
end);
tasks[3].Start;
TTask.WaitForAll(tasks);
//zbieramy dane z wątków razem
for i:= 0 to 9 do
for k:=1 to 4 do
if wynikiRdzeni[k,i].ileCyfr>maks[i].ileCyfr
then
begin
maks[i].ileCyfr:= wynikiRdzeni[k,i].ileCyfr;
maks[i].liczba:= wynikiRdzeni[k,i].liczba
end;
koniec:= now;
timeDiff:= koniec - start;
DecodeTime(timeDiff, hours, minutes, seconds, millisec);
memo1.Lines.Add('godziny='+IntToStr(hours));
memo1.Lines.Add('minuty='+IntToStr(minutes));
memo1.Lines.Add('sekundy='+IntToStr(seconds));
memo1.Lines.Add('milisekundy='+IntToStr(millisec));
for k:= 0 to 9 do
if maks[k].ileCyfr > 0
then
memo1.Lines.Add('najwięcej cyfr dla '+IntToStr(k)+' wynosi '+
IntToStr(maks[k].ileCyfr)+' dla '+IntToStr(maks[k].liczba))
end;