Wikipédia

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

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]

 

ahol

  •   a felhasználás
  •   a rendszerbe érkező feladatok üteme
  •   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

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, 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. ↑ 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. [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. 
A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Elosztó_típusú_sorban_állás&oldid=25937790”