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

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

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

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

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

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

زمان‌بند کوتاه‌مدت

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

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

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

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

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

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

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

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

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

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

الگوریتم نخست کوتاه‌ترین کار (به انگلیسی: Shortest Job First)، پردازنده به پروسه‌ای اختصاص می‌یابد که طول اجرای آن از همه کمتر است. هنگامی که پردازش‌گر آماده اجرا است، پردازشی با کوتاه‌ترین طول اجرای بعدی انتخاب می‌شود. این الگوریتم قابل پیاده‌سازی نیست. چرا که باید طول اجرای هر پروسه را محاسبه کرد که در عمل این کار امکان‌پذیر نیست. طول اجرای پروسه یا باید محاسبه شود (که کاری وقت‌گیر و بیهوده است) یا باید تخمین زده شود. به همین دلیل در مواقعی استفاده می‌شود که طول اجرای پروسه از قبل مشخص باشد. می‌توان اثبات کرد که این الگوریتم بهینه است، و به ازای هر مجموعه از پردازش‌ها کم‌ترین زمان پردازش متوسط را ارائه می‌دهد. این الگوریتم دارای مشکل گرسنگی است. به این معنی که اگر به صورت مداوم فرایندهایی به طول اجرای پایین وارد سیستم شوند، ممکن است پروسه‌هایی با طول اجرای طولانی‌تر هرگز اجرا نشوند. مشکل اساسی این الگوریتم سخت بودن طول اجرای بعدی هر کدام از پردازش‌ها است.

بالاترین نسبت پاسخ

سپس بالاترین نسبت پاسخ (به انگلیسی: Highest Response Ratio Next) یک الگوریتم از نوع غیر-انحصاری است در این الگوریتم، اولویت هر فرایند، هم به مدت زمان اجرای آن و هم به مدت زمانی که در صف آماده منتظر دریافت پردازنده بوده، بستگی دارد. هر چه یک فرایند بیشتر در صف آماده منتظر دریافت پردازنده بماند، اولویتش بالاتر خواهد رفت. به این ترتیب این الگوریتم پدیده گرسنگی را برطرف می‌کند و کارهای طولانی مدت هم بالاخره اجرا خواهد شد. در این الگوریتم، اولویت هر فرایند به صورت زیر تعیین می‌شود:

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

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

صف چندگانه فیدبک

صف چندگانه فیدبک (به انگلیسی: Multilevel queue scheduling) وقتی استفاده می‌شود که بتوان پروسه‌ها را به آسانی به گروه‌هایی دسته‌بندی کرد. برای مثال یک روش رایج برای تقسیم کردن این است که پروسه‌های پیش‌زمینه (به انگلیسی: foreground) (که تعاملی هستند) در یک گروه و پروسه‌های پس‌زمینه (به انگلیسی: background) (که دسته‌ای هستند) در گروهی دیگر قرار گیرند. این دو گروه، احتیاج به زمان پاسخ‌دهی متفاوتی دارند. هر پروسه وارد یک صف خاص می‌شود. صف‌ها نسبت به هم اولویت دارند. مثلاً اولویت اجرای پروسه‌های پیش‌زمینه از پروسه‌های پس زمینه بیشتر است. هر صف می‌تواند الگوریتم زمان‌بندی مخصوص به خود را داشته باشد. مثلاً یک صف از زمانبندی نوبت گردشی و صف دیگر از زمانبندی SRT استفاده کند. این الگوریتم در سیستم‌عامل‌های مدرن هم استفاده می‌شود.

ویندوز ان‌تی

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

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

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

فری‌بی‌اس‌دی

فری‌بی‌اس‌دی از روش صف چندگانه فیدبک با اولویتهایی بین ۰ تا ۲۵۵ استفاده می‌کند. اولویت‌های ۰ تا ۶۳ برای وقفه‌ها رزرو شده‌اند. ۶۴ تا ۱۲۷ برای نیمه بالایی هسته، ۱۲۸ تا ۱۵۹ برای ریسه‌های بلادرنگ کاربر، ۱۶۰ تا ۲۲۳ برای ریسه‌های اشتراک زمانی کاربر، ۲۲۴ تا ۲۵۵ هم برای ریسه‌های بیکار کاربر رزرو شده‌اند. مشابه لینوکس، فری‌بی‌اس‌دی هم یک صف فعال دارد، اما فری‌بی‌اس‌دی علاوه بر این صف، یک صف بیکار هم دارد.