در سمت مقابل، وظایف غیرتناوبی که همانطور که از اسمشان پیداست دارای دوره تناوب نیستند و در زمان‌های تصادفی اتفاق می‌افتند، دارای ماهیت و اثری متفاوت نسبت به وظایف تناوبی هستند. در این نوع وظایف، علاوه براینکه عدم نقض سررسید برای‌مان مهم است، زمان‌پاسخ نیز از اهمیت بسیار بالایی برخوردار است. در همان مثال تلفن‌همراه، عمل لمس‌کردن صفحه و بازکردن یک برنامه یا فشار دادن کلید home که بعداز کلید power، بالاترین اولویت را در وظایف غیرتناوبی یک تلفن هوشمند دارد، دارای وظایف غیرتناوبی هستند و هنگامی که کاربر این وظایف را برای اجرا فراخوانی می‌کند، باید به سرعت اجرا شوند، در غیر این صورت، انتظار برای اجرای این نوع وظایف برای کاربر غیر قابل تحمل است. بنابراین در اجرای این وظایف باید سعی شود تا کمترین زمان پاسخ را دارا باشند و متوسط زمان انتظار آن‌ ها تا حد امکان کاهش یابد.

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

با توجه به همین مسائل، ما در الگوریتم خود، وظایف تناوبی را از وظایف غیرتناوبی جدا کرده‌ایم. پس از تفکیک این دو نوع وظیفه در زیرمجموعه‌های مجزا، هرکدام از این زیرمجموعه‌ها را با روشی جدید به گروهی از هسته‌ها اختصاص می‌دهیم. روش ما به این صورت است که با توجه به نوع وظایف سیستم و مشخصات آن‌ ها و با توجه به تعداد هسته‌های پردازنده، این توزیع صورت گیرد. به عنوان مثال در یک سیستم چهارهسته‌ای، سه حالت برای تفکیک هسته‌ها وجود دارد، یک حالت دو هسته برای وظایف تناوبی و دو هسته برای وظایف غیرتناوبی، حالت دیگر سه هسته برای وظایف تناوبی و یک هسته برای وظایف غیرتناوبی و حالت آخر نیز برعکس حالت قبلی می‌باشد. الگوریتم ما برای هر سه حالت اجرا می‌شود و سپس بهینه‌ترین حالت را برای تفکیک تعداد هسته‌ها انتخاب می‌کند. همچنین وظایف غیرتناوبی در مواقع و تحت شرایط خاصی که در بخش ۴-۵-۲ ذکر خواهدشد، می‌توانند از هسته‌های مربوط به وظایف تناوبی نیز استفاده کنند. این موضوع در شکل ۴-۲ بوسیله فلش‌های نقطه‌چین، بخوبی نشان داده شده است.
بنابراین در این مرحله که برای وظایف تناوبی و غیرتناوبی هرکدام ، بخشی از هسته‌ها در نظر گرفته شدند، زمانبندی سیستم آغاز می‌شود و توسط الگوریتم توزیع پیشنهادی در قسمت ۴-۵-۲ ، وظایف تناوبی به هسته‌های مشخص شده در این قسمت و وظایف غیرتناوبی نیز با الگوریتمی متفاوت بین هسته‌های درنظرگرفته شده برای خود، توزیع می‌گردنند. تعیین تعداد هسته‌های مربوط به وظایف تناوبی و غیرتناوبی که در بخش اول انجام می‌شود به صورت ایستا بوده و قبل از شروع زمانبندی می‌باشد.
مزایای بخش اول الگوریتم پیشنهادی ما این است که یک نوع توازن بار بین هسته‌ها ایجاد کرده و متناسب با ماهیت و خصوصیت وظایف یک سیستم، مجموعه‌ای از هسته‌ها را در اختیار آنها قرار می‌دهد. از آنجایی که سیاست‌های کاهش مصرف انرژی و افزایش بهره‌وری باهم در تضاد هستند، بنابراین تقسیم وظایف بین هسته‌ها امکان اعمال این سیاست‌ها بصورت جداگانه را درپی دارد، که این امر منجر به افزایش بهره‌وری در هسته‌های مربوط به وظایف غیرتناوبی و کاهش مصرف انرژی در هسته‌های مربوط به وظایف تناوبی می‌شود. همچنین این مسئله باعث پایداری بیشتر یک سیستم تعبیه‌شده بی‌درنگ می‌شود و اصل تعادل بارگذاری در توزیع وظایف رعایت شده و در نتیجه از تراکم بار و نقض سررسید وظایف در یک یا چند هسته محدود جلوگیری می‌کند
.
۴-۵-۲ بخش دوم الگوریتم پیشنهادی (توزیع وظایف بین هسته‌ها)
پس از اینکه توسط بخش اول روش پیشنهادی، تعداد هسته‌های مربوط به وظایف تناوبی و همچنین تعداد هسته های مربوط به وظایف غیرتناوبی مشخص شدند، سیستم توسط الگوریتم جدیدی که در این قسمت شرح داده می‌شود، وظایف را به هسته‌های مناسب اختصاص می‌دهد. این الگوریتم دارای دو قسمت متفاوت است، یک الگوریتم برای توزیع وظایف تناوبی و دیگری برای توزیع وظایف غیرتناوبی، که در دو بخش مجزا شرح خواهیم داد.
الگوریتم توزیع وظایف تناوبی:
روشی که ما برای اختصاص وظایف تناوبی به هسته‌های متناظرشان پیشنهاد داده‌ایم، در ابتدا به عامل بهره‌وری هر هسته توجه می‌کند. میزان بهره‌وری هر هسته بصورت مجموع نسبت زمان‌ اجرا به دوره تناوب وظایف تناوبی موجود در صف هسته، تعریف می‌شود. زمانیکه میزان بهره‌وری یک هسته و به عبارتی بارکاری آن افزایش یابد (u≥۱)، پردازنده قادر به اجرای تمامی وظایف نمی‌باشد و به ناچار برخی وظایف از صف هسته مربوطه، حذف خواهند شد. بنابراین برای جلوگیری از این عمل و ازیاد بیش از حد بارکاری هر پردازنده، وظایف تناوبی را مبتنی بر مقدار بهره‌وری هرکدام، طوریکه مجموع بهره‌وری وظایف موجود در صف هر هسته، کوچکتر از ۱ باشد، توزیع می‌کنیم.
با توجه به این تعریف، بهره‌وری هر وظیفه تناوبی به صورت زیر محاسبه می‌شود:
(۲۶)
که در آن،C_i بدترین حالت زمان اجرا و T_i دوره تناوب وظیفه تناوبی می باشد.
طی این الگوریتم، در ابتدا بهره‌وری تمام وظایف موجود در صف یک هسته محاسبه شده و مجموع آن به عنوان بهره‌وری کل آن هسته حساب می‌شود. این محاسبه برای همه هسته‌های مربوط به وظایف تناوبی انجام می‌شود، سپس وظیفه به هسته‌ای تخصیص داده خواهد شد که اولاً، روشن باشد (یعنی خالی نباشد) و ثانیا مجموع بهره‌وری وظایف موجود در آن، کمتر از دیگر هسته‌ها باشد. البته این مسئله شرایط و حالت‌های مختلفی دارد که در ادامه به شرح کامل آن می‌پردازیم.
هدف ما از ارائه این الگوریتم توزیع، این است که مصرف انرژی وظایف تناوبی را روی هسته‌ها، تا حد امکان کاهش دهیم، بنابراین در این الگوریتم، ابتدا بررسی می‌شودکه کدام هسته روشن و در حال کار است تا پس از آن، شرایط دیگر بررسی شود که آیا می‌توانیم به این هسته وظیفه را اختصاص دهیم یا خیر.
بنابراین در ابتدا، وظیفه تناوبی به هسته‌ای اختصاص پیدا می‌کند که تمام شرایط زیر را دارا باشد:

1. 1. هسته روشن باشد. ( یعنی صف آن خالی نباشد )

1. 1. مجموع بهره‌وری وظایف موجود در آن هسته، کوچکتر از ۱ باشد.

1. 1. مجموع بهره‌وری وظایف موجود در آن هسته، از بهره‌وری بقیه هسته‌ها کمتر باشد.

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

• • همه هسته‌های مربوط به وظایف تناوبی روشن بوده و بهره‌وری همه آن‌ ها بزرگتر یا مساوی یک باشد.

• • حداقل دو هسته روشن با بهره‌وری کوچکتر از ۱ وجود داشته باشند که بهره‌وری آنها باهم برابر باشد.

اگر هر کدام از شرایط بالا رخ دهد، وظیفه مورد نظر به هسته‌ای فرستاده می‌شود که واریانس سررسید بزرگتری دارد. همان‌طور که در مرجع ]۳۶ [اشاره شده، هرچقدر بتوانیم وظایف را براساس سررسیدشان، یکنواخت‌تر توزیع کنیم، احتمال از دست دادن سررسید کمتری خواهیم داشت. از آنجایی که واریانس، چگونگی توزیع یک پارامتر را شرح می‌دهد، در نتیجه از واریانس می‌توان به عنوان بیان‌کننده میزان تراکم یک پارامتر استفاده کرد. یک واریانس کوچک از سررسید وظیفه، نشان می‌دهد که فاصله زمانی بین دو سررسید کم است و احتمال از دست رفتن سررسید بیشتر می‌شود.
بنابراین ما در این شرایط، وظیفه را به هسته‌ای می فرستیم که فاصله بین سررسیدهای وظایف موجود در صف آن زیاد باشد، که این مهم توسط معیار واریانس بخوبی مشخص می‌شود. واریانس سررسید وظایف موجود در صف یک هسته از فرمول زیر محاسبه می شود:
(۲۷)
که در آن n تعداد وظایف موجود در صف یک هسته، سررسید متناظر هر وظیفه موجود در صف و میانگین سررسید وظایف موجود در صف هسته مورد نظر می‌باشد.
در ادامه الگوریتم این بخش داریم که، اگر حداقل دو هسته وجود داشته باشد که واریانس سررسید آن‌ ها باهم برابر باشد، آنگاه وظیفه موردنظر را به هسته‌ای می‌فرستیم که تعداد وظایف موجود در صف آن، کمتر از دیگری باشد.
اگر باز هم حداقل دو هسته وجود داشت که تعداد وظایف موجود در صف آن‌ ها باهم برابر بود، وظیفه موردنظر را به هسته‌ای اختصاص می‌دهیم که شماره سریال کمتری دارد. شبه کد این الگوریتم، در شکل ۴-۳ به طور کامل نشان داده شده است. همچنین فلوچارت این الگوریتم در شکل‌های ۴-۵ و ۴-۶ نشان داده شده است (منظور از عبارت هسته‌ها در این فلوچارت، هسته‌های مربوط به وظایف تناوبی است). اصطلاحات و توابعی که در این شبه‌کد استفاده شده است، به شرح زیر می‌باشد:
Core_all : همه هسته‌های پردازنده
Pcore_all : همه هسته‌های مربوط به وظایف تناوبی
Pcore_on , Pcore_off : هسته‌‌های مربوط به وظایف تناوبی که روشن هستند و هسته هایی که خاموش می‌باشند.
Pcore_MaxU : هسته‌‌های مربوط به وظایف تناوبی که بهره‌وری آن‌ ها بزرگتر یا مساوی ۱ باشد.
Pcore_t : هسته‌ای که وظیفه تناوبی در پایان الگوریتم به آن اختصاص خواهد یافت.
MinSerial (core_i) : تابعی است که هسته‌ای که شماره سریال آن کمترین است را برمی‌گرداند.
Num (core) : تابعی است که تعداد هسته‌ها را برگشت می‌دهد.
MinUtility (Pcore) : تابعی است که هسته‌‌ای را که کمترین بهره‌وری را دارد، برمی‌گرداند.
MaxMonotony (Pcore) : تابعی است که هسته‌هایی که دارای بیشترین واریانس سررسید باشند را برمی‌گرداند.
MinTaskNum (core) : تابعی است که هسته‌ای که دارای کمترین تعداد وظیفه در صف خود باشد را برمی‌گرداند.

1. 1. Begin

1. 1. Get status ( Pcore_all)

1. 1. if ( Pcore_off == Pcore_all)

1. 1. Pcore_t= MinSerial ( Pcore_off)

1. turn on MinSerial ( Pcore_off)