Operating Systems – Deadlocks

মাল্টিপ্রোগ্রামিং এনভায়রনমেন্ট একাধিধক প্রসেস নির্দিষ্ট কিছু রিসোর্স ব্যবহার করার জন্য একপ্রকার যুদ্ধ করে থাকে। :-p প্রথমে একটি প্রসেস রিসোর্সকে রিকুয়েস্ট করে, যদি রিসোর্সটি ফাঁকা না থাকে তাহলে রিসোর্স ফাঁকা না হওয়া পর্যন্ত প্রোসেসটি ওয়েটিং স্টেটে থাকে। অনেক সময় প্রোসেসটিকে আজীবন অপেক্ষা করতে হতে পারে। এধরনের অবস্থাকে ডেডলক বলে।

System Model

একটি সিস্টেমে কিছু নির্দিষ্ট সংখ্যক রিসোর্স থাকে। এই রিসোর্সগুলো বিভিন্ন প্রসেসের মাধ্যমে ডিস্ট্রিবিউট করা হয়ে থাকে। রিসোর্সগুলো বিভিন্ন ধরনের হতে পারে। আবার প্রতিটি রিসোর্সের ধরনের আবার অনেকগুলো ইনস্ট্যান্স থাকতে পারে। মেমোরি স্পেস, সিপিউ সাইকেল, ফাইল I/O ডিভাইস প্রভৃতি বিভন্ন ধরনের রিসোর্স টাইপ। যদি কোনো সিস্টেমের দুটি সিপিউ থাকে তাহলে বলা যায় CPU রিসোর্স টাইপের দুই ধরনের ইন্সট্যান্স রয়েছে। একই ভাবে কোনো কোনো সিস্টেমের ৫টি প্রিন্টার টাইপের রিসোর্স থাকতে পারে।

কোনো একটি রিসোর্স ব্যবহার করার আগে অবশ্যই সেই রিসোর্সকে রিকুয়েস্ট করতে হবে। এবং রিসোর্সটি ব্যবহার করার পর তা ছেড়ে (release) দিতে হবে। একটি প্রসেস একাধিক রিসোর্সকে রিকুয়েস্ট করে ব্যবহার করতে পারে। তবে তা অবশ্যই মোট রিসোর্সের সংখ্যার বেশি না। যেমন, একটি সিস্টেমের ২ টি প্রিন্টার থাকলে অবশ্যই ৩টি প্রিন্টার রিকুয়েস্ট করা যাবে না।

সাধরনত, একটি প্রোসেস নিচের সিকুয়েন্সে রিসোর্স ব্যবহার করে থাকে।

1. Request: প্রথমে প্রসেস একটি রিসোর্সকে রিকুয়েস্ট করে থাকে। যদি রিকুয়েস্টটি এই মুহুর্তে গ্রান্ট করা সম্ভব না হয় (উদাহরনসরূপ, রিসোর্সটি অন্য কোনো প্রসেস দ্বারা ব্যবহৃত হচ্ছে), তাহলে রিকুয়েস্টকারী প্রসেসকে রিসোর্সটি ফাঁকা না হওয়া পর্যন্ত অপেক্ষা করতে হবে।
2. Use: প্রসেসটি এরপর রিসোর্সটিকে ব্যবহার করতে পারবে। উদাহরনসরূপ, যদি রিসোর্সটি প্রিন্টার হয়ে থাকে তাহলে কোনো ডকুমেন্ট প্রিন্ট করতে পারবে।
3. Release: ব্যবহার শেষে প্রসেসটি রিসোর্সটিকে রিলিজ / মুক্ত করে দেয়।

Deadlock Conditions

সিস্টেমে ডেডলক হতে পারে যদি কোনো সিস্টের নিচের চারটি শর্ত বারবার ঘটতে থাকে।

