شکل ۲۶شکل ۴-۱ ساختار کلی زمانبندی سیستم پیشنهادی
۴-۲ کلیات الگوریتم پیشنهادی
الگوریتم پیشنهادی ما در این پژوهش شامل سه بخش متفاوت می‌باشد که در هر کدام از این بخش‌ها، روش جدیدی ارائه شده است که ترکیب این سه بخش، الگوریتم پیشنهادی ما را شکل خواهد داد. در این قسمت، هر یک از این سه بخش، به طور کلی و خلاصه، معرفی خواهند شد.
در بخش اول الگوریتم پیشنهادی، روش جدیدی برای نوع سازماندهی وظایف متناسب با هسته‌ها، پیشنهاد می‌شود. ویژگی بارز این سازماندهی این است که پیش از توزیع وظایف بین هسته‌ها، ماهیت وظیفه‌ها مورد توجه قرار می‌گیرد و براساس خصوصیت این وظایف تفکیک شده، سازماندهی هسته‌های پردازنده انجام می‌شود.

(( اینجا فقط تکه ای از متن درج شده است. برای خرید متن کامل فایل پایان نامه با فرمت ورد می توانید به سایت feko.ir مراجعه نمایید و کلمه کلیدی مورد نظرتان را جستجو نمایید. ))

