วันจันทร์ที่ 24 มกราคม พ.ศ. 2554

การติดตาย deadlock

การติดตาย

          ในระบบคอมพิวเตอร์มีทรัพยากรต่างๆ เชื่อมโยงอยู่มากมาย แต่ ณ เวลาหนึ่งอุปกรณ์แต่ละอย่างจะถูกใช้งานได้จากโปรเซสเพียงโปรเซสเดียวเท่านั้น นอกจากนี้จะพบว่าโปรแกรมประยุกต์ หรือการใช้คอมพิวเตอร์เพื่อการทำงานด้านต่างๆ จะมีความเกี่ยวพันกับทรัพยากรมากกว่า 1 อย่าง เช่น การอ่านข้อมูลจากดิสก์เพื่อส่งไปพิมพ์ที่เครื่องพิมพ์ จะเห็นว่ามีการใช้งานทั้งดิสก์และเครื่องพิมพ์ในเวลาเดียวกัน ซึ่งการทำงานในลักษณะนี้ในระบบโปรแกรมเดียวจะไม่มีปัญหาเกิดขึ้นเนื่องจากมีเพียง
โปรเซสเดียงที่ครองทรัพยากร ไม่มีโปรเซสอื่นมาใช้งานร่วมด้วย แต่ในระบบหลายโปรแกรมปัญหา
จะเกิดขึ้น เช่น มี 2 โปรเซสต้องการที่จะใช้งานเครื่องพิมพ์เพื่อพิมพ์แฟ้มที่เก็บในดิสก์ โดยโปรเซส A ร้องขอการใช้เครื่องพิมพ์และระบบปฏิบัติการมอบเครื่องพิมพ์ให้โปรเซส A แล้ว เมื่อโปรเซส A ได้ครอบเครื่องเครื่องพิมพ์ก็จะติดต่อไปยังดิสก์เพื่ออ่านข้อมูลมาพิมพ์ แต่ในขณะนั้น ดิสก์กำลังถูกครอบ
ครองโดยโปรเซส B ในการอ่านข้อมูลเพื่อมาพิมพ์ที่เครื่องพิมพ์ ดังนั้นโปรเซส A จึงต้องคอยจนกว่า
โปรเซส B จะใช้งานดิสก์เสร็จจึงจะอ่านข้อมูลจากดิสก์ได้ ในขณะที่โปรเซส B จะปลดปล่อยดิสก์ก็ต่อเมื่อได้ครองเครื่องพิมพ์ ซึ่งโปรเซส A กำลังครอบครองอยู่ และจะปลดปล่อยเครื่องพิมพ์ก็ต่อเมื่อได้ครองดิสก์ ซึ่งจะเห็นว่าทั้งสองโปรเซสกำลังคอยซึ่งกันและกัน แต่ไม่มีโปรเซสใดสามารถทำงานต่อได้ เหตุการณ์ลักษณะนี้เรียกว่าการติดตาย (deadlock)
การติดตายสามารถเกิดขึ้นได้จากเหตุการณ์หลายเหตุการณ์ นอกเหนือจากการร้องขอใช้อุปกรณ์ เช่นในระบบฐานข้อมูล หากมีโปรแกรมหนึ่งได้ทำการล็อคระเบียนใกระเบียนหนึ่งไว้เพื่อใช้งานซึ่งเป็นการป้งกันปัญหาการแบ่งกันเข้าใช้ทรัพยากร ซึ่งก็คือระเบียนที่ตนกำลังใช้งานอยู่ เช่น โปรเซส A ทำการล็อคระเบียน R1 และโปรเซส B ทำการล็อคระเบียน R2 และทั้งสองโปรเซสต่างพยายามที่จะล็อคระเบียนของอีกฝ่ายหนึ่งเพื่อใช้งาน ซึ่งการที่จะสามารถล็อคระเบียนใดได้นั้นระเบียนนั้นต้องไม่อยู่ระหว่างการถูกล็อคไว้โดยโปรเซสใด เหตุการณ์ลักษณะนี้จะนำมาซึ่งปัญหาการติดตายเช่นเดียวกัน ดังนั้นจึงสามารถกล่าวได้ว่า การติดตายสามารถเกิดขึ้นได้ทั้งกับทรัพยากรที่เป็นฮาร์ดแวร์ และทรัพยากรที่เป็นซอฟต์แวร์


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

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



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

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

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

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

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

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

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 ใช้งาน


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

       - P1 รอเข้าใช้งานทรัพยากร R1 ในขณะที่ทรัพยากร R1 ให้บริการโพรเซส P2 แล้ว P2 ก็กำลังรอเข้าทำงานทรัพยากร R3 ซึ่งกำลังให้บริการโพรเซส P3 ทรัพยากรR2 กำลังให้บริการทั้งโพรเซส P1 และ P2 ส่วนทรัพยากร 4 ว่างไม่มีเรียกใช้งาน ซึ่งสามารถแทนได้ด้วยลักษณะการเคลื่อนดังนี้

