On 28.06.2013 22:12, A.L. wrote:
> On Fri, 28 Jun 2013 15:36:11 +0200, Michoo<m...@v...pl> wrote:

>>> P.S. Zadam to samo zadanko co kiedys: procesy a, b, c, d, e, f
>>>
>>> Wzajemne wykluczanie: (a,c), (c,f), (a,b), (b,e), (b,d), (c,d), (e,f)
>>>
>>> Zaprojeltowac rozwiazanie bez deadlocku i starvation free
>>
>> Ale już Ci na nie odpowiadałem:
>> - tworzysz 6 muteksów (A-F)
>> - sporządzasz dla każdego procesu listę z którymi się wyklucza
>> - sortujesz te listy w kolejności a-f
>>
>> Każdy proces wchodząc do sekcji krytycznej pobiera potrzebne mu blokady
>> w kolejności A-F. Rozwiązuje to problem wzajemnego wykluczania([*]).
>> Problem zagłodzenia nie wystąpi na pewno gdy muteksy budzą w kolejności
>> FIFO, przy braku tej gwarancji do zagłodzenia może dojść[**] więc
>> najlepiej chyba ją zapewnić przez kombinację mutex+lista+condition
>> variable (dopóki !pierwszy na liście).
>>
>>
>> [*] Czyim imieniem nazywamy ten algorytm - nie pamiętam. Jest to daleka
>> wariacja Lamporta.
>> [**] Choćby a i b "wymieniające się" muteksem A mogą zagłodzić c.
>
> Niezupelnie o to chodzi, bo wejscie w proces a powinno blokowac
> procesy b i c ale nie powinno blokowac procesow d, e, f

Nie znam (a przynajmniej nie przypominam sobie) innego "standardowego"
algorytmu rozwiązującego ten problem w sposób przejrzysty a jednocześnie
optymalny pod względem wydajnościowym.

Jakbym miał to zrealizować i powyższe rozwiązanie byłoby
niewystarczające zrobił bym to za pomocą monitora z porównaniem maski
aktualnie działających procesów z wymaganą maską jako warunkiem.

Kwestie zagłodzenia w takim wypadku trzeba rozwiązywać osobno już
zależnie od tego co rozumiemy przez "zagłodzenie"[*] i jakie są schematy
współpracy między wątkami.

Być może statyczny przydział, być może wstrzymywanie procesów które
wybijają się poza zakładany histogram - za mało danych aby odpowiedzieć.

[*] Czy mamy ograniczenia typu "minimum 1 wywołanie na k jednostek
czasu", czy raczej "od a1 do a2 % czasu wykonania w k jednostkach", czy
też kombinację z ewentualnymi dodatkowymi warunkami. Ogólnie wchodzimy
opuszczamy już tutaj problem synchronizacji a wchodzimy w sferę
szeregowania zadań.

--
Pozdrawiam
Michoo

do góry

Dnia pamiętnego Mon, 01 Jul 2013 00:26:42 +0200, Michoo wyjmując peta
oznajmił:

> On 28.06.2013 22:12, A.L. wrote:
>> On Fri, 28 Jun 2013 15:36:11 +0200, Michoo<m...@v...pl> wrote:
>
>>>> P.S. Zadam to samo zadanko co kiedys: procesy a, b, c, d, e, f
>>>>
>>>> Wzajemne wykluczanie: (a,c), (c,f), (a,b), (b,e), (b,d), (c,d), (e,f)
>>>>
>>>> Zaprojeltowac rozwiazanie bez deadlocku i starvation free
>>>
>>> Ale już Ci na nie odpowiadałem:
>>> - tworzysz 6 muteksów (A-F)
>>> - sporządzasz dla każdego procesu listę z którymi się wyklucza
>>> - sortujesz te listy w kolejności a-f

Nawet nie trzeba sortować. Try_lock załatwia problem dealocku, tak:

mając do zamknięcia n,m,l,... zamyka się n, a potem try_lockiem
pozostałe. Jeżeli któryś się nie zamknie, bo zajęty, zwalnia się już
zamknięte i ten który był zajęty jest pierwszy do kolejnej rundy -
przez co proces czeka na tym locku aż się zwolni, bo pierwszy jest lock().

