صف فورک-جوین (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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ 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.