بله
پیدا کردن هستهای که کمترین تعداد وظایف را در صف خود دارد
آیا حداقل دو هسته با تعداد وظایف موجود درصف برابر داریم؟
انتخاب هستهای که دارای شماره سریال کوچکتری باشد
خیر
بله
شکل ۴-۷ فلوچارت الگوریتم پیشنهادی توزیع وظایف غیرتناوبی
شکل ۳۰شکل ۴-۷ فلوچارت الگوریتم پیشنهادی توزیع وظایف غیرتناوبی
راهکار پیشنهادی مربوط به انحصاری بودن وظایف غیرتناوبی
در الگوریتم پیشنهادی ما، وظایف تناوبی از نوع غیرانحصاری بوده و وظایف غیرتناوبی، از نوع انحصاری میباشند. این بدین معنی است که وقتی یک وظیفه تناوبی در حال اجرا باشد و وظیفه دیگری وارد صف این هسته شود که اولویت بالاتری نسبت به آن وظیفه در حال اجرا داشته باشد، پردازنده از وظیفه تناوبی در حال اجرا گرفته نمی شود و آن وظیفه به اجرای خود ادامه خواهد داد.
اما در وظایف غیرتناوبی این مسئله وجود ندارد. در این حالت اگر وظیفه غیرتناوبی در حال اجرا باشد و وظیفه جدیدی وارد صف این هسته شود که اولویت بالاتری داشته باشد، پردازنده از وظیفه در حال اجرا گرفته شده و به وظیفه جدید اختصاص مییابد. سپس وظیفه قبلی که پردازنده از آن گرفته شد، در ابتدای صف کلی وظایف غیرتناوبی قرار میگیرد و الگوریتم اختصاص وظایف غیرتناوبی دوباره برای آن اجرا میگردد تا این وظیفه به هسته دیگر اختصاص یابد.
راهکار پیشنهادی مربوط به مهاجرت وظایف غیرتناوبی بین هستهها
الگوریتم پیشنهادی ما جز طبقهبندی الگوریتمهای دوگانه محسوب میشود، یعنی در آن برخی وظایف میتوانند بین هستهها جابجا شوند و برخی دیگر اجازه مهاجرت بین هستهها را ندارند. در الگوریتم ما، وظایف غیرتناوبی میتوانند تحت شرایطی بین هستهها مهاجرت نمایند، ولی وظایف تناوبی چنین اجازهای ندارند.
شرایط مهاجرت وظایف غیرتناوبی در الگوریتم ما بدین صورت است که اگر صف هریک از هستههای مربوط به وظایف غیرتناوبی، خالی شود، یعنی هسته، تمام وظایف موجود در صف خود را به اتمام برساند، آنگاه قبل از اینکه خود را خاموش کند، هستههای روشن مربوط به وظایف غیرتناوبی را بررسی میکند، اگر هریک از این هستهها دارای بهرهوری کل کمتری نسبت به دیگر هستهها باشند و در عینحال، این میزان بهرهوری از ۰٫۸ بیشتر باشد، آنگاه وظیفهای که در صف این هسته، کمترین سررسید متناظر را دارا باشد انتخاب شده و به هسته خالی موردنظر مهاجرت داده میشود. در این حالت، بهرهوری یک وظیفه غیرتناوبی عبارتانداز؛ نسبت بدترین حالت زمان اجرای وظیفه به سررسید متناظر آن:
(۲۸)
علت اینکه این نوع مهاجرت را برای وظایف تناوبی درنظر نگرفتیم این است که در الگوریتم زمانبندی وظایف تناوبی، هدف اصلی کاهش مصرف انرژی این وظایف است و تا حد امکان که نقض سررسید صورت نگیرد و یا کمتر شود، اصرار به خاموش نگه داشتن هستهای که صف اجرای آن خالی است داریم، بنابراین در صورت مهاجرت وظایف تناوبی به هستههای خالی تناوبی، مصرف انرژی بشدت افزایش یافته و کارایی الگوریتم پایین مییاید.
۴-۵-۳ الگوریتم پیشنهادی تنظیم فرکانس سررسید محور (بخش سوم الگوریتم پیشنهادی)
قسمت آخر الگوریتم پیشنهادی ما، تنظیم فرکانس هر هسته به صورت پویا میباشد که زمان اجرای نهایی هر وظیفه نیز بر همین اساس محاسبه و میزان توان مصرفی هر وظیفه و توان مصرفی کل، بدست آمده و در نتیجه انرژی مصرفی کل سیستم محاسبه خواهد شد. الگوریتمهای تنظیم ولتاژ و فرکانس، معمولاً فقط به کاهش مصرف انرژی پردازنده منجر میشوند، اما الگوریتم پیشنهادی ما علاوه بر کاهش مصرف انرژی، عدم نقض سررسید وظایف را نیز در نظر میگیرد. از این رو این الگوریتم جزء الگوریتمهای تنظیم پویای فرکانس و ولتاژ سررسیدمحور محسوب میگردد.
نحوه عملکرد الگوریتم پیشنهادی ما بدین صورت است که ابتدا در هر هسته، در میان وظایف موجود در آن، کمترین سررسید موجود را پیدا کرده و آن را Dsr (shortest deadline) مینامیم.
سپس پارامتر جدیدی به نام γ (گاما) را به صورت زیر تعریف میکنیم:
(۲۹)
پارامتر x در آزمایش شبیهسازی این پژوهش، در حالتهای مختلف ( ۰٫۲ و۰٫۴ و ۰٫۶ و ۰٫۸ ) بررسی شده و بهترین حالتها با توجه نوع تاثیر روی خروجیها ( یعنی انرژی مصرفی، نرخ از دست دادن سررسید، زمان پاسخ وظایف غیرتناوبی و کارایی بالاتر سیستم) در نظر گرفته شده و نتایج هر حالت در فصل آینده نشان داده شده است.
در این پژوهش، هر هسته پردازنده، دارای تعدادی سطوح فرکانسی بین تا است و متناسب با هر سطح فرکانسی، توان مصرفی متناظری دارد.
در ابتدای اجرای هر وظیفه، فرکانس پردازنده روی تنظیم میشود (چه اینکه وظیفه اولین بار برای اجرا آمده باشد و چه ادامه اجرای قبلیاش باشد. سپس وظیفه شروع به اجرا میکند، حال هرگاه اجرای این وظیفه به اندازه γ واحد زمانی طول کشید ولی اجرایش تمام نشد، آنگاه الگوریتم ما فرکانس اجرای هسته پردازنده را یک سطح افزایش میدهد، سپس از این لحظه به بعد هم اگر باز هم به اندازه γ واحد زمانی اجرایش طول کشید ولی تمام نشد، بازهم یک سطح به فرکانس اجرای وظیفه اضافه کند، این کار را آنقدر ادامه می دهیم تا وظیفه ، تا حد ممکن بدون نقض سررسید و با کمترین انرژی مصرفی، اجرایش به پایان برسد. در شکل ۴-۸ این مفهوم بخوبی نشان داده شده است.
شکل ۴-۸ نمودار زمانی اجرای یک وظیفه با الگوریتم تنظیم فرکانس پیشنهادی
fmin
f1
f2
f3
γ
۰
۲γ
۳γ
t
زمان پایان اجرا
tf
زمان شروع اجرا
شکل ۳۱شکل ۴-۸ نمودار زمانی اجرای یک وظیفه با الگوریتم تنظیم فرکانس پیشنهادی
همانطور که در مثال شکل ۴-۸ مشاهده میکنید، وظیفه در لحظه صفر، اجرایش آغاز میشود و از ابتدا با فرکانس fmin شروع به کار میکند، سپس γ واحد زمانی از شروع اجرایش میگذرد ولی اجرایش به پایان نرسیده است، بنابراین سطح فرکانس هسته را یک پله بالاتر تنظیم میکنیم و از لحظه ۰+γ ، وظیفه موردنظر با فرکانس f1 اجرا میشود (fmin<f1). سپس باز هم γ واحد زمانی از لحظه بالا بردن فرکانس میگذر ولی اجرای وظیفه همچنان تمام نشده است، در نتیجه از لحظه ۲γ ، وظیفه با فرکانس f2 اجرا خواهد شد ( f2 > f1 ). این روند ادامه پیدا میکند تا در لحظه tf که کوچکتر از ۴γ میباشد، اجرای وظیفه روی هسته تمام میشود.
محاسبه زمان اجرای نهایی وظیفه و انرژی مصرفی آن:
برای محاسبه زمان اجرای هر وظیفه با توجه به فرکانس اجرایی هسته متناظر خودش، باید زمان اجرای هر پارت(قسمت) که وظیفه با فرکانس خاصی در حال اجرا میباشد را محاسبه و با هم جمع کرد.
اگر حداکثر فرکانس اجرایی یک هسته، بدترین حالت زمان اجرای یک وظیفه و فرکانسی باشد که در هر پارت زمانی، وظیفه با آن فرکانس در حال اجرای روی هسته باشد، آنگاه بر اساس فرمول فاکتور کاهش سرعت موجود در مراجع ]۳۸[ و ]۳۹ [، زمان اجرای هر وظیفه به صورت زیر محاسبه می شود:
(زمان اجرای هر وظیفه) (۳۰)
برای محاسبه انرژی مصرفی یک وظیفه روی هسته، از رابطه زیر استفاده میکنیم:
(۳۱)
که در آن Pt توان مصرفی متناظر با فرکانس اجرایی وظیفه در هر پارت زمانی است و EXt هم در واقع طول هر پارت زمانی است که وظیفه با این فرکانس و توان P متناظر با آن در حال اجرا میباشد.
برای محاسبه کل یک وظیفه، پس از اجرای الگوریتم تنظیم فرکانس پیشنهادی، باید انرژی تک تک پارتهایی که وظیفه در آن ها با فرکانسهای متفاوتی اجرا میشود، محاسبه شده و در نهایت باهم جمع گردند. علت این مسئله این است که به عنوان مثال ممکن است یک وظیفه از زمان شروع به اجرایش تا پایان کار خود، در سه سطح فرکانسی متفاوتی اجرا شود، در نتیجه می بایست انرژی مصرفی تکتک این سطوح را محاسبه کرده و باهم جمع کرد.
برای فهم بیشتر، مثال شکل ۴-۷ را در نظر بگیرید، همچنین فرض کنید پردازندهای دارای چهار سطح فرکانسی و توان متناظر با آن باشد که در جدول ۴-۱ نشان داده شده است.
جدول ۴جدول ۴-۱ فرکانسها و توان متناظر هر سطح فرکانسی
راهنمای ﻧﮕﺎرش ﻣﻘﺎﻟﻪ ﭘﮋوهشی درباره : زمانبندی وظیفهها در سیستمهای بیدرنگ نهفته چندهستهای با هدف بهبود ...