P1 à R1 à P2 à R3 à P3


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


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

1. แน่ใจว่าระบบจะไม่เกิดการติดตายโดยการใช้ Protocol
2. ยอมให้ระบบเข้าสู่การติดตายได้ชั่วคราวแล้วสามารถออกมาได้
3. เมินเฉยทุกอย่าง แล้วอ้างว่าไม่เคยเกิดการติดตายในระบบ วิธีนี้ใช้อยู่ในระบบ Unix

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

No Preemption ถ้าโพรเซสมีการใช้งานทรัพยากรอื่นอยู่ ดังนั้นก็จะไม่สามารถเข้าทำงานในทรัพยากร

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

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

F(tape drive) = 1 , F(disk drive) = 5, F(printer) = 12

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

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

Safe State

เมื่อโพรเซสร้องของทรัพยากรที่มีอยู่ ระบบต้องตัดสินว่าถ้าให้ใช้ทรัพยากรแล้วระบบจะยังคงอยู่ในสถานะที่ปลอดภัยหรือไม่ (Safe state หมายถึงสถานะที่ทรัพยากรสามารถให้บริการได้ทุกโพรเซส) ลักษณะของ Sequence <P1, P2, ...,Pn> จะยังคงดำเนินได้ก็ต่อเมื่อทรัพยากรที่ Pi ขอทำงาน ยังคงทำงานได้อย่างน่าพอใจ ซึ่งจะกำหนดโดยทรัพยากรที่มีในขณะนั้นบวกกับทรัพยากที่ถูกใช้งานอยู่ทั้งหมดของ Pj โดยที่ j < i นั้นหมายถึงถ้าทรัพยากรที่ Pi ต้องการยังไม่ว่างให้ใช้งาน Pi ต้องสามารถรอได้จนกว่า Pj ทำงานเสร็จ แล้วเมื่อ Pj ทำงานเสร็จ Pi สามารถเข้าทำงานทรัพยากรที่ต้องนั้นแล้วก็ออกไปเมื่อใช้งานเสร็จสิ้น เมื่อโพรเซส Pi ทำงานแล้วออกจากทรัพยากรนั้นแล้ว Pi+1 สามารถที่จะใช้งานทรัพยากรนั้นได้ต่อจากนั้น

ดังนั้นความจริงของสถานะที่ปลอดภัยจะไม่เกิดการติดตาย แต่ถ้าเป็นสถานะที่ไม่ปลอดภัยอาจเกิดการติดตายได้ ดังนั้นจึงต้องทำให้ระบบอยู่ในสถานะที่ปลอดภัย และไม่ยอมให้ระบบเข้าสู่ภาวะที่ไม่ปลอดภัยเพื่อหลีกเลี่ยงการติดตาย ตัวอย่างเช่นถ้าระบบมีเทป 12 ตัวและมีโพรเซส P0, P1 และ P2 เมื่อ P0 ต้องการใช้งานเทป 10 ตัว P 2 ต้องการใช้ 4 ตัว P3 ต้องการใช้อีก 9 ตัว สมมติว่าในเวลาที่ t0 โพรเซส 0 กำลังใช้งานเทป 5 ตัวอยู่ โพรเซส 1 ใช้งานอยู่ 2 และโพรเซส 2 ใช้งานอยู่ 2 ดังนั้นจะมีทรัพยากรเทปว่างอยู่อีก 3 ดังนั้นในเวลาที่ t0 ระบบยังอยู่ในภาวะปลอดภัย แต่ก็มีโอกาสที่จะเข้าสู่ภาวะไม่ปลอดภัยได้ สมมติที่เวลา t1 โพรเซส 2 มีการขอใช้งานเทปเพิ่มอีก 4 ตัว หรือมากกว่านั้น ดังนั้นระบบจะอยู่ในภาวะที่ไม่ปลอดภัย ดังนั้นมีเพียงโพรเซส 1 ที่จะช่วยได้คือต้องปล่อยทรัพยากรเทปให้ว่าง เพื่อให้มีทรัพยากรเหลือว่างพอให้โพรเซส 2 ใช้งานได้
อัลกอริทึมการกำหนดทรัพยากรด้วยกราฟ

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

