صف فورک-جوین (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 زیرکار تقسیم می‌شود که همزمان به صورت موازی سرویس‌دهی می‌شوند.هنگامی که تمامی زیر کارها به اتمام رسیدند و به یکدیگر پیوستن کار بعدی می‌تواند شروع به سرویس‌دهی شود. این کار باعث کند شدن میانگین زمان پاسخ می شود.

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

  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.  Check date values in: |date= (help)
  2. ۲٫۰ ۲٫۱ Lebrecht, Abigail; Knottenbelt, William J. (June 2007). "Response Time Approximations in Fork-Join Queues". 23rd Annual UK Performance Engineering Workshop (UKPEW). 
  3. ۳٫۰ ۳٫۱ Serfozo, Richard (2009). Basics of Applied Stochastic Processes. Springer. p. 78–80. ISBN 3540893318. 
  4. Boxma, Onno; Koole, Ger and Liu, Zhen (1996). Queueing-theoretic Solution Methods for Models of Parallel and Distributed Systems (Technical report). CWI. BS-R9425. 
  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 (September 1989). "Stationary and Stability of Fork-Join Networks". Journal of Applied Probability 26 (3): 604–614. doi:10.2307/3214417. 
  7. Ko, Sung-Seok; Serfozo, Richard F. (August 2008). "Sojourn times in G/M/1 fork-join networks". Naval Research Logistics 55 (5): 432–443. doi:10.1002/nav.20294. 
  8. Nelson, Randolph; Tantawi, Asser N. (June 1988). "Approximate analysis of fork/join synchronization in parallel queues". IEEE Transactions on Computers 37 (6): 739–743. doi:10.1109/12.2213. 
  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) 4705. Springer. pp. 758–766. doi:10.1007/978-3-540-74472-6_62. 
  11. Harrison, Peter G.; Zertal, Soroya (August 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. 

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