Algorytm bombarduje szynę atomikami, ale jest poprawny.

Do zagłodzenia może dojść.

>>> Każdy proces wchodząc do sekcji krytycznej pobiera potrzebne mu blokady
>>> w kolejności A-F. Rozwiązuje to problem wzajemnego wykluczania([*]).
>>> Problem zagłodzenia nie wystąpi na pewno gdy muteksy budzą w kolejności
>>> FIFO, przy braku tej gwarancji do zagłodzenia może dojść[**] więc
>>> najlepiej chyba ją zapewnić przez kombinację mutex+lista+condition
>>> variable (dopóki !pierwszy na liście).

Nope. Trzeba jeszcze dopisać się do list dzielonych z pozostałymi
procesami, inaczej one też mogą zagłodzić/być zagłodzone, np.
mapa list z maską jako kluczem...

>>> [*] Czyim imieniem nazywamy ten algorytm - nie pamiętam. Jest to daleka
>>> wariacja Lamporta.
>>> [**] Choćby a i b "wymieniające się" muteksem A mogą zagłodzić c.

... a wtedy a i b dopiszą się do kolejki z c i c będzie pierwsze.

Nie przemyślałem tylko jak to zaimplementować, bo trzeba jeszcze chronić
same kolejki o ile nie ma kolejek lock-free z peek() i mieć jakąś
politykę reagowania na a przed b na jednej liście a b przed a na drugiej
- random() dałby radę. O ile czegoś na szybko nie pomyliłem, wychodzi
graf pierwszeństwa, który można potraktować w sposób uproszczony,
byle spraweidliwy.

>> Niezupelnie o to chodzi, bo wejscie w proces a powinno blokowac
>> procesy b i c ale nie powinno blokowac procesow d, e, f
>
> Nie znam (a przynajmniej nie przypominam sobie) innego "standardowego"
> algorytmu rozwiązującego ten problem w sposób przejrzysty a jednocześnie
> optymalny pod względem wydajnościowym.

Wiele algorytmów "wątkowych" nie ma ani standardu ani nazwy. Część
ma, czasami nawet patent jak dzielone shared_ptr-y.

> Kwestie zagłodzenia w takim wypadku trzeba rozwiązywać osobno już
> zależnie od tego co rozumiemy przez "zagłodzenie"[*] i jakie są schematy
> współpracy między wątkami.

Wydaje mi się już pisałeś, na czym może polegać zagłodzenie w
prostym przypadku, w bardziej skomplikowanych konfiguracjach
jedne grupy wątków mogą głodzić inne.

Schematy współpracy: skoro się wykluczają mogą w ramach wykluczenia
przekazywać dane. Albo mogą mieć kolejki, które są liśćmi w drzewie
kolejności locków, więc są pomijalne dla poprawności.

> Być może statyczny przydział, być może wstrzymywanie procesów które
> wybijają się poza zakładany histogram - za mało danych aby odpowiedzieć.

Być może FIFO procesów i ten bliżej wyjścia ma pierwszeństwo. Kombinuję,
ale ja jakoś nie widzę w tym problemie poważnego problemu.

> [*] Czy mamy ograniczenia typu "minimum 1 wywołanie na k jednostek
> czasu", czy raczej "od a1 do a2 % czasu wykonania w k jednostkach", czy
> też kombinację z ewentualnymi dodatkowymi warunkami. Ogólnie wchodzimy
> opuszczamy już tutaj problem synchronizacji a wchodzimy w sferę
> szeregowania zadań.

Tak jakby z zagłodzeniem było kiedykolwiek inaczej. Problem polega
na tym, że problem jest jeden i algorytm jest jeden, ale musi
spełniać oba warunki: działać, czyli być bez race'ów i deadlocków, i ma
nie zagłodzić.

--
Edek

do góry

On Sun, 30 Jun 2013 23:47:19 +0000 (UTC), Edek
<e...@g...com> wrote:

>Tak jakby z zagłodzeniem było kiedykolwiek inaczej. Problem polega
>na tym, że problem jest jeden i algorytm jest jeden, ale musi
>spełniać oba warunki: działać, czyli być bez race'ów i deadlocków, i ma
>nie zagłodzić.


