DBMS - การหยุดชะงัก

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

ตัวอย่างเช่นสมมติชุดของธุรกรรม {T 0 , T 1 , T 2 , ... , T n } T 0ต้องการทรัพยากร X เพื่อทำงานให้สำเร็จ ทรัพยากร X จะจัดขึ้นโดย T 1 , และ T 1กำลังรอให้ทรัพยากร Y ซึ่งจะจัดขึ้นโดย T 2 T 2กำลังรอ Z ทรัพยากรซึ่งจะจัดขึ้นโดย T 0 ดังนั้นกระบวนการทั้งหมดจึงรอให้กันและกันเพื่อปลดปล่อยทรัพยากร ในสถานการณ์นี้ไม่มีกระบวนการใดที่สามารถทำงานให้เสร็จสิ้นได้ สถานการณ์นี้เรียกว่าการหยุดชะงัก

การหยุดชะงักไม่ดีต่อระบบ ในกรณีที่ระบบหยุดชะงักธุรกรรมที่เกี่ยวข้องกับการหยุดชะงักจะถูกย้อนกลับหรือเริ่มต้นใหม่

การป้องกันการหยุดชะงัก

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

มีแผนการป้องกันการชะงักงันที่ใช้กลไกการสั่งซื้อการประทับเวลาของธุรกรรมเพื่อกำหนดสถานการณ์การชะงักงันไว้ล่วงหน้า

Wait-Die Scheme

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

  • ถ้า TS (T i ) <TS (T j ) - นั่นคือ T iซึ่งกำลังร้องขอการล็อกที่ขัดแย้งกันเก่ากว่า T j - ดังนั้น T iจะได้รับอนุญาตให้รอจนกว่ารายการข้อมูลจะพร้อมใช้งาน

  • ถ้า TS (T i )> TS (t j ) - นั่นคือ T iอายุน้อยกว่า T j - ดังนั้น T ฉันก็ตาย T iจะเริ่มต้นใหม่ในภายหลังโดยมีการหน่วงเวลาแบบสุ่ม แต่มีการประทับเวลาเดียวกัน

โครงการนี้ช่วยให้ธุรกรรมที่เก่ากว่ารอได้ แต่ฆ่าคนที่อายุน้อยกว่า

โครงการ Wound-Wait

ในโครงร่างนี้หากธุรกรรมร้องขอให้ล็อกทรัพยากร (รายการข้อมูล) ซึ่งมีการล็อกที่ขัดแย้งกันโดยธุรกรรมอื่นอาจเกิดความเป็นไปได้อย่างใดอย่างหนึ่ง -

  • หาก TS (T ฉัน ) <TS (T J ) แล้ว T ฉันบังคับ T Jที่จะรีดกลับ - นั่นคือ T ฉันบาดแผล T J T jถูกรีสตาร์ทในภายหลังโดยมีการหน่วงเวลาแบบสุ่ม แต่มีการประทับเวลาเดียวกัน

  • ถ้า TS (T i )> TS (T j ) ดังนั้น T iจะถูกบังคับให้รอจนกว่าทรัพยากรจะพร้อมใช้งาน

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

ในทั้งสองกรณีธุรกรรมที่เข้าสู่ระบบในระยะต่อมาจะถูกยกเลิก

หลีกเลี่ยงการหยุดชะงัก

การยกเลิกธุรกรรมไม่ใช่แนวทางปฏิบัติเสมอไป กลไกการหลีกเลี่ยงการหยุดชะงักสามารถใช้เพื่อตรวจจับสถานการณ์การหยุดชะงักล่วงหน้าได้ มีวิธีการเช่น "wait-for graph" แต่เหมาะสำหรับระบบที่ธุรกรรมมีน้ำหนักเบาและมีทรัพยากรน้อยกว่า ในระบบขนาดใหญ่เทคนิคการป้องกันการหยุดชะงักอาจทำงานได้ดี

รอกราฟ

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

ระบบจะเก็บรักษากราฟการรอสำหรับทุกธุรกรรมที่รอรายการข้อมูลบางอย่างที่ผู้อื่นถือไว้ ระบบจะตรวจสอบว่ามีวัฏจักรใด ๆ ในกราฟหรือไม่

ที่นี่เราสามารถใช้สองวิธีต่อไปนี้ -

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

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