Witam szukam struktury danych (kolekcji) która najlepiej się sprawdzi w następującej
sytuacji

a) ma przechowywać obiekty w dowolny sposób, jedyny warunek to konieczność
jednorazowego przeiterowania całej kolekcji w dowolnej kolejności.
b) wiele wątków równocześnie będzie zapisywać do tej kolekcji
c) jeden wątek będzie z niej odczytywał

Brak konieczności usuwania obiektów z kolekcji (kolekcja jest niszczona w całości)

Przy czym zapis i odczyt danych z kolekcji nie będzie równoczesny (najpierw zapisy, a
jak już się wszystkie wykonają, dopiero będzie szedł odczyt).

Ponieważ mam dość dobrze zdefiniowany i ograniczony model korzystania ze struktury,
myślę że powinno dać się skonstruować coś lock-free, ale jak na razie nie przychodzi
mi do głowy żadne rozwiązanie. Jakieś rady?

AdamK

do góry

On Feb 20, 1:41 pm, Adam Klobukowski <a...@g...com>
wrote:
> Witam szukam struktury danych (kolekcji) która najlepiej się sprawdzi w
następującej sytuacji
>
> a) ma przechowywać obiekty w dowolny sposób, jedyny warunek to konieczność
jednorazowego przeiterowania całej kolekcji w dowolnej kolejności.
> b) wiele wątków równocześnie będzie zapisywać do tej kolekcji
> c) jeden wątek będzie z niej odczytywał
>
> Brak konieczności usuwania obiektów z kolekcji (kolekcja jest niszczona w całości)
>
> Przy czym zapis i odczyt danych z kolekcji nie będzie równoczesny (najpierw zapisy,
a jak już się wszystkie wykonają, dopiero będzie szedł odczyt).
>
> Ponieważ mam dość dobrze zdefiniowany i ograniczony model korzystania ze struktury,
myślę że powinno dać się skonstruować coś lock-free, ale jak na razie nie przychodzi
mi do głowy żadne rozwiązanie.
> Jakieś rady?

Lista jednokierunkowa?

do góry

On Feb 20, 2:29 pm, Andrzej Jarzabek <a...@g...com>
wrote:
>
> Lista jednokierunkowa?

Szybie uzupełnienie: głównym problemem z implementacjami lock-free
listy jednokierunkowej jest problem ABA, ale jeśli nie usuwasz
elementów, to nie musisz się tym przejmować - powinieneś bez problemu
znaleźć odpowiednią implementację na atomowym swap-ie albo CAS.

do góry

W dniu poniedziałek, 20 lutego 2012, 14:41:41 UTC+1 użytkownik Adam Klobukowski
napisał:
> Witam szukam struktury danych (kolekcji) która najlepiej się sprawdzi w
następującej sytuacji
>
> a) ma przechowywać obiekty w dowolny sposób, jedyny warunek to konieczność
jednorazowego przeiterowania całej kolekcji w dowolnej kolejności.
> b) wiele wątków równocześnie będzie zapisywać do tej kolekcji
> c) jeden wątek będzie z niej odczytywał
>
> Przy czym zapis i odczyt danych z kolekcji nie będzie równoczesny (najpierw zapisy,
a jak już się wszystkie wykonają, dopiero będzie szedł odczyt).

Niech każdy wątek dopisuje dane do swojej lokalnej listy = brak
konieczności synchronizacji. Dopiero po zakończeniu pracy wątek
dokleja swoją listę do listy globalnej - tylko w tym miejscu jest
konieczne wzajemne wykluczanie.

w.

do góry

Dnia 20-02-2012 o 16:02:48 Wojciech Muła <w...@g...com>
napisał(a):

> W dniu poniedziałek, 20 lutego 2012, 14:41:41 UTC+1 użytkownik Adam
> Klobukowski napisał:
>> Witam szukam struktury danych (kolekcji) która najlepiej się sprawdzi w
>> następującej sytuacji
>>
>> a) ma przechowywać obiekty w dowolny sposób, jedyny warunek to
>> konieczność jednorazowego przeiterowania całej kolekcji w dowolnej
>> kolejności.
>> b) wiele wątków równocześnie będzie zapisywać do tej kolekcji
>> c) jeden wątek będzie z niej odczytywał
>>
>> Przy czym zapis i odczyt danych z kolekcji nie będzie równoczesny
>> (najpierw zapisy, a jak już się wszystkie wykonają, dopiero będzie
>> szedł odczyt).
>
> Niech każdy wątek dopisuje dane do swojej lokalnej listy = brak
> konieczności synchronizacji. Dopiero po zakończeniu pracy wątek
> dokleja swoją listę do listy globalnej - tylko w tym miejscu jest
> konieczne wzajemne wykluczanie.

hmm...
z wymagań nie widzę konieczności sklejania, wątek odczytujący może chyba
przeiterować sobie listę list?

--
Jordan Szubert

do góry

No tak, najciemniej pod latarnią jak zwykle :)

AdamK

do góry

Adam Klobukowski <a...@g...com> napisał(a):

> Przy czym zapis i odczyt danych z kolekcji nie b=EAdzie rownoczesny (najp=
> ierw zapisy, a jak ju=BF si=EA wszystkie wykonaj=B1, dopiero b=EAdzie szed=
> =B3 odczyt).

> Poniewa=BF mam do=B6=E6 dobrze zdefiniowany i ograniczony model korzystania=
> ze struktury, my=B6l=EA =BFe powinno da=E6 si=EA skonstruowa=E6 co=B6 lock=
> -free, ale jak na razie nie przychodzi mi do g=B3owy =BFadne rozwi=B1zanie.=
> Jakie=B6 rady?

Wyglada to na liste. Kazdy watek ma swoja liste, a potem scalenie.
Jednak to niekoniecznie bedzie lock-free bo moze dochodzic do
synchronizacji podczas dynamicznego przydzialu pamieci.

Jesli pytasz o lock-free to pewnie wazna jest wydajnosc. Wiec
moze warto pomyslec o liniowej tablicy. Jednorazowy przydzial wiekszej
pamieci niz bedzie potrzeba. Kazdy watek ma swoj punkt wejscia
w tablice i jest lock free. Scalac nie trzeba, wystarczy odpowiednia
zmiana indeksu zeby ominac niezapisane elementy.

Pozdrawiam


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

do góry

W dniu 2012-02-20 21:29, M.M. pisze:
> Adam Klobukowski<a...@g...com> napisał(a):
>
>> Przy czym zapis i odczyt danych z kolekcji nie b=EAdzie rownoczesny (najp=
>> ierw zapisy, a jak ju=BF si=EA wszystkie wykonaj=B1, dopiero b=EAdzie szed=
>> =B3 odczyt).
>
>> Poniewa=BF mam do=B6=E6 dobrze zdefiniowany i ograniczony model korzystania=
>> ze struktury, my=B6l=EA =BFe powinno da=E6 si=EA skonstruowa=E6 co=B6 lock=
>> -free, ale jak na razie nie przychodzi mi do g=B3owy =BFadne rozwi=B1zanie.=
>> Jakie=B6 rady?
>
> Wyglada to na liste. Kazdy watek ma swoja liste, a potem scalenie.
> Jednak to niekoniecznie bedzie lock-free bo moze dochodzic do
> synchronizacji podczas dynamicznego przydzialu pamieci.

Pule pamięci per wątek/lista powinny wystarczyć.

--
Paweł Kierski
n...@p...net

do góry