1. Mutual exclusion: নূন্যতম একটি রিসোর্সকে অবশ্যই non-shareable mode এ থাকতে হবে, অর্থাৎ একই সময়ে শুধুমাত্র একটি প্রসেস রিসোর্স ব্যবহার করতে পারবে। যদি অন্য কোনো প্রসেস রিসোর্সটিকে রিকুয়েস্ট করে, তাহলে রিকুয়েস্টকারী প্রসেসকে অবশ্যই রিসোর্সটি রিলিজ না হওয়া পর্যন্ত অপেক্ষা করতে হবে।
2. Hold and wait: একটি প্রোসেস অবশ্যই বর্তমানে একটি রিসোর্স ব্যবহার করছে এবং আরেকটি রিসোর্স ব্যবহার করার জন্য অপেক্ষা করছে যা বর্তমানে অন্য কোনো প্রসেস দ্বারা ব্যবহৃত হচ্ছে।
3. No preemption: রিসোর্সগুলোকে যে কোনো সময় ফ্রি করা যাবে না (cannot be preempted) অর্থাৎ, একটি রিসোর্স টাস্ক শেষ হবার পর শুধুমাত্র যে প্রোসেসটি দ্বারা ব্যবহৃত হচ্ছে সেই প্রসেস দ্বারাই রিলিজ হতে পারে।
4. Circular wait: প্রসেসের একটি সেট {P₀, P₁, ….., P_n} এমন ভাবে ওয়েটিং এ থাকবে যেনো P₀, P₁ যে রিসোর্সটি ব্যবহার করছে তা ফাঁকা হবার জন্য অপেক্ষা করছে, P₁, P₂ এর জন্য… এভাবে P_n, P₁ এর দ্বারা ব্যবহারকৃত রিসোর্স ফাঁকা হবার জন্য অপেক্ষা করবে।

Resource Allocation Graph

ডেডলককে System Resource-Allocation Graph নামক একটি ডিরেক্টেড গ্রাফের মাধ্যমে খুব সহজে বর্ণনা করা যায়। এই গ্রাফে ভার্টিক্সের সেট V এবং এজের সেট E থাকে। V এর সেটটি দুটি ভিন্ন ধরনের টাইপের নোডে বিভক্ত থাকে; একটি সেট P = {P₁, P₂ …. P_n} থাকবে, যেটি সিস্টেমের সকল অ্যাকটিভ প্রসেসের সেট এবং R = {R₁, R₂, …, R_m} হলো রিসোর্সের সেট।

P_i প্রোসেস থেকে R_j রিসোর্সের মধ্যে ডিরেক্টেড এজ P_i→R_j দ্বারা চিহ্ণিত করা হয়। এর মানে হলো P_i প্রসেসটি R_j রিসোর্সটি ব্যবহার করার জন্য রিকুয়েস্ট করেছে এবং বর্তমানে রিসোর্সটি ব্যবহার করার জন্য অপেক্ষা করছে। R_j রিসোর্স থেকে P_i প্রোসেসের মধ্যে ডিরেক্টেড এজ R_j→P_i দ্বারা চিহ্ণিত হয়। এর মানে হলো R_j রিসোর্সটি P_i প্রোসেসটিকে ব্যবহার করার জন্য অ্যালোকেট করা হয়েছে। P_i→R_j এজকে বলা হয় Request Edge এবং R_j→P_i এজকে বলা হয় Assignment Edge.

গ্রাফিকালি, প্রতিটি প্রোসেসসকে একটি বৃত্ত আকারে প্রকাশ করা হয় এবং প্রতিটি রিসোর্স টাইপকে আয়ত হিসেবে প্রকাশ করা হয়। রিসোর্স টাইপের একাধিক ইন্সট্যান্স থাকলে প্রতিটি ইন্সট্যান্সকে বিন্দু হিসেবে প্রকাশ করা হয়। বিন্দুগুলো ঐ রিসোর্স টাইপের আয়তের মধ্যে থাকবে। রিকুয়েস্ট এজ আয়তের দিকে পয়েন্ট করবে এবং অ্যালোকেশন এজ বিন্দু থেকে শুরু হবে।

যখন কোনো প্রোসেস Pi কোনো একটি রিসোর্স Rj এর একটি ইন্সটান্সকে রিকুয়েস্ট করে তখন রিসোর্স অ্যালেকেশন গ্রাফে একটি রিকুয়েস্ট এজ আঁকা হয়। যখন এই রিকুয়েস্ট গ্রান্ট করা হয়, তখনই এই রিকুয়েস্ট এজটি অ্যাসাইনমেন্ট এজে রূপান্তরিত হয়। যখন রিসোর্সটি আর প্রয়োজন হয় না তখন এই অ্যাসাইনমেন্ট এজটি মুছে ফেলা হয়।

নিচে একটি রিসোর্স অ্যালোকেশন গ্রাফ দেখানো হলোঃ

উপরের গ্রাফের সেট P, R এবং E হলোঃ

• P = {P1, P2, P3}
• R = {R1, R2, R3, R4}
• E = {P1→R1, P2→R3, R1→P2, R2→P2, R2→P1, R3→P3}

