Dnia pamiętnego Mon, 01 Jul 2013 18:24:17 +0200, Michoo wyjmując peta
oznajmił:
> On 01.07.2013 13:02, Edek wrote:
>> Dnia pamiętnego Mon, 01 Jul 2013 12:05:05 +0200, Michoo wyjmując peta
>> oznajmił:
>>> On 01.07.2013 01:47, Edek wrote:
>>
>>>> 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.
>
> live-lock to starvation na dostępie do sekcji krytycznej.

Mógłbyś nie używać określenia sekcja krytyczna mając na myśli mutual
exclusion w mojej obecności? Byłbym dozgonnie wdzięczny ;), bo
przy dwóch lockach ja nie bardzo wiem jak to podzielić:

lock(a) {
... sekcja krytyczna ...
lock (b) {
... sekcja nadkrytyczna?? ...
}
.... sekcja wciąż krytyczna ...
}

Live-lock to nic więcej jak wielokrotne próby wielu wątków,
z których żadnemu się nie udaje przez dłuższy czas. Ludzie sobie
z tym radzą nawet w transactional memory, gdzie tego typu
kolizje są znacznie częstsze bo struktury i transakcje dużo większe,
wymyślono odpowiednie "policies" pierwszeństwa.

> Spotykałem kilkakrotnie z softem który przestawał działać po
> przeniesieniu na dwa rdzenie i tak jak deadlock od razu widać bo "staje"
> tak live-lock ma w praktyce ciekawsze objawy - np strasznie powolna
> praca z obciążeniem dwóch rdzeniu (pozornie bez powodu, strace pokazuje
> ciągłe try_lock) albo występujące raz na jakiś czas zacięcie. Ciężko to
> nazwać "działaniem" gdy procesy 90% czasu walczą o dostęp do sekcji
> krytycznej.

Ja też różne rzeczy spotykałem i widziałem, ale ten konkretnie algorytm
jest jak najbardziej ok. To że widziałeś takie starvation to jeszcze nie
znaczy, że każdy algorytm który teoretycznie nie ma warunku postępu
probabilistycznie też nie ma. Zerknij do boosta - tam chwilowy livelock
jest obsługiwany podobnie jak wielokrotna kolizja w lock-free, mały
backoff a jak nie pomoże to yield.

--
Edek