Elosztó típusú sorban állás

A sorbanállás-elméletben az elosztó típusú sorban állásra az jellemző, hogy a beérkező feladatokat szétosztják számos kiszolgáló között, és kiszolgálás után újra összeállítják őket.^[1]

Elosztó-típusú sorbanállási modell

Ezt a modellt gyakran alkalmazzák párhuzamos számítógép-architektúráknál, és rendszereknél, ahol különböző helyről, különböző beszállítótól érkeznek termékek (raktárak, üzemek). Ennél a modellnél a fő előny a beérkező feladatok elvégzésnek gyorsítása. Ez a modell a párhuzamos-, és elosztott rendszerek egyik fő jellemzője.^[2] Azt a változatot, amikor a feladatok beérkezése a Poisson-folyamat szerint történik, és a kiszolgálási idők exponenciálisan elosztottak, Flatto–Hahn–Wright-modellnek hívják (FHV)^[3][4]

Működés

A villaszerű bemenetekre érkező feladat N alfeladattá válik szét, melyeket N szerver szolgál ki. A kiszolgálás után az alfeladatok addig várnak, míg a többi alfeladat feldolgozása is befejeződött, majd ezután összeállítják őket és elhagyják a rendszert.^[2] Ahhoz, hogy a rendszer stabil maradjon, az szükséges, hogy a beérkezések sebessége kisebb legyen, mint a kiszolgálás sebessége a kiszolgáló pontokon.^[5]

Alkalmazás

Ezt a modellt használják a RAID rendszereknél,^[6] párhuzamos számítógép-architektúráknál, és raktárak működtetésénél.^[2]

Válaszidő

A válaszidő egyenlő azzal az idővel, amíg egy feladat a rendszerben tartózkodik. Ko és Serfőző közelítést ad arra az esetre, amikor a kiszolgálási idők exponenciálisan elosztottak, és a feladatok a Poisson-folyamat szerint, vagy a normális eloszlás szerint érkeznek.^[7]

Átlagos válaszidő

Egzakt képlet az átlagos válaszidőre csak a két szerveres esetre ismert (N=2), ahol a kiszolgálási idő exponenciális eloszlású (azaz,mindegyik szerver egy M/M/1-típusú sorbanállás modell). A válaszidő (a teljes idő, amíg a feladatok a rendszerben tartózkodnak):^[8]

${\displaystyle {\frac {\rho (12-\rho )}{8(1-\rho )}}}$

ahol

• ${\displaystyle \rho =\lambda /\mu }$ a felhasználás
• ${\displaystyle \lambda }$ a rendszerbe érkező feladatok üteme
• ${\displaystyle \mu }$ a teljes kiszolgálási idő az összes ponton

Ebben a helyzetben, amikor az egyes csomópontok M/M/1-típusú sorbanállás modellek, az átlagérték analízis alkalmazható az átlagos válaszidő közelítő kiszámításához.^[9] Általános kiszolgálási idők esetére, amikor minden pont M/G/1-típusú sorbanállás modellként működik, Bacelli és Makowski ad közelítést.^[10] Amikor a feladatok kiszolgálása megtörtént, akkor újra össze kell a sort állítani. Nelson és Tantawi publikációja ad támpontot a sor hosszára, ahol az összes szerver hasonló sebességgel dolgozik. .^[8] Heterogén szerver sebességeknél és eloszlásoknál Li és Zhao publikációja ad közelítést.^[11] A sorosan összeállító változatban (egymás utáni összeállítás) egy közelítő formula használható.^[12]

Irodalom

• Baccelli, François; Makowski: Simple computable bounds for the fork-join queue. (hely nélkül): National Institute for Research in Computer Science and Control Technical Report. 1985.  
• Li, Jun; Zhao, Yiqiang Q: On the Probability Distribution of Join Queue Length in a Fork-Join Model. (hely nélkül): Probability in the Engineering and Informational Sciences 24 (4). 2010. 473–483. o.  
• https://web.archive.org/web/20131029195204/http://pubs.doc.ic.ac.uk/forkjoin/forkjoin.pdf
• http://www.win.tue.nl/~iadan/que/h4.pdf

Kapcsolódó szócikkek

• Eloszlásfüggvény
• Valószínűségszámítás
• Statisztika
• Matematikai statisztika
• Poisson-folyamat
• Sorbanállási elmélet
• M/D/1-típusú sorbanállás
• M/M/c-típusú sorbanállás
• Pollaczek–Khinchine-formula
• M/G/1-típusú sorbanállás

Jegyzetek

1. Kim, C. (1989. február 1.). „Analysis of the Fork-Join Queue”. IEEE Transactions on Computers 38 (2), 250–255. o. DOI:10.1109/12.16501. 
2. Serfozo, Richard. Basics of Applied Stochastic Processes. Springer, 78–80. o. (2009). ISBN 3-540-89331-8 
3. Wright, Paul E. (1992). „Two parallel processors with coupled inputs”. Advances in Applied Probability 24, 986–1007. o. 
4. Pinotsi, D. (2005). „Synchronized queues with deterministic arrivals”. Operations Research Letters 33 (6), 560–566. o. DOI:10.1016/j.orl.2004.12.005. 
5. Konstantopoulos, Panagiotis (1989. September). „Stationary and Stability of Fork-Join Networks”. Journal of Applied Probability 26 (3), 604–614. o. [2012. március 18-i dátummal az eredetiből archiválva]. DOI:10.2307/3214417. (Hozzáférés: 2011. július 8.) 
6. „Modelling Zoned RAID Systems using Fork-Join Queueing Simulation”. 6th European Performance Engineering Workshop (EPEW 2009) Lecture Notes in Computer Science 5652: 16–29, Springer Verlag. [2012. április 25-i dátummal az eredetiből archiválva]. doi:10.1007/978-3-642-02924-0. Hozzáférés: 2013. február 1. 
7. (2008. August) „Sojourn times in G/M/1 fork-join networks”. Naval Research Logistics 55 (5), 432–443. o. DOI:10.1002/nav.20294. 
8. Nelson, Randolph (1988. June). „Approximate analysis of fork/join synchronization in parallel queues”. IEEE Transactions on Computers 37 (6), 739–743. o. DOI:10.1109/12.2213. 
9. Varki, Elizabeth: M/M/1 Fork-join queue with variable sub-tasks. [2010. augusztus 5-i dátummal az eredetiből archiválva]. (Hozzáférés: 2009. március 29.)
10. Baccelli, François (1985). „Simple computable bounds for the fork-join queue”, Kiadó: National Institute for Research in Computer Science and Control Technical Report. (Hozzáférés: 2011. július 8.) 
11. (2010) „On the Probability Distribution of Join Queue Length in a Fork-Join Model”. Probability in the Engineering and Informational Sciences 24 (4), 473–483. o. DOI:10.1017/S0269964810000112. 
12. Ko, Sung-Seok (2007). „Cycle Times in a Serial Fork-Join Network”. International Conference on Computational Science and Its Applications (ICCSA 2007) Lecture Notes in Computer Science 4705: 758–766, Springer. doi:10.1007/978-3-540-74472-6_62.