บทที่ 1 · Deadlock ออกแน่

ชีท process_deadlock(2_4) (หัวข้อ 2.4) — อาจารย์เปิดเป็นไฟล์แรกในคลิปนาที 0:28–6:10 และบอกว่า "บท deadlock รอบนี้จะไปจบที่ Banker's"

⚠️ ยังไม่มีไฟล์ชีทนี้ในเครื่องภาพในหน้านี้จับจากคลิป เพราะอาจารย์เลื่อนผ่านเร็ว บางภาพจึงมีกรอบ Zoom บังอยู่ (ทั้งไฟล์มี 18 หน้า เห็นในคลิป 16 หน้า) ถ้าหาไฟล์จาก Classroom ได้ ให้อ่านประกอบด้วย

1.1 Deadlock คืออะไร

🎯 เรียนจบหัวข้อนี้ต้องอธิบายได้ว่า deadlock คืออะไร ยกตัวอย่างได้ และบอกขั้นตอนการใช้ทรัพยากรได้

🤔 คืออะไร

Deadlock = สถานการณ์ที่กลุ่ม process ต่างถือทรัพยากรไว้ แล้วรอทรัพยากรที่ process อื่นในกลุ่มถืออยู่ ทุกตัวจึงรอกันไปเรื่อยๆ และไม่มีใครทำงานต่อได้เลย (ไม่ใช่แค่ช้า แต่ค้างถาวรถ้าไม่มีใครเข้าไปแก้)

💡 เทียบให้เห็นภาพ: รถติดที่สี่แยก (รูป 2.4.A ในชีท)

รถ 4 คันเข้าสี่แยกพร้อมกัน แต่ละคันจอดขวางช่องที่อีกคันต้องใช้ และทุกคันรอให้คันข้างหน้าไปก่อน ทุกคันจึงรอกันเป็นวง ไม่มีใครไปได้ ในระบบปฏิบัติการ รถ = process และช่องถนน = resource

🤔 Resource และ instance คืออะไร

Resource (ทรัพยากร) = สิ่งที่ process ต้องใช้ทำงาน ในชีทยกตัวอย่างว่า memory space, CPU cycles, files, I/O devices (เครื่องพิมพ์ ฯลฯ)
Resource type = ชนิดของทรัพยากร และ instance = จำนวนชิ้นของชนิดนั้น เช่น มีเครื่องพิมพ์ 3 เครื่อง = resource type "printer" มี 3 instances (ใช้เครื่องไหนก็ได้เหมือนกัน)

⚙️ process ใช้ทรัพยากรยังไง (3 ขั้น)

1. Request ขอ (ถ้ายังไม่ว่างต้องรอ)→2. Use ใช้งาน→3. Release ปล่อยคืน

การขอและการคืนทำผ่าน system call (คำสั่งที่โปรแกรมเรียกให้ OS ทำงานให้) เช่น open/close file, allocate/free memory
Deadlock เกิดตรงขั้นที่ 1 คือ ขอแล้วต้องรอ แต่สิ่งที่รอดันถูกถือไว้โดยคนที่รอเราอยู่เหมือนกัน

เกทไหม? ลองตอบ

ห้องแล็บมีเครื่องพิมพ์รุ่นเดียวกัน 3 เครื่อง (ใช้เครื่องไหนก็ได้) เขียนในรูป resource ได้อย่างไร

ของชนิดเดียวกันที่ใช้แทนกันได้ = resource type เดียว ส่วนจำนวนเครื่อง = instance

deadlock เกิดขึ้นที่ขั้นไหนของการใช้ทรัพยากร

process ขอทรัพยากรที่คนอื่นถืออยู่จึงต้องรอ ถ้าทุกคนรอกันเป็นวง ก็ค้างที่ขั้น request

1.2 เงื่อนไขที่จำเป็น 4 ข้อ ★

🎯 ต้องทำได้เขียนชื่อเงื่อนไขทั้ง 4 ข้อ อธิบายแต่ละข้อ และอธิบาย necessary ≠ sufficient ได้

เงื่อนไข	ความหมาย	เทียบกับรถติด
1. Mutual exclusion	ทรัพยากรใช้ได้ทีละโปรเซส แชร์ไม่ได้	ช่องถนนช่องหนึ่งรถจอดได้คันเดียว
2. Hold and wait	ถือทรัพยากรไว้แล้ว และรอทรัพยากรอื่นเพิ่ม	จอดขวางอยู่ แต่ยังรอช่องข้างหน้า
3. No preemption	ยึดทรัพยากรคืนจากโปรเซสไม่ได้ ต้องรอให้ปล่อยเอง	ยกรถคันอื่นออกไปไม่ได้
4. Circular wait	รอกันเป็นวง: P₀ รอ P₁, P₁ รอ P₂, …, P_n รอ P₀	4 คันรอกันเป็นวงรอบสี่แยก

⚙️ ทำไมแต่ละข้อ "จำเป็น" — ลองคิดว่าถ้าไม่มีข้อนั้นจะเป็นยังไง

ถ้าไม่มี…	จะเกิดอะไรขึ้น	จึงไม่ deadlock เพราะ
Mutual exclusion	ทรัพยากรแชร์กันใช้พร้อมกันได้ (เช่น ไฟล์ที่อ่านอย่างเดียว)	ไม่มีใครต้องรอใคร
Hold and wait	ใครที่ต้องรอ จะไม่ถือของไว้ระหว่างรอ	คนที่รอไม่ได้ขวางใคร ของที่ปล่อยออกมาทำให้คนอื่นไปต่อได้
No preemption	OS ยึดของจากคนที่ค้างอยู่ไปให้คนอื่นได้	วงที่รอกันจะถูกตัดขาดตรงที่ถูกยึด
Circular wait	การรอเป็นเส้นตรง ไม่วนกลับมา (เช่น P1 รอ P2 แต่ P2 ไม่ได้รอใคร)	ตัวสุดท้ายของสายทำงานจบได้ แล้วปล่อยของให้ตัวก่อนหน้าไล่ต่อกันไป

