Zamiennik dla kolejek w RTOS

12

Do komunikacji między zadaniami lub do udostępniania danych między dwoma zadaniami RTOS używamy kolejek. Ale problem z kolejkami polega na tym, że są one powolne ... Kopiują dane do bufora, następnie Mutex Handling, a następnie Transfer danych. Jest irytująco wolny, jeśli musisz przesyłać duże dane. Innym problemem jest dostęp do tej samej kolejki przez wiele zadań. Następnie obraz wygląda następująco: - Najpierw poczekaj, aby uzyskać dostęp do kolejki, następnie kolejka obsługi mutexów w kolejce, a następnie transfer danych.

Zwiększa to obciążenie systemu. Jaki może być skuteczny zamiennik kolejek?

(Myślę, że to pytanie jest niezależne od RTOS, którego używamy. Większość RTOS obsługuje kolejki tylko w ten sposób)

Swanand
źródło
Co rozumiesz przez kolejkę dostępną dla wielu zadań? Masz na myśli wysyłanie do kolejki lub czytanie z kolejki? Wiele zadań powinno być w stanie wysłać do kolejki przy minimalnym obciążeniu. RTOS powinien obsługiwać muteksowanie, aby post był operacją atomową. W przypadku 99% zadań powinieneś mieć pętlę oczekującą w kolejce i przetwarzającą komunikat. Kolejka powinna (zwykle) być odczytywana tylko przez jedno zadanie. Prawdopodobnie będziesz musiał spojrzeć na swój projekt i sposób korzystania z kolejek zamiast ich zastępowania.
Erik
@Erik: Przepraszamy! Korzystam z mechanizmu, o którym wspomniałeś ... Chciałem powiedzieć coś innego i napisałem inaczej .... Zedytuję to !! Dzięki za zwrócenie uwagi na błąd! Czekam na dostęp do kolejki w moim kodzie!
Swanand

Odpowiedzi:

7

Kolejki działają w ten sposób, ponieważ jest to model transakcji bezpieczny dla wątków do komunikacji między zadaniami. Ryzykujesz uszkodzenie danych i / lub problemy z własnością w każdym mniej rygorystycznym systemie.

Czy kopiujesz dane do bufora w pamięci, a następnie przekazujesz wskaźnik z elementami kolejki, czy próbujesz przekazać wszystkie dane w samych elementach kolejki? Jeśli nie przekazujesz wskaźników, zwiększysz wydajność, robiąc to zamiast przepuszczać jeden bajt na raz przez elementy kolejki.

