وظایف غیرتناوبی
Di : سررسید متناظر هر وظیفه
Ti : دوره تناوب وظایف تناوبی
Pi : اولویت وظایف غیرتناوبی
Ci : بدترین حالت زمان اجرای وظیفه
Ai : زمان ورود وظایف
tf : زمان خاتمه هر وظیفه
Ri : زمان پاسخ هر وظیفه
Ei : انرژی مصرفی هر وظیفه
4-4 مدل سيستم الگوريتم پيشنهادی
مدل پیشنهادی ما، یک سیستم تعبیه‌شده بی‌درنگ نرم چندهسته‌ای می باشد که هستههای آن دارای سطوح فرکانسی متفاوت و توان مصرفی متناسب با هر سطح فرکانسی می باشند. بی‌درنگ نرم بودن سیستم ما یعنی تمام سعی سیستم بر این است که وظایف قبل از سرسید خود اجرا شوند اما ممکن است برخی سررسیدها نقض شود و به دلیل بی‌درنگ نرم بودن سیستم، می‌توان از این نقض سررسید چشم‌پوشی کرد و سیستم بدون مشکل به کار خود ادامه دهد. همچنین سیستم ما دارای محدودیت منابع انرژی است و الگوریتم پیشنهادی توجه اساسی به کاهش مصرف انرژی سیستم دارد. نمونه‌ای از کاربرد این سیستم در تلفنهای هوشمند همراه می‌باشد که دارای وظایف بی‌درنگ نرم هستند. بر همین اساس، کاهش زمان انتظار اجرای وظایف غیرتناوبی نیز یکی دیگر از هدف‌های مهم سیستم ما می‌باشد. ایجاد یک توازن بین مصرف انرژی کم ، نقض سررسید کمتر و زمان پاسخ ایدال، یکی دیگر از دغدغه‌های ما در این سیستم می باشد که الگوریتم پیشنهادی توانسته تا حد زیادی این توازن را برقرار کرده و بهره‌وری و کارایی سیستم را افزایش دهد.
همچنین برای پیاده سازی سخت‌افزاری این سیستم میبایست از یک پردازنده مدیر ((Master برای اجرای الگوریتم استفاده شود و در صورت در دسترس نبودن یک پردازنده مدیر، از یکی از هسته‌ها برای اجرای الگوریتم استفاده می شود. ساختار کامل مدل سیستم پیشنهادی در شکل 4-2 نشان داده شده است.
شکل 4-2 مدل سیستم پیشنهادی
شکل 27شکل 4-2 مدل سیستم پیشنهادی
4-5 شرح کامل الگوريتم پيشنهادی
الگوریتم پیشنهادی ما دارای سه بخش می‌باشد که در این قسمت به شرح کامل این سه بخش، همراه با شبه‌کد الگوریتم پیشنهادی می‌پردازیم.
4-5-1 بخش اول الگوريتم پيشنهادی (تفکيک وظايف و هسته‌ها)
بخش اول الگوریتم پیشنهادی ما به این صورت است که ابتدا همه وظایفی که در سیستم بوجود آمده‌اند و در یک مجموعه بزرگ قرار گرفته‌اند را را به دو زیرمجموعه جدا تفکیک می‌کنیم. عامل تفکیک این مجموعه را تناوبی بودن و غیرتناوبی بودن وظایف در نظر می‌گیریم. یعنی وظایف تناوبی را از وظایف غیرتناوبی جدا کرده و هرکدام را در یک زیرمجموعه مجزا قرار می‌دهیم. علت این تفکیک‌سازی ما این است که ماهیت این دو نوع وظیفه باهم متفاوت است و اثرات آنها روی سیستم باهم فرق می‌کند. وظایف تناوبی مکرراً برا اساس نرخ دوره تناوب خود، تکرار می‌شوند. به عنوان یک مثال ساده از کاربرد این نوع وظایف، می‌توان به تلفنهای هوشمند همراه اشاره کرد. هنگامی که گوشی در وضعیت آماده بکار قرار دارد، تعدادی وظیفه در پس‌زمینه سیستم‌عامل آن، در حال اجرا هستند، مانند وظایف مربوط به آنتن‌دهی گوشی که دائماً اجرا شده تا وضعیت ارتباطی با شبکه، بروز شود. این وظایف از نوع تناوبی هستند و نیاز به این دارند که دائماً تکرار شوند، بنابراین می‌توانند نقش زیادی در مصرف انرژی داشته باشند. ویژگی بارزی که این وظایف دارند این است که زمان پاسخ آنها برای کاربر مهم نیست بلکه عدم نقض سررسید و مصرف انرژی کمتر برایش مهم است. بنابراین ماهیت این نوع وظایف مارا به سمت کاهش مصرف انرژی سوق می‌دهد، زیرا باید به خاطرتکرار دائم این وظایف و اجرای مکرر آنها، تا جایی که سررسید آنها نقض نشود، بتوانیم کاری کنیم که کمترین انرژی ممکن مصرف شود تا طول عمر باطری و خود سیستم (به دلیل کاهش گرمای تولید شده)، بیشتر شده و توان کمتری مصرف شود. این مسئله در گوشی‌های تلفن‌همراه بدلیل استفاده از باطری محدود برای ذخیره انرژی، بسیار حیاتی است.
در سمت مقابل، وظایف غیرتناوبی که همانطور که از اسمشان پیداست دارای دوره تناوب نیستند و در زمان‌های تصادفی اتفاق می‌افتند، دارای ماهیت و اثری متفاوت نسبت به وظایف تناوبی هستند. در این نوع وظایف، علاوه براینکه عدم نقض سررسید برای‌مان مهم است، زمان‌پاسخ نیز از اهمیت بسیار بالایی برخوردار است. در همان مثال تلفن‌همراه، عمل لمس‌کردن صفحه و بازکردن یک برنامه یا فشار دادن کلید home که بعداز کلید power، بالاترین اولویت را در وظایف غیرتناوبی یک تلفن هوشمند دارد، دارای وظایف غیرتناوبی هستند و هنگامی که کاربر این وظایف را برای اجرا فراخوانی می‌کند، باید به سرعت اجرا شوند، در غیر این صورت، انتظار برای اجرای این نوع وظایف برای کاربر غیر قابل تحمل است. بنابراین در اجرای این وظایف باید سعی شود تا کمترین زمان پاسخ را دارا باشند و متوسط زمان انتظار آنها تا حد امکان کاهش یابد.
با توجه به همین مسائل، ما در الگوریتم خود، وظایف تناوبی را از وظایف غیرتناوبی جدا کرده‌ایم. پس از تفکیک این دو نوع وظیفه در زیرمجموعه‌های مجزا، هرکدام از این زیرمجموعه‌ها را با روشی جدید به گروهی از هسته‌ها اختصاص می‌دهیم. روش ما به این صورت است که با توجه به نوع وظایف سیستم و مشخصات آنها و با توجه به تعداد هستههای پردازنده، این توزیع صورت گیرد. به عنوان مثال در یک سیستم چهارهسته‌ای، سه حالت برای تفکیک هسته‌ها وجود دارد، یک حالت دو هسته برای وظایف تناوبی و دو هسته برای وظایف غیرتناوبی، حالت دیگر سه هسته برای وظایف تناوبی و یک هسته برای وظایف غیرتناوبی و حالت آخر نیز برعکس حالت قبلی می‌باشد. الگوریتم ما برای هر سه حالت اجرا می‌شود و سپس بهینه‌ترین حالت را برای تفکیک تعداد هسته‌ها انتخاب می‌کند. همچنین وظایف غیرتناوبی در مواقع و تحت شرایط خاصی که در بخش 4-5-2 ذکر خواهدشد، می‌توانند از هستههای مربوط به وظایف تناوبی نیز استفاده کنند. این موضوع در شکل 4-2 بوسیله فلش‌های نقطه‌چین، بخوبی نشان داده شده است.
بنابراین در این مرحله که برای وظایف تناوبی و غیرتناوبی هرکدام ، بخشی از هسته‌ها در نظر گرفته شدند، زمانبندی سیستم آغاز می‌شود و توسط الگوریتم توزیع پیشنهادی در قسمت 4-5-2 ، وظایف تناوبی به هستههای مشخص شده در این قسمت و وظایف غیرتناوبی نیز با الگوریتمی متفاوت بین هستههای درنظرگرفته شده برای خود، توزیع می‌گردنند. تعیین تعداد هستههای مربوط به وظایف تناوبی و غیرتناوبی که در بخش اول انجام می‌شود به صورت ایستا بوده و قبل از شروع زمانبندی می‌باشد.
مزایای بخش اول الگوریتم پیشنهادی ما این است که یک نوع توازن بار بین هسته‌ها ایجاد کرده و متناسب با ماهیت و خصوصیت وظایف یک سیستم، مجموعه‌ای از هسته‌ها را در اختیار آنها قرار می‌دهد. از آنجایی که سیاست‌های کاهش مصرف انرژی و افزایش بهره‌وری باهم در تضاد هستند، بنابراین تقسیم وظایف بین هسته‌ها امکان اعمال این سیاست‌ها بصورت جداگانه را درپی دارد، که این امر منجر به افزایش بهره‌وری در هستههای مربوط به وظایف غیرتناوبی و کاهش مصرف انرژی در هستههای مربوط به وظایف تناوبی می‌شود. همچنین این مسئله باعث پایداری بیشتر یک سیستم تعبیه‌شده بی‌درنگ می‌شود و اصل تعادل بارگذاری در توزیع وظایف رعایت شده و در نتیجه از تراکم بار و نقض سررسید وظایف در یک یا چند هسته محدود جلوگیری می‌کند
.
4-5-2 بخش دوم الگوريتم پيشنهادی (توزيع وظايف بين هسته‌ها)
پس از اینکه توسط بخش اول روش پیشنهادی، تعداد هستههای مربوط به وظایف تناوبی و همچنین تعداد هسته های مربوط به وظایف غیرتناوبی مشخص شدند، سیستم توسط الگوریتم جدیدی که در این قسمت شرح داده می‌شود، وظایف را به هستههای مناسب اختصاص می‌دهد. این الگوریتم دارای دو قسمت متفاوت است، یک الگوریتم برای توزیع وظایف تناوبی و دیگری برای توزیع وظایف غیرتناوبی، که در دو بخش مجزا شرح خواهیم داد.
الگوريتم توزيع وظايف تناوبی:
روشی که ما برای اختصاص وظایف تناوبی به هستههای متناظرشان پیشنهاد داده‌ایم، در ابتدا به عامل بهره‌وری هر هسته توجه می‌کند. میزان بهره‌وری هر هسته بصورت مجموع نسبت زمان اجرا به دوره تناوب وظایف تناوبی موجود در صف هسته، تعریف می‌شود. زمانیکه میزان بهره‌وری یک هسته و به عبارتی بارکاری آن افزایش یابد (u≥1)، پردازنده قادر به اجرای تمامی وظایف نمی‌باشد و به ناچار برخی وظایف از صف هسته مربوطه، حذف خواهند شد. بنابراین برای جلوگیری از این عمل و ازیاد بیش از حد بارکاری هر پردازنده، وظایف تناوبی را مبتنی بر مقدار بهره‌وری هرکدام، طوریکه مجموع بهره‌وری وظایف موجود در صف هر هسته، کوچکتر از 1 باشد، توزیع می‌کنیم.
با توجه به این تعریف، بهره‌وری هر وظیفه تناوبی به صورت زیر محاسبه می‌شود:
u_i=C_i/T_i (26)
که در آن،Ci بدترین حالت زمان اجرا و Ti دوره تناوب وظیفه تناوبی می باشد.
طی این الگوریتم، در ابتدا بهره‌وری تمام وظایف موجود در صف یک هسته محاسبه شده و مجموع آن به عنوان بهره‌وری کل آن هسته حساب می‌شود. این محاسبه برای همه هستههای مربوط به وظایف تناوبی انجام می‌شود، سپس وظیفه به هسته‌ای تخصیص داده خواهد شد که اولاً، روشن باشد (یعنی خالی نباشد) و ثانیا مجموع بهره‌وری وظایف موجود در آن، کمتر از دیگر هسته‌ها باشد. البته این مسئله شرایط و حالت‌های مختلفی دارد که در ادامه به شرح کامل آن می‌پردازیم.
هدف ما از ارائه این الگوریتم توزیع، این است که مصرف انرژی وظایف تناوبی را روی هسته‌ها، تا حد امکان کاهش دهیم، بنابراین در این الگوریتم، ابتدا بررسی می‌شودکه کدام هسته روشن و در حال کار است تا پس از آن، شرایط دیگر بررسی شود که آیا می‌توانیم به این هسته وظیفه را اختصاص دهیم یا خیر.
بنابراین در ابتدا، وظیفه تناوبی به هسته‌ای اختصاص پیدا می‌کند که تمام شرایط زیر را دارا باشد:
هسته روشن باشد. ( یعنی صف آن خالی نباشد )
مجموع بهره‌وری وظایف موجود در آن هسته، کوچکتر از 1 باشد.
مجموع بهره‌وری وظایف موجود در آن هسته، از بهره‌وری بقیه هسته‌ها کمتر باشد.
اگر همه هستههای مربوط به وظایف تناوبی خاموش باشند، یکی از هسته‌ها را روشن کرده و وظیفه مورد نظر را به آن اختصاص می‌دهیم (هسته‌ای که شماره سریال کوچکتری دارد انتخاب می‌شود).
اگر هسته‌ای روشن بوده ولی مجموع بهره‌وری وظایف آن، بزرگتر یا مساوی 1 باشد، ددر این حالت نیز یکی از هستههای خاموش را روشن کرده و وظیفه را به آن اختصاص می‌دهیم. اگر حداقل دو هسته روشن بوده و بهره‌وری آنها کوچکتر از 1 باشد، آنگاه وظیفه را به هسته‌ای که بهروری آن از دیگری کمتر است اختصاص می‌دهیم.
این مراحل را تکرار می‌کنیم تا اینکه به یکی از شرایط زیر برخورد کنیم:
همه هستههای مربوط به وظایف تناوبی روشن بوده و بهره‌وری همه آنها بزرگتر یا مساوی یک باشد.
حداقل دو هسته روشن با بهره‌وری کوچکتر از 1 وجود داشته باشند که بهره‌وری آنها باهم برابر باشد.
اگر هر کدام از شرایط بالا رخ دهد، وظیفه مورد نظر به هسته‌ای فرستاده می‌شود که واریانس سررسید بزرگتری دارد. همانطور که در مرجع ]36 [اشاره شده، هرچقدر بتوانیم وظایف را براساس سررسیدشان، یکنواخت‌تر توزیع کنیم، احتمال از دست دادن سررسید کمتری خواهیم داشت. از آنجایی که واریانس، چگونگی توزیع یک پارامتر را شرح می‌دهد، در نتیجه از واریانس می‌توان به عنوان بیان‌کننده میزان تراکم یک پارامتر استفاده کرد. یک واریانس کوچک از سررسید وظیفه، نشان می‌دهد که فاصله زمانی بین دو سررسید کم است و احتمال از دست رفتن سررسید بیشتر می‌شود.
بنابراین ما در این شرایط، وظیفه را به هسته‌ای می فرستیم که فاصله بین سررسیدهای وظایف موجود در صف آن زیاد باشد، که این مهم توسط معیار واریانس بخوبی مشخص می‌شود. واریانس سررسید وظایف موجود در صف یک هسته