สรุป: deadlock ต้องมีครบทั้ง 4 ข้อพร้อมกัน ขาดข้อไหนข้อหนึ่งก็เกิดไม่ได้

💡 Necessary vs sufficient — เทียบกับ "ไฟติด" ไฟจะติดได้ต้องมี เชื้อเพลิง + ออกซิเจน + ความร้อน ครบ 3 อย่าง
• ถ้าขาดอย่างใดอย่างหนึ่ง → ไม่ติดแน่นอน (นี่คือความหมายของ necessary)
• แต่ถ้ามีครบ ก็ไม่ได้แปลว่าต้องติดเสมอ (จึงไม่ใช่ sufficient)
Deadlock ก็เหมือนกัน: ขาดข้อใดข้อหนึ่ง = ไม่เกิดแน่ แต่ครบ 4 ข้อ = อาจเกิด → วิธีป้องกันจึงคือ "ทำลายเงื่อนไขสักข้อ"

🗣 อาจารย์พูด Deadlock จะเกิดขึ้นได้ต้องอาศัยเงื่อนไขอะไร จำได้ไหม … เงื่อนไขจำเป็น necessary condition ต่างกับเงื่อนไขพอเพียง sufficient condition … เงื่อนไขครบแล้วอาจจะเกิดหรือไม่เกิดก็ได้ แต่ถ้าเงื่อนไขไม่ครบก็คือไม่เกิดแน่ๆ ฉะนั้นการที่เราจะไม่ให้เกิด deadlock เราก็ทำลายเงื่อนไขใดเงื่อนไขหนึ่ง

📝 เขียนตอบแบบนี้ (closed book)

Deadlock เกิดได้เมื่อมีเงื่อนไขจำเป็นครบ 4 ข้อ คือ
1) Mutual exclusion  ทรัพยากรใช้ได้ทีละโปรเซส
2) Hold and wait     ถือทรัพยากรอยู่และรอทรัพยากรอื่น
3) No preemption     ยึดทรัพยากรคืนไม่ได้
4) Circular wait     P0 รอ P1, P1 รอ P2, ..., Pn รอ P0
เป็น necessary ไม่ใช่ sufficient: ครบอาจเกิดหรือไม่เกิดก็ได้
แต่ถ้าขาดข้อใดข้อหนึ่งไม่เกิดแน่นอน จึงป้องกันได้โดยทำลายเงื่อนไขใดเงื่อนไขหนึ่ง

Q1ข้อใดถูกต้อง

เงื่อนไขทั้ง 4 เป็น necessary คือขาดข้อไหนก็ไม่เกิด แต่ครบแล้วไม่จำเป็นต้องเกิด ส่วน cycle จะเท่ากับ deadlock แน่นอนก็ต่อเมื่อทุกทรัพยากรมี instance เดียว

Q2"P1 ถือเครื่องพิมพ์อยู่ และรอสแกนเนอร์ที่ P2 ถือ" ตรงกับเงื่อนไขใดชัดที่สุด

ถือ (hold) ของที่มีอยู่ แล้วรอ (wait) ของเพิ่ม = hold and wait แต่ถ้า P2 ก็รอเครื่องพิมพ์จาก P1 ด้วย จะกลายเป็น circular wait

1.3 Resource-Allocation Graph (RAG) ★

🎯 ต้องทำได้อ่านและวาด RAG ได้ แปลงกราฟเป็น allocation matrix / request matrix แล้วบอกได้ว่ามี cycle หรือ deadlock ไหม

🤔 RAG คืออะไร

Resource-Allocation Graph (RAG) = แผนภาพที่บอกว่า "ตอนนี้ใครถืออะไรอยู่ และใครกำลังรออะไร" ใช้ดูว่าระบบมีการรอกันเป็นวง (circular wait) หรือไม่

⚙️ สัญลักษณ์

○ วงกลม = process (P1, P2, …)
▭ สี่เหลี่ยม = resource type (R1, R2, …) และจุดข้างในกล่อง = จำนวน instance
P → R (ลูกศรออกจาก process ไปที่กล่อง) = process ขอ/รอ resource นั้น (request edge)
R → P (ลูกศรออกจากจุดในกล่องไปที่ process) = process ได้/ถือ instance นั้นอยู่ (assignment edge)

⚙️ วาด RAG จากโจทย์ (ทำตามนี้)

วาดวงกลมให้ทุก process และวาดกล่องให้ทุก resource ใส่จุดตามจำนวน instance
อ่านว่า "ใครถืออะไร" แล้ววาดลูกศร จากกล่อง → process
อ่านว่า "ใครรออะไร" แล้ววาดลูกศร จาก process → กล่อง

⚙️ หา cycle ยังไง

เริ่มที่ process ตัวหนึ่งแล้วเดินตามหัวลูกศรไปเรื่อยๆ (P → R → P → R …) ถ้าวนกลับมาที่จุดเริ่มได้ แปลว่ามี cycle เช่น P1 → R1 → P2 → R3 → P3 → R2 → P1

🤔 Allocation matrix / request matrix คืออะไร

