زمان‌بندی (رایانه)

مولفه زمان‌بندی پردازش‌ها (به انگلیسی: Process Scheduler)‏ در سیستم‌عامل بخشی از سیستم‌عامل است که تصمیم می‌گیرد که کدام پردازش چه زمانی و به چه مدتی اجرا شود.

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

سیستم‌عامل‌های چندوظیفه‌ای

سیستم‌عامل چندوظیفه‌ای سیستم‌عاملی است که در آن بیش از یک پردازش بتواند همزمان در حال اجرا باشد.

سیستم‌عامل‌های چندوظیفه‌ای به طور عمده به دو قسم تقسیم می‌شوند:

چندوظیفه‌ای پیشگیرانه( قبضه کردنی یا غیر انحصاری)

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

چندوظیفه‌ای مشارکتی( انحصاری )

چندوظیفه‌ای مشارکتی (به انگلیسی: cooperative multitasking)‏: در این سیستم‌ها پردازش تا وقتی که به صورت داوطلبانه اجرا را متوقف نسازد، در حال اجراست و سیستم‌عامل دخالتی نمی‌‌کند. دو نمونه از این سیستم‌عامل‌ها، ویندوز ۳.۱ و مک اواس ۹ است.

الگوریتم‌های زمان‌بندی پردازش

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

زمان‌بندی اجرا به ترتیب ورود

در الگوریتم اجرا به ترتیب ورود، پردازشگر به ترتیب درخواست به پردازش‌ها تخصیص می‌یابد. پیاده‌سازی این الگوریتم به آسانی توسط یک صف اول ورود اول خروج(FIFO) قابل انجام است. هنگامی که پردازشگر آزاد است، آن را به پردازشی که در سر صف قرار دارد تخصیص می‌دهیم، و این پردازش را از صف حذف می‌کنیم.

زمان انتظار برای الگوریتم اجرا به ترتیب ورود معمولا زیاد است.

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

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

می‌توان اثبات کرد که این الگوریتم بهینه است، و به ازای هر مجموعه از پردازش‌ها کم‌ترین زمان پردازش متوسط را ارایه می‌دهد.

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

زمان‌بندی اولویت

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

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

زمان‌بندی چرخشی

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

زمان‌بندی در سیستم‌عامل‌های مختلف

مایکروسافت

داس و ویندوزهای اولیه

• ‌ مایکروسافت داس و ویندوز ابتدایی مایکروسافت قابلیت چند پردازشی نداشتند لذا به زمان بندی نیازی نبود.

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

• ویندوز ۹۵ یک زمان بندی پیشگیرانه ناقص و ابتدایی را ارائه کرد؛ البته به منظور پشتیبانی از پردازش‌های ۱۶ بیتی از همان روش ناپیشگیرانه برای این پردازش‌ها استفاده شد.

ویندوز ان‌تی

سیستم‌عامل‌های مبتنی بر ویندوز ان‌تی از زمان‌بندی بازخوردی استفاده می‌کنند. ۳۲ سطح اولویت تعریف شده‌است، از ۰ تا ۳۱. سطوح ۰ تا ۱۵ اولویت معمولی و سطوح ۱۶ تا ۳۱ اولویت بلادرنگ را دارا می‌باشند؛ اولویت ۰ برای سیستم عامل محفوظ است.
هسته سیستم‌عامل می‌تواند سطح اولویت یک ریسه را بر اساس نیاز آن به ورودی/خروجی و پردازنده و یا تعاملی بودن آن تغییر دهد؛ بدین صورت که سطح اولویت ریسمان‌های در تنگنای ورودی/خروجی و ریسمان‌های مربوط به پردازش‌های محاوره‌ای را بالا می‌برد تا میزان پاسخگویی آنها افزایش یابد، از طرفی سطح اولویت ریسه‌های در تنگنای پردازشگر را کاهش می‌دهد.

ویندوز سرور ۲۰۰۸ و ویندوز ویستا

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

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

لینوکس

در سیستم‌عامل لینوکس هر پردازشی در یکی از رده‌های سیاست زمان‌بندی قرار می‌گیرد، که معمولا یکی از مقادیر زیر است:

• SCHED_OTHER: سیاست زمان‌بندی برای پردازش‌های عادی
• SCHED_FIFO: سیاست زمان‌بندی خروج به ترتیب ورود برای پردازش‌های بلادرنگ
• SCHED_RR: سیاست چرخشی برای پردازش‌های بلادرنگ

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

در رده‌های SCHED_FIFO و SCHED_RR زمان‌بندی با توجه به مقدار اولیت بلادرنگی زمان‌بندی می‌شوند که مقداری بین ۱ تا ۹۹ دارد. مقدار بالاتر متناظر با الویت بالاتر است. در این رده، تا زمانی که پردازشی با اولیت بالاتر وجود داشته باشد، سایر پردازش‌ها فرصت اجرا پیدا نمی‌کنند.

در رده SCHED_OTHER پردازش‌ها با توجه به مقدار اولویت nice که مقداری بین ۲۰- تا ۱۹+ است زمان‌بندی می‌شوند. مقدار بالاتر متناظر با اولیت کمتر است.

برای زمان‌بندی پردازش‌های رده SCHED_OTHER از نسخه ۲.۶.۲۳ به بعد هسته لینوکس از «زمان‌بند کاملا عادلانه» یا CFS استفاده می‌شود. پیش از این زمان‌بند، زمان‌بند مورد استفاده در هسته لینوکس نسخه ۲.۶، زمان‌بند مرتبه ۱ یا زمان‌بند O(1) بود.

در نسخه‌های هسته لینوکس ۲.۴ تا قبل از ۲.۶، الگوریتم زمان‌بندی نسبتا ساده بود، و زمان‌بند هر یک از پردازش‌ها را بررسی می‌کرد و به آن امتیازی می‌داد، و پردازشی که بیشترین امتیاز را به دست می‌آورد را برای اجرا انتخاب می‌کرد. بنابراین پیچیدگی زمانی این الگوریتم از مرتبه O(N) بود. با اینکه الگوریتم نسبتا ساده بود، ولی نسبتا ناکارامد بود و برای سامانه‌های بلادرنگ مناسب نبود.

منابع

• ویکی‌پدیای انگلیسی