ในการประมวลผลแบบขนาน การแย่งงาน ( Work Stealing)เป็น กลยุทธ์ การจัดตารางเวลาสำหรับ โปรแกรมคอมพิวเตอร์ แบบมัลติเธรด กลยุทธ์ นี้แก้ปัญหา การประมวลผล แบบมัลติเธรดแบบไดนามิกซึ่งสามารถ "สร้าง" เธรดการทำงานใหม่ได้ บน คอมพิวเตอร์ แบบมัลติเธรดแบบคงที่ที่มีจำนวนโปรเซสเซอร์ (หรือคอร์ ) คงที่ โดยทำได้อย่างมีประสิทธิภาพในแง่ของเวลาในการประมวลผล การใช้หน่วยความจำ และการสื่อสารระหว่างโปรเซสเซอร์

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

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

แนวคิดเรื่องการขโมยงานมีมาตั้งแต่การนำภาษาโปรแกรมMultilisp มาใช้ และการทำงานเกี่ยวกับ ภาษา โปรแกรมเชิงฟังก์ชัน แบบขนาน ในช่วงทศวรรษ 1980 ^{[ 2 ]}มีการนำไปใช้ในตัวกำหนดตารางเวลาสำหรับภาษาโปรแกรมCilk ^{[ 3 ]}เฟรม เวิร์ก Java fork/join ^{[ 4 ]}ไลบรารี Task Parallel ของ . NET ^{[ 5 ]}และรันไทม์Rust Tokio ^{[ 6 ] [ 7 ]}

การขโมยงานได้รับการออกแบบมาสำหรับโมเดลการแยกและเชื่อมต่อแบบ "เข้มงวด" ของการคำนวณแบบขนาน ซึ่งหมายความว่าการคำนวณสามารถมองได้ว่าเป็นกราฟแบบไม่มีวงจรที่มีทิศทางโดยมีแหล่งกำเนิดเดียว (จุดเริ่มต้นของการคำนวณ) และจุดสิ้นสุดเดียว (จุดสิ้นสุดของการคำนวณ) แต่ละโหนดในกราฟนี้แสดงถึงการแยกหรือการเชื่อมต่อการแยกจะสร้าง การคำนวณ แบบขนานเชิงตรรกะ หลายรายการ ซึ่งเรียกกันว่า "เธรด" ^{[ 2 ]}หรือ "สาย" ^{[ 8 ]}ขอบแสดงถึงการคำนวณแบบอนุกรม^{[ 9 ] [หมายเหตุ 1 ]}

ยกตัวอย่างเช่น ลองพิจารณาโปรแกรม fork–join ง่ายๆ ต่อไปนี้ใน รูปแบบไวยากรณ์คล้าย Cilk :

ฟังก์ชัน f(a, b): c ← fork g(a) d ← h(b) เข้าร่วม ส่งคืน c + d ฟังก์ชัน g(a): ส่งคืนค่า a × 2 ฟังก์ชัน h(a): b ← ส้อม g(a) c ← a + 1 เข้าร่วม ส่งคืน b + c

การเรียกฟังก์ชันf(1, 2)ทำให้เกิดกราฟการคำนวณดังต่อไปนี้:

ในกราฟ เมื่อเส้นเชื่อมสองเส้นออกจากโหนดหนึ่ง การคำนวณที่แสดงโดยป้ายกำกับเส้นเชื่อมนั้นจะขนานกันในเชิงตรรกะ กล่าวคือ อาจดำเนินการพร้อมกันหรือตามลำดับก็ได้ การคำนวณจะดำเนินต่อไปได้ก็ต่อ เมื่อการคำนวณที่แสดงโดยเส้นเชื่อม ขาเข้าเสร็จสมบูรณ์แล้วเท่านั้น หน้าที่ของตัวจัดตารางเวลาคือการจัดสรรการคำนวณ (เส้นเชื่อม) ให้กับโปรเซสเซอร์ในลักษณะที่ทำให้การคำนวณทั้งหมดเสร็จสมบูรณ์ตามลำดับที่ถูกต้อง (ตามข้อจำกัดของโหนดเชื่อม) โดยควรทำได้เร็วที่สุดเท่าที่จะเป็นไปได้

อัลกอริทึมการขโมยงานแบบสุ่มที่เสนอโดย Blumofe และ Leiserson นั้นรักษาเธรดการทำงานหลายเธรดและจัดสรรเธรดเหล่านี้ไปยังโปรเซสเซอร์แต่ละตัว โปรเซสเซอร์แต่ละตัวมีคิวแบบสองด้าน (deque) ของเธรด เรียกปลายของ deque ว่า "ด้านบน" และ "ด้านล่าง"${\displaystyle P}$