คือข้อมูลชุดเดียวกับกราฟ แต่เขียนเป็นตาราง (แถว = process, คอลัมน์ = resource)
• Allocation[P_i][R_j] = จำนวน R_j ที่ P_i ถือ (นับลูกศร R_j → P_i)
• Request[P_i][R_j] = จำนวน R_j ที่ P_i ขอ (นับลูกศร P_i → R_j)
• Available = จำนวน instance ทั้งหมด − ผลรวม Allocation ของคอลัมน์นั้น

🗣 อาจารย์พูด Circular wait เป็นการรอคอยเป็นวงกลม เราต้องสามารถวาด resource allocation graph ให้มีการรอคอยทรัพยากรเป็นวงกลม … ถ้า process ชี้ไปยัง resource คือ request ที่จะใช้ ถ้า resource ชี้ไปยัง process คือ process ได้ resource นั้นไปแล้ว … allocation matrix และ request matrix เป็นความสัมพันธ์ระหว่าง P_i กับ R_j ตามที่เราทำ lab ไป ก็ไปทวน concept อันนี้ ก็จะออกอยู่

อ่านกราฟให้เป็น

วงกลม = โปรเซส P_i ส่วนสี่เหลี่ยม = ทรัพยากร R_j และจุดในสี่เหลี่ยม = จำนวน instance
P_i → R_j = P_i ขอ (request) R_j → ใส่ใน Request matrix
R_j → P_i = P_i ถือ (hold / allocation) R_j อยู่ → ใส่ใน Allocation matrix

ตัวอย่างในชีท (รูป 2.4.B) ทำทีละขั้น

ชีทให้ P = {P1, P2, P3}, R = {R1, R2, R3, R4} และ E = {P1→R1, P2→R3, R1→P2, R2→P2, R2→P1, R3→P3} โดยมี instance R1 = 1, R2 = 2, R3 = 1, R4 = 3

ขั้น 1: เส้น R → P ใส่ Allocation

      R1 R2 R3 R4
P1     0  1  0  0   (R2→P1)
P2     1  1  0  0   (R1→P2, R2→P2)
P3     0  0  1  0   (R3→P3)

ขั้น 2: เส้น P → R ใส่ Request

      R1 R2 R3 R4
P1     1  0  0  0   (P1→R1)
P2     0  0  1  0   (P2→R3)
P3     0  0  0  0

ขั้น 3: Available = instance − ผลรวม Allocation = (1−1, 2−2, 1−1, 3−0) = (0, 0, 0, 3)

ขั้น 4: ตรวจ P3 ไม่ได้ขออะไร → ทำงานจบแล้วคืน R3 → P2 ได้ R3 แล้วจบ คืน R1 กับ R2 → P1 ได้ R1 แล้วจบ → ไม่เกิด deadlock (และกราฟนี้ไม่มี cycle)

ตรงกับ "Process State" ในชีท: P1 ใช้ R2 รอ R1 / P2 ใช้ R1, R2 รอ R3 / P3 ใช้ R3

⚠️ จำกฎ cycle ให้แม่น • ไม่มี cycle → ไม่เกิด deadlock แน่นอน
• มี cycle + ทุกทรัพยากรมี 1 instance → deadlock แน่นอน
• มี cycle + ทรัพยากรมีหลาย instance → อาจเกิดหรือไม่เกิดก็ได้ ต้องไล่ดู
รูป 2.4.C เพิ่มเส้น P3→R2 จึงเกิด 2 cycles และติด deadlock ส่วนรูป 2.4.D มี cycle P1→R1→P3→R2→P1 แต่ P2 กับ P4 ไม่ได้รออะไร เมื่อคืนทรัพยากรแล้ว cycle ก็คลายเอง

ลองเลือก "รูป 2.4.C" แล้วดูว่ามี cycle อะไรบ้าง จากนั้นลองแก้ Request ของ P3 ที่ R2 จาก 1 เป็น 0 แล้วดูว่า deadlock หายไหม

Q3ใน RAG ลูกศร R2 → P1 หมายความว่าอะไร

R → P = allocation (ได้ไปแล้ว) ส่วน P → R = request

Q4รูป 2.4.C มี cycle อะไรบ้าง และเกิด deadlock หรือไม่ เพราะอะไร

มี 2 cycles คือ P1→R1→P2→R3→P3→R2→P1 และ P2→R3→P3→R2→P2 และเกิด deadlock (P1, P2, P3) เพราะ Available = (0,0,0,3) ไม่มีโปรเซสไหนได้ตามที่ขอ: P1 รอ R1 (P2 ถือ), P2 รอ R3 (P3 ถือ), P3 รอ R2 (P1 กับ P2 ถือหมด) ทุกตัวรอกันเป็นวง

Q5รูป 2.4.D มี cycle แต่ทำไมไม่เกิด deadlock

เพราะ R1 กับ R2 มีอย่างละ 2 instances และมีโปรเซสนอก cycle คือ P2 (ถือ R1) กับ P4 (ถือ R2) ที่ไม่ได้รออะไร เมื่อ P4 ทำงานจบแล้วคืน R2 → P3 ได้ R2 / เมื่อ P2 จบแล้วคืน R1 → P1 ได้ R1 → ทุกตัวจบได้ cycle จึงเป็นแค่เงื่อนไขจำเป็น ไม่ใช่เงื่อนไขพอเพียง เมื่อทรัพยากรมีหลาย instance

1.4 การบ้าน: Deadlock ในชีวิตประจำวัน ★

