วันพฤหัสบดีที่ 6 มีนาคม พ.ศ. 2551

บทที่4วงจรอับ

วงจรอับ(Deadlock)
ระบบคอมพิวเตอร์โดยทั่วไปนั้นประกอบไปด้วยทรัพยากร หรือ รีซอร์ส (resource) จำนวนมากที่สามารถถูกเรียกใช้งานได้โดยโปรเซล(Process)หนึ่ง ณ เวลาขณะใดขณะหนึ่งเท่านั้น ตัวอย่างที่สามารถมองเห็นได้อย่างชัดเจน ได้แก่ เครื่องพิมพ์ (Printer), ฟลอบบี้ไดรฟ์ (floppy drive) หรือเทปสำรองข้อมูล (tape backup) เป็นต้น ทรัพยากรเหล่านี้จะไม่อนุญาตให้มีโปรเซลมากกว่า 1 โปรเซลเข้ามาใช้พร้อม ๆ กัน เช่น การที่โปรเซล 2 ตัวเข้ามาใช้ระบบไฟล์ เดียวกัน และทำการเขียนหรือเปลี่ยนแปลงระบบไฟล์นั้น พร้อม ๆ กัน อาจจะทำให้ไฟล์นั้นเกิดความเสียหาย หรือสูญเสียได้ ดังนั้นระบบปฏิบัติการที่ดีจะต้องมีความสามารถที่จะหยุดการทำงานของโปรเซลใดๆ เป็นการชั่วคราวได้ ถ้าโปรเซลนั้นพยายามเรียกใช้ทรัพยากรที่กำลังถูกใช้งานอยู่ และทำให้เกิดข้อผิดพลาดดังกล่าว
โปรแกรม หรือแอปพลิเคชันโดยทั่วไปเมื่อทำงาน จะเกิดโปรเซลขึ้นมากมาย และโปรเซลเหล่านี้ส่วนใหญ่ต้องการใช้ทรัพยากรมากกว่า 1 สมมุติว่าการทำงานของโปรแกรมหนึ่ง ทำให้เกิดโปรเซล A และ โปรเซล B เริ่มแรกโปรเซล A ร้องขอใช้เคริ่องสแกนเนอร์ (Scanner) และได้ใช้งาน ส่วนโปรเซล B ถูกโปรแกรมขึ้นมาเพื่อเรียกใช้เครื่องเขียนแผ่นซีดี (CD Writer) ก่อนและได้ใช้งาน ต่อมาโปรเซล A ต้องการใช้เครื่องเขียนแผ่นซืดีบ้าง จึงได้ร้องขอกับระบบ แต่ถูกปฏิเสธจนกว่าโปรเซล B ใช้งานเสร็จ และก็อาจจะเป็นความบังเอิญหรือความโชคร้ายของระบบปฏิบัติการที่โปรเซล B ได้รองขอสแกนเนอร์เพื่อใช้งานพร้อม ๆ กัน ณ จุดนี้เองที่โปรเซลทั้งสองจะถูกปฏิสธให้ทำงานและหยุดเพื่อรอทรัพยากรของอีกฝ่ายหนึ่งโดยไม่มีวันที่จะได้รับทรัพยากรของอีกฝ่ายเลย ดังในรูปที่ 4.1 ซึ่งเหตุการณ์นี้เองที่เรียกว่า วงจรอับ หรือ deadlock
วงจรอับไม่จำเป็นที่จะต้องเกิดขึ้นภายในเครื่องคอมพิวเตอร์เครื่องเดียวเท่านั้น วงจรอับสามารถเกิดข้ามเครื่องได้เช่นกัน เช่น ในระบบเครือข่ายของสำนักงาน (Network) บางครั้งอุปกรณ์ที่เชื่อมต่อกับระบบและสามารถเรียกใช้งานได้โดยผู้ใช้หลาย ๆ คน เช่น เครื่องพิมพ์ เป็นต้น โดยเหตุการณ์และวิธีการป้องกันการเกิดวงจรอับก็จะสลับซับซ้อนและยากขึ้นเป็นลำดับ เมื่อมีอุปกรณ์หรือผู้ใช้เข้าไปเกี่ยวข้องกับระบบมากขึ้น



รูปที่ 4.1 การเกิดวงจรอับโดยโปรเซสทั้งสองต่างก็รอใช้ทรัพยากรของอีกฝ่ายหนึ่ง

4.1 วงจงอับคืออะไร
เราสามารถนิยามวงจรอับ หรือ deadlock ได้ดังนี้
“วงจรอับ คือ กลุ่มของโปรเซสที่ถูกปฎิเสธไม่ให้ทำงาน (blocking) อันมีผลสืบเนื่องมาจากการแย่งชิงกันใช้งานทรัพยากร หรือ การสื่อสาร โดยที่โปรเซสในกลุ่มต่างรอคอยสัญญาณทำงานที่จะเกิดขึ้นได้เฉพาะจากโปรเซสภายในกลุ่มนี้เท่านั้น”
เนื่องจากโปรเซสทั้งหมดจะต้องรอสัญญาณทำงาน และไม่มีโปรเซสใดสามารถส่งสัญญาณทำงานให้กับโปรเซสอื่นภายในกลุ่มได้ ซึ่งจะส่งผลให้โปรเซสทั้งหมดต้องรออย่างไม่มีวันสิ้นสุด โดยในนิยามนี้ สมมุติว่าไม่มีการอินเทอร์รัพต์(Interrupt) ขึ้นในระบบเพื่อที่จะเรียกโปรเซสที่อยู่ในกลุ่มนี้ขึ้นมาทำงานได้ ในกรณีที่เกิดขึ้นโดยทั่วไปนั้น สัญยาณที่แต่ละโปรเซสรอคอยก็คือ สัญญาณการปล่อยทรัพยากรที่สมาชิกของแต่ละโปรเซสภายในกลุ่มใช้อยู่(โดยทรัพยากรนั้นสามารถเป็นได้ทั้งฮาร์ดแวร์หรือซอฟต์แวร์) หรือถ้าจะกล่าวในอีกลักษณะหนึ่งก็คือ สมาชิกของแต่ละโปรเซสในวงจรอับต่างรอคอยทรัพยากรที่ถูกใช้งานโดยโปรเซสที่อยู่ในวงจรอับนั่นเอง ไม่มีโปรเซสใดสามารถทำงานได้ ไม่มีโปรเซสใดปลดปล่อยทรัพยากรที่ตัวเองใช้งานอยู่ และไม่มีโปรเซสใดที่สามารถถูกเรียกออกมากลุ่มได้
วงจรอับโดยส่วนมากนั้นจะเกี่ยวข้องกับความขัดแย้งในการใช้ทรัพยากรของระบบโดย 2 โปรเซส คือ มากกว่า ตัวอย่างง่าย ๆ ที่สามารถแสดงภาพของวงจรอับอยู่ในรูปที่ 4.2 รูปที่ 4.2 แสดงภาพของเหตุการณ์ที่มีรถยนต์ 4 คันแล่นมาจากเส้นทาง 4 เส้นที่แตกต่างกัน เข้ามาสู่สี่แยกพร้อมกัน ณ เวลาเดียวกัน เราสามารถเปรียบเส้นทางทั้งสี่เส้นเป็นทรัพยากรที่ระบบจะต้องควบคุมและถ้ารถยนต์ทั้งสี่ต้องการแล่นตรงไปยังเส้นทางที่อยู่ตรงข้าม ระบบจะต้องทำหน้าที่จัดสรรทรัพยากรดังนี้

รถยนต์ที่วิ่งไปทิศเหนือจะต้องใช้เส้นทางที่ 1 และ 2
รถยนต์ที่วิ่งไปทิศตะวันตกจะต้องใช้เส้นทางที่ 2 และ 3
รถยนต์ที่วิ่งไปทิศใต้จะต้องใช้เส้นทางที่ 3 และ 4
รถยนต์ที่วิ่งไปทิศตะวันออกจะต้องใช้เส้นทางที่ 4 และ 1

รูปที่ 4.2 ตัวอย่างภาพแสดงการเกิดวงจรอับ (Deadlock) [OSID:P254]
โดยปกติเมื่อขับรถเข้าไปในสี่แยก เราจะอนุญาตให้รถที่วิ่งมาทางด้านขวามือไปก่อน ซึ่งกฎดังกล่าวสมารถใช้งานได้ในกรณีที่มีรถเข้ามาจำนวน 2 หรือ 3 ครัน เช่น ถ้ารถที่จะวิ่งไปทิศเหนือมาพร้อมกับรถที่จะวิ่งไปทิศตะวันตกพร้อมกัน รถที่วิ่งไปทิศเหนือจะต้องรอรถที่วิ่งไปทิศตะวันตกไปก่อน อย่างไรก็ตามถ้ารถยนต์ทั้งสี่คันเข้ามาพร้อมกัน แต่ละคันจะต้องรอรถฝั่งขวามือก่อน(ตามกฎที่ตั้งไว้) ซึ่งเป็นการรอในลักษณะวนรอบโดยไม่มีที่สิ้นสุด และก็เกิดวงจรอับขึ้น แต่ถ้ารถทั้งสี่คันไม่ปฎิบัติตามกฎดังกล่าวและแล่นเข้ามาในสี่แยก โดยที่รถแต่ละคันก็จองเส้นทางคนละ 1 เส้น(ดังในรูปที่ 4.2 (ข)) แต่รถทั้งสี่ยังไม่สามารถทำงานต่อไปได้เพราะว่าเส้นทางที่ต้องการอีก 1 เส้น ได้ถูกจองไว้แล้วโดยรถคันอื่น และเราก็เข้าสู่วงจรอับอีกครั้งหนึ่ง

