Deadlock ในระบบปฏิบัติการคืออะไร: เงื่อนไขและอัลกอริทึมการตรวจจับ

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

Deadlock ในระบบปฏิบัติการคืออะไร?

คำจำกัดความ: Dead-Lock เป็นสถานการณ์ที่โปรเซสเซอร์ตั้งแต่สองตัวขึ้นไปกำลังรอให้เหตุการณ์บางอย่างเกิดขึ้น แต่เหตุการณ์ที่ไม่เกิดขึ้นนั้นเป็นสภาวะการชะงักงันและโปรเซสเซอร์ถูกกล่าวว่าอยู่ในสถานะหยุดชะงัก ตัวอย่างเช่นให้เราสมมติสถานการณ์แบบเรียลไทม์ซึ่งมีรถ A & B สองคันขับโดยคนขับแยกกันสองคนบนถนนทางเดียว ตอนนี้สถานการณ์เกิดขึ้นที่คนขับรถ A บอกว่าเขาเคลื่อนตัวไปทางทิศเหนือเป็นทิศทางที่ถูกต้องในขณะที่คนขับรถ B บอกว่าเขาเคลื่อนไปทางทิศใต้นั้นถูกต้อง แต่ไม่มีใครขยับถอยหลังเพื่อให้รถคันอื่นเคลื่อนที่ไปข้างหน้าสภาพนี้เรียกว่าภาวะชะงักงัน

ตัวอย่างรถ

เพื่อความเข้าใจที่ดีขึ้นให้เราพิจารณาอีกตัวอย่างหนึ่งซึ่งมีทรัพยากรสองตัว R1, R2 และสองกระบวนการ P1 และ P2 โดยที่ R1 ถูกกำหนดให้กับ P1 และ R2 ถูกกำหนดให้กับ P2 ตอนนี้ถ้า P1 ต้องการเข้าถึง R2 อย่างที่เราทราบกันดีอยู่แล้วว่า R2 ถูกควบคุมโดย P2 และตอนนี้ P2 ต้องการเข้าถึง R1 ซึ่ง P1 จะดำเนินการเฉพาะเมื่อเข้าถึง R2 เท่านั้น P2 จะดำเนินการเฉพาะเมื่อเข้าถึง R1 ในสถานการณ์นี้ เป็นสภาวะชะงักงัน

ตัวอย่างโปรเซสเซอร์

เงื่อนไข Dead-Lock

ต่อไปนี้เป็นเงื่อนไขการหยุดชะงักที่สำคัญสี่ประการที่จะเกิดขึ้นหากเงื่อนไขทั้งหมดเกิดขึ้นพร้อมกันมีโอกาสที่จะเกิดการชะงักงัน

การกีดกันซึ่งกันและกัน

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

การกีดกันซึ่งกันและกัน

ไม่มีการปล่อยล่วงหน้า

ตาม pre-emptive ตามอัลกอริทึมหากมีงานที่มีลำดับความสำคัญพยายามขัดขวางงานปัจจุบัน อัลกอริธึม pre-emptive จะเก็บงานปัจจุบันและดำเนินการงานลำดับความสำคัญเป็นอันดับแรกและกลับไปที่งานแรก สถานการณ์ที่อธิบายตามตัวอย่างข้างต้นที่กระบวนการเก็บทรัพยากรไว้ตราบเท่าที่มีการดำเนินการนั่นคือ P1 สามารถปล่อย R1 ได้หลังจากดำเนินการเท่านั้นในทำนองเดียวกัน P2 รีลีส R2 หลังจากการดำเนินการเท่านั้น หากไม่มีการปล่อยล่วงหน้าอาจเกิดการหยุดชะงัก

ไม่มีใบจองตัวอย่าง

รอและรอ

กระบวนการกำลังถือทรัพยากรบางส่วนและกำลังรอทรัพยากรเพิ่มเติม แต่ทรัพยากรเหล่านั้นได้มาจากกระบวนการอื่น จากตัวอย่างข้างต้น P1 ถือ R1 และรอ R2 โดยที่ P2 ได้รับ R2 และ P2 ถือ R2 และรอ R1 โดยที่ R1 ได้มาโดย P1 คือการหยุดชะงักของสถานการณ์พักและรอที่อาจเกิดขึ้นในระบบ

ถือและรอตัวอย่าง

รอแบบวงกลม

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

วงกลมรอตัวอย่าง

อัลกอริทึมการตรวจจับ Dead-Lock