🎯 ต้องทำได้ยกตัวอย่าง deadlock จากชีวิตจริงได้เอง แปลงเป็น process / resource วาด RAG และเช็คเงื่อนไขทั้ง 4 ข้อโดยโยงกับเรื่องที่ยกมา ซึ่งเป็นโจทย์ที่อาจารย์ให้ทำเป็นการบ้าน จึงมีโอกาสออกสอบในรูปแบบนี้

📋 โจทย์ (Classroom, 24 ก.ค.)"ยกตัวอย่าง deadlock ในชีวิตประจำวัน และเขียน resource allocation graph พร้อมทั้งเช็ค 4 เงื่อนไข 1. mutual exclusion 2. hold and wait 3. no preemption 4. circular wait"

สูตร 5 ขั้น ใช้ตอบโจทย์แบบนี้ได้ทุกเรื่อง

เล่าสถานการณ์ และกำหนดตัวแปร: ใคร = process (P1, P2, …), ของที่แย่งกัน = resource (R1, R2, …) และของแต่ละอย่างมีกี่ชิ้น = instance
Process state (คำเดียวกับในชีท): แต่ละ process ใช้ (hold) อะไรอยู่ และรอ (wait) อะไร
วาด RAG โดยใส่ชื่อกำกับทุกวงกลมและทุกกล่อง ลูกศร R → P = ถืออยู่, P → R = รอ/ขอ
หา cycle แล้วเขียนเป็นสาย (เช่น P1 → R2 → P2 → …) และถ้ามีเวลา ให้เขียน allocation matrix / request matrix ด้วย (อาจารย์บอกว่าเรื่องนี้ออก)
เช็ค 4 เงื่อนไขทีละข้อ โดยโยงกับเรื่องที่ยกมา แล้วสรุปว่าเกิด deadlock เพราะครบ 4 ข้อ และถ้าทุก resource มี 1 instance + มี cycle แปลว่า deadlock แน่นอน (bonus: บอกวิธีแก้)

ตรวจงานที่ส่งไป

✅ ถูกต้องแล้ว • สถานการณ์ดี: ห้องแล็บมีนักศึกษา 3 คน (P1–P3) กับ Printer (R1), Projector (R2), Notebook (R3) อย่างละ 1 instance
• process state ถูก: P1 ใช้ R1 รอ R2 / P2 ใช้ R2 รอ R3 / P3 ใช้ R3 รอ R1
• cycle ถูก: P1 → R2 → P2 → R3 → P3 → R1 → P1
• เช็ค 4 เงื่อนไขครบ และเหตุผลแต่ละข้อถูก

✏️ เขียนให้ได้คะแนนเต็มกว่านี้ • ในรูป RAG กล่องยังไม่มีชื่อ ให้เขียน R1/R2/R3 กำกับกล่อง และให้หัวลูกศรชัดว่าเส้นไหนคือ "ถือ" (R→P) เส้นไหนคือ "รอ" (P→R)
• หัวข้อ "Process Type" ในชีทใช้คำว่า "Process State"
• ข้อ circular wait ที่เขียนว่า "เกิดการรอเป็นวง" สั้นไป ให้เขียนเป็นสาย: P1 รอ P2 (ถือ R2) → P2 รอ P3 (ถือ R3) → P3 รอ P1 (ถือ R1)
• ปิดท้ายด้วยข้อสรุป และถ้ามีเวลา ให้ใส่ allocation/request matrix กับวิธีแก้

คำตอบตัวอย่างแบบเต็ม (ใช้สถานการณ์เดิม)

📝 เขียนตอบแบบนี้

สถานการณ์: ห้องแล็บมีนักศึกษา 3 คน ต้องใช้อุปกรณ์ร่วมกัน อุปกรณ์ละ 1 เครื่อง
  P1, P2, P3 = นักศึกษาคนที่ 1, 2, 3
  R1 = Printer, R2 = Projector, R3 = Notebook   (อย่างละ 1 instance)

Process state
  P1  ใช้ R1 (Printer)    รอ R2 (Projector)
  P2  ใช้ R2 (Projector)  รอ R3 (Notebook)
  P3  ใช้ R3 (Notebook)   รอ R1 (Printer)

Allocation (R→P)        Request (P→R)
      R1 R2 R3                R1 R2 R3
  P1   1  0  0            P1   0  1  0
  P2   0  1  0            P2   0  0  1
  P3   0  0  1            P3   1  0  0
  Available = (0, 0, 0)

Cycle: P1 → R2 → P2 → R3 → P3 → R1 → P1

เช็ค 4 เงื่อนไข
1) Mutual exclusion ✓  อุปกรณ์แต่ละเครื่องใช้ได้ทีละคน (1 instance)
2) Hold and wait    ✓  ทุกคนถืออุปกรณ์ 1 เครื่อง และรอเครื่องที่คนอื่นถือ
3) No preemption    ✓  แย่งอุปกรณ์จากคนที่กำลังใช้ไม่ได้ ต้องรอให้เขาปล่อยเอง
4) Circular wait    ✓  P1 รอ P2 (ถือ R2), P2 รอ P3 (ถือ R3), P3 รอ P1 (ถือ R1)
สรุป: ครบทั้ง 4 ข้อ และทุก resource มี 1 instance + มี cycle → เกิด deadlock แน่นอน
วิธีแก้ (ทำลาย 1 ข้อ): เช่น ให้ทุกคนจองอุปกรณ์ตามลำดับเลข R1→R2→R3 เสมอ
  (ทำลาย circular wait) หรือให้ขอครบทุกเครื่องก่อนค่อยเริ่มใช้ (ทำลาย hold and wait)

