Deadlock เกิดเมื่อ Process 2 ตัวขึ้นไป ต้องการ Resource เพื่อทำงานเสร็จ แต่ Resource นั้นถูก Process อีกตัวครองอยู่
Process 1 มี Resource 1 ต้องการ Resource 2 Process 2 มี Resource 2 ต้องการ Resource 1 ทั้งคู่ต้องการ Resource ของอีกฝ่าย แต่อยู่ไม่ยอมปล่อย → Deadlock
Coffman Conditions (เงื่อนไขของ Coffman)
Deadlock จะเกิดก็ต่อเมื่อเงื่อนไข 4 ข้อนี้เป็นจริงพร้อมกัน (ไม่จำเป็นต้อง Mutually Exclusive):
1. Mutual Exclusion (การปิดกั้นร่วมกัน)
ต้องมี Resource ที่ถูกครองโดย Process เดียวในเวลาเดียวกัน ในแผนภาพ มี Resource R1 ตัวเดียว ถูก P1 ครอง
2. Hold and Wait (ถือและรอ)
Process สามารถถือ Resource หลายตัว และยังขอ Resource เพิ่มจาก Process อื่นที่ถืออยู่ P1 ถือ R1, R2 ขอ R3 ที่ P2 ถือ
3. No Preemption (ไม่มีการ 선점)
Resource ไม่สามารถถูก Preempt (ยึด) จาก Process โดยบังคับ Process ต้องปล่อย Resource เองโดยสมัครใจ P1 ไม่สามารถยึด R3 จาก P2 ได้ จะปล่อยต่อเมื่อ P2 จบการทำงาน
4. Circular Wait (การรอแบบวงกลม)
Process รอ Resource ที่ Process ถัดไปถืออยู่ จน Process สุดท้ายรอ Resource ของ Process แรก → วงกลม P1 ถือ R1 ขอ R2, P2 ถือ R2 ขอ R1 → Circular Wait
Deadlock Detection (การตรวจจับ Deadlock)
Resource Scheduler ตรวจจับได้ เพราะติดตาม Resource ทั้งหมดที่ Allocate ให้ Process ต่างๆ หลังตรวจพบ แก้ไขได้ 2 วิธี:
- Terminate ทุก Process ที่เกี่ยวข้อง (ไม่ดี เพราะ Progress ทั้งหมดหาย)
- Preempt Resource จากบาง Process ให้อีกฝ่าย จน Deadlock แก้
Deadlock Prevention (การป้องกัน Deadlock)
ป้องกันก่อนเกิด ระบบตรวจสอบ Transaction ทุกตัวก่อนรัน ถ้ามีโอกาสนำไปสู่ Deadlock ห้ามรัน
มี Prevention Schemes ใช้ Timestamp:
Wait-Die Scheme
ถ้า T1 ขอ Resource ที่ T2 ถือ:
- TS(T1) < TS(T2) (T1 เก่ากว่า) → T1 รอจน T2 เสร็จ
- TS(T1) > TS(T2) (T1 ใหม่กว่า) → T1 ถูก Kill รีสตาร์ททีหลังด้วย Timestamp เดิม
Wound-Wait Scheme
ถ้า T1 ขอ Resource ที่ T2 ถือ:
- TS(T1) < TS(T2) (T1 เก่ากว่า) → T1 Roll back T2 (Wound T2) T1 เอา Resource ทำงานต่อ T2 รีสตาร์ททีหลัง
- TS(T1) > TS(T2) (T1 ใหม่กว่า) → T1 รอจน T2 เสร็จ
Deadlock Avoidance (การหลีกเลี่ยง Deadlock)
หลีกเลี่ยงดีกว่าแก้ไขหลังเกิด Wait-for Graph ใช้ได้ แต่เหมาะกับฐานข้อมูลเล็ก ฐานใหญ่ซับซ้อนมาก
Wait-for Graph
แสดงความสัมพันธ์ Resource และ Transaction ถ้า Transaction ขอ Resource หรือถืออยู่ จะเห็นเป็น Edge ถ้า Graph มี Cycle → อาจมี Deadlock
Ignore Deadlock - Ostrich Algorithm
Ostrich Algorithm = มองข้าม Deadlock สมมติว่าไม่เกิดเลย เพราะในบางระบบ ค่าใช้จ่ายจัดการ Deadlock สูงกว่ามองข้าม มันเกิดนานๆ ครั้ง → ถ้าเกิดจริงแค่ Reboot ระบบ
