برنامه ریزی CPU

زیر بخش های زیر چندین استراتژی برنامه ریزی مشترک را توضیح می دهد ، که فقط یک پردازنده واحد را برای تعداد کمی از فرآیند پشت سر می گذارد. بدیهی است که سیستم های واقعی باید با فرآیندهای بسیار همزمان با اجرای چرخه پشت سر هم CPU-I/O خود مقابله کنند.

6. 3. 1 برنامه ریزی برای اولین بار-FCFS

• FCFS بسیار ساده است - فقط یک صف FIFO ، مانند مشتریانی که در صف در بانک یا اداره پست یا در یک دستگاه کپی هستند.
• متأسفانه ، با این حال ، FCF ها می توانند زمان انتظار متوسط بسیار طولانی را داشته باشند ، به ویژه اگر اولین فرایند رسیدن به آنجا مدت زمان طولانی طول بکشد. به عنوان مثال ، سه روند زیر را در نظر بگیرید:

• در اولین نمودار GANTT در زیر ، فرآیند P1 ابتدا وارد می شود. میانگین زمان انتظار برای سه فرآیند (0 + 24 + 27) / 3 = 17. 0 ms است.
• در نمودار دوم GANTT در زیر ، همان سه فرآیند زمان انتظار متوسط (0 + 3 + 6) / 3 = 3. 0 ms دارند. کل زمان اجرا برای سه پشت سر هم یکسان است ، اما در حالت دوم دو مورد از این سه مورد خیلی سریعتر و روند دیگر فقط با یک مقدار کوتاه به تأخیر می افتد.

• FCFS همچنین می تواند سیستم را در یک سیستم پویا شلوغ به روش دیگری ، معروف به اثر کاروان مسدود کند. هنگامی که یک فرآیند فشرده CPU CPU را مسدود می کند ، تعدادی از فرآیندهای فشرده I/O می توانند پشت آن پشتیبان تهیه شوند و دستگاه های I/O را بیکار می کنند. هنگامی که گرگ CPU سرانجام از CPU منصرف می شود ، فرآیندهای I/O به سرعت از طریق CPU عبور می کنند و CPU را بیکار می کنند در حالی که همه صف I/O را می گیرند ، و سپس چرخه خود را تکرار می کند وقتی که روند فشرده CPU دوباره به آماده بازگردد. صف

6. 3. 2 کوتاهترین برنامه ریزی شغلی ، SJF

• ایده پشت الگوریتم SJF انتخاب سریعترین سریعترین کار کوچک است که باید انجام شود ، ابتدا آن را از راه خارج کنید و سپس کوچکترین کار بعدی را برای انجام بعدی انتخاب کنید.
• (از نظر فنی این الگوریتم فرآیندی را بر اساس کوتاهترین پشت سر هم CPU بعدی انتخاب می کند ، نه زمان کلی فرآیند.)
• به عنوان مثال ، نمودار GANTT در زیر بر اساس زمان پشت سر هم CPU زیر است ، (و این فرض که همه مشاغل در همان زمان وارد می شوند.)

