Please enable JavaScript.
Coggle requires JavaScript to display documents.
บทที่ 5การติดตาย - Coggle Diagram
บทที่ 5การติดตาย
5.6 การป้องกันการติดตาย โดยการออกแบบให้ระบบมีการป้องกันการเกิดวงจรอับไว้ก่อน ดังนั้นการ
ป้องกันการเกิดวงจรอับสามารถแบ่งได้เป็น 2 กลุ่ม ได้แก่
- การป้องกันการเกิดวงจรอับทางอ้อม คือ การป้องกันการเกิดเงื่อนไขสามข้อแรกที่อาจจะทำให้
เกิดวงจรอับได้
- ที่ว่าเงื่อนไขทั้งสี่ข้อจะต้องเกิดขึ้นพร้อมกัน จึงจะทำให้เกิดวงจรอับได้
5.6.1 การใช้ทรัพยากรร่วมกันได้(Mutual Exclusion Prevention) ปัญหาในข้อนี้คือ การที่ทรัพยากรในระบบไม่อนุญาตให้โพรเซสหลาย ๆ โพรเซสใช้งานพร้อม ๆ
กันได้ระบบปฏิบัติการจะต้องจัดการให้โพรเซสในระบบสามารถใช้งานทรัพยากรเหล่านั้นร่วมกันได้
5.6.2 การป้องกันการถือครองและรอคอย (Hold and Wait Prevention) เงื่อนไขของการถือครองและรอคอยนั้นสามารถป้องกันได้ โดยเราจะอนุญาตให้โพรเซสร้องขอทรัพยากรที่ต้องการทั้งหมดก่อนและจะไม่อนุญาตให้โพรเซสนั้นท างานจนกว่าจะได้รับทรัพยากรที่ร้องขอ
ไปพร้อมกันทั้งหมดก่อน
5.6.3 ยอมให้มีการแทรกกลางคัน (Preemptable)เงื่อนไขนี้เราสามารถทำการป้องกันได้หลาย ๆ วิธี และเงื่อนไขนี้จะยอมให้โพรเซสสามารถแย่งชิงทรัพยากรที่ถูกครอบครองโดยโพรเซสอื่นได้อย่างแรกคือถ้าโพรเซสกำลังถือครองทรัพยากรหนึ่งอยู่ เราจะให้ระบบป้องกันไม่ให้โพรเซสนั้นทำการร้องขอทรัพยากรอื่นใดอีก จนกว่าโพรเซสนั้นจะปลดปล่อยทรัพยากรที่ตัวเองครอบครองเสียก่อน และในบางกรณีถ้าโพรเซสต้องการทรัพยากรเพิ่ม ระบบอาจจะ
กำหนดให้โพรเซสปล่อยทรัพยากรที่ตัวเองครอบครองอยู่ก่อน
5.6.4 การป้องกันการเกิดวงจรรอคอย (Circular wait protection)เพื่อไม่ให้เกิดการรอแบบวงกลม ระบบจะกำหนดหมายเลขประจำให้แต่ละทรัพยากร และเมื่อมีการร้องขอทรัพยากรจากโพรเซสใด ๆจะต้องเป็นการร้องขอเรียงตามลำดับหมายเลขประจำทรัพยากร
จากน้อยไปมากเสมอ
5.7 การหลีกเลี่ยงการติดตาย รูปแบบอัลกอริทึมของการหลีกเลี่ยงการติดตายจะมีการตรวจสอบสถานะของการใช้ทรัพยากร เพื่อให้แน่ใจว่าจะไม่เกิดการรอแบบลูปอย่างสม่ำเสมอตลอดเวลาความหมายคือต้องการให้ระบบอยู่ในสถานะที่ปลอดภัย (Safe state) ดังนั้นสถานะของการใช้ทรัพยากร
ถูกก าหนดด้วยจ านวนของทรัพยากรที่ถูกใช้งานและจ านวนทรัพยากรที่มีอยู่ในระบบ
5.7.1 สถานะที่ปลอดภัย (Safe State) เมื่อโพรเซสร้องขอทรัพยากรที่มีอยู่ ระบบต้องตัดสินว่าถ้าให้ใช้ทรัพยากรแล้วระบบจะยังคงอยู่ในสถานะที่ปลอดภัยหรือไม่ (Safe state หมายถึง สถานะที่ทรัพยากรสามารถให้บริการได้ทุกโพรเซส)ลักษณะของ Sequence <P1, P2, ...,Pn> จะยังคงดำเนินได้ก็ต่อเมื่อทรัพยากรที่ Pi ขอทำงาน ยังคงทำงานได้อย่างน่าพอใจ ซึ่งจะกำหนดโดยทรัพยากรที่มีในขณะนั้นบวกกับทรัพยากรที่ถูกใช้งานอยู่ทั้งหมด
5.7.2 อัลกอริทึมการกำหนดทรัพยากรด้วยกราฟ Claim Edge Pi -> Rj เป็นตัวกำหนดว่าโพรเซส Pi อาจทำการขอใช้ทรัพยากร Rj ซึ่งแทนได้
ด้วยจุดปะ มีโพรเซส 2 ขอใช้งานทรัพยากร 2 และ 1 ในขณะนั้นมีโพรเซส 1กำลังร้องขอใช้งานด้วย แล้วทรัพยากร 1 ให้บริการโพรเซส 1 อยู่ ดังนั้นระบบมีสิทธิที่จะยอมให้โพรเซส 2เข้าใช้งานทรัพยากร 2 ได้ แต่พบว่าถ้ายอมให้มีการใช้ทรัพยากร 2 จะทำให้ระบบอยู่ในภาวะที่ไม่ปลอดภัยเนื่องจากจะเกิดการลูปรอหรือการติดตายทันที
-
5.7.4 อัลกอริทึมที่ปลอดภัย อัลกอริทึมที่หาได้ว่าระบบปลอดภัยหรือไม่ สามารถท าได้โดยก าหนดให้work และ finish เป็น
เวกเตอร์ที่มีขนาด n x m โดยเริ่มท างานตามล าดับดังนี้
ขั้นตอนที่ 2 หาค่า Pi ทั้ง 2 ฟังก์ชัน คือ Finish[i] == false , Needi ≤ Work ถ้าไม่ตามเงื่อนไข ข้ามไปยังขั้นตอนที่ 4
ขั้นตอนที่ 3 Work = Work + Allocation, Finish[i] = true กลับไปยังขั้นที่ 2 ถ้า
ขั้นตอนที่ 1 Work = Available และ Finish[i] = false โดยที่ i มีค่าตั้งแต่ 0, 1, 2...,n-1
ขั้นตอนที่ 4 ถ้า Finish [i] == true สำหรับทุกๆ i, แสดงว่าระบบอยู่ ใน Safe state เวลาในการใช้ทำงานอัลกอริทึมนี้เท่ากับ m x n2
5.7.5 อัลกอริทึมของการขอใช้ทรัพยากร กำหนดให้Requesti เป็นเวกเตอร์ของการขอใช้งานสำหรับโพรเซส i ถ้า requesti[j] = k
- ถ้า Requesti ≤ Available ไปยังขั้นตอนที่ 3 นอกจากนี้โพรเซส i ต้องรอเนื่องจากทรัพยากรไม่มีให้ใช้งาน
- ถ้า Requesti ≤ Needi ไปยังขั้นตอนที่ 2 นอกจากนั้น ให้แสดงข้อความเตือน เนื่องจาก โพรเซสมีการใช้ทรัพยากรมากกว่าที่คาดการณ์ไว้
- มีการตั้งระบบลวงเพื่อใช้ทรัพยากรที่โพรเซส i ขอใช้ โดยการใส่ค่าในตัวแปรต่อไปนี้
Available = Available – Request;
Allocationi = Allocationi + Requesti;
Needi = Needi – Requesti
5.4 เงื่อนไขที่ทำให้เกิดวงจรอับ วงจรอับ เป็นสถานการณ์ที่เราไม่ต้องการให้เกิดขึ้นในระบบ เพราะว่าเมื่อเกิดวงจรอับขึ้นมา จะทำให้ไม่มีโพรเซสใดสามารถทำงานจนเสร็จสมบูรณ์ได้ และทรัพยากรของระบบจะถูกครอบครองจนหมด
- การครอบครองและการรอใช้ทรัพยากร (Hold and Wait)โพรเซสที่ได้ครอบครอง (Hold)ทรัพยากรอยู่แล้ว ต้องการใช้ทรัพยากรอื่นเพิ่มเติม และร้องขอทรัพยากรที่มีสถานะไม่ว่าง ทำให้โพรเซส
ต้องรอ (Wait)
- การไม่แย่งชิงทรัพยากร (No preemptive)โพรเซสที่รอใช้ทรัพยากรต่อจากโพรเซสอื่น (ที่ก าลังใช้ทรัพยากรนั้นอยู่) จะต้องรอจนกว่าโพรเซสนั้น ๆ ทำงานเสร็จ และปลดปล่อยทรัพยากร โพรเซสไม่
สามารถแย่งชิงทรัพยากรจากโพรเซสอื่นได้
- การไม่เกิดร่วม (Mutual exclusion)ขณะเวลาหนึ่งจะมีเพียงโพรเซสเดียวที่ใช้งาน
ทรัพยากรได้ไม่สามารถมีโพรเซสอื่นใช้งานทรัพยากรพร้อมกันได้
- การรอแบบวงกลม (Circulate wait)โพรเซสเกิดการรอเป็นวัฏจักร (P0, P1, P2, ..., Pn)
โดย P0 รอทรัพยากรที่ถูกครอบครองโดย P1 P1 รอทรัพยากรที่ถูกครอบครองโดย P2 จนถึง Pn-1
5.5 การกำหนดทรัพยากรด้วยกราฟ เราได้เรียนรู้การทำงานของกราฟการจัดสรรทรัพยากรในลักษณะที่ทรัพยากรแต่ละชนิดมีทรัพยากรเพียง 1 ตัว (Single resource for each type) แต่กราฟนี้สามารถใช้งานในกรณีที่ทรัพยากรแต่
ละชนิดมีทรัพยากรหลาย ๆหลังจากนี้เราจะเรียนรู้ถึงวิธีการป้องกันไม่ให้ระบบเกิดวงจรอับ
ซึ่งโดยทั่วไปแล้ว การจัดการวงจรอับนั้นมีกลยุทธ์อยู่ 4 วิธี ที่สามารถนำมาใช้ได้
- ทำการหลีกเลี่ยง โดยการจัดสรรทรัพยากรให้ถูกต้อง
- การตรวจพบและแก้ไขคืน จะอนุญาตให้วงจรอับเกิดขึ้น และค่อยทำการเช็คหาและแก้ไขมัน
- ทำการป้องกันไว้ก่อน โดยไม่ให้หนึ่งในเงื่อนไขทั้งสี่ข้อของการทำให้เกิดวงจรอับเกิดขึ้น
- ไม่ต้องสนใจปัญหาใด ๆ เลย ในบางครั้งถ้าเราไม่สนใจปัญหาที่จะเกิดขึ้น ปัญหาก็อาจจะไม่เกิด
ขึ้นกับคุณก็ได้
5.9 การกู้คืนจากการติดตาย ระบบที่เกิดการติดตายจะไม่สามารถท างานใด ๆ ต่อไปได้จำเป็นต้องมีวิธีการก าจัดการติดตายที่เกิดขึ้น เพื่อกู้ระบบกลับคืนสู่สภาพที่ใกล้เคียงกับสภาพก่อนที่จะเกิดการติดตาย วิธีการที่ใช้ก าจัดการติดตายสามารถ ทำได้2 วิธีคือ
- การยกเลิกโพรเซส (Process termination)
- การแย่งชิงทรัพยากรจากโพรเซส (Resource preemption)
5.9.1 การยกเลิกโพรเซส (Process Termination)การก าจัดการติดตายด้วยการยกเลิกโพรเซส สามารถทำได้2 วิธีซึ่งแต่ละวิธีนั้นระบบจะเรียก
ทรัพยากร (ที่ได้จัดสรรไปแล้ว) คืนจากโพรเซส จากนั้นจึงยกเลิกโพรเซส
- การยกเลิกทุกโพรเซสที่เกิดการติดตาย วิธีนี้เป็นการกำจัดการติดตายด้วยการยกเลิก แต่มีข้อเสียอาจมีบางโพรเซสที่ทำงานมาเป็นเวลานานแล้วแต่โพรเซสต้องถูกยกเลิกไป ท าให้โพรเซสต้องเสียเวลาและเสียค่าใช้จ่าย
- การยกเลิกทีละหนึ่งโพรเซส วิธีนี้เป็นการยกเลิกโพรเซสทีละหนึ่งโพรเซส จนกว่าการติดตายจะถูกกำจัดออกไประบบต้องเรียกอัลกอริทึมตรวจสอบการติดตายเพื่อตรวจสอบว่า ระบบยังคงมีการติดตายอยู่หรือไม่ ทำให้เปลืองค่าใช้จ่ายอื่น ปัจจัยที่ระบบใช้ในการพิจารณาเลือกว่าระบบจะยกเลิกโพรเซสใด โดยสามารถใช้หลักเกณฑ์ดังนี้
- เลือกโพรเซสที่ได้ครอบครองทรัพยากรไปแล้วน้อยที่สุด เนื่องจากโพรเซสนั้นมีโอกาสทำงาน
เสร็จสมบูรณ์น้อยกว่าโพรเซสที่ได้ครอบครองทรัพยากรเป็นจำนวนมาก
- เลือกโพรเซสที่มีลำดับความสำคัญ หรือความสำคัญน้อยที่สุด จะถูกยกเลิกก่อนโพรเซสที่มีล าดับความสำคัญมากกว่า
- เลือกโพรเซสที่ได้ให้ผลลัพธ์ หรือเอาต์พุตออกมาแล้วน้อยที่สุด
- เลือกโพรเซสที่ยังต้องการเวลาในการทำงานมากที่สุด
- เลือกโพรเซสที่ได้ใช้เวลาของตัวประมวลผลไปแล้วน้อยที่สุดลักษณะนี้เนื่องจากจะเกิดความเสียหายน้อยกว่าการเลือกยกเลิกโพรเซสที่ถูกประมวลผลไปเป็นระยะเวลานาน
5.9.2 การแย่งชิงทรัพยากรจากโพรเซส (Resource preemptive) วิธีนี้ระบบพยายามกำจัดการติดตายด้วยการแย่งชิงทรัพยากรจากโพรเซสใดโพรเซสหนึ่ง เพื่อนำทรัพยากรนั้นไปมอบให้อีกโพรเซสหนึ่ง
- การถอยกลับ (Rollback) ให้โพรเซสที่ถูกแย่งชิงทรัพยากรไปนั้นไม่
สามารถประมวลผลต่อไปได้ระบบจำเป็นต้องให้โพรเซสถอยหลังกลับไปอยู่ในสถานะปลอดภัยคือให้โพรเซสถอยหลังกลับไปยังสถานะที่อยู่ห่างจากสถานะที่ทำให้เกิดการติดตายมากที่สุดดังนั้นต้องมีการเก็บค่าสถานะของ โพรเซสที่กำลังทำงานไว้ก่อนเริ่มงานใหม่
- การอดตาย (Starvation) เป็นไปได้ว่าอาจเกิดการแย่งชิงทรัพยากรจากโพรเซสเดิมอยู่ตลอดเวลา โพรเซสอยู่ในสถานะอดตายการรอดตายต้องให้มั่นใจว่าเมื่อยึดไปแล้วจะไม่เกิดการอดตายเนื่องจากโพรเซสไม่มีโอกาสได้ใช้ทรัพยากรอีกเลย
- การเลือกเหยื่อ (Selecting a victim) ดังนั้นถ้าระบบ
จ าเป็นต้องพิจารณาเพื่อยกเลิกโพรเซสจำนวนหนึ่งโพรเซส ระบบอาจเลือกยกเลิกโพรเซสที่ครอบครอง ทรัพยากรเป็นจำนวนน้อยที่สุด และเป็นโพรเซสที่ทำงานไปแล้วเป็นเวลาไม่นานนัก
5.1 รูปแบบโครงสร้าง เมื่อโพรเซสต้องการใช้
ทรัพยากรจะต้องร้องขอทรัพยากรจากระบบโดยสามารถขอใช้ทรัพยากรให้ได้จำนวนมากที่สุด เพื่อให้
โพรเซสสามารถทำงานได้เสร็จสิ้นแต่ไม่สามารถร้องขอทรัพยากรมากเกินกว่าที่ระบบมีอยู่จริง
- การใช้งาน (Use) เมื่อโพรเซสได้รับทรัพยากรที่ต้องการแล้ว โพรเซสสามารถใช้งานทรัพยากรที่ได้รับ
- การคืน (Release) โพรเซสต้องคืนทรัพยากรที่ใช้เสร็จแล้วกลับสู่ระบบ เพื่อเปิดโอกาสให้โพรเซสอื่นที่ต้องการใช้ทรัพยากรนั้นได้รับการจัดสรรทรัพยากรต่อไป
- การร้องขอ (Request) เมื่อโพรเซสต้องการใช้ทรัพยากรใด ๆ จะต้องทำการร้องขอทรัพยากร
นั้นจากระบบ โดยระบบจะตรวจสอบว่าทรัพยากรที่ถูกร้องขอว่างหรือไม่
5.8 การตรวจจับการติดตาย ระบบต้องมีอัลกอริทึมที่สามารถตรวจสอบภาวะของระบบว่าจะเกิดการติดตายหรือไม่ (การตรวจจับ) อัลกอริทึมที่จะกู้ระบบจากการติดตาย
5.8.1 กรณีที่มี 1 บริการในทรัพยากร 1 ตัว ทุกทรัพยากรสามารถใช้บริการได้เพียง 1 โพรเซส สามารถกำหนดอัลกอริทึมของการตรวจจับการติดตายด้วยการใช้กราฟแสดงทรัพยากรที่เรียกว่ากราฟ Wait-for
-
5.2 การแก้ปัญหาส่วนวิกฤติ
(โพรเซสไม่มีโอกาสได้รับการจัดสรรทรัพยากร) เหตุการณ์นี้คือ การติดตาย โพรเซสทั้งสองจะถูกปฏิเสธให้ทำงาน และหยุดเพื่อรอทรัพยากรของอีกฝ่ายหนึ่งโดยไม่มีวันที่จะได้รับทรัพยากรของอีกฝ่ายเลยซึ่งเหตุการณ์นี้
เองที่เรียกว่า วงจรอับ หรือ Deadlock
5.3 ตัวอย่างของการติดตาย เหตุการณ์ที่มี
รถยนต์ 4 คันแล่นมาจากเส้นทาง 4 เส้นที่แตกต่างกัน
เข้ามาสู่สี่แยกพร้อมกัน ณ เวลาเดียวกัน
5.10 สรุป วงจรอับหรือเรียกกันว่า การติดตาย เป็นปัญหาที่สำคัญสำหรับทุก ๆ ระบบปฏิบัติการ ปัญหานี้จะเกิดขึ้นเมื่อกลุ่มของโพรเซสหลาย ๆ โพรเซสต่างได้รับและกำลังถือครองทรัพยากร และโพรเซสแต่ละ โพรเซสเหล่านี้ต่างต้องการใช้ทรัพยากรที่โพรเซสอื่นในกลุ่มนั้นครองอยู่ดังนั้นโพรเซสภายในกลุ่มนั้นจะถูก
ปฏิเสธให้ทำงาน (Blocked) และไม่มีโพรเซสใดทำงานได้อีกต่อไป