زمان‌بندی CPU

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

Definition

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

Scope

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

Core questions

• کیفیت زمان‌بندی با چه معیارهایی اندازه‌گیری می‌شود؟
• الگوریتم‌های زمان‌بندی رایج چگونه در انصاف و کارایی متفاوت هستند؟
• زمان‌بند چه زمانی باید یک وظیفه در حال اجرا را پیشگیرانه متوقف کند؟
• زمان‌بندی چگونه برای چندپردازنده‌ها و مهلت‌های بی‌درنگ تطبیق داده می‌شود؟

Key concepts

• اولین-ورودی-اولین-خروجی
• کوتاه‌ترین-کار-اول
• گردشی و سهم زمانی
• زمان‌بندی اولویت‌بندی
• صف‌های بازخورد چندسطحی
• پیشگیرانه در مقابل غیرپیشگیرانه
• زمان برگشت، انتظار و پاسخ
• گرسنگی و کهن‌سالگی
• زمان‌بندی بی‌درنگ

Key theories

اهداف و بده‌بستان‌های زمان‌بندی

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

Mechanisms

زمان‌بند زمانی اجرا می‌شود که یک فرآیند مسدود می‌شود، واگذار می‌کند یا سهم زمانی آن منقضی می‌شود، و وظیفه بعدی را از صف آماده بر اساس سیاست خود انتخاب می‌کند. زمان‌بندی گردشی به هر وظیفه به نوبت یک برش زمانی می‌دهد؛ صف‌های اولویت‌بندی و بازخورد چندسطحی وظایف را بر اساس اهمیت و رفتار مشاهده شده مرتب می‌کنند و از کهن‌سالگی (aging) برای جلوگیری از گرسنگی (starvation) استفاده می‌کنند. زمان‌بندهای پیشگیرانه می‌توانند یک وظیفه در حال اجرا را قطع کنند تا به یک وظیفه با اولویت بالاتر سوئیچ کنند، که برای تعامل‌پذیری و مهلت‌های بی‌درنگ ضروری است.

Clinical relevance

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

History

مشکلات زمان‌بندی با چندبرنامگی و اشتراک زمانی در دهه ۱۹۶۰ پدیدار شد، زمانی که طرح‌های گردشی و اولویت‌بندی برای به اشتراک گذاشتن پردازنده‌ها توسعه یافتند. نظریه زمان‌بندی بی‌درنگ، از جمله تحلیل‌های نرخ-یکنواخت (rate-monotonic) و اولین-مهلت-اول (earliest-deadline-first)، در دهه ۱۹۷۰ رسمی شد، و زمان‌بندهای چند هسته‌ای مدرن این ایده‌ها را به بسیاری از پردازنده‌ها گسترش دادند.

Debates

انصاف در مقابل توان عملیاتی و اولویت

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

Key figures

• Edsger W. Dijkstra
• Abraham Silberschatz
• Andrew S. Tanenbaum
• C. L. Liu
• James W. Layland

Seminal works

• silberschatz2018
• tanenbaum2014os

Frequently asked questions

تفاوت بین زمان‌بندی پیشگیرانه و غیرپیشگیرانه چیست؟

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

گرسنگی چیست و چگونه از آن جلوگیری می‌شود؟

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