صف فورک-جوین (fork-join)

در تئوری صف، با توجه به تئوری احتمالات در علم ریاضی، صف fork-join را اینگونه تعریف می‌کنیم که صفی است که کارهای ورودی به چند بخش تقسیم می‌شوند تا سرورها بتوانند به کارهای ورودی سرویس دهند، و در انتها ادغام می‌شوند^[۱]. این مدل بیشتر برای محاسبات‌های موازی^[۲] یا در سامانه‌هایی که برای تولید محصول از چندین تامین‌کننده نیاز است(کارگاه‌های تولیدی)، استفاده می‌شود^[۳]. در این مدل‌ها مسئله‌ای که مورد بررسی قرار می‌گیرد معمولاً زمانی است که طول می‌کشد تا یک کار به اتمام برسد.
مدل را می‌توان اینگونه تعریف کرد: "مدلی اساسی برای آنالیز سیستم‌های موازی و توزیع شده."^[۴]

جواب تحلیلی کمی برای صف‌های fork-join وجود دارد ولی چندین تقریب برای آن شناخته شده است.

زمانی که ورودی کارها بر اساس فرایند پواسون و زمان سرویس‌ها بر مبنای توزیع نمایی باشد از آن به عنوان مدل Flatto–Hahn–Wright یا مدل FHW یاد می‌کنند.^[۵]

تعریف[ویرایش]

هنگام رسیدن یک کار در نقطه‌ی fork (جدایی)، کار به N زیر کار تبدیل می‌شود که هر کدام توسط یکی از N سرور سرویس‌دهی می‌شوند. بعد از سرویس دهی زیرکارها منتظر می‌مانند تا تمامی زیر کارها پردازش شوند. سپس تمامی زیرکارها به هم متصل می‌شوند و سیستم را ترک می‌کنند.^[۳]

برای این که صف fork-join پایدار بماند نیاز است که میزان نرخ زمان ورودی‌ها از مجموع نرخ زمانی زیرکارها کمتر باشد.^[۶]

زمان پاسخ[ویرایش]

زمان پاسخ در این مدل برابر با کل زمانی است که یک کار در سیستم سپری می‌کند.

توزیع[ویرایش]

Ko و Serfozo یک تقریبی برای توزیع زمان پاسخ ارائه داده اند، هنگامی که زمان سرویس دهی ها توزیع نمایی و زمان ورود کارها دارای توزیع پواسون یا general باشند^[۷].

میانگین زمان پاسخ[ویرایش]

فرمول دقیق برای میانگین زمان پاسخ تنها برای حالتی که تعداد سرورها برابر 2 است شناخته شده است، با شرایطی که زمان سرویس‌دهی‌ها از توزیع پواسون برخوردار باشد. در این شرایط زمان پاسخ برابر است با^[۸]:

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

هنگامی که که:

$\rho =\lambda /\mu$
λ برابر با نرخ ورودی کارها به سیستم
Μ برابر با نرخ تمامی سرویس‌دهی‌ها روی تمامی گره‌ها

برای حالت سرویس‌دهی کلی ، Baccelli و Makowski برای میانگین زمان پاسخگویی، حدودی، و مقدار moment بیشتری در حالت گذرا و ایستا می‌دهند. Kemper و Mandjes نشان می‌دهند که برای بعضی از متغیرها این حدودها دقیق نیستند و یک تکنیک تقریبی برای آن ارائه می‌دهند.

توزیع ایستا[ویرایش]

به طور کلی توزیع ایستای چند کار در هر صف قابل بررسی نیست. Flatto حالت دو سروری را در نظر گرفت و یک توزیع ایستا برای تعداد کارها در هر صف با کمک تکنیک uniformization بدست آورد. Pinotsi و Zazanis نشان می‌دهند که محصولی از جواب وجود خواهد داشت هنگامی که ورودی‌ها قطعی (deterministic) و طول صف‌ها، از صف مستقل D/M/1 پیروی کنند.

توزیع پیوستن صف[ویرایش]

هنگامی که کارها انجام شدند و به پایان رسیدند، قطعه‌ها در صفِ پیوستن به یکدیگر متصل می‌شوند. Nelson و Tantawi یک توزیع برای صفِ پیوستن منتشر کردند در حالتی که تمامی سرورها نرخ سرویس‌دهی یکسان داشته باشند. توزیع آنالیزی مجانبی نیز توسط Jun و Li مطرح شده است^[۹].

شبکه‌های صف‌های fork-join[ویرایش]

برای محاسبه‌ی زمان پاسخگویی برای شبکه‌ی صف‌های fork-join که سری هستند می‌توان از یک فرمول تقریبی استفاده کرد^[۱۰] .

مدل Split-merg(جدا شدن و بهم پیوستن)[ویرایش]

یک مدل مرتبط مدل split-merge است^[۲]^[۱۱]، که نتایج آنالیزی برای آن وجود دارد. در این مدل یک کار با ورودش به N زیرکار تقسیم می‌شود که همزمان به صورت موازی سرویس‌دهی می‌شوند.هنگامی که تمامی زیر کارها به اتمام رسیدند و به یکدیگر پیوستن کار بعدی می‌تواند شروع به سرویس‌دهی شود. این کار باعث کند شدن میانگین زمان پاسخ می شود.

منابع[ویرایش]

