การติดตาย (Deadlock)

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

        รูปแบบโครงสร้าง

ทรัพยากรในระบบมีอยู่อย่างจำกัดในการใช้งาน ดังนั้นจึงต้องเกิดการแย่งเข้าใช้ทรัพยากรนั้น  ชนิดของ

ทรัพยากรในที่นี้แบ่งออกเป็น เนื้อที่ว่างในหน่วยความจำ  เวลาในการประมวลผล  ไฟล์ และอุปกรณ์ I/O เมื่อโพรเซสต้องการเข้าใช้ทรัพยากรต้องมีการร้องขอแล้วก็ออกจากการใช้ทรัพยากรนั้นหลังจากเสร็จสิ้นการทำงาน ณ ส่วนนั้น จำนวนการร้องขอใช้ทรัพยากรจะต้องไม่มากกว่าจำนวนทรัพยากรที่มีอยู่ในระบบ ดังนั้นสามารถลำดับการทำงานของโพรเซสใช้ทรัพยากรดังนี้

1. request  ถ้าในกรณีที่การร้องขอไม่สามารถได้รับการตอบสนองทันที อาจเนื่องจากทรัพยากรขณะนั้นกำลังถูกโพรเซสอื่นใช้งาน  แล้วโพรเซสที่ทำการร้องขอเข้ามาต้องรอจนกว่าจะเข้าใช้ทรัพยากรนั้นได้

2. Use : โพรเซสสามารถทำงานบนทรัพยากร (เช่น การพิมพ์งานผ่านทางเครื่องพิมพ์)

3. Release : โพรเซสออกจากการใช้ทรัพยากร

ลักษณะของการติดตาย

การติดตายสามารถเกิดขึ้นได้หากเกิดสถานการณ์ดังต่อไปนี้

1. Mutual Exclusion  ต้องมีทรัพยากรอย่างน้อย 1 ตัวที่ไม่ได้อนุญาตให้ร่วมใช้งาน ดังนั้นมีเพียงโพรเซสเดียวที่สามารถเข้าใช้งาน  ถ้าโพรเซสอื่นมีการร้องขอเข้าใช้งาน การร้องขอต้องถูกรอจนกว่าทรัพยากรนั้นจะว่างให้ใช้งาน

2. Hold & wait ต้องมีโพรเซสมีการใช้งานทรัพยากรอย่างน้อย 1 ตัว และกำลังรอเพื่อเข้าทำงานทรัพยากรอีกตัวที่กำลังถูกโพรเซสอื่นใช้งาน

3. No  Preemption  ทรัพยากรสามารถถูกปล่อยได้ตามความพอใจของโพรเซสที่กำลังใช้งาน ซึ่งก็คือหลังจากที่งานของโพรเซสนั้นเสร็จสิ้น เนื่องจากขึ้นอยู่กับความพอใจของโพรเซสว่าจะยอมปล่อยทรัพยากรออกให้ใช้งานได้เมื่อไหร่

4. Circular Wait มีเชตของ {P0, P1, ..., Pn} ของโพรเซสที่กำลังรอเช่น P0 กำลังรอทรัพยากรที่ถูกใช้โดย P1 ขณะเดียวกัน P1 ก็รอเข้าใช้ทรัพยากรที่กำลังถูกโพรเซส P2 ใช้งาน  ท้ายสุดโพรเซสตัวสุดท้ายกำลังรอเข้าใช้ทรัพยากรที่โพรเซสแรกกำลังใช้งาน

การกำหนดทรัพยากรด้วยกราฟ

 

                การติดตายสามารถอธิบายได้ด้วยกราฟอย่างง่ายๆ เรียกว่า System resource-allocation graph  กราฟนี้จะประกอบไปด้วยกลุ่มของ V (Vertices) และกลุ่มของ E (edge)   กลุ่มของ V แบ่งออกเป็น 2 ส่วนใหญ่คือจุดของ

P = {P1,P2,P3...,Pn}  เซตนี้ประกอบด้วยโพรเซสที่กำลังทำงานในระบบ  และจุดของ R = {R1,R2,R3...,Rm} เซตนี้ประกอบด้วยทรัพยากรทุกชนิดในระบบ    การร้องขอสามารถแทนได้ด้วย  Pi à Rj  หมายถึงโพรเซส Pi ขอเข้าทำงานทรัพยากร Rj   ส่วนการกำหนดให้ทรัพยากรบริการโพรเซสแทนได้ด้วย Rk à Pj หมายถึงทรัพยากร Rk กำลังถูกโพรเซส Pj ใช้งาน

 วิธีการควบคุมการติดตาย

เพื่อป้องกันหรือควบคุมการเกิดการติดตายสามารถทำได้ 3 วิธีคือ

1. แน่ใจว่าระบบจะไม่เกิดการติดตายโดยการใช้ Protocol

2. ยอมให้ระบบเข้าสู่การติดตายได้ชั่วคราวแล้วสามารถออกมาได้

3. เมินเฉยทุกอย่าง แล้วอ้างว่าไม่เคยเกิดการติดตายในระบบ วิธีนี้ใช้อยู่ในระบบ Unix

 การป้องกันการติดตาย

Mutual Exclusion  เงื่อนไขของการเกิด mutual คือการใช้งานทรัพยากรที่อนุญาตให้ใช้ได้ทีละงาน เช่น เครื่องพิมพ์  อีกนัยหนึ่งการร่วมใช้ข้อมูลโดยไม่ต้องการเข้า mutual ทำให้ไม่เกิดการติดตาย ตัวอย่างของไฟล์ที่สามารถอ่านได้อย่างเดียว ถ้าหลายๆโพรเซสพยายามที่จะอ่านก็สามารถเข้าอ่านได้ทันทีอย่างต่อเนื่อง อย่างไรก็ดีทรัพยากรบางชนิดไม่สามารถประกาศใช้งานร่วมกันได้

                Hold / Wait  รับรองได้ว่าเมื่อมีการร้องขอใช้ทรัพยากรทำงาน โพรเซสนั้นต้องไม่ได้กำลังใช้งานทรัพยากรอื่นอยู่ ซึ่งสามารถทำได้หลายวิธีการเช่น บังคับให้โพรเซสร้องขอแล้วก็จัดสรรการใช้งานทรัพยากรให้กับโพรเซสนั้นๆก่อนที่จะมีการเริ่มทำงาน   หรือยอมให้โพรเซสขอใช้ทรัพยากรได้เมื่อโพรเซสไม่ได้ทำงานในส่วนใดอยู่

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

                Circular Wait  ก่อนที่จะเริ่มใช้วิธีการนี้ต้องทำการกำหนดลำดับของชนิดทรัพยากรทั้งหมดและเมื่อร้องขอว่าในแต่ละโพรเซสที่ขอใช้ทรัพยากรเป็นการเพิ่มจำนวนลำดับของชนิดทรัพยากรที่ได้ระบุไว้ กำหนดให้ R เป็นเซตของชนิดทรัพยากร R1 , R2 .. ,Rn  เรากำหนดในแต่ละชนิดทรัพยากรเป็นเลขจำนวนเต็มเพื่อให้สามารถทำการเปรียบเทียบได้  เช่นถ้าเซต ทรัพยากรกลุ่ม R คือมีเทป ดิสก์ และเครื่องพิมพ์

   การหลีกเลี่ยงการติดตาย

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

fivedots.coe.psu.ac.th/~wannarat/240-323/chapter7.doc