4.2 เงื่อนไขที่ทำให้เกิดวงจรอับ
วงจรอับ เป็นสถานการณ์ที่เราไม่ต้องการให้เกิดขึ้นในระบบ เพราะว่าเมื่อเกิดวงจรอับขึ้นมา จะทำให้ไม่มีโปรเซสใดสามารถทำงานจนเสร็จสมบูรณ์ได้ และทรัพยากรของระบบจะถูกครอบครองจนหมด ดังนั้นก่อนที่เราจะกล่าวลึกลงในรายละเอียดเกี่ยวกับการจัดการกับวงจรอับนั้น เราควรเรียนรู้เกี่ยวกับสาเหตุสำคัญที่ทำให้เกิดวงจรอับก่อน
วงจรอับอาจจะเกิดขึ้นก็ต่อเมื่อเงื่อนไขทั้งสามข้อต่อไปนี้เกิดขึ้น
1. เมื่อมีทรัพยากรที่ไม่สามารถถูกใช้ร่วมกับหลาย ๆ โปรเซสพร้อมกันได้ (Mutual exclusion condition) ถ้ามีทรัพยากรอย่างน้อย 1 ตัวในระบบที่จะยอมให้โปรเซสเพียง 1 ตัว ใช้งานมันได้เท่านั้น นั่นก็คือ ถ้ามีโปรเซสอื่นเข้ามาร้องขอให้ช้งาน โปรเซสนั้นจะต้องรอจนกว่าโปรเซสดังกล่าวได้ใช้งานเสร็จและปล่อยทรัพยากรนั้นว่าง
2. เมื่อมีการถือครองและรอ(Hold and wait condition) ถ้าโปรเซสสามารถถือครองทรพัยากรที่ตัวเองได้รับ และในขณะเดียวกันก็สามารถทำการร้องขอทรัพยากรเพิ่มเติ่มได้
3. เมื่อการทำงานในระบบไม่มีการแทรกกลางคัน (No preemption condition) ถ้าโปรเซสกำลังใช้งานทรัพยากรอยู่ และระบบไม่สามารถบังคับให้โปรเซสนั้นปลดปล่อยทรัพยากรนั้นให้เป็นอิสระได้ โดยทรัพยากรจะเป็นอิสระได้ก็ต่อเมื่อโปรเซสยกเลิกการถือครองเท่านั้น
เงื่อนไขทั้งสามข้อด้านบนนั้นเป็นสิ่งที่ระบบปฎิบัติการทั่วไปต้องการและใช้อยู่ เพื่อให้ระบบ
ทำงานได้อย่างถูกต้อง ตัวอย่างเช่น การที่ทรัพยากรไม่สามารถถูกใช้ร่วมกับหลาย ๆ โปรเซสได้นั้น มีความจำเป็นสำหรับการใช้งานของฐานข้อมูลเพื่อให้เกิดความถูกต้องและตรงกัน เช่นเดียวกับการแทรกกลางคันของระบบนั้น ไม่ควรเกิดขึ้น ถ้าปราศจากเหตุผลอันควร โดยเฉพาะเมื่อระบบทำงานเกี่ยวข้องกับทรัพยากรที่เป็นข้อมูลที่เราต้องการให้ระบบแบ็คอัพข้อมูลเหล่านั้นได้ นั่นคือ ระบบสามารถเรียกโปรเซสและข้อมูลที่เหมาะสมมาใช้ได้อีกเมื่อเกิดการสูญหายของข้อมูล
อย่างไรก็ตาม เงื่อนไขทั้งสามอาจจะทำให้เกิด หรือ ไม่ทำให้เกิดวงจรอับก็ได้ วงจรอับจะ
เกิดขึ้นจริงก็ต่อเมื่อเงื่อนไขที่สีเกิดขึ้น
4. เมื่อเกิดวงจรรอคอย (Circuit wait condition) ถ้าเกิดวงจรลูกโซ่ของโปรเซส 2 ตัว หรือ มากกว่า
ที่ต่างรอคอยทรัพยากรที่ถือครองโดยโปรเซสที่อยู่ในวงจรลูกโซ่นั้น ดังในรูปที่ 4.3

รูปที่ 4.3 วงจรลูกโซ่ของโปรเซสที่ต่างรอคอยซึ่งกันและกัน [OSID:P260]

