الگوریتمها بصورت پیشفرض، یک جزءبندی ایستا از n وظیفه به m زیرمجموعه مجزا تعریف می‌شود. سپس هر زیرمجموعه به صورت محلی، بروی یک پردازنده توسط یک الگوریتم زمانبندی مختص سیستم‌های تک‌پردازنده، زمانبندی می‌شود. در واقع هر هسته پردازنده، وظایف مشخص شده خودش را با استفاده از یک الگوریتم جدا، زمانبندی می‌کند. ( شکل 3-4 – الف )
الگوریتم‌های کاملا مهاجرتی111 (عمومی112) :
در این سیاست یک زمانبند به عنوان نماینده کل سیستم، اجرای هر وظیفه روی هر پردازنده را زمانبندی می‌کند، بعلاوه اجرای وظایف می‌تواند، با احتمالی بیشتر از یک بار به حالت معلق رفته، سپس مجددا بازیابی شود و این بازیابی می‌تواند، در پردازنده متفاوتی رخ دهد. یعنی وظایف می‌توانند علاوه بر این که روی هر کدام از هسته‌ها اجرا شوند، می‌توانند بین هسته‌های پردازنده جابجا شوند. در این حالت یک صف تنهای عمومی برای همه وظایف بکار برده می‌شود و وظایف می‌توانند براساس اولویتشان بوسیله یک زمانبند، زمانبندی شوند. ( شکل 3-4 – ب )
الگوریتم‌های مهاجرتی محدودشده113 (دوگانه114) :
در این حالت تمامی وظایف می‌توانند، در پردازنده‌های متفاوتی اجرا شوند، اما حتی در صورت انحصاری بودن یک وظیفه باید کاملا بروی تنها یک پردازنده اجرا شوند. در واقع این نوع زمانبندی، ترکیبی از دو زمانبندی عمومی و جزبندی است که در آن برخی وظایف نمی‌توانند بین هسته‌ها جابجا شوند، در حالی که برخی دیگر از وظایف می‌توانند جابجا شوند. ( شکل 3-4 – ج )
وظیفه
دوره‌تناوب
زمان اجرا
بهره‌وری
T1
4
2
0.5
T2
5
2
0.4
T3
10
8
0.8