โปรเซสเซอร์แต่ละตัวที่มีเธรดปัจจุบันที่ต้องดำเนินการ จะดำเนินการคำสั่งในเธรดทีละคำสั่ง จนกว่าจะพบคำสั่งที่ทำให้เกิดพฤติกรรม "พิเศษ" สี่ประการ: ^{[ 2 ] : 10}

• คำ สั่ง spawnจะสร้างเธรดใหม่ขึ้นมา เธรดปัจจุบันจะถูกวางไว้ที่ด้านล่างสุดของ deque และโปรเซสเซอร์จะเริ่มทำงานเธรดใหม่นั้น
• คำ สั่งหยุดการทำงานชั่วคราว (stalling instruction) คือคำสั่งที่หยุดการทำงานของเธรดนั้นชั่วคราว โปรเซสเซอร์จะดึงเธรดออกจากด้านล่างของ deque และเริ่มการทำงานของเธรดนั้น หาก deque ว่างเปล่า โปรเซสเซอร์จะเริ่มกระบวนการขโมยงาน (work stealing) ซึ่งจะอธิบายต่อไป
• คำสั่งบางอย่างอาจทำให้เธรดหยุดทำงานพฤติกรรมในกรณีนี้จะเหมือนกับคำสั่งที่ทำให้เธรดหยุดชะงัก
• คำสั่งหนึ่งอาจเปิดใช้งานเธรดอื่น เธรดอื่นนั้นจะถูกผลักไปไว้ด้านล่างสุดของเดคิว แต่โปรเซสเซอร์ยังคงดำเนินการประมวลผลเธรดปัจจุบันต่อไป

ในขั้นต้น การคำนวณจะประกอบด้วยเธรดเดียวและถูกกำหนดให้กับโปรเซสเซอร์บางตัว ในขณะที่โปรเซสเซอร์อื่นๆ จะอยู่ในสถานะว่าง โปรเซสเซอร์ใดก็ตามที่กลายเป็นว่างจะเริ่มกระบวนการขโมยงาน ซึ่งหมายความว่าดังต่อไปนี้:

• โดยจะเลือกโปรเซสเซอร์อื่นแบบสุ่มอย่างสม่ำเสมอ
• หาก deque ของโปรเซสเซอร์ตัวอื่นไม่ว่างเปล่า มันจะดึงเธรดที่อยู่บนสุดออกจาก deque และเริ่มดำเนินการเธรดนั้น
• มิเช่นนั้น ให้ทำซ้ำ

มีการเสนอรูปแบบการขโมยงานหลายแบบ รูป แบบ สุ่มของ Blumofe และ Leiserson ดำเนินการคำนวณแบบขนานในเวลาที่คาดหวัง บนโปรเซสเซอร์ โดยที่คืองานหรือปริมาณเวลาที่จำเป็นในการดำเนินการคำนวณบนคอมพิวเตอร์แบบอนุกรมและคือช่วงปริมาณเวลาที่จำเป็นบนเครื่องขนานแบบอนันต์^{[หมายเหตุ 2 ]}ซึ่งหมายความว่าโดยเฉลี่ยแล้วเวลาที่ต้องการจะไม่เกินค่าคงที่คูณกับค่าต่ำสุดทางทฤษฎี^{[ 2 ]}อย่างไรก็ตาม เวลาในการทำงาน (โดยเฉพาะจำนวนการขโมยที่ดำเนินการ) อาจเป็นเลขชี้กำลังในกรณีที่เลวร้ายที่สุด^{[ 10 ]}รูปแบบเฉพาะที่ซึ่งโปรเซสเซอร์พยายามขโมยงานของตนเองกลับคืนมาเมื่อใดก็ตามที่ว่าง ก็ได้รับการวิเคราะห์ทั้งในเชิงทฤษฎีและเชิงปฏิบัติเช่นกัน^{[ 11 ] [ 12 ]}${\displaystyle T_{1}/P+O(T_{\infty })}$${\displaystyle P}$${\displaystyle T_{1}}$${\displaystyle T_{\infty }}$${\displaystyle T_{\infty }}$

สำหรับ i = 0 ถึง n: แยก f(i) ออกมาแล้วรวมเข้าด้วยกัน

