درس‌هایی از سیستم عامل برای زندگی روزمره: الگوریتم‌های زمان‌بندی

نویسنده این مطلب در حال گذراندن درس سیستم‌عامل است.

به نظرم رسید که مفاهیم این درس بیش‌تر از مقداری که بهشان پرداخته می‌شود کاربردی هستند، نه لزوما در رشتهٔ کامپیوتر بلکه در زندگی روزمره.

چرا؟ در ادامه می‌بینیم.

تعریف ویکیپدیا:‌ سیستم عامل یا سامانهٔ عامل[۱] نرم‌افزار سیستمی ای است که مدیریت منابع رایانه را به عهده گرفته و بستری را فراهم می‌سازد که نرم‌افزار کاربردی اجرا شده و از خدمات آن استفاده کنند.

به زبان ساده یعنی سیستم‌عامل منابع کامپیوتر را در اختیار گرفته و کارهایی‌که باید انجام شوند (تسک‌ها) را مدیریت می‌کند یعنی به آن‌ها بسته به نیازشان منبع می‌دهد.

برای تشریح کاربرد‌ سیستم‌عامل در روزمره هم از همین واژه‌ها استفاده می‌کنم: یک سری کار برای انجام دادن داریم و یک سری منابع.

کار (task) که فکر نمی‌کنم ابهامی داشته باشد! مثلا تکلیف چهارم درس فلان، پروژه‌ای که برای خودم دارم و می‌خواهم با زبان X انجام دهم یا چیزی که کارفرما خواسته و تا آخر هفته باید تمام شود.

منبع (resource) یعنی امکاناتی که برای انجام کارها در اختیار داریم، مثلا زمان و سرمایه. اینجا بیشتر با زمان کار داریم. ولی می‌توانید برای چیزهای دیگر را هم منابع در نظر بگیرید مثلا فضای روی میز!

برای کامپیوتر فهمیدیم که چه کسی مسئول تخصیص منابع است، اما برای خودمان چی؟ متاسفانه (و البته خوشبختانه) کسی به این دقت برای ما برنامه‌ نمی‌ریزد و این کارِ خودِ ماست. کدام کار را انجام دهیم؟ کدام را انجام ندهیم؟ کدام را زودتر انجام دهیم چون واجب‌تر است و ...

سیستم عامل خودت باش

خب من به عنوان سیستم‌عامل خودم که قرار است تسک‌ها را مدیریت کنم، چطوری باید این کار را انجام بدهم؟

روش‌های مختلفی برای مدیریت‌ کار‌ها هست. من صرفا دو تا را که خودم شنیدم اینجا ذکر می‌کنم.

از طریق مشاور دبیرستانمان با ماتریس آیزنهاور آشنا شدم. این روش می‌گوید کار‌ها ۴ حالت دارند:

• مهم و فوری: باید به سرعت انجام شود.
• مهم و غیرفوری: باید انجام شود ولی زمانش چندان اهمیتی ندارد.
• غیرمهم و فوری: انجام شدنش برای شخص ما اهمیتی ندارد ولی زمان انجامش محدود است.
• غیرمهم و غیرفوری: اسمش گویا هست.

در صورتی که از این روش تبعیت کنیم کارهای مهم و فوری باید اول انجام شوند، سپس بین کارهای مهم و غیرفوری و غیرمهم و فوری تصمیم می‌گیریم و احتمالا به غیر مهم و غیر فوری نخواهیم رسید.

روش معروف دیگر که در کتاب clean coder با آن آشنا شدم، روش مدیریت زمان گوجه‌ای یا پومودرو است. در این روش، فرد کار‌ها را در بازه‌های زمانی ۲۵ دقیقه‌ای انجام می‌دهد. در آن ۲۵ دقیقه هیچ کار دیگری انجام نمی‌دهد. بعد از ۲۵ دقیقه چند دقیقه استراحت می‌کند و سپس ۲۵ دقیقه بعدی را شروع می‌کند.

این مثال‌ها را دیدید؟ این‌ها روش‌هاییست برای مدیریت زمان برای انجام کارها. دقیقا کاری که سیستم عامل در کامپیوتر شما انجام می‌دهد. (البته کار سیستم‌عامل بسیار بیشتر است، یکی از کارهایش CPU scheduling است.)

الگوریتم‌های اولویت‌دهی در سیستم‌عامل

از اسم این قسمت نترسید! قرار نیست حرف پیچیده‌ای بزنم! حداقل پیچیده‌تر از «عمیق نگاه کردن به زندگی روزمره».

توضیح مختصر پس‌گیرنده و پس‌نگیرنده

