আমাদের কথা খুঁজে নিন

   

প্রোগ্রামাররা আসুন, সলভ করি : প্রসেস শিডিউলিং এর চতুর্থ এ্যালগোরিদম রাউন্ড রবিন

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

প্রোগ্রামে আপনাকে প্রথমেই বলে দেওয়া হবে যে কতটি প্রসেস দেওয়া হবে। অতঃপর আপনি প্রতিটি প্রসেসর জন্য নিচের মতো করে ইনপুট নিবেন। Arrival | Process | Burst Time 0--------|--- 1 -----| ----- 3 ------ 1--------|--- 2 -----| ----- 2 ------ 2--------|--- 3 -----| ----- 1 ------ Quantum = 2 Second রাউন্ড রবিন কিছুটা ফার্স্ট কাম ফার্স্ট সার্ভড এর মতো। পার্থক্য হলো এখানে সিপিইউ প্রতিটা প্রসেসের একটা নির্দিস্ট পরিমাণ কাজ এক বারে করবে, তারপর নেক্সট প্রসেস এন্ড সো অন...সব শেষ হলে অর্থাত ফ্রি হলে আবার প্রথম প্রসেসে আসবে কাজ বাকি থাকলে আবার নির্দিস্ট পরিমাণ কাজ করবে এবং চলতে থাকবে। এই নির্দিষ্ট পরিমাণটাই হলো কোয়ান্টাম।

এখানে কোয়ান্টাম ২ সেকেন্ড এবং এটা নির্দিস্ট নয়, ভ্যারী করতে পারে। টেস্ট ইনপুট এ বড়জোড় ৫-৬ টা প্রসেস দেওয়া হবে। বার্স্ট টাইম হলো টাইম ইউনিট, ধরতে পারেন সেকেন্ড। সেই হিসেবে এখানে প্রসেস-১ করবে ৩ সেকেন্ড কাজ , প্রসেস-২ করবে ২ সেকেন্ড কাজ, প্রসেস-৩ করবে ১ সেকেন্ড কাজ । নিচের বর্ণনা থেকেই বুঝতে পারবেন যে সিপিইউ কিভাবে কাজ করছে।

০ তম সেকেন্ড: এই সময় একটিই কাজ আছে। তা হলো প্রসেস-১ যার বার্স্ট টাইম ৩ সেকেন্ড । সিপিইউ ১ কোয়ান্টাম অর্থাত ২ সেকেন্ডের কাজ করবে প্রসেস-১ এর । তাহলের প্রসেস-১ এর কাজ বাকি থাকে ১ সেকেন্ড। বর্তমান সময় ২ তম সেকেন্ড কারণ, ০ তম আর ১ তম সেকেন্ডে সিপিইউ প্রসেস-১ এর ২ সেকেন্ডের কাজ করছে।

২ তম সেকেন্ড: এই সময় ৩ টি কাজ হলো। প্রসেস-১ এসেছে ০ তম সেকেন্ডে, কাজ আছে ১ সেকেন্ডের প্রসেস-২ এসেছে ১ তম সেকেন্ডে, কাজ আছে ২ সেকেন্ডের প্রসেস-৩ এসেছে ২ তম সেকেন্ডে, কাজ আছে ১ সেকেন্ডের এর আগের বার কাজ হইছে প্রসেস-১ এর তাই এবার কাজ হবে প্রসেস-২ এর। ১ কোয়ান্টাম (২ সেকেন্ডের) কাজ হবে প্রসেস-২ এর। প্রসেস-২ এর বাকি থাকলো ০ সেকেন্ডের কাজ, অর্থাত কাজ শেষ। বর্তমান সময় ৪ তম সেকেন্ড কারণ, ২ তম আর ৩ তম সেকেন্ডে সিপিইউ প্রসেস-২ এর ২ সেকেন্ডের কাজ করছে।