อัลกอริทึมการขโมยงานตามที่ได้อธิบายไว้ก่อนหน้านี้และการวิเคราะห์นั้น ถือว่าสภาพแวดล้อมการคำนวณมีการกำหนดตารางการคำนวณไว้บนชุดของโปรเซสเซอร์เฉพาะ ใน สภาพแวดล้อม แบบมัลติโปรแกรมมิ่ง (มัลติทาสก์) อัลกอริทึมจะต้องได้รับการแก้ไขเพื่อกำหนดตารางงานการคำนวณไปยังกลุ่มของเธรดทำงานแทน ซึ่งเธรดทำงานเหล่านี้จะถูกกำหนดตารางไปยังโปรเซสเซอร์จริงโดยตัว กำหนดตารางเวลา ของระบบปฏิบัติการ ในเวลาใดก็ตาม ตัวกำหนดตารางเวลาของระบบปฏิบัติการจะกำหนดโปรเซสเซอร์จำนวนหนึ่ง P ≤ Pจาก โปรเซสเซอร์ Pในคอมพิวเตอร์ให้กับกระบวนการขโมยงาน เนื่องจากกระบวนการอื่นอาจกำลังใช้โปรเซสเซอร์ที่เหลืออยู่ ในการตั้งค่านี้ การขโมยงานด้วยกลุ่มเธรดทำงาน Pมีปัญหาที่ว่าเธรดทำงานที่ทำหน้าที่เป็นผู้ขโมยอาจทำให้เกิดภาวะติดขัดได้ กล่าวคือ พวกมันอาจขัดขวางการทำงานของเธรดทำงานที่จะสร้างงานที่มีประโยชน์ได้^{[ 14 ] [ 15 ]}

มีการคิดค้นวิธีการขโมยงานแบบหนึ่งขึ้นมาเพื่อใช้กับสถานการณ์นี้ ซึ่งจะทำการคำนวณให้เสร็จภายในเวลาที่คาดไว้

$${\displaystyle O\left({\frac {T_{1}}{P_{\mathrm {avg} }}}+{\frac {T_{\infty }P}{P_{\mathrm {avg} }}}\right),}$$

โดยที่P คือจำนวนเฉลี่ยของโปรเซสเซอร์ที่จัดสรรให้กับการคำนวณโดยตัวกำหนดตารางเวลาของระบบปฏิบัติการตลอดระยะเวลาการทำงานของการคำนวณ^{[ 16 ]} ตัวกำหนดตารางเวลาการทำงานแบบมัลติโปรแกรมมิ่งแตกต่างจากเวอร์ชันดั้งเดิมในสองประเด็น:

• คิวของระบบนี้ไม่ปิดกั้นการทำงาน แม้ว่าบนโปรเซสเซอร์เฉพาะ การเข้าถึงคิวสามารถซิงโครไนซ์ได้โดยใช้ล็อกแต่ไม่แนะนำให้ใช้ในสภาพแวดล้อมแบบมัลติโปรแกรมมิ่ง เนื่องจากระบบปฏิบัติการอาจแย่งการทำงานของเธรดที่ถือล็อกอยู่ ทำให้การทำงานของเธรดอื่นที่พยายามเข้าถึงคิวเดียวกันหยุดชะงัก
• ก่อนที่จะพยายามขโมยงานในแต่ละครั้ง เธรดการทำงานจะเรียกใช้ระบบ " yield " ซึ่งจะปล่อยโปรเซสเซอร์ที่มันถูกกำหนดให้ทำงานให้กับระบบปฏิบัติการ เพื่อป้องกันการอดอยาก

ความพยายามในการปรับปรุงตัวขโมยงานมัลติโปรแกรมมิ่งมุ่งเน้นไปที่ปัญหาความใกล้เคียงของแคช^{[ 12 ]}และโครงสร้างข้อมูลคิวที่ได้รับการปรับปรุง^{[ 17 ]}

อัลกอริทึมการจัดตารางเวลาหลายรายการสำหรับการคำนวณแบบมัลติเธรดแบบไดนามิกแข่งขันกับการขโมยงาน นอกจากวิธีการแบ่งปันงานแบบดั้งเดิมแล้ว ยังมีตัวจัดตารางเวลาที่เรียกว่าparallel depth-first (PDF) ซึ่งปรับปรุงขอบเขตพื้นที่ของการขโมยงาน^{[ 18 ]}และยังให้ประสิทธิภาพที่ดีกว่าในบางสถานการณ์ที่คอร์ของชิปมัลติโปรเซสเซอร์ใช้แคชร่วมกัน^{[ 1 ]}