اگر زمانی که در حال انجام یک کار هستیم، تا زمانی که تمام نشده، با آمدن کارهای جدید، آن را متوقف نکنیم، می‌شود پس نگیرنده (non-Preemptive). اما اگر هنگامی که در حال یک کار هستیم با آمدن کار جدید به لیست کارها، سری هم به کار جدید بزنیم و یک دور لیست کار‌ها ها ورق بزنیم و بعد تصمیم بگیریم چه کاری را انجام دهیم، می‌شود پس‌گیرنده (preemptive). منظور از پس‌گیرنده این است که کاری که در حال اجرا بود را پس می‌دهیم و کار دیگری را برمی‌داریم اما در حالت پس‌نگیرنده کار گرفته شده تا وقتی کامل انجام نشود پس گرفته نمی‌شود.

الگوریتم‌های پس‌نگیرنده

• هرکاری اول آمده را زودتر انجام بده (first come first serve): منتظر بمان تا کاری بیاید، آن را انجام بده و دوباره ببین (به ترتیب آمدن) کار بعدی را انتخاب کن و انجام بده.
• کار کوتاه‌تر را زودتر انجام بده (shortest job first): بین کارها کاری را انتخاب کن که زمان کم‌تری برای انجام شدن نیاز دارد. با این ریسک که کار خیلی بلندی ممکن است هیچوقت انجام نشود.

الگوریتم‌های پس‌گیرنده

• کوتاه‌ترین زمان باقی‌مانده را اول انجام بده (shortest remaining time first): مثل حالت کار کوتاه‌تر است با این تفاوت که در زمانی که کار جدید بیاید (بدون توجه به اینکه کار فعلی انجام شده یا نشده) بررسی می‌کند و کاری که زمان باقی‌مانده کمتری دارد را انجام می‌دهد. مثلا یک کار ۲ ساعته دارم و یک ساعتش انجام شده، حالا یک کار نیم ساعته اضافه می‌شود. پس کار ۲ ساعته را رها می‌کنم و نیم ساعته را پیگیری می‌کنم. استفاده از این الگوریتم با این ریسک است که یک کار در لیست بماند و قدیمی و قدیمی‌تر شود.
• بالاترین نسبت پاسخ (highest response ratio next): برای حل مشکل قدیمی‌شدن، علاوه بر اولویت‌دادن به «کوتاه‌ترها»، به کار‌های «قدیمی‌تر» هم اولویت می‌دهیم تا کاری در صف برای مدت زیادی نماند.
• نوبت‌گردشی (round robin): به نظرم این روش خیلی به روش گوجه نزدیک است. روش کار به این صورت است که از هر کار مدت زمان معینی را انجام بده (مثلا همان ۲۵ دقیقه). سپس این کار را بگذار کنار و کار بعدی را ۲۵ دقیقه انجام بده. در این صورت همه کار‌ها در حال انجام شدن هستند.

در روش نوبت گردشی، دو نکته قابل توجه است.

• اول اینکه اگر کاری در صف است که اهمیت بیشتری‌دارد می‌توانیم چند نوبت به آن اختصاص دهیم، مثلا در طی یک گردش که از هر کدام از کارها ۲۵ دقیقه انجام می‌دهیم، از این کار دو یا چند نوبت انجام دهیم.
• نکته دوم اینکه برای انتخاب زمان مناسب (در مثال ما ۲۵ دقیقه) باید تعادلی برقرار کنیم بین دیر شدن کار‌ها (اگر ۱۰۰ کار داشته باشیم، بعد از ۲۵۰۰ دقیقه دوباره نوبت کار فعلی می‌شود!) و زمان کانتکست سوییچ.

کانتکست سوییچ؟

کانتکست‌سوییچ (context switch) یعنی زمانی که بین انجام کارها هدر می‌رود. یعنی زمانی که تصمیم می‌گیرم دست از کار۱ بکشم و به کار۲ بپردازم، زمانی در این بین هدر می‌رود. مثلا الان در حال نوشتن وبلاگ هستم (کار۱)، از زمانی که این کار‌ را رها کنم تا زمانی که شروع کنم و به صورت موثر برای امتحان فردا بخوانم (کار۲) می‌شود زمان context switch. این زمان برای کامپیوتر معمولا اندک و قابل چشم‌پوشی است ولی برای ما انسان‌ها نه! مثلا من تا جزوه را در بیاورم و شماره صفحه و فصل‌های مورد سوال و .. را پیدا کنم و اولین کلمه را بخوانم همه در زمان هدر رفته‌ی context switch هستند. اگر می‌خواهیم بازه‌های زمانی کوتاهی انتخاب کنیم باید حواسمان به این زمان هدر رفته باشد.