http://comjnl.oxfordjournals.org/content/34/4/345.fu
ll.pdf+html

A.L.

do góry

On 01.07.2013 02:31, A.L. wrote:
> On Sun, 30 Jun 2013 23:47:19 +0000 (UTC), Edek
> <e...@g...com> wrote:
>
>> Tak jakby z zagłodzeniem było kiedykolwiek inaczej. Problem polega
>> na tym, że problem jest jeden i algorytm jest jeden, ale musi
>> spełniać oba warunki: działać, czyli być bez race'ów i deadlocków, i ma
>> nie zagłodzić.
>
>
> http://comjnl.oxfordjournals.org/content/34/4/345.fu
ll.pdf+html

Ładne.

Nawet pomyślałem, że żeby zapewnić większą równoległość należy zwalniać
wszystkie locki poza jednym, tylko z jakiejś przyczyny mi wyszło, że to
nie zadziała. (Będę musiał przejrzeć jeszcze raz notatki.)

--
Pozdrawiam
Michoo

do góry

On 01.07.2013 01:47, Edek wrote:
>>>> - sortujesz te listy w kolejności a-f
>
> Nawet nie trzeba sortować. Try_lock załatwia problem dealocku, tak:
>
> mając do zamknięcia n,m,l,... zamyka się n, a potem try_lockiem
> pozostałe. Jeżeli któryś się nie zamknie, bo zajęty, zwalnia się już
> zamknięte i ten który był zajęty jest pierwszy do kolejnej rundy -
> przez co proces czeka na tym locku aż się zwolni, bo pierwszy jest lock().

W takiej sytuacji możesz mieć live-lock - wystarczą już dwa procesy
"wymieniające się" dwoma blokadami.

> Do zagłodzenia może dojść.

Jest jeszcze gorzej - nie ma warunku postępu.

>
>>>> Każdy proces wchodząc do sekcji krytycznej pobiera potrzebne mu blokady
>>>> w kolejności A-F. Rozwiązuje to problem wzajemnego wykluczania([*]).
>>>> Problem zagłodzenia nie wystąpi na pewno gdy muteksy budzą w kolejności
>>>> FIFO, przy braku tej gwarancji do zagłodzenia może dojść[**] więc
>>>> najlepiej chyba ją zapewnić przez kombinację mutex+lista+condition
>>>> variable (dopóki !pierwszy na liście).
>
> Nope. Trzeba jeszcze dopisać się do list dzielonych z pozostałymi
> procesami, inaczej one też mogą zagłodzić/być zagłodzone, np.
> mapa list z maską jako kluczem...

Nie zrozumiałem. Skoro kolejką emulujemy listę oczekujących na muteksie
to oczywistym jest, że ona musi być współdzielona.

>
>>>> [*] Czyim imieniem nazywamy ten algorytm - nie pamiętam. Jest to daleka
>>>> wariacja Lamporta.
>>>> [**] Choćby a i b "wymieniające się" muteksem A mogą zagłodzić c.
>
> ... a wtedy a i b dopiszą się do kolejki z c i c będzie pierwsze.

Nie rozumiem.

>
> Nie przemyślałem tylko jak to zaimplementować, bo trzeba jeszcze chronić
> same kolejki o ile nie ma kolejek lock-free z peek() i mieć jakąś
> politykę reagowania na a przed b na jednej liście a b przed a na drugiej
> - random() dałby radę.

Używasz parę blokad:
lock(Xa);
dodaj_na_koniec_kolejki(procId,a);
unlock(Xa);

do{
cond_wait(Ya);
}while(head(a)!=procId);
do_stuff();
lock(Xa);
usun_zpoczatku_kolejki(a);
unlock(Xa);
unlock(Ya);

>
>>> Niezupelnie o to chodzi, bo wejscie w proces a powinno blokowac
>>> procesy b i c ale nie powinno blokowac procesow d, e, f
>>
>> Nie znam (a przynajmniej nie przypominam sobie) innego "standardowego"
>> algorytmu rozwiązującego ten problem w sposób przejrzysty a jednocześnie
>> optymalny pod względem wydajnościowym.
>
> Wiele algorytmów "wątkowych" nie ma ani standardu ani nazwy.