ลองดูกราฟของตัวอย่างนี้ในเครื่องมือ แล้วเลือก "ห้องแล็บ แต่มี Projector 2 เครื่อง" ดูว่าทำไม deadlock ถึงหายไป

ตัวอย่างอื่นที่ใช้ตอบได้ (เผื่อข้อสอบให้ยกตัวอย่างเอง)

สถานการณ์	Process	Resource	รอกันแบบไหน
กินข้าว ช้อนกับส้อม	คน A, คน B	ช้อน 1 คัน, ส้อม 1 คัน	A ถือช้อนรอส้อม, B ถือส้อมรอช้อน
สี่แยกรถติด (รูป 2.4.A ในชีท)	รถ 4 คัน	พื้นที่สี่แยก 4 ช่อง	รถแต่ละคันจอดในช่องหนึ่ง และรอช่องข้างหน้าที่คันอื่นจอดอยู่
สะพานแคบรถสวนกัน	รถ 2 คัน	สะพาน 2 ครึ่ง (ฝั่งซ้าย/ขวา)	แต่ละคันขึ้นมาครึ่งหนึ่งแล้วรออีกครึ่งที่อีกคันอยู่
โอนเงินข้ามบัญชี	ธุรกรรม T1, T2	บัญชี X, บัญชี Y (lock)	T1 ล็อก X รอ Y, T2 ล็อก Y รอ X

⚠️ ระวังตัวอย่างที่ "ไม่ใช่" deadlock • คิวรอซื้อข้าว: รอนานก็จริง แต่คนข้างหน้าซื้อเสร็จก็ไปไม่มีการรอเป็นวง จึงขาด circular wait
• ของมีหลายชิ้น: ถ้าห้องแล็บมี Projector 2 เครื่อง แม้จะมี cycle ใน RAG แต่ P1 ได้เครื่องที่ว่าง แล้วทำงานจบได้ จึงไม่ deadlock (เหมือนรูป 2.4.D)

Qกินข้าว: A ถือช้อนรอส้อม และ B ถือส้อมรอช้อน ถ้ากำหนดกติกาว่า "ทุกคนต้องหยิบช้อนก่อนส้อมเสมอ" จะทำลายเงื่อนไขใด

กำหนดลำดับการขอทรัพยากร (order no.) ทำให้รอกันเป็นวงไม่ได้ จึงทำลาย circular wait เพราะคนที่ได้ช้อนแล้วเท่านั้นถึงจะขอส้อมได้

Qถ้ากำหนดว่า "ถ้าหยิบส้อมไม่ได้ ต้องวางช้อนคืนก่อนแล้วค่อยรอ" จะทำลายเงื่อนไขใด

ตรงกับชีท "if wait → not hold" คือรอได้แต่ห้ามถือของไว้ จึงทำลาย hold and wait

Qถ้าให้พนักงานร้าน "ยึดช้อนจาก A ไปให้ B ได้" จะทำลายเงื่อนไขใด

ยึดทรัพยากรคืนจากคนที่ถืออยู่ได้ = allow preemption จึงทำลาย no preemption

Qลองยกตัวอย่าง deadlock ในชีวิตประจำวันเรื่องใหม่ของตัวเอง แล้วทำตามสูตร 5 ขั้น (เขียนลงกระดาษก่อนค่อยดูเฉลย)

ตัวอย่าง: สะพานแคบ P1 = รถฝั่งซ้าย, P2 = รถฝั่งขวา, R1 = สะพานครึ่งซ้าย, R2 = สะพานครึ่งขวา (อย่างละ 1)
Process state: P1 ใช้ R1 รอ R2 / P2 ใช้ R2 รอ R1 → cycle P1 → R2 → P2 → R1 → P1
ME ✓ (ครึ่งสะพานรถอยู่ได้ทีละคัน) · Hold & wait ✓ (อยู่บนครึ่งหนึ่งแล้วรออีกครึ่ง) · No preemption ✓ (ยกรถออกไม่ได้ ต้องถอยเอง) · Circular wait ✓ (P1 รอ P2, P2 รอ P1)
สรุป: ครบ 4 ข้อ + 1 instance + มี cycle → deadlock แน่นอน วิธีแก้คือติดไฟจราจรให้ขึ้นได้ทีละฝั่ง (ขอทั้งสะพานในครั้งเดียว = ทำลาย hold and wait)
ตรวจงานตัวเองโดยดูว่า (1) มีการรอเป็นวงจริงไหม (2) ทุกข้อโยงกับเรื่องที่ยกมาไหม (3) RAG ใส่ชื่อและทิศลูกศรถูกไหม

1.5 วิธีจัดการ deadlock: prevention และ avoidance ★

🤔 OS รับมือ deadlock ได้ 3 แนวทาง (ตามชีท)

แนวทาง	ความคิด	เทียบกับสี่แยก
Prevention (ป้องกัน)	ออกกฎให้เงื่อนไขข้อใดข้อหนึ่งเกิดไม่ได้เลย	ออกกฎจราจร เช่น ห้ามเลี้ยวขวา (ไม่มีทางวนเป็นวง)
Avoidance (หลีกเลี่ยง)	ก่อนให้ทรัพยากร คำนวณก่อนว่าให้แล้วยังปลอดภัย (safe) ไหม ถ้าไม่ปลอดภัยให้รอ	ตำรวจดูก่อนว่าให้รถคันนี้เข้าแยกแล้วจะติดไหม ถ้าติดก็ให้รอ
Detection (ตรวจจับ)	ปล่อยให้เกิด แล้วตรวจหาว่ามีใครติดอยู่ จากนั้นค่อยแก้	รถติดแล้วค่อยให้ตำรวจมาจัดการ

