Livelock: อะไรคือความแตกต่างกับ Deadlock

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

1 ตัวอย่าง:

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

2 ตัวอย่าง:

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

1. ประมวลผลทรัพยากร Y ที่ระงับ
2. กระบวนการ B ถือทรัพยากร X
3. กระบวนการ A ต้องใช้ทรัพยากร X
4. กระบวนการ B ต้องการทรัพยากร Y

สมมติว่า กระบวนการ A รันก่อนและรับทรัพยากรข้อมูล X จากนั้นประมวลผล B รันและรับทรัพยากร Y ไม่ว่ากระบวนการใดจะรันก่อน ไม่มีความคืบหน้าใด ๆ เพิ่มเติม

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

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

อะไรนำไปสู่ ​​Livelock?

Livelock เกิดขึ้นเมื่อจำนวนกระบวนการที่อนุญาตทั้งหมดในระบบเฉพาะควรถูกกำหนดโดยจำนวนรายการทั้งหมดในตารางกระบวนการ ดังนั้น ช่องตารางกระบวนการจึงควรเรียกว่าทรัพยากรที่มีจำกัด

Deadlock คืออะไร?

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

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

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

ความอดอยากคืออะไร?

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

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

ตัวอย่างความอดอยาก

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

ความแตกต่างระหว่าง Deadlock, Starvation และ Livelock

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

สรุป

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