Istnieją pewne "wzorce" czy "idiomy". Nie znałem takiego. Jak widać
wystarczyła drobna wariacja tego co przedstawiłem.

> Schematy współpracy: skoro się wykluczają mogą w ramach wykluczenia
> przekazywać dane. Albo mogą mieć kolejki, które są liśćmi w drzewie
> kolejności locków, więc są pomijalne dla poprawności.

Mogą. Właśnie od "mogą" zależy bardzo dużo jeżeli chodzi o wątki. Jeżeli
masz problem producenci-konsumenci to daje się go rozwiązać lock-free.

> Tak jakby z zagłodzeniem było kiedykolwiek inaczej. Problem polega
> na tym, że problem jest jeden i algorytm jest jeden, ale musi
> spełniać oba warunki: działać, czyli być bez race'ów i deadlocków, i ma
> nie zagłodzić.

3 producentów na 2 procesorach plus konsument wymagający po 500
jednostek na cykl pracy. Optymalnie ze względu na przepustowość będzie
generowanie po 500 jednostek (opóźnienie 1000, ale brak strat na
przełączanie). Optymalnie ze względu na czas odpowiedzi będzie dążenie
do opóźnienia 750 - jeżeli konsument czeka dłużej to znaczy, ze jest
głodzony.

--
Pozdrawiam
Michoo

do góry

Dnia pamiętnego Mon, 01 Jul 2013 12:05:05 +0200, Michoo wyjmując peta
oznajmił:

> On 01.07.2013 01:47, Edek wrote:

>> mając do zamknięcia n,m,l,... zamyka się n, a potem try_lockiem
>> pozostałe. Jeżeli któryś się nie zamknie, bo zajęty, zwalnia się już
>> zamknięte i ten który był zajęty jest pierwszy do kolejnej rundy -
>> przez co proces czeka na tym locku aż się zwolni, bo pierwszy jest lock().
>
> W takiej sytuacji możesz mieć live-lock - wystarczą już dwa procesy
> "wymieniające się" dwoma blokadami.

Praktycznie ten algorytm w implementacji boost-a ma jeszcze kilka
yieldów.

>> Do zagłodzenia może dojść.
>
> Jest jeszcze gorzej - nie ma warunku postępu.

To nie jest gorzej. Możliwy deadlock/starvation zawsze kiedyś się zdarzą,
tego typu live-lock nawet jeżeli się zdarzy, to tymczasowo. Konsekwencje
live-locka w tym konkretnym przypadku są praktycznie wyłącznie teoretyczne.

>>>>> Każdy proces wchodząc do sekcji krytycznej pobiera potrzebne mu blokady
>>>>> w kolejności A-F. Rozwiązuje to problem wzajemnego wykluczania([*]).
>>>>> Problem zagłodzenia nie wystąpi na pewno gdy muteksy budzą w kolejności
>>>>> FIFO, przy braku tej gwarancji do zagłodzenia może dojść[**] więc
>>>>> najlepiej chyba ją zapewnić przez kombinację mutex+lista+condition
>>>>> variable (dopóki !pierwszy na liście).
>>
>> Nope. Trzeba jeszcze dopisać się do list dzielonych z pozostałymi
>> procesami, inaczej one też mogą zagłodzić/być zagłodzone, np.
>> mapa list z maską jako kluczem...
>
> Nie zrozumiałem. Skoro kolejką emulujemy listę oczekujących na muteksie
> to oczywistym jest, że ona musi być współdzielona.

Na którym mutexie miałaby być lista wszystkich sąsiadów? Nie da się
podzielić grafu w ten sposób.

>>>>> [*] Czyim imieniem nazywamy ten algorytm - nie pamiętam. Jest to daleka
>>>>> wariacja Lamporta.
>>>>> [**] Choćby a i b "wymieniające się" muteksem A mogą zagłodzić c.
>>
>> ... a wtedy a i b dopiszą się do kolejki z c i c będzie pierwsze.
>
> Nie rozumiem.

