Ticket lock
কম্পিউটার বিজ্ঞানে, টিকিট লক হল একটি সিঙ্ক্রোনাইজেশন প্রক্রিয়া, বা লকিং অ্যালগরিদম, যা এক ধরনের স্পিনলক যা কার্যকর করার কোন থ্রেডকে একটি সমালোচনামূলক বিভাগে প্রবেশ করার অনুমতি দেওয়া হয় তা নিয়ন্ত্রণ করতে "টিকিট" ব্যবহার করে। সংক্ষিপ্ত বিবরণ টিকিট লকের মৌলিক ধারণাটি টিকিট সারি পরিচালন ব্যবস্থার অনুরূপ। এই পদ্ধতিটি অনেক বেকারি এবং ডেলি গ্রাহকদের লাইনে দাঁড় করিয়ে না রেখে তাদের আগমনের ক্রমে পরিবেশন করার জন্য ব্যবহার করে। সাধারণত, এমন কিছু ডিসপেনসার থাকে যা থেকে গ্রাহকরা আগমনের পরে ক্রমানুসারে সংখ্যাযুক্ত টিকিট টানতে পারেন। বিতরণকারীর সাধারণত উপরে বা কাছাকাছি একটি চিহ্ন থাকে যাতে "দয়া করে একটি নম্বর নিন"-এর মতো কিছু লেখা থাকে। সাধারণত একটি গতিশীল চিহ্ন থাকে, সাধারণত ডিজিটাল, যা এখন যে টিকিট নম্বরটি দেওয়া হচ্ছে তা প্রদর্শন করে। প্রতিবার পরবর্তী টিকিট নম্বর (গ্রাহক) পরিবেশন করার জন্য প্রস্তুত হলে, "এখন পরিবেশন করা হচ্ছে" চিহ্নটি বৃদ্ধি করা হয় এবং নম্বরটি কল করা হয়। এটি সমস্ত অপেক্ষারত গ্রাহকদের জানতে সাহায্য করে যে কতজন লোক এখনও সারি বা লাইনে তাদের থেকে এগিয়ে রয়েছে। এই ব্যবস্থার মতো, টিকিট লক একটি ফার্স্ট ইন ফার্স্ট আউট (এফআইএফও) সারি-ভিত্তিক প্রক্রিয়া। এটি লক অধিগ্রহণের ন্যায্যতার সুবিধা যোগ করে এবং নিম্নরূপ কাজ করে; দুটি পূর্ণসংখ্যা মান রয়েছে যা 0 থেকে শুরু হয়। প্রথম মূল্য হল সারির টিকিট, দ্বিতীয়টি হল ডিউক টিকিট। সারির টিকিট হল সারিতে থ্রেডের অবস্থান, এবং ডিক্যু টিকিট হল টিকিট বা সারির অবস্থান, যার এখন তালা রয়েছে (এখন পরিবেশন করা হচ্ছে)। যখন একটি থ্রেড আসে, এটি পারমাণবিকভাবে পায় এবং তারপর সারির টিকিট বৃদ্ধি করে। এই ক্রিয়াকলাপের পারমাণবিকতা দুটি থ্রেডকে একই সাথে একই টিকিট নম্বর পেতে সক্ষম হতে বাধা দেওয়ার জন্য প্রয়োজন। এরপরে এটি ইনক্রিমেন্টের আগে তার টিকিটের মূল্যকে ডিক্যু টিকিটের মূল্যের সাথে তুলনা করে। যদি তারা একই হয়, তবে থ্রেডটিকে সমালোচনামূলক বিভাগে প্রবেশ করার অনুমতি দেওয়া হয়। যদি সেগুলি একই না হয়, তবে আরেকটি থ্রেড অবশ্যই সমালোচনামূলক বিভাগে থাকতে হবে এবং এই থ্রেডটি অবশ্যই ব্যস্ত-অপেক্ষা বা ফলন হবে। যখন একটি থ্রেড লক দ্বারা নিয়ন্ত্রিত সমালোচনামূলক বিভাগটি ছেড়ে যায়, তখন এটি পারমাণবিকভাবে ডিক্যু টিকিটকে বৃদ্ধি করে। এটি পরবর্তী অপেক্ষার থ্রেড, পরবর্তী ক্রমিক টিকিট নম্বর সহ, সমালোচনামূলক বিভাগে প্রবেশের অনুমতি দেয়। তালা অধিগ্রহণের ন্যায্যতা তালা অধিগ্রহণের ক্ষেত্রে ন্যায্যতার ধারণাটি সেই ক্রমের ক্ষেত্রে প্রযোজ্য যেখানে থ্রেডগুলি সফলভাবে তালা অর্জন করে। যদি কোনও ধরনের ন্যায্যতা প্রয়োগ করা হয়, তবে এটি অন্যান্য সুতোর পক্ষে একটি তালা অর্জন করতে না পারার কারণে একটি সুতাকে দীর্ঘ সময়ের জন্য অনাহারে থাকা থেকে বিরত রাখে। ন্যায্যতার কোনও নিশ্চয়তা না থাকলে, এমন একটি পরিস্থিতি তৈরি হতে পারে যেখানে একটি সূত্র (বা একাধিক সূত্র) অন্যদের তুলনায় কার্যকর করতে অসমভাবে দীর্ঘ সময় নিতে পারে। লক অধিগ্রহণের ক্ষেত্রে ন্যায্যতার অভাবের কারণে কীভাবে একটি সূত্র অত্যধিক বিলম্বিত হতে পারে তা দেখানোর জন্য এখন একটি সহজ উদাহরণ উপস্থাপন করা হবে। একটি কেস ধরে নিন যেখানে তিনটি থ্রেড, প্রতিটি তিনটি প্রসেসরের একটিতে এক্সিকিউট করছে, নিম্নলিখিত সিউডোকোডটি এক্সিকিউট করছে যা ন্যায্যতার জন্য কোনও বিবেচনা ছাড়াই একটি লক ব্যবহার করে। যখন (1) {লক {. ক্রিটিক্যাল সেকশন.} আনলক} এখন আরও ধরে নিন যে তিনটি প্রসেসর, পি1, পি2 এবং পি3-এর শারীরিক বিন্যাসের ফলে শেয়ার্ড লক ভেরিয়েবলের অবস্থানে একটি অভিন্ন মেমরি অ্যাক্সেস সময় পাওয়া যায় না। তিনটি প্রসেসরের জন্য লক ভেরিয়েবলের অ্যাক্সেস সময় বাড়ানোর ক্রম হল পি1 <পি2 <পি3। সুতরাং পি 1 সর্বদা লক অর্জনের ক্ষেত্রে সবচেয়ে সুবিধাজনক, তারপরে পি 2, পি 3 সবচেয়ে সুবিধাবঞ্চিত। ন্যায্যতার গ্যারান্টির অভাবে এই পরিস্থিতি কীভাবে অনাহারের দিকে পরিচালিত করে তা এই তিনটি প্রসেসর দ্বারা উপরের সিউডোকোড কার্যকর করার নিম্নলিখিত দৃষ্টান্তে দেখানো হয়েছে। প্রাথমিকভাবে, লকটি বিনামূল্যে এবং তিনটি প্রসেসরই একযোগে লকটি অর্জনের চেষ্টা করে (সময় 1)। পি1-এর লকে দ্রুততম প্রবেশাধিকারের সময় থাকার কারণে, এটি প্রথমে এটি অর্জন করে এবং সমালোচনামূলক বিভাগে প্রবেশ করে। পি 2 এবং পি 3 এখন ঘুরছে যখন পি 1 সমালোচনামূলক বিভাগে রয়েছে (সময় 2)। সমালোচনামূলক বিভাগ (সময় 3) থেকে বেরিয়ে আসার পরে, পি 1 একটি আনলক কার্যকর করে, লকটি ছেড়ে দেয়। যেহেতু পি2-এর পি3-এর তুলনায় দ্রুত লক অ্যাক্সেস রয়েছে, তাই এটি পরবর্তী লকটি অর্জন করে এবং সমালোচনামূলক বিভাগে প্রবেশ করে (সময় 4)। যখন পি2 সমালোচনামূলক বিভাগে রয়েছে, পি1 আবার লকটি অর্জনের চেষ্টা করে কিন্তু করতে পারে না (সময় 5), এটি পি3-এর সাথে অপেক্ষা করতে বাধ্য করে। একবার পি 2 সমালোচনামূলক বিভাগটি শেষ করে এবং একটি আনলক জারি করলে, পি 1 এবং পি 3 উভয়ই একই সাথে এটি আবার অর্জনের চেষ্টা করে (সময় 6)। কিন্তু পি1, তার দ্রুত অ্যাক্সেস সময়ের সাথে আবার জিতে যায়, এইভাবে সমালোচনামূলক বিভাগে প্রবেশ করে (সময় 7)। পি 3-এর এই প্যাটার্নটি অনির্দিষ্টকালের জন্য অব্যাহত থাকবে যতক্ষণ না পি 1 বা পি 2 এটি অর্জনের চেষ্টা বন্ধ করে দেয়। এটি নির্দিষ্ট পরিস্থিতিতে লক অধিগ্রহণের ক্ষেত্রে কিছু স্তরের ন্যায্যতা নিশ্চিত করার প্রয়োজনীয়তার চিত্র তুলে ধরে। সমস্ত লকের এমন কোনও প্রক্রিয়া নেই যা কোনও স্তরের ন্যায্যতা নিশ্চিত করে, যা উপরে বর্ণিত পরিস্থিতির মতো পরিস্থিতির সম্ভাবনা ছেড়ে দেয়। কোনও ন্যায্যতার গ্যারান্টি প্রয়োগ করে না এমন লকের উদাহরণের জন্য নীচের তালিকার তুলনা বিভাগটি দেখুন। টিকিট লকের বাস্তবায়ন একটি নন-ইউনিফর্ম মেমোরি আর্কিটেকচার (এন. ইউ. এম. এ) ব্যবস্থায় একটি লক বাস্তবায়ন করা গুরুত্বপূর্ণ যা লক অধিগ্রহণের কিছু স্তরের ন্যায্যতার নিশ্চয়তা দেয়। টিকিট লক হল স্পিনলকের একটি বাস্তবায়ন যা এই কাঙ্ক্ষিত বৈশিষ্ট্যটি যোগ করে। নিম্নলিখিত সিউডোকোডটি লকটি শুরু করা, লকটি অর্জন করা এবং লকটি ছেড়ে দেওয়ার ক্রিয়াকলাপগুলি দেখায়। কোডের সমালোচনামূলক অংশের আগে টিকিটলক _ অ্যাকুয়ারে একটি কল করা হবে এবং টিকিটলক _ রিলিজ এটি অনুসরণ করবে। প্রতিটি প্রসেসর প্রতিটি প্রসেসরের মাই-টিকিটের মূল্যের মাধ্যমে তার পালা পর্যবেক্ষণ করবে। ইয়ান সোলিহিনের সিউডোকোডের উদাহরণটি ডায়াগ্রামে তালিকাভুক্ত করা হয়েছে below.ticketLock_init (ইন্ট * নেক্সট _ টিকিট, ইন্ট * নাও _ সার্ভিং) {* এখন _ সার্ভিং = * নেক্সট _ টিকিট = 0;} টিকিটলকলেক _ অ্যাকুইন (ইন্ট * নেক্সট _ টিকিট, ইন্ট * নাও _ সার্ভিং) {মাই _ টিকিট = fetch _ এবং _ inc (নেক্সট _ টিকিট); যখন (* এখন _ সার্ভিং! = মাই _ টিকিট) {} টিকিটলক রিলিজ (ইন্ট * এখন _ সার্ভিং) {+ + * এখন _ সার্ভিং;} উপরের সিউডোকোডের সাথে অনুসরণ করে আমরা দেখতে পারি যে প্রতিবার কোনও প্রসেসর টিকিটলকলোক _ অ্যাকুইন () দিয়ে একটি লক অর্জনের চেষ্টা করে, fetch _ এবং _ inc বলা হয়, ফেরত দেয় এটি লক্ষ করা গুরুত্বপূর্ণ যে আনয়ন এবং বৃদ্ধি পারমাণবিকভাবে করা হয়, যার ফলে অ্যাক্সেসের ক্ষেত্রে অন্য কোনও সমবর্তী প্রচেষ্টার অনুমতি দেওয়া হয় না। একবার আমার টিকিট পাওয়া গেলে, প্রতিটি থ্রেড ওয়াইল লুপে ঘুরবে যখন এখন পরিবেশন করা তার আমার টিকিটের সমান নয়। একবার এখন _ পরিবেশন একটি প্রদত্ত থ্রেডের মাই _ টিকিটের সমান হয়ে গেলে তাদের টিকিটলক _ অ্যাকুইয়ার () থেকে ফিরে আসার অনুমতি দেওয়া হয় এবং কোডের সমালোচনামূলক বিভাগে প্রবেশ করার অনুমতি দেওয়া হয়। কোডের সমালোচনামূলক বিভাগের পরে, থ্রেডটি টিকিটলক রিলিজ () সম্পাদন করে যা এখন পরিবেশন বৃদ্ধি করে। এটি পরবর্তী ক্রমিক মাই _ টিকিট সহ থ্রেডটিকে টিকিটলক _ অ্যাকুইন () থেকে প্রস্থান করতে এবং সমালোচনামূলক বিভাগে প্রবেশ করতে দেয়। যেহেতু মাই-টিকিটের মানগুলি লকে থ্রেড আগমনের ক্রমে অর্জিত হয়, তাই লকের পরবর্তী অধিগ্রহণও একই ক্রমে হওয়ার নিশ্চয়তা দেওয়া হয়। এইভাবে, এফ. আই. এফ. ও-র আদেশ কার্যকর করে তালা অধিগ্রহণের ন্যায্যতা নিশ্চিত করা হয়। নিম্নলিখিত টেবিলটি চারটি প্রসেসর (পি1, পি2, পি3, পি4) সহ একটি সিস্টেমে টিকিট লক ইন অ্যাকশনের একটি উদাহরণ দেখায় যা সমালোচনামূলক বিভাগে অ্যাক্সেসের জন্য প্রতিদ্বন্দ্বিতা করে। "অ্যাকশন" কলাম অনুসরণ করে, উপরের সিউডোকোডের উপর ভিত্তি করে ফলাফল পর্যবেক্ষণ করা যেতে পারে। প্রতিটি সারির জন্য, প্রদর্শিত পরিবর্তনশীল মানগুলি নির্দেশিত ক্রিয়া (গুলি) সম্পন্ন হওয়ার পরে। উদাহরণ থেকে লক্ষ্য করার মতো মূল বিষয় হল যে চারটি প্রসেসরের দ্বারা লক অর্জনের প্রাথমিক প্রচেষ্টার ফলে শুধুমাত্র প্রথমে পৌঁছনো প্রকৃতপক্ষে লক পেয়ে যায়। পরবর্তী সমস্ত প্রচেষ্টা, যখন প্রথমটি এখনও তালা ধরে রাখে, সমালোচনামূলক বিভাগে তাদের পালা অপেক্ষা করা প্রসেসরগুলির সারি তৈরি করতে কাজ করে। এর পরে প্রত্যেকে পালাক্রমে তালা পায়, যার ফলে পরের সারিতে থাকা ব্যক্তিটি আগের ধারক চলে যাওয়ার সাথে সাথে এটি অর্জন করতে পারে। এছাড়াও মনে রাখবেন যে অন্য প্রসেসর যে কোনও সময় অন্যান্য প্রসেসর দ্বারা লক অধিগ্রহণ/মুক্তির ক্রমের সময় আসতে পারে এবং কেবল তার পালা অপেক্ষা করে। লক ব্যবহারের আগে প্রথম পদক্ষেপটি হল সমস্ত লক ভেরিয়েবলের সূচনা (সারি 1)। নেক্সট _ টিকিট এবং নাও _ সার্ভিং 0-তে আরম্ভ করা নিশ্চিত করে যে প্রথম যে থ্রেডটি লক পাওয়ার চেষ্টা করবে সে টিকিট 0 পাবে, এইভাবে তার টিকিটের মিল এখন _ সার্ভিং-এর কারণে লক অর্জন করবে। সুতরাং যখন পি1 লকটি অর্জনের চেষ্টা করে তখন এটি অবিলম্বে সফল হয় এবং পরবর্তী টিকিট 1 (সারি 2)-এ বৃদ্ধি করা হয়। যখন পি3 লকটি অর্জনের চেষ্টা করে তখন এটি তার মাই টিকিটের জন্য 1 পায়, পরবর্তী টিকিটটি 2-এ বৃদ্ধি করা হয় এবং এটি অপেক্ষা করতে হবে যেহেতু এখন পরিবেশন এখনও 0 (সারি 3)। এরপরে, যখন পি 2 লকটি অর্জনের চেষ্টা করে তখন এটি তার মাই টিকিটের জন্য 2 পায়, নেক্সট টিকিটটি 3-এ বৃদ্ধি করা হয় এবং এটি এখনও 0 (সারি 4) হওয়ার কারণে অপেক্ষা করতে হবে। পি1 এখন 1-এ বৃদ্ধি করে লকটি ছেড়ে দেয়, এইভাবে পি3-কে 1 (সারি 5)-এর মাই-টিকিট মানের কারণে এটি অর্জন করতে দেয়। এখন পি3 লকটি ছেড়ে দেয়, এখন 2-এ বৃদ্ধি করে, পি2-কে এটি অর্জন করতে দেয় (সারি 6)। পি2-এর লক থাকা সত্ত্বেও, পি4 এটি অর্জনের চেষ্টা করে, মাই-টিকিটের মান 3 পায়, পরবর্তী টিকিটের মান 4-এ বৃদ্ধি করে এবং এখন-পরিবেশন এখনও 2 (সারি 7) হওয়ার জন্য অপেক্ষা করতে হবে। যখন পি2 লকটি ছেড়ে দেয়, তখন এটি এখন 3-এ বৃদ্ধি পায়, পি4-কে এটি পেতে দেয় (সারি 8)। অবশেষে, পি4 লকটি ছেড়ে দেয়, এখন 4 (সারি 9)-এ বৃদ্ধি করে। বর্তমানে কোনও অপেক্ষমান থ্রেডে এই টিকিট নম্বর নেই, তাই পরবর্তী থ্রেডটি তার টিকিটের জন্য 4 পাবে এবং অবিলম্বে লকটি অর্জন করবে। লকের তুলনা লিনাক্স কার্নেল বাস্তবায়নে আধুনিক মেশিনে সহজ টেস্ট-অ্যান্ড-সেট বা এক্সচেঞ্জ ভিত্তিক স্পিনলক অ্যালগরিদমের তুলনায় কম বিলম্বতা থাকতে পারে। বিভিন্ন ধরনের স্পিন ভিত্তিক লকের তুলনা করার সময় নীচের টেবিলটি বিবেচনা করুন। আরও মৌলিক লকিং প্রক্রিয়াগুলিতে উন্নত লকিং পদ্ধতির তুলনায় অনিচ্ছাকৃত বিলম্বতা কম থাকে। সুবিধা অন্যান্য স্পিনলক অ্যালগরিদমের তুলনায় টিকিট লকের একটি সুবিধা হল এটি ন্যায্য। অপেক্ষার থ্রেডগুলি ফার্স্ট-ইন-ফার্স্ট-আউট ভিত্তিতে প্রক্রিয়া করা হয় কারণ ডেক্যু টিকিট পূর্ণসংখ্যা বৃদ্ধি পায়, এইভাবে অনাহার রোধ করে। একটি টিকিট লক অ্যালগরিদম বজ্রধ্বনি করা পশুর সমস্যাকেও প্রতিরোধ করে কারণ একবারে শুধুমাত্র একটি থ্রেড সমালোচনামূলক বিভাগে প্রবেশ করার চেষ্টা করে। অ্যারে-ভিত্তিক ক্যুইং লক (এ. বি. কিউ. এল)-এর মতো নয়, যাদের একটি অ্যারের পৃথক উপাদানের উপর থ্রেড স্পিন থাকে, সঞ্চয় একটি সমস্যা নয় কারণ সমস্ত থ্রেড একটি পরিবর্তনশীলের উপর স্পিন করে। অসুবিধাগুলি একটি অসুবিধা হল যে একটি লক ছেড়ে দেওয়ার আগে সমস্ত থ্রেডগুলি যে মানটি ঘুরছে তা পড়তে এবং পরীক্ষা করার জন্য প্রয়োজনীয় অতিরিক্ত নির্দেশাবলীর কারণে একটি উচ্চতর অনিচ্ছাকৃত বিলম্বতা রয়েছে। টিকিট লকের আরেকটি বড় অসুবিধা হল এটি অ-স্কেলযোগ্য। গবেষণা ইঙ্গিত দেয় যে প্রসেসরগুলি একটি টিকিট লক সিস্টেমে যুক্ত হওয়ার সাথে সাথে কর্মক্ষমতা দ্রুত হ্রাস পায়। আরেকটি সমস্যা হল তালা ছেড়ে দেওয়া। সমস্ত থ্রেডগুলি একটি চলকের উপর ঘুরছে, তাই যখন লকটি ছেড়ে দেওয়া হয় তখন η (p) অকার্যকর (পাশাপাশি η (p) অধিগ্রহণ) হয়। এর কারণ হল সমস্ত থ্রেডকে অবশ্যই ক্যাশে তাদের ব্লক পুনরায় লোড করতে হবে এবং সমালোচনামূলক বিভাগে তাদের প্রবেশ নির্ধারণের জন্য একটি পরীক্ষা করতে হবে। 1991 সালে মেলোর-ক্রামি এবং স্কট দ্বারা টিকিট লক চালু করা হয়েছিল। এই অ্যালগরিদমটি এর সুবিধার কারণে 2008 সালে লিনাক্স কার্নেলে চালু করা হয়েছিল, তবে প্যারাভর্চুয়ালাইজড পরিবেশে বাদ দেওয়া হয়েছিল যেখানে এর অসুবিধা ছিল। প্যারাবার্জুয়ালাইজেশনে টিকিট লকের ব্যবহার সক্ষম করার কাজ চলছে। 2015 সালের মার্চ পর্যন্ত রেড হ্যাট এন্টারপ্রাইজ লিনাক্স তাদের সিস্টেমে এই ধরনের লকিং স্কিম পুনরায় নিয়োগ করেছে। সম্পর্কিত কাজ ল্যাম্পোর্টের বেকারি অ্যালগরিদম একটি "টিকিট" বা "কাউন্টার" এর অনুরূপ ধারণা ব্যবহার করে তবে পারমাণবিক হার্ডওয়্যার ক্রিয়াকলাপ ব্যবহার করে না। এটি পারফরম্যান্সের পরিবর্তে ত্রুটি সহনশীলতার জন্য ডিজাইন করা হয়েছিল। সমস্ত প্রসেসর ক্রমাগত রিলিজ কাউন্টার পরীক্ষা করার পরিবর্তে, বেকারি তার সমবয়সীদের টিকিট পরীক্ষা করে। সারি-ভিত্তিক স্পিন লকগুলি ওয়েটারদের সারি বজায় রেখে এবং আনলক অপারেশনের সময় প্রথম ওয়েটারকে তালা দিয়ে ন্যায্যতার নিশ্চয়তা দেয়। আরও দেখুন আনয়ন-ও-সংযোজন, আরেকটি পারমাণবিক নির্দেশ যা টিকিট লক প্রয়োগ করতে আনয়ন-ও-বৃদ্ধির পরিবর্তে ব্যবহার করা যেতে পারে।