در بخش دوم الگوریتم پیشنهادی، روش جدیدی برای توزیع وظایف بین هسته‌ها، پیشنهاد می‌شود، یعنی الگوریتم جدیدی برای مشخص شدن اینکه هر وظیفه باید به کدام هسته برای اجرا فرستاده شود، پیشنهاد می‌شود. الگوریتم توزیع پیشنهادی ما، هدف‌های مهمی را دنبال می‌کند، از جمله این هدف‌ها می‌توان به کاهش نرخ نقض سررسید، کاهش مصرف انرژی، افزایش زمان پاسخ برخی وظایف و افزایش بهره‌وری سیستم اشاره کرد. همچنین سعی شده است تا سربار پیچیدگی الگوریتم، نسبت به کارهای گذشته، کاهش پیدا کرده و کارایی سیستم افزایش یابد.
در بخش سوم الگوریتم پیشنهادی، تکنیک جدیدی برای تنظیم فرکانس و ولتاژ هسته‌ها، در هنگام اجرای وظایف روی هر هسته، پیشنهاد می شود. این الگوریتم، همزمان با الگوریتم توزیع، اجرا می‌شود و زمان اجرای نهایی وظایف و میزان انرژی مصرفی آن‌ها را محاسبه خواهد کرد. همچنین این الگوریتم، جز الگوریتم‌های تنظیم فرکانس سررسید محور می‌باشد که به این معنی است که این الگوریتم، علاوه بر اینکه سعی در کاهش مصرف انرژی دارد، سررسید وظایف را نیز در نظر دارد، یعنی با بهره گرفتن از تکنیک پیشنهادی، برای جلوگیری از نقض سررسید وظیفه در حال اجرا، در مواقع لازم، سطح فرکانس اجرایی هسته را افزایش می‌دهد.
۴-۳ مدل وظیفه الگوریتم پیشنهادی
در مدل پیشنهاد شده در این پژوهش، وظایف سیستم به دو دسته تناوبی و غیرتناوبی تقسیم می‌گردند. وظایف تناوبی از نوع غیر انحصاری بوده و وظایف غیرتناوبی از نوع انحصاری درنظر گرفته می شوند. این مسئله بدین معنی است که هرگاه وظیفه‌ای تناوبی در حال اجرا در هسته‌ای باشد و وظیفه دیگری با اولویت بالاتر از راه برسد، این وظیفه جدید نمی‌تواند پردازنده را از وظیفه در حال اجرا بگیرد و در انحصار خود قرار دهد. اما اگر وظیفه غیرتناوبی در حال اجرا باشد و وظیفه غیرتناوبی دیگری با اولویت بالاتر وارد صف این هسته شود، پردازنده از وظیفه در حال اجرا گرفته شده و به وظیفه با اولویت بالاتر داده می شود.
همچنین در این مدل، وظایف غیرتناوبی می‌توانند تحت شرایطی بین هسته‌ها مهاجرت کنند، اما وظایف تناوبی چنین اجازه‌ای ندارند و باید تا پایان اجرا، روی هسته‌ای که الگوریتم توزیع، آن را به وظیفه اختصاص داده، باقی بمانند.
مشخصه‌ های وظایف سیستم پیشنهادی به صورت زیر می باشد:
Si : مجموعه کل وظایف سیستم
Tp : مجموعه وظایف تناوبی
TAp : مجموعه وظایف غیرتناوبی
Di : سررسید متناظر هر وظیفه
Ti : دوره تناوب وظایف تناوبی
Pi : اولویت وظایف غیرتناوبی
Ci : بدترین حالت زمان اجرای وظیفه
Ai : زمان ورود وظایف
tf : زمان خاتمه هر وظیفه
Ri : زمان پاسخ هر وظیفه
Ei : انرژی مصرفی هر وظیفه
۴-۴ مدل سیستم الگوریتم پیشنهادی
مدل پیشنهادی ما، یک سیستم تعبیه‌شده بی‌درنگ نرم چندهسته‌ای می باشد که هسته‌های آن دارای سطوح فرکانسی متفاوت و توان مصرفی متناسب با هر سطح فرکانسی می باشند. بی‌درنگ نرم بودن سیستم ما یعنی تمام سعی سیستم بر این است که وظایف قبل از سرسید خود اجرا شوند اما ممکن است برخی سررسیدها نقض شود و به دلیل بی‌درنگ نرم بودن سیستم، می‌توان از این نقض سررسید چشم‌پوشی کرد و سیستم بدون مشکل به کار خود ادامه دهد. همچنین سیستم ما دارای محدودیت منابع انرژی است و الگوریتم پیشنهادی توجه اساسی به کاهش مصرف انرژی سیستم دارد. نمونه‌ای از کاربرد این سیستم در تلفن‌های هوشمند همراه می‌باشد که دارای وظایف بی‌درنگ نرم هستند. بر همین اساس، کاهش زمان انتظار اجرای وظایف غیرتناوبی نیز یکی دیگر از هدف‌های مهم سیستم ما می‌باشد. ایجاد یک توازن بین مصرف انرژی کم ، نقض سررسید کمتر و زمان پاسخ ایدال، یکی دیگر از دغدغه‌های ما در این سیستم می باشد که الگوریتم پیشنهادی توانسته تا حد زیادی این توازن را برقرار کرده و بهره‌وری و کارایی سیستم را افزایش دهد.
همچنین برای پیاده سازی سخت‌افزاری این سیستم میبایست از یک پردازنده مدیر ((Master برای اجرای الگوریتم استفاده شود و در صورت در دسترس نبودن یک پردازنده مدیر، از یکی از هسته‌ها برای اجرای الگوریتم استفاده می شود. ساختار کامل مدل سیستم پیشنهادی در شکل ۴-۲ نشان داده شده است.
مجموعه همه وظایف سیستم
مجموعه وظایف تناوبی
مجموعه وظایف غیرتناوبی
الگوریتم زمانبندی اولویت
الگوریتم زمانبندی اولویت
هسته۱
هسته۲
هسته۴
هسته۳
الگوریتم توزیع وظایف تناوبی
الگوریتم توزیع وظایف غیرتناوبی
الگوریتم تنظیم فرکانس
الگوریتم تنظیم فرکانس
الگوریتم تنظیم فرکانس
الگوریتم تنظیم فرکانس
الگوریتم زمانبندی EDF
الگوریتم زمانبندی EDF
خروجی سیستم : یک مجموعه زمانبندی شده
ورودی :
شکل ۴-۲ مدل سیستم پیشنهادی
شکل ۲۷شکل ۴-۲ مدل سیستم پیشنهادی
۴-۵ شرح کامل الگوریتم پیشنهادی
الگوریتم پیشنهادی ما دارای سه بخش می‌باشد که در این قسمت به شرح کامل این سه بخش، همراه با شبه‌کد الگوریتم پیشنهادی می‌پردازیم.
۴-۵-۱ بخش اول الگوریتم پیشنهادی (تفکیک وظایف و هسته‌ها)
بخش اول الگوریتم پیشنهادی ما به این صورت است که ابتدا همه وظایفی که در سیستم بوجود آمده‌اند و در یک مجموعه بزرگ قرار گرفته‌اند را را به دو زیرمجموعه جدا تفکیک می‌کنیم. عامل تفکیک این مجموعه را تناوبی بودن و غیرتناوبی بودن وظایف در نظر می‌گیریم. یعنی وظایف تناوبی را از وظایف غیرتناوبی جدا کرده و هرکدام را در یک زیرمجموعه مجزا قرار می‌دهیم. علت این تفکیک‌سازی ما این است که ماهیت این دو نوع وظیفه باهم متفاوت است و اثرات آن‌ها روی سیستم باهم فرق می‌کند. وظایف تناوبی مکرراً برا اساس نرخ دوره تناوب خود، تکرار می‌شوند. به عنوان یک مثال ساده از کاربرد این نوع وظایف، می‌توان به تلفن‌‌های هوشمند همراه اشاره کرد. هنگامی که گوشی در وضعیت آماده بکار قرار دارد، تعدادی وظیفه در پس‌زمینه سیستم‌عامل آن، در حال اجرا هستند، مانند وظایف مربوط به آنتن‌دهی گوشی که دائماً اجرا شده تا وضعیت ارتباطی با شبکه، بروز شود. این وظایف از نوع تناوبی هستند و نیاز به این دارند که دائماً تکرار شوند، بنابراین می‌توانند نقش زیادی در مصرف انرژی داشته باشند. ویژگی بارزی که این وظایف دارند این است که زمان‌ پاسخ آنها برای کاربر مهم نیست بلکه عدم نقض سررسید و مصرف انرژی کمتر برایش مهم است. بنابراین ماهیت این نوع وظایف مارا به سمت کاهش مصرف انرژی سوق می‌دهد، زیرا باید به خاطرتکرار دائم این وظایف و اجرای مکرر آنها، تا جایی که سررسید آنها نقض نشود، بتوانیم کاری کنیم که کمترین انرژی ممکن مصرف شود تا طول عمر باطری و خود سیستم (به دلیل کاهش گرمای تولید شده)، بیشتر شده و توان کمتری مصرف شود. این مسئله در گوشی‌های تلفن‌همراه بدلیل استفاده از باطری محدود برای ذخیره انرژی، بسیار حیاتی است.

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


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