شکل 3-4 مثالی از زمانبندی تولید شده امکان‌پذیر، از الگوریتم : الف) جزءبندی ب) کاملا مهاجرتی ج) مهاجرتی محدودشده ]21[
شکل 7شکل 3-4 مثالی از زمانبندی تولید شده امکان‌پذیر، از الگوریتم : الف) جزءبندی ب) کاملا مهاجرتی ج) مهاجرتی محدودشده [21]
الگوریتم‌های جزءبندی به دلیل سادگی پیاده‌سازی ساده، به‌صورت گسترده مورد استفاده قرار می‌گیرند. کارایی این دسته از الگوریتم‌ها، زمانیکه از الگوریتم‌های مبتنی بر تک‌پردازنده شناخته‌شده و معروف مانند EDF و RMS استفاده می‌کنند، منطقی است ]21[ .
3-4-1 معایب روش‌های زمانبندی عمومی و جزبندی
یکی از مهم‌ترین معایب زمانبندی عمومی این است که جابجایی وظایف بین هسته‌ها باعث بوجود آمدن ترافیک زیادی در حافظه نهان پردازنده می‌شود و ضعف وابستگی پردازنده و سربار انحصار طلبی، باعث می‌شود که سیستم‌های تعبیه‌شده، دچار آسیب شوند.
در طرف مقابل، روش جزبندی باعث می‌شود که متوسط زمان پاسخ سیستم برای کارهایی با اندازه بزرگ و وسیع بهبود پیدا کند. با این وجود نظریه جزءبندی، شامل چند عیب می‌باشد. در سیستم‌های پویا، هنگامی‌که وظایف در زمان اجرا وارد سیستم می‌شوند، این نظریه مشکل ساز می شود. چراکه ورود یک وظیفه جدید در سیستم، موجب می‌شود، مجموعه وظایف مجددا جزءبندی شوند و این باعث افزایش سربار زمان اجرا می‌شود.
بزرگترین عیب نظریه جزءبندی، این است که وقتی وظایف تناوبی، زمانبندی می‌شوند، این نظریه یک روش نیمه بهینه می‌باشد. به عنوان مثال، سه وظیفه با مشخصات موجود در جدول شکل 3-5 را در نظر بگیرید. در این حالت زمانبند باید بلافاصله متوجه شود که حتی اگر فاکتور بهره‌وری کل، تغییری نکند، در این هنگام هیچ الگوریتم زمانبندی جزءبندی‌‌ ای قادر به زمانبندی این مجموعه وظایف بروی یک m پردازنده ( m<3 ) نخواهد بود، چراکه تقاضای محاسباتی هر زیرمجموعه ممکن، از 2 و یا تعداد بیشتری وظیفه، از ظرفیت محاسباتی یک تک پردازنده تجاوز خواهد‌کرد]21[ . وظیفه دوره‌تناوب زمان اجرا بهره‌وری T1 4 2 0.5 T2 5 3 0.6 T3 10 6 0.6 شکل 3-5 مثالی کمی متفاوت از مثال قبلی ، که با رویکرد جزءبندی، قابل زمانبندی نیست]21[ شکل 8شکل 3-5 مثالی کمی متفاوت از مثال قبلی ، که با رویکرد جزءبندی، قابل زمانبندی نیست.[21] از دید نظری، کران‌های بهره‌وری شناخته‌شده تاکنون(که ضمانت می‌کنند، قادر به زمانبندی مجموعه وظایفی با فاکتور بهره‌وری داده‌شده، هستند ) برای نسخه‌های جزءبندی EDF و RMS ، محافظه‌کار می‌باشند. در حالت کلی، هیچ الگوریتم جزءبندی شده‌ای، دارای بدترین حالت بهره‌وری روی m پردازنده، بیشتر از "(m+1)" /"2" ندارد. توجه شود که m+1 وظیفه، هرکدام با بهره‌وری "(1+?)" /"2" نمی‌تواند بروی m پردازنده جزءبندی شود. در صورتیکه0 ?? ، کل بهره‌وری چنین مجموعه وظایفی به سمت "(m+1)" /"2" ، میل خواهد‌کرد]21[ . بطور کلی کران‌های بهره‌وری بهتر، می‌تواند توسط ایجاد محدودیت‌هایی روی بهره‌وری هر وظیفه، ایجاد شود. فرض کنید UMax بیشترین بهره‌وری هر وظیفه در مجموعه وظایف است، هر وظیفه می‌تواند به یک پردازنده که ظرفیت مجزایی از حداکثر UMax دارد، اختصاص یابد. این بدین معنی است که اگر یک مجموعه از وظایف قابل زمانبندی نباشند، دراین صورت هر پردازنده باید یک ظرفیتی حداقل به اندازه UMax داشته باشد. از این رو کل بهره‌وری چنین مجموعه وظیفه‌ای، بیشتر از m(1-UMax)+UMax خواهدبود. به عبارتی هر مجموعه وظیفه با حداکثر بهره‌وری به میزان m-(m-1)UMax ، قابل زمانبندی است]21[ . در شکل 3-6 نمودار تقسیم بندی الگوریتم‌های زمانبندی چندهسته‌ای نشان داده شده است. شکل 3-6 طبقه‌بندی الگوریتم‌های زمانبندی چندهسته‌ای ]21[ شکل 9شکل 3-6 طبقه‌بندی الگوریتم‌های زمانبندی چندهسته‌ای 3-5 زمانبندی چند هسته‌ای مبتنی بر DVFS115 در طی سال‌های گذشته تولیدکنندگان برای بهبود عملکرد پردازنده‌ها، از طریق بالابردن فرکانس ساعت پردازنده‌ها، باهم رقابت می‌کردند. اما تحت تکنولوژی‌های ساخت و فرایندساخت پردازنده، بالاترین فرکانس کاری یک پردازنده مبتنی بر CMOS 116، به بالاترین ولتاژ منبع احتیاج دارد. از آنجا که ولتاژ منبع تغذیه تاثیر مستقیمی روی سرعت پردازنده دارد، زمانبندی وظایف و انتخاب ولتاژ منبع باید همزمان مورد توجه قرار گیرد ]27[ . توان مصرفی پویای ( Pdynamic) یک پردازنده مبتنی بر CMOS ، با فرکانس کاری و ولتاژ منبع رابطه مستقیم دارد، یعنی: P_dynamic?f×V_dd^2 (3) بنابراین افزایش فرکانس کاری، فقط باعث افزایش بهره‌وری نمی‌شود، بلکه باعث می‌شود توان مصرفی نیز افزایش یابد. با توجه به این حقیقت که دستگاه‌هایی که از باطری‌های قابل حمل استفاده ‌می‌کنند، دارای انرژی محدودی هستند، تحقیقات روی ذخیره توان، توجه زیادی را به خود جلب کرده است که اغلب آن‌ها از تکنیک‌های DVFS برای افزایش طول عمر باطری دستگاه‌های قابل حمل استفاده کرده اند ]28[ . DVFS ولتاژ منبع و فرکانس کاری پردازنده را به صورت همزمان کاهش می‌دهد تا بتواند زمانی که ما نیاز به بهره‌وری کمی داریم، انرژی را ذخیره کند. همانند مغز انسان که مقدار زیادی انرژی مصرف می‌کند، پردازنده یک سیستم نیز انرژی زیادی را مصرف می‌کند. بنابراین معماری‌های چندهسته‌ای می‌توانند بهره زیادی از تکنولوژی DVFS ببرند ]29[ . در سیستم‌های چندهسته‌ای اولیه، همه هسته‌های پردازنده دارای یک ساعت مشترک بودند. تحت این معماری، هنوز DVFS می‌تواند باعث ذخیره انرژی شود، اما محدودیت‌های زیادی در این بین وجود دارد که ایجاد توازن بین کارایی و توان مصرفی را سخت‌تر کرده است. در پردازنده‌های امروزی هر هسته می‌تواند با فرکانس و ولتاژ متفاوتی کار کند. این پردازنده‌ها در دو مدل وجود دارند، حالت بسته117 و حالت برخط118. در حالت بسته، فرکانس هسته‌های پردازنده نمی‌تواند در حین اجرای یک وظیفه تغییر کند و فقط در ابتدا که وظیفه اجرایش آغاز می‌شود، می‌تواند تغییر کند. اما در حالت برخط، فرکانس هسته‌ها می‌تواند در هر لحظه از اجرای وظیفه تغییر کند ]30[ . دو استراتژی برای استفاده از تکنیک‌های DVFS برای کاهش مصرف انرژی وجود دارد: تغییر ولتاژ و فرکانس در زمان سکون وظیفه119 تغییر ولتاژ و فرکانس در هنگام دسترسی به منابع خارجی در روش اول که تغییر ولتاژ و فرکانس در زمان سکون وظیفه می باشد (منظور از زمان سکون وظیفه، مدت زمانی است که وظیفه در صف آماده پردازنده منتظر می‌شود تا اجرایش آغاز شود یا ادامه پیدا کند)، وقتی که پردازنده شروع به اجرای وظیفه می‌کند، فرکانس اجرایی آن در نسبت بین بدترین حالت زمان اجرا و سررسید وظیفه، ضرب می‌شود تا با این کار فرکانس اجرایی آن کاهش یافته و در نتیجه توان مصرفی کاهش یابد. مثالی از این حالت را در شکل3-7 مشاهده می‌کنید. شکل 3-7 نمونه‌ای از تنظیم فرکانس و ولتاژ در زمان سکون وظیفه، الف) بدون , DVFS ب) با DVFS شکل 10شکل 3-7 نمونه‌ای از تنظیم فرکانس و ولتاژ در زمان سکون وظیفه، الف) بدون , DVFS ب) با DVFS در مرجع ]31[ روشی پیشنهاد شده که در آن از ترکیب دو مولفه برخط و برون خط استفاده شده تا هم قید زمانی را در نظر بگیرند و هم انرژی مصرفی را کاهش دهند. در این روش، مولفه برون‌خط، کمترین سزعت ممکن پردازنده را پیدا می‌کند که در این سرعت پایین، همچنان همه قیود زمانی بهبود داشته است. از سوی دیگر مولفه برخط به صورت پویا سرعت عملیاتی را تغییر می‌دهد تا انرژی و توان بیشتری ذخیره شود. بنابراین زمان اجرای وظیفه، ممکن است کمی تغییر کند. در مرجع ]32[ نیز از یک وقفه برای بروز رسانی فرکانس مناسب استفاده شده تا تغییرات ناگهانی حجم‌بار، در نظر گرفته شود. در این الگوریتم از داده‌های مربوط به تاریخچه برای پیشبینی حجم‌بار بعدی استفاده می‌شود و سپس با توجه به خطای پیشبینی120، نرخ بروز رسانی فرکانس، تنظیم می‌شود. روش دوم که تغییر فرکانس و ولتاژ در هنگام دسترسی به منابع خارجی است، هنگامی استفاده می‌شود که وظایف ما دارای محدودیت حافظه و I/O (ورودی/خروجی) باشند. می‌دانیم که سرعت عملیاتی حافظه و لوازم جانبی بسیار کمتر از پردازنده است، بنابراین برای وظایفی که مکرراً باید منتظر رسیدن مقادیرشان از حافظه یا I/O هستند، فرکانس عملیاتی پردازنده می‌تواند کاهش پیدا کند ]33[ . بنابراین تا وقتی که پردازنده منتظر مقادیر خارجی برای پایان دادن به وظیفه مورد است، توان کمتری مصرف می‌شود. 3-6 بررسی کارهای گذشته در این بخش به بررسی و شرح کامل چند الگوریتم پیشنهاده‌شده مهم زمانبندی و توزیع وظایف در سیستم‌های تعبیه‌شده چند هسته‌ای خواهیم پرداخت و همچنین مزایا و معایب آن‌ها را را بیان می‌کنیم. 3-6-1 الگوریتم توزیع بار غیر تعادلی LU-McEP121 یکی از کارهایی که برای کاهش مصرف انرژی و توان پردازنده‌های چندهسته‌ای تعبیه‌شده انجام شده، روش پیشنهادی در مرجع ]34[ بوده که یک روش بارگیری نامتعادل122 است که وظایف را به دو دسته تناوبی و غیرتناوبی تقسیم می‌کند.در این روش، وظایف تناوبی به حداقل هسته‌ها متمرکز می‌شوند تا بقیه هسته‌ها بتوانند خاموش بمانند. برای اینکه هیچ سررسیدی از دست نرود، این روش از دو الگوریتم زمانبندی استفاده کرده است که یکی RMS و دیگری SQ 123 می‌باشد. RMS برای متمرکز کردن وظایف تناوبی استفاده شده است و برای اینکه بفهمد که یک وظیفه تناوبی، امکان متمرکزسازی دارد یا نه از حد آستانه بهره‌وری124 استفاده می‌کند تا تعیین کند که یک وظیفه تناوبی چقدر قابلیت متمرکز سازی دارد. رابطه حد آستانه بهره‌وری به صورت زیر است: ?_(i=)^n?C_i/T_i ?n(?(n&2)-1) (4) که در آن، n تعداد کل وظایف تناوبی است، C زمان اجرای هر وظیفه و T دوره‌تناوب هر وظیفه می‌باشد. از الگوریتم SQ در این روش برای توزیع وظایف غیرتناوبی روی هسته‌های باقیمانده استفاده شده است. در SQ یک وظیفه جدید به هسته‌ای که کمترین تعداد وظایف را دارد، فرستاده می‌شود. مهم‌ترین چیز برای سنجیدن کارایی وظایف تناوبی، اجرای قبل از سررسید آن می‌باشد، تا اجرای سریع آن‌ها. یعنی در وظایف تناوبی مشکل زمان انتظار نسبت به سررسید خیلی مهم نیست. در مقابل در وظایف غیرتناوبی که کمتر اتفاق می‌افتند و خیلی زود در آینده‌ای نزدیک رخ نمی‌دهند( مانند ورودی‌های کاربر، از قبیل لمس‌کردن صفحه نمایش لمسی و باز کردن یک برنامه کاربردی )، از روش توزیع بار استفاده می‌کنیم. وقتی کار یک وظیفه غیرتناوبی تمام می‌شود، هسته متناظرش می‌تواند خاموش شود، همچنین حافظه نهان آن هسته نیز می‌تواند خاموش شود، چون وظیفه از نوع غیرتناوبی است و قرار نیست تا آینده‌ای نزدیک دوباره تکرار شود. همچنین از آنجایی که زمان پاسخ از سررسید در این وظایف مهم‌تر است، به علت توزیع این وظایف بین بقیه پردازنده‌ها، زمان پاسخ‌دهی آن‌ها کاهش می‌یابد. دو روش در مدیریت توان به عنوان نماینده‌ای از بقیه روش‌ها وجود دارد: DVS 125 DPM 126 DVS به طور معمول برای ذخیره و صرفه‌جویی توان استفاده می‌شود، زیرا توان پویا با Vdd متناسب است که Vdd ولتاژ منبع می‌باشد. p=???C_L×f×V_dd^2 ? (5) که در آن CL ظرفیت خازن بارگذاری می‌باشد. امروزه با تکنولوژی نانو، که ولتاژ منبع را می‌توان به اندازه ولتاژ آستانه127 پایین آورد ( ولتاژ آستانه، حداقل ولتاژ لازم برای کارکردن پردازنده است)، بهره‌وری DVS کمتر شده است. بنابراین خیلی مشکل است که از DVS به عنوان یک روش با بهره‌وری خوب در محیط‌هایی با بارگذاری متغییر پویا استفاده‌شود. از این‌رو محاسبه سطح ولتاژ مناسب برای هر وظیفه در زمان اجرا مشکل است. برای استفاده DVS در محیط‌های واقعی غیرقابل پیشبینی، نیاز به زیرساخت‌های پیشبینی اضافی می باشد، اما این زیرساخت‌های اضافی باعث ایجاد سربار در سیستم‌های تعبیه‌شده می‌شوند که باعث محدود کردن منابع سخت‌افزاری می‌گردد. در این مقاله از روش DPM برای کاهش مصرف توان استفاده شده است که هسته‌ها را به صورت پویا خاموش می‌کند. این روش بیشتر در کاهش توان نشتی128 موثر است. روش‌های کاهش دما( مدیریت دما) باید شامل انتخاب یک سیاست در زمانبندی باشند، اگرچه پردازنده‌های تعبیه‌شده‌‌‌، در مقایسه با پردازنده‌هایی با کارایی بالا مانند Intel CORE i7 سبب افزایش دمای بیش از اندازه نمی‌شوند.بنابراین در این الگوریتم از دما صحبتی نشده‌است. برای وظایف غیرتناوبی که مجبور نیستیم محتویاتشان را بعداز اتمام اجرا در حافظه نهان نگه داریم( چون به ندرت رخ می‌دهند و دیربه دیر تکرار می‌شوند)، می‌توانیم هسته‌ها را به طور کامل خاموش کنیم و حتی حافظه نهان مربوطه را هم خاموش نماییم. اما برای وظایف تناوبی این‌طور نیست، حتی در حالت بیکار129 هم باید هسته‌ها و حافظه نهان روشن بمانند. بهترین مثال‌ها برای وظایف تناوبی، برنامه‌های دنباله‌دار( جریان‌دار پشت‌سرهم) هستند، مانند پخش یک آهنگ یا اجرای یک بازی یا پخش فیلم و... و بهترین مثال‌ها برای وظایف غیرتناوبی، برنامه‌هایی هستند که با کاربر در تعامل هستند، مانند پیمودن صفحه‌های منوهای یک تلفن‌همراه و یا بازکردن برنامه‌ها و لمس‌کردن روی آیکون‌ها و... در وظایف تناوبی، داده‌ها باید مکررا درحال رمزگذاری و رمزگشایی باشند که دارای نرخ رمزگشایی نیز می‌باشند، به عنوان مثال اگر فرض کنیم در یک برنامه پخش آهنگ، زمان اجرای هر وظیفه به‌طور متوسط 200 میلی‌ثانیه و دوره تناوب آن یک ثانیه باشد، آنگاه بهره‌وری پردازنده برای این برنامه U=C/T=200ms/1000ms=0.2 می‌باشد. ( جون همواره زمان اجرای یک وظیفه از دوره‌تناوب آن کمتر است. در این نوع از برنامه‌ها که مسئله زمان مارا راضی نگه می‌دارد، نیازی به سرعت بیش‌از اندازه پردازش نداریم. بنابراین در مثال قبل که مربوط به برنامه H.264130 بود( یک برنامه رمزگشایی است که در پخش فایل‌های چندرسانه‌ای استفاده میشود)، فقط در هر ثانیه به 20 درصد از قدرت پردازش پردازنده احتیاج داشتیم. این یعنی 80 درصد از توان پردازشی پردازنده می‌تواند به وظایف دیگر اختصاص پیدا کند. از سوی دیگر برنامه‌هایی نظیر لمس‌کردن صفحه نمایش لمسی، شروع و فشاردادن یک برنامه کاملا تصادفی و غیرقابل پیشبینی اتفاق می‌افتند، و این وظایف که با کاربر در ارتباط هستند، وقتی که رخ می‌دهند باید بلافاصله اجرا شوند. اگرچه از نظر سررسید سخت‌گیری‌ ندارند، اما تاخیر پاسخ‌دهی این‌گونه وظایف، کاملا واضح توسط کاربر قابل مشاهده و ناخوشایند است. شرح جزئیات الگوریتم: استراتژی که دراینجا توسط Jeon ، Lee و Chung پیشنهاد شده]34[، دو نوع وظیفه را پوشش می‌دهد، به این صورت که وظایف تناوبی را به حداقل هسته‌ها و وظایف غیرتناوبی را به بقیه هسته‌های پردازنده اختصاص می‌دهد. از این طریق، هم مصرف انرژی بدلیل اختصاص وظایف تناوبی به کمترین تعداد هسته‌ها، کاهش می‌یابد و هم بدلیل توزیع وظایف غیرتناوبی به بقیه هسته‌ها، متوسط زمان انتظار برای اجرای وظایف غیرتناوبی کاهش داده‌ می‌شود. برای وظایف تناوبی، بارگذاری روی یک هسته، زمانی تغییر می‌کند که سیستم در دو شرایط مختلف قرار گیرد: 1)موقعی که یک وظیفه جدید ایجاد می‌شود. 2)موقعی که یک وظیفه موجود به پایان می‌رسد. در هردو حالت با استفاده از RMS نباید سررسید وظایف از دست برود. وقتی که یک وظیفه جدید ایجاد می‌شود، زمانبند به دنبال هسته‌ای می‌گردد که روشن باشد و کمترین بارگیری را داشته‌ باشد. وقتی هیچ هسته‌ای وجود نداشته باشد که بتواند وظیفه جدید را اجرا کند، یکی از هسته‌هایی که خاموش بودند، روشن می‌شوند و این وظیفه جدید به آن اختصاص میابد. وقتی یک وظیفه موجود کارش تمام شود، زمانبند چک می‌کند که آیا این هسته که اخیرا این وظیفه روی آن کارش تمام شد، می‌تواند خاموش شود یا خیر. برای به حداقل رساندن تعداد هسته‌های روشن، زمانبند به دنبال هسته‌ دیگری می‌گردد تا وظایف تناوبی باقیمانده را به آن منتقل کند، به این صورت که اگر هر هسته‌ای که بارکاری آن به اندازه کافی کم باشد تا بتواند وظایف باقیمانده از یک هسته دیگر را اجرا کند، پیدا شود، وظایف باقیمانده از هسته قبلی به این هسته انتقال می‌یابند و هسته قبلی خاموش می‌شود، در غیر این صورت جابجایی مجدد برویش انجام نمی‌شود. TaskInit (pNewtask,pSchedparam,... ) Do task initialization // find a core on which new task is to be assigned according to // the task's scheduling policy. If (pSchedparam->schedpolicy == RMS)
// if periodic task, find the an idle core
Core = findBusiestCore();
If (pSchedparam-schedpolicy ==FCFS)
// if aperiodic task, find the an idle core
Core = findIdlestCore();

