ในระบบคอมพิวเตอร์มีทรัพยากรต่างๆ เชื่อมโยงอยู่มากมาย แต่ ณ เวลาหนึ่งอุปกรณ์แต่ละอย่างจะถูกใช้งานได้จากโปรเซสเพียงโปรเซสเดียวเท่านั้น นอกจากนี้จะพบว่าโปรแกรมประยุกต์ หรือการใช้คอมพิวเตอร์เพื่อการทำงานด้านต่างๆ จะมีความเกี่ยวพันกับทรัพยากรมากกว่า 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/