রিসোর্সসমূহের ইনস্টান্সগুলো হলোঃ

• R1 রিসোর্স টাইপের একটি ইন্সট্যান্স
• R2 রিসোর্স টাইপের দুইটি ইন্সট্যান্স
• R3 রিসোর্স টাইপের একটি ইন্সট্যান্স
• R4 রিসোর্স টাইপের তিনটি ইন্সট্যান্স

প্রোসেসসমূহের স্টেটঃ

• P1 প্রোসেসটি R2 রিসোর্সের একটি ইন্সট্যান্স ব্যবহার করছে এবং R1 রিসোর্স ব্যবহার করার জন্য অপেক্ষা করছে।
• P2 প্রোসের্সটি R1 এবং R2 রিসোর্সের একটি করে মোট দুটি ইন্সট্যান্স ব্যবহার করছে এবং R3 রিসোর্সের জন্য অপেক্ষা করছে।
• P3 প্রোসেসটি R3 এর একটি ইন্সট্যান্স ব্যবহার করছে।

উক্ত গ্রাফ থেকে এটা স্পষ্ট বোঝা যাচ্ছে যে,, গ্রাফটিতে কোনো প্রকার সাইকেল নেই এবং সিস্টেমের কোনো প্রোসেস ডেডলক অবস্থায় নেই। যদি গ্রাফটিতে সাইকেল থাকতো তাহলে সিস্টেমে ডেডলক থাকতে পারতো।

Methods for Handling Deadlock

সিস্টেমে ডেডলক পরিস্থিতি সামাল দেওয়া যেতে পারে দুইটি উপায়েঃ

1. Deadlock Prevention: এ ব্যবস্থায় কিছু পদ্ধতি দেওয়া থাকে যার মাধ্যমে এটা নিশ্চিত করা হয় যে Deadlock এর যে সকল নেসেসিটি কন্ডিশন রয়েছে তার অন্তত একটি না ঘটে।
2. Deadlock Avoidance: এ ব্যবস্থায় অপারেটিং সিস্টেমকে কিছু অতিরিক্ত তথ্য দেওয়া হয়। এই তথ্যগুলোর মধ্যে আছে কোন প্রসেস কোন রিসোর্সকে এর লাইফটাইমে রিকুয়েস্ট করতে পারবে এবং তা ব্যবহার করতে পারবে।

Deadlock Prevention

সিস্টেমে ডেডলক হবার জন্য যে চারটি শর্ত রয়েছে তার যে কোনো একটি ঘটা থেকে যদি বিরত রাখা যায় তাহলে ডেডলককে প্রিভেন্ট করা সম্ভব। চারটি শর্ত আলাদাভাবে না ঘটার উপায় নিচে বর্ণনা করা হলো।

Mutual Exclusion: সিস্টেমে অবশ্যই মিউচাল এক্সক্লিউশন শর্তটি থাকতে হবে। কারন, নূন্যতম একটি রিসোর্স নন-শেয়ারেবল অবস্থায় থাকতে হবে। Read only ফাইলগুলো শেয়ারেবল হতে পারে। যে কোনো সময় একাধিক প্রোসেস রিড অনলি ফাইল রিড করতে পারবে। কিন্তু একই সময় একাধিক ফাইলে লেখার অনুমতি দেওয়া হয় না। বাস্তবে, Mutual Exclusion শর্তটি বন্ধ করা সম্ভব নয়। কারণ, কিছু রিসোর্স কখনই শেয়ারেবল হয় না। যেমন, প্রিন্টারকে একই সময়ে একাধিক প্রোসেস ব্যবহার করতে পারবে না।

Hold and Wait: যখন একটি প্রোসেস কোনো একটি রিসোর্সকে রিকুয়েস্ট করবে তখন যেনো অন্য কোনো রিসোর্স ব্যবহার না করে, এটি নিশ্চিত করলে Hold and Wait শর্তটি ঘটা থেকে বিরত রাখা সম্ভব। একটি প্রোটকল হলো প্রোসেস এক্সিকিউট হবার পূর্বেই সকল প্রয়োজনীয় রিসোর্সগুলো অ্যালোকেট করে নেওয়া। অথবা, একটি প্রোসেস তখনই একটি রিসোর্সকে রিকুয়েস্ট করবে যখন সে কোনো রিসোর্স ব্যবহার করছে না। একটি প্রোসেস কিছু সংখ্যক রিসোর্স ব্যবহার করতে পারে। কিন্তু নতুন রিসোর্সের জন্য রিকুয়েস্ট করার আগে বর্তমানে অ্যালোকেট করা রিসোর্সগুলোকে ফাঁকা করে দিতে হবে।