W tej pracy linkowanej przez A.L. w referencjach jest edge-based solution,
wspomniana jest we wstępie. Jeszcze nie czytałem, a sam mogłem coś pokręcić
(biorąc pod uwagę fakt że moje 10 minut < publikacja - nic dziwnego ;) ).

>> Nie przemyślałem tylko jak to zaimplementować, bo trzeba jeszcze chronić
>> same kolejki o ile nie ma kolejek lock-free z peek() i mieć jakąś
>> politykę reagowania na a przed b na jednej liście a b przed a na drugiej
>> - random() dałby radę.
>
> Używasz parę blokad:
> lock(Xa);
> dodaj_na_koniec_kolejki(procId,a);
> unlock(Xa);
>
> do{
> cond_wait(Ya);
> }while(head(a)!=procId);
> do_stuff();
> lock(Xa);
> usun_zpoczatku_kolejki(a);
> unlock(Xa);
> unlock(Ya);

Nie zrozumiałem. Gdzie jest lock(Ya)? Co robi do_stuff()? I gdzie to pasuje
do całości?

>> Wiele algorytmów "wątkowych" nie ma ani standardu ani nazwy.
>
> Istnieją pewne "wzorce" czy "idiomy". Nie znałem takiego. Jak widać
> wystarczyła drobna wariacja tego co przedstawiłem.

W algorytmach wątkowych najczęściej nie ma czegoś takiego jak
drobna wariacja. W zasadzie każda zmiana, nawet drobna, wymaga
dowodu od początku. Przykład:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2
008/n2660.htm#AppendixSource

Część ludzi twierdzi, że algorytm działa po "drobnej zmianie",
gdy _fast_pthread_once_per_thread_epoch jest nie monotonicznie
rosnąca ale flagą - a łatwo udowodnić, że wtedy całość się rozsypie.

Każda zmiana wymaga dowodu od początku.

>> Schematy współpracy: skoro się wykluczają mogą w ramach wykluczenia
>> przekazywać dane. Albo mogą mieć kolejki, które są liśćmi w drzewie
>> kolejności locków, więc są pomijalne dla poprawności.
>
> Mogą. Właśnie od "mogą" zależy bardzo dużo jeżeli chodzi o wątki. Jeżeli
> masz problem producenci-konsumenci to daje się go rozwiązać lock-free.

Zazwyczaj w takich sytuacjach używa się:
a = try_get()
if (a == null) {
zwolnij_wszystkie_locki
a = get();
od początku ustawiamy się w kolejce do locków
}

To nie wymaga ani zmiany głównego algorytumu ani kolejek lock-free.
Dlatego, że try_get zamyka jeden lock jako ostatni, na krótko,
bez wait(), a jeżeli ma być wait() to już trzeba wszystko zwolnić
bo wait() zalicza się w myśleniu o deadlockach do locków.

--
Edek

do góry

Dnia pamiętnego Mon, 01 Jul 2013 12:05:05 +0200, Michoo wyjmując peta
oznajmił:

> On 01.07.2013 01:47, Edek wrote:

>> Schematy współpracy: skoro się wykluczają mogą w ramach wykluczenia
>> przekazywać dane. Albo mogą mieć kolejki, które są liśćmi w drzewie
>> kolejności locków, więc są pomijalne dla poprawności.
>
> Mogą. Właśnie od "mogą" zależy bardzo dużo jeżeli chodzi o wątki. Jeżeli

Tak dla rozróżnienia: wątki są w domenie logiki i "mogą" używa się różnie.
Ja mówię o tym, że niektóre elementy "mogą" być dodane bez zmiany
głównego algorytmu, co można udowodnić. Ty mówisz o "może" w sensie
takim jak że deadlock "może" się zdarzyć - co już oznacza zwykły błąd.
To pierwsze jest kwestią logiki ograniczeń, to drugie kwestią złego
dowodu lub jego braku.

