Ticket lock
کمپیوٹر سائنس میں، ٹکٹ لاک ایک مطابقت پذیری میکانزم، یا لاکنگ الگورتھم ہے، جو کہ ایک قسم کا اسپن لاک ہے جو یہ کنٹرول کرنے کے لیے "ٹکٹ" کا استعمال کرتا ہے کہ عمل کے کس دھاگے کو ایک اہم حصے میں داخل ہونے کی اجازت ہے۔ جائزہ ٹکٹ لاک کا بنیادی تصور ٹکٹ قطار کے انتظام کے نظام سے ملتا جلتا ہے۔ یہ وہ طریقہ ہے جسے بہت سی بیکریاں اور ڈیلیاں گاہکوں کو لائن میں کھڑے کیے بغیر، ان کے پہنچنے کی ترتیب میں خدمت کرنے کے لیے استعمال کرتی ہیں۔ عام طور پر، کسی قسم کا ڈسپینسر ہوتا ہے جس سے گاہک آمد پر ترتیب وار نمبر والے ٹکٹ کھینچتے ہیں۔ ڈسپینسر کے اوپر یا اس کے قریب عام طور پر ایک نشان ہوتا ہے جس پر "براہ کرم ایک نمبر لیں" جیسا کچھ لکھا ہوتا ہے۔ عام طور پر ایک متحرک نشان بھی ہوتا ہے، عام طور پر ڈیجیٹل، جو ٹکٹ نمبر دکھاتا ہے جو اب پیش کیا جا رہا ہے۔ ہر بار جب اگلا ٹکٹ نمبر (گاہک) پیش کرنے کے لیے تیار ہوتا ہے، تو "اب خدمت کر رہا ہے" کا نشان بڑھا دیا جاتا ہے اور نمبر کو کال کیا جاتا ہے۔ اس سے تمام انتظار کرنے والے گاہکوں کو یہ معلوم ہوتا ہے کہ قطار یا قطار میں ان سے کتنے لوگ اب بھی آگے ہیں۔ اس نظام کی طرح، ٹکٹ لاک فرسٹ ان فرسٹ آؤٹ (ایف آئی ایف او) قطار پر مبنی طریقہ کار ہے۔ یہ لاک کے حصول کے منصفانہ ہونے کے فائدے میں اضافہ کرتا ہے اور مندرجہ ذیل کام کرتا ہے۔ دو عدد اقدار ہیں جو 0 سے شروع ہوتی ہیں۔ پہلی قیمت قطار کا ٹکٹ ہے، دوسری ڈیویو ٹکٹ ہے۔ قطار کا ٹکٹ قطار میں دھاگے کی پوزیشن ہے، اور ڈیویو ٹکٹ ٹکٹ، یا قطار کی پوزیشن ہے، جس میں اب تالا ہے (اب خدمت کر رہا ہے)۔ جب کوئی دھاگہ آتا ہے، تو یہ جوہری طور پر حاصل ہوتا ہے اور پھر قطار کے ٹکٹ میں اضافہ کرتا ہے۔ اس آپریشن کی جوہرییت دو دھاگوں کو بیک وقت ایک ہی ٹکٹ نمبر حاصل کرنے کے قابل ہونے سے روکنے کے لیے ضروری ہے۔ اس کے بعد یہ انکریمنٹ سے پہلے اپنے ٹکٹ کی قیمت کا موازنہ ڈیویو ٹکٹ کی قیمت سے کرتا ہے۔ اگر وہ ایک جیسے ہیں، تو دھاگے کو تنقیدی حصے میں داخل ہونے کی اجازت ہے۔ اگر وہ ایک جیسے نہیں ہیں، تو ایک اور دھاگہ پہلے سے ہی تنقیدی حصے میں ہونا چاہیے اور اس دھاگے کو مصروف ہونا چاہیے-انتظار کریں یا فائدہ اٹھائیں۔ جب کوئی دھاگہ لاک کے زیر کنٹرول اہم حصے کو چھوڑتا ہے، تو یہ جوہری طور پر ڈیویو ٹکٹ میں اضافہ کرتا ہے۔ یہ اگلے انتظار کے دھاگے کو، جو اگلے ترتیب وار ٹکٹ نمبر کے ساتھ ہے، اہم حصے میں داخل ہونے کی اجازت دیتا ہے۔ لاک کے حصول میں انصاف کا تصور اس ترتیب پر لاگو ہوتا ہے جس میں دھاگے کامیابی کے ساتھ لاک حاصل کرتے ہیں۔ اگر کسی قسم کی انصاف پسندی کو نافذ کیا جاتا ہے، تو یہ دوسرے دھاگوں کے حق میں تالا حاصل کرنے میں ناکامی کی وجہ سے ایک دھاگے کو طویل عرصے تک پھانسی سے باہر ہونے سے روکتا ہے۔ انصاف کی ضمانت کے بغیر، ایسی صورتحال پیدا ہو سکتی ہے جہاں ایک دھاگہ (یا متعدد دھاگے) دوسروں کے مقابلے میں غیر متناسب طور پر طویل وقت لے سکتا ہے۔ اب یہ ظاہر کرنے کے لیے ایک سادہ سی مثال پیش کی جائے گی کہ لاک کے حصول میں انصاف کی کمی کی وجہ سے دھاگے میں کس طرح ضرورت سے زیادہ تاخیر ہو سکتی ہے۔ ایک ایسا معاملہ فرض کریں جہاں تین دھاگے، جن میں سے ہر ایک تین پروسیسرز میں سے کسی ایک پر چلتا ہے، مندرجہ ذیل سڈوکوڈ کو انجام دے رہے ہیں جو انصاف پسندی پر غور کیے بغیر لاک کا استعمال کرتا ہے۔ جبکہ (1) {لاک {. کریٹیکل سیکشن.} ان لاک} اب مزید تین پروسیسرز، P1، P2، اور P3 کے فزیکل انتظامات کو فرض کریں، جس کے نتیجے میں مشترکہ لاک متغیر کے مقام پر میموری تک رسائی کا غیر یکساں وقت آتا ہے۔ تین پروسیسرز کے لیے لاک متغیر تک رسائی کے وقت کو بڑھانے کا حکم P1 <P2 <P3 ہے۔ لہذا P1 ہمیشہ تالا حاصل کرنے میں سب سے زیادہ فائدہ مند ہوتا ہے، اس کے بعد P2، جس میں P3 سب سے زیادہ نقصان دہ ہوتا ہے۔ انصاف کی ضمانت کی عدم موجودگی میں یہ صورتحال کس طرح دھاگے کی فاقہ کشی کا باعث بنتی ہے، یہ ان تینوں پروسیسرز کے ذریعہ مذکورہ بالا سڈو کوڈ پر عمل درآمد کی درج ذیل مثال میں دکھایا گیا ہے۔ ابتدائی طور پر، تالا مفت ہے اور تینوں پروسیسرز بیک وقت تالا حاصل کرنے کی کوشش کرتے ہیں (وقت 1)۔ پی 1 کے تالے تک سب سے تیز رسائی کا وقت ہونے کی وجہ سے، یہ اسے پہلے حاصل کرتا ہے اور اہم حصے میں داخل ہوتا ہے۔ P2 اور P3 اب گھومتے ہیں جبکہ P1 نازک حصے (وقت 2) میں ہے۔ کریٹیکل سیکشن (ٹائم 3) سے باہر نکلنے پر، P1 لاک کو چھوڑتے ہوئے ایک ان لاک پر عمل درآمد کرتا ہے۔ چونکہ P2 کو P3 کے مقابلے لاک تک تیزی سے رسائی حاصل ہے، اس لیے یہ اگلے لاک کو حاصل کرتا ہے اور اہم حصے (وقت 4) میں داخل ہوتا ہے۔ جبکہ P2 نازک حصے میں ہے، P1 ایک بار پھر تالا حاصل کرنے کی کوشش کرتا ہے لیکن نہیں کر سکتا (وقت 5)، اسے P3 کے ساتھ انتظار کرنے پر مجبور کرتا ہے۔ ایک بار جب P2 اہم حصے کو ختم کر دیتا ہے اور ایک ان لاک جاری کرتا ہے، تو P1 اور P3 دونوں بیک وقت اسے ایک بار پھر حاصل کرنے کی کوشش کرتے ہیں (وقت 6)۔ لیکن P1، اپنے تیز رسائی کے وقت کے ساتھ دوبارہ جیت جاتا ہے، اس طرح اہم حصے (وقت 7) میں داخل ہوتا ہے۔ P3 کا تالا حاصل کرنے سے قاصر ہونے کا یہ نمونہ غیر معینہ مدت تک جاری رہے گا جب تک کہ P1 یا P2 اسے حاصل کرنے کی کوشش کرنا بند نہ کر دیں۔ یہ بعض حالات میں لاک کے حصول میں کسی حد تک انصاف پسندی کو یقینی بنانے کی ضرورت کی وضاحت کرتا ہے۔ تمام تالے ایسے میکانزم نہیں رکھتے جو کسی بھی سطح کی انصاف پسندی کو یقینی بناتے ہیں، جس سے اوپر بیان کردہ حالات سے ملتے جلتے حالات کا امکان باقی رہ جاتا ہے۔ تالے کی مثالوں کے لیے نیچے تالے کا موازنہ سیکشن دیکھیں جو کسی منصفانہ ضمانت کو نافذ نہیں کرتے ہیں۔ ٹکٹ لاک کا نفاذ غیر یکساں میموری آرکیٹیکچر (این یو ایم اے) سسٹم میں لاک کا نفاذ ضروری ہے جو لاک کے حصول کی کسی حد تک انصاف کی ضمانت دیتا ہے۔ ٹکٹ لاک اسپن لاک کا نفاذ ہے جو اس مطلوبہ خصوصیت کو شامل کرتا ہے۔ مندرجہ ذیل سڈو کوڈ لاک کو شروع کرنے، لاک حاصل کرنے اور لاک کو جاری کرنے کی کارروائیوں کو ظاہر کرتا ہے۔ ٹکٹ لاک _ ایکوائن پر کال کوڈ کے اہم حصے سے پہلے ہوگی اور ٹکٹ لاک _ ریلیز اس کے بعد آئے گی۔ ہر پروسیسر ہر پروسیسر کے مائی ٹکٹ کی قیمت کے ذریعے اپنی باری پر نظر رکھے گا۔ یان سولہین کی فرضی کوڈ کی مثال خاکہ below.ticketLock_init (int * نیکسٹ _ ٹکٹ، int * اب _ سروئنگ) میں درج ہے۔ ٹکٹ لاک حاصل کریں (int * نیکسٹ _ ٹکٹ، int * اب _ سروئنگ) {میرا ٹکٹ = fetch _ and _ inc (نیکسٹ _ ٹکٹ) ؛ جبکہ (* اب _ سروئنگ! = میرا ٹکٹ) {} ٹکٹ لاک ریلیز (int * اب _ سروئنگ) {+ + * اب _ سروئنگ ؛} اوپر کے فرضی کوڈ کے ساتھ ہم دیکھ سکتے ہیں کہ ہر بار جب کوئی پروسیسر ٹکٹ لاک کے ساتھ لاک حاصل کرنے کی کوشش کرتا ہے تو اسے واپس لانے کے لیے fetch _ and _ inc کہا جاتا ہے۔ یہ نوٹ کرنا ضروری ہے کہ حاصل کرنا اور اضافہ جوہری طور پر کیا جاتا ہے، اس طرح رسائی میں کسی بھی دوسری ہم آہنگی کی کوششوں کی اجازت نہیں دی جاتی ہے۔ ایک بار میرا ٹکٹ موصول ہونے کے بعد، ہر تھریڈ وائل لوپ میں گھومے گا جبکہ اب خدمت کرنا اس کے میرے ٹکٹ کے برابر نہیں ہے۔ ایک بار جب اب _ سرونگ کسی دیئے گئے تھریڈ کے مائی _ ٹکٹ کے برابر ہو جاتا ہے تو انہیں ٹکٹ لاک _ ایکوائن () سے واپس آنے اور کوڈ کے اہم حصے میں داخل ہونے کی اجازت ہوتی ہے۔ کوڈ کے اہم حصے کے بعد، تھریڈ ٹکٹ لاک ریلیز () انجام دیتا ہے جو اب _ سرونگ میں اضافہ کرتا ہے۔ یہ اگلے ترتیب وار مائی ٹکٹ والے دھاگے کو ٹکٹ لاک سے باہر نکلنے اور اہم حصے میں داخل ہونے کی اجازت دیتا ہے۔ چونکہ مائی ٹکٹ ویلیوز لاک پر دھاگے کی آمد کی ترتیب میں حاصل کی جاتی ہیں، اس لیے لاک کے بعد کے حصول کی ضمانت بھی اسی ترتیب میں ہوتی ہے۔ اس طرح، ایف آئی ایف او کے حکم کو نافذ کرتے ہوئے لاک کے حصول کی انصاف پسندی کو یقینی بنایا جاتا ہے۔ مندرجہ ذیل جدول ایک ایسے نظام میں ٹکٹ لاک ان ایکشن کی مثال دکھاتا ہے جس میں چار پروسیسرز (پی 1، پی 2، پی 3، پی 4) اہم حصے تک رسائی کے لیے مقابلہ کرتے ہیں۔ "ایکشن" کالم کے بعد، مندرجہ بالا سڈو کوڈ پر مبنی نتیجہ کا مشاہدہ کیا جا سکتا ہے۔ ہر صف کے لیے، دکھائی گئی متغیر اقدار وہ ہیں جو اشارہ کردہ عمل (کارروائیوں) کے مکمل ہونے کے بعد ہیں۔ مثال سے نوٹ کرنے کی کلیدی بات یہ ہے کہ چاروں پروسیسرز کی طرف سے لاک حاصل کرنے کی ابتدائی کوششوں کے نتیجے میں صرف سب سے پہلے پہنچنے والے کو اصل میں لاک مل جاتا ہے۔ اس کے بعد کی تمام کوششیں، جب کہ پہلی ابھی بھی تالا رکھتی ہے، اہم حصے میں اپنی باری کا انتظار کرنے والے پروسیسرز کی قطار بنانے کا کام کرتی ہے۔ اس کے بعد ہر ایک کو باری باری لاک مل جاتا ہے، جس سے اگلے قطار والے کو پچھلے ہولڈر کے جانے پر اسے حاصل کرنے کی اجازت ملتی ہے۔ یہ بھی نوٹ کریں کہ دوسرا پروسیسر دوسرے پروسیسرز کے ذریعہ لاک کے حصول/ریلیز کے سلسلے کے دوران کسی بھی وقت پہنچ سکتا ہے، اور صرف اپنی باری کا انتظار کرتا ہے۔ لاک کے استعمال سے پہلے پہلا قدم، تمام لاک متغیرات (صف 1) کو شروع کرنا ہے۔ نیکسٹ _ ٹکٹ اور ناؤ _ سرونگ کو 0 سے شروع کرنا اس بات کو یقینی بناتا ہے کہ لاک حاصل کرنے کی کوشش کرنے والے پہلے دھاگے کو ٹکٹ 0 ملے گا، اس طرح اس کے ٹکٹ کے میچنگ ناؤ _ سرونگ کی وجہ سے لاک حاصل ہو جائے گا۔ لہذا جب P1 تالا حاصل کرنے کی کوشش کرتا ہے تو یہ فوری طور پر کامیاب ہو جاتا ہے اور نیکسٹ ٹکٹ کو بڑھا کر 1 (صف 2) کر دیا جاتا ہے۔ جب پی 3 تالا حاصل کرنے کی کوشش کرتا ہے تو اسے اس کے مائی ٹکٹ کے لیے 1 ملتا ہے، اگلے ٹکٹ کو بڑھا کر 2 کر دیا جاتا ہے، اور اسے انتظار کرنا چاہیے کیونکہ ابھی خدمت کرنا ابھی بھی 0 ہے (صف 3)۔ اگلا، جب پی 2 تالا حاصل کرنے کی کوشش کرتا ہے تو اسے اس کے مائی ٹکٹ کے لیے 2 ملتے ہیں، نیکسٹ ٹکٹ کو بڑھا کر 3 کر دیا جاتا ہے، اور اسے ابھی بھی انتظار کرنا پڑتا ہے کیونکہ ابھی خدمت کرنا ابھی بھی 0 ہے (صف 4)۔ پی 1 اب لاک کو 1 تک بڑھا کر جاری کرتا ہے، اس طرح پی 3 کو 1 (صف 5) کی مائی ٹکٹ ویلیو کی وجہ سے اسے حاصل کرنے کی اجازت دیتا ہے۔ اب P3 لاک کو جاری کرتا ہے، اب 2 تک بڑھاتا ہے، جس سے P2 اسے حاصل کر سکتا ہے (صف 6)۔ جبکہ پی 2 کے پاس تالا ہوتا ہے، پی 4 اسے حاصل کرنے کی کوشش کرتا ہے، اسے 3 کی مائی ٹکٹ ویلیو ملتی ہے، نیکسٹ ٹکٹ کو 4 تک بڑھا دیتا ہے، اور اسے انتظار کرنا ہوگا کیونکہ ابھی خدمت کرنا اب بھی 2 ہے (صف 7)۔ جب P2 تالا جاری کرتا ہے، تو یہ اب 3 تک بڑھ جاتا ہے، جس سے P4 اسے حاصل کر سکتا ہے (صف 8)۔ آخر میں، P4 لاک کو جاری کرتا ہے، اور اسے بڑھا کر 4 (صف 9) کر دیتا ہے۔ فی الحال انتظار کرنے والے دھاگوں میں یہ ٹکٹ نمبر نہیں ہے، اس لیے آنے والے اگلے دھاگے کو اس کے ٹکٹ کے لیے 4 ملیں گے اور فوری طور پر تالا حاصل کر لیں گے۔ تالے کا موازنہ لینکس دانا کے نفاذ میں جدید مشینوں پر آسان ٹیسٹ اینڈ سیٹ یا ایکسچینج پر مبنی اسپن لاک الگورتھم کے مقابلے میں کم تاخیر ہو سکتی ہے۔ مختلف قسم کے اسپن پر مبنی تالے کا موازنہ کرتے وقت نیچے دیے گئے جدول پر غور کریں۔ زیادہ بنیادی لاکنگ میکانزم میں جدید لاکنگ میکانزم کے مقابلے میں غیر ارادی تاخیر کم ہوتی ہے۔ فوائد دوسرے اسپن لاک الگورتھم پر ٹکٹ لاک کا ایک فائدہ یہ ہے کہ یہ منصفانہ ہے۔ ویٹنگ تھریڈز کو فرسٹ ان فرسٹ آؤٹ کی بنیاد پر پروسیس کیا جاتا ہے کیونکہ ڈیویو ٹکٹ انٹیجر بڑھتا ہے، اس طرح فاقہ کشی کو روکا جاتا ہے۔ ٹکٹ لاک الگورتھم گرج دار ریوڑ کے مسئلے کو بھی روکتا ہے کیونکہ ایک وقت میں صرف ایک دھاگہ اہم حصے میں داخل ہونے کی کوشش کرتا ہے۔ اسٹوریج لازمی طور پر کوئی مسئلہ نہیں ہے کیونکہ تمام دھاگے ایک متغیر پر گھومتے ہیں، اس کے برعکس صف پر مبنی قطار والے تالے (اے بی کیو ایل) جن کے دھاگے صف کے انفرادی عناصر پر گھومتے ہیں۔ نقصانات ایک نقصان یہ ہے کہ لاک جاری ہونے سے پہلے تمام دھاگے جس قدر پر گھوم رہے ہیں اسے پڑھنے اور جانچنے کے لیے درکار اضافی ہدایات کی وجہ سے غیر ارادی تاخیر زیادہ ہوتی ہے۔ ٹکٹ لاک کا ایک اور بڑا نقصان یہ ہے کہ یہ غیر توسیع پذیر ہے۔ تحقیق سے پتہ چلتا ہے کہ جیسے جیسے پروسیسرز کو ٹکٹ لاک سسٹم میں شامل کیا جاتا ہے، کارکردگی تیزی سے خراب ہوتی دکھائی دیتی ہے۔ ایک اور مسئلہ تالا جاری کرنے سے آتا ہے۔ تمام دھاگے ایک متغیر پر گھوم رہے ہوتے ہیں، لہذا جب تالا جاری کیا جاتا ہے تو وہاں τ (p) کی منسوخی ہوتی ہے (نیز τ (p) کے حصول)۔ اس کی وجہ یہ ہے کہ تمام دھاگوں کو اپنے بلاک کو کیش میں دوبارہ لوڈ کرنا چاہیے اور اہم حصے میں ان کے داخلے کا تعین کرنے کے لیے ایک ٹیسٹ کرنا چاہیے۔ ٹکٹ لاک 1991 میں میلر-کریمی اور اسکاٹ نے متعارف کرایا تھا۔ یہ الگورتھم 2008 میں لینکس کرنل میں اس کے فوائد کی وجہ سے متعارف کرایا گیا تھا، لیکن پیرا ورچوئلائزڈ ماحول میں چھوڑ دیا گیا تھا جہاں اس کے نقصانات تھے۔ پیرا ورچوئلائزیشن میں ٹکٹ لاک کے استعمال کو قابل بنانے کے لیے کام جاری ہے۔ مارچ 2015 تک اس قسم کی لاکنگ اسکیم کو ریڈ ہٹ انٹرپرائز لینکس نے اپنے سسٹم میں دوبارہ استعمال کیا ہے۔ متعلقہ کام لامپورٹ کا بیکری الگورتھم "ٹکٹ" یا "کاؤنٹر" کے اسی طرح کے تصور کا استعمال کرتا ہے لیکن جوہری ہارڈ ویئر آپریشنز کا استعمال نہیں کرتا ہے۔ اسے کارکردگی کے بجائے غلطی برداشت کرنے کے لیے ڈیزائن کیا گیا تھا۔ تمام پروسیسرز مسلسل ریلیز کاؤنٹر کی جانچ پڑتال کرنے کے بجائے، بیکری لاک اپنے ساتھیوں کے ٹکٹوں کی جانچ پڑتال پر گھومتا ہے۔ قطار پر مبنی اسپن لاک ویٹرز کی قطار کو برقرار رکھتے ہوئے اور ان لاک آپریشن کے دوران پہلے ویٹر کو لاک دے کر انصاف کی ضمانت دیتے ہیں۔ فیچ اینڈ ایڈ بھی دیکھیں، ایک اور جوہری ہدایت جسے ٹکٹ لاک کو نافذ کرنے کے لیے فیچ اینڈ انکریمنٹ کی جگہ استعمال کیا جا سکتا ہے۔