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