Non-blocking algorithm
কম্পিউটার বিজ্ঞানে, একটি অ্যালগরিদমকে নন-ব্লকিং বলা হয় যদি কোনও থ্রেডের ব্যর্থতা বা সাসপেনশন অন্য থ্রেডের ব্যর্থতা বা সাসপেনশন ঘটাতে না পারে; কিছু ক্রিয়াকলাপের জন্য, এই অ্যালগরিদমগুলি ঐতিহ্যবাহী ব্লকিং বাস্তবায়নের একটি দরকারী বিকল্প প্রদান করে। একটি নন-ব্লকিং অ্যালগরিদম লক-মুক্ত হয় যদি সিস্টেম-ব্যাপী অগ্রগতির নিশ্চয়তা থাকে এবং প্রতি-থ্রেডের অগ্রগতির নিশ্চয়তা থাকলে অপেক্ষা-মুক্ত থাকে। 2003 সালে বাধা-স্বাধীনতা প্রবর্তনের আগে পর্যন্ত সাহিত্যে "নন-ব্লকিং" শব্দটি "লক-ফ্রি" শব্দের সমার্থক হিসেবে ব্যবহৃত হত। "নন-ব্লকিং" শব্দটি ঐতিহ্যগতভাবে টেলিযোগাযোগ নেটওয়ার্কগুলি বর্ণনা করতে ব্যবহৃত হত যা "বিদ্যমান কলগুলি পুনরায় সাজানো ছাড়াই" রিলেগুলির একটি সেটের মাধ্যমে একটি সংযোগকে রুট করতে পারে (ক্লোজ নেটওয়ার্ক দেখুন)। এছাড়াও, যদি টেলিফোন এক্সচেঞ্জটি "ত্রুটিপূর্ণ না হয়, তবে এটি সর্বদা সংযোগ তৈরি করতে পারে" (ন্যূনতম স্প্যানিং সুইচটি ব্লক না করা দেখুন)। অনুপ্রেরণা মাল্টি-থ্রেডেড প্রোগ্রামিংয়ের ঐতিহ্যবাহী পদ্ধতি হল ভাগ করা সংস্থানগুলিতে অ্যাক্সেসকে সিঙ্ক্রোনাইজ করতে লক ব্যবহার করা। সিঙ্ক্রোনাইজেশন প্রিমিটিভ যেমন মিউট্যাক্স, সেমাফোর এবং সমালোচনামূলক বিভাগগুলি এমন সমস্ত প্রক্রিয়া যার মাধ্যমে একজন প্রোগ্রামার নিশ্চিত করতে পারেন যে কোডের নির্দিষ্ট বিভাগগুলি একযোগে কার্যকর হয় না, যদি তা করা হয় তবে ভাগ করা মেমরি কাঠামোকে দূষিত করবে। যদি একটি থ্রেড ইতিমধ্যে অন্য থ্রেড দ্বারা ধরে রাখা একটি লক অর্জন করার চেষ্টা করে, তবে থ্রেডটি লক মুক্ত না হওয়া পর্যন্ত অবরুদ্ধ থাকবে। একটি সুতো ব্লক করা বিভিন্ন কারণে অবাঞ্ছিত হতে পারে। একটি সুস্পষ্ট কারণ হ 'ল থ্রেডটি অবরুদ্ধ থাকাকালীন এটি কিছুই সম্পাদন করতে পারে নাঃ অবরুদ্ধ থ্রেডটি যদি উচ্চ-অগ্রাধিকার বা রিয়েল-টাইম কাজ করত তবে এর অগ্রগতি বন্ধ করা অত্যন্ত অবাঞ্ছিত হত। অন্যান্য সমস্যাগুলি কম সুস্পষ্ট। উদাহরণস্বরূপ, লকগুলির মধ্যে নির্দিষ্ট মিথস্ক্রিয়া অচলাবস্থা, লাইভলক এবং অগ্রাধিকার বিপরীতকরণের মতো ত্রুটির অবস্থার দিকে নিয়ে যেতে পারে। লক ব্যবহারের মধ্যে মোটা-দানাদার লকিংয়ের মধ্যে একটি বিনিময়ও জড়িত, যা সমান্তরালতার সুযোগগুলি উল্লেখযোগ্যভাবে হ্রাস করতে পারে এবং সূক্ষ্ম-দানাদার লকিং, যার জন্য আরও যত্নশীল নকশার প্রয়োজন হয়, ওভারহেড লকিং বৃদ্ধি করে এবং বাগের প্রবণতা বেশি থাকে। ব্লকিং অ্যালগরিদমগুলির বিপরীতে, নন-ব্লকিং অ্যালগরিদমগুলি এই ডাউনসাইডগুলিতে ভুগছে না এবং এছাড়াও ইন্টারাপ্ট হ্যান্ডলারগুলিতে ব্যবহারের জন্য নিরাপদঃ যদিও প্রি-এম্প্টেড থ্রেডটি পুনরায় চালু করা যায় না, তবুও এটি ছাড়া অগ্রগতি সম্ভব। বিপরীতে, পারস্পরিক বর্জন দ্বারা সুরক্ষিত বিশ্বব্যাপী তথ্য কাঠামো একটি ইন্টারাপ্ট হ্যান্ডলারের মাধ্যমে নিরাপদে অ্যাক্সেস করা যায় না, কারণ প্রি-এম্প্টেড থ্রেডটি লক ধরে রাখতে পারে-তবে সমালোচনামূলক বিভাগের সময় ইন্টারাপ্ট অনুরোধটি মাস্ক করে এটি সহজেই সংশোধন করা যেতে পারে। কর্মক্ষমতা উন্নত করতে একটি লক-ফ্রি ডেটা স্ট্রাকচার ব্যবহার করা যেতে পারে। একটি লক-ফ্রি ডেটা স্ট্রাকচার সিরিয়াল এক্সিকিউশনের পরিবর্তে সমান্তরাল এক্সিকিউশনে ব্যয় করা সময়ের পরিমাণ বাড়ায়, মাল্টি-কোর প্রসেসরে কর্মক্ষমতা উন্নত করে, কারণ ভাগ করা ডেটা স্ট্রাকচারের অ্যাক্সেসকে সুসংগত থাকার জন্য সিরিয়ালাইজ করার প্রয়োজন হয় না। বাস্তবায়ন কয়েকটি ব্যতিক্রম ছাড়া, নন-ব্লকিং অ্যালগরিদমগুলি পারমাণবিক রিড-মডিফাই-রাইট প্রিমিটিভ ব্যবহার করে যা হার্ডওয়্যারকে অবশ্যই প্রদান করতে হবে, যার মধ্যে সবচেয়ে উল্লেখযোগ্য হল তুলনা এবং অদলবদল (সিএএস)। সমালোচনামূলক বিভাগগুলি প্রায় সর্বদা এই আদিমগুলির উপর স্ট্যান্ডার্ড ইন্টারফেস ব্যবহার করে প্রয়োগ করা হয় (সাধারণ ক্ষেত্রে, সমালোচনামূলক বিভাগগুলি ব্লক করা হবে, এমনকি এই আদিমগুলির সাথে প্রয়োগ করা হলেও)। 1990-এর দশকে সমস্ত নন-ব্লকিং অ্যালগরিদমগুলি গ্রহণযোগ্য কর্মক্ষমতা অর্জনের জন্য অন্তর্নিহিত আদিমগুলির সাথে "স্থানীয়ভাবে" লিখতে হয়েছিল। যাইহোক, সফ্টওয়্যার লেনদেনের মেমরির উদীয়মান ক্ষেত্রটি দক্ষ নন-ব্লকিং কোড লেখার জন্য আদর্শ বিমূর্ততার প্রতিশ্রুতি দেয়। স্ট্যাক, সারি, সেট এবং হ্যাশ টেবিলের মতো মৌলিক তথ্য কাঠামো প্রদানের ক্ষেত্রেও অনেক গবেষণা করা হয়েছে। এগুলি প্রোগ্রামগুলিকে অ্যাসিঙ্ক্রোনাসভাবে থ্রেডের মধ্যে সহজেই তথ্য বিনিময় করার অনুমতি দেয়। উপরন্তু, কিছু অ-অবরুদ্ধ তথ্য কাঠামো বিশেষ পারমাণবিক আদিম ছাড়া বাস্তবায়িত করার জন্য যথেষ্ট দুর্বল। এই ব্যতিক্রমগুলির মধ্যে রয়েছেঃ একটি একক-পাঠক একক-লেখক রিং বাফার এফ. আই. এফ. ও, এমন একটি আকার যা উপলব্ধ স্বাক্ষরহীন পূর্ণসংখ্যা প্রকারের ওভারফ্লোকে সমানভাবে বিভক্ত করে, কেবলমাত্র একটি মেমরি বাধা ব্যবহার করে নিঃশর্তভাবে প্রয়োগ করা যেতে পারে একটি একক লেখক এবং যে কোনও সংখ্যক পাঠকের সাথে পড়ুন-অনুলিপি করুন। (পাঠকরা অপেক্ষা-মুক্ত; লেখক সাধারণত লক-মুক্ত থাকেন, যতক্ষণ না এটি মেমরি পুনরুদ্ধার করতে হয়)। একাধিক লেখক এবং যে কোনও সংখ্যক পাঠকের সাথে পড়ুন-অনুলিপি-আপডেট। (পাঠকরা অপেক্ষা-মুক্ত; একাধিক লেখক সাধারণত একটি তালা দিয়ে ধারাবাহিকভাবে কাজ করেন এবং বাধা-মুক্ত নন)। বেশ কয়েকটি গ্রন্থাগার অভ্যন্তরীণভাবে লক-মুক্ত কৌশল ব্যবহার করে, তবে সঠিক লক-মুক্ত কোড লেখা কঠিন। নন-ব্লকিং অ্যালগরিদমগুলিতে সাধারণত সাবধানে পরিকল্পিত ক্রমে পড়া, পড়া-পরিবর্তন-লেখা এবং নির্দেশাবলী লেখার একটি সিরিজ জড়িত থাকে। কম্পাইলারগুলিকে অনুকূল করা আক্রমণাত্মকভাবে ক্রিয়াকলাপগুলি পুনরায় সাজাতে পারে। এমনকি যখন তারা তা করে না, তখনও অনেক আধুনিক সিপিইউ প্রায়শই এই ধরনের ক্রিয়াকলাপগুলি পুনরায় সাজায় (তাদের একটি "দুর্বল সামঞ্জস্য মডেল" রয়েছে), যদি না সিপিইউকে পুনরায় সাজানো না করার জন্য একটি মেমরি বাধা ব্যবহার করা হয়। সি + + 11 প্রোগ্রামাররা <atomic>-এ std:: atomic ব্যবহার করতে পারে, এবং সি11 প্রোগ্রামাররা <stdatomic.h> ব্যবহার করতে পারে, যা উভয়ই এমন প্রকার এবং ফাংশন সরবরাহ করে যা সংকলককে এই ধরনের নির্দেশাবলী পুনরায় সাজাতে না বলে এবং উপযুক্ত মেমরি বাধা সন্নিবেশ করতে বলে। অপেক্ষা-স্বাধীনতা অপেক্ষা-স্বাধীনতা হল অগ্রগতির সবচেয়ে শক্তিশালী নন-ব্লকিং গ্যারান্টি, যা অনাহার-স্বাধীনতার সাথে নিশ্চিত সিস্টেম-ওয়াইড থ্রুপুটকে একত্রিত করে। একটি অ্যালগরিদম অপেক্ষা-মুক্ত হয় যদি প্রতিটি অপারেশনের অপারেশন শেষ হওয়ার আগে অ্যালগরিদম কতগুলি পদক্ষেপ নেবে তার উপর একটি সীমা থাকে। এই বৈশিষ্ট্যটি রিয়েল-টাইম সিস্টেমের জন্য গুরুত্বপূর্ণ এবং যতক্ষণ না পারফরম্যান্সের খরচ খুব বেশি না হয় ততক্ষণ থাকা সবসময়ই ভালো। 1980-এর দশকে দেখানো হয়েছিল যে সমস্ত অ্যালগরিদম অপেক্ষা-মুক্তভাবে প্রয়োগ করা যেতে পারে এবং সিরিয়াল কোড থেকে অনেক রূপান্তর, যাকে সার্বজনীন নির্মাণ বলা হয়, প্রদর্শিত হয়েছে। যাইহোক, ফলস্বরূপ পারফরম্যান্স সাধারণভাবে এমনকি সরল ব্লকিং ডিজাইনের সাথে মেলে না। বেশ কয়েকটি গবেষণাপত্র তখন থেকে সর্বজনীন নির্মাণের কার্যকারিতা উন্নত করেছে, তবে তবুও, তাদের কার্যকারিতা ব্লকিং ডিজাইনের অনেক নিচে। বেশ কয়েকটি গবেষণাপত্রে অপেক্ষা-মুক্ত অ্যালগরিদম তৈরির অসুবিধা তদন্ত করা হয়েছে। উদাহরণস্বরূপ, এটি দেখানো হয়েছে যে ব্যাপকভাবে উপলব্ধ পারমাণবিক শর্তাধীন প্রিমিটিভ, সিএএস এবং এলএল/এসসি, অনেক সাধারণ তথ্য কাঠামোর অনাহার-মুক্ত বাস্তবায়ন প্রদান করতে পারে না, যদি না থ্রেডের সংখ্যায় রৈখিকভাবে মেমরি খরচ বৃদ্ধি পায়। কিন্তু বাস্তবে এই নিম্ন সীমাগুলি কোনও প্রকৃত বাধা উপস্থাপন করে না কারণ শেয়ারড মেমরিতে প্রতিটি থ্রেডে ক্যাশ লাইন বা একচেটিয়া রিজার্ভেশন গ্রানুল (এআরএম-এ 2 কেবি পর্যন্ত) ব্যয় করা ব্যবহারিক ব্যবস্থার জন্য খুব ব্যয়বহুল বলে মনে করা হয় না (সাধারণত যুক্তিসঙ্গতভাবে স্টোরের পরিমাণ একটি শব্দ, তবে শারীরিকভাবে একই ক্যাশ লাইনে সিএএস ক্রিয়াকলাপগুলি সংঘর্ষ করবে এবং একই একচেটিয়া রিজার্ভেশন গ্রানুলের এলএল/এসসি ক্রিয়াকলাপগুলি সংঘর্ষ করবে, তাই শারীরিকভাবে প্রয়োজনীয় স্টোরের পরিমাণ বেশি)। 2011 সাল পর্যন্ত গবেষণা এবং অনুশীলন উভয় ক্ষেত্রেই ওয়েট-ফ্রি অ্যালগরিদম বিরল ছিল। যাইহোক, 2011 সালে কোগান এবং পেট্র্যাঙ্ক সিএএস প্রিমিটিভের উপর একটি অপেক্ষা-মুক্ত সারি বিল্ডিং উপস্থাপন করেছিলেন, যা সাধারণত সাধারণ হার্ডওয়্যারে উপলব্ধ। তাদের নির্মাণ মাইকেল এবং স্কটের লক-মুক্ত সারি প্রসারিত করে, যা প্রায়শই অনুশীলনে ব্যবহৃত একটি দক্ষ সারি। কোগান এবং পেট্র্যাঙ্কের একটি ফলো-আপ পেপার অপেক্ষা-মুক্ত অ্যালগরিদমগুলি দ্রুত করার জন্য একটি পদ্ধতি সরবরাহ করেছিল এবং এই পদ্ধতিটি ব্যবহার করে অপেক্ষা-মুক্ত সারিটিকে কার্যত তার লক-মুক্ত প্রতিরূপের মতো দ্রুততর করে তোলে। টিমনাট এবং পেট্র্যাঙ্কের পরবর্তী একটি গবেষণাপত্রে লক-মুক্ত ডেটা স্ট্রাকচার থেকে ওয়েটিং-ফ্রি ডেটা স্ট্রাকচার তৈরির জন্য একটি স্বয়ংক্রিয় প্রক্রিয়া সরবরাহ করা হয়েছিল। এইভাবে, অনেক তথ্য-কাঠামোর জন্য এখন অপেক্ষা-মুক্ত বাস্তবায়ন উপলব্ধ। লক-ফ্রিডম পৃথক থ্রেডগুলিকে অনাহারে থাকার অনুমতি দেয় তবে সিস্টেম-ওয়াইড থ্রুপুটের নিশ্চয়তা দেয়। একটি অ্যালগরিদম লক-মুক্ত হয় যদি, প্রোগ্রাম থ্রেডগুলি পর্যাপ্ত দীর্ঘ সময়ের জন্য চালানো হয়, অন্তত একটি থ্রেড অগ্রগতি করে (অগ্রগতির কিছু বোধগম্য সংজ্ঞার জন্য)। সমস্ত ওয়েট-ফ্রি অ্যালগরিদমগুলি লক-মুক্ত। বিশেষত, যদি একটি থ্রেড স্থগিত করা হয়, তবে একটি লক-ফ্রি অ্যালগরিদম গ্যারান্টি দেয় যে অবশিষ্ট থ্রেডগুলি এখনও অগ্রগতি করতে পারে। অতএব, যদি দুটি থ্রেড একই মিউটেক্স লক বা স্পিনলকের জন্য প্রতিদ্বন্দ্বিতা করতে পারে, তবে অ্যালগরিদমটি লক-মুক্ত নয়। (যদি আমরা একটি থ্রেড ঝুলিয়ে রাখি যা লক ধরে রাখে, তবে দ্বিতীয় থ্রেডটি ব্লক হয়ে যাবে।) একটি অ্যালগরিদম লক-মুক্ত হয় যদি অসীমভাবে প্রায়শই কিছু প্রসেসর দ্বারা অপারেশন সীমিত সংখ্যক ধাপে সফল হয়। উদাহরণস্বরূপ, প্রসেসর যদি একটি অপারেশন চালানোর চেষ্টা করে, তবে কিছু প্রক্রিয়া সীমিত সংখ্যক ধাপে অপারেশন শেষ করতে সফল হবে এবং অন্যরা ব্যর্থ হতে পারে এবং ব্যর্থ হলে পুনরায় চেষ্টা করতে পারে। অপেক্ষা-মুক্ত এবং লক-মুক্তের মধ্যে পার্থক্য হল যে প্রতিটি প্রক্রিয়া দ্বারা অপেক্ষা-মুক্ত অপারেশন অন্যান্য প্রসেসর নির্বিশেষে সীমিত সংখ্যক ধাপে সফল হওয়ার নিশ্চয়তা দেয়। সাধারণভাবে, একটি লক-মুক্ত অ্যালগরিদম চারটি পর্যায়ে চলতে পারেঃ নিজের অপারেশন সম্পূর্ণ করা, একটি বাধাদানকারী অপারেশনে সহায়তা করা, একটি বাধাদানকারী অপারেশন বাতিল করা এবং অপেক্ষা করা। একযোগে সহায়তা এবং গর্ভপাতের সম্ভাবনার কারণে নিজের অস্ত্রোপচার সম্পূর্ণ করা জটিল, তবে এটি সর্বদা সমাপ্তির দ্রুততম পথ। কোনও বাধা পূরণ হলে কখন সহায়তা করতে হবে, বাতিল করতে হবে বা অপেক্ষা করতে হবে সে সম্পর্কে সিদ্ধান্ত নেওয়া একজন বিবাদ ব্যবস্থাপকের দায়িত্ব। এটি খুব সহজ হতে পারে (উচ্চ অগ্রাধিকারের ক্রিয়াকলাপে সহায়তা করা, নিম্ন অগ্রাধিকারের ক্রিয়াকলাপগুলি বাতিল করা), বা আরও ভাল থ্রুপুট অর্জনের জন্য আরও অনুকূলিত হতে পারে, বা অগ্রাধিকারের ক্রিয়াকলাপগুলির বিলম্বতা কমাতে পারে। সঠিক সমবর্তী সহায়তা সাধারণত একটি লক-মুক্ত অ্যালগরিদমের সবচেয়ে জটিল অংশ, এবং প্রায়শই কার্যকর করা খুব ব্যয়বহুলঃ সহায়তা থ্রেডটি কেবল ধীর হয় না, তবে ভাগ করা মেমরির যান্ত্রিকতার জন্য ধন্যবাদ, সহায়তা করা থ্রেডটিও ধীর হয়ে যাবে, যদি এটি এখনও চলছে। বাধা-স্বাধীনতা-বাধা-স্বাধীনতা হল সবচেয়ে দুর্বল প্রাকৃতিক অ-বাধা অগ্রগতির নিশ্চয়তা। একটি অ্যালগরিদম বাধা-মুক্ত হয় যদি যে কোনও সময়ে, একটি সীমাবদ্ধ সংখ্যক ধাপের জন্য বিচ্ছিন্নভাবে কার্যকর করা একটি একক থ্রেড (অর্থাৎ, সমস্ত বাধা থ্রেড স্থগিত সহ) তার ক্রিয়াকলাপ সম্পূর্ণ করে। সমস্ত লক-মুক্ত অ্যালগরিদম বাধামুক্ত। বাধা-স্বাধীনতা শুধুমাত্র দাবি করে যে কোনও আংশিকভাবে সম্পন্ন অপারেশন বাতিল করা যেতে পারে এবং পরিবর্তনগুলি প্রত্যাহার করা যেতে পারে। সমবর্তী সহায়তা বাদ দেওয়ার ফলে প্রায়শই অনেক সহজ অ্যালগরিদম হতে পারে যা যাচাই করা সহজ। সিস্টেমটিকে ক্রমাগত লাইভ-লকিং থেকে বিরত রাখা একজন বিতর্ক ব্যবস্থাপকের কাজ। কিছু বাধা-মুক্ত অ্যালগরিদম তথ্য কাঠামোতে একজোড়া "ধারাবাহিকতা চিহ্নিতকারী" ব্যবহার করে। তথ্য কাঠামো পড়ার প্রক্রিয়াগুলি প্রথমে একটি ধারাবাহিকতা চিহ্নিতকারীকে পড়ে, তারপর প্রাসঙ্গিক তথ্যকে একটি অভ্যন্তরীণ বাফারের মধ্যে পড়ে, তারপর অন্য চিহ্নিতকারীকে পড়ে এবং তারপর চিহ্নিতকারীগুলির তুলনা করে। দুটি চিহ্নিতকারী অভিন্ন হলে তথ্য সামঞ্জস্যপূর্ণ হয়। ডেটা স্ট্রাকচার আপডেট করার অন্য কোনও প্রক্রিয়া দ্বারা রিড বাধাগ্রস্ত হলে মার্কারগুলি অভিন্ন নাও হতে পারে। এই জাতীয় ক্ষেত্রে, প্রক্রিয়াটি অভ্যন্তরীণ বাফারের ডেটা ফেলে দেয় এবং আবার চেষ্টা করে। আরও দেখুন ডেডলক জাভা ConcurrentMap#Lock-মুক্ত পারমাণবিকতা লাইভনেস লক (কম্পিউটার বিজ্ঞান) পারস্পরিক বর্জন অগ্রাধিকার বিপরীতমুখী সম্পদ অনাহার রেফারেন্স বাহ্যিক লিঙ্ক লক-মুক্ত প্রোগ্রামিং অ-ব্লকিং অ্যালগরিদমের একটি ভূমিকা সিঙ্ক্রোনাইজেশন কনকারেন্সি নিয়ন্ত্রণ অ্যালগরিদম