Deadlock prevention algorithms
কম্পিউটার বিজ্ঞানে, অচলাবস্থা প্রতিরোধ অ্যালগরিদমগুলি সমবর্তী প্রোগ্রামিংয়ে ব্যবহৃত হয় যখন একাধিক প্রক্রিয়াকে একাধিক ভাগ করা সম্পদ অর্জন করতে হয়। যদি দুই বা ততোধিক সমবর্তী প্রক্রিয়া নির্বিচারে একাধিক সম্পদ অর্জন করে, তবে এমন একটি পরিস্থিতি ঘটতে পারে যেখানে প্রতিটি প্রক্রিয়ার অন্য প্রক্রিয়া দ্বারা প্রয়োজনীয় একটি সম্পদ থাকে। ফলস্বরূপ, কোনও প্রক্রিয়া তার প্রয়োজনীয় সমস্ত সম্পদ অর্জন করতে পারে না, তাই সমস্ত প্রক্রিয়া আরও কার্যকর হতে বাধা পায়। এই পরিস্থিতিকে অচলাবস্থা বলা হয়। একটি অচলাবস্থা প্রতিরোধ অ্যালগরিদম প্রতিটি প্রক্রিয়ার দ্বারা সম্পদ ব্যবহারের আয়োজন করে যাতে অন্তত একটি প্রক্রিয়া সর্বদা তার প্রয়োজনীয় সমস্ত সম্পদ পেতে সক্ষম হয়। ডেডলক অ্যালগরিদমের এমনই একটি উদাহরণ হল ব্যাঙ্কারের অ্যালগরিদম। ওভারভিউ ডিস্ট্রিবিউটেড ডেডল্ক ডিস্ট্রিবিউটেড ডেডলোক ডিস্ট্রিবিউটেড সিস্টেমে ঘটতে পারে যখন ডিস্ট্রিবিউটেড লেনদেন বা কনকারেন্সি নিয়ন্ত্রণ ব্যবহার করা হচ্ছে। ডিস্ট্রিবিউটেড ডেডলকগুলি একটি গ্লোবাল ওয়েট-ফর গ্রাফ তৈরি করে, একটি ডেডলক ডিটেক্টরের স্থানীয় ওয়েট-ফর গ্রাফ থেকে বা এজ চেজের মতো ডিস্ট্রিবিউটেড অ্যালগরিদম দ্বারা সনাক্ত করা যেতে পারে। ফ্যান্টম ডেডলক হল ডেডলক যা সিস্টেমের অভ্যন্তরীণ বিলম্বের কারণে একটি ডিস্ট্রিবিউটেড সিস্টেমে সনাক্ত করা হয় তবে সনাক্তকরণের সময় আসলে আর বিদ্যমান থাকে না। ডেডলক প্রতিরোধ সমান্তরালতা বাড়ানোর বিভিন্ন উপায় রয়েছে যেখানে পুনরাবৃত্তিমূলক লকগুলি অন্যথায় ডেডলকের কারণ হতে পারে। কিন্তু একটা দাম আছে। এবং সেই মূল্য হয় পারফরম্যান্স/ওভারহেড, ডেটা দুর্নীতির অনুমতি দেয়, বা উভয়ই। কিছু উদাহরণের মধ্যে রয়েছেঃ লক হায়ারার্কি, লক রেফারেন্স-কাউন্টিং এবং প্রিএম্পশন (হয় সংস্করণ ব্যবহার করে বা প্রিএম্পশন ঘটলে ডেটা দুর্নীতির অনুমতি দেওয়া); ওয়েট-ফর-গ্রাফ (ডাব্লুএফজি) অ্যালগরিদম, যা ডেডলক সৃষ্টি করে এমন সমস্ত চক্রকে ট্র্যাক করে (অস্থায়ী ডেডলক সহ); এবং হিউরিস্টিক্স অ্যালগরিদম যা ডেডলক সম্ভব এমন জায়গাগুলির 100%-এ সমান্তরালতা বৃদ্ধি করে না, বরং পর্যাপ্ত জায়গায় সমাধান করে আপস করে যাতে পারফরম্যান্স/ওভারহেড বনাম সমান্তরালতা গ্রহণযোগ্য হয়। একটি "যখন দুটি ট্রেন একটি ক্রসিংয়ে একে অপরের কাছে আসে" পরিস্থিতি বিবেচনা করুন। জাস্ট-ইন-টাইম প্রিভেনশন ক্রসিংয়ে (ক্রসিং গার্ড) একজন ব্যক্তিকে এমন একটি সুইচ দিয়ে দাঁড় করানোর মতো কাজ করে যা শুধুমাত্র একটি ট্রেনকে "সুপার ট্র্যাক"-এ উঠতে দেবে যা অন্য অপেক্ষমান ট্রেনের (গুলি) উপরে এবং উপরে চলে। অ-পুনরাবৃত্তিমূলক লকগুলির জন্য, একটি লক শুধুমাত্র একবার প্রবেশ করা যেতে পারে (যেখানে একটি একক থ্রেড আনলক না করে দুবার প্রবেশ করলে অচলাবস্থা সৃষ্টি হবে, বা বৃত্তাকার অপেক্ষা প্রতিরোধ কার্যকর করার জন্য একটি ব্যতিক্রম নিক্ষেপ করবে)। পুনরাবৃত্তিমূলক লকের জন্য, শুধুমাত্র একটি থ্রেডকে একটি লকের মধ্য দিয়ে যাওয়ার অনুমতি দেওয়া হয়। যদি অন্য কোনও থ্রেড লকে প্রবেশ করে, তবে তাদের অবশ্যই অপেক্ষা করতে হবে যতক্ষণ না প্রাথমিক থ্রেডটি অতিক্রম করে এটি কতবার প্রবেশ করেছে তা সম্পূর্ণ করে। সুতরাং প্রথমটির সমস্যা হল যে এটি কোনও অচলাবস্থা প্রতিরোধ করে না। দ্বিতীয়টি বিতরণকৃত অচলাবস্থা প্রতিরোধ করে না। কিন্তু দ্বিতীয়টি একটি অচলাবস্থা পরিস্থিতি প্রতিরোধ করার জন্য নতুন করে সংজ্ঞায়িত করা হয়েছে যা প্রথমটি সম্বোধন করে না। পুনরাবৃত্তিমূলকভাবে, শুধুমাত্র একটি থ্রেডকে একটি লকের মধ্য দিয়ে যাওয়ার অনুমতি দেওয়া হয়। যদি অন্য থ্রেডগুলি লকে প্রবেশ করে, তবে তাদের অবশ্যই অপেক্ষা করতে হবে যতক্ষণ না প্রাথমিক থ্রেডটি n বার সম্পন্ন হয়। কিন্তু যদি লকিং-এ প্রবেশকারী থ্রেডের সংখ্যা লক হওয়া সংখ্যার সমান হয়, তবে একটি থ্রেডকে সুপার-থ্রেড হিসাবে নির্ধারণ করুন এবং এটি সম্পূর্ণ না হওয়া পর্যন্ত কেবল এটি চালানোর অনুমতি দিন (এটি কতবার লকিং-এ প্রবেশ/প্রস্থান করে তা ট্র্যাক করে)। একটি সুপার-থ্রেড শেষ হওয়ার পরে, শর্তটি পুনরাবৃত্তিমূলক লক থেকে যুক্তি ব্যবহার করার জন্য পরিবর্তিত হয় এবং প্রস্থানকারী সুপার-থ্রেড নিজেকে একটি সুপার-থ্রেড না হিসাবে সেট করে লকারকে অবহিত করে যে অন্যান্য লক করা, অপেক্ষমান থ্রেডগুলিকে এই শর্তটি পুনরায় পরীক্ষা করতে হবে যদি একটি অচল পরিস্থিতি বিদ্যমান থাকে, একটি নতুন সুপার-থ্রেড সেট করুন এবং সেই যুক্তিটি অনুসরণ করুন। অন্যথায়, নিয়মিত লকিং পুনরায় শুরু করুন। উপরে যে বিষয়গুলির সমাধান করা হয়নি সেগুলি অনেক বিভ্রান্তি থামার সমস্যাকে ঘিরে আবর্তিত হয়। কিন্তু এই যুক্তি থামানোর সমস্যার সমাধান করে না কারণ যে শর্তে লকিং ঘটে তা জানা যায়, যা একটি নির্দিষ্ট সমাধান দেয় (অন্যথায় প্রয়োজনীয় সাধারণ সমাধানের পরিবর্তে যা থামানোর সমস্যার প্রয়োজন হয়)। তবুও, এই লকারটি শুধুমাত্র এই যুক্তি ব্যবহার করে লক বিবেচনা করে সমস্ত অচলাবস্থা রোধ করে। কিন্তু যদি এটি অন্যান্য লকিং পদ্ধতির সাথে ব্যবহার করা হয়, তবে যে লকটি শুরু করা হয় তা কখনই আনলক হয় না (ব্যতিক্রম আনলক না করে লাফিয়ে বেরিয়ে যাওয়া, অনির্দিষ্টকালের জন্য লকের মধ্যে লুপিং করা, বা আনলক কল করতে ভুলে যাওয়া কোডিং ত্রুটি), অচলাবস্থা খুব সম্ভব। এগুলি অন্তর্ভুক্ত করার জন্য শর্তটি বাড়ানোর জন্য থামার সমস্যাটি সমাধান করতে হবে, কারণ একজন এমন অবস্থার সাথে মোকাবিলা করবে যা সম্পর্কে কেউ কিছুই জানে না এবং পরিবর্তন করতে অক্ষম। আরেকটি সমস্যা হ 'ল এটি অস্থায়ী অচলাবস্থার সমস্যাটিকে সম্বোধন করে না (প্রকৃতপক্ষে একটি অচলাবস্থার নয়, বরং একটি পারফরম্যান্স কিলার), যেখানে দুটি বা ততোধিক থ্রেড একে অপরের উপর লক করে থাকে যখন অন্য একটি সম্পর্কহীন থ্রেড চলছে। এই অস্থায়ী ডেডলকগুলির মধ্যে একচেটিয়াভাবে একটি সূত্র চলতে পারে, যা সমান্তরালতা বাড়িয়ে তোলে। কিন্তু ডিস্ট্রিবিউটেড ডেডলোক সনাক্তকরণ কীভাবে সমস্ত লকের জন্য কাজ করে, এবং তার মধ্যে উপসেট নয়, অস্থায়ী ডেডলোক অপসারণের জন্য সুপার-থ্রেড লজিক সম্পাদন করার আগে সম্পর্কহীন চলমান থ্রেডটি সম্পূর্ণ করতে হবে। উপরের অংশে অস্থায়ী লাইভ-লক দৃশ্যপট দেখতে পাওয়া যায়। যদি প্রথম সম্পর্কহীন থ্রেডটি বেরিয়ে যাওয়ার আগে আরেকটি সম্পর্কহীন চলমান থ্রেড শুরু হয়, তবে অস্থায়ী অচলাবস্থার আরেকটি সময়কাল ঘটবে। যদি এটি ক্রমাগত ঘটে (অত্যন্ত বিরল), অস্থায়ী অচলাবস্থা প্রোগ্রামটি প্রস্থান করার ঠিক আগে পর্যন্ত বাড়ানো যেতে পারে, যখন অন্যান্য সম্পর্কহীন থ্রেডগুলি শেষ হওয়ার নিশ্চয়তা দেওয়া হয় (গ্যারান্টির কারণে যে একটি থ্রেড সর্বদা সমাপ্তির জন্য চলবে)। আরও সম্প্রসারণ সমান্তরালতা বাড়ানোর জন্য অতিরিক্ত যুক্তি জড়িত করার জন্য এটি আরও প্রসারিত করা যেতে পারে যেখানে অস্থায়ী অচলাবস্থা অন্যথায় ঘটতে পারে। কিন্তু আরও যুক্তি যোগ করার প্রতিটি ধাপের জন্য, আমরা আরও ওভারহেড যোগ করি। কয়েকটি উদাহরণের মধ্যে রয়েছেঃ বিদ্যমান লকগুলির প্রতিটি উপসেট বিবেচনা করার জন্য বিতরণকৃত সুপার-থ্রেড লকিং প্রক্রিয়া সম্প্রসারণ; ওয়েট-ফর-গ্রাফ (ডাব্লুএফজি) অ্যালগরিদম, যা ডেডলক সৃষ্টি করে এমন সমস্ত চক্রকে ট্র্যাক করে (অস্থায়ী ডেডলক সহ); এবং হিউরিস্টিক্স অ্যালগরিদম যা অস্থায়ী ডেডলক সম্ভব এমন জায়গাগুলির 100%-এ সমান্তরালতা বৃদ্ধি করে না, তবে পরিবর্তে পর্যাপ্ত জায়গায় সমাধান করে আপস করে যাতে পারফরম্যান্স/ওভারহেড বনাম সমান্তরালতা গ্রহণযোগ্য হয় (যেমন। উপলব্ধ প্রতিটি প্রসেসরের জন্য, প্রসেসরের সংখ্যা + 1 গভীরের চেয়ে কম অচল চক্র খুঁজে বের করার দিকে কাজ করুন)। রেফারেন্স বিতরণকৃত কম্পিউটিং