Prevention ปลอดภัยแต่ทำให้ใช้ทรัพยากรได้ไม่คุ้ม, avoidance ต้องรู้ล่วงหน้าว่าแต่ละ process ต้องการสูงสุดเท่าไร (Max), ส่วน detection ต้องมีวิธีแก้หลังเกิดแล้ว (เช่น ยกเลิก process หรือยึดทรัพยากรคืน)

Deadlock prevention = ทำลายเงื่อนไขข้อใดข้อหนึ่ง

เงื่อนไข	วิธีทำลาย (ตามชีท)	หมายเหตุ
Mutual exclusion	ทำให้ทรัพยากรแชร์ได้	อาจารย์บอกว่าถ้าขัดกับระบบที่ออกแบบไว้ ก็ต้องคงเงื่อนไขนี้ไว้ (เช่น เครื่องพิมพ์แชร์ไม่ได้)
Hold and wait	Request all resources (ขอทั้งหมดในครั้งเดียว) หรือ if wait → not hold (ถ้าต้องรอ ห้ามถือของไว้)	อาจารย์: "สิ่งที่เราควบคุมได้คือ hold and wait, circular wait กับ preemption" และ no preemption เกี่ยวข้องกับ hold and wait
No preemption	Allow preemption (ยึดทรัพยากรคืนได้)
Circular wait	Order no. ให้เลขลำดับทรัพยากร แล้วขอได้ตามลำดับเลขจากน้อยไปมากเท่านั้น จึงวนเป็นวงไม่ได้

❌ ข้อเสียของแต่ละวิธี prevention (ควรรู้ไว้ตอบข้อเปรียบเทียบ)

ขอทั้งหมดครั้งเดียว: ต้องรู้ล่วงหน้าว่าจะใช้อะไรบ้าง ทรัพยากรถูกจองไว้นานโดยยังไม่ได้ใช้ (ใช้ไม่คุ้ม) และ process ที่ต้องการของเยอะอาจรอนานมาก (starvation)
Allow preemption: ทำได้กับทรัพยากรที่เก็บสถานะแล้วคืนได้ (เช่น CPU, memory) แต่ทำกับเครื่องพิมพ์ที่กำลังพิมพ์ครึ่งแผ่นไม่ได้
Order no.: ต้องกำหนดเลขให้ทุกทรัพยากร และโปรแกรมต้องขอตามลำดับเสมอ ทำให้เขียนโปรแกรมยากขึ้น

Deadlock avoidance = ไม่ให้ระบบเข้า unsafe state

Safe state = มีลำดับการรัน (safe sequence) อย่างน้อยหนึ่งลำดับ ที่ทุกโปรเซสได้ทรัพยากรครบแล้วจบได้ → ไม่เกิด deadlock
Unsafe state = หา safe sequence ไม่ได้ ซึ่งยังไม่ใช่ deadlock แต่มีโอกาสเกิด
เครื่องมือหลักคือ Banker's algorithm: ก่อนให้ทรัพยากรต้องลองคำนวณก่อนว่าให้แล้วยัง safe ไหม

🔍 ตัวอย่างง่ายๆ ก่อนเจอตารางใหญ่: ทรัพยากรชนิดเดียว มี 12 ชิ้น

         Max   ถืออยู่   ยังต้องการ (Need)
P0        10      5          5
P1         4      2          2
P2         9      2          7
ว่างอยู่ (Available) = 12 − (5+2+2) = 3

ใครที่ Need ≤ 3 ได้บ้าง? → P1 (ต้องการ 2) ให้ P1 ไปจนจบ แล้ว P1 คืนของที่ถือทั้งหมด → ว่าง 3 + 2 = 5
Need ≤ 5? → P0 (ต้องการ 5) ทำจนจบแล้วคืน 5 → ว่าง 10
Need ≤ 10? → P2 (ต้องการ 7) ทำจนจบ → ครบทุกตัว

มีลำดับ <P1, P0, P2> ที่ทุกคนทำจบได้ → safe state

แต่ถ้าตอนนี้ยอมให้ P2 เพิ่ม 1 ชิ้น (P2 ถือ 3, ว่าง 2): P1 ทำจบได้ → ว่าง 4 แต่ P0 ต้องการ 5 และ P2 ต้องการ 6 ไม่มีใครไปต่อได้ → unsafe → avoidance จึงไม่ยอมให้ P2 ตอนนี้ ให้รอก่อน

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

เกทไหม? ลองตอบ

ทรัพยากรชนิดเดียวมี 10 ชิ้น P0 (Max 7, ถือ 3) และ P1 (Max 4, ถือ 2) ตอนนี้ระบบ safe หรือไม่

ว่าง = 10 − 5 = 5 · P1 ต้องการอีก 2 ≤ 5 → ทำจบแล้วคืน 2 → ว่าง 7 · P0 ต้องการอีก 4 ≤ 7 → จบได้ จึง safe

กติกา "ต้องขอทรัพยากรทั้งหมดก่อนเริ่มทำงาน" ทำลายเงื่อนไขใด

ถ้าได้ครบตั้งแต่แรกก็ไม่ต้องถือของไว้แล้วรอของเพิ่ม (request all resources)

unsafe state เท่ากับ deadlock หรือไม่

unsafe = หา safe sequence ไม่ได้ จึงเสี่ยง แต่ deadlock อาจยังไม่เกิดจริง (deadlock เป็นส่วนหนึ่งของ unsafe)

1.6 Banker's Algorithm ★