อัลกอริทึมของนายธนาคาร (Banker Algorithm)

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

โครงสร้างของระบบนายธนาคารมีดังนี้ กำหนดให้มี n โพรเซส มีทรัพยากรในระบบทั้งหมด m ตัว

Available : เป็นเวกเตอร์ของขนาดที่ใช้ชี้จำนวนของทรัพยากรที่สามารถใช้งานได้ Available [j]=k ดังนั้น k คือจำนวนที่ทรัพยากรชนิด j จะสามารถให้บริการได้

Max : เป็นค่าเมตริกซ์ขนาด n x m ที่กำหนดความต้องการสูงสุดของแต่ละโพรเซส ถ้า max[i,j] = k แล้วโพรเซส i อาจต้องใช้ทรัพยากร j สูงถึง k บริการ

Allocation เป็นเมตริกซ์ขนาด n x m ที่กำหนดจำนวนของทรัพยากรในแต่ละชนิดที่ให้บริการแต่ละโพรเซสอยู่ได้ ถ้า allocation[i,j] = k หมายถึงโพรเซส i กำลังใช้งานทรัพยากรชนิด j อยู่เป็นจำนวน k บริการ

Need : เมตริกซ์ขนาด n x m เพื่อบ่งบอกจำนวนทรัพยากรที่เหลือที่ยังต้องการใช้ของแต่ละโพรเซส เช่น Need[i,j] = k หมายถึงโพรเซส i ยังคงต้องการใช้งานทรัพยากร j อยู่อีก k บริการ พบกว่า need[i,j] = Max[i,j] – Allocation[i,j]
อัลกอริทึมที่ปลอดภัย

อัลกอริทึมที่หาได้ว่าระบบปลอดภัยหรือไม่ สามารถทำได้ดังนี้

1. กำหนดให้ work และ finish เป็นเวกเตอร์ที่มีขนาด n x m โดยเริ่มทำงานที่ work := available และ finish[i] เป็นเท็จ โดยที่ i มีค่าตั้งแต่ 1, 2 , 3 ... n
2. หาค่า i ทั้ง 2 ฟังกัชัน คือ finish[i] := false , Needi =< Work ถ้าไม่ตามเงื่อนไข ข้ามไปยังขั้นที่ 4
3. Work := Work + allocation, finish[i] := true กลับไปยังขั้นที่ 2
4. ถ้า finish[i] = true สำหรับทุกค่าของ i แล้วระบบจะอยู่ในภาวะปลอดภัย

เวลาในการใช้ทำงานอัลกอริทึมนี้เท่ากับ m x n2
อัลกอริทึมของการขอใช้ทรัพยากร

กำหนดให้ Request i เป็นเวกเตอร์ของการขอใช้งานสำหรับโพรเซส i ถ้า requesti[j] = k หมายถึง

โพรเซส i ต้องการทำงาน k บริการจากทรัพยากร j เมื่อมีการขอใช้งานทรัพยากรโดยโพรเซส i ก็จะเกิดการทำงานดังต่อไปนี้

1. ถ้า Requesti =< Needi ไปยังขั้นตอนที่ 2 นอกจากนั้น ให้แสดงข้อความเตือน เนื่องจากโพรเซสมีการใช้ทรัพยากรมากว่าที่คาดการณ์ไว้
2. ถ้า Requesti =< Available ไปยังขั้นตอนที่ 3 นอกจากนี้โพรเซส i ต้องรอเนื่องจากทรัพยากรไม่มีให้ใช้งาน
3. มีการตั้งระบบลวงเพื่อใช้ทรัพยากรที่โพรเซส i ขอใช้ โดยการใส่ค่าในตัวแปรต่อไปนี้

Available := Available – Request;

Allocationi := Allocationi + Requesti;

Needi := Needi – Requesti;



ถ้าผลของการกำหนดค่าการให้ใช้ทรัพยากรออกมาพบว่าระบบอยู่ในภาวะปลอดภัย ก็จะจบสิ้นการ

ทำงานแล้วยอมให้โพรเซส i ใช้งานทรัพยากรนั้นจริงๆ อย่างไรก็ตามถ้าผลออกมาว่าไม่ปลอดภัย โพรเซส i ต้องรอ Requesti แล้วก็จะกลับไปสู่ค่าสถานะเก่า

     แสดงข้อมูลการใช้งานของระบบพบกว่ามี 5 โพรเซสในการทำงาน P0 – P 4 และมีทรัพยากรให้ใช้งานได้ 3 ตัว คือ A, B และ C ทรัพยากร A มีให้ใช้ได้ถึง 10 ตัว ทรัพยากร B ใช้ได้ถึง 5 ตัว และทรัพยากร C ใช้ได้ถึง 7 ตัว สมมติว่าที่เวลา t0 เกิดเหตุการณ์ดังรูปที่ 5 ดังนั้นจะสามารถหา Need := Max – allocation ดังรูปที่ 6 พบว่าระบบอยู่ในภาวะปลอดภัยแน่นอน และลำดับของความปลอดภัยเป็น <P1,P3,P4,P2,P0>