حالت چند‌صفی

ما قرار نیست همه کارهایمان را فقط در یک صف قرار دهیم بلکه می‌توانیم برای کار‌های ددلاین‌دار یک صف داشته‌باشیم و آن‌ها را بر اساس ددلاینشان زمان‌بندی کنیم و برای کار‌های بدون ددلاین (مثلا همان پروژه‌های شخصی) صف دیگری داشته باشیم. یا مثلا یک صف برای کارهای بزرگ و طولانی داشته‌باشیم و یک صف برای کارهای کوتاه که هر کدام جدا زمان‌بندی شوند. (Multi Queue)

در آخر باید تصمیم بگیریم که چقدر از زمان را به هر صف بدهیم. مثلا ۷۰ درصد برای کارهای مهم (ضروری و غیرضروری) و ۳۰ درصد برای کارهای غیرمهم.

حتی می‌توانیم بسته به شناخت از خودمان ساعت‌های پربازده را به یک‌سری کار بپردازیم و ساعات کم‌بازده را به یک سری کار دیگر. داشتن صف‌های جدا در این مورد خیلی کمک‌کننده است.

بازخورد گرفتن هم بسیار مهم است، مثلا می‌توانیم با بازخوردی که از کارایی یک کار در یک تسک داشتیم، تصمیم بگیریم در صف دیگری قرارش دهیم. (Multi Queue with feedback)

اگر این قسمت را خواندید قطعا یاد صف نانوایی افتاده‌اید. صف «یدونه‌ای» و صف «چندتایی». با این هدف که کسی که کار کوتاه‌تری دارد (یک نان می‌خواهد) برای کار کوتاهش معطل یک کار بزرگ نشود. هر صف به صورت مستقل و با قوانین خودش (مثلا هرکس اول آمده را زودتر انجام بده) مدیریت می‌شود.

زمان‌بندی برای کارهای دوره‌ای

کارهای دوره‌ای یعنی مثلا کاری که هر هفته باید انجام شود، مثلا درسی که هر هفته تکلیف می‌دهد و مهلتش تا هفته دیگر همان موقع است. در همین حین ممکن است درس دیگری هر ۱۰ روز و درس دیگری هر ۱۴ روز تکلیف دهد.

کدام را باید اول انجام داد؟

• هر کدام زمان کم‌تری دارد (Rate-monotonic scheduling): به صورت پس‌گیرنده تسکی را انجام بده که زمان کم‌تری دارد. مثلا درسی که هرروز تکلیف می‌دهد را با اولویت بالا انجام بده.
• هر کدام ددلاین نزدیک تری دارد (earliest deadline first): به صورت پس‌گیرنده، تسکی را انجام بده که ددلاین نزدیک‌تری دارد. (بیشتر توضیح دهم؟)
• کاری که نسبت به زمان باقی‌مانده‌اش، زمان کم‌تری داریم (least laxity first): از بین تسک‌ها تسکی را انتخاب کن که زمان باقی‌مانده تا ددلاین منهای زمان باقی‌مانده از تسک، کم‌ترین باشد. به بیانی برای رساندن کار به ددلاینْ تنبلی (laxity) کم‌تری مجاز است.

از کجا بفهمیم این کار چقدر طول می‌کشد؟

در بعضی از الگوریتم‌ها نیاز داریم بدانیم که این کار چقدر طول می‌کشد. در کامپیوتر و زمانی‌ که یک کار ناشناخته را می‌خواهد انجام دهد این سوال خوبی است. البته جواب خوبی ندارد! می‌توان از اطلاعات گذشته برای حدس زدن انتخاب کرد ولی معمولا برای پاک کردن صورت مسئله از الگوریتم‌هایی استفاده می‌شود که نیاز به این عدد ندارند مثلا نوبت‌گردشی.

برای ما انسان‌ها ولی معمولا تخمین زدن کار سختی نیست، با استناد به همین توانایی جلو بروید و هربار سعی کنید تخمین بهتری بزنید.

سعی کردم در این مطلب ساده و کاربردی مباحث را توضیح دهم، در صورتی که به منبع دقیق‌تری نیاز دارید این مطلب در مورد الگوریتم‌های زمان‌بندی را توصیه می‌کنم:

در انتها یادی کنم از دوست خوبم جناب آقای محمدصادق دهقان که با مدیریت بی‌نظیر منابع زندگی‌اش هنگام کار و تحصیل، ایده‌ی این مطلب را در ذهنم انداخت.