DeadLock
admin September 14th, 2008
Translate from DeadLock and Deadlock Prevention of Jakob Jenkov’s tutorial
Thanks a ton to Jakob for allowing me to translate his excellent tutorial
Deadlock คือการที่เธรด (thread) สองเธรดหรือมากกว่านั้นถูกบล็อคการทำงานไว้เพื่อรอเข้าถือจองล็อค (lock) ที่มีเธรดอื่นใน deadlock นั้นได้ทำการจองไว้เรียบร้อยแล้ว. Deadlock สามารถเกิดขึ้นได้เมื่อเธรดต้องการล็อดเดียวกันพร้อมๆกัน เพียงแต่ได้ทำการขอจองล็อคเหล่านั้นในลำดับที่ต่างกันไป
ตัวอย่างเช่น เธรด1 ทำการจองล็อค A ไว้แล้ว และกำลังพยายามจะขอจองล็อค B แต่ในขณะนั้นเองเธรด2 ที่ได้ทำการจองล็อค B ไว้ได้แล้วก็พยายามจะขอจองล๊อค A ที่เธรด1 ถืออยู่ เธรด1 จะไม่มีวันได้ล๊อค B ไปและเธรด2 ก็ไม่มีวันจะได้ล็อค A ไป นอกจากนั้นแล้วทั้งสองเธรดต่างก็ไม่มีทางจะรู้ได้เลยว่าตัวเองต่างก็ไม่มีวันจะได้ล็อคที่ต้องการมา สถานการณ์เช่นนี้เรียกว่าเกิด deadlock ขึ้น
สถานการณ์นี้อาจจะแสดงให้เห็นได้ดังนี้
Thread 1 locks A, waits for B
Thread 2 locks B, waits for A
ตัวอย่างโค้ดด้านล่างนี้คือคลาส TreeNode ที่ได้ทำการเรียกเมธอดที่ทำการ synchronized ในแต่ละอินสแตนต่างกันไป
public class TreeNode {
TreeNode parent = null;
List children = new ArrayList();
public synchronized void addChild(TreeNode child){
if(!this.children.contains(child)) {
this.children.add(child);
child.setParentOnly(this);
}
}
public synchronized void addChildOnly(TreeNode child){
if(!this.children.contains(child) ) {
this.children.add(child);
}
}
public synchronized void setParent(TreeNode parent){
this.parent = parent;
parent.addChildOnly(this);
}
public synchronized void setParentOnly(TreeNode parent){
this.parent = parent;
}
}
จากตัวอย่างด้านบน deadlock สามารถเกิดขึ้นได้ ถ้าเธรด(1) ทำการเรียก parent.addChild(child) พร้อมๆกับที่เธรด(2) ทำการเรียก child.setParent(parent) บนอินสแตนของ parent และ child ชุดเดียวกันนี้ ด้านล่างเป็นโค้ดจำลองเพื่อแสดงให้เห็นสถานการณ์นี้
Thread 1: parent.addChild(child); //locks parent
–> child.setParentOnly(parent);
Thread 2: child.setParent(parent); //locks child
–> parent.addChildOnly()
เธรด1 เรียกใช้งาน parent.addChild(child) ซึ่งจากการที่ addChild() นั้นเป็น synchronized ดังนั้นเธรด1 ได้ทำการจองล็อคตัว parent อ็อบเจกต์ไว้ทำให้เธรดอื่นไม่สามารถเข้าใช้งานตัว parent อ็อบเจกต์นี้ได้ (ดูเพิ่มเติมข้อ1) ในขณะเดียวกันนั้นเธรด2 ก็ทำการเรียกใช้ child.setParent(parent) ซึ่ง setParent() ก็เป็น synchronized ดังนั้นเธรด2 ก็ได้ทำการจองล็อคตัว child อ็อบเจกต์ไว้ทำให้เธรดอื่นไม่สามารถเข้าใช้งานตัว child อ็อบเจกต์นี้ได้ (ดูเพิ่มเติมข้อ1) จากนั้นเธรด1 ก็ได้พยายามจะเรียกใช้งาน child.setParentOnly() แต่ก็พบว่า child อ็อบเจกต์ได้ถูกล็อคไปแล้วโดยเธรด2 ดังนั้นเธรด1จะเข้าสู่สถานะบล็อค (เพื่อรอจนกว่าคนที่ล็อค child อ็อบเจกต์ไว้จะปล่อยล็อค เธรด1จึงจะสามารถเข้าทำงานเมธอดนี้ได้) ในลักษณะเดียวกันนั้น เธรด2 ก็ได้พยายามจะเรียก parent.addChildOnly() แล้วก็พบว่า parent อ็อบเจกต์นั้นได้ถูกล็อคไปแล้วโดยเธรด1 เป็นผลให้ เธรด2เข้าสู่สถานะบล็อคเช่นเดียวกัน ถึงตอนนี้ทั้งสองเธรดต่างก็อยู่ในสถานะบล็อคเพื่อรอขอล็อคที่อีกเธรดหนึ่งถืออยู่
สถานการณ์ดังกล่าวข้างบนนั้นจะเกิดขึ้นได้เมื่อเธรดหนึ่งเรียก parent.addChild(child) และ อีกเธรดหนึ่งจะเรียก child.setParent(parent) ในขณะเวลาเดียวกัน บนชุด parent และ child อ็อบเจกต์เดียวกัน โค้ดตัวอย่างนี้อาจจะประมวลผลได้ถูกต้องไปเป็นระยะเวลานานจนกระทั่งเกิด deadlock ขึ้นสักวันนึงในทันทีทันใด
โปรดสังเกตุว่าเพื่อที่ deadlock จะเกิดขึ้นได้นั้นทั้งสองเธรดจะต้องพยายามจะขอจองล็อค “ในขณะเวลาเดียวกัน” จริงๆ ถ้าหากว่าเธรด1 เร็วกว่าเธรด2 สักนิดนึงและได้ทำการจองได้ทั้งล็อค A และ B แล้วละก็ จะทำให้เธรด2 เข้าสู่สถานะบล็อคตั้งแต่ตอนที่พยายามจะขอล็อค B แล้ว ซึ่งก็จะไม่ทำให้เกิด deadlock ขึ้น และเนื่องจากการจัดตารางลำดับเวลาการประมวลผลของเธรดนั้นเป็นสิ่งที่คาดเดาไม่ได้ ดังนั้นเราจึงไม่สามารถทำนายได้ว่า deadlock “จะเกิดขึ้นเมื่อไร” เราบอกได้แต่เพียง “มันสามารถเกิดขึ้นได้”
Deadlock ที่ซับซ้อนขึ้น
Deadlock ยังสามารถเกิดขึ้นได้กับเธรดมากกว่าสองซึ่งทำให้เราตรวจหามันได้ยากขึ้น. ด้านล่างเป็นตัวอย่าง เธรด 4 ตัวเกิด deadlock กัน
Thread 1 locks A, waits for B
Thread 2 locks B, waits for C
Thread 3 locks C, waits for D
Thread 4 locks D, waits for A
การป้องกันไม่ให้เกิด deadlock (Deadlock Prevention)
ในบางสถานการณ์นั้นเราสามารถป้องกัน deadlock ไม่ให้เกิดขึ้นได้ ผมจะอธิบายเทคนิคสามข้อดังต่อไปนี้
1. การจัดลำดับการจองล็อค (Lock Ordering)
2. การจำกัดเวลาในการจองล็อค (Lock Timeout)
3. การตรวจหา deadlock (Deadlock Detection )
1. การจัดลำดับการจองล็อค
Deadlock เกิดขึ้นเมื่อเธรดมากกว่าหนึ่งต้องการจองล็อคตัวเดียวกันแต่ทำการเข้าจองในลำดับที่ต่างกัน ถ้าเราสามารถบังคับให้การจองล็อคทั้งหมดนั้นเป็นไปในลำดับเดียวกันในทุกๆเธรดแล้ว deadlock ก็จะไม่เกิด พิจารณาตัวอย่างต่อไปนี้
Thread 1:
lock A
lock B
Thread 2:
wait for A
lock C (when A locked)
Thread 3:
wait for A
wait for B
wait for C
เมื่อเธรดใดๆ ต้องการล็อคหลายตัวแล้ว เธรดนั้นจะต้องเข้าของล็อคนั้นๆในลำดับที่ถูกกำหนดไว้ก่อนแล้ว เธรดจะต้องไม่จองล็อคสลับลำดับที่ได้กำหนดไว้ ตัวอย่างเช่น ทั้งเธรด 2 และเธรด 3 ต่างก็ไม่สามารถจะเข้าขอจองล็อค C ได้ถ้าไม่ได้ถือครองล็อค A ไว้ได้ก่อนแล้ว และเมื่อเธรด 1 ถือครองล็อค A ไว้อยู่ ดังนั้นเธรด 2 และเธรด 3 ต้องรอให้เธรด 1 ปล่อยการถือครองล็อค A เสียก่อน จากนั้นจึงเข้าถือครองล็อค A ไว้ได้สำเร็จจึงจะสามารถขอเข้าจองล็อค B และ C ต่อไป การจัดลำดับการเข้าจองล็อคนั้นเป็นวิธีที่เรียบง่ายและได้ผลดีในการป้องกันการเกิด deadlock อย่างไรก็ตาม วิธีนี้จะใช้ได้ก็ต่อเมื่อคุณรู้การใช้งานล็อคทั้งหมดล่วงหน้าก่อนการเข้าจองล็อคใดๆ ซึ่งนั่นก็ไม่ใช่สิ่งที่จะสามารถรู้ล่วงหน้าได้ในทุกกรณี
2. การจำกัดเวลาในการจองล็อค
วิธีการป้องกัน deadlock อีกวิธีหนึ่งคือการกำหนดเวลาในการพยายามจองล็อค นั่นคือเธรดจะพยายามขอจองล็อคในระยะเวลาหนึ่งก่อนที่จะเลิกล้มความพยายาม ถ้าเธรดใดไม่สามารถเข้าถือครองล็อคที่ต้องการไว้ได้ทั้งหมดในระยะเวลาที่กำหนด เธรดนั้นจะถอยกลับโดยปล่อยการถือครองล็อคทั้งหมดที่ถือไว้ จากนั้นทำการรอเป็นระยะเวลาหนึ่งก่อนจะพยายามใหม่ ที่ทำการรอเป็นช่วงเวลาหนึ่งนั้นก็เพื่อจะเปิดโอกาสให้เธรดอื่นเข้าขอจองล็อค (ที่เธรดนั้นได้เคยถือครองไว้ก่อนจะถอยกลับ) และทำให้โปรแกรมสามารถทำงานต่อไปได้
ด้านล่างนี้เป็นตัวอย่างของเธรดสองตัวพยายามจะเข้าจองล็อคชุดเดียวกันในลำดับที่ต่างกัน ซึ่งจะเห็นการถอยกลับและพยายามเข้าจองล็อคใหม่อีกครั้งของเธรดทั้งสองตัว
Thread 1 locks A
Thread 2 locks B
Thread 1 attempts to lock B but is blocked
Thread 2 attempts to lock A but is blocked
Thread 1’s lock attempt on B times out
Thread 1 backs up and releases A as well
Thread 1 waits randomly (e.g. 257 millis) before retrying.
Thread 2’s lock attempt on A times out
Thread 2 backs up and releases B as well
Thread 2 waits randomly (e.g. 43 millis) before retrying
ในตัวอย่างนั้นเธรด 2 จะพยายามเข้าจองล็อคใหม่อีกครั้งก่อนเธรด 1 เป็นระยะเวลาประมาณ 200 มิลลิเซค ซึ่งมีความเป็นไปได้สูงที่เธรด 2 จะประสบความสำเร็จในการเข้าจองล็อคทั้งสองตัว จากนั้นเธรด 1 จึงจะพยายามเข้าจองล็อค A ใหม่อีกครั้ง และเมื่อเธรด 2 ทำการประมวลผลเสร็จแล้ว (และทำการปล่อยการถือครองล็อคที่ถืออยู่) เธรด 1 ก็จะมีโอกาสจะเข้าจองล็อคทั้งสองตัวบ้าง (นอกจากว่าเธรด 2 หรือเธรดอื่นๆเข้าทำการจองล็อคชุดนี้แทรกระหว่างนั้น) ข้อควรจำอย่างหนึ่งคือ การที่เธรดไม่สามารถจองล็อคได้สำเร็จ ในระยะเวลาที่กำหนดนั้นไม่ได้หมายความว่าเป็นเพราะมี deadlock เกิดขึ้นเสมอไป อาจจะเป็นได้ว่าเธรดที่ถือครองล็อค (จนทำให้เธรดอื่นหมดเวลาในการพยายามเข้าจองล็อค ) อยู่นั้น ใช้เวลานานในการทำงานจนสำเร็จ นอกจากนั้นแล้ว ถ้ามีเธรดจำนวนมากเข้าแย่งกันขอจองล็อคแล้ว มีโอกาสสูงที่เธรดจะเข้าแย่งกันจองล็อคพร้อมๆกันครั้งแล้วครั้งเล่า แม้ว่าจะเกิดกระบวนการถอยกลับแล้วพยายามใหม่แล้วก็ตาม เหตุการณ์เช่นนี้ อาจจะไม่เกิดกับเธรดแค่สองตัวที่ทำการรอเป็นเวลา 0 ถึง 500 มิลลิเซค ก่อนพยายามใหม่อีกครั้ง แต่ถ้าหากพูดถึงเธรด 10 – 20 ตัวละก็อีกเรื่องหนึ่ง มีโอกาสสูงที่สองเธรดจะรอเป็นเวลาเท่าๆกัน (หรือใกล้เคียงกันพอที่จะทำให้เกิดปัญหา) ก่อนจะเริ่มพยายามจองล็อคใหม่อีกครั้ง ปัญหาอย่างหนึ่งของการกำหนดเวลาในการจองขอจองล็อคก็คือ เราไม่สามารถจะจำกัดเวลาสำหรับ synchronized block (โค้ดส่วนที่ถูกครอบด้วย synchronized keyword) ได้ เราอาจจะต้องสร้างล็อคขึ้นเองหรือไม่ก็ใช้ล็อคของ Java 5 ใน java.util.concurrency
3. การตรวจหา deadlock
การตรวจหา deadlock นั้นจะถูกใช้ในกรณีที่การจัดลำดับการจองล็อคและการกำหนดเวลาในการพยายามจองล็อคนั้นไม่สามารถทำได้ โดยทุกครั้งที่เธรดได้ทำการถือครองล็อคไว้ เธรดนั้นจะถูกบันทึกไว้ในโครงสร้างข้อมูล (map , graph etc.) ของเธรดและล็อค นอกจากนั้นแล้วเมื่อไรก็ตามที่เธรดทำการขอเข้าจองล็อคตัวใด ข้อมูลการร้องงขอนี้ก็จะถูกบันทำไว้ด้วย เมื่อเธรดหนึ่งเธรดใดขอเข้าจองล็อคแล้วถูกปฏิเสธ เธรดนั้นสามารถตรวจสอบกราฟของล็อคเพื่อตรวจหา deadlock ได้ ตัวอย่างเช่น ถ้าเธรด A ขอจองล็อค 7 ที่ถูกถือครองไว้โดยเธรด B แล้ว เธรด A สามารถตรวจสอบได้ว่าเธรด B ได้ทำการขอจองล็อคใดๆที่เธรด A ได้ถือครองอยู่หรือไม่ ถ้าใช่ก็แสดงว่าเกิด deadlock ขึ้น (เธรด A ถือครองล็อค 1 ไว้อยู่และกำลังพยายามขอจองล็อค 7 ขณะเดียวกันเธรด B ได้ทำการถือครองล็อค 7 ไว้และกำลังพยายามจะขอจองล็อค 1) แน่นอนว่ารูปแบบการเกิด deadlock นั้นสามารถมีความซับซ้อน ได้มากกว่าการที่สองเธรดต่างถือครองล็อคที่อีกเธรดหนึ่งต้องการ เธรด Aอาจจะรอเธรด B, เธรด B รอเธรด C, เธรด C รอเธรด D และเธรด D รอเธรด A การที่เธรด A จะสามารถตรวจหา deadlock ได้นั้น เธรด A ต้องตรวจสอบล็อคทั้งหมดที่ที่เธรด B ต้องการทั้งหมดทั้งทางตรงและทางอ้อม จากล็อคที่เธรด B ร้องขอโดยตรงนั้น เธรด A จะต้องมองไปถึงเธรด C (เพราะ เธรด C ถือล็อคตัวหนึ่งที่เธรด B ต้องการอยู่ เธรด A จึงเหมือนกับรอเธรด C ไปด้วย) จากเธรด C มองต่อไปจนถึงเธรด D จึงจะพบว่ามีล็อคตัวหนึ่ง (ที่เธรด B ต้องการทั้งทางตรงและทางอ้อม) ที่ถูกถือครองไว้แล้วโดยเธรด A ถึงตอนนี้จึงสรุปได้ว่าเกิด deadlock ขึ้น ตัวอย่างด้านล่างคือกราฟของล็อคที่ถูกถือครองอยู่ (taken) และกำลังถูกร้องขอการเข้าจอง (requested) ของเธรดสี่ตัว A, B, C และ D โครงสร้างข้อมูลเช่นนี้สามารถนำมาใช้ตรวจหา deadlock ได้
ถามว่าจะทำอย่างไรถ้าเกิด deadlock ขึ้น?
ทางหนึ่งที่เป็นไปได้คือปล่อยการถือครองล็อคทั้งหมด ทำการถอยกลับรอเป็นระยะเวลาหนึ่งแล้วเริ่มพยายามใหม่อีกครั้ง ซึ่งเป็นวิธีเดียวที่ใช้กับการจำกัดเวลาการพยายามจองล็อคต่างกันที่ทำเฉพาะตอนที่เกิด deadlock ขึ้นจริงๆเท่านั้น อย่างไรก็ตาม ถ้าเธรดจำนวนมากทำการเแย่งขอจองล็อคตัวเดียวกันแล้ว ก็มีโอกาสที่เธรดจะเกิด deadlock ซ้ำๆกันบ่อยคร้งแท้ว่าจะทำการถอยกลับและรอพยายามใหม่แล้วก็ตาม