৪ তম সেকেন্ডে: এই সময় ২ টি কাজ হলো প্রসেস-১ এসেছে ০ তম সেকেন্ডে, কাজ আছে ১ সেকেন্ডের প্রসেস-৩ এসেছে ২ তম সেকেন্ডে, কাজ আছে ১ সেকেন্ডের এর আগের বার কাজ হইছে প্রসেস-২ এর তাই এবার কাজ হবে প্রসেস-৩ এর। কিন্তু প্রসেস-৩ এর কাজ ১ সেকেন্ডর। অর্থাত কোয়ান্টাম এর চাইতে কম। সিপিইউ কোয়ান্টাম সময় বা তার চেয়ে কম সময় এর কাজ এক বারে করতে পারে কিন্তু বেশি পারে না। তাই প্রসেস-৩ এর ১ সেকেন্ডের কাজ হবে।

প্রসেস-৩ এর বাকি থাকলো ০ সেকেন্ডের কাজ, অর্থাত কাজ শেষ। বর্তমান সময় ৫ তম সেকেন্ড কারণ, ৪ তম সেকেন্ডে সিপিইউ প্রসেস-৩ এর ১ সেকেন্ডের কাজ করছে। ৫ তম সেকেন্ড: এই সময় কোন কাজ নাই, তাই আগের কোন কাজ বাকি আছে কিনা তা চেক করা হবে। সেক্ষেত্রে সিপিইউ দেখবে যে প্রসেস-১ এর ১ সেকেন্ডের কাজ বাকি আছে। তাই প্রসেস-১ এর ১ সেকেন্ডের কাজ হবে।

----------------------------------------সব কাজ শেষ। কিন্তু দেখা যাচ্ছে। প্রসেস-১ এসেছিলো ০ তম সেকেন্ডে ৩ সেকেন্ডের কাজ নিয়ে। অর্থাৎ তার কাজ ০তম, ১ম, ২য় এই ৩ সেকেন্ডে শেষ হওয়ার কথা। কিন্তু তা না হয়ে শেষ হলো ৫ম সেকেন্ডে।

তার সময়সীমা হলো তাহলে ০তম, ১ম, ২য়, ৩য়, ৪র্থ, ৫ম এই ৬ সেকেন্ড। কিন্তু তার কাজ ছিলো ৩ সেকেন্ডের। অর্থাৎ সে ৩ সেকেন্ড ওয়েট করছে। প্রসেস-২ এসেছিলো ১ তম সেকেন্ডে ২ সেকেন্ডের কাজ নিয়ে। তার কাজ হওয়ার কথা ১ম ও ২য় সেকেন্ডে।

কিন্তু হইছে ২য় এবং ৩য় সেকেন্ডে। অর্থাত এর সময়সীমা ১ম, ২য়, ৩য় সেকেন্ড এই ৩ সেকেন্ডে। কিন্তু কাজ ২ সেকেন্ডের। অতএব প্রসেস-২ ১ সেকেন্ড ওয়েট করছে। প্রসেস-৩ এসেছিলো ২ তম সেকেন্ডে ১ সেকেন্ডের কাজ নিয়ে।

অর্থাৎ তার কাজ ২ তম সেকেন্ডেই শেষ হওয়ার কথা। কিন্তু তা না হয়ে শেষ হলো ৪র্থ সেকেন্ডে। তার সময়সীমা হলো তাহলে ২য়, ৩য়, ৪র্থ এই ৩ সেকেন্ড। কিন্তু তার কাজ ছিলো ১ সেকেন্ডের। অর্থাৎ সে ২ সেকেন্ড ওয়েট করছে।

তাহলে দাঁড়ালো যে মোট ওয়েটিং টাইম = ৩+১+২ = ৬ গড় ওয়েটিং টাইম দাঁড়ালো = (৬/৩) = ২ এই পুরো আউটপুট আপনাকে নিম্নরূপে দেখাতে হবে ব্যাতিক্রম: এ বার নিচের ইনপুট ধরুন, Arrival | Process | Burst Time 0--------|--- 1 -----| ----- 6 ----- 55-------|--- 2 -----| ----- 2 ---- 60-------|--- 3 -----| ----- 1 ---- Quantum = 2 Second প্রসেস-১ এর ১ কোয়ান্টাম কাজ হবে ০ তম আর ১ তম সেকেন্ডে। বাকি থাকে ৪ সেকেন্ড। বর্তমান সময় ২ তম সেকেন্ড। কিন্তু ২ তম সেকেন্ডে কোন কাজ নাই। তাই সিপিইউ প্রথম থেকে শুরু করবে আর প্রসেস-১ এর আরো ১ কোয়ান্টাম কাজ হবে ২ তম আর ৩ তম সেকেন্ডে।

