มิวเท็กซ์แบบรีเอนแทรนต์

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

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

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

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

พิจารณาสถานการณ์ต่อไปนี้ในรูปแบบรหัสเทียม :

var m : Mutex // มิวเท็กซ์มาตรฐานที่ไม่สามารถเรียกซ้ำได้ โดยเริ่มต้นจะไม่ได้เรียกใช้งาน ฟังก์ชัน lock_and_call(i : จำนวนเต็ม) เอ็ม.ล็อก() เรียกกลับ(i) ม.ปลดล็อก() ฟังก์ชันเรียกกลับ (i : จำนวนเต็ม) ถ้า i > 0 lock_and_call(i - 1) lock_and_call(1) // เรียกใช้ฟังก์ชัน 

เมื่อ เรียกใช้ lock_and_call(1)ด้วย mutex มาตรฐาน จะส่งผลให้เกิดภาวะเดดล็อก:

1. การเรียกครั้งแรกไปยังlock_and_call(1)สำเร็จในการได้รับล็อกm
2. จากนั้นจึงเรียกcallback(1 )
3. ภายในcallback(1)เนื่องจากi > 0จึงเรียกlock_and_call(0 )
4. การเรียกlock_and_call ครั้งที่สองนี้ พยายามที่จะได้มาซึ่งล็อกmอีกครั้ง
5. ภาวะติดตาย (Deadlock) : เนื่องจากมิวเท็กซ์mถูกล็อกอยู่แล้ว เธรดจึงหยุดทำงานและรอจนกว่าการล็อกจะถูกปล่อย อย่างไรก็ตาม เธรดนั้นเองที่เป็นผู้ถือล็อกอยู่ ดังนั้นมันจึงรอให้ตัวเองทำสิ่งที่มันไม่สามารถทำได้สำเร็จ

การใช้ mutex แบบ reentrant สำหรับmจะช่วยป้องกันภาวะ deadlock นี้ได้ เมื่อการเรียกlock_and_call(0) ครั้งที่สอง พยายามล็อก mutex การดำเนินการจะสำเร็จเนื่องจากเธรดที่พยายามจะล็อกนั้นเป็นเจ้าของอยู่แล้ว จำนวนนับภายในของ mutex จะเพิ่มขึ้น การล็อกจะถูกปล่อยอย่างสมบูรณ์ก็ต่อเมื่อการเรียกlock_and_call ทั้งสองครั้ง เสร็จสมบูรณ์และดำเนินการ m.unlock() ที่เกี่ยวข้องแล้วเท่านั้น

W. Richard Stevensตั้งข้อสังเกตว่าล็อกแบบเรียกซ้ำนั้น "ยุ่งยาก" ในการใช้งานอย่างถูกต้อง และแนะนำให้ใช้ล็อกแบบเรียกซ้ำเพื่อปรับโค้ดแบบเธรดเดียวโดยไม่ต้องเปลี่ยนAPIแต่ "เฉพาะเมื่อไม่มีวิธีแก้ปัญหาอื่นที่เป็นไปได้" ^{[ 3 ]}

กลไกการซิงโครไนซ์ดั้งเดิมของภาษา Java ที่เรียกว่าmonitor ใช้การล็อกแบบเรียกซ้ำ ในทางไวยากรณ์ การล็อกคือบล็อกของโค้ดที่มีคำหลัก 'synchronized' นำหน้า และ มีการอ้างอิงถึง Object ใดๆ ในวงเล็บที่จะใช้เป็น mutex ภายในบล็อก synchronized วัตถุที่กำหนดสามารถใช้เป็นตัวแปรเงื่อนไขได้โดยการเรียกใช้ wait(), notify() หรือ notifyAll() ดังนั้น Object ทั้งหมดจึงเป็นทั้ง mutex แบบเรียกซ้ำและตัวแปรเงื่อนไข^{[ 4 ]}

1. เธรด A เรียกฟังก์ชัน F ซึ่งจะได้รับล็อกแบบเรียกซ้ำได้สำหรับตัวเองก่อนที่จะดำเนินการต่อไป
2. เธรด B เรียกฟังก์ชัน F ซึ่งพยายามขอรับล็อกแบบ reentrant สำหรับตัวเอง แต่ไม่สามารถทำได้เนื่องจากมีล็อกที่ใช้งานอยู่แล้ว ส่งผลให้เกิดการบล็อก (รอ) หรือหมดเวลาหากมีการร้องขอ
3. ฟังก์ชัน F ของเธรด A เรียกตัวเองซ้ำๆ มันเป็นเจ้าของล็อกอยู่แล้ว ดังนั้นมันจะไม่บล็อกตัวเอง (ไม่มีภาวะติดตาย) นี่คือแนวคิดหลักของมิวเท็กซ์แบบเรียกซ้ำ และเป็นสิ่งที่ทำให้มันแตกต่างจากล็อกทั่วไป
4. F ของเธรด B ยังคงรออยู่ หรืออาจพบปัญหาหมดเวลาและแก้ไขปัญหาได้แล้ว
5. เกลียว A's F สิ้นสุดการทำงานและปลดล็อก
6. ตอนนี้ F ของเธรด B สามารถเข้าถึงล็อกแบบ reentrant และดำเนินการต่อได้หากยังคงรออยู่

การจำลองซอฟต์แวร์สามารถทำได้โดยใช้โครงสร้างดังต่อไปนี้:

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

1. ตรวจสอบเงื่อนไขการควบคุม
2. หากกำหนดเจ้าของแล้วและไม่ใช่เธรดปัจจุบัน ให้รอการแจ้งเตือนเงื่อนไขการควบคุม (ซึ่งจะปล่อยเงื่อนไขนั้นด้วย)
3. ตั้งค่าเจ้าของเป็นเธรดปัจจุบัน ตัวระบุเจ้าของควรถูกล้างไปแล้วในขั้นตอนนี้ เว้นแต่ว่าผู้ซื้อจะเป็นเจ้าของอยู่แล้ว
4. เพิ่มจำนวนการได้มา (ควรเป็น 1 เสมอสำหรับเจ้าของใหม่)
5. ยกเลิกเงื่อนไขการควบคุม

1. ได้รับเงื่อนไขการควบคุม โดยยืนยันว่าเจ้าของเป็นผู้ปล่อยสิทธิ์
2. ลดจำนวนการได้มาซึ่งข้อมูลลง โดยกำหนดเงื่อนไขว่าจำนวนนั้นต้องมากกว่าหรือเท่ากับศูนย์
3. หากจำนวนการได้มาซึ่งข้อมูลเป็นศูนย์ ให้ล้างข้อมูลเจ้าของและแจ้งเงื่อนไขการควบคุม
4. ยกเลิกเงื่อนไขการควบคุม