• در مورد بالاتر از میانگین زمان انتظار (0 + 3 + 9 + 16) / 4 = 7. 0 ms (بر خلاف 10. 25 ms برای FCFS برای همان فرآیندهای مشابه.)
• SJF را می توان ثابت کرد که سریعترین الگوریتم برنامه ریزی است ، اما از یک مشکل مهم رنج می برد: چگونه می دانید ترکیبی از پردازنده بعدی چه مدت خواهد بود؟
  • برای مشاغل دسته ای بلند مدت این کار را می توان بر اساس محدودیتی که کاربران برای مشاغل خود در هنگام ارسال آنها تعیین می کنند انجام داد ، که آنها را ترغیب به تعیین محدودیت های پایین می کند ، اما در صورت تعیین حد مجاز ، آنها را مجدداً ارسال می کنند. وادبا این حال این کار برای برنامه ریزی CPU کوتاه مدت بر روی یک سیستم تعاملی کار نمی کند.
  • گزینه دیگر این است که از نظر آماری ویژگی های زمان اجرا مشاغل را اندازه گیری کند ، به ویژه اگر همان کارها به طور مکرر و به طور پیش بینی انجام شود. اما یک بار دیگر این یک گزینه مناسب برای برنامه ریزی کوتاه مدت CPU در دنیای واقعی نیست.
  • یک رویکرد عملی تر پیش بینی طول پشت سر هم ، بر اساس برخی از اندازه گیری تاریخی زمان پشت سر هم اخیر برای این فرآیند است. یک روش ساده ، سریع و نسبتاً دقیق میانگین نمایی است که می تواند به شرح زیر باشد.(این کتاب از Tau و T برای متغیرهای آنها استفاده می کند ، اما تشخیص آنها از یکدیگر دشوار است و در HTML خوب کار نمی کنند.)

  برآورد [i + 1] = آلفا * پشت سر هم [i] + (1. 0 - alpha) * برآورد [i]

  • در این طرح ، تخمین قبلی شامل تاریخچه تمام دوران قبلی است و آلفا به عنوان یک عامل وزنی برای اهمیت نسبی داده های اخیر در مقابل تاریخ گذشته عمل می کند. اگر آلفا 1. 0 باشد ، تاریخ گذشته نادیده گرفته می شود ، و فرض می کنیم پشت سر هم بعدی به همان اندازه آخرین پشت سر هم خواهد بود. اگر آلفا 0. 0 باشد ، تمام زمان پشت سر هم اندازه گیری شده نادیده گرفته می شود ، و ما فقط یک زمان پشت سر هم ثابت را فرض می کنیم. معمولاً آلفا در 0. 5 تنظیم شده است ، همانطور که در شکل 5. 3 نشان داده شده است:

  

  شکل 6. 3 - پیش بینی طول پشت سر هم CPU بعدی.

  • SJF می تواند پیشگیرانه یا غیرقانونی باشد. پیشگیری هنگامی اتفاق می افتد که یک فرآیند جدید به صف آماده می رسد که مدت زمان پشت سر هم کوتاه تر از زمان باقی مانده در فرآیند است که پشت سر هم در حال حاضر در CPU است. SJF پیشگیرانه گاهی اوقات به عنوان کوتاهترین زمان برنامه ریزی برای اولین بار گفته می شود.
  • به عنوان مثال ، نمودار زیر GANTT براساس داده های زیر است:
  • میانگین زمان انتظار در این مورد ((5 - 3) + (10 - 1) + (17 - 2)) / 4 = 26/4 = 6. 5 ms است.(برخلاف 7. 75 ms برای SJF غیر پیشگیرانه یا 8. 75 برای FCF.)

  6. 3. 3 برنامه ریزی اولویت

  • برنامه ریزی اولویت یک مورد عمومی تر از SJF است که در آن به هر شغل در اولویت اختصاص می یابد و شغل با بالاترین اولویت در ابتدا برنامه ریزی می شود.(SJF از معکوس زمان پشت سر هم مورد انتظار به عنوان اولویت خود استفاده می کند - هرچه پشت سر هم مورد انتظار کوچکتر باشد ، اولویت بالاتر است.
  • توجه داشته باشید که در عمل ، اولویت ها با استفاده از عدد صحیح در یک محدوده ثابت اجرا می شوند ، اما هیچ کنوانسیون توافق شده ای وجود ندارد که آیا اولویت های "بالا" از تعداد زیادی یا تعداد کمی استفاده می کنند. این کتاب از تعداد کم برای اولویت های بالا استفاده می کند که 0 بالاترین اولویت ممکن است.
  • به عنوان مثال ، نمودار زیر GANTT براساس این زمان و اولویت های پشت سر هم فرآیند است و به طور متوسط زمان انتظار 8. 2 میلی ثانیه را به دست می آورد:
  • اولویت ها را می توان در داخل یا خارج از کشور اختصاص داد. اولویت های داخلی توسط سیستم عامل با استفاده از معیارهایی مانند میانگین زمان پشت سر هم ، نسبت CPU به فعالیت I/O ، استفاده از منابع سیستم و سایر عوامل موجود در هسته اختصاص می یابد. اولویت های خارجی بر اساس اهمیت شغل ، هزینه های پرداخت شده ، سیاست و غیره توسط کاربران اختصاص داده می شود.
  • برنامه ریزی اولویت می تواند پیشگیرانه یا غیرقانونی باشد.
  • برنامه ریزی اولویت می تواند از یک مشکل اساسی که به عنوان مسدود کردن نامشخص یا گرسنگی شناخته می شود ، رنج ببرد ، که در آن یک کار با اولویت پایین می تواند برای همیشه منتظر بماند زیرا همیشه مشاغل دیگری در اطراف وجود دارد که اولویت بالاتری دارند.
    • اگر این مشکل مجاز به بروز باشد ، پس از آن که بار سیستم روشن می شود (در ساعت 2:00 بعد از ظهر) فرآیندها یا در نهایت اجرا می شوند ، یا در نهایت هنگام خاموش شدن سیستم یا خراب شدن از بین می روند.(شایعات مربوط به مشاغل وجود دارد که سالها گیر افتاده است.)
    • یک راه حل رایج برای این مشکل پیری است که در آن اولویت های مشاغل بیشتر منتظر می ماند. براساس این طرح ، یک کار با اولویت پایین در نهایت اولویت خود را به اندازه کافی بالا می برد که اجرا می شود.

    6. 3. 4 برنامه ریزی رابین دور

    • برنامه ریزی دور رابین شبیه به برنامه ریزی FCFS است ، به جز اینکه پشت سر هم CPU با محدودیت هایی به نام Time Quantum اختصاص داده می شود.
    • هنگامی که یک فرآیند به CPU داده می شود ، یک تایمر برای هر مقدار تعیین شده برای یک کوانتومی زمان تنظیم می شود.
      • اگر این فرآیند قبل از اتمام تایمر کوانتومی ، پشت سر هم تمام شود ، دقیقاً مانند الگوریتم FCFS معمولی از CPU خارج می شود.
      • اگر تایمر ابتدا خاموش شود ، فرایند از CPU تعویض می شود و به انتهای پشت صف آماده منتقل می شود.

      

      • عملکرد RR به کوانتوم زمانی انتخاب شده حساس است. اگر کوانتوم به اندازه کافی بزرگ باشد، RR به الگوریتم FCFS کاهش می یابد. اگر خیلی کوچک باشد، هر فرآیند 1/nth زمان پردازنده را می گیرد و CPU را به طور مساوی تقسیم می کند.
      • اما، یک سیستم واقعی برای هر سوئیچ زمینه، سربار را فراخوانی می کند، و هر چه کوانتومی زمان کوچکتر باشد، سوئیچ های زمینه بیشتری وجود دارد.(شکل 6. 4 را در زیر ببینید.) اکثر سیستم های مدرن از کوانتوم زمانی بین 10 تا 100 میلی ثانیه و زمان های سوئیچ زمینه حدود 10 میکروثانیه استفاده می کنند، بنابراین سربار نسبت به کوانتوم زمانی کوچک است.

      

      شکل 6. 4 - روشی که در آن کوانتوم زمانی کوچکتر سوئیچ های زمینه را افزایش می دهد.

      • زمان چرخش نیز با زمان کوانتومی، به روشی غیر ظاهری، متفاوت است. به عنوان مثال فرآیندهای نشان داده شده در شکل 6. 5 را در نظر بگیرید:

      

      شکل 6. 5 - روشی که در آن زمان چرخش با کوانتوم زمان تغییر می کند.

      • به طور کلی، در صورتی که اکثر فرآیندها انفجار CPU بعدی خود را در یک زمان کوانتومی به پایان برسانند، زمان چرخش به حداقل می رسد. به عنوان مثال، با سه فرآیند 10 میلی‌ثانیه انفجار، میانگین زمان چرخش برای کوانتومی 1 میلی‌ثانیه 29 است و برای کوانتومی 10 میلی‌ثانیه به 20 کاهش می‌یابد. اما اگر خیلی بزرگ شود، RR فقط به FCFS تبدیل می‌شود. یک قانون سرانگشتی این است که 80 درصد انفجارهای CPU باید کوچکتر از کوانتوم زمانی باشد.

      6. 3. 5 زمانبندی صف چند سطحی

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

      

      شکل 6. 6 - زمانبندی صف چند سطحی

      6. 3. 6 بازخورد چند سطحی زمانبندی صف

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

        

        شکل 6. 7 - صف های بازخورد چندسطحی.

        6. 4 زمانبندی موضوع

        • زمانبندی فرآیند فقط رشته های هسته را زمان بندی می کند.
        • رشته های کاربر توسط کتابخانه رشته به رشته های هسته نگاشت می شوند - سیستم عامل (و به ویژه زمانبند) از آنها بی اطلاع است.

        6. 4. 1 محدوده بحث

        • Contention scope به محدوده ای اشاره دارد که در آن رشته ها برای استفاده از CPU های فیزیکی با هم رقابت می کنند.
        • در سیستم‌هایی که رشته‌های چند به یک و چند به چند را پیاده‌سازی می‌کنند، محدوده بحث فرآیند، PCS، رخ می‌دهد، زیرا رقابت بین رشته‌هایی که بخشی از یک فرآیند هستند رخ می‌دهد.(این مدیریت / زمان‌بندی رشته‌های کاربر متعدد در یک رشته هسته واحد است و توسط کتابخانه رشته مدیریت می‌شود.)
        • دامنه مشاجره سیستم ، SCS ، شامل برنامه های برنامه ریزی برنامه ریزی سیستم برای اجرای یک یا چند CPU است. سیستم های اجرای موضوعات یک به یک (XP ، Solaris 9 ، Linux) ، فقط از SCS استفاده می کنند.
        • برنامه ریزی PCS به طور معمول با اولویت انجام می شود ، جایی که برنامه نویس می تواند اولویت موضوعات ایجاد شده توسط برنامه های خود را تنظیم و یا تغییر دهد. حتی برش زمان در بین موضوعات با اولویت برابر تضمین نمی شود.

        6. 4. 2 برنامه ریزی pthread

        • کتابخانه pthread برای مشخص کردن مشاجره دامنه ارائه می دهد:
          • PTHREAD_SCOPE_PROCESS با برنامه ریزی موضوعات کاربر بر روی LWP های موجود با استفاده از مدل بسیار زیاد ، موضوعات را با استفاده از رایانه های شخصی برنامه ریزی می کند.
          • Pthread_Scope_System موضوعات را با استفاده از SCS ، با اتصال موضوعات کاربر به LWP های خاص ، برنامه ریزی می کند ، به طور موثری یک مدل یک به یک را اجرا می کند.

          6. 5 برنامه ریزی چند پردازنده

          • هنگامی که چندین پردازنده در دسترس است ، برنامه ریزی پیچیده تر می شود ، زیرا اکنون بیش از یک CPU وجود دارد که باید در همه زمان ها مشغول کار و استفاده مؤثر باشد.
          • به اشتراک گذاری بار در اطراف متعادل کردن بار بین چندین پردازنده می چرخد.
          • سیستم های چند پردازنده ممکن است ناهمگن ، (انواع مختلف CPU) یا همگن باشد (همه نوع پردازنده). حتی در مورد دوم ممکن است محدودیت های برنامه ریزی ویژه ای مانند دستگاه هایی که از طریق یک اتوبوس خصوصی به یکی از CPU ها وصل می شوند ، وجود داشته باشد. این کتاب بحث خود را به سیستم های همگن محدود می کند.

          6. 5. 1 رویکرد به برنامه ریزی چند فرآیند

          • یک رویکرد برای برنامه ریزی چند پردازنده ، چند پردازش نامتقارن است که در آن یک پردازنده استاد است ، همه فعالیت ها را کنترل می کند و تمام کد هسته را اجرا می کند ، در حالی که دیگری فقط کد کاربر را اجرا می کند. این رویکرد نسبتاً ساده است ، زیرا نیازی به به اشتراک گذاشتن داده های مهم سیستم نیست.
          • رویکرد دیگر چند پردازش متقارن ، SMP است ، جایی که هر پردازنده مشاغل خاص خود را برنامه ریزی می کند ، چه از یک صف آماده مشترک یا از صف های آماده جداگانه برای هر پردازنده.
          • تقریباً همه سیستم عامل های مدرن از SMP پشتیبانی می کنند ، از جمله XP ، Win 2000 ، Solaris ، Linux و Mac OSX.

          6. 5. 2 میل پردازنده

          • پردازنده ها حاوی حافظه حافظه پنهان هستند که دسترسی مکرر به همان مکان های حافظه را سرعت می بخشد.
          • اگر یک فرآیند هر بار که یک قطعه زمان را از یک پردازنده به دیگری تغییر می داد ، داده های موجود در حافظه نهان (برای آن فرآیند) باید از حافظه اصلی باطل شوند و دوباره بارگذاری شوند و از این طریق از مزایای حافظه نهان جلوگیری کنند.
          • بنابراین سیستم های SMP سعی می کنند از طریق میل پردازنده فرآیندها را در همان پردازنده نگه دارند. وابستگی نرم هنگامی اتفاق می افتد که سیستم سعی در حفظ فرآیندها در همان پردازنده دارد اما هیچ تضمینی ندارد. لینوکس و برخی از سیستم عامل های دیگر از وابستگی سخت پشتیبانی می کنند ، که در آن یک فرایند مشخص می کند که بین پردازنده ها جابجا نمی شود.
          • معماری حافظه اصلی همچنین می تواند بر وابستگی فرآیند تأثیر بگذارد ، اگر CPU های خاص دسترسی سریع تری به حافظه در همان تراشه یا تخته نسبت به سایر حافظه های بار دیگر داشته باشند..

          6. 5. 3 تعادل بار

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

            6. 5. 4 پردازنده های چند هسته ای

            • SMP سنتی برای اجرای چندین موضوع هسته به طور همزمان به تراشه های CPU متعدد نیاز داشت.
            • روندهای اخیر این است که چندین CPU (هسته) را بر روی یک تراشه واحد قرار دهید که به عنوان چندین پردازنده در سیستم ظاهر می شود.
            • چرخه های محاسباتی را می توان با زمان مورد نیاز برای دسترسی به حافظه مسدود کرد ، هر زمان که داده های مورد نیاز از قبل در حافظه نهان موجود نباشد.(حافظه پنهان.) در شکل 5. 10 ، به اندازه نیمی از چرخه CPU در غرفه حافظه از بین می رود.

            

            شکل 6. 10 - غرفه حافظه.

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

            

            شکل 6. 11 - سیستم چند رشته ای چند رشته ای.

            • یک سیستم دو هسته ای با دو رشته دارای چهار پردازنده منطقی در دسترس سیستم عامل است. CPU Ultrasparc T1 دارای 8 هسته در هر تراشه و 4 موضوع سخت افزاری در هر هسته است ، برای کل 32 پردازنده منطقی در هر تراشه.
            • دو روش برای یک پردازنده چند رشته وجود دارد:
              1. سوئیچ های چند رشته ای درشت دانه ای که فقط در صورت بلوک کردن یک موضوع ، بین موضوعات سوئیچ می شود ، در یک حافظه بخوانید. تعویض زمینه شبیه به سوئیچینگ فرآیند است ، با سربار قابل توجهی.
              2. چندتایی ریز و درشت ریز در فواصل منظم کوچکتر رخ می دهد ، در مرز چرخه های دستورالعمل بگویید. با این حال معماری برای پشتیبانی از تعویض نخ طراحی شده است ، بنابراین سربار نسبتاً جزئی است.
            • توجه داشته باشید که برای یک سیستم چند هسته ای چند رشته ای ، دو سطح برنامه ریزی در سطح هسته وجود دارد:
              • سیستم عامل برنامه ریزی می کند که نخ (های) هسته را به کدام پردازنده های منطقی اختصاص می دهد ، و چه زمانی باید سوئیچ های زمینه را با استفاده از الگوریتم هایی که در بالا توضیح داده شده است ، انجام دهند.
              • در سطح پایین تر ، سخت افزار با استفاده از برخی الگوریتم های دیگر ، پردازنده های منطقی را در هر هسته فیزیکی برنامه ریزی می کند.
                • Ultrasparc T1 از یک روش ساده دور رابین برای برنامه ریزی 4 پردازنده منطقی (موضوعات هسته) در هر هسته فیزیکی استفاده می کند.
                • Intel Itanium یک تراشه دو هسته ای است که از یک طرح اولویت 7 سطح (فوریت) استفاده می کند تا تعیین کند که در هنگام وقوع یکی از 5 رویداد مختلف ، کدام موضوع را برنامه ریزی می کند.

                /* قدیمی 5. 5. 5 مجازی سازی و برنامه ریزی (اختیاری ، حذف شده از نسخه نهم)

                • مجازی سازی لایه دیگری از پیچیدگی و برنامه ریزی را اضافه می کند.
                • به طور معمول یک سیستم عامل میزبان وجود دارد که بر روی پردازنده (های) واقعی "و تعدادی سیستم عامل مهمان که روی پردازنده های مجازی کار می کنند ، کار می کند.
                • سیستم عامل میزبان تعدادی از پردازنده های مجازی را ایجاد می کند و آنها را به سیستم عامل های مهمان ارائه می دهد که گویی پردازنده های واقعی هستند.
                • سیستم عامل های مهمان نمی دانند که پردازنده های آنها مجازی هستند و تصمیم گیری در مورد فرض پردازنده های واقعی می گیرند.
                • در نتیجه ، عملکرد تعاملی و به ویژه در زمان واقعی می تواند به شدت در سیستم های مهمان به خطر بیفتد. ساعت زمان روز نیز غالباً خاموش خواهد بود.

                6. 6 برنامه ریزی CPU در زمان واقعی

                • اگر نیازهای زمان بندی آنها برآورده نشود ، سیستم های نرم در زمان واقعی عملکرد تخریب شده اند. مثال: پخش ویدیو.
                • اگر نیازهای زمان بندی آنها برآورده نشود ، سیستم های سخت در زمان واقعی دارای شکست کامل هستند. مثالها: روباتیک خط مونتاژ ، استقرار کیسه هوایی خودرو.

                6. 6. 1 به حداقل رساندن تأخیر

                • تأخیر رویداد زمان بین وقوع یک رویداد آغازگر و (تکمیل) پاسخ سیستم به رویداد است:
                • علاوه بر زمان مورد نیاز برای پردازش واقعی رویداد، دو مرحله اضافی وجود دارد که قبل از اینکه کنترل کننده رویداد (روال سرویس وقفه، ISR)، حتی بتواند شروع شود، باید رخ دهد:
                  • پردازش وقفه تعیین می کند که کدام وقفه رخ داده است، و کدام روال کنترل کننده وقفه اجرا شود. در صورت وقفه های همزمان، یک طرح اولویت مورد نیاز است تا مشخص شود کدام ISR بالاترین اولویت را دارد و می تواند در مرحله بعدی قرار گیرد.
                  • سوئیچینگ زمینه شامل حذف یک فرآیند در حال اجرا از CPU، ذخیره وضعیت آن و بارگذاری ISR به طوری که بتواند اجرا شود.
                  • تأخیر کل ارسال (تغییر زمینه) از دو بخش تشکیل شده است:
                    • حذف فرآیند در حال اجرا از CPU، و آزاد کردن هر گونه منابعی که توسط ISR مورد نیاز است. با استفاده از هسته های پیشگیرانه می توان سرعت این مرحله را بسیار افزایش داد.
                    • بارگیری ISR روی CPU، (Dispatching)

                    6. 6. 2 برنامه ریزی بر اساس اولویت

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

                      6. 6. 3 زمانبندی نرخ-یکنواخت

                      • الگوریتم زمان‌بندی نرخ یکنواخت از زمان‌بندی پیشگیرانه با اولویت‌های ثابت استفاده می‌کند.
                      • اولویت ها به طور معکوس به دوره هر کار اختصاص داده می شوند و اولویت بالاتر (بهتر) را به وظایف با دوره های کوتاه تر می دهند.
                      • بیایید یک مثال را در نظر بگیریم، ابتدا نشان می‌دهیم که اگر به کار با دوره طولانی‌تر اولویت بیشتری داده شود، چه اتفاقی می‌افتد:
                        • فرض کنید که فرآیند P1 دارای دوره 50، زمان اجرا 20 و مهلتی است که با دوره آن مطابقت دارد (50).
                        • به طور مشابه فرض کنید که فرآیند P2 دارای دوره 100، زمان اجرا 35 و مهلت 100 است.
                        • کل زمان استفاده از CPU 20/50 = 0. 4 برای P1، و 25/100 = 0. 35 برای P2، یا 0. 75 (75٪) به طور کلی است.
                        • با این حال، اگر P2 اجازه داشته باشد ابتدا برود، آنگاه P1 نمی تواند قبل از مهلت خود تکمیل شود:
                        • حالا از طرف دیگر، اگر P1 اولویت بیشتری داشته باشد، ابتدا باید برود و P2 پس از اتمام انفجار P1 شروع می شود.
                        • در زمان 50 که دوره بعدی برای P1 شروع می شود، P2 تنها 30 واحد از 35 واحد زمانی مورد نیاز خود را تکمیل کرده است، اما توسط P1 پیشی گرفته می شود.
                        • در زمان 70، P1 وظیفه خود را برای دوره دوم خود کامل می کند و P2 مجاز است 5 واحد زمانی آخر خود را تکمیل کند.
                        • به طور کلی هر دو فرآیند در زمان 75 کامل می‌شوند، و سپس Cpu برای 25 واحد زمانی بی‌کار است، قبل از اینکه فرآیند تکرار شود.
                        • زمان‌بندی نرخ یکنواخت در بین الگوریتم‌هایی که از اولویت‌های ایستا استفاده می‌کنند بهینه در نظر گرفته می‌شود، زیرا هر مجموعه‌ای از فرآیندهایی که با این الگوریتم نمی‌توانند زمان‌بندی شوند، نمی‌توانند با هیچ الگوریتم زمان‌بندی اولویت ایستایی دیگر نیز زمان‌بندی شوند.
                        • با این حال، مجموعه‌ای از فرآیندها وجود دارد که نمی‌توان آنها را با اولویت‌های ثابت برنامه‌ریزی کرد.
                          • به عنوان مثال، فرض کنید که P1 = 50، T1 = 25، P2 = 80، T2 = 35، و سررسیدها با دوره ها مطابقت دارند.
                          • استفاده کلی از CPU 25/50 = 0. 5 برای P1، 35 / 80 = 0. 44 برای P2، یا 0. 94 (94٪) به طور کلی است، نشان می دهد که باید امکان زمان بندی فرآیندها وجود داشته باشد.
                          • با زمان‌بندی نرخ یکنواخت، P1 اول می‌رود و اولین انفجار خود را در زمان ۲۵ کامل می‌کند.
                          • P2 در مرحله بعدی قرار می گیرد، و 25 واحد از 35 واحد زمانی خود را قبل از اینکه در زمان 50 توسط P1 پیشی گرفته شود، تکمیل می کند.
                          • P1 دومین انفجار خود را در 75 کامل می کند، و سپس P2 10 واحد زمانی آخر خود را در زمان 85 تکمیل می کند و ضرب الاجل خود را 80 در 5 واحد زمانی از دست می دهد.:-(
                          • بدترین حالت استفاده از CPU برای زمان‌بندی فرآیندهای N تحت این الگوریتم N * (2^(1/N) - 1 است که 100% برای یک فرآیند است، اما به 75% برای دو فرآیند و به 69% کاهش می‌یابد. N به بی نهایت نزدیک می شود. توجه داشته باشید که در مثال ما بالای 94% بالاتر از 75% است.

                          6. 6. 4 برنامه ریزی زودهنگام-اولین مهلت

                          • زمان‌بندی Earliest Deadline First (EDF) اولویت‌ها را به صورت پویا تغییر می‌دهد، و بالاترین اولویت را به فرآیند با زودترین مهلت می‌دهد.
                          • شکل 6. 19 مثال قبلی ما را نشان می دهد که تحت زمان بندی EDF تکرار شده است:
                            • در زمان 0 P1 زودترین ضرب الاجل، بالاترین اولویت را دارد و اول می شود. پس از آن P2 در زمان 25 زمانی که P1 اولین انفجار خود را کامل می کند، قرار می گیرد.
                            • در زمان 50، فرآیند P1 دوره دوم خود را آغاز می کند، اما از آنجایی که P2 مهلت 80 دارد و مهلت P1 تا 100 نیست، P2 مجاز است روی CPU بماند و انفجار خود را کامل کند، که در زمان 60 انجام می دهد.
                            • سپس P1 دومین انفجار خود را شروع می کند که در زمان 85 کامل می شود.
                            • P2 دومین انفجار خود را در زمان 85 شروع می کند و تا زمان 100 ادامه می یابد، در این زمان P1 دوره سوم خود را آغاز می کند.
                            • در این مرحله P1 دارای مهلت 150 و P2 دارای مهلت 160 است، بنابراین P1 از P2 جلوگیری می کند.
                            • P1 سومین انفجار خود را در زمان 125 کامل می کند، در این زمان P2 شروع می شود و سومین انفجار خود را در زمان 145 تکمیل می کند.
                            • CPU برای 5 واحد زمانی بیکار می ماند، تا زمانی که P1 دوره بعدی خود را در 150 و P2 در 160 شروع کند.
                            • سوال: کدام فرآیند در زمان 160 اجرا می شود و چرا؟
                              • پاسخ: فرآیند P2، زیرا P1 اکنون مهلت 200 دارد و مهلت جدید P2 240 است.

                              6. 6. 5 زمانبندی سهم متناسب

                              • زمان‌بندی سهم متناسب با تقسیم کل زمان موجود به تعداد مساوی از سهام کار می‌کند، و سپس هر فرآیند هنگام شروع تلاش باید سهم معینی از کل را درخواست کند.
                              • مثلاً بگویید که کل سهام، T، = 100، و سپس یک فرآیند خاص هنگام راه‌اندازی، 30 = N را درخواست می‌کند. سپس 30/100 یا 30 درصد از زمان موجود تضمین می شود.
                              • زمان‌بندی سهم متناسب با یک سیاست پذیرش-کنترل کار می‌کند، اگر نتواند سهامی را که وظیفه می‌گوید به آن نیاز دارد تضمین کند، هیچ کاری را شروع نمی‌کند.

                              6. 6. 6 برنامه ریزی زمان واقعی POSIX

                              • POSIX دو کلاس زمان‌بندی را برای رشته‌های زمان واقعی تعریف می‌کند، SCHED_FIFO و SCHED_RR، بسته به اینکه چگونه رشته‌هایی با اولویت زمان اشتراک برابری دارند.
                              • SCHED_FIFO وظایف را به ترتیب اول به اول برنامه‌ریزی می‌کند، بدون برش زمانی بین رشته‌های با اولویت یکسان.
                              • SCHED_RR برش زمان چرخشی را در بین رشته هایی با اولویت یکسان انجام می دهد.
                              • POSIX روش هایی را برای دریافت و تنظیم خط مشی زمانبندی رشته ارائه می دهد، همانطور که در زیر نشان داده شده است:

                              6. 7 نمونه های سیستم عامل (اختیاری)

                              6. 7. 1 مثال: زمانبندی لینوکس (5. 6. 3 بود)

                              • قبل از نسخه 2. 5، لینوکس از یک الگوریتم زمانبندی سنتی یونیکس استفاده می کرد.
                              • نسخه 2. 6 از الگوریتمی به نام O(1) استفاده می کرد که بدون توجه به تعداد کارها در زمان ثابتی اجرا می شد و از سیستم های SMP پشتیبانی بهتری می کرد. با این حال عملکرد تعاملی ضعیفی را به همراه داشت.
                              • از 2. 6. 23، Completely Fair Scheduler، CFS، به سیستم استاندارد زمانبندی لینوکس تبدیل شد. نوار کناری زیر را ببینید

                              عملکرد CFS (زمانبندی کاملا منصفانه).

                              • زمانبندی لینوکس یک الگوریتم مبتنی بر اولویت پیشگیرانه با دو محدوده اولویت است - زمان واقعی از 0 تا 99 و یک محدوده خوب از 100 تا 140.
                              • برخلاف Solaris یا XP، لینوکس کوانتوم‌های طولانی‌تری را به وظایف با اولویت بالاتر اختصاص می‌دهد.

                              /* مطالب زیر از ویرایش نهم حذف شد:

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

                              

                              از ویرایش نهم حذف شده است. شکل 5. 16 در ویرایش هشتم.

                              6. 7. 2 مثال: Windows XP Scheduling (5. 6. 2 بود)

                              • ویندوز XP از یک الگوریتم زمان‌بندی پیشگیرانه مبتنی بر اولویت استفاده می‌کند.
                              • توزیع کننده از یک طرح اولویت 32 سطحی برای تعیین ترتیب اجرای thread استفاده می کند که به دو کلاس تقسیم می شود - کلاس متغیر از 1 تا 15 و کلاس بلادرنگ از 16 تا 31، (به علاوه یک رشته در اولویت 0 حافظه مدیریتی. )
                              • همچنین یک thread بیکار ویژه وجود دارد که زمانی برنامه ریزی می شود که هیچ رشته دیگری آماده نباشد.
                              • Win XP 7 کلاس اولویت (ردیف های جدول زیر) و 6 اولویت نسبی را در هر کلاس (ستون ها) شناسایی می کند.
                              • همچنین به هر یک از فرآیندها یک اولویت پایه در کلاس اولویت خود داده می شود. هنگامی که فرآیندهای کلاس متغیر کل کوانتای زمانی خود را مصرف می کنند، اولویت آنها کاهش می یابد، اما کمتر از اولویت پایه آنها نیست.
                              • فرآیندهای موجود در پیش زمینه (پنجره فعال) دارای کوانتای زمان بندی آنها در 3 ضرب می شوند تا به فرآیندهای تعاملی در پیش زمینه پاسخ بهتری بدهند.

                              

                              شکل 6. 22 - اولویت های رشته ویندوز.

                              6. 7. 1 مثال: زمانبندی سولاریس

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

                                

                                شکل 6. 23 - جدول اعزام سولاریس برای موضوعات به اشتراک گذاری زمانی و تعاملی.

                                • سولاریس 9 دو کلاس زمانبندی جدید را معرفی کرد: اولویت ثابت و سهم منصفانه.
                                  • اولویت ثابت مشابه اشتراک زمانی است، اما به صورت پویا تنظیم نشده است.
                                  • سهم منصفانه از سهم زمان CPU به جای اولویت ها برای برنامه ریزی کارها استفاده می کند. سهم مشخصی از زمان موجود CPU به یک پروژه اختصاص می یابد که مجموعه ای از فرآیندها است.

                                  

                                  شکل 6. 24 - برنامه ریزی سولاریس.