বাকি থাকে ২ সেকেন্ড। বর্তমান সময় ৪ তম সেকেন্ড। কিন্তু ৪ তম সেকেন্ডে কোন কাজ নাই। তাই সিপিইউ প্রথম থেকে শুরু করবে আর প্রসেস-১ এর আরো ১ কোয়ান্টাম কাজ হবে ৪ তম আর ৫ তম সেকেন্ডে। বাকি থাকে ০ সেকেন্ড।

বর্তমান সময় ৬ তম সেকেন্ড। ৬ তম সেকেন্ডে কোন কাজ নাই, শুরুতে ফিরে গিয়েও দেখা যাচ্ছে প্রসেস-১ এর কাজও শেষ। অতএব ৬ তম সেকেন্ড থেকে ৫৪ তম সেকেন্ড পর্যন্ত সিপিইউ আইডেল থাকবে। ৫৫ এবং ৫৬ তম সেকেন্ডে প্রসেস-২ এর ১ কোয়ান্টাম কাজ করবে, এতে প্রসেস-২ এর কাজ শেষ হবে। ফলে কাজ না থাকায় সিপিইউ ৫৭ তম থেকে ৫৯ তম সেকেন্ড পর্যন্ত আইডেল থাকবে।

৬০ তম সেকেন্ডে প্রসেস-৩ এর ১ কোয়ান্টাম কাজ হবে। এবং সব কাজ শেষ হবে। এখানে কোন প্রসেসকেই ওয়েট করতে হয় নাই তাই মোট ওয়েটিং টাইম ০, এভারেজ ওয়েটিং টাইমও ০. নীচের স্ক্রিনশটটি দেখুন। ওকে, বলে রাখি ইনপুট আউটপুট এক্সেসপশন নিয়ে মাথা ঘামানোর দরকার নাই, উল্টাপাল্টা ইনপুট দেওয়া হবে না। প্রসেসের নাম্বার সিরিয়ালি দেওয়া হবে, ১,২,৩...করে।

একটি প্রসেসের এ্যারাইভাল টাইম তার আগের প্রসেসের এ্যারাইভাল টাইমের সমান বা তার চেয়ে বড় হতে পারে। বার্স্ট টাইমও ১০-১৫ এরকমই দেওয়া হবে আরকি। আমার করা প্রোগ্রামটি এই লিংক থেকে ডাউনলোড করতে পারেন। পুরো এক্সপ্ল্যানাশেন এর জন্য এই লিংকে যান। ----------------------------এর আগের ৩ টা প্রবেলেম এই লিংকে "ফার্স্ট কাম ফার্স্ট সার্ভড" - বাংলায় - ব্রিফ "ফার্স্ট কাম ফার্স্ট সার্ভড" - ইংরেজীতে - ডিটেইলস "শর্টেস্ট জব ফার্স্ট" - বাংলায় - ব্রিফ "শর্টেস্ট জব ফার্স্ট" - ইংরেজীতে - ডিটেইলস "প্রাওরিটি শিডিউলিং"- বাংলায় - ব্রিফ "প্রাওরিটি শিডিউলিং" - ইংরেজীতে - ডিটেইলস ।

অনলাইনে ছড়িয়ে ছিটিয়ে থাকা কথা গুলোকেই সহজে জানবার সুবিধার জন্য একত্রিত করে আমাদের কথা । এখানে সংগৃহিত কথা গুলোর সত্ব (copyright) সম্পূর্ণভাবে সোর্স সাইটের লেখকের এবং আমাদের কথাতে প্রতিটা কথাতেই সোর্স সাইটের রেফারেন্স লিংক উধৃত আছে ।