No Preemption: ডেডলকের তৃতীয় শর্ত হলো কোনো একটি প্রসেস বর্তমানে যে সকল রিসোর্স ব্যবহার করছে সেগুলোকে অন্য কেউ ফাঁকা করতে পারবে না। এই শর্তটি না ঘটার জন্য একটি পদ্ধতি অবলম্বন করা যেতে পারে। যদি একটি প্রোসেস কিছু সংখ্যক রিসোর্স ব্যবহার করছে এবং নতুন একটি রিসোর্স ব্যবহার করার জন্য রিকুয়েস্ট করছে কিন্তু তাৎক্ষনিকভাবে রিসোর্সটি অ্যালোকেট করা সম্ভব নয়, তাহলে প্রসেসটি যে সকল রিসোর্স ব্যবহার করছে সেগুলো ফাঁকা/রিলিজ করে দিতে হবে।

Circular Wait: সিস্টেমের রিসোর্সগুলোকে নাম্বার দিয়ে একটি নির্দিষ্ট অর্ডারে ব্যবহার করার মাধ্যমে Circular Wait শর্তটা ঘটা থেকে বিরত রাখা সম্ভব। ধরা যাক R = {R1, R2…. Rn} একটি রিসোর্স টাইপের সেট। আমরা প্রতিটি রিসোর্সের জন্য একটি স্বতন্ত্র (unique) নম্বর দিতে পারি। মূলত আমরা একটি ওয়ান-টু-ওয়ান ফাংশন F: R → N ডিফাইন করতে পারি, যেখানে N হলো বাস্তব সংখ্যার সেট। উদাহরন স্বরূপ আমাদের R গুলো যদি tape drive, disk drive, printer হয় তাহলে আমাদের F ফাংশনটি এভাবে ডিফাইন করতে পারিঃ

F(tape drive) = 1 F(disk drive) = 5 F(printer) = 12

এখন ডেডলক প্রিভেন্ট করার জন্য এই পদ্ধতি অনুসরণ করা যেতে পারেঃ প্রতিটি প্রোসেস শুরুতে যে কোনো রিসোর্স ব্যবহার করতে পারে। কিন্তু এর পরে সেই সকল রিসোর্সগুলোকে (Rj) রিকুয়েস্ট করতে পারবে যেগুলোর নম্বর বর্তমানে ব্যবহারকৃত রিসোর্সের (Ri) চেয়ে বেশি। অর্থাৎ F(Rj) > F(Ri) হতে হবে।

Deadlock Avoidance

একটি প্রোসেস কতোগুলো রিসোর্স রিকুয়েস্ট করতে পারবে, কতোগুলো রিসোর্স অ্যাভইলেবল আছে এবং কতোগুলো রিসোর্স ব্যবহার করছে এই তত্যগুলো ভিত্তিতে ডেডলক অ্যাভয়েড করা সম্ভব।

Safe State: একটি স্টেট safe স্টেটে আছে যদি সিস্টেম প্রতিটি প্রসেসকে একটি নির্দিস্ট অর্ডারে রিসোর্স অ্যালোকেট করতে পারবে এবং এটা সত্তে্ও সিস্টেমে কোনো ডেডলকের সৃষ্টি হবে না। Safe State এ কখনও ডেডলকের সৃষ্টি হয় না। অনুরূপভাবে, unsafe স্টেটে ডেডলকের সৃষ্টি হতে পারে।

Banker’s Algorithm

যখন একটি প্রসেস সিস্টেমে প্রবেশ করবে তখন অবশ্যই একে প্রতিটি রিসোর্সের সর্বোচ্চ কত সংখ্যক ইন্সট্যান্স ব্যবহার করতে প্রয়োজন হতে পারে তা বলে দিতে হবে। যদি এই রিসোর্সগুলো অ্যালোকেট করার পর সিস্টেম সেফটি স্টেটে থাকবে তাহলে রিসোর্সগুলো অ্যালোকেট হবে অনথ্যায় প্রসেসটি ওয়েটিং স্টেটে থাকবে।

ব্যাংকার অ্যালগরিদম ইম্প্লিমেন্ট করার জন্য ৪ ধরনের ডাটা স্ট্রাকচার ব্যবহার করা হয়। একটি সিস্টেমে প্রোসেসের সংখ্যা n এবং রিসোর্সের সংখ্যা m থাকতে পারে।

