คิวแบบ Fork-join

Q: คำนิยาม

เมื่อมาถึงจุดแยก งานจะถูกแบ่งออกเป็นงานย่อย N งาน ซึ่งแต่ละงานจะได้รับการบริการจากเซิร์ฟเวอร์ N เครื่อง หลังจากบริการเสร็จสิ้น งานย่อยจะรอจนกว่างานย่อยอื่นๆ ทั้งหมดจะได้รับการประมวลผลเสร็จสิ้น จากนั้นงานย่อยจะรวมกันอีกครั้งและออกจากระบบ [ 3 ]

Q: แอปพลิเคชัน

คิวแบบ Fork–join ถูกนำมาใช้เพื่อสร้างแบบจำลองระบบ RAID แบบแบ่งโซน [ 9 ] การคำนวณแบบขนาน [ 2 ] และเพื่อสร้างแบบจำลองการดำเนินการตามคำสั่งซื้อในคลังสินค้า [ 3 ]

Q: เวลาตอบสนอง

เวลาตอบสนอง (หรือเวลาพัก [ 10 ] ) คือระยะเวลาทั้งหมดที่งานใช้ในระบบ

ในทฤษฎีการเข้าคิวซึ่งเป็นสาขาหนึ่งในทฤษฎีความน่าจะเป็น ทางคณิตศาสตร์ คิวแบบแยกและรวม ( fork–join queue)คือคิวที่งานขาเข้าจะถูกแยกออกเมื่อมาถึงเพื่อให้บริการโดยเซิร์ฟเวอร์จำนวนมาก และรวมเข้าด้วยกันก่อนที่จะออกจากคิว^{[ 1 ]}แบบจำลองนี้มักใช้สำหรับการคำนวณแบบขนาน^{[ 2 ]}หรือระบบที่ต้องได้รับผลิตภัณฑ์พร้อมกันจากซัพพลายเออร์ที่แตกต่างกัน (ในคลังสินค้าหรือโรงงานผลิต) ^{[ 3 ]}^{: 78–80}ปริมาณสำคัญที่น่าสนใจในแบบจำลองนี้มักจะเป็นเวลาที่ใช้ในการให้บริการงานให้เสร็จสมบูรณ์ แบบจำลองนี้ได้รับการอธิบายว่าเป็น "แบบจำลองสำคัญสำหรับการวิเคราะห์ประสิทธิภาพของระบบ แบบขนานและ แบบกระจาย " ^[⁴^]มีผลการวิเคราะห์น้อยมากสำหรับคิวแบบแยกและรวม แต่มีการประมาณค่าต่างๆ ที่เป็นที่รู้จัก

สถานการณ์ที่งานมาถึงตามกระบวนการปัวซงและเวลาให้บริการมีการกระจายแบบเอกซ์โปเนนเชียล บางครั้งเรียกว่าแบบจำลอง Flatto–Hahn–Wrightหรือ แบบ จำลองFHW ^{[ 5 ]}^{[ 6 ]}^{[ 7 ]}

คำนิยาม

เมื่อมาถึงจุดแยก งานจะถูกแบ่งออกเป็นงานย่อยN งาน ซึ่งแต่ละงานจะได้รับการบริการจากเซิร์ฟเวอร์ Nเครื่อง หลังจากบริการเสร็จสิ้น งานย่อยจะรอจนกว่างานย่อยอื่นๆ ทั้งหมดจะได้รับการประมวลผลเสร็จสิ้น จากนั้นงานย่อยจะรวมกันอีกครั้งและออกจากระบบ^{[ 3 ]}

เพื่อให้คิวแยกและรวมมีเสถียรภาพ อัตราการป้อนข้อมูลจะต้องน้อยกว่าผลรวมของอัตราการให้บริการที่โหนดบริการอย่างเคร่งครัด^{[ 8 ]}

แอปพลิเคชัน

คิวแบบ Fork–join ถูกนำมาใช้เพื่อสร้างแบบจำลองระบบRAID แบบแบ่งโซน ^{[ 9 ]}การคำนวณแบบขนาน^{[ 2 ]}และเพื่อสร้างแบบจำลองการดำเนินการตามคำสั่งซื้อในคลังสินค้า^{[ 3 ]}