Insert the to the selected core’s readt queue
شکل 3-8 شبه کد الگوریتم تخصیص وظایف]34[
شکل 11شکل 3-8 شبه کد الگوریتم تخصیص وظایف [34]
در شکل 3-8 شبه‌کد تخصیص یک وظیفه جدید ایجاد شده، براساس مشخصات وظیفه می‌باشد. این کد با سیاست زمانبندی خود در واقع وظایف تناوبی را از وظایف غیرتناوبی جدا می‌کند.(تمایز قائل می‌شود)
اگر وظیفه جدید ایجاد شده تناوبی بود، پررفت‌وآمدترین هسته برای اجرای این وظیفه جدید، انتخاب می‌شود و تا زمانی که سررسید آن فرابرسد می‌تواند اجرا شود. اما اگر وظیفه جدید ایجادشده، غیرتناوبی بود، بیکارترین هسته انتخاب خواهد شد تا وظیفه در آن اجرا شود.
این تراکم بارگذاری روی تعداد کمی هسته( توسط وظایف غیرتناوبی) ممکن است منجر به این شود که بخشی از ظرفیت محتوای حافظه نهان L1 از دست برود. به هر حال پردازنده‌های چندهسته‌ای جدیدنتنها دارای حافظه نهان L1 برای هر هسته به صورت جداگانه هستند، بلکه دارای یک حافظه نهان L2 مشترک بسیار بزرگ نیز هستند. این حافظه نهان L2 می‌تواند جریمه فقدان131 حافظه نهان L1 را به حداقل ممکن برساند که در مقایسه با زمان کل اجرا، زیاد نیست. در آزمایش این مقاله که از پردازنده ARM11MPcore استفاده شده، دارای 4 حافظه نهان L1 32 کیلوبایتی و یک حافظه نهان L2 یک مگابایتی است.
برای وظایف غیرتناوبی از الگوریتم‌های دیگری استفاده شده است که یکی برای زمانبندی درون‌هسته‌ای132 و دیگری برای زمانبندی بین‌هسته‌ای133 استفاده می‌شود. برای زمانبندی درون‌هسته‌ای در اینجا از الگوریتم SQ استفاده شده است که به این معنی است که وقتی یک وظیفه جدید بوجود آمد، آن را به هسته‌ای می فرستد که دارای کوتاه ترین صف وظایف درحال انتظار برای اجرا باشد. در واقع وظایف غیرتناوبی تا حد امکان به صورت مساوی بین هسته‌ها توزیع می‌شوند. اما برای زمانبندی بین‌هسته‌ای از سیاست FCFS 134 استفاده می‌شود.
مزایا و معایب این الگوریتم :
این الگوریتم، بدلیل تفکیف وظایف تناوبی و غیرتناوبی از یکدیگر (بدون در نظر گرفتن نرخ نقض سررسید)، می‌تواند همزمان هم به انرژی مصرفی کمتر برای وظایف تناوبی و زمان پاسخ بهتر برای وظایف غیرتناوبی تا حدودی دست پیدا کند. همچنین بدلیل متمرکز کردن وظایف تناوبی روی تعداد بسیار محدود هسته‌ها، می‌تواند انرژی مصرفی را تا حد زیادی کاهش دهد. اما این الگوریتم معایبی نیز دارد که عبارت انداز :
انتخاب هسته با بیشترین ازدحام، برای تخصیص وظیفه تناوبی به آن، با هدف خاموش نگه داشتن هسته‌های خاموش، درست است که باعث کاهش انرژی مصرفی هسته‌ها می‌شود اما این مسئله می‌تواند در هسته شلوغ، موجب حذف وظیفه(ها) بدلیل عدم سرویس دهی به موقع بدان‌ها شده و در نهایت نرخ خطای سررسید در آن‌ها افزایش می‌یابد.
توزیع بار ناهمگن و نامتعادل در هسته‌ها سبب روشن نگه داشتن بیش از اندازه برخی هسته‌ها در کنار خاموش بودن طولانی هسته‌های دیگر می‌شود. که این مسئله می‌تواند در حالت کلی قابلیت اعتماد سیستم را کاهش داده، هچنین موجب افزایش دمای بیش از اندازه برخی از هسته‌ها و آسیب دیدن آن‌ها در درازمدت شود. درنتیجه بازده و کارایی سیستم کاهش می‌یابد.
این سیستم در زمان توزیع وظایف غیرتناوبی، درصورت روشن بودن تمامی هسته‌ها، وظیفه را به هسته ای که کمترین تعداد وظیفه در صف آن موجود است، ارسال می‌کند. واضح است که لزوما تعداد کم وظایف در صف هسته، سبب سرویس دهی سریعتر نمی‌باشد بلکه این مسئله به زمان اجرای وظایف وابسته می‌باشد. بنابراین ممکن است، این نحوه تخصیص سبب افزایش زمان پاسخ وظایف غیزتناوبی شود.
وظایف غیرتناوبی در صف هر هسته براساس سیاست FCFS، اجرا می شوند. این مسئله سبب اجرای دیرهنگام وظایف با اولویت بالاتر شده و می‌تواند زمان پاسخ آن‌ها را افزایش دهد.
این الگوریتم در زمانیکه هسته ای در وظایف تناوبی، ازدحام کمی داشته باشد، سعی در ارسال وظایف آن هسته به سایر هسته ها و خاموش کردن هسته مورد نظر دارد. این مسئله علاوه بر سربار جهت زمان انتقال وظایف، موجب ازدحام هسته های دیگر و افزایش خطای نرخ سررسید می‌شود.
3-6-2 الگوریتم زمانبندی غیرتعادلی جزبندی با RBound
در مرجع ]35[ نیز همانند مرجع ]34[ از یک روش بارگذاری غیرتعادلی استفاده شده است که روی وظایف تناوبی و غیرتناوبی در سیستم‌های تعبیه‌شده بی‌درنگ چندهسته‌ای سخت، برای کاهش مصرف توان اعمال می‌شود. در این مقاله از یک معماری زمانبندی دو سطحی استفاده شده است که در سطح بالایی وظایف تناوبی بوسیله الگوریتم RBound-FF که این الگوریتم در قسمت بعدی توضیح داده خواهد شد، به تعداد محدودی از هسته‌ها فرستاده می‌شوند و وظایف غیرتناوبی به هسته‌های باقیمانده ارسال می‌شوند. اما در سطح پایینی این طرح زمانبندی، از دو زمانبند استفاده شده است، یکی برای وظایف تناوبی و دیگری برای وظایف غیر تناوبی. برای وظایف تناوبی از الگوریتم RMS استفاده شده و برای وظایف غیرتناوبی، الگوریتم DMS 135 بکار برده شده است. مشخصه‌هایی که برای یک وظیفه در این مقاله استفاده شده عبارت‌انداز:
Ti : دوره تناوب وظیفه تناوبی i
Ci : بدترین حالت زمان اجرای یک وظیفه تناوبی
Pi : اولویت هر وظیفه تناوبی که برابر است با 1/T_i و برای وظایف غیرتناوبی برابر است با 1/D_i
RMS : الگوریتم زمانبندی نرخ یکنواخت که برای زمانبندی وظایف تناوبی استفاده شده است.
Ai : زمان ورود یک وظیفه غیر تناوبی
Di : سررسید هر وظیفه
DMS : الگوریتم زمانبندی سررسید یکنواخت
در هر دو حالت تناوبی و غیرتناوبی، وظایف قابل دسترسی که اولویت بالاتری داشته باشند، پردازش می‌شوند.
الگوریتم RBound-FF :
Rbound یک شرایط قابل زمانبندی تک پردازنده‌ای برای RMS است، که با استفاده از دوره‌تناوب وظایف تناوبی، بهره‌وری بالایی برای پردازنده ایجاد می‌کند. مجموعه وظایف ورودی T با m وظیفه، بوسیله Rbound شدن، مطابق الگوریتم scale task set که در شکل 3-9 آورده‌شده است، تبدیل به مجموعه T’ می‌شود. این الگوریتم، مجموعه وظایفی را پیدا می‌کند که نسبت حداکثر و حداقل دوره تناوب‌هایش، کمتر از 2 باشد. در واقع یک اجازه‌ای بر اساس Rbound برای T’ صادر می‌شود. R را به عنوان نسبت کمترین به بیشترین دوره تناوب بین همه وظایف در سیستم تعریف می‌کنیم. بنابراین با r<2 در پایان الگوریتم برای m وظیفه داریم: (6) -1) + 2/(r-1) URbound (r,m) = (m-1)( r^(1/(m-1)) Rbound می‌گوید که اگر T' خروجی الگوریتم ScaleTaskSet باشد و عبارت (7) ? URbound (r,m) ???Ci/Ti? برقرار باشد(r=Tm'/T1' )، آنگاه T یک مجموعه وظیفه قابل زمانبندی روی یک تک پردازنده بوسیله RMS است. Scale TaskSet(Input: T) Begin Sort the tasks in T by increasing period While T1 ? Tm /2 Ci = 2 Ci Ti = 2 Ti Sort the task in T by increasing period End while ? i, T_i^'=T_i; C_i^'=C_i; Return (T') end شکل 12شکل 3-9 الگوریتم ScaleTaskSet [35] جزبندی با Rbound : بیشتر الگوریتم‌های پیشنهاد شده با RMS اولویت‌دار، براساس جزبندی‌کردن هستند، بنابراین زمانبندی عمومی با RMS اولویت‌دار می‌تواند بازده کمی در بدترین حالت روی بهره‌وری پردازنده داشته باشد. استراتژی جزبندی شامل دو قسمت زیر است: تخصیص دادن وظایف به هسته‌ها زمانبندی وظایف روی هر پردازنده در الگوریتم RBound ، زمانی که r مربوط به هر وظیفه، به عدد 1 نزدیک می‌شود، این نوع وظایف به هسته یکسانی فرستاده می‌شوند، در نتیجه بهره‌وری پردازنده به 100 درصد می‌رسد (صرف نظر از تعداد وظایف). برای نزدیک شدن r به 1 باید وظایفی که نزدیک‌ترین دوره تناوب را دارند، در مجموعه وظایف مندرج شده T' قرار داد شوند و این کار با مرتب‌کردن وظایف در T' براساس افزایش دوره تناوب و سپس فرستادن وظایف به پردازنده با روش‌های Next-Fit و یا First-Fit امکان‌پذیر می‌باشد. در اینجا برای وظایف تناوبی از روش First-Fit استفاده شده است، زیرا First-Fit به خاطر جستجو در یک مجموعه جهانی136 از بین پردازنده‌های جستجو شده بوسیله Next-Fit ، بهتر از Next-Fit عمل می‌کند. در سیستم‌هایی با وظایف تناوبی، عمل تخصیص وظایف، زمانی اتفاق می‌افتد که یک وظیفه جدیدی بوجود می آید. به هر حال RBound-FF وقتی که مجموعه وظایف تناوبی سیستم، بر اساس دوره تناوب، مرتب شوند، می‌تواند بیشترین بهره‌وری پردازنده را به ما بدهد. بنابراین در اینجا فقط وظایف تناوبی، در مرحله مقداردهی اولیه وظیفه، به هسته‌های مناسب محدود می‌شوند و سپس وقتی که این وظایف به طور کامل ایجاد شدند، به هسته‌ها اختصاص می‌یابند. RBound-FF_init(Input: T,p) Begin ScaleTaskSet(T , T') For (i=1 ; i?m ,i++) For (j=1 ; j?pn ; j++) If ( ?i can be admitted by Rbound an pj ) Bound ?i to pj Else If (j== pn) return(REJECT) Endif Endfor Endfor Return(ACCEPT) end شکل 3-10 شبه کد الگوریتم RBound-FF ]35[ شکل 13شکل 3-10 شبه کد الگوریتم RBound-FF [35] بهره‌وری RBound برای وظایف غیرتناوبی: برای وظایف غیرتناوبی، مجموعه V(t) به عنوان مجموعه همه وظایف درگیری که وارد شده‌اند، اما سررسیدشان سپری نشده است، به صورت زیر تعریف می‌شوند: V(t) = { Ti | Ai ? t < Ai + Di } (8) S(t) که زیرمجموعه V(t) است، شامل فقط وظایفی در V(t) است که بعداز شروع آخرین دوره تناوب زمان بیکاری پردازنده، وارد شوند. و در نهایت می‌رسیم به تعریف بهره‌وری ترکیبی که عبارت انداز: u(t)=?_(Ti ?s(t))?C_i/D_i (9) یک مجموعه از n وظیفه غیرتناوبی، بوسیله سیاست زمانبندی DMS ، قابل زمانبندی است هرگاه : ? t :U(t)?UB(n) (10) که UB(n) به صورت زیر تعریف می‌شود: UB(n)={?(1/2+1/2n for n<[email protected]/(1+?(1/2(1-1/(n-1)))) for n?3)? (11) معماری زمانبندی الگوریتم مرجع ]35[ : می‌دانیم که وظایف تناوبی در سیستم‌های تعبیه‌شده، دائم در حال تکرار شدن اجرایشان هستند، تا زمانیکه پردازنده خاموش شود. بنابراین بهتر است که بین تکرار وظایف، هسته‌ها بجای اینکه خاموش و روشن شوند، به حالت مصرف‌پایین137 بروند. در این الگوریتم وظایف تناوبی را به تعداد کمی هسته محدود کرده اند تا به حداقل هسته‌ها برای روشن ماندن نیاز داشته باشند، از سوی دیگر، وظایف غیرتناوبی را که خیلی کمتر رخ می‌دهند، به بقیه هسته‌ها اختصاص داده اند.وقتی اجرای یک وظیفه به پایان رسید، هسته‌ متناظر آن، همانند حافظه نهان آن، میتواند خاموش شود، بنابراین نیازی نیست محتوای مقادیر این وظایف که قرار نیست تا آینده‌ای نزدیک اتفاق بیوفتد، نگهداری شود. در الگوریتم این مقاله، وظایف تناوبی به وسیله الگوریتم RBound-FF به حداقل هسته‌ها اختصاص می‌یابند و وظایف غیرتناوبی بین بقیه هسته‌ها به صورت عادلانه توزیع می‌شوند. شبه کد این الگوریتم را در شکل 3-11 صفحه بعد مشاهده می‌کنید. 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
شکل 3-11 الگوریتم اختصاص دادن وظایف در مرجع ]35[
شکل 14شکل 3-11 الگوریتم اختصاص دادن وظایف در مرجع [35]
مزایا و معایب این الگوریتم:
این الگوریتم بدلیل استفاده از RMS در زمانبندی وظایف تناوبی و الگوریتم DMS برای زمانبندی وظایف غیرتناوبی، می‌تواند تاثیر بسازیی در کاهش نرخ نقض سررسید وظایف گردد. همچنین در این الگوریتم نیز وظایف تناوبی از وظایف غیرتناوبی تفکیک شده و جداگانه توزیع می‌شوند که در مصرف انرژی موثر می‌باشد.
اما از جمله معایب این الگوریتم این است که، ورود یک وظیفه جدید در سیستم، موجب می‌شود، مجموعه وظایف مجددا توسط الگوریتم RBound جزءبندی شوند و این مسئله باعث افزایش سربار زمان اجرا می‌شود. همچنین در این الگوریتم نیز فشار زیادی روی تعداد محدودی از هسته‌ها برای اجرای وظایف غیرتناوبی می‌باشد که باعث می‌شود کارایی سیستم پایین بیاید.
3-6-3 الگوریتم زمانبندی چند

این مطلب رو هم توصیه می کنم بخونین:   تحقیق دربارهحمل و نقل، نرم افزار
دسته‌ها: No category

دیدگاهتان را بنویسید