Kolejka widełkowa

Węzeł kolejkowania typu fork-join

W teorii kolejek , dyscyplinie w ramach matematycznej teorii prawdopodobieństwa , kolejka typu fork-join to kolejka, w której przychodzące zadania są dzielone po przybyciu do usługi przez wiele serwerów i łączone przed odlotem. Model jest często używany do obliczeń równoległych lub systemów, w których produkty muszą być pozyskiwane jednocześnie od różnych dostawców (w warunkach magazynowych lub produkcyjnych). Kluczową wielkością, która nas interesuje w tym modelu, jest zazwyczaj czas potrzebny na obsłużenie kompletnego zlecenia. Model został opisany jako „kluczowy model do analizy wydajności równoległych i systemy rozproszone .” Istnieje niewiele wyników analitycznych dla kolejek typu fork-join, ale znane są różne przybliżenia.

Sytuacja, w której zadania pojawiają się zgodnie z procesem Poissona , a czasy obsługi są rozkładane wykładniczo, jest czasami określana jako model Flatto – Hahn – Wright lub model FHW .

Definicja

Po przybyciu do punktu rozwidlenia zadanie jest dzielone na N podzadań, które są obsługiwane przez każdy z N serwerów. Po wykonaniu usługi zadanie podrzędne poczekaj, aż wszystkie inne zadania podrzędne również zostaną przetworzone. Zadania podrzędne są następnie ponownie łączone i opuszczają system.

Aby kolejka fork-join była stabilna, szybkość wejściowa musi być ściśle mniejsza niż suma stawek usług w węzłach usług.

Aplikacje

Kolejki fork-join zostały wykorzystane do modelowania strefowych systemów RAID , obliczeń równoległych oraz do modelowania realizacji zamówień w magazynach.

Czas odpowiedzi

Czas odpowiedzi (lub czas przebywania) to całkowity czas, jaki zadanie spędza w systemie.

Dystrybucja

Ko i Serfozo podają przybliżony rozkład czasu odpowiedzi, gdy czasy obsługi są rozłożone wykładniczo, a zadania pojawiają się albo zgodnie z procesem Poissona , albo z rozkładem ogólnym. QIu, Pérez i Harrison podają metodę aproksymacji, gdy czasy obsługi mają rozkład fazowy .

Średni czas odpowiedzi

Dokładny wzór na średni czas odpowiedzi jest znany tylko w przypadku dwóch serwerów ( N =2) o wykładniczo rozłożonych czasach obsługi (gdzie każdy serwer jest kolejką M/M/1 ). W tej sytuacji czas odpowiedzi (całkowity czas, jaki zadanie spędza w systemie) wynosi

${\ Displaystyle {\ Frac {12-\ rho}}}}$

Gdzie

• ${\ Displaystyle \ rho = \ lambda / \ mu}$ to wykorzystanie.
• ${\ displaystyle \ lambda}$ to wskaźnik nadejścia zadań do wszystkich węzłów.
• ${\ displaystyle \ mu}$ to stawka za usługę we wszystkich węzłach.

W sytuacji, gdy węzły są kolejkami M/M/1 i N > 2, modyfikację analizy wartości średniej Varki'ego można również wykorzystać do podania przybliżonej wartości średniego czasu odpowiedzi.

Dla ogólnych czasów obsługi (gdzie każdy węzeł jest kolejką M/G/1 ) Baccelli i Makowski podają granice średniego czasu odpowiedzi i wyższych momentów tej wielkości zarówno w stanach przejściowych, jak i ustalonych. Kemper i Mandjes pokazują, że dla niektórych parametrów granice te nie są ścisłe i demonstrują technikę aproksymacji. W przypadku heterogenicznych kolejek fork-join (kolejki fork-join o różnych czasach obsługi) Alomari i Menasce proponują przybliżenie oparte na liczbach harmonicznych, które można rozszerzyć, aby objąć bardziej ogólne przypadki, takie jak probabilistyczne widełki, otwarte i zamknięte kolejki fork-join.

Dyspersja podzadań

Dyspersję podzadań, zdefiniowaną jako zakres czasów obsługi, można obliczyć numerycznie i wprowadzić optymalne deterministyczne opóźnienia w celu zminimalizowania zakresu.

Dystrybucja stacjonarna

Ogólnie stacjonarny rozkład liczby zadań w każdej kolejce jest trudny do rozwiązania. Flatto rozważył przypadek dwóch serwerów ( N=2 ) i wyprowadził stacjonarny rozkład liczby zadań w każdej kolejce za pomocą technik uniformizacji . Pinotsi i Zazanis pokazują, że rozwiązanie w postaci produktu istnieje, gdy przybycia są deterministyczne , ponieważ długości kolejek są wówczas niezależnymi kolejkami D/M/1 .

Przybliżenie dużego natężenia ruchu/dyfuzji

Gdy serwer jest mocno obciążony (szybkość obsługi kolejki jest tylko nieznacznie większa niż szybkość przybycia), proces długości kolejki można przybliżyć za pomocą odbitego ruchu Browna , który zbiega się do tego samego rozkładu stacjonarnego, co pierwotny proces kolejkowania. W warunkach ograniczających przestrzeń stanów kolejek synchronizacji załamuje się i wszystkie kolejki zachowują się identycznie.

Dołącz do dystrybucji kolejki

Po obsłużeniu zadań części są ponownie składane w kolejce łączenia. Nelson i Tantawi opublikowali rozkład długości kolejki dołączania w sytuacji, gdy wszystkie serwery mają taką samą stawkę za usługę. Heterogeniczne stawki usług i analiza asymptotyczna dystrybucji są rozważane przez Li i Zhao.

Sieci kolejek fork-join

Przybliżony wzór może być użyty do obliczenia rozkładu czasu odpowiedzi dla sieci kolejek fork-join połączonych szeregowo (jedna po drugiej).

Model dzielenia i scalania

Powiązanym modelem jest model split-merge, dla którego istnieją wyniki analityczne. Dokładne wyniki dla kolejki split-merge podają Fiorini i Lipsky. Tutaj po przybyciu zadanie jest dzielone na N podzadań, które są obsługiwane równolegle. Dopiero gdy wszystkie zadania zakończą obsługę i zostaną ponownie połączone, można rozpocząć następne zadanie. Prowadzi to do średnio wolniejszego czasu reakcji.

Uogólniony (n, k) system połączeń widełkowych

Uogólnieniem systemu kolejkowania fork-join jest $}$$fork -join,$ którym zadanie opuszcza system, gdy { $}$$displaystyle$ zadań jest obsługiwanych. Tradycyjny system $displaystyle$$k = n$ szczególnym przypadkiem systemu, którym . Granice średniego czasu odpowiedzi tego uogólnionego systemu znaleźli Joshi, Liu i Soljanin.