Elosztó típusú sorban állás

A Wikipédiából, a szabad enciklopédiából

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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ő[szerkesztés | forrásszöveg szerkesztése]

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ő[szerkesztés | forrásszöveg szerkesztése]

Exakt 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[szerkesztés | forrásszöveg szerkesztése]

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

Kapcsolódó szócikkek[szerkesztés | forrásszöveg szerkesztése]

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

  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. ^ a b c Serfozo, Richard. Basics of Applied Stochastic Processes. Springer (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. DOI:10.2307/3214417.  
  6. Modelling Zoned RAID Systems using Fork-Join Queueing Simulation6th European Performance Engineering Workshop (EPEW 2009). Lecture Notes in Computer Science 5652: 16–29, Springer Verlag. doi:10.1007/978-3-642-02924-0. 
  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. ^ 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.  
  9. Varki, Elizabeth: M/M/1 Fork-join queue with variable sub-tasks
  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 ideje: 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.