กรณีที่เราจัดสรรทรัพยากรให้กับกระบวนการและระบบปฏิบัติการจะตรวจสอบอีกครั้งว่าเกิดการชะงักงันในระบบหรือไม่โดยใช้อัลกอริธึมการตรวจจับการหยุดชะงักหลัก 2 ตัว

• อินสแตนซ์เดียว
• ประเภททรัพยากรหลายอินสแตนซ์

อินสแตนซ์เดียว

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

• กราฟการจัดสรรทรัพยากร: กระบวนการ P1, P2, P3 และทรัพยากร R1, R2, R3 จะแสดงในกราฟการจัดสรรทรัพยากร
• รอกราฟ: เฉพาะกระบวนการ P1, P2, P3 เท่านั้นที่กล่าวถึงในการรอกราฟ
• หากมีเงื่อนไขเป็นวัฏจักรหากมีการไหลของกระบวนการอย่างต่อเนื่องในทิศทางเดียวหมายความว่าเงื่อนไขวงจรออกและรอให้กราฟอยู่ในสภาวะชะงักงัน

ตัวอย่างที่ 1: ตัวอย่างด้านล่างแสดงให้เห็นว่าไม่มีสถานะการหยุดชะงักเนื่องจากไม่มีการสังเกตการไหลอย่างต่อเนื่องในการรอกราฟ

single-instance-example1

ตัวอย่างที่ 2: สภาวะ Deadlock เกิดขึ้นเนื่องจากมีวัฏจักรการไหลอย่างต่อเนื่องจาก P1 ถึง P4

single-instance-example2

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

ประเภททรัพยากรหลายอินสแตนซ์

ประเภททรัพยากรหลายอินสแตนซ์เป็นสถานการณ์ที่ระบบมีหลายอินสแตนซ์ของทรัพยากรทั้งหมดซึ่งเรียกอีกอย่างว่าอัลกอริทึม Bankers ตามอัลกอริทึมของ Bankers ทันทีที่กระบวนการได้รับทรัพยากรที่จำเป็นทั้งหมดมันก็จะปล่อยทรัพยากรออกไป

ให้เราพิจารณาตัวอย่างต่อไปนี้สมมติว่ามี 3 กระบวนการ P0, P1, P2 และทรัพยากรประเภท A, B, C โดยที่ A สามารถเป็นได้ ซีพียู , B สามารถเป็นเครื่องพิมพ์และ C สามารถเป็นคีย์บอร์ดได้ ตัวเลข“ 0” ในคอลัมน์แสดงถึงความพร้อมของทรัพยากร

กรณี (i): สมมติว่าหากเรายอมรับว่าคำขอเงื่อนไขคือเงื่อนไข“ 000” ซึ่งมีอยู่ใน P0 และ P2 เราควรตรวจสอบว่าคำขอใดเป็นไปตามกระบวนการ P0 จะปล่อยกระบวนการหลังจากได้รับการจัดสรรแล้วกระบวนการ P2 ถัดไปจะเผยแพร่หลังจากได้รับการจัดสรร เช่นนี้ในลำดับทีละกระบวนการจะเผยแพร่ P0, P2, P3, P1, P4 ตามลำดับ สุดท้ายเราได้รับทรัพยากรที่มีอยู่เช่น P7, P2, P6 ลำดับที่ใช้ได้คือเงื่อนไขที่ไม่มีการหยุดชะงัก

นายธนาคารอัลกอริทึมตัวอย่าง 1

บ้าน (ii): สมมติว่า P2 เป็น 001 แทนที่จะเป็น 000 ตอนนี้ให้ใช้อัลกอริทึมของนายธนาคารเพื่อตรวจสอบสภาวะการหยุดชะงักโดยที่ P0 เพียงตัวเดียวจะถูกดำเนินการจากทั้ง 5 กระบวนการ ดังนั้น P1, P2, P3, P4 จึงอยู่ในสถานะหยุดชะงักยกเว้น P0

นายธนาคารตัวอย่าง 2

การใช้งาน Deadlock

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

ข้อดี

ข้อดีของการหยุดชะงักคือ

• ไม่พบการปล่อยล่วงหน้าในการหลีกเลี่ยงการหยุดชะงัก
• ไม่มีความล่าช้าในกระบวนการ

ข้อเสีย

ข้อเสียของการหยุดชะงักคือ

• ทรัพยากรที่จะใช้จะต้องทราบล่วงหน้า
• การอุดตันของกระบวนการเป็นเวลานาน
• การสูญเสียก่อนการปล่อยออกมาเป็นมรดก

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