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]

Tartalomjegyzék

Működés [szerkeszté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 [szerkeszté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ő [szerkesztés]

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]

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]

  • Baccelli, François; Makowski: Simple computable bounds for the fork-join queue,. 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. Probability in the Engineering and Informational Sciences 24 (4). 2010. 473–483. o.

Kapcsolódó szócikkek [szerkesztés]

Jegyzetek [szerkesztés]

  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. ↑ Sablon:Cite
  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 Simulation” 6th 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. ↑ Sablon:Cite
  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. 
A lap eredeti címe: „http://hu.wikipedia.org/w/index.php?title=Elosztó_típusú_sorban_állás&oldid=13406973”