เงื่อนไขสามข้อแรกนั้นจำเป็น แต่ไม่เพียงพอต่อการทำให้เกิดวงจรอับ เงื่อนที่สี่แท้จริงแล้วเป็นผลที่เกิดจากเงื่อนไขทั้งสามข้อแรก นั่นคือ เมื่อเงื่อนไขทั้งสามข้อแรกเกิดขึ้น ผลที่กิดตามมาอาจจะทำให้เกิดวงจรรอคอย ซึ่งแท้จริงก็คือวงจรอับนั่นเอง วงจรรอคอยในรูปที่ 4.3 เป็นวงจรที่ระบบไม่สามารถแก้ได้ เพราะเงื่อนไขทั้งสามข้อแรกบังคับอยู่ ดังนั้นเงื่อนไขทั้งสี่ข้อจะต้องสมบูรณ์จึงจะทำให้เกิดวงจรอับได้
แผนภาพแสดงของวงจรอับ
เงื่อนไขของวงจรอับทั้งสี่ข้อตามที่ได้กล่าวไปแล้วในหัวข้อที่ผ่านมานั้น เราสามารถอธิบายโดย
ใช้แผนภาพ หรือ กราฟของการจัดสรรทรัพยากรได้ (directed graph) กราฟดังกล่าวประกอบไปด้วยโหนด 2 ประเภท คือ 1 โหนดโปรเซสแสดงเป็นรูปวงกลม และ 2 โหนดทรัพยากรที่แสดงเป็นรูปสี่เหลี่ยม
o ลูกศรจากโหนดทรัพยากรชี้ไปหาโหนดโปรเซส หมายถึง ทรัพยากรนั้นได้ถูกร้องขอและโปรเซสนั้น ก็ได้ใช้ไปแล้ว และกำลังถือครองอยู่ ในรูปที่ 4.4(ก๗ ทรัพยากร R ในขณะนั้นถูกโปรเซส A ถือครองอยู่
o ลูกศรจากโหนดโปรเซสชี้ไปหาโหนดทรัพยากร หมายถึง โปรเซสในขณะนั้นกำลังรอคอยทรัพยากรนั้นอยู่ ในรูปที่ 4.4(ข๗ โปรเซส B กำลังรอทรัพยากร S
ในรูปที่ 4.4 (ค) จะเห็นได้ว่ามีวงจรอับเกิดขึ้น โปรเซส C กำลังรอคอยที่จะใช้ทรัพยากร T ซึ่ง
ในขณะนั้นก็ถูกถือครองโดยโปรเซส D โปรเซส D เองไม่สามารถปล่อยทรัพยากร T ได้ เพราะว่าตัวเองก็กำลังรอคอยทรัพยากร U ที่ถือครองโดยโปรเซส C เช่นกัน โปรเซสทั้งสองก็จะรอคอยอย่างไม่มีที่สิ้นสุด แผนภาพวงกลมในกราฟแสดงว่า วงจรอับนั้นเกี่ยวข้องกับโปรเซสและทรัพยากรที่มีเส้นกราฟต่อกันเป็นลูกโซ่ โดยจากตัวอย่างในรูปนั้น คือ วงจร C-T-D-U- C



รูปที่ 4.4 กราฟการจัดการสรรทรัพยากร การถือครองทรัพยากร (ข) การรอคอยทรัพยากร (ค) วงจรอับ [MOS:P165]
ลองเจาะลึกเข้าไปดูตัวอย่างการใช้งานกราฟการจัดสรรทรัพยากรว่า เราจะสามารถนำไปใช้ประโยชน์
ได้อย่างไรบ้าง สมมุติว่า ในระบบมีโปรเซส 3 ตัว คือ A,B และ C และทรัพยากร 3 ตัว คือ R,S และ T การร้องขอและการปล่อยทรัพยากรของทั้งสามโปรเซสแสดงในรูปที่ 4.5(ก) ถึง (ค) ระบบปฎิบัติการมีอิสระในการอนุญาตเสร็จ ให้โปรเซสใดทำงานหรือป้องกันไม่ให้โปรเซสใดทำงานก็ได้ โดยอาจจะเริ่มจากให้ A ทำงานจนกว่า A จะทำงานเสร็จ และจึงให้ B ทำงานจนเสร็จ แล้ว C จึงทำงานต่อ ลักษณะการกำหนดให้โปรเซสทำงานดังกล่าวจะไม่ทำให้เกิดวงจรอับอย่างแน่นอน เพราะไม่มีการแข่งขันในการใช้ทรัพยากรร่วมกับโปรเซสอื่น ขอยกตัวอย่างการร้องขอ และการปล่อยทรัพยากรเป็นโปรเซสที่ทำการคำนวณแล้วจึงแสดงผล เมื่อโปรเซสทำงานแบบเป็นลำดับ ในขณะที่โปรเซสหนึ่งกำลังรอที่จะแสดงผล จะเป็นไปไม่ได้ที่จะมีโปรเซสอื่นเข้ามาใช้งานซีพียูไปทำการคำนวณ ซึ่งการทำงานแบบนี้จะทำให้ระบบทำงานล่าช้าและไม่มีประสิทธิภาพ อย่างไรก็ตามการทำงานแบบเป็นลำดับก็มีผลดีเหมือนกัน ในกรณีที่ไม่มีโปรเซสใดเลยทำการแสดงผลอยู่ เราก็ควรให้โปรเซสที่สั้นที่สุดทำงานก่อน (shortest job first) ซึ่งจะทำให้ระบบทำงานได้ดีกว่าที่เราจะกำหนดให้โปรเซสมีการทำงานแบบหมุนเวียนกันไป (round robin)
คราวนี้เรามาลองกำหนดให้โปรเซสสามารถทำการคำนวณและแสดงผลพร้อมกันได้ การ
จัดการตารางทำงานที่เหมาะสมควรเป็นการทำงานแบบหมุนเวียนกันไป หรือ round robin นั่นเอง ทรัพยากรอาจจะถูกร้องของดังในรูปที่ 4.5 (ง) ถ้าการร้องขอทรัพยากรทั้ง 6 ครั้งนั้นเกิดขึ้นดังแสดงในรูปที่ 4.5 (จ) –(ญ) หลังจากการร้องขอครั้งที่ 4 เกิดขึ้นโปรเซส A จะถูกบังคับให้รอทรัพยากร S ดังในรูปที่ 4.5 (ซ) และการร้องขอ 2 ครั้งถัดไป โปรเซส B และ C ก็จะถูกบังคับให้รอเช่นกัน ซึ่งทำให้เกิดวงจรลูกโซ่แห่งการรอคอย และเกิดวงจรอับในที่สุด อย่างไรก็ตามระบบปฎิบัติการไม่จำเป็นต้องให้โปรเซสทำงานอย่างเป็นลำดับดังกล่าวก็ได้ ระบบปฎิบัติการเพียงระงับไม่ให้โปรเซสร้องขอทรัพยากรจนกว่าระบบจะอยู่ในสถานะที่ปลอดภัย ในรูปที่ 4.5 ถ้าระบบปฎิบัติการทราบว่าวงจรอับอาจจะเกิดขึ้น ระบบอาจจะระงับไม่ให้โปรเซส B ได้รับทรัพยากร S และให้เพียงโปรเซส A และ C ทำงานก่อน โดยเราจะได้ลำดับของการร้องขอและการปล่อยทรัพยากรดังในรูปที่ 4.5 (ฎ) และลำดับการทำงานของโปรเซสก็สามารถแสดงได้ในรูปที่ 4.5(ฏ)-(ด) ซึ่งทำให้ไม่เกิดวงจรอับขึ้นมาในระบบ และหลังจากโปรเซส A ปลดปล่อยทรัพยกร S ในรูปที่ 4.5(ด) โปรเซส B ก็สามารถใช้ทรัพยากร S ได้เนื่องจาก โปรเซส A ได้ทำงานเสร็จเรียบร้อย และโปรเซส C ก็ได้รับทรัพยากรที่ต้องการไปเรียบร้อยแล้ว ถึงแม้นว่าโปรเซส B จะถูกระงับการใช้งานทรัพยากร T วงจรอับก็จะไม่มีทางเกิดขึ้น เพราะ B เพียงแต่รอให้โปรเซส C ทำงานเสร็จเท่านั้นเอง
ในส่วนนี้อธิบายขึ้นมาเพื่อให้เราทราบถึงประโยชน์ของการนำเอากราฟการจัดสรรทรัพยากร
มาใช้เป็นเครื่องมื่อเพื่อให้เรามองเห็นภาพลำดับการร้องขอและการปลดปล่อยทรัพยากรอย่างเป็นขั้นตอน และในแต่ละขั้นตอนก็ทำการตรวจสอบว่ามีเส้นกราฟที่ทำให้เกิดเป็นวงจรลูกโซ่หรือไม่ ถ้ามีวงจรอับก็จะเกิดขึ้นในระบบ แต่ถ้าไม่มี วงจรอับก็จะไม่เกิดขึ้น
ถึงแม้นว่าในตัวอย่างที่ผ่านมา เราได้เรียนรู้การทำงานาของกราฟการจัดสรรทรัพยากรใน
ลักษณะที่ทรัพยากรแต่ละชนิดมีทรัพยากรเพียง 1 ตัว (Single resource for each type) แต่กราฟนี้สามารถใช้งานในกรณีที่ทรัพยากรแต่ละชนิดมีทรัพยากรหลาย ๆ ตัวก็ได้เช่นกัน หลังจากนี้เราจะเรียนรู้ถึงวิธีการป้องกันไม่ให้ระบบเกิดวงจรอับ ซึ่งโดยทั่วไปแล้ว การจัดการวงจรอับนั้นมีกลยุทธอยู่ 4 วิธี ที่สามารถนำมาใช้ได้คือ
o ทำการป้องกันไว้ก่อน โดยไม่ให้หนึ่งในเงื่อนไขทั้งสี่ข้อของการทำให้เกิดวงจรอับเกิดขึ้น
o ทำการหลีกเลี่ยง โดยการจัดสรรทรัพยากรให้ถูกต้อง
o การตควจพบและแก้ไขคืน เราจะอนุญาตให้วงจรอับเกิดขึ้น และเราค่อยทำการเช็คหาและแก้ไขมัน
o ไม่ต้องสนใจปัญหาใด ๆ เลย ในบางครั้งถ้าเราไม่สนใจปัญหาที่จะเกิดขึ้น ปัญหาก็อาจจะไม่เกิดขึ้น กับคุณก็ได้
เราจะพิจารณาการจัดการกับวงจรอับในแต่ละกลยุทธในรายละเอียดในหัวข้อต่อ ๆ ไป


รูป 4.5 ตัวอย่างการเกิด/หลีกเลี่ยงวงจรอับ แสดงจากกราฟการจัดสรรทรัพยากร [MOS:P166]
การป้องกันการเกิดวงจรอับ (Protection)
วิธีการป้องกันการเกิดวงจรอับ (deadlock prevention) นั้นอาจจะกล่าวได้ง่าย ๆ โดยการออกแบบให้
ระบบมีการป้องกันการเกิดวงจรอับไว้ก่อน จากที่เราได้กล่าวมาในหัวข้อที่ 4.2 เกี่ยวกับเงื่อนไขที่ทำให้เกิดวงจรอับ จะเห็นว่าการป้องกันการเกิดวงจรอับสามารถแบ่งได้เป็น 2 กลุ่ม คือ 1. การป้องกันการเกิดวงจรอับทางอ้อม คือ การป้องกันการเกิดเงื่อนไขสามข้อแรกที่อาจจะทำให้เกิดวงจรอับได้ และ 2 ที่ว่าเงื่อนไขทั้งสี่ข้อจะต้องเกิดขึ้นพร้อมกันจึงจะทำให้เกิดวงจรอับได้ ดังนั้น ถ้าป้องกันไม่ให้เงื่อนไขใดเงื่อนไขหนึ่งเกิดขึ้น เราก็จะสามารถป้องกันการเกิดวงจรอับได้ โดยจะพิจารณาในแต่ละเงื่อนไขดังต่อไปนี้
4.4.1 การใช้ทรัพยากรร่วมกันได้(Mutual exclusion prevention)
ปัญหาในข้อนี้คือ การที่ทรัพยากรในระบบไม่อนุญาตให้โปรเซสหลาย ๆ โปรเซสใช้งานพร้อม ๆ กัน
ได้ ดังนั้นการแก้ปัญหาข้อนี้ ระบบปฎิบัติการจะต้องจัดการให้โปรเซสในระบบสามารถใช้งานทรัพยากรเหล่านั้นร่วมกันได้ ตัวอย่างของทรัพยากรบางประเภท เช่น ไฟล์ข้อมูล ระบบปฎิบัติการอาจจะอนุญาตให้โปรเซสหลาย ๆ โปรเซสเข้าถึงไฟล์ข้อมูลนั้นได้ โดยมีการกำหนดให้มีการเข้าถึงเป็นแบบอ่านได้อย่างเดียว (read only) ก็จะทำให้ไฟล์นั้นสามารถใช้งานร่วมกันได้ และ อนุญาตให้โปรเซสเพียงโปรเซสเดียวเท่านั้นที่ทำการเขียนได้ อย่างไรก็ตาม การป้องกันการเกิดวงจรอับในระบบโดยใช้วิธีนี้ไม่สามารถทำได้เสมอไป เพราะว่ายังมีทรัพยากรบางตัวที่ไม่สามารถใช้งานร่วมกันกับหลาย ๆ โปรเซสพร้อมกันได้ เช่น เครื่องพิมพ์ เป็นต้น (แต่เราก็อาจจะใช้วิธีสพูลลิ่ง (Spooling) เข้า มาช่วยในการจัดการได้ โดยใช้พื้นที่ดิสก์เป็นตัวรับเอาต์พุตแทนเครื่องพิมพ์ แล้วค่อยส่งข้อมูลไปให้เครื่องพิมพ์ ซึ่งวิธีนี้จะทำให้โปรเซสหลาย ๆ ตัวสามารถใช้เครื่องพิมพ์นี้กได้)
4.4.2 การป้องกันการถือครองและรอคอย (Hold and wait prevention)
เงื่อนไขของการถือครองและรอคอยนั้นสามารถป้องกันได้ โดยเราจะอนุญาตให้โปรเซสร้องขอ
ทรัพยากรที่ต้องการทั้งหมดก่อน และจะไม่อนุญาตให้โปรเซสนั้นทำงานจนกว่าจะได้รับทรัพยากรที่ร้องขอไปพร้อมกันทั้งหมดก่อน อย่างไรก็ตาม วิธีการป้องกันแบบนี้จะทำให้ระบบปฎิบัติการทำงานอย่างไม่มีประสิทธิภาพ เพราะอย่างแรกโปรเซสจะต้องถือครองทรัพยากรเป็นเวลานานในขณะที่รอให้ตัวเองได้รับทรัพยากรทั้งหมดก่อนจึงจะทำงานได้ทั้ง ๆ ที่โปรเซสเหล่านั้นเพียงได้รับทรัพยากรบางตัวก็สามารถทำงานก่อนได้เลย อย่างที่สองบางทรัพยากรที่ถูกครอบครองโดยโปรเซสอาจจะยังไม่ได้ถูกใช้งาน และโปรเซสอื่นก้ไม่สามารถเรียกนำไปใช้ได้ด้วย
อย่างไรก็ตามในทางปฏิบัติ เราสามารถพบปัญหาที่ไม่สามารถแก้ไขได้ เช่น ในกรณีที่เราใช้โปรแกรมที่มีโปรแกรมย่อย ๆ หลาย โปรแกรม หรือ โปรแกรมที่มีโครงสร้างที่สามารถทำงานหลาย ๆ อย่างพร้อมกันได้(Multithreaded structure) โปรแกรมเหล่านี้จะต้องทำการตรวจสอบด้วยว่าถ้ามีการร้องขอทรัพยากรจากโปรแกรมย่อย ๆ ภายในพร้อมกัน ทรัพยากรทั้งหมดภายในระบบจะเพียงพอหรือไม่ มิฉะนั้นวงจรอับก็จะเกิดขึ้นได้เช่นกัน
4.4.3 ยอมให้มีการแทรกกลางคัน (Preemptable)
เงื่อนไขนี้เราสามารถทำการป้องกันได้หลาย ๆ วิธี อย่างแรกคือ ถ้าโปรเซสกำลังถือครองทรัพยากร
หนึ่งอยู่ เราจะให้ระบบป้องกันไม่ให้โปรเซสนั้นทำการร้องขอทรัพยากรอื่นใดอีก จนกว่าโปรเซสนั้นจะปลดปล่อยทรัพยากรที่ตัวเองครอบครองเสียก่อน และในบางกรณีถ้าโปรเซสต้องการทรัพยากรเพิ่ม ระบบอาจจะกำหนดให้โปรเซสปล่อยทรัพยากรที่ตัวเองครอบครองอยู่ก่อน และค่อยทำการ้องขอทรัพยากรเหล่านั้นอีกครั้งพร้อมกับ ทรัพยากรที่ต้องการเพิ่มเติม หรือในอีกวิธีหนึ่ง ถ้าโปรเซสต้องการทรัพยากรที่ขณะนั้นถูกถือครองโดยโปรเซสอื่น ระบบปฎิบัติการอาจจะทำการแทรกการทำงานของโปรเซสที่สองและให้โปรเซสนั้นปลดปล่อยทรัพยากร วิธีการที่สองจะป้องกันการเกิดวงจรอับได้ก็ต่อเมื่อ โปรเซสทั้งสองมีสิทธิและความสำคัญที่แตกต่างกัน
4.4.4 การป้องกันการเกิดวงจรรอคอย(Circular wait protection)
การป้องกันสามารถทำได้โดยกำหนดลำดับของทรัพยากรทั้งหมดในระบบ และกำหนดให้โปรเซส
ต้องร้องขอใช้ทรัพยากรเรียงตามลำดับนี้ เช่น ถ้าโปรเซสกำลังถือครองทรัพยากร S อยู่ และต่อมาโปรเซสนี้ได้ทำการร้องขอทรัพยากร ซึ่งระบบจะอนุญาตให้โปรเซสนั้นร้องขอได้เฉพาะทรัพยากรที่อยู่ในลำดับที่สูงกว่า S
เพื่อให้เรามองเห็นภาพที่ชัดเจนขึ้น เราจะกำหนดให้ทรัพยากร Ri มาก่อน Rj ในลำดับของเงื่อนไขที่ว่า I < j และลองพิจารณาโปรเซส A และ B ที่จะทำให้เกิดวงจรอับ โดยวงจรอับจะเกิดขึ้นก็ต่อเมื่อ A กำลังถือครองRi และ ทำการร้องขอ Rj และ B ก็กำลังถือครอง Rj และทำการร้องขอ Ri ซึ่งมีความเป็นไปไม่ได้เพราะว่าเกิดความขัดแย้งในข้อกำหนดที่เราได้ตั้งไว้ก่อนหน้าคือ i < j แต่ถ้า B ทำการร้องขอ Ri ได้ก็หมายความว่า j < I ซึ่งถ้าระบบปฎิบัติการทำตามข้อกำหนดก็จะทำไม่ให้เกิดวงจรรอคอยดังกล่าว โปรดสังเกตว่าการกำหนดค่าเลขลำดับของทรัพยากรนั้น ควรเรียงตามลำดับการใช้งานของระบบตามปกติ เช่น ปกติเราจะใช้ไฟล์ข้อมูลก่อนเครื่องพิมพ์เสมอ ระบบก็ควรจะกำหนดลำดับของไฟล์ข้อมูล < ลำดับของเครื่องพิมพ์
อย่างไรก็ตามการป้องกันวิธีนี้จะส่งผลให้การทำงานของระบบปฎิบัติการไร้ประสิทธิภาพเช่นเดียวกับการป้องกันการถือครองและรอคอย(Hold and wait) โดยจะทำให้การประมวลผลช้าลงและมีการปฎิเสธการใช้งานของทรัพยาการโดยไม่มีความจำเป็น
จากการป้องกันการเกิดวงจรอับตามที่ได้กล่าวมาแล้วข้างต้นเราสามารถสรุปได้เป็น
เงื่อนไข วิธีการ
การใช้ทรัพยากรร่วมกันไม่ได้
การถือครองและรอคอย
การไม่การแทรกกลางคัน
การเกิดวงจรรอคอย ให้ใช้ทรัพยากรที่สามารถใช้ร่วมกันได้ เช่น ดิสก์ในการจัดการสพูลลิ่ง
ให้โปรเซสร้องขอทรัพยากรทั้งหมดก่อน
ให้ระบบสามารถแทรกการทำงานและเรียกคืนทรัพยากรได้
จัดเรียงและใช้ทรัพยากรอย่างเป็นลำดับ
การหลีกเลี่ยงการเกิดวงจรอับ (Avoidance)
ในหัวข้อ 4.4 ที่ผ่านมา เสนอการป้องกันการเกิดวงจรอับขึ้นมาในระบบ โดยสร้างข้อกำหนดของการร้อง
ขอทรัพยากร เพื่อให้แน่ใจว่าเงื่อนไขเพียงข้อใดข้อหนึ่งที่เป็นสิ่งจำเป็นในการเกิดกวงจรอับจะไม่เกิดขึ้นอย่างแน่นอน แต่การกำหนดเหล่านั้นอาจจะมีผลกระทบต่อการทำงาานของระบบได้ เช่น การใช้งานทรัพยากร หรือการทำงานของโปรเซสในระบบจะมีประสิทธิภาพต่ำลง
อีกทางเลือกหนึ่งที่จะทำให้ระบบสามารถหลีกเลี่ยงการเกิดวงจรอับได้ โดยอนุญาตให้เงื่อนไขสามข้อแรก
สามารถเกิดขึ้นได้ แต่จะให้ระบบใช้วิจารณญาณในการเลือกที่จะไม่ทำให้เกิดวงจรอับขึ้นมา กล่าวคือ ระบบจะต้องมีความสามารถในการตัดสินใจว่า ในการที่โปรเซสร้องขอทรัพยากรหนึ่ง ๆ นั้นจะทำให้ระบบปลอดภัยหรือไม่ และจะอนุญาตให้โปรเซสนั้นได้รับทรัพยากรถ้าระบบปลอดภัยเท่านั้น ดังนั้น จึงมีคำถามตามมาว่า มีวิธีการคิดใด หรือไม่ที่เราจะสามารถหลีกเลี่ยงวงจรอับได้ โดยทำการเลือกตัวเลือกที่ถูกต้องทุกครั้ง ถ้ามีคำตอบที่บอกว่า “ใช่ไ เราก็สามารถหลีกเลี่ยงวงจรอับได้ แต่ก่อนที่ระบบจะเลือกตัวเลือกที่ถูกต้องได้นั้น ข้อมูลทั้งหมดของระบบจะต้องถูกจัดเตรียมไว้ก่อนแล้ว
4.5.1 แนวเส้นของการใช้ทรัพยากร
วิธีการคิด หรืออัลกอริทึ่มขงการหลีกเลี่ยงการเกิดวงจรอับวิธีนี้มีพื้นฐานอยู่บนแนวความคิดของการที่เรา
ต้องการให้ระบบอยู่ในสถานะที่ปลอดภัย(safe state) และก่อนที่เราจะเรียนรู้ในรายละเอียดของวิธีการคิดแบบนี้ แผนภาพจะถูกใช้เพื่อแสดงแนวความคิดของคำว่า “อยู่ในสถานะที่ปลอดภัย” ถึงแม้ว่า ในบางครั้งการใช้แผนภาพจะไม่สามารถสื่อความหมายโดยตรงเกี่ยวกับการใช้อัลกอริทึ่มนี้ก็ตาม แต่มันก็สามารถทำให้เราเข้าใจ ความหมายของปัญหาและหนทางแก้ไขได้มากขึ้น


รูปที่ 4.6 ตารางการใช้ทรัพยากรของโปรเซส 2 ตัว [MOS:P176]

ในรูปที่ 4.6 จะแสดงให้เห็นถึงรูปแบบของการจัดการวงจรอับที่เกิดจากโปรเซส 2 ตัว และทรัพยากร 2 ตัว
ตัวอย่างเช่น เครื่องพิมพ์ 1 เครื่อง และเครื่องพล็อตเตอร์ 1 เครื่อง จากกราฟในแนวนอนแสดงถึงจำนวนคำสั่งที่เรียกใช้โดยโปรเซส A ส่วนกราฟในแนวตั้งจะแสดงถึงจำนวนคำสั่งที่เรียกใช้โดยโปรเซส B ณ จุด l1 โปรเซส A ได้ร้องขอที่จะใช้เครื่องพิมพ์ และที่จุด l 2 ก็ต้องการใช้เครื่องพล็อตเตอร์ด้วยเช่นกัน จากนั้นเครื่องพิมพ์แลเครื่องพล็อตเตอร์จะถูกปล่อยคืนสู่ระบบ ณ จุด l3 และ l4 ตามลำดับ ส่วนโปรเซส B ก็ต้องการเครื่องพล็อตเตอร์จาก l5 ถึง l7 และต้องการเครื่องพิมพ์จาก l6 ถึง l8 ทุก ๆ จุดบนแผนภาพจะแสดงถึงสถานะความสัมพันธ์ของทั้งสองโปรเซส เริ่มต้นจากจุด p ในแผนภาพ ณ จุดนี้จะไม่มีโปรเซสใดได้เรียกใช้คำสั่งใด ๆ เลย และถ้าระบบกำหนดให้โปรเซส A เริ่มทำงานก่อน เราก็จะมาอยู่ที่จุด q ที่ซึ่ง A ได้เรียกใช้คำสั่งบางคำสั่งแต่ B ยังไม่ได้เรียกใช้อะไรเลย ที่จุด q เส้นกรากฟเดินทางในแนวตั้ง ซึ่งแสดงว่าระบบเริ่มกำหนดตารางให้ B ทำงาน ถ้าในระบบที่มีตัวประมวลผลเพียง 1 ตัว แนวเส้นจะอยู่ในแนวนอนหรือแนวตั้งเท่านั้นและจะไม่มีเส้นทะแยงมุมเป็นอันขาด นอกจากนี้ทิศทางการเดินก็จะอยู่ในทิศเหนือ หรือทิศตะวันออกเท่านั้น(โปรเซสไม่สามารถทำงานย้อนกลับได้) ส่วนพื้นที่แรเงาก็จะแสดงถึงพื้นที่ที่โปรเซสทั้งสองใช้งานทรัพยากรเดียวกัน โดยพื้นที่แรเงาจากด้านล่างซ้ายไปฝั่งบนขวาแทนการใช้งานเครื่องพิมพ์พร้อมกัน และพื้นที่แรเงาในด้านตรงกันข้ามแทนการใช้งานเครื่องพล็อตเตอร์พร้อมกัน อย่างไรก็ตามโดยเงื่อนไขของการใช้ทรัพยากรร่วมกันไม่ได้ หรือ Mutual exclusive นั้นทำให้แนวเส้นการใช้ทรัพยากรไม่สามารถเดินทางเข้าไปในพื้นที่เหล่านี้ได้
เราจะเริ่มพิจารณาแนวเส้นในแผนภาพกันต่อ โดยเมื่อโปรเซส A ได้เดินไปในแนวทางจาก r ถึง s โปรเซส A ได้ร้องขอและได้ใช้งานเครื่องพิมพ์แล้ว เช่นเดียวกันเมื่อถึงจุด t โปรเซส B ก็ทำการร้องขอใช้เครื่องพล็อตเตอร์ หลังจากจุด t ถ้าแนวเส้นการใช้ทรัพยากรเข้าไปในกรอบระหว่าง l1, l2 และ l5,l6 ก็จะทำให้เกิดวงจรอับขึ้นในระบบ เมื่อแนวเส้นเดินทางไปถึงจุดตัดระหว่าง l2 และ l6 ณ จุดนั้น A จะร้องขอใช้เครื่องพล็อตเตอร์ และ B ก็ร้องขอใช้เครื่องพิมพ์ แต่ทรัพยากรทั้งคู่ก็ถูกครอบครองอยู่ ดังนั้นพื้นที่ของกรอบดังกล่าวจะแทนสถานที่ไม่ปลอดภัย (unsafe sate) และเราไม่ควรให้แนวเส้นการใช้ทรัพยากรเดินเข้าไป ณ จุด t การทำงานที่ปลอดภัยก็คือ ให้โปรเซส A ทำงานจนถึงจุด l4 และหลังจากนั้นแนวเส้นก็สามารถเดินไปถึงจุด u ได้
ข้อคิดที่สำคัญที่เราควรมองเห็นคือ ณ จุด t โปรเซส B กำลังร้องขอใช้ทรัพยากร ระบบจะต้องตัดสินใจว่าจะให้ทรัพยากรกับโปรเซสหรือไม่ ถ้าให้ไป ระบบก็จะเจ้าสู่สถานะทีไม่ปลอดภัยและก็อาจจะเกิดวงจรอับในที่สุด ถ้าจะหลีกเลี่ยงวงจรอับ B จะต้องถูกระงับไม่ให้ทำงานจนกระทั่ง A ได้ใช้งานและปลดปล่อยเครื่องพล็อตเตอร์กลับคืนสู่ระบบเรียบร้อยแล้ว
จะเห็นได้ว่าการหลีกเลี่ยงไม่ให้เกิดวงจรอับขึ้นมาในระบบนั้น ระบบจำเป็นต้องรู้ความต้องการทรัพยากร ทั้งหมดของโปรเซสที่เกิดขึ้นในอนาคตก่อนเสมอ และเราสามารถหลีกเลี่ยงวงจรอับได้โดย
1. ไม่อนุญาตให้โปรเซสทำงานถ้าทรัพยากรที่ร้องขออาจทำให้เกิดวงจรอับได้
2. ไม่อนุญาตให้ทรัพยากรเพิ่มแก่โปรเซสที่ร้องขอ ถ้าการครอบครองของโปรเซสอาจทำให้เกิดวงจรอับได้
4.5.2 การปฏิเสธให้โปรเซสทำงาน
ให้เราลองพิจารณาระบบที่มีโปรเซส n ตัว และมีทรัพยากรต่างชนิดกัน m ตัวให้เรานิยมเวกเตอร์และแมตทริกซ์ ของทรัพยากรได้ดังนี้
Resource = (R1,R2,…,Rm) จำนวนทรัพยากรแต่ละชนิดทั้งหมดในระบบ
Available = (V1,V2,…,Vm) จำนวนทรัพยากรทั้งหมดที่ไม่ได้ถูกครอบครอง

Claim = ความต้องการทรัพยากรแต่ละชนิดของแต่ละโปรเซส
Allocation = ทรัพยากรแต่ละชนิดที่ถูกครอบครองโดยแต่ละโปรเซส

แมตทริกซ์ Claim แสดงถึงความต้องการทรัพยากรแต่ละชนิดสูงสุดของแต่ละโปรเซส โดยให้แต่ละแถวแทนโปรเซส 1 ตัว นั่นคือ

Cij = จำนวนทรัพยากร j ที่โปรเซส i ต้องการ
และข้อมูลดังกล่าวจะต้องทำการประกาศก่อนหน้าขั้นตอนที่ใช้ในการหลีกเลี่ยงวงจรอับทำงานได้ และเช่นเดียวกับ A=จำนวนทรัพยากร j ที่ถูกครอบครองโดยโปรเซส i นอกจากนี้ความสัมพันธ์ต่างๆจะต้องเป็นไปตามข้อมูลด้านล่างนี้
1.Ri = Vi+Aki สำหรับทุกๆค่าของ I; ทรัพยากรทั้งหมดเท่ากับทรัพยากรที่ว่างบวกกับที่ถูก
ครอบคองอยู่
2.Cki ≤ Ri สำหรับทุกคำสั่งของ k,I; ไม่มีโปรเซสใดที่สามารถร้องขอมากได้กว่าจำนวน
ทรัพยากรที่มีอยู่ทั้งหมด
3. Aki ≤ Cki สำหรับทุกค่าของ k,I; ไม่มีโปรเซสใดที่สามารถครอบครองทรัพยากรมากกว่า
ที่ตัวเองร้องขอในตอนแรก
จากข้อกำหนดด้านบน เราสามารถกำหนดนโยบายของการหลีหเลี่ยงวงจรอับได้ว่า เราไม่อนุญาตให้โปรเซสใดทำงาน ถ้าความต้องการทรัพยากรของโปรเซสนั้นจะนำพาระบบเข้าสู่วงจรอับได้ นั่นคือ เราจะเริ่มโปรเซสPn+1ใหม่ก็ต่อเมื่อ
Ri > = C(n+1) I + Cki สำหรับทุกค่าของ i
นั่นคือโปรเซสหนึ่งจะสามารถทำงานได้ก็ต่อเมื่อ จำนวนทรัพยากรแต่ละชนิดที่โปรเซสต้องการทั้งหมดรวมกับ จำนวนทรัพยากรแต่ละชนิดที่โปรเซสใหม่ต้องการ จะต้องไม่เกินจำนวนทรัพยากร
ที่มีอยู่ในระบบทั้งหมด อย่างไรก็ตามวิธีนี้อาจจะทำให้การทำงานไม่มีประสิทธิภาพมากหนัก เพราะโปรเซสทั้งหมดจะต้องทำการร้องขอทรัพยากรสูงสุดก่อน
4.5.3การปฏิเสธไม่ให้ครอบครองทรัพยากร
วิธีการครอบครองทรัพยากร หรือที่เรารู้จักกันดีในชื่อของ “วิธีการทำงานของนายธนาคาร”
(Banker’s Algorithm)ซึ่งหมายถึงเป็นการแก้ปัญหาของธนาคารในกรณีที่มีลูกค้าต้องการกู้ยืมเงินซึ่งมีลักษณะการทำงานเหมือนโปรเซสที่ใช้ทรัพยากรในระบบปฏิบัติการทั่วๆไป (ลูกค้าเปรียบเสมือนโปรเซส และเงินที่ถูกยืมเปรียบเสมือนทรัพยากร) จากวิธีการทำงานของธนาคารนั้น ธนาคารจะมีจำนวนเงินที่ให้ลูกค้ากู้ยืมที่จำกัด และก็มีรายชื่อของลูกค้าพร้อมกับเครดิตที่แต่ละตนจะได้รับ ลูกค้าบางคนอาจจะพยายามกู้เงินให้ได้เต็มเครดิตที่ตัวเองมี และบางครั้งลูกค้าคนนั้นก็ไม่ยอมจ่ายเงินคืนกลับให้ธนาคารจนกว่าจะได้รับจำนวนเงินที่ต้องการกู้ยืมทั้งหมด แต่นายธนาคารเองก็สามารถปฏิเสธการกู้ยืมของลูกค้าบางคนได้ ถ้าการปล่อยกู้ยืมครั้งนั้นจะทำให้เกิดความเสี่ยงทำให้ธนาคารมีเงินไม่เพียงพอที่จะให้ผู้นั้นได้กู้ยืมเพิ่มเติม และลูกค้าคนนั้นก็ไม่สามารถใช้เงินคืนแก่ธนาคารได้ รายละเอียดของการทำงานแบบนายธนาคารกับระบบที่มีทรัพยากรเพียง1ตัวจะอธิบายดังด้านล่างนี้ ส่วนการจัดการกับระบบที่มีทรัพยากรหลายๆตัวนั้นเราจะอธิบายในรายละเอียดในหัวข้อต่อไปนี้
จากในหัวข้อที่4.5.2 ณ เวลาใดก็ตาม สถานะของระบบขึ้นอยู่กับค่าของ R ,V,C และ A และสถานะของระบบจะปลอดภัยเมื่อไม่มีวงจรอับเกิดขึ้น ดังนั้นเราต้องจัดลำดับการทำงานให้กับทุกๆโปรเซสให้สามารถทำงานจนเสร็จสิ้นสมบูรณ์ ถึงแม้ว่าโปรเซสทั้งหมดำด้ร้องขอทรัพยากรตามโควต้าสูงสุดที่ได้รับพร้อมกัน เราจะใช้แผนภาพในรูปที่4.7 แสดงตัวอย่างของการจัดการใช้ทรัพยากร1ตัวโดยรูป4.7 (ก) โปรเซส A ได้รับทรัพยากรนั้นมา 3 ตัว แต่ต้องการทั้งหมด 9 ตัว, B ได้รับ 2 ตัว และต้องการทั้งหมด 4 ตัว เช่นเดียวกับ C ได้รับ 2 ตัว แต่ต้องการเพิ่มอีก 5 ตัว (ต้องการทั้งหมด 7ตัว) สมมุติว่าทรัพยากรนี้ 10 ตัว ในระบบแลโปรเซสได้ถือครองไปแล้ว 7 ตัวจึงเหลืออีก 3 ตัว

รูปที่4.7การแสดงของสถานะทำงานที่ปลอดภัย[MOS:P177]
สถานะของรูป4.7 (ก) นั้นปลอดภัย เพราะว่าเราสามารถกำหนดลำดับการครอบครองทรัพยากรของ โปรเซสแต่ละชนิดให้สามารถทำงานจนเสร็จสมบูรณ์ ได้ โดยเราอาจจะกำหนดการทำงานได้ดังนี้
• ให้โปรเซส B ทำงานก่อน เสร็จโดยให้ทรัพยากรเพิ่ม 2 ตัว ดังรูป4.7 (ข)
• เมื่อ B ทำงานจนเสร็จ B ก็จะคืนทรัพยากรกลับสู่ระบบ ดังรูป 4.7(ค)
• กำหนดให้ C ทำงานโดยให้ทรัพยากรเพิ่มดังรูป4.7 (ง)
• เมื่อ C ทำงานจนเสร็จสมบูรณ์แล้ว เราก็จะได้ผลดังในรูปที่4.7(จ) ซึ่ง ณ จุดนี้ A ก็สามารถใช้ทรัพยากรเพิ่มและทำงานจนเสร็จสมบูรณ์ได้
เราจะเห็นได้ว่าระบบของรูปที่ 4.7นั้น อยู่ในสถานะที่ปลอดภัย เพราะว่าระบบได้กำหนดการทำงานของโปรเซสได้อย่างถูกต้องและสมารถหลีกเลี่ยงวงจรอับได้



รูป4.8การแสดงของสถานะทำงานที่ไม่ปลอดภัย[MOS:P177]
คราวนี้เรามาลองพิจารณาตัวอย่างอีกตัวอย่างหน฿งกันในรูป4.8(ก)แต่คราวนี้โปรเซสA ได้รับขอและได้รับทรัพยากรเพิ่มมาอีก 1 ตัว ดังในรูปที่4.8(ข)ระบบจะสามารถหาหนทางที่จะทำให้โปรเซสแต่ละอันทำงานจนเสร็จสมบูรณ์ได้หรือไม่ โดยทดลองให้B ทำงานโดยทำการให้ทรัพยากรเพิ่มเติมกับ B ดังในรูปที่4.8(ค)และในที่สุดB ก็จะทำงานเสร็จและคืนทรัพยากรกลับสู่ระบบดังรูปที่4.8(ง) ณ จุดนี้ระบบมีทรัพยากรเหลือ4ตัวแต่โปรเซสที่เหลือต่างต้องการทรัพยากรอย่างน้อย5ตัว จึงจะสามารถทำงานได้ ดังนั้นการที่ระบบตัดสินใจให้ทรัพยากรจากรูปที่4.8(ก)ไปสู่รูปที่4.8(ข)เป็นการตักสินใจที่นำพาระบบเข้าสู่สถานะที่ไม่ปลอดภัย และแม้นระบบจะให้โปรเซสAหรือCทำงานหลังจากนั้นก็ไม่ส่งผลสำเร็จทั้งคู่ ดังนั้น ถ้าเราพิจารณาย้อนกลับไป ระบบควรปฏิเสธการร้องขอของโปรเซสA
แต่อย่างไรก็ตามเมื่อระบบเข้าสู่สถานะที่ไม่ปลอดภัยก็ไม่ได้หมายความว่า ระบบจะเข้าสู่วงจรอับเสมอถ้าพิจารณากลับไปที่รูป 4.8(ข) ระบบสามารถทำงานได้สักระยะหนึ่ง ซึ่งก็ทำโปรเซสB ทำงานจนเสร็จและนอกจากนี้ มันก็มีความเป็นไปได้ว่า A อาจจะทำการปล่อยทรัพยากรมาสัก1ตัวก่อนทำการร้องขอทรัพยากรเพิ่มซึ่งก็ทำให้C ทำงานจนสำเร็จและวงจรอับก็ไม่เกิดขึ้นในระบบ ดังนั้นข้อแตกต่างของสถานะที่ปลอดภัยและสถานะที่ไม่ปลอดภัยก็คือ ในสถานะที่ปลอดภัย เราสามารถทำการยืนยันว่าโปรเซสทุกตัวในระบบจะทำงานเสร็จสิ้นสมบูรณ์และไม่เกิดวงจรอับ แต่ในสถานะที่ไม่ปลอดภัยนั้นเราไม่สามารถทำการยืนยันได้เท่านั้นเอง ซึ่งวงจรอับอาจจะเกิดขึ้นก็ได้ในระบบ ดังแสดงในแผนภาพในรูปที่ 4.9

รูป 4.9 เซ็ตในระบบที่แทนสถานะที่ปลอดภัย,สถานะที่ไม่ปลอดภัย และการเกิดวงจรอับ[OSC6:P254]
4.5.4 วิธีการทำงานแบบนายธนาคารสำหรับระบบที่มีทรัพยากรหลายตัว


รูปที่ 4.10 หารใช้ banker’s algorithm กับระบบบมีทรัพยกรหลายตัว[MOS:P179]
วิธีการทำงานแบบนายธนาคารสามารถจัดการกับระบบที่มีทรัพยากรหลายๆ ตัว โดยแมทริกซ์ด้านซ้ายแสดงถึงจำนวนทรัพยากรแต่ละชนิดที่ถูกกระบวนทั้ง5ตัวครอบครองในขณะนั้นและแมทริกซ์
ด้านขวามือแสดงถึงจำนวนทรัพยากรที่แต่ละโปรเซสต้องการเพิ่มเติมเพื่อให้สามารถทำงานจนเสร็จสมบูรณ์ได้ แมทริกซ์เหล่านี้แสดงถึงตัวแปร A และ C ตามลำดับ เช่นเดียวกับการพิจารณาทรัพยากรตัวเดียว โปรเซสทุกตัวต้องทำการประกาศทรัพยากรทั้งหมดที่ต้องการ (C) ก่อนที่ระบบจะเริ่มทำงานได้ ดังนั้นแมทริกซ์ด้านขวามือก็คือจำนวนทรัพยากรที่ต้องการทั้งหมดของแต่ละกระบวน ณ ขณะใดขณะหนึ่งนั่นเอง
ส่วนเวกเตอร์สามตัวทางด้านขวามือแสดงถึงจำนวนทรัพยากรทั้งหมด R จำนวนทรัพยากรที่ถูกครอบครองขณะนั้น P และ จำนวนทรัพยากรแต่ละชนิดที่ยังคงว่างอยู่ V ตามลำดับ จากเวกเตอร์ R เราจะเห็นว่าในระบบ มีเทปบันทึกข้อมูล 6 ตัวพล็อตเตอร์ 3 ตัวและเครื่องพิมพ์ 4 ตัวและไดร์ซีดีรอม 2 ตัวจากจำนวนเหล่านี้ มีทรัพยากรที่ถูกใช้ไปแล้ว คือ เทปบันทึกข้อมูล 5 ตัวพล็ตเตอร์ 3 ตัว เครื่องพิมพ์ 2 ตัว และไดร์ซีดีรอม 2 ตัว โดยสามารถคำนวณได้จากผลรวมของแต่คอลัมน์ของแมทริกซ์ทางด้านซ้ายมือ(A)และเวกเตอร์V คือผลต่างของทรัพยากรที่ถูกครอบครองไปแล้วนั่นเอง (R-P)
วิธีการคิดที่ใช้ตรวจสอบดูว่าระบบอยู่ในสถานะที่ปลอดภัยหรือไม่ ทำได้โดย
1.เริ่มตรวจสอบที่แถว ของโปรเซสในตารางแมทริกซ์ C ให้ดูว่าแถวไหนบ้างที่มีจำนวนทรัพยากรแต่ละตัวที่ต้องการน้อยกว่าหรือเท่ากับเวกเตอ์ V หรือไม่ ถ้าไม่มีแสดงว่าวงจรเข้าสู่ระบบวงอับเรียบร้อยแล้ว เพราะว่าไม่มีโปรเซสใดที่สามารถทำงานได้สำเร็จ
2.สมมุติว่ามีอยู่ 1 แถว ที่สามารถได้รับทรัพยากรแต่ละตัวที่ต้องการทั้งหมด (อย่างเช่น โปรเซส D ) และทำงานได้ ให้เราทำเครื่องหมายว่าโปรเซสนั้นทำงานจนเสร็จสิ้น และส่งคืนทรัพยากรเข้าสู่ระบบโดยทำการบวกทรัพยากรที่โปรเซสนั้นได้รับกลับสู่เวกเตอร์ V
3.ทำข้อ 1 และข้อ 2 ซ้ำ จนกระทั่งทุกๆ โปรเซสทำงานเสร็จเรียบร้อย โดยทุกงานสามารถทำงานได้เสร็จก็หมายความว่าระบบอยู่ในสถานะที่ปลอดภัย แต่ถ้ามีวงจรอับเกิดขึ้นดังอธิบายในข้อ 1 ก็หมายความว่าระบบไม่อยู่ในความปลอดภัยแน่นอน
เราลองกลับไปพิจารณารูป4.10 เป็นตัวอย่างจะเห็นว่า สถานะของระบบนั้นปลอดภัย ถึงแม้นว่าโปรเซส B จะร้องขอใช้เครื่องพิมพ์เพิ่ม ระบบก็สามารถให้ได้เพราะว่าระบบก็ยังอยู่ในสถานะที่ปลอดภัย ก็คือ โปรเซส D สามารถทำงานให้แล้วเสร็จได้ จากนั้น ก็ให้โปรเซส A หรือ E ทำงาน และให้โปรเซสที่เหลือทำหลังจากนั้น (เช่น D,A,E,B,และ C)
แต่อีกกรณีหนึ่ง หลังจากที่ B ได้รับ 1 ใน 2 เครื่องพิมพ์ที่เหลือ, E ก็ต้องการเครื่องพิมพ์เครื่องสุดท้ายนั้น ถ้าระบบให้เครื่องพิมพ์ไปตามคำร้องขอ เวกเตอร์ V ก็จะเหลือค่า [1000] ซึ่งทำให้เกิดวงจรอับ ดังนั้นระบบจะต้องปฏิเสธการร้องขอของ E จนกว่าระบบจะออกจากสถานะที่ไม่ปลอดภัย
ถึงแม้ว่าขั้นตอนและวิธีการทำงานแบบนี้จะดีอย่างไรก็ตาม ในระบบปฏิบัติการคอมพิวเตอร์จริง ๆ นั้นการใช้วิธีการแบบนี้เป็นไปได้ยากมาก เพราะการที่โปรเซสต่าง ๆ จะรู้ล่วงหน้าถึงจำนวนทรัพยากรที่ตัวเองต้องการก่อนทำงานนั่นมีความเป็นไปได้น้อยมากหรือแทบไม่มีเลย และจำนวนของโปรเซสก็ไม่คงที่ด้วย เช่น ในกรณีที่มีผู้ใช้ใหม่ ๆ เข้ามา หรือออกไปจากระบบ หรือทรัพยากรบางอย่างที่ระบบคิดว่ามีอยู่แต่พอใช้งานจริง ๆ อาจจะสูญหายหรือเสียไปก็ได้ เช่น ดิสก์เสียโดยกระทันหัน (damaged sector)
4.6วิธีการตรวจสอบและกู้คืนเมื่อเกิดวงจรอับ
วิธีการป้องกันการเกิดวงจรอับที่ผ่านมานั้นค่อนข้างส่งผลให้ระบบทำงานอย่างไม่เต็มประสิทธิภาพส่วนมากจะแก้ปัญหาโดยการจำกัดสิทธิในการใช้งานทรัพยากร หรือ โดยการกำหนดข้อห้ามกับโปรเซสที่ต้องการทำงาน แต่การจัดการวงจรอับที่เราจะศึกษาในหัวข้อนี้จะมีวิธีการที่ตรงกันข้ามกับที่เคยกล่าวมาแล้ว คือการตรวจสอบและกู้คืนจะไม่จำกัดสิทธิใด ๆ ในการใช้งานทรัพยากร หรือกำหนดข้อบังคับแก่โปรเซสแต่อย่างไร วิธีการนี้โปรเซสที่ร้องขอทรัพยากรจะได้รับทรัพยากรนั้นเสมอถ้าเป็นไปได้ แต่ระบบจะต้องมีวิธีการที่สามารถทำการตรวจสอบได้ว่ามีวงจรรอคอยเกิดขึ้นมาในระบบหรือไม่ ถ้ามีก็ต้องทำการแก้ไขหรือกู้คืนระบบให้อยู่ในสภาวะปกติต่อไป
4.6.1.ขั้นตอนของการตรวจหาวงจรอับ
การตรวจสอบว่าเกิดวงจรอับเกิดหรือไม่ เราสามารถทำได้ทุกครั้งที่ทรัพยากรในระบบถูกร้องขอ หรือจะทำน้อยครั้งกว่านั้นก็ได้ขึ้นอยู่กับว่าในระบบนั้นมีความน่าจะเป็นที่จะเกิดวงจรอับมากน้อยเพียงใด การตรวจสอบระบบทุกครั้งที่มีการร้องขอทรัพยากร มีข้อดีอยู่2ข้อคือ 1.เราสามารถตรวจพบวงจรอับได้เร็ว และ 2.เราสามารถกำหนดเวลาทำงานได้ง่าย แต่ในทางตรงข้ามกันการตรวจสอบระบบบ่อยครั้งก็เป็นการเปลืองเวลาของตัวประมวลผลในการทำงานเช่นกัน
ตัวอย่างของอัลกอริทึ่มที่ใช้ในการตรวจสอบสามารถอธิบายได้โดยใช้แมตทริกซ์ที่ได้เคยกล่าวไว้ในหัวข้อ4.5.2 นอกเหนือจากแมตทริกซ์จำนวนของทรัพยากรแต่ละชนิดที่๔กครอบครอง (Allocation) และเวกเตอร์จำนวนของทรัพยากรที่เหลืด (Available) ที่เราจะนำมาใช้แล้ว ยังมีแมตทริกซ์Q ที่เรานิยามให้ qij แทนจจำนวนทรัพยากรชนิด j ที่ถูกร้องขอโดยโปรเซส i อัลกอริทึมนี้ทำงานได้โดยอาศัยหลักการทำเครื่องหมายให้กับโปรเซสที่ไม่อยู่ในวงจรอับดังนี้
1.แรกเริ่มโปรเซสทั้งหมดจะไม่มีเครื่องหมายใดๆ
2.จากนั้นทำเครื่องหมายบนโปรเซสทุกตัวที่มีค่าของแถวใน A เป็นศูนย์หมด
3.สร้างเวกเตอร์ชั่วคราว W ให้มีค่าเท่ากับเวกเตอร์ V
4.ค้นหาตำแหน่งแถว i โดยที่โปรเซส i จะต้องไม่ถูกทำเครื่องหมายแล้ว และแถวที่ i ของ Q มีค่า
น้อยกว่าหรือเท่ากับ W นั่นคือ Qik<=Wk, สำหรับทุกค่าของ 1<=k <=m ถ้าไม่พบแถวตามที่
กำหนดให้หยุดการทำงาน
5.ถ้าพบแถวที่ตรงตามเงื่อนไข ให้ทำเครื่องหมายที่โปรเซส i และเพิ่มค่าของ W โดยการบวกเพิ่ม
ค่าของแถวที่ตรงกันในแมตทริกซ์ A นั่นคือให้ Wk =Wk + Aik
วงจรอับจะเกิดขึ้นก็ต่อเมื่อมีโปรเซสที่ไม่ถูกทำเครื่องหมายเมื่อจบการทำงาน และโปรเซสที่ไม่มีเครื่องหมายนั้นก็อยู่ในวงจรอับนั่นเอง วิธีการคิดแบบนี้สร้างขึ้นเพื่อค้นหาโปรเซสที่ร้องขอทรัพยากรที่ระบบสามารถให้ได้ และเมื่อให้ทรัพยากรแล้วโปนรเซสนั้นสามารถทำงานจนจบและคืนทรัพยากรกลับสู่ระบบ
พึ่งสังเกตว่าวิธีการแบบนี้จะไม่มีการป้องกันการเกิดวงจรอับเลย เพราะการเกิดวงจรอับขึ้นอยู่กับลำดับของการให้ทรัพยากรแก่โปรเซสที่ร้องขออีกที ขั้นตอนที่กล่าวมาข้างต้นเป็นเพียงการตรวจหาว่าเกิดวงจรอับขึ้นในระบบหรือไม่เท่านั้น

รูป4.11 ตัวอย่างของวิธีการตรวจหาวงจรอับ[OSID:P268]
เรามาทดลองดูตัวอย่างดังรูปที่4.11ซึ่งจะแสดงวิธีการตรวจหาวงจรอับได้ดังนี้
1.ทำเครื่องหมายที่กระบวน P4เพราะว่า P4 ไม่มีทรัพยากรในครอบครองเลย
2.กำหนดให้ W=[00001](เท่ากับ เวกเตอร์ aVailable)
3.ทรัพยากรที่โปรเซส P3 ต้องการนั้นน้อยกว่าหรือเท่ากับ W ดังนั้น ให้ทำเครื่องหมายที่ P3 และเพิ่มค่า W =W + [00010]=[00011]
4.ออกจากการตรวจสอบ
จะเห็นว่าผลการตรวจสอบจบลงตรงที่ P1 และ P2 ไม่ถูกทำเครื่องหมายใด ๆ ซึ่งเป็นตัวบอกว่าวงจรอับจะเกิดขึ้นกับโปรเซสเหล่านี้
2.การกู้คืนระบบ
1.ยกเลิกการทำงานของแต่ละโปรเซสที่เกิดวงจรอับทีละตัว จนกว่าไม่มีวงจรอับเกิดขึ้นในระบบ โดยลำดับของโปรเซสที่ถูกเลือกให้ยกเลิกนั้นควรเลือกตามเกณฑ์ที่จะทำให้ระบบสูญเสียน้อยที่สุดโดยสามารถใช้หลักเกณฑ์
- เลือกโปรเซสที่ได้ใช้เวลาของตัวประมวลผลไปแล้วน้อยที่สุด
- เลือกโปรเซสที่ได้ให้ผลลัพธ์ หรือเอาต์พุตออกมาแล้วน้อยที่สุด
- เลือกโปรเซสที่ได้ครอบครองทรัพยากรไปแล้วน้อยที่สุด
- เลือกโปรเซสที่มีลำดับความสำคัญ หรือ priority น้อยที่สุด
- เลือกโปรเซสที่ยังต้องการเวลาในการทำงานมากที่สุด
2.ทำการแทรกและเรียกทรัพยากรคืนจากกระบวนที่ละตัวจนกว่าจะวงจรอับจะหายไป การเลือกโปรเซสที่จะถูกแทรกมีหลักเกณฑ์เช่นเดียวกับข้อ 2 ส่วนโปรเซสที่ถูกแทรกจะต้องกลับไปเริ่มต้นใหม่ตั้งแต่จากเริ่มร้องขอทรัพยากรใหม่เลย
3.ยกเลิกการทำงานของทุกโปรเซสที่เกิดวงจรอับ (Abort ALL) ซึ่งเป็นหนึ่งในหลาย ๆ วิธีที่ระบบปฏิบัติทั่ว ๆ ไปใช้อยู่
4.ทำการสำรองข้อมูลของทุก ๆ โปรเซสที่เกิดวงจรอับไปยังจุดที่ทำการตรวจสอบก่อนหน้านี้ และให้โปรเซสทั้งหมดเริ่มทำงานใหม่ (Restart) อย่างไรก็ตาม การจะใช้วิธีการนี้ระบบจะต้องมีความสามารถในการย้อนกลับและเริ่มทำงานใหม่ได้ (Rollback and Restart) แต่ข้อด้อยของวิธีการนี้ก็คือ วงจรอับเดิมอาจจะเกิดขึ้นในระบบอีกก็ได้
4.7การที่ไม่ต้องสนใจอะไรเลย
วิธีการนี้ในต่างประเทศเรียกกันว่า วิธีการคิดแบบนกกระจองเทศ (Ostrich algorithm) ซึ่งมีความหมายมาจากลักษณะของนกกระจอกเทศที่เอาหัวมุดทรายและแกล้งทำเป็นไม่สนใจสิ่งที่เกิดขึ้น
ดังนั้นหลักการของวิธีการนี้ก็มีวิธีการใช้ของแต่ละคนที่ไม่เหมือนกัน นักคณิตศาสตร์อาจจะบอกว่าเขาไม่ยอมรับวธีการนี้ เพราะเขาต้องการป้องกันการเกิดวงจรอับ ถึงแม้ว่าจะต้องสูญเสียอะไรไปก็ตาม วิศวกรอาจถามปัญหาวงจรอับเกิดขึ้นบ่อยครั้งเพียงใด การที่ระบบล่มเพราะเหตุนี้บ่อยครั้งแค่ไหน และอาจจะทำให้เกิดความเสียหายรุนแรงมากหรือไม่ ถ้าวงจรอับเกิดขึ้นโดยเฉลี่ย1ครั้งในรอบ4ปีแต่ระบบกลับล่มเนื่องจาก ฮาร์ดแวร์เสีย การประมวลผลผิดพลาด ไวรัส และเกิดข้อผิดพลาดในตัวระบบปฏิบัติการเองทุกๆสัปดาห์ วิศวกรนั้นคงไม่มานั่งเสียเวลาในการจัดการกับการเกิดวงจรอับ การอธิบายข้อแตกต่างนี้ให้เห็นภาพชัดเจนได้นั้น ให้เราลองพิจารณาถึงระบบจริงๆ ที่อาจจะเกิดมีวงจรอับขึ้นมา แต่ไม่สามารถตรวจพบเจอได้เลยเป็นต้น
ระบบปฏิบัติการส่วนใหญ่ รวมทั้งUnix หรือ Windows นั้นจะไม่ค่อยสนใจปัญหาเหล่านี้มากนัก โดยเขาได้ตั้งสมมุติฐานเอาเองว่าผู้ใช้ หรือUser ส่วนใหญ่ต้องการให้เกิดวงจรอับขึ้นมาในระบบบ้าง เพื่อเป็นการห้ามไม่ให้ผู้ใช้หลายคนเรียกใช้โปรเซสเดียวกัน เปิดไฟล์เดียวกันหรือใช้อะไรอย่างดอย่างหนึ่งพร้อมกัน ถ้าการจัดการกับวงจรอับนั้นง่ายและระบบไม่ต้องสูญเสียอะไรมากนัก เราก็คงไม่ต้องกล่าวในรายละเอียด ร่วมถึงวิธีแก้ไขกันมาถึงเพียงนี้ แต่ปัญหาก็อยู่ที่ว่าสิ่งที่ต้องสูญเสียนั้นมีมาก โดยเฉพาะอย่างยิ่งข้อจำกัดต่างๆ ที่เกิดขึ้นกับโปรเซสที่จะต้องทำงาน และก็ทำให้เราต้องเผชิญอยู่กับสิ่งที่ไม่พึ่งปรารถนาระหว่างความถูกต้อง กับ ความสะดวกสบายและการพิจารณาว่าสิ่งใดนั้นสำคัญกว่ากัน ซึ่งการหาคำตอบที่มีเหตุผลของคำถามเหล่านี้คงเป็นไปแบบไม่ง่ายนัก
4.8สรุปวิธีการจัดการกับวงจรอับ
จากตารางที่4.2เป็นวิธีการจัดการกับวงจรอับแบบต่างๆ พร้อมทั้งแสดงถึงข้อดีและข้อเสียของแต่ละวิธี ในการออกแบบระบบปฏิบัติการนั้น เราควรนำวิธีการหลายๆวิธีมารวมกันเพื่อให้ระบบมีประสิทธิภาพในการจัดการกับเหตุการณ์ที่แตกต่างกันได้
เป็นที่ทราบกันดีว่า ไม่มีวิธีการใดวิธีเดียวที่จะเหมาะสมกับการจัดการปัญหาวงจรอับในระบบย่อยต่างๆของระบบปฏิบัติการได้ ไม่ว่าจะเป็น วิธีการป้องกัน วิธีการตรวจสอบและกู้คืน หรือวิธีการหลีกเลี่ยง เราจึงอาจต้องใช้หลายๆวิธีผสมกัน โดยเลือกวิธีที่เหมาะสมกับลักษณะของระบบย่อยนั้นๆ เราอาจเริ่มต้นได้จากการแบ่งทรัพยากรเป็ยพวกๆ และจัดเรียงตามความสำคัญ เพื่อที่เราจะได้ศึกษาหาวิธีการที่เหมาะสมที่สุดให้แต่ละกลุ่มของทรัพยากร ตัวอย่างของวิธีการแบ่งกลุ่มนั้น ให้เราพิจารณาระบบที่ประกอบไปด้วยกลุ่มของทรัพยากร 4 กลุ่มดังนี้
1.ทรัพยากรชั้นในของระบบ เป็นทรัพยากรที่ใช้โดยระบบ เช่นตัวควบคุมโปรเซส(Process control
block)
2.หน่วยความจำหลัก เป็นหน่วยความจำที่ใช้งานโดย ผู้ใช้
3.อุปกรณ์ต่างๆได้แก่อุปกรณ์ที่ต่อพ่วงเช่นCD-ROMไดว์หรืออุปกรณ์ทางตรรกเช่นไฟล์ก็ได้
4.หน่วยความจำสำรอง ได้แก่พื้นที่สำรองข้อมูลของผู้ใช้ในงานแต่ละคน เช่น ฮาร์ดดิกสก์
เราสามารถจัดการปัญหาวงจรอับในระบบนี้ โดยจัดแบ่งกลุ่มของทรัพยากรเป็น4กลุ่มตามที่กล่าวมาแล้วนั้น ในแต่ละกลุ่มอาจจะใช้วิธีจัดการดังนี้
1. ทรัพยากรชั้นในระบบ เราสามารถป้องกันได้โดยใช้การจัดลำดับของทรัพยากร เพราะโปรเซสที่ร้องขอเป็นโปรเซสภายในระบบของระบบเอง จึงต้องการให้ทรัพยากรกับระบบที่ร้องขอเร็วที่สุด
2. หน่วยความจำหลัก สามารถป้องกันโดยใช้วิธ๊แทรกกลางคันได้ เนื่องจากงานแต่ละงานแต่ละตัวสามารถย้ายออกจากหน่วยความจำหลัก เข้าไปเก็บไว้ในหน่วยความจำสำรองได้ง่าย
3. อุปกรณ์ต่างๆ สามารถป้องกันโดยใช้วิธีหลีกเลี่ยงได้ เพราะข้อมูลเกี่ยวกับ จำนวนทรัพยากรที่ร้องขอสูงสุดของแต่ละโปรเซสนั้น ระบบอาจจะรู้ล่วงหน้าได้ เช่น จากการ์ดควบคุมการทำงาน
4. หน่วยความจำสำรอง สามารถป้องกันได้โดยใช้วิธีการจัดสรรทรัพยากรไว้ล่วงหน้า เนื่องจากจำนวนหน่วยความจำสำรองสูงสุดของแต่ละงานมักจะถูกกำหนดไว้ล่วงหน้าอยู่แล้ว
จากตัวอย่างที่ได้กล่าวมา แสดงให้เห็นถึงแนวทางการจัดการกับปัญหาวงจรอับโดยใช้หลายๆวิธีผสมกันโดยเริ่มจากแบ่งกลุ่มของทรัพยากรออกเป็นพวกๆและเลือกหาวิธีที่เหมาะสมและส่งผลให้เกิดประสิทธิภาพสูงสุดให้กับงานแต่ละกลุ่ม


วิธีการจัดการ นโยบายการครอบครองทรัพยากร วิธีการจัดการแบบต่างๆ ข้อดี ข้อเสีย
การป้องกัน(Prevention) นโยบายค่อนข้างเข้มงวด เช่นจำกัดการใช้งานทรัพยากร •จัดลำดับการใช้งานทรัพยากร(Spooling)
•ให้โปรเซสร้องขอทรัพยากรทั้งหมดก่อนถึงเริ่มทำงาน
•การแทรกกลางคันได้ •ระบบไม่จำเป็นต้องจัดการขณะเครื่องทำงาน(run-time)เพราะปัญหาได้ถูกแก้เมื่อตอนออกแบบระบบแล้ว
•ทำงานได้ดีสำหรับโปรเซสที่มีการทำงานอย่างหนักเป็นช่วงๆ(bursting)
•เหมาะที่จะใช้กับทรัพยากรที่สามารถสำรองข้อมูลและกู้คืนได้ง่าย •ปฏิเสธการให้ทรัพยากรกับโปรเซส
•ไม่มีประสิทธิภาพ
•การทำงานของโปปรเซสเริ่มได้ช้าลง
•การแทรกกลางคันทำให้การทำงานไม่ต่อเนื่องและบางครั้งก็ไม่จำเป็น
การตรวจสอบและกู้คืน(Detection) นโยบายค่อนข้างเสรีทรัพยากรที่โปรเซสร้องขอสามารถได้รับได้เลย และค่อยทำการตรวจหาวงจรอับ •ทำการตรวจหาวงจรอับเป็นช่วงๆของเวลา •ไม่มีการชะลอเวลาเริ่มทำงานของโปรเซส
•เป็นเครื่องที่ใช้ในการจัดการแบบออนไลน์(online) •อาจจะมีการแทรกการทำงาน
•หรือโปรเซสต้องเริ่มทำงานใหม่ทั้งหมด
การหลีกเลี่ยง(Avoidance) เป็นนโยบายที่เป็นกลางระหว่างวิธีการทั้งสอง •พยายามทำให้ระบบอยู่ในสถานะปลอดภัย •ไม่มีการแทรกกลางคัน •จัต้องรู้จำนวนทรัพยากรที่ต้องการทั้งหมดก่อน
•โปรเซสอาจจะถูกปฏิเสธไม่ให้ทำงานเป็นเวลานานได้

ตารางที่ 4.2 สรุปวิธีการจัดการกับวงจรอับที่ใช้สำหรับระบบปฏิบัติการ
4.9สรุป
วงจรอับหรือ deadlock เป็นปัญหาที่สำคัญสำหรับทุกๆระบบปฏิบัติการ ปัญหานี้จะเกิดขึ้นเมื่อกลุ่มของโปรเซสหลายๆตัวต่างได้รับและกำลังถือครองทรัพยากร และโปรเซสแต่ละตัวเหล่านี้ต่างก้ต้องการใช้ทรัพยากรที่โปรเซสอื่นในกลุ่มนั้นครองอยู่ ดังนั้นโปรเซสาภายในกลุ่มนั้นจะถูกปฏิเสธให้ทำงาน(blocked)และไม่มีโปรเซสใดทำงานได้อีกต่อไป
ระบบปฏิบัติการสามารถหลีกเลี่ยง วงจรอับได้โดยตรวจสอบว่าระบบอยู่ในสถานะที่ปลอดภัยหรือไม่อย่างสม่ำเสมอ สถานะที่ปลอดภัยหรือ safe state คือสถานะที่ระบบสมารถทำการยืนยันได้ว่าโปรเซสต่างๆในระบบสามารถทำงานจนเสร็จสมบูรณ์ได้ แต่จะไม่สามารถทำการยืนยันได้ในสถานะที่ไม่ปลอดภัย และวิธีการคิดแบบนายธนาคาร (Banker’s algorithm) สามารถนำมาใช้ให้ระบบหลีกเลี่ยงการเกิดวงจรอับได้ โดยไม่อนุญาตให้ทรัพยากรแก่โปรเซสที่ร้องขอถ้าการให้นั้นจะทำให้ระบบเข้าไปอยู่ในสถานะที่ไม่ปลอดภัย
เราสามารถออกแบบระบบที่มีการป้องกันการเกิดวงจรอับตั้งแต่เริ่มต้นได้ ตัวอย่างเช่นการที่เราจะอนุญาตให้โปรเซสสามารถครอบครองทรัพยากรได้เพียง1ตัวในขณะหนึ่ง เพื่อเป็นการป้องกันการเกิดวงจรรอคอย(circuler wait) ซึ่งทำให้เกิดปัญหาวงจรอับอย่างแน่นอน หรือ วงจรอับสามารถป้องกันได้โดยใส่ลำดับเลขให้แก่ทรัพยากรทั้งหมด และให้โปรเซสร้องขอได้เฉพาะทรัพยากรที่มีลำดับของเลขสูงกว่าตัวเองถือครองอยู่

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