<f...@N...gazeta.pl> napisał(a):

> np dwa zbiory botow na wspolnej mapie moga byc tez
> zrownoleglone o ile te zbiory sa wzajemnie rozlaczne
>
> np jeden zbior ruszaq sie po lewej stronie mapy a drugi
> po prawej i miedzy nimi jest przerwa - jest to trudniejszy
> przypadek bo takie boty na wspolnej mapie sa potencjalnie
> kolizyjne i trzebaby normalnie synchronizowac 'mutexami'

Ciekawe zadanie do przemyslenia. Gdyby nie synchronizowac to
dwa boty by mogly znalezc sie w tym samym miejscu mapy:

watek A)
bot nr 123 sprawdza czy pole nr 34 jest wolne - i jest wolne
watek B)
bor nr 234 sprawdza czy pole nr 34 jest wolne - i jest wolne
a wiec:
watek A)
bot nr 123 wchodzi na pole 34 - bo jest wolne
watek B)
bot nr 234 wchodzi na pole 34 - bo jest wolne
I mamy problem.

> ale dzieki wykorzystaniu tego ze ich dzialania na ramke
> odznaczaja sie pewna lokalnoscia mozna je wlasnie
> przestrzennie podzielic na nie zachodzace w sensie dzialania
> obszary i puscic na watkach bezkolizyjnie- o tym pislem
Mozna tak zrobic, ale widze problem z korzysciami. Np kazdy
bot moze wykonac ruch odlegly o 2-3 pola. A wiec zerujemy jakas
tablice pol i jesli jakis bot potencjalnie moze wejsc na pole
to inkrementujemy, np.:

tablica_pol = empty;
forall( bot in boty )
forall( pole in bot.pola )
tablica_pol[pole] ++ ;

Potem kazdy watek ifem sprawdza czy w polu docelowym bota jest jedynka,
czy wieksza wartosc. Jesli jest jedynka to wykonuje bez synchronizacji,
jesli wartosc wieksza, to wykonuje z synchronizacja - mozna zminimalizowac
ilosc synchronizacji. Niestety, jak pisalem wyzej, jest problem z korzysciami,
gdyz najpierw w jednym watku trzeba taka tablice zbudowac.


Jesli algorytm zrownoleglany ma zlozonosc np. N^2, a algorytm budujacy
jakas wstepna strukture danych umozliajaca bezkolizyjne (albo prawie
bezkolizyjne) wykonanie ma zloznosc N, to taki zabieg moze sie oplacac,
gdyz potencjalnie pozbywamy sie N^2 synchronizacji koszem algorytmu o
zlozonosci N.

Jesli oba algorytmy maja podobna zlozonosc, np. oba maja linowa, to
taki zabieg nie przyniesie korzysci.


> - wydaje sie ze poszukiwania takich bezkolizyjnych metod
> zrownoleglania to dobre podejscie - wymaga dobrej orientacji
> co sie dzieje w programie (programowania na slepo raczej
> nie przjedzie) i jest troche 'dirty' ale nie ma strat
> na synchronizacji
Tez tak uwazam.

Pozdrawiam
No i wszystkiego najlepszego :)


--
Wysłano z serwisu Usenet w portalu Gazeta.pl -> http://www.gazeta.pl/usenet/