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]

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]

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

ahol

$\rho =\lambda /\mu$ a felhasználás
$\lambda$ a rendszerbe érkező feladatok üteme
$\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

Jegyzetek

↑ 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.
↑ ^a ^b ^c Serfozo, Richard. Basics of Applied Stochastic Processes. Springer, 78–80. o. (2009). ISBN 3-540-89331-8
↑ Wright, Paul E. (1992). „Two parallel processors with coupled inputs”. Advances in Applied Probability 24, 986–1007. o.
↑ Pinotsi, D. (2005). „Synchronized queues with deterministic arrivals”. Operations Research Letters 33 (6), 560–566. o. DOI:10.1016/j.orl.2004.12.005.
↑ 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.)
↑ „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.
↑ (2008. August) „Sojourn times in G/M/1 fork-join networks”. Naval Research Logistics 55 (5), 432–443. o. DOI:10.1002/nav.20294.
↑ ^a ^b 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.
↑ 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.)
↑ 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.)
↑ (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.
↑ 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.

[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.

[serfozo-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.

[pinotsi-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.

[nelson-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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]