เวลาตอบสนอง

เวลาตอบสนอง (หรือเวลาพัก^{[ 10 ]} ) คือระยะเวลาทั้งหมดที่งานใช้ในระบบ

การกระจาย

Ko และ Serfozo ให้ค่าประมาณสำหรับการกระจายเวลาตอบสนองเมื่อเวลาบริการมีการกระจายแบบเอกซ์โปเนนเชียลและงานมาถึงตามกระบวนการปัวซง^{[ 11 ]}หรือการกระจายทั่วไป^{[ 12 ]} QIu, Pérez และ Harrison ให้วิธีการประมาณเมื่อเวลาบริการมี การ กระจายแบบเฟส^{[ 13 ]}

เวลาตอบสนองเฉลี่ย

สูตรที่แน่นอนสำหรับเวลาตอบสนองเฉลี่ยจะทราบได้เฉพาะในกรณีที่มีเซิร์ฟเวอร์สองตัว ( N = 2) ที่มีเวลาให้บริการแบบกระจายแบบเอกซ์โปเนนเชียล (โดยที่แต่ละเซิร์ฟเวอร์เป็นคิว M/M/1 ) ในสถานการณ์นี้ เวลาตอบสนอง (เวลาทั้งหมดที่งานใช้ในระบบ) คือ^{[ 14 ]}

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

ที่ไหน

$\rho =\lambda /\mu$ คือการใช้ประโยชน์
$\lambda$ คืออัตราการมาถึงของงานไปยังโหนดทั้งหมด
$\mu$ คืออัตราการให้บริการทั่วทุกโหนด

ในสถานการณ์ที่โหนดเป็นคิว M/M/1และN > 2 การปรับเปลี่ยน การวิเคราะห์ค่าเฉลี่ย ของ Varki ยังสามารถใช้เพื่อให้ค่าโดยประมาณสำหรับเวลาตอบสนองเฉลี่ยได้อีกด้วย^[¹⁵^]

สำหรับเวลาให้บริการทั่วไป (โดยที่แต่ละโหนดเป็นคิว M/G/1 ) Baccelli และ Makowski ให้ขอบเขตสำหรับเวลาตอบสนองเฉลี่ยและโมเมนต์ ที่สูงกว่า ของปริมาณนี้ทั้งในสถานการณ์ชั่วคราวและสภาวะคงที่^{[ 16 ]} Kemper และ Mandjes แสดงให้เห็นว่าสำหรับพารามิเตอร์บางตัว ขอบเขตเหล่านี้ไม่แน่นหนาและแสดงเทคนิคการประมาณค่า^{[ 10 ]}สำหรับคิวแยก-รวมแบบไม่เป็นเนื้อเดียวกัน (คิวแยก-รวมที่มีเวลาให้บริการต่างกัน) Alomari และ Menasce เสนอการประมาณค่าโดยใช้จำนวนฮาร์มอนิกที่สามารถขยายเพื่อครอบคลุมกรณีทั่วไปมากขึ้น เช่น คิวแยก-รวมแบบความน่าจะเป็น คิวแยก-รวมแบบเปิดและแบบปิด^{[ 17 ]}

การกระจายงานย่อย

การกระจายงานย่อย ซึ่งกำหนดให้เป็นช่วงเวลาการให้บริการ สามารถคำนวณได้ทางตัวเลข และสามารถนำความล่าช้าแบบกำหนดที่เหมาะสมที่สุดมาใช้เพื่อลดช่วงเวลาดังกล่าวให้น้อยที่สุด^{[ 18 ]}

การกระจายแบบคงที่

