(۹)
یک مجموعه از n وظیفه غیرتناوبی، بوسیله سیاست زمانبندی DMS ، قابل زمانبندی است هرگاه :
(۱۰)
که UB(n) به صورت زیر تعریف می‌شود:
(۱۱)
معماری زمانبندی الگوریتم مرجع ]۳۵[ :
می‌دانیم که وظایف تناوبی در سیستم‌های تعبیه‌شده، دائم در حال تکرار شدن اجرایشان هستند، تا زمانیکه پردازنده خاموش شود. بنابراین بهتر است که بین تکرار وظایف، هسته‌ها بجای اینکه خاموش و روشن شوند، به حالت مصرف‌پایین[۱۳۷] بروند. در این الگوریتم وظایف تناوبی را به تعداد کمی هسته محدود کرده اند تا به حداقل هسته‌ها برای روشن ماندن نیاز داشته باشند، از سوی دیگر، وظایف غیرتناوبی را که خیلی کمتر رخ می‌دهند، به بقیه هسته‌ها اختصاص داده اند.وقتی اجرای یک وظیفه به پایان رسید، هسته‌ متناظر آن، همانند حافظه نهان آن، میتواند خاموش شود، بنابراین نیازی نیست محتوای مقادیر این وظایف که قرار نیست تا آینده‌ای نزدیک اتفاق بیوفتد، نگهداری شود. در الگوریتم این مقاله، وظایف تناوبی به وسیله الگوریتم RBound-FF به حداقل هسته‌ها اختصاص می‌یابند و وظایف غیرتناوبی بین بقیه هسته‌ها به صورت عادلانه توزیع می‌شوند. شبه کد این الگوریتم را در شکل ۳-۱۱ صفحه بعد مشاهده می‌کنید.
دانلود پایان نامه - مقاله - پروژه
Task assignment(Inpot: τj , schedparam)
Begin
If(schedparam ->scedpolicy == RMS)
Assign τj to its bounded core
Endif
If(schedparam ->scedpolicy == DMS)
Pi = IDLestCore_RestCore()
If (τj can be admitted on Pi)
Assign τj to Pi
Endif
Else return(REJECT)
Endif
end
شکل ۳-۱۱ الگوریتم اختصاص دادن وظایف در مرجع ]۳۵[
شکل ۱۴شکل ۳-۱۱ الگوریتم اختصاص دادن وظایف در مرجع [۳۵]
مزایا و معایب این الگوریتم:
این الگوریتم بدلیل استفاده از RMS در زمانبندی وظایف تناوبی و الگوریتم DMS برای زمانبندی وظایف غیرتناوبی، می‌تواند تاثیر بسازیی در کاهش نرخ نقض سررسید وظایف گردد. همچنین در این الگوریتم نیز وظایف تناوبی از وظایف غیرتناوبی تفکیک شده و جداگانه توزیع می‌شوند که در مصرف انرژی موثر می‌باشد.
اما از جمله معایب این الگوریتم این است که، ورود یک وظیفه جدید در سیستم، موجب می‌شود، مجموعه وظایف مجددا توسط الگوریتم RBound جزءبندی شوند و این مسئله باعث افزایش سربار زمان اجرا می‌شود. همچنین در این الگوریتم نیز فشار زیادی روی تعداد محدودی از هسته‌ها برای اجرای وظایف غیرتناوبی می‌باشد که باعث می‌شود کارایی سیستم پایین بیاید.
۳-۶-۳ الگوریتم زمانبندی چند سطحی PDAMS [۱۳۸]
در مرجع ]۳۶[ ، مسئله زمانبندی چندهسته‌ای توان محور[۱۳۹] به دو قسمت زیر تقسیم می‌شود:

 

    • توزیع بار [۱۴۰] بین هسته‌ها

 

    • زمانبندی توان محور برای هر هسته

 

با توجه به همین تقسیم‌بندی، برای هر کدام از این موارد، الگوریتم‌هایی جداگانه پیشنهاد شده است. برای کم‌کردن محدودیت‌ها وساختن یک الگوریتمی که اجرایش راحت‌تر باشد، از دست دادن برخی سررسیدها در این پژوهش اجازه داده شده است. مدلی که در این مقاله پیشنهاد شده، بشرح زیر می‌باشد.
مدل سیستم پیشنهادی مقاله ]۳۶[ :
در این سیستم، یک واحد پردازنده به عنوان مدیر[۱۴۱] و n تا هسته پردازنده به عنوان برده[۱۴۲] ، وجود دارند و هر هسته پردازنده برای خودش یک سیستم‌عامل خاص دارد و می‌تواند به صورت مستقل، فرکانس و ولتاژ عملیاتی خود را تغییر و تنظیم کند. وقتی وظایف در این سیستم توزیع می‌شوند، واحد پردازنده مدیر، اطلاعات هر هسته را بوسیله IPC [۱۴۳] مبادله می‌کند و سپس این وظایف را بین هسته‌ها توزیع می‌کند. سپس هسته‌ها، وظایفی که به آنها توزیع شده است را به صورت مستقل زمانبندی می‌کنند. تحت این معماری، الگوریتم پیشنهادی این مقاله می‌تواند هم برای سیستم‌های چندهسته‌ای همگن و هم ناهمگن پذیرفته شود و هر هسته پردازنده می‌تواند خودش را مدیریت کند.
ورودی‌های الگوریتم:
یک مجموعه کلی برای همه وظایف در نظر می‌گیریم:
T= { Treal , Tnormal } (۱۲)
Treal مجموعه وظایف بی‌درنگ می‌باشد و Tnormal مجموعه وظایف معمولی است. همچنین هر وظیفه بی‌درنگ دارای مشخصات زیر می‌باشد:

 

    • زمان آزادشدن

 

    • اولویت

 

    • سررسید متناظر

 

همچنین این وظایف می‌توانند تناوبی یا غیرتناوبی باشند. در محیط های پویا، بدست آوردن همه اطلاعات یک وظیفه مشکل می باشد و همچنین سربار الگوریتم‌های بهینه‌سازی استفاده شده، بسیار سنگین است( هنگامی که هر وظیفه آزاد می شود). بنابراین در این مقاله سعی شده است که بدون در نظر گرفتن زمان اجرای وظایف، وظایف بی‌درنگ را زمانبندی کند.
با اینکه سررسیدهای سخت ضمانت نشده است ولی روش‌هایی که پیشنهاد داده شده تا حد امکان باعث کاهش از دست دادن سررسیدها شده است..
Tnormal فقط از مشخصه‌ های اولویت و زمان آزاد شدن تشکیل شده است. در کل، ترتیب اجرای وظایف بی‌درنگ براساس سررسید مطلق وظایف می‌باشد. اولویت وظایف بی‌درنگ فقط وقتی که دو یا چند وظیفه دارای سررسید مطلق یکسانی باشند، استفاده می شود.
خروجی الگوریتم :
خروجی الگوریتم PDAMS، یک مجموعه‌ای از زمانبندی‌های ممکن S که :
S= { S1 , S2 , … , Sn } (۱۳)

موضوعات: بدون موضوع  لینک ثابت


فرم در حال بارگذاری ...