صف فورک-جوین (fork-join)
در تئوری صف، با توجه به تئوری احتمالات در علم ریاضی، صف fork-join را اینگونه تعریف میکنیم که صفی است که کارهای ورودی به چند بخش تقسیم میشوند تا سرورها بتوانند به کارهای ورودی سرویس دهند، و در انتها ادغام میشوند[۱]. این مدل بیشتر برای محاسباتهای موازی[۲] یا در سامانههایی که برای تولید محصول از چندین تامینکننده نیاز است(کارگاههای تولیدی)، استفاده میشود[۳]. در این مدلها مسئلهای که مورد بررسی قرار میگیرد معمولاً زمانی است که طول میکشد تا یک کار به اتمام برسد.
مدل را میتوان اینگونه تعریف کرد: "مدلی اساسی برای آنالیز سیستمهای موازی و توزیع شده."[۴]
جواب تحلیلی کمی برای صفهای fork-join وجود دارد ولی چندین تقریب برای آن شناخته شده است.
زمانی که ورودی کارها بر اساس فرایند پواسون و زمان سرویسها بر مبنای توزیع نمایی باشد از آن به عنوان مدل Flatto–Hahn–Wright یا مدل FHW یاد میکنند.[۵]
تعریف
ویرایشهنگام رسیدن یک کار در نقطهی fork (جدایی)، کار به N زیر کار تبدیل میشود که هر کدام توسط یکی از N سرور سرویسدهی میشوند. بعد از سرویس دهی زیرکارها منتظر میمانند تا تمامی زیر کارها پردازش شوند. سپس تمامی زیرکارها به هم متصل میشوند و سیستم را ترک میکنند.[۳]
برای این که صف fork-join پایدار بماند نیاز است که میزان نرخ زمان ورودیها از مجموع نرخ زمانی زیرکارها کمتر باشد.[۶]
زمان پاسخ
ویرایشزمان پاسخ در این مدل برابر با کل زمانی است که یک کار در سیستم سپری میکند.
توزیع
ویرایشKo و Serfozo یک تقریبی برای توزیع زمان پاسخ ارائه داده اند، هنگامی که زمان سرویس دهی ها توزیع نمایی و زمان ورود کارها دارای توزیع پواسون یا general باشند[۷].
میانگین زمان پاسخ
ویرایشفرمول دقیق برای میانگین زمان پاسخ تنها برای حالتی که تعداد سرورها برابر 2 است شناخته شده است، با شرایطی که زمان سرویسدهیها از توزیع پواسون برخوردار باشد. در این شرایط زمان پاسخ برابر است با[۸]:
هنگامی که که:
- λ برابر با نرخ ورودی کارها به سیستم
- Μ برابر با نرخ تمامی سرویسدهیها روی تمامی گرهها
برای حالت سرویسدهی کلی ، 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)