AngryEE
źródło
2
Chciałem powiedzieć to samo. Jeśli po prostu przekażesz wskaźniki do danych w kolejkach, możesz zwiększyć prędkość, ale upewnij się, że nie skończysz z dwoma wątkami próbującymi używać i zmieniać dane.
Kortuk
Jak powiedział @Kortuk, potrzebuję „upewnij się, że nie skończysz z dwoma wątkami próbującymi używać i zmieniać dane” ... Co oznacza wzrost kosztów ogólnych ... Nie chcę dużo przetwarzania! :(
Swanand
Więc nie ma takiego zastępstwa dla kolejek ... Zamiast kolejki danych muszę użyć kolejki wskaźników!
Swanand
1
@Swan i jeśli planujesz swoją aplikację tak, aby kolejki były tylko jednokierunkowe (tzn. Nigdy nie czytasz tej samej kolejki w dwóch zadaniach) i natychmiast przetwarzasz dane przechowywane we wskaźniku, a następnie je zwalniasz, nie powinieneś mieć problemu z udostępnianiem danych. Zwiększone zostaną koszty ogólne, ponieważ może być konieczne utworzenie wielu kolejek w celu niezawodnego przesyłania danych tam iz powrotem, ale jest to koszt prowadzenia działalności w środowisku wielozadaniowym.
AngryEE
7

Jednym prostym sposobem jest umieszczenie wskaźnika w danych w kolejce i wykorzystanie danych za pomocą wskaźnika.

Pamiętaj, że w ten sposób zamieniasz bezpieczeństwo na wydajność, ponieważ musisz upewnić się, że:

  1. bufor pozostaje ważny, dopóki konsument nie wykorzysta danych
  2. ktoś zwalnia bufor

Jeśli nie używasz pamięci dynamicznie alokowanej, nie musisz jej cofać przydziału, ale musisz upewnić się, że obszar pamięci nie zostanie ponownie wykorzystany przed zużyciem danych.

Trygve Laugstøl
źródło
6

Kolejki bez blokady można wdrożyć w przypadku pojedynczego producenta / pojedynczego konsumenta, a często można tak zaprojektować oprogramowanie, aby zminimalizować liczbę kolejek wielu producentów lub wielu konsumentów.

Kolejkę bez blokady można tak skonstruować: Przydziel tablicę elementów, które mają być komunikowane, a także dwie liczby całkowite, nazywaj je Głową i Ogonem. Head jest indeksem w tablicy, do którego zostanie dodany następny element. Ogon jest indeksem w tablicy, w którym można usunąć następny element. Zadanie producenta odczytuje H i T, aby ustalić, czy jest miejsce na dodanie elementu; zapisuje element w indeksie H, a następnie aktualizuje H. Zadania konsumenta odczytują H i T, aby ustalić, czy są dostępne dane, odczytują dane z indeksu T, a następnie aktualizują T. Zasadniczo jest to bufor pierścieniowy, do którego dostęp mają dwa zadania, a kolejność operacji (wstaw, następnie zaktualizuj H; usuń, a następnie zaktualizuj T) zapewnia, że ​​nie nastąpi uszkodzenie danych.

Jeśli masz sytuację z wieloma producentami i jednym konsumentem lub z jednym producentem i wieloma konsumentami, faktycznie masz pewnego rodzaju ograniczenie zasobów i nie pozostaje nic innego, jak korzystać z synchronizacji, ponieważ ograniczenie wydajności jest bardziej prawdopodobne być samotnym producentem / konsumentem niż narzut systemu operacyjnego z mechanizmem blokującym.

Ale jeśli masz wielu producentów ORAZ konsumentów, warto poświęcić czas (w przestrzeni projektowej), aby sprawdzić, czy nie możesz uzyskać bardziej skoordynowanego mechanizmu komunikacji; w takim przypadku, szeregowanie wszystkiego za pomocą pojedynczej kolejki zdecydowanie sprawia, że ​​wydajność kolejki jest głównym wyznacznikiem wydajności.

JustJeff
źródło
1
Chciałem dać +1, ale nie masz racji: kolejki bez blokady są możliwe do wdrożenia dla wielu czytelników i pisarzy, są po prostu bardziej skomplikowane. (spójrz na artykuł Michaela + Scotta o kolejkach bez blokady google.com/search?q=michael%20scott%20queue )
Jason S
1
@Jason S - czy papier Scott wyraźnie żąda ponownego wejścia dla operacji wkładania i wyjmowania bez blokady? Jeśli tak, jeśli możesz to wyodrębnić i opublikować, zrób to, dla wielu będzie to nieoceniony atut. Czytelnik powinien zauważyć, że cytowany artykuł korzysta ze specjalnych instrukcji maszynowych, podczas gdy moja pozycja w powyższym poście nie zakładała takich instrukcji.
JustJeff,
1
Tak, koszt algorytmów bez blokady zwykle zależy od CAS lub równoważnych instrukcji. Ale w jaki sposób w grę wchodzi ponowne entrancja? Ma to sens dla muteksów + struktur blokujących, ale nie dla operacji struktury danych.
Jason S
2

Wydajną pracę można uzyskać w bezblokującej kolejce jednego producenta dla wielu producentów, jeśli sama kolejka zawiera elementy, które są wystarczająco małe, aby współpracować z operacją podstawową wyłączną dla magazynu ładunków, giełdą porównawczą lub podobną, i można użyć wartość zarezerwowana lub wartości zastrzeżone dla pustych miejsc w kolejce. Podczas pisania do kolejki pisarz dokonuje wymiany porównania, aby spróbować zapisać swoje dane w następnym pustym polu; jeśli to się nie powiedzie, pisarz próbuje następujące gniazdo. Chociaż kolejka utrzymuje wskaźnik do następnego pustego miejsca, wartość wskaźnika to „wskazówka”. Należy zauważyć, że jeśli system używa wymiany-porównania zamiast wyłączności ładowania magazynu, może być konieczne posiadanie „rodziny” różnych wartości „pustego gniazda”. W przeciwnym razie, jeśli między czasem program piszący znajdzie puste miejsce w kolejce i spróbuje do niego napisać, inny pisarz pisze automat, a czytelnik go czyta, pierwszy pisarz nieświadomie umieściłby swoje dane w miejscu, w którym czytelnik by ich nie widział. Ten problem nie występuje w systemach, które wykorzystują wyłącznie ładowanie do magazynu, ponieważ wyłączność do przechowywania wykryłaby, że dane zostały zapisane, mimo że zostały zapisane z powrotem do starej wartości.

supercat
źródło
1

Dostęp do kolejek można uzyskać bardziej efektywnie, pisząc na górze kolejki. Zwykle większość systemów RTOS obsługuje dodawanie na początku kolejki, co nie wymaga nabywania muteksu. Ale upewnij się, że używasz dodawania do przodu kolejki tak minimalnie, jak to możliwe, jeśli chcesz tylko szybciej wykonać dane. Zwykle struktury kolejek mają maksymalny limit rozmiaru, więc nie możesz umieścić wszystkich danych w kolejce, dlatego przekazanie wskaźnika jest zawsze łatwe.

Twoje zdrowie!!

Sai
źródło
1

Kolejki nie są z natury wolne. Ich realizacja może być.

Jeśli ślepo kopiujesz dane i używasz synchronicznej kolejki, zobaczysz spadek wydajności.

Jak wskazały inne plakaty, istnieją alternatywy bez blokady. Sprawa jednego producenta / pojedynczego konsumenta jest prosta; dla wielu producentów i konsumentów algorytm kolejki bez blokady Michaela i Scotta (są to ich nazwiska) jest standardem i jest wykorzystywany jako podstawa dla ConcurrentLinkedQueue w Javie .

W niektórych przypadkach można zoptymalizować potrzebę kolejek, ale zapewniają one gwarancje współbieżności, które zwykle zapewniają ogromne korzyści w zakresie uproszczenia systemów, umożliwiając rozdzielenie zadań.

Jason S.
źródło
Z artykułu Michaela i Scotta: „jest to wyraźny algorytm z wyboru dla maszyn, które zapewniają uniwersalną prymityw atomową (np. Porównywanie i zamiana lub ładowanie połączone / przechowywanie warunkowe)” Chociaż może to nie do końca dokładnie zablokować wątek, tutaj odbywa się pewna forma synchronizacji.
JustJeff
masz rację; może zmniejszyć wymóg współbieżności z wyłącznego dostępu do bariery pamięci.
Jason S,