Deadlock prevention algorithms
کمپیوٹر سائنس میں، ڈیڈ لاک پریوینشن الگورتھم کو ہم آہنگی پروگرامنگ میں استعمال کیا جاتا ہے جب متعدد عمل کو ایک سے زیادہ مشترکہ وسائل حاصل کرنا ہوتے ہیں۔ اگر دو یا دو سے زیادہ ہم آہنگ عمل اندھا دھند متعدد وسائل حاصل کرتے ہیں، تو ایسی صورتحال پیدا ہو سکتی ہے جہاں ہر عمل کے پاس دوسرے عمل کے لیے درکار وسائل ہوں۔ نتیجے کے طور پر، کوئی بھی عمل اپنے مطلوبہ تمام وسائل حاصل نہیں کر سکتا، اس لیے تمام عمل کو مزید عمل درآمد سے روک دیا جاتا ہے۔ اس صورت حال کو ڈیڈ لاک کہا جاتا ہے۔ ڈیڈ لاک پریوینشن الگورتھم ہر عمل کے ذریعے وسائل کے استعمال کو منظم کرتا ہے تاکہ یہ یقینی بنایا جا سکے کہ کم از کم ایک عمل ہمیشہ اپنے مطلوبہ تمام وسائل حاصل کرنے کے قابل ہو۔ ڈیڈ لاک الگورتھم کی ایسی ہی ایک مثال بینکر کا الگورتھم ہے۔ جائزہ تقسیم شدہ ڈیڈ لاک تقسیم شدہ نظاموں میں اس وقت ہو سکتے ہیں جب تقسیم شدہ لین دین یا ہم آہنگی کا کنٹرول استعمال کیا جا رہا ہو۔ تقسیم شدہ ڈیڈ لاک کا پتہ یا تو عالمی ویٹ فار گراف بنا کر، ڈیڈ لاک ڈیٹیکٹر پر مقامی ویٹ فار گراف سے یا تقسیم شدہ الگورتھم جیسے ایج چیسنگ کے ذریعے لگایا جا سکتا ہے۔ فینٹم ڈیڈ لاک ڈیڈ لاک ہوتے ہیں جو نظام کی اندرونی تاخیر کی وجہ سے تقسیم شدہ نظام میں پائے جاتے ہیں لیکن پتہ لگانے کے وقت اصل میں موجود نہیں ہوتے ہیں۔ ڈیڈ لاک کی روک تھام متوازی پن کو بڑھانے کے بہت سے مختلف طریقے ہیں جہاں ریکرسو لاک بصورت دیگر ڈیڈ لاک کا سبب بن سکتے ہیں۔ لیکن ایک قیمت ہے۔ اور وہ قیمت یا تو کارکردگی/اوور ہیڈ ہے، ڈیٹا کی بدعنوانی کی اجازت دیتی ہے، یا دونوں۔ کچھ مثالوں میں شامل ہیں: لاک ہائیرارکیز، لاک ریفرنس گنتی اور پریمپشن (یا تو ورژننگ کا استعمال کرتے ہوئے یا پریمپشن ہونے پر ڈیٹا کی بدعنوانی کی اجازت دینا) ؛ ویٹ فار گراف (ڈبلیو ایف جی) الگورتھم، جو ڈیڈ لاک کا سبب بننے والے تمام چکروں کو ٹریک کرتے ہیں (بشمول عارضی ڈیڈ لاک) ؛ اور ہیورسٹکس الگورتھم جو ضروری نہیں کہ ان جگہوں کے 100% میں متوازییت میں اضافہ کریں جو ڈیڈ لاک ممکن ہیں، لیکن اس کے بجائے انہیں کافی جگہوں پر حل کرکے سمجھوتہ کریں تاکہ کارکردگی/اوور ہیڈ بمقابلہ متوازییت قابل قبول ہو۔ "جب دو ٹرینیں کراسنگ پر ایک دوسرے کے قریب آتی ہیں" کی صورت حال پر غور کریں۔ جسٹ ان ٹائم پریوینشن ایک ایسے سوئچ کے ساتھ کراسنگ (کراسنگ گارڈ) پر کھڑے کسی شخص کو رکھنے کی طرح کام کرتا ہے جو صرف ایک ٹرین کو "سپر ٹریک" پر جانے دے گا جو دوسری ویٹنگ ٹرین (ٹرینوں) کے اوپر اور اس کے اوپر چلتی ہے۔ غیر بار بار آنے والے تالے کے لیے، تالا صرف ایک بار داخل کیا جا سکتا ہے (جہاں ایک دھاگہ غیر مقفل کیے بغیر دو بار داخل ہونے سے تعطل پیدا ہو جائے گا، یا سرکلر انتظار کی روک تھام کو نافذ کرنے کے لیے مستثنی ہو جائے گا)۔ تکراری تالے کے لیے، صرف ایک دھاگے کو تالے سے گزرنے کی اجازت ہے۔ اگر کوئی دوسرے دھاگے تالے میں داخل ہوتے ہیں، تو انہیں اس وقت تک انتظار کرنا چاہیے جب تک کہ ابتدائی دھاگہ جو اس سے گزرا ہے وہ n بار داخل ہوا ہے۔ لہذا پہلے والے کے ساتھ مسئلہ یہ ہے کہ یہ ڈیڈ لاک کی روک تھام بالکل نہیں کرتا ہے۔ دوسرا تقسیم شدہ تعطل کی روک تھام نہیں کرتا ہے۔ لیکن دوسرے کو ڈیڈ لاک کے منظر نامے کو روکنے کے لیے نئی شکل دی گئی ہے جو پہلا حل نہیں کرتا ہے۔ بار بار، صرف ایک دھاگے کو تالے سے گزرنے کی اجازت ہے۔ اگر دوسرے دھاگے تالے میں داخل ہوتے ہیں، تو انہیں اس وقت تک انتظار کرنا چاہیے جب تک کہ ابتدائی دھاگہ جو گزرتا ہے n بار مکمل نہ ہو جائے۔ لیکن اگر لاکنگ میں داخل ہونے والے دھاگوں کی تعداد لاک ہونے والے نمبر کے برابر ہے، تو ایک دھاگے کو سپر تھریڈ کے طور پر تفویض کریں، اور اسے صرف چلانے دیں (لاکنگ میں داخل ہونے/باہر نکلنے کی تعداد کا سراغ لگانا) جب تک کہ یہ مکمل نہ ہو جائے۔ سپر تھریڈ ختم ہونے کے بعد، کنڈیشن دوبارہ ریکرسو لاک سے منطق استعمال کرنے میں تبدیل ہو جاتی ہے، اور باہر نکلنے والا سپر تھریڈ خود کو سپر تھریڈ نہ ہونے کے طور پر سیٹ کرتا ہے جو لاکر کو مطلع کرتا ہے کہ دوسرے لاک شدہ، ویٹنگ تھریڈز کو اس کنڈیشن کو دوبارہ چیک کرنے کی ضرورت ہے۔ اگر ڈیڈ لاک کا منظر نامہ موجود ہے، تو ایک نیا سپر تھریڈ سیٹ کریں اور اس منطق پر عمل کریں۔ ورنہ، باقاعدہ لاکنگ دوبارہ شروع کریں۔ اوپر جن مسائل پر توجہ نہیں دی گئی بہت سی الجھن رکنے کے مسئلے کے گرد گھومتی ہے۔ لیکن یہ منطق رکنے کے مسئلے کو حل نہیں کرتی کیونکہ وہ حالات جن میں لاکنگ ہوتی ہے وہ معلوم ہوتے ہیں، جو ایک مخصوص حل دیتے ہیں (بصورت دیگر مطلوبہ عمومی حل کے بجائے جو رکنے کے مسئلے کی ضرورت ہوتی ہے)۔ پھر بھی، یہ لاکر اس منطق کا استعمال کرتے ہوئے صرف تالے پر غور کرتے ہوئے تمام تعطل کو روکتا ہے۔ لیکن اگر اسے دیگر لاکنگ میکانزم کے ساتھ استعمال کیا جاتا ہے، تو ایک تالا جو شروع ہوتا ہے وہ کبھی بھی کھولتا نہیں ہے (استثناء کو غیر مقفل کیے بغیر باہر پھینک دیا جاتا ہے، غیر معینہ مدت تک لاک کے اندر لوپنگ، یا کال ان لاک کرنا بھول جانا کوڈنگ کی غلطی)، ڈیڈ لاکنگ بہت ممکن ہے۔ ان کو شامل کرنے کی شرط کو بڑھانے کے لیے رکنے کے مسئلے کو حل کرنے کی ضرورت ہوگی، کیونکہ کوئی ایسے حالات سے نمٹ رہا ہوگا جس کے بارے میں کوئی نہیں جانتا ہے اور اسے تبدیل کرنے سے قاصر ہے۔ ایک اور مسئلہ یہ ہے کہ یہ عارضی تعطل کے مسئلے کو حل نہیں کرتا ہے (واقعی تعطل نہیں، بلکہ ایک کارکردگی کا قاتل)، جہاں دو یا زیادہ دھاگے ایک دوسرے پر بند ہوتے ہیں جبکہ دوسرا غیر متعلقہ دھاگہ چل رہا ہوتا ہے۔ ان عارضی ڈیڈ لاک میں ایک دھاگہ ہو سکتا ہے جو خصوصی طور پر ان کے اندر چل رہا ہو، جس سے متوازییت میں اضافہ ہوتا ہے۔ لیکن اس وجہ سے کہ تقسیم شدہ ڈیڈ لاک کا پتہ لگانا تمام تالوں کے لیے کیسے کام کرتا ہے، اور اس میں ذیلی سیٹ نہیں، غیر متعلقہ چلنے والے دھاگے کو عارضی ڈیڈ لاک کو دور کرنے کے لیے سپر تھریڈ منطق انجام دینے سے پہلے مکمل ہونا چاہیے۔ مذکورہ بالا میں عارضی لائیو لاک منظر نامہ دیکھا جا سکتا ہے۔ اگر ایک اور غیر متعلقہ چل رہا دھاگہ پہلے غیر متعلقہ دھاگے کے باہر نکلنے سے پہلے شروع ہوتا ہے، تو عارضی تعطل کی ایک اور مدت واقع ہوگی۔ اگر ایسا مسلسل ہوتا ہے (انتہائی نایاب)، عارضی تعطل کو پروگرام سے باہر نکلنے سے ٹھیک پہلے تک بڑھایا جا سکتا ہے، جب دوسرے غیر متعلقہ دھاگوں کو ختم کرنے کی ضمانت دی جاتی ہے (اس ضمانت کی وجہ سے کہ ایک دھاگہ ہمیشہ تکمیل تک چلے گا)۔ مزید توسیع متوازییت کو بڑھانے کے لیے اضافی منطق کو شامل کرنے کے لیے اس میں مزید توسیع کی جا سکتی ہے جہاں عارضی ڈیڈ لاک دوسری صورت میں ہو سکتے ہیں۔ لیکن مزید منطق شامل کرنے کے ہر قدم کے لیے، ہم مزید اوور ہیڈ شامل کرتے ہیں۔ چند مثالوں میں شامل ہیں: موجودہ تالے کے ہر ذیلی سیٹ پر غور کرنے کے لیے تقسیم شدہ سپر تھریڈ لاکنگ میکانزم کو بڑھانا ؛ ویٹ فار گراف (ڈبلیو ایف جی) الگورتھم، جو ڈیڈ لاک کا سبب بننے والے تمام چکروں کا سراغ لگاتا ہے (بشمول عارضی ڈیڈ لاک) ؛ اور ہیورسٹکس الگورتھم جو ضروری نہیں کہ ان جگہوں کے 100% میں متوازی کو بڑھاتے ہیں جہاں عارضی ڈیڈ لاک ممکن ہیں، بلکہ اس کے بجائے انہیں کافی جگہوں پر حل کرکے سمجھوتہ کرتے ہیں کہ کارکردگی/اوور ہیڈ بمقابلہ متوازییت قابل قبول ہے (مثال کے طور پر۔ دستیاب ہر پروسیسر کے لیے، ڈیڈ لاک سائیکلوں کو تلاش کرنے کی سمت کام کریں جو پروسیسرز کی تعداد + 1 ڈیپ سے کم ہوں)۔ حوالہ جات تقسیم شدہ کمپیوٹنگ