โดยทั่วไปการกระจายแบบคงที่ของจำนวนงานในแต่ละคิวนั้นยากที่จะคำนวณได้^{[ 11 ]} Flatto พิจารณากรณีของเซิร์ฟเวอร์สองตัว ( N=2 ) และได้มาจากการกระจายแบบคงที่สำหรับจำนวนงานในแต่ละคิวโดยใช้เทคนิคการทำให้เป็นมาตรฐาน^{[ 5 ]} Pinotsi และ Zazanis แสดงให้เห็นว่า มี วิธีแก้ปัญหาในรูปแบบผลคูณเมื่อการมาถึงเป็นแบบกำหนดได้เนื่องจากความยาวของคิวจะเป็นคิว D/M/1 ที่เป็นอิสระต่อ กัน^{[ 7 ]}

การประมาณค่าการจราจรหนาแน่น/การกระจายตัว

เมื่อเซิร์ฟเวอร์มีภาระงานมาก (อัตราการให้บริการของคิวมากกว่าอัตราการมาถึงเพียงเล็กน้อย) กระบวนการความยาวคิวสามารถประมาณได้ด้วยการเคลื่อนที่แบบบราวน์สะท้อนซึ่งลู่เข้าสู่การกระจายสถานะคงที่แบบเดียวกันกับกระบวนการคิวเดิม^{[ 19 ]}^{[ 20 ]}ภายใต้เงื่อนไขที่จำกัด พื้นที่สถานะของคิวการซิงโครไนซ์จะยุบตัวลง และคิวทั้งหมดจะมีพฤติกรรมเหมือนกัน^{[ 21 ]}

การกระจายคิวการเข้าร่วม

เมื่อให้บริการงานเสร็จแล้ว ชิ้นส่วนต่างๆ จะถูกประกอบใหม่ที่คิวรวม Nelson และ Tantawi ได้เผยแพร่การกระจายความยาวของคิวรวมในสถานการณ์ที่เซิร์ฟเวอร์ทั้งหมดมีอัตราการให้บริการเท่ากัน^{[ 14 ]}อัตราการให้บริการที่ไม่เหมือนกันและการวิเคราะห์เชิงอะซิมโทติก ของการกระจายได้ รับการพิจารณาโดย Li และ Zhao ^{[ 22 ]}

เครือข่ายของคิวแบบแยกและรวม

สามารถใช้สูตรโดยประมาณในการคำนวณการกระจายเวลาตอบสนองสำหรับเครือข่ายคิวแบบแยกและเชื่อมต่อที่เชื่อมต่อกันเป็นอนุกรม (ทีละคิว) ^{[ 23 ]}

แบบจำลองการแยกและการรวม

โมเดลที่เกี่ยวข้องคือโมเดลแยก-ผสาน ซึ่งมีผลลัพธ์เชิงวิเคราะห์อยู่แล้ว^{[ 2 ]}^{[ 24 ]}ผลลัพธ์ที่แม่นยำสำหรับคิวแยก-ผสานนั้นได้มาจาก Fiorini และ Lipsky ^{[ 25 ]} ในที่นี้ เมื่อมาถึง งานจะถูกแบ่งออกเป็นงาน ย่อย Nงาน ซึ่งจะได้รับการบริการแบบขนาน เฉพาะเมื่องานทั้งหมดเสร็จสิ้นการบริการและกลับมารวมกันแล้วเท่านั้น งานถัดไปจึงจะเริ่มต้นได้ ซึ่งส่งผลให้เวลาตอบสนองโดยเฉลี่ยช้าลง

ระบบแยกและเชื่อมต่อแบบทั่วไป (n,k)

การขยายความทั่วไปของระบบคิวแบบแยกสาขาและเข้าร่วม (fork-join queueing system) คือ $(n,k)$ ระบบ fork-join ที่งานจะออกจากระบบเมื่อใดก็ตามที่... $k$ จาก $n$ งานต่างๆ ได้รับการดำเนินการ ระบบคิวแบบแยกสาขาและรวมสาขาแบบดั้งเดิมเป็นกรณีพิเศษของระบบนี้ $(n,k)$ ระบบเมื่อ $k=n$ Joshi, Liu และ Soljanin ได้ค้นพบขอบเขตของเวลาตอบสนองเฉลี่ยของระบบทั่วไปนี้^{[ 26 ]}^{[ 27 ]}

[ 1 ]

[ 2 ]

[ 3 ]

[

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[

[ 16 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]