อัลกอริทึมของเดกเกอร์
อัลกอริทึมของ Dekkerเป็นวิธีแก้ปัญหาที่ถูกต้องวิธีแรกที่ทราบกันดีสำหรับ ปัญหา การกีดกันร่วมกันในการเขียนโปรแกรมแบบขนานซึ่งกระบวนการต่างๆ สื่อสารกันผ่านหน่วยความจำที่ใช้ร่วมกันเท่านั้น วิธีแก้ปัญหานี้ได้รับการระบุว่าเป็นผลงานของนักคณิตศาสตร์ชาวดัตช์Th. J. DekkerโดยEdsger W. Dijkstraในเอกสารที่ยังไม่ได้ตีพิมพ์เกี่ยวกับการอธิบายกระบวนการแบบลำดับ[ 1 ]และต้นฉบับของเขาเกี่ยวกับกระบวนการแบบลำดับที่ร่วมมือกัน [ 2 ] วิธีนี้ช่วยให้เธรดสองเธรดสามารถใช้ทรัพยากรแบบใช้ครั้งเดียวร่วมกันได้โดยไม่มีข้อขัดแย้ง โดยใช้เพียงหน่วยความจำที่ใช้ร่วมกันสำหรับการสื่อสาร
อัลกอริทึมนี้หลีกเลี่ยงการสลับกันอย่างเคร่งครัดของอัลกอริทึมการผลัดกันเล่นแบบง่ายๆ และเป็นหนึ่งใน อัลกอริทึม การกีดกันซึ่งกันและกัน ชุดแรกๆ ที่ถูกคิดค้นขึ้น
ภาพรวม
หากกระบวนการสองกระบวนการพยายามเข้าสู่ส่วนวิกฤตพร้อมกัน อัลกอริทึมจะอนุญาตให้เพียงกระบวนการเดียวเข้าไป โดยพิจารณาจากลำดับ ของ กระบวนการนั้น หากมีกระบวนการหนึ่งอยู่ในส่วนวิกฤตแล้ว กระบวนการอื่นจะรอจนกว่ากระบวนการแรกจะออกจากส่วนวิกฤต การดำเนินการนี้ทำได้โดยใช้แฟล็กสองตัว คือwants_to_enter[0]และwants_to_enter[1]ซึ่งระบุความตั้งใจที่จะเข้าสู่ส่วนวิกฤตของกระบวนการ 0 และ 1 ตามลำดับ และตัวแปรturnที่ระบุว่ากระบวนการใดมีลำดับความสำคัญมากกว่ากัน
อัลกอริทึมของ Dekker สามารถแสดงเป็นรหัสเทียมได้ดังนี้[ 3 ]
ตัวแปร wants_to_enter : อาร์เรย์ของค่าบูลีน 2 ค่า เทิร์น : จำนวนเต็ม wants_to_enter[0] ← false wants_to_enter[1] ← false หมุน ← 0 // หรือ 1 | |
p0: wants_to_enter[0] ← true ในขณะที่ต้องการเข้า[1] { ถ้าเทิร์น ≠ 0 { wants_to_enter[0] ← false ในขณะที่เทิร์น ≠ 0 { // รอแบบไม่ว่าง } wants_to_enter[0] ← true } } // ส่วนวิกฤต ... เลี้ยว ← 1 wants_to_enter[0] ← false // ส่วนที่เหลือ | หน้า 1: wants_to_enter[1] ← true ในขณะที่ต้องการเข้า[0] { ถ้าเทิร์น ≠ 1 { wants_to_enter[1] ← false ในขณะที่เทิร์น ≠ 1 { // รอแบบไม่ว่าง } wants_to_enter[1] ← true } } // ส่วนวิกฤต ... เลี้ยว ← 0 wants_to_enter[1] ← false // ส่วนที่เหลือ |
กระบวนการต่างๆ จะแสดงเจตนาที่จะเข้าสู่ส่วนวิกฤต ซึ่งจะถูกตรวจสอบโดยลูป while ภายนอก หากกระบวนการอื่นไม่ได้แสดงเจตนา ก็สามารถเข้าสู่ส่วนวิกฤตได้อย่างปลอดภัยโดยไม่คำนึงถึงลำดับการทำงานในปัจจุบัน การกีดกันซึ่งกันและกันจะยังคงได้รับการรับประกัน เนื่องจากไม่มีกระบวนการใดสามารถกลายเป็นส่วนวิกฤตได้ก่อนที่จะตั้งค่าแฟล็กของตน (ซึ่งหมายความว่าอย่างน้อยหนึ่งกระบวนการจะเข้าสู่ลูป while) นอกจากนี้ยังรับประกันความคืบหน้าเนื่องจากจะไม่เกิดการรอคอยในกระบวนการที่ถอนเจตนาที่จะเป็นส่วนวิกฤต ในทางกลับกัน หากตัวแปรของกระบวนการอื่นถูกตั้งค่า ลูป while จะถูกเข้า และตัวแปรลำดับการทำงานจะกำหนดว่าใครได้รับอนุญาตให้เป็นส่วนวิกฤต กระบวนการที่ไม่มีลำดับความสำคัญจะถอนเจตนาที่จะเข้าสู่ส่วนวิกฤตจนกว่าจะได้รับลำดับความสำคัญอีกครั้ง (ลูป while ภายใน) กระบวนการที่มีลำดับความสำคัญจะออกจากลูป while และเข้าสู่ส่วนวิกฤตของตน
อัลกอริทึมของ Dekker รับประกันการกีดกันซึ่งกันและกันการปราศจากภาวะติดตายและการปราศจากภาวะอดอยาก มาดูกันว่าทำไมคุณสมบัติสุดท้ายจึงเป็นจริง สมมติว่า p0 ติดอยู่ใน ลูป while wants_to_enter[1]ตลอดไป เนื่องจากปราศจากภาวะติดตาย ในที่สุด p1 จะดำเนินการไปยังส่วนวิกฤตและตั้งค่าturn = 0 (และค่าของ turn จะยังคงไม่เปลี่ยนแปลงตราบใดที่ p0 ยังไม่ดำเนินการต่อไป) ในที่สุด p0 จะหลุดออกจาก ลูป while turn ≠ 0 ภายใน (หากมันเคยติดอยู่ในนั้น) หลังจากนั้นมันจะตั้งค่าwants_to_enter[0]เป็น true และรอให้wants_to_enter[1]กลายเป็น false (เนื่องจากturn = 0มันจะไม่ทำการกระทำใดๆ ในลูป while) ครั้งต่อไปที่ p1 พยายามเข้าสู่ส่วนวิกฤต มันจะถูกบังคับให้ดำเนินการตามการกระทำในลูปwhile wants_to_enter[0]โดยเฉพาะอย่างยิ่ง ในที่สุดมันจะตั้งค่าwants_to_enter[1]เป็น false และติดอยู่ใน ลูป while turn ≠ 1 (เนื่องจาก turn ยังคงเป็น 0) ครั้งถัดไปที่การควบคุมผ่านไปยัง p0 มันจะออกจาก ลูป while wants_to_enter[1]และเข้าสู่ส่วนวิกฤต
หากอัลกอริทึมถูกแก้ไขโดยดำเนินการใน ลูป while wants_to_enter[1]โดยไม่ต้องตรวจสอบว่าturn = 0หรือไม่ ก็อาจเกิดภาวะอดอยากได้ ดังนั้นขั้นตอนทั้งหมดในอัลกอริทึมจึงจำเป็น
หมายเหตุ
ข้อดีอย่างหนึ่งของอัลกอริทึมนี้คือ ไม่จำเป็นต้องใช้ คำสั่ง ทดสอบและตั้งค่า พิเศษ (การอ่าน/แก้ไข/เขียนแบบอะตอมิก) ดังนั้นจึงสามารถใช้งานได้กับภาษาและสถาปัตยกรรมเครื่องคอมพิวเตอร์หลายประเภท ข้อเสียอย่างหนึ่งคือ จำกัดอยู่ที่สองกระบวนการ และใช้การรอแบบไม่หยุดนิ่ง (busy waiting) แทนการระงับกระบวนการ (process suspension) (การใช้การรอแบบไม่หยุดนิ่งบ่งชี้ว่ากระบวนการควรใช้เวลาภายในส่วนวิกฤตให้น้อยที่สุด)
ระบบปฏิบัติการสมัยใหม่มีกลไกการกีดกันร่วมกันที่ครอบคลุมและยืดหยุ่นกว่าอัลกอริทึมของเดกเกอร์ อย่างไรก็ตาม ในกรณีที่ไม่มีการแย่งชิงทรัพยากรกันอย่างแท้จริงระหว่างสองกระบวนการ การเข้าและออกจากส่วนวิกฤตจะมีประสิทธิภาพสูงมากเมื่อใช้อัลกอริทึมของเดกเกอร์
ซีพียูสมัยใหม่หลาย ตัว ประมวลผลคำสั่งแบบไม่เรียงลำดับ แม้แต่การเข้าถึงหน่วยความจำก็สามารถจัดลำดับใหม่ได้ (ดูการจัดลำดับหน่วยความจำ ) อัลกอริทึมนี้จะไม่ทำงานบน เครื่อง SMP ที่ติดตั้งซีพียูเหล่านี้ โดย ไม่ใช้ตัวกั้นหน่วยความจำ
นอกจากนี้ คอมไพเลอร์ที่ปรับแต่งประสิทธิภาพจำนวนมากสามารถทำการแปลงที่จะทำให้ขั้นตอนวิธีนี้ล้มเหลวได้ไม่ว่าจะเป็นแพลตฟอร์มใดก็ตาม ในหลายภาษา คอมไพเลอร์สามารถตรวจจับได้ว่าตัวแปรแฟล็กwants_to_enter[0]และwants_to_enter[1]ไม่เคยถูกเข้าถึงในลูป และสามารถลบการเขียนไปยังตัวแปรเหล่านั้นออกจากลูปได้ โดยใช้กระบวนการที่เรียกว่า การเคลื่อนย้ายโค้ดที่ไม่ขึ้นกับ ลูป (loop-invariant code motion ) นอกจากนี้ คอมไพเลอร์จำนวนมากยังสามารถตรวจจับได้ว่า ตัวแปร turnไม่เคยถูกแก้ไขโดยลูปภายใน และทำการแปลงที่คล้ายกัน ซึ่งอาจส่งผลให้เกิด ลูปอนันต์ได้ หากมีการแปลงอย่างใดอย่างหนึ่งเกิดขึ้น ขั้นตอนวิธีนี้จะล้มเหลวไม่ว่าจะเป็นสถาปัตยกรรมใดก็ตาม
เพื่อแก้ไขปัญหานี้ ตัวแปร volatileควรถูกทำเครื่องหมายว่าสามารถแก้ไขได้จากภายนอกขอบเขตของบริบทการทำงานปัจจุบัน ตัวอย่างเช่น ในภาษา C, C++, C# หรือ Java เราจะใส่คำอธิบายประกอบให้กับตัวแปรเหล่านี้ว่า 'volatile' อย่างไรก็ตาม โปรดทราบว่าแอตทริบิวต์ "volatile" ใน C/C++ รับประกันเพียงว่าคอมไพเลอร์จะสร้างโค้ดที่มีลำดับที่ถูกต้องเท่านั้น ไม่ได้รวมถึงตัวกั้นหน่วยความจำ ที่จำเป็น เพื่อรับประกันการทำงานของโค้ด ตามลำดับ ตัวแปรอะตอมิก ใน C++11สามารถใช้เพื่อรับประกันข้อกำหนดลำดับที่เหมาะสมได้ โดยค่าเริ่มต้น การดำเนินการกับตัวแปรอะตอมิกจะมีความสอดคล้องกันตามลำดับ ดังนั้นหากตัวแปร wants_to_enter และ turn เป็นอะตอมิก การใช้งานแบบง่ายๆ ก็จะ "ทำงานได้" หรืออีกทางหนึ่ง สามารถรับประกันลำดับได้โดยการใช้ fence แยกต่างหากอย่างชัดเจน โดยการดำเนินการ load และ store จะใช้ลำดับที่ผ่อนคลายกว่า