🎯 ต้องทำได้หา Total, Need และ safe sequence ได้ และตอบได้ว่าคำขอ (request) ให้ได้หรือไม่ พร้อมเหตุผล

🤔 Banker's algorithm คืออะไร

คือวิธีทำ avoidance เมื่อมีทรัพยากรหลายชนิด (R1, R2, R3 …) ทำแบบเดียวกับตัวอย่าง 12 ชิ้นด้านบนเป๊ะ เพียงแต่ตัวเลขเป็นเวกเตอร์หลายช่อง และต้องเทียบทุกช่อง

❓ ทำไมใช้ Need ไม่ใช้ Max

เพราะ process ถือของอยู่แล้วบางส่วน สิ่งที่ต้องได้เพิ่มจึงเหลือแค่ Need = Max − Allocation ถ้า Need ≤ Work แปลว่าตอนนี้มีของว่างพอให้มันทำงานจนจบ

❓ ทำไมพอทำจบแล้วต้อง Work = Work + Allocation

เพราะ process ที่ทำงานจบจะคืนทุกอย่างที่ถืออยู่ (ซึ่งก็คือ Allocation ของมัน) ของว่างจึงเพิ่มขึ้นเท่ากับที่มันถือ (ไม่ใช่บวก Need หรือ Max)

โครงสร้างข้อมูล (n โปรเซส, m ชนิดทรัพยากร)

Available (เวกเตอร์ m ช่อง) = ที่เหลือว่างตอนนี้
Max (n × m) = ที่แต่ละโปรเซสประกาศว่าจะใช้มากที่สุด
Allocation (n × m) = ที่ได้ไปแล้ว
Need = Max − Allocation (ที่ยังต้องการอีก) เช่น N₁₂ = M₁₂ − A₁₂

Safety algorithm (ตามชีท)

1. Work = Available,  Finish[i] = false ทุกตัว
2. หา i ที่ Finish[i] = false และ Need[i] ≤ Work
   ถ้าไม่มี ไปขั้น 4
3. Work = Work + Allocation[i],  Finish[i] = true  แล้วกลับไปขั้น 2
4. ถ้า Finish[i] = true ทุกตัว → safe state  ไม่งั้น → unsafe state

Resource-request algorithm (เมื่อ P_i ขอเพิ่ม)

1. Request ≤ Need[i] ?      ไม่ใช่ → error (ขอเกินที่ประกาศ)
2. Request ≤ Available ?    ไม่ใช่ → ต้องรอ (Available ไม่พอ)
3. สมมติให้ไปก่อน:  Available −= Request, Allocation[i] += Request, Need[i] −= Request
   แล้วรัน safety → safe = ให้ได้ / unsafe = ยกเลิก ให้รอ

ตัวอย่างในชีท (หน้า 58–61) ทำทีละขั้น

Allocation

    R1 R2 R3
P1   0  1  0
P2   2  0  0
P3   3  0  2
P4   2  1  1
P5   0  0  2

Max

    R1 R2 R3
P1   7  5  3
P2   3  2  2
P3   9  0  2
P4   2  2  2
P5   4  3  3

Need = Max − Allocation

    R1 R2 R3
P1   7  4  3
P2   1  2  2
P3   6  0  0
P4   0  1  1
P5   4  3  1

Available = (3, 3, 2) → Total = Allocation รวม + Available = (7+3, 2+3, 5+2) = (10, 5, 7)

Work = (3,3,2)
P1 need 7,4,3 ≤ 3,3,2 ?  ไม่ได้ ข้าม
P2 need 1,2,2 ≤ 3,3,2 ?  ได้  → Work = 3,3,2 + 2,0,0 = (5,3,2)
P3 need 6,0,0 ≤ 5,3,2 ?  ไม่ได้ ข้าม
P4 need 0,1,1 ≤ 5,3,2 ?  ได้  → Work = 5,3,2 + 2,1,1 = (7,4,3)
P5 need 4,3,1 ≤ 7,4,3 ?  ได้  → Work = 7,4,3 + 0,0,2 = (7,4,5)
(วนรอบ 2)
P1 need 7,4,3 ≤ 7,4,5 ?  ได้  → Work = (7,5,5)
P3 need 6,0,0 ≤ 7,5,5 ?  ได้  → Work = (10,5,7)
Safe sequence = <P2, P4, P5, P1, P3>   ✓ ตรงกับชีท

คำขอในชีท (ทำต่อเนื่องกัน):

P2 ขอ (1,0,2): ≤ Need (1,2,2) ✓ และ ≤ Available (3,3,2) ✓ → สมมติให้: Available = (2,3,0) → ตรวจแล้วยัง safe <P2, P4, P5, P1, P3> → ให้ได้
P4 ขอ (3,3,0): Available (2,3,0) ไม่พอ → ให้ไม่ได้ ("Available not enough" ตามชีท) (ถ้าตรวจตามอัลกอริทึมเต็ม ข้อ 1 ก็ไม่ผ่านแล้ว เพราะ Need ของ P4 คือ (0,1,1))
P1 ขอ (0,2,0): Available พอ แต่พอ "simulate new state" แล้ว Available = (2,1,0) ไม่มีใครผ่านเลย → unsafe จึงให้ไม่ได้

⚠️ จุดที่มักพลาด • ลืมหา Need แล้วไปเทียบ Max กับ Work แทน (ต้องใช้ Need)
• ตอนให้ทำงานจบ ต้องบวก Allocation เข้า Work ไม่ใช่บวก Max หรือ Need
• ชีทเรียก P1–P5 ส่วนตำราใช้ P0–P4 ให้ใช้ชื่อตามโจทย์
• safe sequence มีได้หลายแบบ ถ้าทุกขั้นผ่าน Need ≤ Work ก็ถูก แต่ต้องแสดง Work ทุกขั้น