สมมติให้โพรเซส 1 มีการขอใช้งานทรัพยากรเพิ่ม 1 ตัว ของ A และจากทรัพยากร C อีก 2 ตัว ดังนั้น request1 := (1,0,2) ซึ่งสามารถตรวจสอบได้จาก

Request1 =< Available : (1,0,2) <= (3,3,2) เป็นจริงดังนั้นจึงต้องทำการสร้างระบบจำลองขึ้นมาเพื่อ

ตรวจสอบภาวะของระบบดังรูปที่ 7 หลังจากนั้นไปเข้าไปทำอัลกอริทึมที่ปลอดภัยเพื่อหาลำดับความปลอดภัย และได้ลำดับออกมาดังนี้ <P1, P3, P4, P0, P2> แต่เราพบกว่าถ้าโพรเซส P4 มีการขอใช้ทรัพยากร(3,3,0) จะไม่มีให้ใช้งานได้ และถ้า P0 ขอใช้งาน (0,2,0) ก็จะใช้ไม่ได้เช่นกันเนื่องจากจะทำให้อยู่ในภาวะไม่ปลอดภัย



7.5 การตรวจจับการติดตาย

ระบบต้องมีการจัดการดังต่อนี้

- อัลกอริทึมที่ตรวจสอบภาวะของระบบว่าจะเกิดการติดตายหรือไม่ (การตรวจจับ)

- อัลลกอริทึมที่จะกู้ระบบจากการติดตาย
กรณีที่มี 1 บริการในทรัพยากร 1 ตัว

ถ้าทุกทรัพยากรสามารถใช้บริการได้เพียง 1 โพรเซสแล้วเราสามารถกำหนดอัลกอริทึมของการตรวจจับการติดตายด้วยการใช้กราฟแสดงทรัพยากรที่เรียกว่ากราฟ Wait-for การติดตั้งดูแลการใช้กราฟสามารถทำได้โดยกำหนดให้ โหนดแทนโพรเซส สัญลักษณ์ Pi à Pj หมายถึงโพรเซส i กำลังรอโพรเซส j โดยจะทำการแปลงจากกราฟแทนทรัพยากรเป็น wait-for กราฟที่มีแต่โพรเซส จากนั้นจึงอ้างใช้อัลกอริทึมเพื่อทำการค้นหาตรวจดูว่ากราฟที่ได้เกิดเป็นลูปขึ้นหรือไม่ ซึ่งใช้ order n2 โดยที่ n คือจำนวนของเส้นตรงที่อยู่ในกราฟ
กรณีที่สามารถให้บริการมากกว่า 1 ในทรัพยากร 1 ตัว

ลักษณะจะคล้ายกับอัลกอริทึมของนายธนาคาร โดยมีโครงสร้างดังนี้

Available : เป็นเวกเตอร์ของขนาดที่ใช้ชี้จำนวนของทรัพยากรที่สามารถใช้งานได้

Allocation เป็นเมตริกซ์ขนาด n x m ที่กำหนดจำนวนของทรัพยากรในแต่ละชนิดที่ให้บริการแต่ละโพรเซสอยู่ได้

Request เป็นเวกเตอร์ขนาด n x m เพื่อบ่งบอกการร้องทรัพยากรของแต่ละโพรเซสในขณะนั้น เช่น

Request[i,j] = k หมายถึงโพรเซส i กำลังขอใช้ทรัพยากรจาก j เป็นจำนวน k บริการ

อัลกอริทึมของการตรวจจับมีดังนี้

1. ให้ work และ finish เป็นเวกเตอร์ที่มีขนาด n และ m เริ่มค่าที่ work := available สำหรับทุกค่าของ i ถ้า allocation != 0 แล้ว finish[i] = false นอกนั้นค่า finish[i] = true
2. ทำการหา i ดังต่อไปนี้
- finish[i] := false

- Requesti =< Work
ถ้าไม่เป็นตามนี้ข้อไปข้อ 4
3. Work := Work + Allocation;

Finish[i] := true ;

กลับไปยังข้อ 2