↑ Kim, C.; Agrawala, A. K. (Feb. 1989). "Analysis of the Fork-Join Queue". IEEE Transactions on Computers. 38 (2): 250–255. doi:10.1109/12.16501. {{cite journal}}: Check date values in: |date= (help)
↑ ^۲٫۰ ^۲٫۱ Lebrecht, Abigail; Knottenbelt, William J. (2007). "Response Time Approximations in Fork-Join Queues" (PDF). 23rd Annual UK Performance Engineering Workshop (UKPEW). Archived from the original (PDF) on 29 October 2013. Retrieved 9 December 2011. {{cite journal}}: Unknown parameter |month= ignored (help)
↑ ^۳٫۰ ^۳٫۱ Serfozo, Richard (2009). Basics of Applied Stochastic Processes. Springer. p. 78–80. ISBN 3540893318.
↑ Boxma, Onno (1996). Queueing-theoretic Solution Methods for Models of Parallel and Distributed Systems (PDF) (Technical report). CWI. BS-R9425. Archived from the original (PDF) on 19 March 2012. Retrieved 9 December 2011. {{cite techreport}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
↑ Pinotsi, D.; Zazanis, M.A. (2005). "Synchronized queues with deterministic arrivals". Operations Research Letters. 33 (6): 560–566. doi:10.1016/j.orl.2004.12.005.
↑ Konstantopoulos, Panagiotis; Walrand, Jean (1989). "Stationary and Stability of Fork-Join Networks" (PDF). Journal of Applied Probability. 26 (3): 604–614. doi:10.2307/3214417. Archived from the original (PDF) on 18 March 2012. Retrieved 9 December 2011. {{cite journal}}: Unknown parameter |month= ignored (help)
↑ Ko, Sung-Seok; Serfozo, Richard F. (2008). "Sojourn times in G/M/1 fork-join networks". Naval Research Logistics. 55 (5): 432–443. doi:10.1002/nav.20294. {{cite journal}}: Unknown parameter |month= ignored (help)
↑ Nelson, Randolph; Tantawi, Asser N. (1988). "Approximate analysis of fork/join synchronization in parallel queues". IEEE Transactions on Computers. 37 (6): 739–743. doi:10.1109/12.2213. {{cite journal}}: Unknown parameter |month= ignored (help)
↑ Li, Jun; Zhao, Yiqiang Q. (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. doi:10.1017/S0269964810000112.
↑ Ko, Sung-Seok (2007). "Cycle Times in a Serial Fork-Join Network". Lecture Notes in Computer Science. International Conference on Computational Science and Its Applications (ICCSA 2007). Vol. 4705. Springer. pp. 758–766. doi:10.1007/978-3-540-74472-6_62.
↑ Harrison, Peter G.; Zertal, Soroya (2003). "Queueing models with maxima of service times". Lecture Notes in Computer Science. Lecture Notes in Computer Science. 2794: 152–168. doi:10.1007/978-3-540-45232-4_10. ISBN 978-3-540-40814-7. {{cite journal}}: Unknown parameter |month= ignored (help)

پیوند به بیرون[ویرایش]

[1] Kim, C.; Agrawala, A. K. (Feb. 1989). "Analysis of the Fork-Join Queue". IEEE Transactions on Computers. 38 (2): 250–255. doi:10.1109/12.16501. {{cite journal}}: Check date values in: |date= (help)

[rtapprox-2] ۲٫۰ ^۲٫۱ Lebrecht, Abigail; Knottenbelt, William J. (2007). "Response Time Approximations in Fork-Join Queues" (PDF). 23rd Annual UK Performance Engineering Workshop (UKPEW). Archived from the original (PDF) on 29 October 2013. Retrieved 9 December 2011. {{cite journal}}: Unknown parameter |month= ignored (help)

[serfozo-3] ۳٫۰ ^۳٫۱ Serfozo, Richard (2009). Basics of Applied Stochastic Processes. Springer. p. 78–80. ISBN 3540893318.

[4] Boxma, Onno (1996). Queueing-theoretic Solution Methods for Models of Parallel and Distributed Systems (PDF) (Technical report). CWI. BS-R9425. Archived from the original (PDF) on 19 March 2012. Retrieved 9 December 2011. {{cite techreport}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)

[pinotsi-5] Pinotsi, D.; Zazanis, M.A. (2005). "Synchronized queues with deterministic arrivals". Operations Research Letters. 33 (6): 560–566. doi:10.1016/j.orl.2004.12.005.

[6] Konstantopoulos, Panagiotis; Walrand, Jean (1989). "Stationary and Stability of Fork-Join Networks" (PDF). Journal of Applied Probability. 26 (3): 604–614. doi:10.2307/3214417. Archived from the original (PDF) on 18 March 2012. Retrieved 9 December 2011. {{cite journal}}: Unknown parameter |month= ignored (help)

[7] Ko, Sung-Seok; Serfozo, Richard F. (2008). "Sojourn times in G/M/1 fork-join networks". Naval Research Logistics. 55 (5): 432–443. doi:10.1002/nav.20294. {{cite journal}}: Unknown parameter |month= ignored (help)

[nelson-8] Nelson, Randolph; Tantawi, Asser N. (1988). "Approximate analysis of fork/join synchronization in parallel queues". IEEE Transactions on Computers. 37 (6): 739–743. doi:10.1109/12.2213. {{cite journal}}: Unknown parameter |month= ignored (help)

[9] Li, Jun; Zhao, Yiqiang Q. (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. doi:10.1017/S0269964810000112.

[10] Ko, Sung-Seok (2007). "Cycle Times in a Serial Fork-Join Network". Lecture Notes in Computer Science. International Conference on Computational Science and Its Applications (ICCSA 2007). Vol. 4705. Springer. pp. 758–766. doi:10.1007/978-3-540-74472-6_62.

[11] Harrison, Peter G.; Zertal, Soroya (2003). "Queueing models with maxima of service times". Lecture Notes in Computer Science. Lecture Notes in Computer Science. 2794: 152–168. doi:10.1007/978-3-540-45232-4_10. ISBN 978-3-540-40814-7. {{cite journal}}: Unknown parameter |month= ignored (help)

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]

[۱۰]

[۱۱]