Non-blocking algorithm
کمپیوٹر سائنس میں، ایک الگورتھم کو نان بلاکنگ کہا جاتا ہے اگر کسی دھاگے کی ناکامی یا معطلی کسی دوسرے دھاگے کی ناکامی یا معطلی کا سبب نہیں بن سکتی۔ کچھ کارروائیوں کے لیے، یہ الگورتھم روایتی بلاکنگ نفاذ کا ایک مفید متبادل فراہم کرتے ہیں۔ ایک نان بلاکنگ الگورتھم لاک فری ہوتا ہے اگر سسٹم بھر میں پیش رفت کی ضمانت ہو، اور اگر فی تھریڈ پیش رفت کی ضمانت بھی ہو تو ویٹ فری ہوتا ہے۔ 2003 میں رکاوٹ-آزادی کے تعارف تک ادب میں "نان بلاکنگ" کو "لاک فری" کے مترادف کے طور پر استعمال کیا جاتا تھا۔ لفظ "نان بلاکنگ" روایتی طور پر ٹیلی کمیونیکیشن نیٹ ورکس کو بیان کرنے کے لیے استعمال کیا جاتا تھا جو "موجودہ کالز کو دوبارہ ترتیب دیے بغیر" ریلے کے ایک سیٹ کے ذریعے کنکشن کو روٹ کر سکتا تھا (کلوس نیٹ ورک دیکھیں)۔ اس کے علاوہ، اگر ٹیلی فون ایکسچینج "عیب دار نہیں ہے، تو یہ ہمیشہ کنکشن بنا سکتا ہے" (دیکھیں نان بلاکنگ منمل اسپیننگ سوئچ)۔ محرک ملٹی تھریڈڈ پروگرامنگ کا روایتی نقطہ نظر مشترکہ وسائل تک رسائی کو ہم آہنگ کرنے کے لیے تالے استعمال کرنا ہے۔ مطابقت پذیری پرائمیٹیوز جیسے میوٹیکس، سیمافورس، اور کریٹیکل سیکشن وہ تمام میکانزم ہیں جن کے ذریعے ایک پروگرامر اس بات کو یقینی بنا سکتا ہے کہ کوڈ کے کچھ حصے بیک وقت انجام نہیں دیتے ہیں، اگر ایسا کرنے سے مشترکہ میموری کے ڈھانچے خراب ہو جائیں گے۔ اگر ایک دھاگہ ایک تالا حاصل کرنے کی کوشش کرتا ہے جو پہلے سے ہی دوسرے دھاگے کے پاس ہے، تو دھاگہ اس وقت تک بلاک رہے گا جب تک کہ تالا خالی نہ ہو جائے۔ دھاگے کو بلاک کرنا کئی وجوہات سے ناپسندیدہ ہو سکتا ہے۔ ایک واضح وجہ یہ ہے کہ جب دھاگہ مسدود ہوتا ہے، تو یہ کچھ بھی پورا نہیں کر سکتا: اگر مسدود دھاگہ اعلی ترجیحی یا حقیقی وقت کا کام انجام دے رہا ہوتا، تو اس کی پیش رفت کو روکنا انتہائی ناپسندیدہ ہوتا۔ دیگر مسائل کم واضح ہیں۔ مثال کے طور پر، تالے کے درمیان بعض تعاملات غلطی کے حالات کا باعث بن سکتے ہیں جیسے ڈیڈ لاک، لیو لاک، اور ترجیحی الٹ۔ تالے استعمال کرنے میں موٹے دانے والے تالے کے درمیان تجارت بھی شامل ہوتی ہے، جو متوازی ہونے کے مواقع کو نمایاں طور پر کم کر سکتی ہے، اور باریک دانے والے تالے، جس کے لیے زیادہ محتاط ڈیزائن کی ضرورت ہوتی ہے، لاکنگ اوور ہیڈ کو بڑھاتا ہے اور کیڑوں کا زیادہ شکار ہوتا ہے۔ الگورتھم کو روکنے کے برعکس، نان بلاکنگ الگورتھم ان منفی پہلوؤں سے متاثر نہیں ہوتے ہیں، اور اس کے علاوہ انٹرپٹ ہینڈلرز میں استعمال کے لیے محفوظ ہیں: اگرچہ پہلے سے خالی تھریڈ کو دوبارہ شروع نہیں کیا جا سکتا، اس کے بغیر بھی ترقی ممکن ہے۔ اس کے برعکس، باہمی اخراج سے محفوظ عالمی ڈیٹا ڈھانچے کو انٹرپٹ ہینڈلر میں محفوظ طریقے سے رسائی حاصل نہیں کی جا سکتی، کیونکہ پیشگی تھریڈ وہ ہو سکتا ہے جو لاک کو تھامے ہوئے ہو-لیکن اس کو کریٹیکل سیکشن کے دوران انٹرپٹ کی درخواست کو ماسک کرکے آسانی سے درست کیا جا سکتا ہے۔ کارکردگی کو بہتر بنانے کے لیے لاک فری ڈیٹا ڈھانچہ استعمال کیا جا سکتا ہے۔ لاک فری ڈیٹا ڈھانچہ سیریل پر عمل درآمد کے بجائے متوازی عمل میں گزارے گئے وقت کی مقدار میں اضافہ کرتا ہے، جس سے ملٹی کور پروسیسر پر کارکردگی بہتر ہوتی ہے، کیونکہ مربوط رہنے کے لیے مشترکہ ڈیٹا ڈھانچے تک رسائی کو سیریلائز کرنے کی ضرورت نہیں ہے۔ نفاذ چند مستثنیات کے ساتھ، نان بلاکنگ الگورتھم ایٹمک ریڈ-موڈیفائی-رائٹ پرائمیٹوز کا استعمال کرتے ہیں جو ہارڈ ویئر کو فراہم کرنا ضروری ہے، جن میں سب سے قابل ذکر موازنہ اور تبادلہ (سی اے ایس) ہے۔ تنقیدی حصوں کو تقریبا ہمیشہ ان پرائمیٹوز پر معیاری انٹرفیس کا استعمال کرتے ہوئے نافذ کیا جاتا ہے (عام صورت میں، تنقیدی حصے مسدود ہوں گے، یہاں تک کہ جب ان پرائمیٹوز کے ساتھ نافذ کیا جائے)۔ 1990 کی دہائی میں تمام نان بلاکنگ الگورتھم کو قابل قبول کارکردگی حاصل کرنے کے لیے بنیادی پرائمیٹوز کے ساتھ "مقامی طور پر" لکھنا پڑتا تھا۔ تاہم، سافٹ ویئر ٹرانزیکشنل میموری کا ابھرتا ہوا میدان موثر نان بلاکنگ کوڈ لکھنے کے لیے معیاری تجریدوں کا وعدہ کرتا ہے۔ بنیادی ڈیٹا ڈھانچے جیسے اسٹیک، قطاریں، سیٹ اور ہیش ٹیبل فراہم کرنے میں بھی کافی تحقیق کی گئی ہے۔ یہ پروگراموں کو تھریڈز کے درمیان آسانی سے غیر متزلزل طور پر ڈیٹا کا تبادلہ کرنے کی اجازت دیتے ہیں۔ مزید برآں، کچھ غیر مسدود ڈیٹا ڈھانچے اتنے کمزور ہیں کہ خصوصی جوہری ابتدائی کے بغیر نافذ کیے جا سکتے ہیں۔ ان مستثنیات میں شامل ہیں: ایک واحد ریڈر سنگل رائٹر رنگ بفر ایف آئی ایف او، جس کا سائز دستیاب غیر دستخط شدہ انٹیجر اقسام میں سے کسی ایک کے اوور فلو کو یکساں طور پر تقسیم کرتا ہے، اسے بغیر کسی شرط کے صرف ایک میموری رکاوٹ کا استعمال کرتے ہوئے محفوظ طریقے سے نافذ کیا جا سکتا ہے۔ (قارئین ویٹ فری ہوتے ہیں ؛ مصنف عام طور پر لاک فری ہوتا ہے، جب تک کہ اسے میموری کو دوبارہ حاصل کرنے کی ضرورت نہ ہو)۔ متعدد مصنفین اور کسی بھی تعداد میں قارئین کے ساتھ کاپی اپ ڈیٹ پڑھیں۔ (قارئین انتظار سے آزاد ہیں ؛ متعدد مصنفین عام طور پر تالے کے ساتھ سیریلائز کرتے ہیں اور رکاوٹ سے پاک نہیں ہوتے ہیں)۔ کئی کتب خانے اندرونی طور پر لاک فری تکنیک کا استعمال کرتے ہیں، لیکن لاک فری کوڈ لکھنا مشکل ہے جو درست ہو۔ نان بلاکنگ الگورتھم میں عام طور پر احتیاط سے ڈیزائن کردہ ترتیب میں پڑھنے، پڑھنے، ترمیم کرنے اور لکھنے کی ہدایات کا ایک سلسلہ شامل ہوتا ہے۔ مرتب کرنے والوں کو بہتر بنانا جارحانہ طور پر کارروائیوں کو دوبارہ ترتیب دے سکتا ہے۔ یہاں تک کہ جب وہ ایسا نہیں کرتے ہیں، بہت سے جدید سی پی یو اکثر اس طرح کی کارروائیوں کو دوبارہ ترتیب دیتے ہیں (ان کے پاس "کمزور مستقل ماڈل" ہوتا ہے)، جب تک کہ میموری رکاوٹ کا استعمال سی پی یو کو دوبارہ ترتیب نہ دینے کے لیے نہ کیا جائے۔ C + + 11 پروگرامر <atomic> میں std:: atomic استعمال کر سکتے ہیں، اور C11 پروگرامر <stdatomic.h> استعمال کر سکتے ہیں، یہ دونوں ایسی اقسام اور افعال فراہم کرتے ہیں جو مرتب کرنے والے کو اس طرح کی ہدایات کو دوبارہ ترتیب نہ دینے، اور مناسب میموری رکاوٹیں داخل کرنے کے لیے کہتے ہیں۔ انتظار کی آزادی انتظار کی آزادی ترقی کی سب سے مضبوط غیر مسدود ضمانت ہے، جس میں نظام بھر میں یقینی پیداوار کو فاقہ کشی کی آزادی کے ساتھ ملایا گیا ہے۔ ایک الگورتھم انتظار سے پاک ہوتا ہے اگر ہر آپریشن کا پابند ہوتا ہے کہ آپریشن مکمل ہونے سے پہلے الگورتھم کتنے اقدامات کرے گا۔ یہ خاصیت حقیقی وقت کے نظام کے لیے اہم ہے اور ہمیشہ اچھا لگتا ہے جب تک کہ کارکردگی کی لاگت بہت زیادہ نہ ہو۔ یہ 1980 کی دہائی میں دکھایا گیا تھا کہ تمام الگورتھم کو ویٹ فری لاگو کیا جا سکتا ہے، اور سیریل کوڈ سے بہت سی تبدیلیاں، جنہیں یونیورسل کنسٹرکشنز کہا جاتا ہے، کا مظاہرہ کیا گیا ہے۔ تاہم، نتیجے میں کارکردگی عام طور پر سادہ بلاکنگ ڈیزائن سے بھی میل نہیں کھاتی ہے۔ اس کے بعد سے کئی کاغذات نے عالمگیر تعمیرات کی کارکردگی کو بہتر بنایا ہے، لیکن پھر بھی، ان کی کارکردگی بلاکنگ ڈیزائن سے بہت کم ہے۔ کئی مقالے ویٹ فری الگورتھم بنانے میں دشواری کی تحقیقات کر چکے ہیں۔ مثال کے طور پر، یہ دکھایا گیا ہے کہ وسیع پیمانے پر دستیاب جوہری مشروط ابتدائی، سی اے ایس اور ایل ایل/ایس سی، دھاگوں کی تعداد میں لکیری طور پر بڑھتے ہوئے میموری اخراجات کے بغیر بہت سے عام ڈیٹا ڈھانچوں کا فاقہ کشی سے پاک نفاذ فراہم نہیں کر سکتے ہیں۔ لیکن عملی طور پر یہ نچلی حدود کوئی حقیقی رکاوٹ پیش نہیں کرتی ہیں کیونکہ شیئرڈ میموری میں فی تھریڈ کی کیش لائن یا خصوصی ریزرویشن گرینول (اے آر ایم پر 2 کے بی تک) خرچ کرنا عملی نظاموں کے لیے بہت مہنگا نہیں سمجھا جاتا ہے (عام طور پر اسٹور کی مقدار منطقی طور پر ایک لفظ ہے، لیکن جسمانی طور پر اسی کیش لائن پر سی اے ایس آپریشنز ٹکرائیں گے، اور اسی خصوصی ریزرویشن گرینول میں ایل ایل/ایس سی آپریشنز ٹکرائیں گے، لہذا جسمانی طور پر اسٹور کی ضرورت کی مقدار زیادہ ہے)۔ تحقیق اور عمل دونوں میں 2011 تک ویٹ فری الگورتھم نایاب تھے۔ تاہم، 2011 میں کوگن اور پیٹرانک نے سی اے ایس پر ایک ویٹ فری قطار کی عمارت پیش کی، جو عام طور پر عام ہارڈ ویئر پر دستیاب ہے۔ ان کی تعمیر نے مائیکل اور اسکاٹ کی لاک فری قطار کو بڑھا دیا، جو کہ ایک موثر قطار ہے جو اکثر عملی طور پر استعمال ہوتی ہے۔ کوگن اور پیٹرانک کے ایک فالو اپ پیپر نے ویٹ فری الگورتھم کو تیز بنانے کا ایک طریقہ فراہم کیا اور اس طریقہ کو ویٹ فری قطار کو عملی طور پر اس کے لاک فری ہم منصب کی طرح تیز بنانے کے لیے استعمال کیا۔ ٹمنات اور پیٹرانک کے بعد کے ایک مقالے نے لاک فری ڈیٹا ڈھانچے سے ویٹ فری ڈیٹا ڈھانچے تیار کرنے کے لیے ایک خودکار طریقہ کار فراہم کیا۔ اس طرح، اب بہت سے ڈیٹا اسٹرکچرز کے لیے ویٹ فری نفاذ دستیاب ہیں۔ لاک فریڈم لاک فریڈم انفرادی دھاگوں کو بھوکا رہنے کی اجازت دیتا ہے لیکن نظام بھر میں تھرو پٹ کی ضمانت دیتا ہے۔ ایک الگورتھم لاک فری ہوتا ہے اگر، جب پروگرام کے دھاگوں کو کافی لمبے عرصے تک چلایا جاتا ہے، تو کم از کم ایک دھاگ ترقی کرتا ہے (ترقی کی کچھ سمجھدار تعریف کے لیے)۔ تمام ویٹ فری الگورتھم لاک فری ہیں۔ خاص طور پر، اگر ایک دھاگہ معطل ہے، تو ایک لاک فری الگورتھم اس بات کی ضمانت دیتا ہے کہ باقی دھاگے اب بھی ترقی کر سکتے ہیں۔ لہذا، اگر دو دھاگے ایک ہی میوٹیکس لاک یا اسپن لاک کے لیے مقابلہ کر سکتے ہیں، تو الگورتھم لاک فری نہیں ہے۔ (اگر ہم ایک دھاگے کو معطل کرتے ہیں جس میں تالا ہوتا ہے، تو دوسرا دھاگہ بلاک ہو جائے گا۔) ایک الگورتھم لاک فری ہوتا ہے اگر لامحدود طور پر اکثر کچھ پروسیسرز کے ذریعہ آپریشن محدود تعداد میں مراحل میں کامیاب ہو جائے۔ مثال کے طور پر، اگر پروسیسرز کسی آپریشن کو انجام دینے کی کوشش کر رہے ہیں، تو کچھ عمل محدود تعداد میں آپریشن کو ختم کرنے میں کامیاب ہو جائیں گے اور دوسرے ناکام ہو سکتے ہیں اور ناکامی پر دوبارہ کوشش کر سکتے ہیں۔ ویٹ فری اور لاک فری کے درمیان فرق یہ ہے کہ ہر عمل کے ذریعے ویٹ فری آپریشن دوسرے پروسیسرز سے قطع نظر محدود تعداد میں مراحل میں کامیاب ہونے کی ضمانت دیتا ہے۔ عام طور پر، ایک لاک فری الگورتھم چار مراحل میں چل سکتا ہے: اپنے آپریشن کو مکمل کرنا، رکاوٹ ڈالنے والے آپریشن میں مدد کرنا، رکاوٹ ڈالنے والے آپریشن کو روکنا، اور انتظار کرنا۔ اپنے آپریشن کو مکمل کرنا بیک وقت مدد اور اسقاط حمل کے امکان کی وجہ سے پیچیدہ ہے، لیکن یہ ہمیشہ تکمیل کا تیز ترین راستہ ہے۔ اس بارے میں فیصلہ کہ کب مدد کرنی ہے، اسقاط کرنا ہے یا جب رکاوٹ پوری ہو تو انتظار کرنا تنازعہ مینیجر کی ذمہ داری ہے۔ یہ بہت آسان ہو سکتا ہے (اعلی ترجیحی کارروائیوں میں مدد کرنا، کم ترجیحی کارروائیوں کو روکنا)، یا بہتر تھرو پٹ حاصل کرنے کے لیے زیادہ بہتر بنایا جا سکتا ہے، یا ترجیحی کارروائیوں کی تاخیر کو کم کیا جا سکتا ہے۔ درست بیک وقت مدد عام طور پر لاک فری الگورتھم کا سب سے پیچیدہ حصہ ہوتا ہے، اور اکثر اس پر عمل درآمد کرنا بہت مہنگا ہوتا ہے: نہ صرف اسسٹنگ تھریڈ سست ہوجاتا ہے، بلکہ شیئرڈ میموری کے میکانکس کی بدولت، اسسٹ کیے جانے والے تھریڈ کو بھی سست کردیا جائے گا، اگر یہ اب بھی چل رہا ہے۔ رکاوٹ-آزادی رکاوٹ-آزادی سب سے کمزور قدرتی غیر مسدود ترقی کی ضمانت ہے۔ ایک الگورتھم رکاوٹ سے پاک ہوتا ہے اگر کسی بھی وقت، ایک محدود تعداد میں مراحل کے لیے تنہائی میں پھانسی دیا گیا ایک تھریڈ (یعنی تمام رکاوٹ ڈالنے والے دھاگوں کے ساتھ) اپنا عمل مکمل کرے گا۔ تمام لاک فری الگورتھم رکاوٹ سے پاک ہیں۔ رکاوٹ کی آزادی صرف اس بات کا مطالبہ کرتی ہے کہ کسی بھی جزوی طور پر مکمل ہونے والے عمل کو ختم کیا جا سکے اور کی گئی تبدیلیوں کو واپس لیا جا سکے۔ بیک وقت مدد چھوڑنے کے نتیجے میں اکثر بہت آسان الگورتھم ہو سکتے ہیں جن کی توثیق کرنا آسان ہوتا ہے۔ سسٹم کو مسلسل لائیو لاکنگ سے روکنا ایک تنازعہ مینیجر کا کام ہے۔ کچھ رکاوٹ سے پاک الگورتھم ڈیٹا ڈھانچے میں "مستقل مارکر" کا ایک جوڑا استعمال کرتے ہیں۔ ڈیٹا ڈھانچے کو پڑھنے والے عمل پہلے ایک مستقل مارکر کو پڑھتے ہیں، پھر متعلقہ ڈیٹا کو اندرونی بفر میں پڑھتے ہیں، پھر دوسرے مارکر کو پڑھتے ہیں، اور پھر مارکر کا موازنہ کرتے ہیں۔ ڈیٹا مستقل ہے اگر دونوں مارکر ایک جیسے ہوں۔ مارکر غیر یکساں ہو سکتے ہیں جب ڈیٹا ڈھانچے کو اپ ڈیٹ کرنے والے کسی دوسرے عمل سے پڑھنے میں خلل پڑتا ہے۔ ایسی صورت میں، عمل اندرونی بفر میں موجود ڈیٹا کو خارج کر دیتا ہے اور دوبارہ کوشش کرتا ہے۔ ڈیڈ لاک جاوا ConcurrentMap#Lock-فری ایٹمائٹی لیونس لاک (کمپیوٹر سائنس) باہمی اخراج ترجیحی الٹ وسائل فاقہ کشی حوالہ جات بیرونی لنکس لاک فری پروگرامنگ کا تعارف غیر مسدود کرنے والے الگورتھم مطابقت پذیری ہم آہنگی کنٹرول ہم آہنگی کنٹرول الگورتھم