ภาวะตันใน Operaระบบ Ting: คืออะไร, Circular Wait (ตัวอย่าง)

Deadlock คืออะไร?

การหยุดชะงัก เป็นสถานการณ์ที่เกิดขึ้นใน ระบบปฏิบัติการ ภาวะติดตาย (Deadlock) เกิดขึ้นเมื่อกระบวนการหนึ่งเข้าสู่สถานะรอคอยเนื่องจากกระบวนการรอคอยอื่นกำลังครอบครองทรัพยากรที่ต้องการอยู่ ภาวะติดตายเป็นปัญหาที่พบได้บ่อยในระบบมัลติโปรเซสซิ่ง ซึ่งหลายกระบวนการใช้ทรัพยากรเฉพาะประเภทหนึ่งร่วมกัน ซึ่งเรียกว่า ซอฟต์ล็อก (Softlock) หรือซอฟต์แวร์ล็อก (Software Lock)

เมื่อเกิดภาวะชะงักงัน กระบวนการที่เกี่ยวข้องทั้งหมดจะไม่สามารถดำเนินการต่อได้ ดังนั้นงานที่ได้รับผลกระทบจะหยุดลงจนกว่าระบบปฏิบัติการจะเข้ามาแทรกแซง

ตัวอย่างของ Deadlock

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

ตัวอย่างการเกิดภาวะเดดล็อค

การรอแบบวงกลมคืออะไร?

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

ตัวอย่างเช่น กระบวนการ A ได้รับการจัดสรรทรัพยากร B ในขณะที่กำลังร้องขอทรัพยากร A ในทำนองเดียวกัน กระบวนการ B ก็ได้รับการจัดสรรทรัพยากร A ในขณะที่กำลังร้องขอทรัพยากร B ซึ่งก่อให้เกิดวงจรการรอคอยแบบวนซ้ำ

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

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

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

การตรวจจับเดดล็อคในระบบปฏิบัติการ

ภาวะการติดตาย (deadlock) สามารถตรวจจับได้โดยตัวจัดตารางทรัพยากร (resource scheduler) ตัวจัดตารางทรัพยากรช่วยให้ระบบปฏิบัติการจัดการทรัพยากรได้อย่างมีประสิทธิภาพ track คือค่าของทรัพยากรทั้งหมดที่ถูกจัดสรรให้กับกระบวนการต่างๆ เมื่อตรวจพบภาวะติดตายแล้ว สามารถแก้ไขได้โดยการแย่งชิงทรัพยากร การย้อนกลับกระบวนการ หรือการยุติกระบวนการที่ติดตายอย่างน้อยหนึ่งกระบวนการ

การป้องกันเดดล็อกในระบบปฏิบัติการ

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

การป้องกันภาวะติดตาย (Deadlock prevention) คือชุดวิธีการที่ใช้เพื่อให้แน่ใจว่าอย่างน้อยหนึ่งในสี่เงื่อนไขที่จำเป็นนั้นไม่สามารถเกิดขึ้นได้

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

ทรัพยากรจะถูกปล่อยคืนได้โดยสมัครใจจากกระบวนการที่ถือครองทรัพยากรนั้นเท่านั้น หลังจากที่กระบวนการนั้นได้เสร็จสิ้นภารกิจแล้ว

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

การยกเว้นร่วมกัน

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

ทรัพยากรที่ใช้ร่วมกัน เช่น ไฟล์แบบอ่านอย่างเดียว จะไม่ทำให้เกิดภาวะการติดตาย (deadlock) แต่ทรัพยากรอย่างเช่นเครื่องพิมพ์และไดรฟ์เทป จำเป็นต้องได้รับการเข้าถึงแบบพิเศษจากกระบวนการเดียวเท่านั้น

กดค้างไว้และรอ

ในสภาวะนี้ กระบวนการต่างๆ จะต้องถูกระงับไม่ให้ครอบครองทรัพยากรหนึ่งหรือมากกว่านั้น ในขณะเดียวกันก็รอทรัพยากรอื่นๆ อีกหนึ่งหรือมากกว่านั้นไปพร้อมกัน

รอแบบวงกลม

วิธีการนี้กำหนดลำดับโดยรวมของทรัพยากรทุกประเภท การป้องกันการรอคอยแบบวนซ้ำยังกำหนดให้ทุกกระบวนการต้องร้องขอทรัพยากรตามลำดับการแจงนับจากน้อยไปมากด้วย

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

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

การหลีกเลี่ยง Algorithms

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

สำหรับทรัพยากรประเภทเดียว:

• ใช้กราฟการจัดสรรทรัพยากร
• วงจรในกราฟเป็นสิ่งจำเป็นและเพียงพอสำหรับการเกิดภาวะชะงักงัน

สำหรับทรัพยากรประเภทเดียวกันที่มีหลายรายการ:

• วัฏจักรเป็นสิ่งจำเป็นแต่ไม่เพียงพอที่จะทำให้เกิดภาวะชะงักงัน
• ใช้ อัลกอริทึมของนายธนาคาร.

ความแตกต่างระหว่างภาวะอดอาหารและภาวะหยุดชะงัก

ต่อไปนี้คือความแตกต่างที่สำคัญบางประการระหว่างภาวะชะงักงันและการอดอยาก:

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

ข้อดีของ Deadlock

ต่อไปนี้คือข้อดีของการใช้วิธีการจัดการภาวะติดตาย:

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

ข้อเสียของ Deadlock

ต่อไปนี้คือข้อเสียของการใช้วิธีการจัดการภาวะติดตาย:

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

คำถามที่พบบ่อย