4. ถ้า finish[i] = false สำหรับบางค่าของ i ที่ 1 =< i =< n แล้วระบบจะอยู่ในภาวะการติดตาย ยิ่งกว่านั้นถ้า

finish[i] = false แล้วโพรเซส i จะถูกติดตาย

อัลกอริทึมนี้ใช้เวลาในการทำงาน order = m x n2


             ไม่เกิดการติดตาย เมื่อเราใช้อัลกอริทึมการตรวจจับสามารถได้ลำดับออกเป็น <P0, P2, P3, P1, P4> ที่ทำให้ค่า i เป็นจริงทุกค่า สมมติว่าถ้าให้โพรเซส 2 มีการขอใช้ทรัพยากรเพิ่มอีก 1 ในทรัพยากร C ดังนั้นค่า request จะเป็นไปตามรูปที่ 9 ระบบสามารถเกิดการติดตายแน่นอนเนื่องจากโพรเซส 0 ก็ไม่สามารถปล่อยทรัพยากร C ให้โพรเซส 2 ใช้เนื่องจากโพรเซส 0 ไม่ได้มีการใช้งานทรัพยากร C เลย
การใช้งานอัลกอริทึมตรวจจับ

จะมีการใช้งานอัลกอริทึมก็ต่อเมื่อ

- การติดตายเกิดขึ้นบ่อยอย่างไร

- จะมีโพรเซสจำนวนเท่าไหร่ที่ถูกกระทบเมื่อเกิดการติดตาย

ถ้ามีการใช้อัลกอริทึมตรวจจับในลักษณะวนลูป อาจพบหลายลูปในทรัพยากรกราฟและดังนั้นจะไม่

สามารถบอกได้ว่าโพรเซสใดที่ทำให้เกิดการติดตาย
การกู้คืนจากการเกิดตาย
การกู้คืนด้วยการออกจากระบบ

กำจัดการติดตายด้วยการให้โพรเซสออกจากระบบ ซึ่งมี 2 วิธี

- ให้โพรเซสติดตายออกจากระบบทั้งหมด : วิธีนี้ชัดเจนในการกำจัดการติดตายแต่ผลเสียมีมากเนื่องจากโพรเซสอาจทำงานมาเป็นเวลานานดังนั้นผลลัพธ์ที่ได้ในแต่ละงานของโพรเซสจะหายทั้งหมด ต้องเสียเวลาในการทำงานใหม่ทั้งหมด

- ออกทีละโพรเซสจนกว่าการติดตายจะหายไป : เนื่องจากต้องมีการคิดถึงสิ่งที่สูญเสียไปเมื่อออกจากระบบทั้งหมด ดังนั้นจึงใช้การออกทีละโพรเซสแล้วลูปตรวจจับไปจนกว่าจะไม่พบการติดตาย

ดังนั้นการใช้วิธีการใดต้องคำนึงแล้วเลือกจาก

1. ความสำคัญของโพรเซส

2. โพรเซสนั้นใช้เวลาในการประมวลผลมานานเท่าใด อีกนานเท่าไรจึงจะเสร็จ

3. ทรัพยากรที่โพรเซสนั้นใช้งาน

4. มีกี่โพรเซสที่ต้องถูกออกจากระบบ

5. โพรเซสนั้นเป็นแบบ interactive หรือ bath
วิธีการยึดทรัพยากร

แก้ปัญหาการติดตายด้วยการยึดทรัพยากร จากโพรเซสอื่นเพื่อให้อีกโพรเซสทำงานได้แล้วส่งผลให้ระบบไม่เกิดการติดตาย ดังนั้นจึงต้องพิจารณาเน้นที่จุดต่างๆดังนี้

1. การเลือกทรัพยากรที่จะยึด จะต้องเลือกให้เกิดความเสียหายน้อยที่สุด หมายถึงเลือกทรัพยากรที่จะยึดคืนให้น้อยที่สุด หรือคำนึงถึงเวลาที่จะสามารถแก้ปัญหาได้

2. การย้อนกลับ ต้องพิจารณาด้วยว่าการกลับเริ่มทำงานใหม่ของโพรเซส ดังนั้นต้องมีการเก็บค่าสเตตของโพรเซสที่กำลังทำงานไว้ก่อนเริ่มงานใหม่

3. การอดตาย ต้องให้มั่นใจว่าเมื่อยึดไปแล้วจะไม่เกิดการอดตายเนื่องจากโพรเซสไม่มีโอกาสได้ใช้ทรัพยากรอีกเลย

แหล่งอ้างอิง
http://webcache.googleusercontent.com/

ไม่มีความคิดเห็น:

แสดงความคิดเห็น

แสดงความคิดเห็น