แบบฝึกหัดจากชีท

Q6Example 2.4.B: Total instances ของ R1, R2, R3 คือเท่าไร (ตอบเช่น 9,3,6)

Total = ผลรวม Allocation + Available = (1+6+2+0, 0+1+1+0, 0+2+1+2) + (0,1,1) = (9, 3, 6)

Q7Example 2.4.B: safe sequence คืออะไร (ไล่ P1→P4 วนแบบชีท)

Need: P1 2,2,2  P2 0,0,1  P3 1,0,3  P4 4,2,0
Work 0,1,1: P1 ✗ · P2 ✓ → 6,2,3 · P3 ✓ → 8,3,4 · P4 ✓ → 8,3,6
รอบ 2: P1 ✓ → 9,3,6
safe sequence = <P2, P3, P4, P1>

Q8Example 2.4.C: safe sequence คืออะไร

Total = (7,2,6)
Need: P1 0,0,0  P2 2,0,2  P3 0,0,0  P4 1,0,0  P5 0,0,2
Work 0,0,0: P1 ✓ → 0,1,0 · P2 ✗ · P3 ✓ → 3,1,3 · P4 ✓ → 5,2,4 · P5 ✓ → 5,2,6
รอบ 2: P2 ✓ → 7,2,6
safe sequence = <P1, P3, P4, P5, P2>

ฝึกเพิ่มด้วยโจทย์สุ่ม (ระบบตรวจ safe sequence ที่เราตอบได้ทุกแบบที่ถูก):

1.7 Deadlock detection

🤔 Detection ต่างจาก Banker's (avoidance) ยังไง

	Avoidance (Banker's)	Detection
ทำตอนไหน	ก่อนให้ทรัพยากร	หลังปล่อยให้ระบบทำงานไปแล้ว (ตรวจเป็นระยะ)
ถามว่าอะไร	ถ้าให้แล้ว "อนาคต" ยังมีทางให้ทุกคนจบไหม	"ตอนนี้" มีใครติดอยู่จริงไหม
ใช้ข้อมูล	Need (= Max − Allocation)	Request (สิ่งที่ขออยู่ตอนนี้จริงๆ)
ผลลัพธ์	safe / unsafe	มี deadlock ไหม และใครติด

⚙️ Wait-for graph (เมื่อทุกทรัพยากรมี 1 instance)

เอากล่อง R ออกจาก RAG แล้วต่อเส้นตรง: ถ้า P_i → R → P_j (P_i รอ R ที่ P_j ถืออยู่) ให้เขียนเป็น P_i → P_j (P_i รอ P_j) ถ้ากราฟใหม่มี cycle = deadlock

⚙️ หลาย instance: อัลกอริทึมคล้าย safety

Work = Available แล้วหา P_i ที่ Request_i ≤ Work ให้ทำจบแล้ว Work += Allocation_i วนไปเรื่อยๆ ตัวที่ไล่ไม่ถึง (Finish = false) คือตัวที่ติด deadlock

ทรัพยากร instance เดียว: ใช้ RAG แล้วยุบเป็น wait-for graph (เอาโหนด R ออก เหลือ P_i → P_j = P_i รอ P_j) ถ้ามี cycle = deadlock
หลาย instance: ใช้อัลกอริทึมคล้าย safety แต่ใช้ Request แทน Need และถ้า Finish[i] = false ที่ตัวไหน แปลว่าตัวนั้นติด deadlock

ตัวอย่างในชีท: Resource = (7, 2, 6) ให้ข้อ 1 ตรวจ deadlock และข้อ 2 ถ้า P3 ขอ R3 เพิ่ม 1 instance จะเป็นอย่างไร

Q9ตัวอย่างหน้า 66: ข้อ 1 เกิด deadlock ไหม และข้อ 2 (P3 ขอ R3 เพิ่ม 1) เป็นอย่างไร

ข้อ 1: Work (0,0,0) → P1 ✓ (0,1,0) → P3 ✓ (3,1,3) → P4 ✓ (5,2,4) → P5 ✓ (5,2,6) → P2 ✓ (7,2,6) ไม่เกิด deadlock
ข้อ 2: Request ของ P3 เป็น (0,0,1) → P1 ✓ ได้ Work (0,1,0) แต่ P2 (2,0,2), P3 (0,0,1), P4 (1,0,0), P5 (0,0,2) ไม่มีใครผ่าน → deadlock: P2, P3, P4, P5

สรุปบทนี้ใน 1 นาที

เงื่อนไข 4 ข้อ: ME, Hold & wait, No preemption, Circular wait (necessary ไม่ใช่ sufficient)
RAG: P→R = request, R→P = allocation; instance เดียว + cycle = deadlock
การบ้านชีวิตประจำวัน: สถานการณ์ → process state → RAG → cycle/matrix → เช็ค 4 ข้อ + สรุป
Prevention: ขอทั้งหมด / ถ้ารอห้ามถือ, ยอม preempt, ให้เลขลำดับ
Avoidance: safe/unsafe → Banker's: Need = Max − Alloc, Work += Alloc
Request: ≤ Need → ≤ Available → ลองให้ → ยัง safe ไหม
Detection: แบบ safety แต่ใช้ Request ตัวที่ Finish = false = ติด deadlock

← บทที่ 0 ปูพื้นฐาน บทที่ 2 Memory →