Wydaje się prawdą, ale moja myśl była błotnista. Czy ktoś może dać jasne wyjaśnienie i kilka ważnych przypadków, w których zawsze działa bez blokowania? dzięki!Dlaczego jednolity cykliczny wątek pojedynczego producenta jest bezpieczny bez blokowania?
To z pewnością zależy od realizacji cyklicznej kolejki. Jeśli jednak tak jest, jak sobie wyobrażam, masz dwa indeksy - head i tail kolejki. Producent współpracuje z tail, a konsument współpracuje z head. Dzielą się tablicą wiadomości, ale używają dwóch różnych wskaźników.
Jedyny przypadek, w którym producent i konsument mogą stanąć w konflikcie, to taki, w którym np. konsument sprawdza nową wiadomość i przybywa tuż po kontroli. Jednak w takim przypadku konsument trochę poczeka i jeszcze raz sprawdzi. Poprawność programu nie zostanie utracona.
Powód, dla którego działa dobrze z pojedynczym użytkownikiem pojedynczego producenta, wynika głównie z faktu, że dwóch użytkowników nie ma zbyt dużo pamięci. W przypadku wielu producentów, np. będziesz mieć więcej niż jeden wątek dostępu do head i mogą pojawić się konflikty.
EDYTOWANIE jak wspomina dasblinkenlight w swoim komentarzu moje rozumowanie jest prawdziwe tylko wtedy, gdy oba wątki zwiększają/zmniejszają swoje liczniki jako ostatnią operację ich konsumowania/produkcji.
+1 Należy wspomnieć, że bezpieczeństwo wątku jest uzależnione od tego, czy producent najpierw zapisze element w kolejce, a dopiero potem inkrementuje indeks "ogona". W środowiskach jednowątkowych kolejność nie ma znaczenia, ale w środowiskach współbieżnych zmiana kolejności może doprowadzić do załamania. – dasblinkenlight
@dasblinkenlight Dzięki, uzasadniony komentarz. –
@ dasblinkenlight wzdłuż tej samej linii, czy konsument powinien najpierw zrobić element, a następnie zwiększyć indeks __head__? –
Prawdziwą sztuczką stojącą za pojedynczym producentem - kolejką kołową dla pojedynczego klienta jest zmiana wskaźników głowy i ogona atomowo. Oznacza to, że jeśli pozycja w pamięci zostanie zmieniona z wartości A na wartość B, obserwator (tj. Czytnik), który odczytuje pamięć, gdy jej wartość jest zmieniona, otrzymuje jako wynik A lub B, nic więcej.
Twoja kolejka nie będzie działać, jeśli na przykład korzystasz z 16-bitowych wskaźników, ale zmieniasz je w dwóch krokach 8-bitowych (może się to zdarzyć w zależności od architektury procesora i wymagań dotyczących wyrównania pamięci). Czytnik w tym przypadku może odczytać całkowicie błędną wartość przejściową.
Upewnij się, że Twoje wskaźniki zostały zmodyfikowane atomowo w twojej platformie!
Jakie jest źródło lub kontekst tego roszczenia? Na pewno możesz to zaimplementować za pomocą pojedynczego semafora, czy to właśnie masz na myśli? Semafor ma również zamek wewnątrz lub jest atomowy w sprzęcie. – ypnos
Byłbym zaskoczony, gdyby twierdzenie było ogólnie prawdziwe, choćby ze względu na problemy z modelem pamięci. Co sprawia, że zmiany dokonane przez producenta są widoczne dla konsumenta i na odwrót? Możliwe jest napisanie bezpiecznej implementacji bez blokowania przy użyciu lotnych i/lub atomowych operacji, ale można to zrobić dla wielu struktur danych. –
Myślę, że jest to ogólnie prawda bez względu na kontekst, o ile kolejka cykliczna ma rozsądnie rozsądną implementację. żadna blokada nie będzie potrzebna do użycia z pojedynczym konsumentem, pojedynczym producentem. Pytanie brzmi, jak wszystkie przypadki konfliktów są obsługiwane poprawnie. –