Please enable JavaScript.

Coggle requires JavaScript to display documents.

บทที่ 5 การติดตาย - Coggle Diagram

- - - - สถานะที่ปลอดภัย
        
        เมื่อโพรเซสร้องขอทรัพยากรที่มีอยู่ ระบบต้องตัดสินว่าถ้าให้ใช้ทรัพยากรแล้วระบบจะยังคงอยู๋ในสถานะที่ปลอดภัยหรือไม่
        
        ความจริงของสถานะที่ปลอดภัยจะไม่เกิดการติดตาย แต่ถ้าเป็นสถานะที่ไม่ปลอดภัยอาจเกิดการติดตายได้ ดังนั้นจึงต้องทำให้ระบบอยู่ในสถานะที่ปลอดภัย และไม่ยอมให้ระบบเข้าสู่ภาวะที่ไม่ปลอดภัยเพื่อหลีกเลี่ยงการติดตาย
      - อัลกอริทึมของนายธนาคาร
        
        โครงสร้างของระบบนายธนาคารมีดังนี้ กำหนดให้มี n โพรเซส มีทรัพยากรในระบบทั้งหมด m ตัวมีข้อมูลดังนี้
        
        Max
        
        เป็นค่าเมตริกซ์ขนาด n x m ที่กำหนดความต้องการสูงสุดของแต่ละโพรเซส ถ้าMax[i,j]=k แล้วโพรเซส i อาจต้องใช้ทรัพยากร j สูงถึง k บริการ
        
        Allocation
        
        เป็นเมตริกซืขนาด n x m ที่กำหนดจำนวนของทรัพยากรในแต่ละชนิดที่ให้บริการแต่ละโพรเซสอยู่ได้ ถ้า Allocation[i,j]=k หมายถึงโพรเซส i กำลังใช้งานทรัพยากรชนิด j อยู่เป็นจำนวน k บริการ
        
        Available
        
        เป็นเวกเตอร์ของขนาดที่ใช้ชี้จำนวนของทรัพยากรที่สามารถใช้งานได้ Available [j]=k ดังนั้น k คือจำนวนที่ทรัพยากรชนิด j จะสามารถให้บริการได้
        
        Need
        
        เมตริกซ์ขนาด n x m เพื่อบ่งบอกจำนวนทรัพยากรที่เหลือที่เหลือที่ยังต้องการใช้ของแต่ละโพรเซส
      - อัลกอริทึมการกำหนดทรัพยากรด้วยกราฟ
        
        Claim Edge Pi => Rj เป็นตัวกำหนดว่าโพรเซส Pi อาจทำการขอใช้ทรัพยากร Rj ซึ่งแทนได้ด้วยจุดปะ ดังนั้นจุดปะจะถูกเปลี่ยนให้กลายเป็นการขอใช้งานจริง(แทนด้วยเส้นทึบ) เมื่อโพรเซสนั้นทำการขอใช้ทรัพยากรจริง และเมื่อทรัพยากรบริการโพรเซสเรียบร้อยแล้วก็จะเปลี่ยนกลับเป็นเส้นปะ Claim Edge เหมือนเดิม
      - อัลกอริทึมที่ปลอดภัย
        
        อัลกอริทึมที่หาได้ว่าระบบปลอดภัยหรือไม่ สามารถทำได้โดยกำหนดให้ work และ finish เป็นเวกเตอร์ที่มีขนาด n x m โดยเริ่มทำงานตามลำดับ
        
        ขั้นตอนที่ 2:
        
        หาค่า Pi ทั้ง 2 ฟังก์ชัน คือ Finish[i] == false,Need i <= 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 nยกกำลัง2
      - อัลกอริทึมของการขอใช้ทรัพยากร
        
        กำหนดให้ Request i เป็นเวกเตอร์ของการขอใช้งานสำหรับโพรเซส i ถ้า reauest[j] = k หมายถึงโพรเซส i ต้องการทำงาน k บริการจากทรัพยากร j เมื่อมีการขอใช้ทรัพยากรโดยโพรเซส i ก็จะเกิดการทำงานดังต่อไปนี้
        
        ถ้า Request i <= Available ไปยังขั้นตอนที่ 3 นอกจากนี้โพรเซส i ต้องรอเนื่องจากทรัพยากรไม่มีให้ใช้งาน
        
        มีการตั้งระบบลองเพื่อใช้ทรัพยากรที่โพรเซสที่โพรเซส i ขอใช้ โดยการใส่ค่าในตัวแปรต่อไปนี้
        
        Allocation(i) = Allocation(i) + Request(i);
        
        Need(i) = Need(i) - Request;
        
        Available = Available - Request;
        
        ถ้าผลของการกำหนดค่าการให้ใช้ทรัพยากรออกมา พบว่าระบบอยู่ในภาวะปลอดภัย ก็จะจบสิ้นการทำงานแล้วยอมโพรเซส i ใช้งานทรัพยากรนั้นจริงๆ อย่างไรก็ตามถ้าผลออกมาว่าไม่ปลอดภัยโฑรเซส i ต้องรอ Request i แล้วก็จะกลับไปสู่ค่าสถานะเก่า
        
        ถ้า Request i <= Need i ไปยังขั้นตอนที่ 2 นอกจากนั้น ให้แสดงข้อความเตือน เนื่องจากโพรเซสมีการใช้ทรัพยากรมากกว่าที่คาดไว้
  - - - การใช้งาน
        
        เมื่อโพรเซสได้รับทรัพยากรที่ต้องการแล้ว โพรเซสสามารถใช้งานทรัพยากรที่ได้รับได้
      - การคืน
        
        โพรเซสต้องคืนทรัพยากรที่ใช้เสร็จแล้วกลับสู๋ระบบ เพื่อเปิดโอกาสให้โพรเซสอื่นที่ต้องการใช้ทรัพยากรนั้นได้รับการจัดสรรทรัพยากรต่อไป
      - การร้องขอ
        
        เมื่อโพรเซสต้องการใช้ทรัพยากร จะต้องทำการร้องขอทรัพยากรนั้นจากระบบ โดยระบบจะตรวจสอบว่าทรัพยากรนั้นว่างอยู่ไม่ ถ้าว่างอยู่โพรเซสจะได้รับการจัดสรรทันที แต่ถ้าไม่โพรเซสที่ร้องขอจะต้องรอจนกว่าจะได้รับทรัพยากรที่ต้องการ
  - - - พิจารณาแต่ละเงื่อนไขดังต่อไปนี้
        
        การใช้ทรัพยากรร่วมกันได้
        
        ปัญหา
        
        ทรัพยากรในระบบไม่อนุญาตให้โพรเซสหลายๆโพรเซสใช้งานพร้อมๆกันได้
        
        วิธีแก้ปัญหานี้คือ ระบบปฏิบัติการจะต้องจัดการให้โพรเซสในระบบสามารถใช้งานทรัพยากรเหล่านั้นร่วมกันได้ วิธีการป้องกันนี้ไม่สามารถทำได้เสมอไปเพราะว่าทรัพยากรบางตัวที่ไม่สามารถใช้งานร่วมกันกับหลายๆโพรเซสพร้อมกันได้
        
        การป้องกันการถือครองและรอคอย
        
        เงื่อนไขของการถือครองและรอคอยนั้นสามารถป้องกันได้ โดยเราจะอนุญาตให้โพรเซสร้องขอทรัพยากรที่ต้องการทั้งหมดก่อน และจะไม่อนุญาตให้โพรเซสนั้นทำงานจนกว่าจะได้รับทรัพยากรที่ร้องขอไปพร้อมกันทั้งหมดก่อน
        
        วิธีการป้องกันแบบนี้จะทำให้ระบบปฏิบัติการทำงานอย่างไม่มีประสิทธิภาพ เพราะโพรเซสจะต้องถือครองทรัพยากรเป็นเวลานาน ในขณะที่รอให้ตัวเองได้รับทรัพยากรทั้งหมดก่อนจึงจะทำงานได้ทั้งๆที่โฑรเซสเหล่านั้นเพียงได้รับทรัพยากรบางตัวก็สามารถทำงานก่อนได้เลย
        
        ในทางปฏิบัติ เราสามารถพบปัญหาที่ไม่สามารถแก้ไขได้ เช่น ในกรณีที่เราใช้โปรแกรมย่อยๆหลายๆโปรแกรม หรือโปรแกรมที่มีโครงส้รางที่สามารถทำงานหลายๆอย่างพร้อมกันได้ โปรแกรมเหล่านี้ต้องตรวจสอบว่ามีการร้องขอทรัพยากรจากโปรแกรมย่อยๆภายในพร้อมกันหรือไม่ ทรัพยากรภายในเพียงพอหรือไม่ ถ้าไม่วงจรอับก็จะเกิดขึ้นได้เช่นกัน
        
        ยอมให้มีการแทรกแทรงกลางคัน
        
        เงื่อนไขนี้เราสามารถทำการป้องกันได้หลายๆวิธีและเงื่อนไขนี้จะยอมให้โพรเซสสามารถแย่งชิงทรัพยากรที่ถูกครอบครองโดยโพรเซสอื่นได้
        
        ถ้าโพรเซสกำลังถือครองทรัพยากรหนึ่งอยู่เราจะให้ระบบป้องกันไม่ให้โพรเซสนั้นทำการร้องขอทรัพยากรอื่นได้อีก จนกว่าโพรเซสนั้นจะปลดปล่อยทรัพยากรที่ตัวเองครอบครองเสียก่อน
        
        ในบางกรณีถ้าโพรเซสต้องการทรัพยากรเพิ่ม ระบบอาจจะกำหนดให้โพรเซสปล่อยทรัพยากรที่ตัวเองครอบครองอยู๋ก่อน และค่อยทำการร้องขอทรัพยากรเหล่านั้นอีกครั้งพร้อมกับทรัพยากรที่ต้องการเพิ่มเติม
        
        การป้องกันการเกิดวงจรรอคอย
        
        เพื่อไม่ให้เกิดการรอแบบวงจร ระบบจะกำหนดหมายเลขประจำให้แต่ละทรัพยากร และเมื่อมีการร้องขอทรัพยากรจากโพรเซสใดๆ จะต้องเป็นการร้องของเรียงตามลำดับหมายเลขประจำทรัพยากรจากน้อยไปมากเสมอ
        
        ถ้าโพรเซสต้องการทรัพยากรเป็นการขอแบบเรียงลำดับหมายเลขทรัพยากรต้องคืนทรัพยากรคือสู่ระบบทุกตัวเสียก่อน
  - - - ระบบจะต้องทำหน้าที่จัดสรรทรัพยากรดังนี้
        
        รถยนต์ที่วิ่งไปทิศตะวันตกจะต้องใช้เส้นทางที่ 2 และ 3
        
        รถยนต์ที่วิ่งไปทิศใต้จะต้องใช้เส้นทางที่ 3 และ 4
        
        รถยนต์ที่วิ่งไปทิศเหนือจะต้องใช้เส้นทางที่ 1 และ 2
        
        รถยนต์ที่วิ่งไปทิศตะวันออกจะต้องใช้เส้นทางที่ 4 และ 1
        
        โดยเมื่อขับเข้าสู่สี่แยกแล้ว จอนุญาตให้รถที่วิ่งมาทางด้านขาวมือไปก่อน กฎนี้สามารถใช้งานได้กรณีที่มีรถเข้ามา 2หรือ 3 คัน อย่างไรก็ตามถ้ารถยนต์ทั้งสี่คันเข้ามาพร้อมกัน แต่ละคันจะต้องรอรถฝั่งขาวมือก่อน การรอในลักษณะวนรอโโยไม่มีที่สิ้นสุดและเกิดวงจรอับขึ้น
  - - - วงจรอับจะเกิดขึ้นก็ต่อเมื่อ
        
        การครอบครองและการรอใช้ทรัพยากร
        
        โฑรเซสที่ได้ครอบครองทรัพยากรอยู่แล้ว ต้องการใช้ทรัพยากรอื่นเพิ่มเติม และร้องขอทรัพยากรที่มีสถานะไม่ว่าง ทำให้โพรเซสต้องรอ
        
        การไม่แย่งชิงทรัพยากร
        
        โฑรเซสที่รอใช้ทรัพยากรต่อจากโฑรเซสที่กำลงใช้ทรัพยากรนั้นอยู่จะต้องรอจนกว่าโฑรเซสนั้นๆทำงานเสร็จและปลดปล่อยทรัพยากร โพรเซสไม่สามารถแย่งชิงทรัพยากรจากโพรเซสอื่นได้
        
        การไม่เกิดร่วม
        
        ขณะเวลาหนึ่งจะมีเพียงโพรเซสเดียวที่ใช้งานทรัพยากรได้ ไม่สามารถมีโพรเซสอื่นใช้งานพร้อมกันได้
        
        การรอแบบวงกลม
        
        โพรเซสเกิดการรอเป็นวัฏจักร
  - - - กลุ่มของ V แบ่งออกเป็น 2 ส่วนใหญ่
        
        จุดของ P ={P1,P2,P3..,Pn} เซตนี้ประกอบด้วยโฑรเซสที่กำลังทำงานในระบบ
        
        จุดของ R ={R1,R2,R3..,Rn} เซตนี้ประกอบไปด้วยทรัพยากรทุกชนิดในระบบ
        
        การร้องขอสามารถแทนได้ด้วย Pi => Rj หมายถึงโพรเซส Pi ขอเข้าทำงานทรัพยากร Rj
        
        การกำหนดให้ทรัพยากรบริการโฑรเซสแทนได้ด้วย Rk => Pj หมายถึงทรัพยากร Rk กำลังถูกโพรเซส Pj ใช้งาน
    - - วงกลม แทน โพรเซส
      - สี่เหลี่ยม แทน ทรัพยากร
      - จึดที่อยู๋ในช่องสี่เหลี่ยม เป็นตัวบ่งชี้ว่าทรัพยากรนี้สามารถถูกใช้งานได้พร้อมกันกี่โพรเซส
      - การขอเข้าใช้งานโฑรเซส i (วงกลม)จะใช้ลูกศรชี้เข้าหาทรัพยากร(กล่องสี่เหลี่ยม)
      - สามารถแสดงว่าทรัพยากรนี้ได้ถูกโฑรเซส i ใช้งานด้วยการชี้ลูกศรออกจากกล่องสี่เหลี่ยมโดยพุ่งออกจากจุดที่โพรเซสนั้นๆกำลังใช้งาน
    - - ถ้ากราฟไม่เป็นลูปจะไม่เกิดติดตาย
      - ถ้ากราฟมีลูป
        
        ทรัพยากรมีให้ใช้งานได้ทีละตัวจะเกิดการติดตาย
        
        ทรัพยากรหนึ่งตัวสามารถใช้ได้พร้อมกันหลายโพรเซส จะมีการเกิดการติดตายหรือไม่เกิดก็เป็นได้
    - - ทำการหลีกเลี่ยง โดยการจัดสรรทรัพยากรให้ถูกต้อง
      - การตรวจพบและแก้ไขให้ถูกต้อง
      - ทำการป้องกันไว้ก่อน โดยไม่ให้หนึ่งในเงื่อนไขทั้งสี่ข้อของการทำให้เกิดวงจรอับ
      - ไม่ต้องสนใจปัญหาใดๆเลย ในบางครั้งถ้าเราไม่สนใจปัญหาที่จะเกิดขึ้น ปัญหาก็อาจจะไม่เกิดขึ้นก็ได้
  - - - กรณีที่มี 1 บริการในทรัพยากร 1 ตัว
        
        ถ้าทุกทรัพยากรสามารถใช้บริการได้เพียง 1 โพรเซสแล้ว ดังนั้นสามารถกำหนดอัลกอริทึมของการตรวจจับการติดตายด้วยการใช้กราฟแสดงทรัพยากรที่เรียกว่า Wait-for การติดตั้งดูแลการใช้กราฟสามารถทำได้โดยกำหนดให้โหนดแทนโพรเซส สัญลักษณ์ Pi -> Pj หมายถึง โพรเซส i กำลังรอโพรเซส j โดยจะทำการแปลงจากกราฟแทนทรัพยากรเป็น wait-for กราฟที่มีแต่โพรเซส จากนั้นจึงอ้างใช้อัลกอริทึม
      - กรณีที่สามารถให้บริการมากกว่า 1 ในทรัพยากร 1 ตัว
        
        Allocation
        
        เป็นเมตริกซ์ขนาด n x m ที่กำหนดจำนวนของทรัพยากรในแต่ละชนิดให้บริการแต่ละโพรเซสอยู่
        
        Request
        
        เป็นเวกเตอร์ขนาด n x m เพื่อบ่งบอกการร้องขอทรัพยากรของแต่ละโพรเซสในขณะนั้น
        
        Available
        
        เป็นเวกเตอร์ของขนาดที่ใช้ชี้จำนวนของทรัพยากรที่สามารถใช้งานได้
        
        อัลกอริทึมของการตรวจจับ
        
        ให้ work และ finish เป็นเวกเตอร์ที่มีขนาด n และ m
        เริ่มค่าที่ work = available สำหรับทุกค่าของ i ถ้า Allocation != 0 แล้ว Finish[i]=false; นอกนั้นค่า Finish[i] = true
        
        ทำการหา i ดังต่อไปนี้ Finish[i] == false และ Requesti <= Work
        
        ถ้าไม่เป็นตามนี้ไปข้อ 4 Work =Work+Allocation; Finish[i] = true; กลับไปยังข้อ 2
        
        ถ้า Finish[i] == false สำหรับบางค่าของ i ที่ 0 <= i <= n แล้วระบบจะอยู่ในสภาวะการติดตาย ยิ่งกว่านั้นถ้า Finish[i] == false แล้วโพรเซส i จะถูกติดตาย
  - - - การยกเลิกโพรเซส
        
        การยกเลิกทุกโพรเซสที่เกิดการติดตาย
        
        วิธีนี้เป็นการกำจัดการติดตายด้วยการยกเลิก โพรเซสที่เกิดการติดตายทั้งหมด
        
        ข้อเสียอาจมีบางโพรเซสที่ทำงานเป็นเวลานานแล้ว และงานใกล้จะเสร็จสิ้นแล้ว แต่โพรเซสต้องถูกยกเลิกไป ทำให้โพรเซสต้องเสียเวลาและเสียค่าใช้จ่าย เนื่องจากโพรเซสที่ถูกยกเลิกไปนั้นต้องเริ่มต้นทำงานใหม่
        
        การยกเลิกทีละหนึ่งโพรเซส
        
        วิธีนี้เป็นการยกเลิกโพรเซสทีละหนึ่งโพรเซส จนกว่าการติดตายจะถูกกำจัดออกไป โดยที่หลังจากแต่ละโพรเซสถูกยกเลิกหรือกำจัดไปนั้น ระบบอัลกอริทึมตรวจสอบการติดตายเพื่อตรวจสอบว่า
        ระบบยังคงติดตายอยู่หรือไม่
        
        การยกเลิกโพรเซสออกจากระบบไม่ได้เป็นสิ่งที่ทำได้ง่าย ถ้าโพรเซสไหนทำงานไปได้ระยะหนึ่ง แล้วสถานะของทรัพยากรต่างๆเปลี่ยนไป ระบบต้องกำหนดสถานะใหม่ ก่อนที่จะทำงานอื่น
        
        ปัจจัยที่ระบบใช้ในการพิจารณาเลือกว่าระบบจะยกเลิกโพรเซสใด โดยมีหลักเกณฑ์ดังนี้
        
        เลือกโพรเซสที่ได้ใช้เวลาของตัวประมวลผลไปแล้วน้อยที่สุด เนิ้องจากจะเกิดความเสียหายน้อยกว่าการเลือกยกเลิกโพรเซสที่ถูกประมวลผลไปเป็นระยะเวลานาน และงานใกล้จะเสร็จสมบูรณ์แล้ว
        
        เลือกโพรเซสที่ได้ให้ผลลัพธ์ หรือเอาต์พุตออกมาแล้วน้อยที่สุด
        
        เลือกโพรเซสที่ได้ครอบครองทรัพยากรไปแล้วน้อยที่สุด
        
        เลือกโพรเซสที่มีลำดับสำคัญหรือความสำคัญน้อยที่สุด จะถูกยกเลิกก่อนโพรเซสที่มีลำดับความสำคัญมากว่า
        
        เลือกโพรเซสที่ยังต้องการเวลาในการทำงานมากที่สุด
      - การแย่งชิงทรัพยากรจากโพรเซส
        
        พิจารณาการแย่งชิงทรัพยากร
        
        การถอยกลับ
        
        ถ้าระบบแย่งชิงทรัพยากรจากโพรเซสใดก็ตาม จะทำให้โพรเซสที่ถูกแย่งชิงทรัพยากรไปนั้นไม่สามารถประมวลผลต่อไปได้ ระบบจำเป็นต้องให้โพรเซสถอยหลังกลับไปอยู่ในสถานะปลอดภัยและเริ่มต้นทำงานจากสถานะนั้น
        
        การอดตาย
        
        ใช้วิธีการเลือกเหยื่อโดยพิจารณาจากค่าใช้จ่ายเป็นสำคัญ ในการแย่งชิงทรัพยากรของโพรเซสนั้น อาจเกิดการแย่งชิงทรัพยากรจากโพรเซสเดิมอยู่ตลอดเวลา ทำให้โพรเซสที่ถูกแย่งชิงไม่สามารถทำงานได้เสร็จสิ้น เรียกว่า โพรเซสอยู่ในสถานะอดตาย
        
        การเลือกเหยื่อ
        
        ปัจจัยที่นำมาพิจารณาคือ ค่าใช้จ่าย ซึ่งเป็นค่าใช้จ่ายที่เกิดขึ้นจากการยกเลิกโพรเซสใดโพรเซสหนึ่ง ดังนั้นถ้าระบบจำเป็นต้องพิจารณาเพื่อยกเลิกโพรเซสจำนวนหนึ่ง