Deadlocks & Synchronization Interview Questions

Deadlock এবং Synchronization হলো মাল্টি-থ্রেডেড প্রোগ্রামিং এবং OS-এর সবচেয়ে জটিল বিষয়। এখানে ক্লাসিকাল প্রবলেম এবং ইন্টারভিউ প্রশ্নগুলো আলোচনা করা হলো।

Core Concepts (Deadlock)

Q1: Banker's Algorithm বাস্তবে কেন OS-এ ব্যবহার করা হয় না?

Answer: Banker's Algorithm ব্যবহার করে ডেডলক এড়ানো (Deadlock Avoidance) সম্ভব, কিন্তু এটি আধুনিক OS-এ (Windows/Linux) ব্যবহার করা হয় না। Reason:

1. প্রসেস শুরু হওয়ার আগেই তাকে বলতে হয় ম্যাক্সিমাম কত রিসোর্স লাগবে, যা বাস্তবে অসম্ভব (Dynamic memory allocation)।
2. প্রসেসের সংখ্যা ফিক্সড হতে হয়, কিন্তু রিয়েল সিস্টেমে প্রসেস ডায়নামিকালি তৈরি হয়।
3. এটি অনেক বেশি ওভারহেড তৈরি করে (প্রতিটি রিকোয়েস্টে সেফটি চেক করতে হয়)। আধুনিক OS সাধারণত Ostrich Algorithm ব্যবহার করে (Deadlock হবে না ধরে নেয়, হলে ইউজার রিস্টার্ট করবে বা প্রসেস কিল করবে)।

Q2: Deadlock Prevention এবং Avoidance-এর পার্থক্য কী?

Answer:

• Prevention: ডেডলক হওয়ার ৪টি শর্তের (Mutual Exclusion, Hold & Wait, No Preemption, Circular Wait) যেকোনো একটিকে অসম্ভব করে দেওয়া। (Rule-based, system restrictions)।
• Avoidance: OS প্রতিটি রিসোর্স রিকোয়েস্ট চেক করে দেখে যে এটি গ্রান্ট করলে সিস্টেম "Unsafe State"-এ যাবে কিনা। (Decision-based, e.g., Banker's Algorithm)।

Q3: Spinlock কি? কখন Mutex-এর বদলে Spinlock ব্যবহার করবেন?

Answer:

• Spinlock: এটি একটি লক যেখানে থ্রেড লক না পাওয়া পর্যন্ত লুপে (busy-wait) ঘুরতে থাকে। এটি CPU সাইকেল খরচ করে কিন্তু কনটেক্সট সুইচ করে না।
• Mutex: লক না পেলে থ্রেড স্লিপ (sleep) করে এবং OS তাকে ওয়েটিং কিউতে ফেলে দেয় (Context switch হয়)। Use Case: যদি Critical Section খুব ছোট হয় (কয়েক ইনস্ট্রাকশন) এবং লকের জন্য বেশিক্ষণ ওয়েট করতে না হয়, তবে Spinlock ব্যবহার করা ভালো কারণ Context Switching-এর ওভারহেড Spinlock-এর চেয়ে বেশি হতে পারে। (Kernel development-এ বেশি ব্যবহৃত হয়)।

---

Classical Synchronization Problems

Q4: Dining Philosophers Problem-এর সমাধান কী?

Problem: ৫ জন ফিলোসফার গোল টেবিলে বসে আছেন। ৫টি চপস্টিক আছে। খেতে হলে দুপাশের দুটি চপস্টিক লাগে। সবাই যদি একসাথে বাম পাশের চপস্টিক তোলে, তবে ডেডলক হবে। Answer:Solution (Resource Hierarchy): চপস্টিকগুলোতে নম্বর দেওয়া হবে (1 থেকে 5)।

• নিয়ম: সবাইকে প্রথমে ছোট নম্বরের চপস্টিক তুলতে হবে, তারপর বড় নম্বরের।
• উদারহণ: ফিলোসফার ৪ (চপস্টিক ৪, ৫) এবং ফিলোসফার ৫ (চপস্টিক ১, ৫)।
  • ফিলোসফার ৪ তুলবে চপস্টিক ৪।
  • ফিলোসফার ৫ তুলবে চপস্টিক ১ (৫ না, কারণ ১ < ৫)।
  • এতে সার্কুলার ওয়েট ভেঙে যাবে এবং ডেডলক হবে না।

Q5: Readers-Writers Problem এবং Priority Inversion কী?

Question: একটি ডাটাবেসে অনেক রিডার একসাথে পড়তে পারে, কিন্তু রাইটার আসলে বাকিদের ব্লক করতে হয়। যদি অনবরত রিডার আসতে থাকে, রাইটার কি কখনো সুযোগ পাবে? Answer: একে Writer Starvation বলে। Solution: রাইটার আসলে নতুন রিডারদের ব্লক করে দিতে হবে যতক্ষণ না রাইটারের কাজ শেষ হয়।

Priority Inversion: ধরি, লো প্রায়োরিটি টাস্ক (L) একটি রিসোর্স লক করেছে। হাই প্রায়োরিটি টাস্ক (H) সেই রিসোর্সের জন্য ওয়েট করছে। মিডিয়াম প্রায়োরিটি টাস্ক (M) এসে L-কে প্রিম্পট করে দিল। ফলে L লক ছাড়তে পারছে না, এবং H অনন্তকাল ওয়েট করছে। মনে হচ্ছে M-এর প্রায়োরিটি H-এর চেয়ে বেশি! Solution: Priority Inheritance Protocol (L-কে সাময়িকভাবে H-এর প্রায়োরিটি দেওয়া হয় যাতে সে দ্রুত কাজ শেষ করে লক ছাড়তে পারে)।

Q6: Producer-Consumer Problem-এ বাফার সাইজ ১ হলে কী হবে?

Answer: তখন একে Binary Semaphore বা Mutex দিয়ে সলভ করা যায়। বাফার সাইজ ১ মানে আসলে এটি একটি Ping-Pong কমিউনিকেশন। Producer ডেটা রেখে সিগন্যাল দিবে, Consumer ডেটা নিয়ে সিগন্যাল দিবে।

---

Scenario-Based Questions

Scenario 1: Deadlock Recovery

Q: একটি ডাটাবেস সিস্টেমে ডেডলক ডিটেক্ট হয়েছে। আপনি রিকভার করবেন কীভাবে? Answer: রিকভারির জন্য কয়েকটি স্ট্র্যাটেজি আছে:

1. Process Termination:
   • সব ডেডলকড প্রসেস কিল করা (সহজ কিন্তু ডেটা লস হতে পারে)।
   • একে একে প্রসেস কিল করা যতক্ষণ না ডেডলক ভাঙ্গে (কম ক্ষতিকর প্রসেস আগে)।
2. Resource Preemption:
   • কোনো প্রসেস থেকে রিসোর্স জোর করে কেড়ে নিয়ে অন্যকে দেওয়া (Rollback করতে হয়)।

Scenario 2: Mars Pathfinder Bug

Q: ১৯৯৭ সালে Mars Pathfinder ল্যান্ড করার পর বারবার রিসেট হচ্ছিল। এটি ছিল একটি ক্লাসিক রিয়েল-টাইম OS সমস্যা। এটি কী ছিল? Answer: এটি ছিল একটি Priority Inversion সমস্যা।

• একটি লো প্রায়োরিটি মেটিওরোলজিক্যাল টাস্ক বাস (Bus) লক করেছিল।
• একটি হাই প্রায়োরিটি টাস্ক বাসের জন্য ওয়েট করছিল।
• একটি মিডিয়াম প্রায়োরিটি টাস্ক লো প্রায়োরিটি টাস্ককে থামিয়ে দিচ্ছিল। ফলে হাই প্রায়োরিটি টাস্ক টাইমআউট হচ্ছিল এবং সিস্টেম রিসেট করছিল। Fix: ইঞ্জিনিয়াররা পৃথিবী থেকে কোড প্যাচ করে Priority Inheritance অন করে দিয়েছিল।

Scenario 3: Volatile Keyword in C

Q: মাল্টি-থ্রেডেড প্রোগ্রামিংয়ে volatile কীওয়ার্ড এবং Mutex এর সম্পর্ক কী? volatile কি থ্রেড সেফটি দেয়? Answer: না, volatile থ্রেড সেফটি বা অ্যাটমিক অপারেশন নিশ্চিত করে না।

• এটি কম্পাইলারকে বলে যে ভেরিয়েবলটি যেকোনো সময় হার্ডওয়্যার বা অন্য থ্রেড দ্বারা চেঞ্জ হতে পারে, তাই একে রেজিস্টারে ক্যাশ না করে সরাসরি মেমোরি থেকে পড়তে হবে (Visibility)।
• Race Condition আটকাতে Mutex বা Atomic ব্যবহার করতেই হবে।