>> Tak jakby z zagłodzeniem było kiedykolwiek inaczej. Problem polega
>> na tym, że problem jest jeden i algorytm jest jeden, ale musi
>> spełniać oba warunki: działać, czyli być bez race'ów i deadlocków, i ma
>> nie zagłodzić.
>
> 3 producentów na 2 procesorach plus konsument wymagający po 500
> jednostek na cykl pracy. Optymalnie ze względu na przepustowość będzie
> generowanie po 500 jednostek (opóźnienie 1000, ale brak strat na
> przełączanie). Optymalnie ze względu na czas odpowiedzi będzie dążenie
> do opóźnienia 750 - jeżeli konsument czeka dłużej to znaczy, ze jest
> głodzony.

Nie znałem takiej definicji. Jak się to sprawdza albo dowodzi? Naprawdę
pytam bo nie wiem.

A, i odnosiłem się tylko do ostatniego zdania:

>>> Ogólnie wchodzimy
>>> opuszczamy już tutaj problem synchronizacji a wchodzimy w sferę
>>> szeregowania zadań.

--
Edek

do góry

Dużo odpowiedzi na jeden post wychodzi, ale trudno.

Dnia pamiętnego Mon, 01 Jul 2013 12:05:05 +0200, Michoo wyjmując peta
oznajmił:

> Jeżeli
> masz problem producenci-konsumenci to daje się go rozwiązać lock-free.

Pod względem /poprawności/ kolejki lock-free niczym się nie różnią od
blokujących kolejek. Istnieją tylko w celu /wydajności/, operacje na nich
są zarówno bardzo częste jak i krótkotrwałe, więc nie warto tracić
czasu na usypianie wątku i budzenie, lepszy jest spin w momencie
kolizji.

Inne struktury lock-free mają znaczenie dla poprawności, ale akurat
nie kolejki.

Inną generalną zasadą jest to, że podstawowe atomiczne operacje
używane w strukturach lock-free da się zaimplementować tak:

lock
do_single_memory_op
unlock

I tak się czasami robi, gdy sprzęt nie wspiera albo operacji albo
wystarczająco dużego słowa, co /poprawności/ nie zmienia. Chociażby
w C++11 MemoryModel zmienia semantykę operacji na 'stricter', a
nie w drugą stronę. Traci się tylko na /wydajności/.

--
Edek

do góry

Dnia pamiętnego Mon, 01 Jul 2013 11:32:22 +0200, Michoo wyjmując peta
oznajmił:

> On 01.07.2013 02:31, A.L. wrote:

>> http://comjnl.oxfordjournals.org/content/34/4/345.fu
ll.pdf+html
>
> Ładne.
>
> Nawet pomyślałem, że żeby zapewnić większą równoległość należy zwalniać
> wszystkie locki poza jednym, tylko z jakiejś przyczyny mi wyszło, że to
> nie zadziała. (Będę musiał przejrzeć jeszcze raz notatki.)

Fakt że ładne, ale journal ma widocznie taką politykę, że cytowane
prace są tylko w płatnej wersji (albo jestem niemotą i nie potrafię
wyklikać przypisów).

--
Edek

do góry

On Mon, 1 Jul 2013 13:10:30 +0000 (UTC), Edek
<e...@g...com> wrote:

>Dnia pamiętnego Mon, 01 Jul 2013 11:32:22 +0200, Michoo wyjmując peta
>oznajmił:
>
>> On 01.07.2013 02:31, A.L. wrote:
>
>>> http://comjnl.oxfordjournals.org/content/34/4/345.fu
ll.pdf+html
>>
>> Ładne.
>>
>> Nawet pomyślałem, że żeby zapewnić większą równoległość należy zwalniać
>> wszystkie locki poza jednym, tylko z jakiejś przyczyny mi wyszło, że to
>> nie zadziała. (Będę musiał przejrzeć jeszcze raz notatki.)
>
>Fakt że ładne, ale journal ma widocznie taką politykę, że cytowane
>prace są tylko w płatnej wersji (albo jestem niemotą i nie potrafię
>wyklikać przypisów).

W Computer Jorurnal bezplatne sa artykuly od poczatku wydawanie
czasopisma do roku XXXX (niestety, nie pamietam ktorego)

A.L.

P.S. Tu jest jeszcze jeden papier

http://www.ece.iupui.edu/~dskim/Classes/ESW5004/jaco
b,page89-mutual%20exclusion%20solution%20based%20on%
20binary%20semaphore.pdf

do góry