• Available: এটি একটি m সাইজের ভেক্টর (অ্যারে)। যদি Available[j] = k হয় তাহলে বুঝে নিতে হবে Rj তম রিসোর্সের k সংখ্যক ইন্সট্যান্স অ্যাভয়লেবল আছে।
• Max: এটি একটি nxm ম্যাট্রিক্স। Max[i][j] = k হলে Pi প্রোসেস Rj রিসোর্সের সর্বোচ্চ k সংখ্যক ইন্সট্যান্সকে রিকুয়েস্ট করতে পারে।
• Allocation: এটি একটি nxm ম্যাট্রিক্স। Allocation[i][j] = k হলে Pi প্রোসেস Rj রিসোর্সের k সংখ্যক ইন্সট্যান্সকে ব্যবহার করছে।
• Need: এটি একটি nxm ম্যাট্রিক্স। Need[i][j] = k হলে Pi প্রোসেসটি সম্পন্ন করতে Rj রিসোর্সের সর্বোচ্চ আরও k সংখ্যক ইন্সট্যান্সকে রিকুয়েস্ট করতে হবে। Need[i][j] = Max[i][j] – Allocation[i][j]

ব্যাংকার্স অ্যালগোরিদম ইম্প্লিমেন্টের জন্য সেফটি স্টেট চেকিং এর জন্য Safety Algorithm এবং রিসোর্স অ্যালোকেট করা যাবে কিনা তার জন্য Resource-Request Algorithm প্রয়োজন।

Safety Algorithm

বর্তমানে কোনো একটি সিস্টেম সেফটি স্টেটে আছে নাকি তা বোঝার জন্য নিচের অ্যালগরিদমটি ব্যবহার করা হয়ঃ

1. ধরি Work এবং Finish যথাক্রমে m and n দৈর্ঘ্যের দুটি ভেক্টর। Work = Available এবং Finish[i] = false for i = 0, 1, …, n – 1 দিয়ে ইনিশিয়ালাইজ করা হয়েছে।
2. এমন একটি ইনডেক্স i খুঁজে বের করতে হবে যেনো
   1. Finish[i] == false
   2. Need i ≤ Work যদি এরকম কোনো ইন্ডেক্স না পাওয়া যায় তাহলে 4 নং স্টেপে চলে যেতে হবে।
3. Work = Work + Allocation[i] Finish[i] = true স্টেপ ২ এ চলে যাও।
4. যদি প্রতিটি i এর জন্য Finish[i] == true হয় তাহলে সিস্টেমটি safe state এ আছে।

এই অ্যালগরিদমের কম্প্লেক্সিটি O(m x n^2)

Resource-Request Algorithm

রিসোর্সের জন্য রিকুয়েস্ট নিরাপদভাবে অনুমোদন করা যাবে কিনা তা নির্ণয় করার জন্য এই অ্যালরিদম ব্যবহার করা হয়ে থাকে। ধরা যাক Request[i], একটি প্রোসেস Pi এর জন্য রিকুয়েস্ট। যদি Request[i][j] == k হয় তাহলে প্রসেস Pi, রিসোর্স Rj এর k সংখ্যক ইন্সট্যান্স এর জন্য রিকুয়েস্ট করেছে। যখন এই রিকুয়েসট করা হয় তখন নিম্নেক্ত অ্যাকশনগুলো নেওয়া হয়ঃ

1. য়দি Request[i] <= Need[i] হয় তাহলে ২ নং স্টেপে চলে যাও। নতুবা একটি এরর দেখাও যেহেতু প্রয়োজনের চেয়ে রিকুয়েস্ট বেশি।
2. যদি Request[i] <= Available[i] হয় তাহলে ৩ নং স্টেপে চলে যাও। নতুবা একটি এরর দেখাও যেহেতু অ্যাভয়লেবল রিসোর্সের চেয়ে রিকুয়েস্ট বেশি।
3. এই স্টেটে আসার পর নিচের কাজগুলো করো: Available = Available – Request[i]; Allocation[i] = Allocation[i] + Request[i]; Need[i] = Need[i] – Request[i];

যদি এই ট্রান্জেকশনের পর সিস্টেম সেফ স্টেটে থাকে তাহলে ট্রান্জেকশনটি সম্পন্ন হবে। নতুবা সিস্টেমটি ট্রান্জেকশনের পূর্বের অবস্থায় রোল ব্যাক করবে।