دانلود پایان نامه user8209- فایل

Please enter banners and links.

فهرست شکلها
TOC \h \z \c “شکل” شکل 2-1- تابع بهره‌وری u(t) برای انواع مختلف وظایف بی‌درنگ PAGEREF _Toc422763903 \h 13شکل 2-2- نمودار گذار حالت یک وظیفه PAGEREF _Toc422763904 \h 14شکل 2-3 سررسید متناظر و سررسید مطلق یک وظیفه PAGEREF _Toc422763905 \h 17شکل 3-1 تفسیم‌بندی انواع روش‌های زمانبندی PAGEREF _Toc422763906 \h 26شکل 3-2 مثالی از کاربرد زمانبندی تک هسته‌ای با استفاده از الگوریتم EDF PAGEREF _Toc422763907 \h 27شکل 3-3 بررسی اجمالی معماری پردازنده AMP و SMP PAGEREF _Toc422763908 \h 30شکل 3-4 مثالی از زمانبندی تولید شده امکان‌پذیر، از الگوریتم : الف) جزءبندی ب) کاملا مهاجرتی ج) مهاجرتی محدودشده PAGEREF _Toc422763909 \h 32شکل 3-5 مثالی کمی متفاوت از مثال قبلی ، که با رویکرد جزءبندی، قابل زمانبندی نیست PAGEREF _Toc422763910 \h 33شکل 3-6 طبقه‌بندی الگوریتم‌های زمانبندی چندهسته‌ای PAGEREF _Toc422763911 \h 34شکل 3-7 نمونه‌ای از تنظیم فرکانس و ولتاژ در زمان سکون وظیفه، الف) بدون DVFS ب) با DVFS PAGEREF _Toc422763912 \h 36شکل 3-8 شبه کد الگوریتم تخصیص وظایف PAGEREF _Toc422763913 \h 40شکل 3-9 الگوریتم ScaleTaskSet PAGEREF _Toc422763914 \h 43شکل 3-10 شبه کد الگوریتم RBound-FF PAGEREF _Toc422763915 \h 45شکل 3-11 الگوریتم اختصاص دادن وظایف در مرجع [35] PAGEREF _Toc422763916 \h 46شکل 3-12 مدل سیستم مرجع [36] PAGEREF _Toc422763917 \h 50شکل 3-13 شبه کد الگوریتم ED3VFS PAGEREF _Toc422763918 \h 54شکل 3-14 مثالی از بارگذاری غیرتعادلی PAGEREF _Toc422763919 \h 55شکل3-15 مثالی از توزیع وظایف بی‌درنگ PAGEREF _Toc422763920 \h 56شکل 3-16 شبه کد الگوریتم توزیع وظایف TLDHLB PAGEREF _Toc422763921 \h 59شکل 3-17 شبه‌کد الگوریتم جزبندی با WFD PAGEREF _Toc422763922 \h 61شکل 3-18 شبه کد زمانبند پیشنهادی در [37] PAGEREF _Toc422763923 \h 62شکل 3-19 شبه‌کد سیاست اجرای EDF PAGEREF _Toc422763924 \h 62شکل 3-20 شبه‌کد سیاست زمانبندی TBS و EDF PAGEREF _Toc422763925 \h 63شکل 3-21 شبه‌کد روش مهاجرت وظایف غیرتناوبی در [37] PAGEREF _Toc422763926 \h 63شکل 3-22 نمودار زمانی مثال مربوطه در [37] PAGEREF _Toc422763927 \h 65شکل 4-1 ساختار کلی زمانبندی سیستم پیشنهادی PAGEREF _Toc422763928 \h 67شکل 4-2 مدل سیستم پیشنهادی PAGEREF _Toc422763929 \h 70شکل 4-3 شبه‌کد الگوریتم توزیع وظایف تناوبی PAGEREF _Toc422763930 \h 76شکل 4-6 شبه‌کد الگوریتم پیشنهادی توزیع وظایف غیرتناوبی PAGEREF _Toc422763931 \h 80شکل 4-7 فلوچارت الگوریتم پیشنهادی توزیع وظایف غیرتناوبی PAGEREF _Toc422763932 \h 81center535460یازده
0یازده
شکل 4-8 نمودار زمانی اجرای یک وظیفه با الگوریتم تنظیم فرکانس پیشنهادی PAGEREF _Toc422763933 \h 84شکل 5-1 مقایسه انرژی مصرفی حالت‌های مختلف نسبت تفکیک هسته‌ها برای وظایف تناوبی و غیرتناوبی PAGEREF _Toc422763934 \h 93شکل 5-2 انرژی مصرفی الگوریتم پیشنهادی در شش مجموعه وظیفه مختلف PAGEREF _Toc422763935 \h 94شکل 5-3 مقایسه انرژی مصرفی الگوریتم پیشنهادی با الگوریتم‌های LU-McEP و PDAMS PAGEREF _Toc422763936 \h 95شکل 5-4 مقایسه انرژی مصرفی الگوریتم پیشنهادی با الگوریتم‌های LU-McEP و PDAMS در 6 مجموعه وظیفه مختلف PAGEREF _Toc422763937 \h 96شکل 5-5 مقایسه نرخ نقض سررسید وظایف در همه حالت‌های ممکن الگوریتم پیشنهادی PAGEREF _Toc422763938 \h 97شکل 5-6 مقایسه میزان نرخ نقض سررسید الگوریتم پیشنهادی با الگوریتم‌های LU-McEP و PDAMS PAGEREF _Toc422763939 \h 98شکل 5-7 مقایسه میزان نرخ نقض سررسید الگوریتم پیشنهادی ما با الگوریتم‌های LU-McEP و PDAMS را در تمام حالت‌ها PAGEREF _Toc422763940 \h 99شکل 5-8 مقایسه زمان پاسخ وظایف غیرتناوبی الگوریتم ما با الگوریتم‌های LU-McEP و PDAMS PAGEREF _Toc422763941 \h 100شکل 5-9 مقایسه متوسط زمان پاسخ وظایف غیرتناوبی الگوریتم ما با الگوریتم‌های LU-McEP و PDAMSدر همه حالت‌ها PAGEREF _Toc422763942 \h 101شکل 5-10 مقایسه متوسط زمان انتظار وظایف غیرتناوبی الگوریتم پیشنهادی ما نسبت به الگوریتم‌های LU-McEP و PDAMS PAGEREF _Toc422763943 \h 102
فهرست جدولها
TOC \h \z \c “جدول” جدول 2-1 خلاصه‌ای از مشخصه‌های یک سیستم تعبیه‌شده بی‌درنگ PAGEREF _Toc421408075 \h 10جدول 3-2 مشخصات وظایف تناوبی در مثال مربوطه در [37] PAGEREF _Toc421408076 \h 64جدول 3-3 مشخصات وظایف غیرتناوبی در مثال مربوطه در [37] PAGEREF _Toc421408077 \h 64جدول 4-1 فرکانسها و توان متناظر هر سطح فرکانسی PAGEREF _Toc421408078 \h 85جدول 4-2 مثال عددی از الگوریتم تنظیم فرکانس سررسیدمحور پیشنهادی PAGEREF _Toc421408079 \h 86جدول 5-1 مشخصات پردازنده چندهسته‌ای PowerPC 405PL شرکت IBM PAGEREF _Toc421408080 \h 89
23644141185614دوازده
0دوازده

چکيدهامروزه با پیشرفتهای چشمگیر در صنعت الکترونیک و نیاز روزافزون به تکنولوژیهای کنترلی، کاربرد و اهمیت سیستمهای تعبیه‌شده نیز بیشتر شده است تا جاییکه سیستمهای تعبیه‌شده از مهمترین زمینههای پژوهشی در سالهای اخیر محسوب میشوند. در اکثر مواقع، عملیات در یک سیستم تعبیه‌شده باید در زمان کوتاه و مناسبی اجرا شوند، از اینرو عموماً اکثر سیستمهای تعبیه‌شده، بیدرنگ میباشند. تجهیزات نظامی و صنعتی، تلفن همراه و کاربردهای تجاری همچون دستگاههای خودپرداز و سیستمهای هوشمند، نمونه‌هایی از سیستمهای تعبیه‌شده بیدرنگ میباشند. علاوه بر بیدرنگ بودن، مصرف انرژی مناسب نیز یکی دیگر از مشخصههای اصلی سیستمهای تعبیه‌شده میباشد که یک مسئله اساسی پیش روی طراحان سیستمهای دیجیتال محسوب میشود. یکی از مسائل مهم در سیستمهای چند هستهای زمانبندی وظیفهها و اجرای آنها توسط هستههای موجود است. برخلاف سیستمهای تک هستهای که مسئله زمانبندی فقط در مورد زمان میباشد، در سیستمهای چند هستهای این مسئله یک مسئله دو بعدی است و علاوه بر زمان ، مکان و فضای اجرای هستهها را هم شامل میشود، یعنی تصمیمگیری میشود که یک وظیفه چه زمانی و توسط کدام هسته اجرا شود و هدف آن استفاده بهینه از توان پردازشی موجود، افزایش بازده و حداقل کردن زمان پاسخ سیستم است. در این پایان نامه ما بروی چهار مشکل اصلی در این نوع سیستم ها تمرکز میکنیم: مصرف انرژی ، بهره‌وری سیستم، کارایی سیستم، زمان پاسخ سیستم. یکی از مهم ترین مسائلی که روی تمامی این چهار مشکل تاثیر مستقیم دارد نحوه توزیع بار بین منابع موجود است که در اینجا منظور از منابع، هستههای یک پردازنده چند هستهای میباشد. یک توزیع ناکارامد بار روی هستهها باعث مصرف انرژی بیشتر و پایین آمدن بهرهوری و کارایی کل سیستم میشود. بیشتر روشهایی که تاکنون ارائه شده‌اند، بدون توجه به نوع وظیفه، آنها را بین پردازندهها توزیع میکنند و بیشتر به تمرکز روی روشهای تنظیم فرکانس و ولتاژ هر هسته بسنده میکنند. الگوریتم پیشنهادی ما در این پروژه، یک الگوریتم سه سطحی میباشد که در سطح اول یک روش جدید برای تفکیک وظایف تناوبی از وظایف غیرتناوبی متناسب با تعداد هستههای موجود ارائه میشود. سطح دوم از دو قسمت تشکیل میشود. در قسمت اول یک الگوریتم جدید برای توزیع وظایف تناوبی بین هستههای مربوط به آن ها که در سطح اول الگوریتم مشخص شده، ارائه میشود و در قسمت دوم الگوریتم توزیع وظایف غیرتناوبی بین هستههای مشخص شده برای آن‌ها ، مطرح میشود. در سطح سوم الگوریتم جدیدی برای تنظیم فرکانس و ولتاژ سررسید محور بیان میکنیم. نتایج شبیهسازی نشان میدهد که الگوریتم پیشنهادی ما در مقایسه با الگوریتم‌های موجود، در حین اینکه باعث کاهش مصرف انرژی کل سیستم میشود، بهرهوری و کارایی سیستم و همچنین زمان پاسخ وظایف غیر تناوبی را بهبود بخشیده است و با توجه به تامین سررسیدهای زمانی بیشتر برای وظایف تناوبی وکاهش زمان پاسخ وظایف غیرتناوبی با حفظ میزان کارایی و پایین بودن نسبی مرتبه زمانی اجرای الگوریتم، کیفیت سیستم افزایش پیدا خواهد کرد.
کلمات کلیدی : زمان‌بندی، وظایف بی‌درنگ، پردازنده‌های چند هسته‌ای ، سیستمهای تعبیه‌شده
-287883-777827right101624
-335188-81249400
فصل اول
فصل اول :مقدمه1-1 پيشگفتار سیستم‌های تعبیه‌شده یکی از بخش‌های اصلی زندگی ما هستند و نقش مهمی در آسان نمودن زندگی مدرن ما ایفا می‌کنند. از تلفن‌های هوشمند که امکانات متنوعی را در اختیار کاربران قرار‌‌می‌دهند گرفته تا لوازم منزل، آسانسورها، ترمز در یک خودرو و سیستم های هدایت موشک همگی نمونه هایی از سیستم های تعبیه‌شده هستند.
امروزه بیش از 98 درصد تمام پردازنده‌های تولیدشده در جهان در سیستم‌های تعبیه‌شده استفاده شده ‌است. این پردازشگرهای تعبیه‌شده در نگاه اول کاربر، قابل مشاهده نیستند؛ در هرصورت عملکرد صحیح آنها برای درست کار کردن هرسیستمی ضروری است. در اکثر مواقع عملیات در یک سیستم تعبیه‌شده باید در زمان کوتاه و مناسبی اجرا شوند. از این رو اکثر سیستم‌های تعبیه‌شده، بی‌درنگ می‌باشند، بنابراین زمان پاسخ در سیستم های تعبیه‌شده بی‌درنگ از اهمیت بالایی برخوردار است. علاوه بر بی‌درنگ بودن و اهمیت زمان پاسخ، مصرف انرژی کم نیز یکی از مهم‌ترین ویژگی‌های یک سیستم تعبیه‌شده می باشد.از دیگر ویژگی‌های یک سیستم تعبیه‌شده می توان به تولید گرمای پایین و هزینه کم اشاره کرد. مبحث انرژی و توان مصرفی مانع از افزایش سرعت مخصوصا در سیستم‌های چندهسته‌ای می‌شود. سیستم‌های بی‌درنگ می توانند بهره خوبی از پردازنده‌های چندهسته‌ای ببرند، یعنی وظیفه‌های مستقل می‌توانند به طور همزمان اجرا شوند و خیلی سریع باهم بین هسته‌ها ارتباط برقرار کنند.
یکی از مسائل مهم در سیستم‌های چندهسته‌ای که تاثیر مستقیم روی مصرف انرژی، زمان پاسخ،کارایی و بهره‌وری سیستم دارد، زمان‌بندی وظیفه‌ها و اجرای آن‌ها توسط هسته‌های موجود است. بنابراین به زمان‌بندی‌هایی احتیاج داریم که بتوانند با یک توزیع بار مناسب بین هسته‌ها و روش مطلوب زمانبندی در هر کدام از هسته‌ها، به مصرف انرژی پایین، زمان پاسخ حداقل، بهره‌وری مناسب و کارایی بالا در یک سیستم بی‌درنگ تعبیه‌شده دست پیدا کنند.
1-2 توصيف مسئله
یکی از اساسی‌ترین مفاهیم در سیستم‌های تعبیه‌شده بی‌درنگ، زمانبندی، سیاست و نحوه توزیع وظایفی است که در سیستم وارد یا ایجاد می شوند. این مسئله باید باتوجه به نوع کاریرد یک سیستم تعبیه‌شده، حساسیت‌ها ومحدودیت‌ها، در مرحله طراحی سیاست‌گذاری شود. به طور کلی زمانبندی می‌بایست دارای خصوصیات اولیه‌ای باشد که این خصوصیات در جهت کاربرد سیستم نمایان می شوند. از آنجا که سیستم‌های بی‌درنگ سطح وسیعی از سیستم‌های موجود را شامل میشوند، نوع زمانبندی اجرای وظایف در آنها اهمیت زیادی دارد که محدودیت زمانی بین همه آنها مشترک است. در سیستم‌های چندهسته‌ای برخلاف سیستم‌های تک هسته‌ای که مسئله زمانبندی فقط در مورد زمان می‌باشد، این موضوع یک مسئله دوبعدی است و علاوه بر زمان، مکان و فضای اجرای وظایف در یکی از هسته ها را هم شامل می شود. یعنی تصمیم‌گیری می شود که یک وظیفه چه زمانی و توسط کدام هسته اجرا شود و هدف آن استفاده بهینه از توان پردازشی موجود، افزایش بازده و حداقل کردن زمان پاسخ سیستم است. در برخی سیستم‌ها هم بار کاری زیادی به سیستم وارد می شود، بنابراین باید جلوی مسئله اضافه بار را گرفت تا سیستم وظیفه‌هایی که در حال اجرا و در صف اجرا قرار دارد را به درستی و در زمان مقرر به اتمام برساند. اگر بار کاری زیاد از حد باشد ممکن است برخی سررسیدها از دست برود و درنتیجه کارایی یک سیستم بی‌درنگ زیر سوال برود. بنابراین یک توزیع مناسب وظایف بین هسته‌ها و زمانبندی کارامد می‌تواند این مشکل را کمتر کند. در برخی از کاربردها، زمان پاسخ سیستم از اهمیت بالایی برخوردار است وهر چه سریع‌تر تعداد وظایف بیشتری را انجام دهد، به رضایت بیشتر کاربر منجر می‌شود.
با فراگیر شدن سیستم‌های نهفته میزان مصرف انرژی سیستم نیز بشدت مورد توجه قرار گرفته است. وجود محدودیت در انرژی باطری در سیستم‌های نهفته قابل حمل، جلوی افزایش سرعت پردازنده‌ها را گرفته است، بنابراین وجود راهکاری در این گونه سیستم‌ها که بتواند مصرف انرژی را همزمان با افزایش بهره وری و کارایی بهبود دهد، می‌تواند پیشرفت بزرگی محسوب شود.
در این تحقیق ما روشی را برای توزیع بار بین هسته‌ها و زمانبندی وظایف درهریک از هسته‌ها ارائه می دهیم تا بتوانیم پارامترهای مهم انرژی مصرفی، زمان پاسخ، کارایی سیستم و بهره وری آن را بهبود ببخشیم. راهکاری که ما ارائه داده‌ایم در واقع به نوع ماهیت یک وظیفه اهمیت می دهد و براساس تناوبی یا غیرتناوبی بودن آن، شالوده و اهداف الگوریتم پیشنهادی شکل می گیرد. این تفکیک وظایف به خاطر ماهیت هر کدام از این نوع وظایف است، دغدغه ما در این پژوهش این است که بتوانیم یک نوع تعادل بین انرژی مصرفی و کارایی سیستم برقرار کنیم. یعنی با ارائه یک زمانبندی برای وظایف سیستم، آن‌ها را طوری بین هسته‌ها توزیع کنیم که حداقل انرژی مصرفی و همزمان با آن بهترین کارایی برای سیستم را به دنبال داشته باشد.
1-3 ساختار پايان نامه در فصل اول به صورت مختصر به اهمیت، دغدغه‌ها و کاربردهای مختلف سیستم‌های تعبیه‌شده و مشخصه‌های کاربردی آن پرداخته می‌شود و پس از آن به سراغ توصیف مسئله رفته واهمیت آن را بیان می‌کنیم. در پایان نیز خلاصه‌ای از ساختار بخش‌ها و فصل‌های مختلف پایان‌نامه را شرح می‌دهیم.
در فصل دوم، مفاهیم و تعاریف اولیه که برای درک مسئله اهمیت دارد را به تفصیل شرح داده و بررسی می‌کنیم. ابتدا سیستم‌های تعبیه‌شده را تعریف کرده و مهم‌ترین خواص این سیستم‌ها را به طور کامل شرح می‌دهیم. سپس به بیان اهمیت مصرف انرژی در سیستم‌های تعبیه‌شده می‌پردازیم و بیان خواهیم کرد که چطور یک توزیع مناسب وظایف بین هسته‌های یک پردازنده چندهسته‌ای، می‌تواند باعث کاهش انرژی مصرفی در سیستم مخصوصا سیستم‌هایی که دارای محدودیت منبع تامین‌کننده انرژی هستند، شود. سپس سیستم‌های بی‌درنگ را توضیح داده و انواع سیستم‌های بی‌درنگ از نظر محدودیت زمانی را بیان می‌کنیم. سپس تابع سودمندی در یک سیستم بی‌درنگ را با توجه به نوع ماهیت وظایف بیان کرده و رسم می‌کنیم. سپس به تعریف یک وظیفه پرداخته و حالت‌های مختلفی که یک وظیفه می‌تواند در طول حیاتش در سیستم تجربه کند را با رسم شکل بیان می‌کنیم. پس از آن وظیفه بی‌درنگ و مشخصه‌های مهم آن را بیان می‌کنیم و انواع وظایف بی‌درنگ را بر اساس فرکانس آزاد شدنشان شرح می‌دهیم. سپس به تعریف سررسید یک وظیفه پرداخته و انواع آن را بر اساس وابستگی آن به زمان آزاد شدن و همچنین وابستگی آن به دوره تناوب وظیفه شرح می‌دهیم. پس از تعریف هسته‌ پردازنده در یک سیستم چندهسته‌ای و منابع در یک سیستم تعبیه‌شده، به بررسی مفاهیم زمانبندی و اصطلاحات مختلف در زمانبندی یک سیستم می‌پردازیم و در نهایت سیستم‌های چندهسته‌ای را تعریف کرده و ویژگی‌ها و عملکرد آن‌ها را شرح می‌دهیم.
در فصل سوم ابتدا به طبقه‌بندی انواع روش‌های زمانبندی تک‌هسته‌ای می‌پردازیم و سپس چندتا از الگوریتم‌های معروف زمانبندی تک هسته‌ای را شرح می‌دهیم. سپس انواع معماری سیستم‌های چندهسته‌ای را تشریح می‌کنیم و پس از آن به توصیف طبقه‌بندی انواع روش‌های زمانبندی چندهسته‌ای و مزایا و معایب هرکدام خواهیم پرداخت. سپس روش‌های زمانبندی مبتنی بر تنظیم فرکانس و ولتاژ را بیان می‌کنیم و در نهایت به شرح کامل الگوریتم‌های زمانبندی چندهسته‌ای ارائه شده در مقاله‌های مرتبط گذشته می‌پردازیم و مزایا و معایب آن‌ها را تحلیل می‌کنیم.
در فصل چهارم الگوریتمی برای توزیع و زمانبندی وظایف در یک سیستم چندهسته‌ای پیشنهاد خواهد شد. این الگوریتم شامل سه سطح است، سطح اول تفکیک وظایف و هسته‌های متناسب با آن‌ها، سطح دوم الگوریتمی برای توزیع واختصاص وظایف بین هسته‌ها و سطح سوم، یک الگوریتم انرژی- سررسید محور، برای تنظیم فرکانس هسته‌ها متناسب با سررسید و زمان اجرای وظایف می‌باشد. در این فصل ابتدا جایگاه الگوریتم پیشنهادی خود را در بین طبقه‌بندی انواع الگوریتم‌های زمانبندی چندهسته‌ای مشخص می‌کنیم و سپس ساختار کلی زمانبندی پیشنهادی خود را با رسم شکل دقیق آن بیان می‌کنیم. سپس به بیان کلیات الگوریتم پیشنهادی خود پرداخته و مدل وظیفه و تمامی مشخصه‌های آن در الگوریتم خود را تشریح می‌کنیم. سپس مدل سیستم پیشنهادی خود را بیان می‌کنیم و بعداز آن به شرح کامل همراه با جزئیات الگوریتم پیشنهادی خود می‌پردازیم.
در فصل پنجم نحوه شبیه سازی، محیط آن و شرایط سیستم شرح داده خواهد شد و نتایج آزمایش و مقایسه با دیگر روش‌ها بیان خواهد شد. ابتدا به بیان تنظیمات اولیه شبیه‌سازی خواهیم پرداخت و سپس محیط شبیه‌سازی و زبان برنامه نویسی مورد استفاده برای شبیه‌سازی را بیان خواهیم کرد. سپس به ارزیابی مصرف انرژی، میزان نقض سررسید، متوسط زمان پاسخ وظایف غیرتناوبی و متوسط زمان انتظار آن‌ها در الگوریتم پیشنهادی در مقایسه با دیگر الگوریتم‌ها با نشان دادن نمودار خواهیم پرداخت.
در فصل ششم به بیان نتیجه‌گیری نهایی این پژوهش پرداخته خواهد شد و پیشنهاداتی برای کارهای آینده ارائه می‌شود.
-165136-698739
-286542-82702700
-296545-530860
فصل دوم
فصل دوم :مفاهيم اوليهامروزه سیستم‌های تعبیه‌شده، به صورت وسیعی درحال استفاده در زندگی روزمره ما هستند و در وسایل دیجیتالی، دستگاه‌های قابل حمل و محصولات ارتباطی مختلف کاربرد دارند. در این فصل ابتدا سیستم‌های تعبیه‌شده را تعریف کرده و مهم‌ترین خواص این سیستم‌ها را به طور کامل شرح می‌دهیم، سپس سیستم‌های بی‌درنگ را توضیح داده و انواع سیستم‌های بی‌درنگ از نظر محدودیت زمانی را بیان می‌کنیم. سپس تابع بهره‌وری را متناسب با نوع وظیفه شرح می‌دهیم و بعداز آن وظیفه، سررسید، هسته پردازنده ، منابع و زمانبند را تعریف کرده و به بررسی مفاهیم زمانبندی می‌پردازیم و در نهایت سیستم‌های چندهسته‌ای را تعریف کرده و عملکرد آن‌ها را شرح می‌دهیم.
2-1 سيستم های تعبيه‌شدهیک سیستم تعبیه‌شده، یک سیستم پردازش اطلاعات مبتنی یر پردازنده می‌باشد که برای انجام محاسبات خاص در درون یک سیستم بزرگتر که خود شامل اجزای الکترونیکی یا مکانیکی است، جاسازی شده است و وظیفه کنترل عملکرد و پردازش درست سیستم را برعهده دارد]1[ . با توجه به پیشرفت صنعت نیمه‌هادی و ارزان شدن محصولات نیمه‌هادی، چند سالی است که سیستم‌های تعبیه‌شده جای خود را در زندگی روزمره انسان‌ها باز کرده‌اند و به عنوان یک کالای عادی به فراوانی مورد استفاده قرار می‌گیرند. گوشی‌های تلفن‌همراه، ادوات صوتی و تصویری، لوازم خانگی و… نمونه‌های کوچکی از نفوذ این صنعت در زندگی انسان‌ها هستند. با توجه به تقاضای روزافزون برای این تجهیزات و نیز قیمت رو به کاهش آنها در سال‌های آینده نیز این روند به شدت رشد خواهد‌کرد. بر‌خلاف رایانه‌های همه‌منظوره، مانند رایانه‌های رومیزی که برای رفع نیاز‌های عمومی طراحی شده‌اند، سیستم‌های تعبیه‌شده به‌گونه‌ای طراحی می‌شوند که برای یک کاربرد خاص با کمترین هزینه، بهترین کارایی را از خود نشان دهند. سیستم‌های تعبیه‌شده دارای هسته‌های پردازشی هستند که می‌توانند ریزکنترل‌کننده، ریزپردازنده و یا پردازنده سیگنال‌های دیجیتال (DSP) باشند.مشخصه کلیدی این سیستم‌ها طراحی اختصاصی برای انجام یک کار مشخص است، به همین دلیل مهندسین طراح می‌توانند محصول را برای کاهش اندازه و قیمت و مصرف انرژی بهینه کرده و اطمینان‌پذیری و کارایی آن را بالا ببرند.
برخی از مهمترین خواص سیستم‌های تعبیه‌شده به شرح زیر می‌باشد:
معمولاً برای یک کاربرد خاص طراحی و تولید می‌شوند.
عموماً ابزار‌هایی هستند که به‌صورت قابل حمل استفاده شده ودر نتیجه باید مصرف توان کمی داشته باشند.
معمولاً سطح کارایی بسیار بالایی ندارند ولی باید نیاز کاربرد مورد نظر خود را برآورده سازند.
معمولاً نیازمندی‌های بی‌درنگ در آنها مطرح است.
بیشتر واسط‌های کاربری خاصی لازم دارند.
معمولاً از طریق حسگر‌ها و فعال‌کننده‌های متعددی با محیط اطراف تعامل زیادی دارند.
عموماً به‌صورت سیستم‌های ترکیبی آنالوگ و دیجیتال ساخته می‌شوند.
باتوجه به فراوانی سیستمهای تعبیه‌شده در زندگی بشر طراحان باید بتوانند سیستمهای تعبیه‌شده‌ای با حداقل قیمت و بالاترین کارایی طراحی کنند. بنابراین منابع موجود برای طراحان محدود است.
پیش‌بینی رفتار این سیستم‌ها بسیار مهم است. این بدین معنی است که رفتار این سیستمها، تحت هر شرایطی باید قابل پیشبینی باشد. این سیستمها شامل سخت‌افزاری هستند که تضمین میکند هر زیربرنامه‌ای که روی آنها اجرا می‌شود، در هر زمان اجرا، سربار اجرای یکسانی داشته باشد. علاوه بر این نرم‌افزارهای موجود با در نظر‌گرفتن بدترین شرایط ممکن طراحی می‌شوند و به این طریق است که سربار زمانی سیستم را می‌توان بصورت قطعی درنظر گرفت.
قابلیت اعتماد : قابلیت اعتماد به عنوان یک توانایی در یک سیستم برای ارائه یک سرویسی که می‌توان به نحو موجهی به آن اعتماد کرد، تعریف شده است. همچنین قابلیت اعتماد، توانایی یک سیستم برای جلوگیری از شکستی است که بسیار شدیدتر از چیزی باشد که برای کاربران قابل قبول باشد. در واقع سیستم باید در سطح قابل قبولی از اعتماد‌پذیری قرار داشته باشد. تجهیزات انرژی هسته‌ای یک نمونه از سیستم‌های به شدت بحرانی امن هستند که بخش‌های بحرانی آن باید بطور کامل توسط نرم افزار کنترل شوند. راه اصلی برای رسیدن به قابلیت اعتماد، اجتناب از خطاهای مربوطه است، راه‌هایی مانند: پیشگیری خطا، تحمل خطا، حذف خطا و پیشبینی خطا که توسط ویژگی‌های زیر مشخص می‌شود]2[ :
قابلیت اطمینان
دردسترس‌بودن
بی‌عیبی
ایمنی
محرمانگی
نگهداشت‌پذیری
2-1-1 مصرف انرژی در سيستم‌های تعبيه‌شدهبا نگاهی به تاریخچه تکنولوژی، می‌بینیم که بهره‌وری پردازنده‌ها در هر نسل جدید، با افزایش نرخ ساعت بهبود پیدا کرده است اما افزایش انرژی مصرفی و تراکم حرارتی مانع از این قضیه شده و سبب شده که نرخ ساعت پردازنده‌ها تقریبا از حرکت بایستد. همواره یک تقاضای همیشگی برای بهره‌وری محاسباتی بیشتر، در عین حال مصرف انرژی کمتر، در پردازنده‌های مدرن امروزی وجود دارد. بهتر شدن در عملکرد و توان، نتنها به برنامه‌های کاربردی اجازه می‌دهد که سریع‌تر اجرا شوند، در عین حال که انرژی کمتری را مصرف می‌کنند، بلکه آن‌ها را قادر می‌سازند که برنامه‌های کاربردی جدیدی را که قبلا به هیچ عنوان درنظر گرفته نمی‌شدند را هم پوشش دهند. به عنوان مثال انجام بازی‌های سه‌بعدی، داشتن یک مرورگر وب در حد اندازه‌های مرورگرهای رایانه‌های رومیزی و ضبط ویدئوهایی با کیفیت فوق العاده بالا تا ده سال پیش بروی تلفن‌های همراه امکان‌پذیر نبود ]3[ .
افزایش کاربرد پردازنده‌های تعبیه‌شده در سیستم‌های سیار و قابل‌حمل مانند تلفن‌های همراه باعث شده‌است مصرف انرژی به عنوان یکی از مهمترین محدودیت‌های طراحی سیستم‌های تعبیه‌شده مطرح شود. بسیاری از این سیستم‌ها انرژی موردنیاز خود را از طریق باطری تامین می‌کنند. به‌علاوه در بسیاری از موارد تعویض و یا شارژ باطری در محیط عملیاتی سیستم‌های تعبیه‌شده با دشواری همراه است. در این گونه سیستم‌ها استفاده از روش‌های کاهش مصرف انرژی برای بالا بردن طول عمر باطری ضروری است ]4[ . یک حقیقت مهم در اینجا این است که پیشرفت در تکنولوژی باطری‌ها بسیار آهسته‌تر از پیشرفت در سرعت انجام محاسبات و پردازش و در نتیجه آن، مصرف انرژی بیشتر در پردازنده‌ها بوده‌است .با توجه به این دلایل و برای بهبود کارایی سیستم‌های تعبیه‌شده مدرن، سیستم احتیاج دارد تا توان محاسباتی بیشتری را فراهم کند و در عین حال که کارایی حفظ شده، توان مصرفی را هم کاهش بدهد. یکی از راه‌های ممکن برای کاهش مصرف انرژی و در عین حال افزایش بهروری، اختصاص دادن موثر وظایف بین هسته‌های پردازنده می‌باشد، که در این پژوهش، یکی از مهم‌ترین دغدغه‌های ما می‌باشد.
2-2 سيستم های تعبيه‌شده بی‌درنگامروزه بیشتر سیستم‌های تعبیه‌شده دارای ویژگی‌ بی‌درنگ بودن هستند.در این گونه سیستم‌ها وظیفه‌های مربوط به درخواست‌ها باید در کمتر از زمان مشخص‌شده اجرا شوند. یک سیستم بی‌درنگ را می‌توان به این صورت تعریف کرد : ” به سیستمی بی‌درنگ گفته می‌شود که صحت درستی یک فرایند تنها وابسته به صحت منطقی آن نباشد، بلکه به زمانی که در آن اجرا می‌شود نیز وابسته باشد.”
از جمله کاربرد‌های این نوع سیستم‌ها می‌توان به سیستم‌های حساس پزشکی، سیستم‌های نظامی، کنترل سیستم‌های نیروگاه هسته‌ای،سیستم فرمان و کنترل، پردازش سیگنال، سیستم ارتباطات راه دور، سیستم‌های کنترل دیجیتال، پردازش پروتکل‌های شبکه و … اشاره کرد. سیستم ضدقفل در ترمز ماشین یکی دیگر از نمونه های ساده‌ای از سیستم‌های بی‌درنگ است که محدودیت زمانی در این سیستم زمان کوتاهی است که باید ترمز گرفته‌شود تا از قفل‌شدن چرخ‌ها جلوگیری شود. محاسبات بی‌درنگ اگر قبل از محدودیت زمانی، جایی که این محدودیت مربوط به یک رویداد است، کامل نشده‌باشد، با شکست مواجه می‌شود. در این گونه سیستم‌ها باید پاسخ درخواست‌ها حتما در زمان مشخصی ارسال گردد و در غیر‌این صورت سیستم دچار اختلال شده و حتی در کاربردهای حساس می‌تواند منجر به یک فاجعه گردد. از این‌رو نوع پیاده‌سازی، کنترل زمان پاسخ‌گویی، سربار و نحوه الگوریتم‌های پیاده‌سازی شده و همچنین بستر سیستم‌عامل و سخت‌افزار حائز اهمیت فراوانی است. به طور کلی سیستم‌های بی‌درنگ و سیستم‌های توزیع زمانی دو پیاده‌سازی کاملا متفاوت داشته و در نوع عملکرد کاملا متفاوت عمل می‌کنند، زیرا به علت ماهیت پاسخ‌دهی بی‌درنگ، حافظه اشتراکی و اشتراک زمانی عملا کاربرد نخواهد داشت. به همین دلیل است که در سیستم‌های بی‌درنگ معمولا اثری از سیستم‌عامل‌های نسل جدید و مدرن به چشم نمی‌خورد و در اکثر آن‌ها از رسانه‌های ذخیره‌سازی مانند دیسک سخت نیز خبری نیست. در واقع سیستم‌های بی‌درنگ پاسخی برای یک سری از ورودی‌های خارجی هستند که به‌صورت غیرقابل پیشبینی وارد سیستم می‌شوند، سپس این ورودی‌ها به‌وسیله سیستم بی‌درنگ پردازش شده و تصمیمات مناسب در زمان مناسب اتخاذ می‌شوند. همچنین خروجی لازم برای کنترل دستگاه‌های جانبی متصل به آنها نیز تولید می‌شود و در صورتی که سرویس‌ها و منابع خواسته شده توسط وظیفه، قبل از اتمام آن، در اختیارش قرار‌نگیرد و وظیفه نتواند در زمان مناسب و تعیین‌شده خاتمه یابد، وظیفه مورد‌نظر از اعتبار ساقط می‌شود. در پردازش‌های بی‌درنگ، هر وظیفه یک سررسید دارد که این بدین معنی است که برای اینکه سیستم به درستی کار کند می‌بایست اجرای هر وظیفه تا قبل از فرارسیدن سررسید مربوطه‌اش به اتمام برسد. بر همین اساس تقسیم‌بندی سیستم‌های بی‌درنگ انجام می‌شود. در جدول 2-1 خلاصه‌ای از مشخصه‌های مختلف یک سیستم تعبیه‌شده بی‌درنگ و زیرمشخصه‌های آن را مشاهده می‌کنید.
جدول SEQ جدول \* ARABIC 1جدول 2-1 خلاصه‌ای از مشخصه‌های یک سیستم تعبیه‌شده بی‌درنگجدول 2-1 خلاصه‌ای از مشخصه‌های یک سیستم تعبیه‌شده بی‌درنگ
مشخصه‌ها زیرمشخصه‌ها
خواص بی‌درنگ بودن زمان پاسخ یا تاخیر
زمان اجرای وظیفه
بدترین حالت زمان اجرا
سررسید
قابلیت اعتماد قابلیت اطمینان
در دسترس‌بودن
بی‌عیبی
محرمانگی
ایمنی
منابع مصرفی توان مصرفی
توان محاسباتی
حافظه مصرفی
زمان اجرای پردازنده
مشخصه طول عمر نگهداشت‌پذیری
2-2-1 انواع سيستم های بی‌درنگ از نظر محدوديت زمانیسیستم‌های بی‌درنگ از نظر محدودیت زمانی به سه دسته تقسیم می‌شوند:
سیستم‌های بی‌درنگ سخت
سیستم‌های بی‌درنگ نرم
سیستم های بی‌درنگ ثابت
در سیستم‌های بی‌درنگ سخت، کار انجام شده توسط سیستم، بایستی دقیقا به موقع انجام شود و هیچ گونه تاخیری قابل قبول نیست در غیر این صورت سبب ناتوانی سیستم می‌شود. در سیستم‌های تعبیه‌شده، سیستم بی‌درنگ سخت در سطح پایینی از سخت افزار فیزیکی عمل می کند. برای مثال سیستم کنترل موتور ماشین یک سیستم بی‌درنگ سخت است چون ممکن است سیگنال های تاخیر به موتور آسیب برسانند. مثال دیگر از سیستم بی‌درنگ سخت، سیستم‌های تعبیه‌شده در دستگاه‌های پزشکی مثل دستگاه تنظیم کننده ضربان قلب وپردازشگر های کنترل صنعتی می‌باشد. سیستم بی‌درنگ سخت برای رویدادهایی که به محدودیت زمانی واکنش نشان می دهند، ضروری اند، به عبارتی، تعریف مهلت زمانی سخت لزوماَ این نیست که این زمان غیر قابل از دست دادن باشد، بلکه مهلت زمانی سخت به سادگی تعیین می‌کند که یک عمل اگر مهلت زمانی‌اش از دست برود بی‌فایده است. معمولاً ضمانت‌های معتبر مهلت‌های زمانی، برای سیستم‌هایی موردنیاز هستند که در فاصله‌های زمانی از خود واکنش نشان نمی‌دهند و باعث خسارت‌های بزرگی می‌شوند]5[ .
در سیستم‌های بی‌درنگ نرم، ضرورتی در بررسی تمامی محدودیت‌های زمانی سیستم نیست و در صورت تاخیر در اجرای وظیفه، سیستم دچار بحران و یا وقوع فاجعه نمی‌شود. یعنی هرچند این سیستم‌ها می‌بایست پاسخی سریع داشته باشند ولی مسئله پاسخ‌دهی، به حادی سیستم‌های بی‌درنگ سخت نیست. سیستم‌های بی‌درنگ نرم در دستیابی‌های همزمان استفاده می‌شوند و قابلیت پاسخ‌گویی به چند واقعه را دارا بوده و همچنین قابلیت تقسیم‌بندی پدیده‌ها به بحرانی و غیربحرانی را دارا می‌باشند. در این‌گونه سیستم‌ها، اولویت اجرا همیشه با پدیده‌های بحرانی می‌باشد. یکی از معایب این سیستم‌ها این است که وظایف غیربحرانی تا زمانی که وظایف بحرانی پاسخ داده‌نشوند، بی‌پاسخ می‌مانند و این موضوع ممکن است سیستم را دچار تاخیر در پاسخ‌گویی نماید. در سیستم‌های بی‌درنگ نرم، خطاهای ناشی از عدم اهمیت جدی به محدودیت زمانی، کیفیت را کاهش می‌دهد اما سیستم همچنان به کار خود ادامه می‌دهد. به عنوان نمونه‌هایی از سیستم‌های بی‌درنگ نرم می‌توان به سیستم‌های پخش صوتی و تصویری (چندرسانه‌ای)، واقعیت مجازی، رزرواسیون شرکت های هواپیمایی و… اشاره کرد]6[ .
در سومین نوع از سیستم‌های بی‌درنگ، به سیستم‌های بی‌درنگ ثابت می‌رسیم که در این نوع سیستم‌های بی‌درنگ که معمولا در تقسیم‌بندی‌ها به‌عنوان یک نوع مجزا، محسوب نمی‌شوند، سررسیدها هم به صورت سخت و هم به صورت نرم هستند، یعنی اجرا نشدن وظیفه تا سررسید خود، آن را بی فایده می‌کند(همانند سیستم‌های بی‌درنگ سخت)، در عین حال گاهی می‌تواند اجرا نشود(همانند سیستم‌های بی‌درنگ نرم). در واقع این سیستم‌ها سررسیدهای سختی دارند اما در جایی‌که یک احتمال کم و مشخص از خطا و نقض سررسید وجود دارد، سیستم می‌تواند این خطا را تحمل کند]5[ .
2-2-2 تابع بهره‌وری در سيستم‌های بی‌درنگمسئله به‌هنگام‌بودن، یکی از کلیدی‌ترین اصل در طراحی سیستم‌های بی‌درنگ می‌باشد. مسئله به‌هنگام‌بودن، دو جنبه کمی دارد؛ یکی اینکه سیستم باید در زمان مشخص و تعیین‌شده، وظیفه موردنظر را اجرا کند و دیگری اینکه باید علاوه‌ بر به‌موقع بودن، درستی و مفید بودن اجرا را نیز درنظر بگیرد. یعنی باید رابطه بین زمانی که نتایج تولید می‌شوند و مفید بودن این نتایج تولید‌شده را نیز درنظر گرفت. این رابطه می‌تواند بوسیله توابع ریاضی نشان داده‌شود.
بهره‌وری یک وظیفه معمولی ( غیربی‌درنگ ) کاملا مستقل از زمان است. نمودار تابع بهره‌وری نسبت به زمان در یک سیستم با وظیفه غیربی‌درنگ را در شکل 2-1- الف مشاهده می‌کنید. بهره‌وری یک وظیفه بی‌درنگ نرم تابعی است که بعد از فرارسیدن سررسید مربوطه، به تدریج کاهش یافته تا به صفر می‌رسد.(شکل 2-1- ب) نمونه‌هایی از وظایف بی‌درنگ نرم می‌توان به VOIP ، تلویزیون دیجیتال، کنفرانس ویدئویی و بسیاری از سیستم‌های چندرسانه‌ای دیگر اشاره کرد. اما در مورد یک وظیفه بی‌درنگ سخت، دو مورد باید قابل تشخیص باشد؛ اولین مورد که معمول‌تر است، این است که با فرارسیدن سررسید مربوطه، تابع بهره‌وری بلافاصله مستقیم به صفر سقوط کند. (شکل 2-1- ج) و مورد دوم که بسیار بدتر از حالت اول است این است که تابع بهره‌وری بعداز فرارسیدن سررسید، به منفی بی‌نهایت (∞-) سقوط کند (شکل 2-1- د ). از نمونه‌های این حالت می‌توان به سیستم‌های نظامی اشاره کرد که در آن عواقب یک عملی که درست و بموقع انجام نشود، می‌تواند حتی بدتر از انجام ندادن آن عمل باشد]5[ .
center2997939شکل 2-1- تابع بهره‌وری u(t) برای انواع مختلف وظایف بی‌درنگ ]5[
شکل SEQ شکل \* ARABIC 1–2-1- تابع بهره‌وری u(t) برای انواع مختلف وظایف بی‌درنگ0شکل 2-1- تابع بهره‌وری u(t) برای انواع مختلف وظایف بی‌درنگ ]5[
شکل SEQ شکل \* ARABIC 1–2-1- تابع بهره‌وری u(t) برای انواع مختلف وظایف بی‌درنگ
2-3 وظيفهکنترل نرم‌افزاری سخت‌افزار یک سیستم بی‌درنگ، نقش مهمی در بهبود عملکرد سیستم دارد. به عنوان مثال در یک ماشین‌لباس‌شویی، کنترل قسمت‌های مکانیکی و نمایش زمان باقی‌مانده برنامه شستشو و… نمونه‌ کارهایی هستند که توسط یک سیستم تعبیه‌شده موجود در لباس‌شویی اجرا می‌شوند. به منظور فشرده سازی کارهای مختلف و بهبود قابلیت استفاده مجدد و نگهداشت‌پذیری، کارها از زیربخش‌هایی تشکیل شده‌اند که به هر کدام از این زیربخش‌ها، وظیفه گفته‌می‌شود.
به عبارت دیگر “یک وظیفه ، یک موجودیت نرم‌افزاری یا یک برنامه از قبل تعیین‌شده برای پردازش برخی ورودی‌های خاص یا برای پاسخ به رفتاری خاص است که توسط رخدادی به آن منتقل می‌شود” ]7[ .
معمولا یک وظیفه دنباله‌ای از دستورات است که شامل اجراها و تعاملات منابع می‌شود. یک دستور اجرایی شامل یک دنباله‌ دلخواهی از دستورالعمل‌هاست که هر دستور باید بخشی از مجموعه دستورالعمل پردازنده باشد که می‌تواند انحصاری یا غیرانحصاری باشد. وظایف یا به صورت تناوبی و یا به صورت پراکنده و غیرتناوبی اتفاق می‌افتند. وظایف تناوبی در یک دوره ثابت زمانی تکرار می‌شوند مانند تقسیم عددی بر مضرب وقفه ساعت. این درحالی است که وظایف غیرتناوبی در زمان‌های تصادفی رخ‌ می‌دهند. مانند یک وقفه از یک حسگر خارجی. وظایفی که به صورت پراکنده اتفاق می‌افتند، وظایف غیرتناوبی نامیده می‌شوند، به شرطی که این وظایف به جای داشتن یک سررسید سخت، یک سررسید نرم داشته یا بدون سررسید باشند.
یک وظیفه می‌تواند دریکی از شش وضعیت غیرموجود، ایجاد‌شده ، آماده ، در حال اجرا، مسدود و یا خاتمه‌یافته قرار داشته‌باشد. نحوه گذار از یک حالت به حالت دیگر با استفاده از نمودار انتقال حالت در شکل2-2 نشان داده شده‌است. در این نمودار یک گذار معتبر و معمول با فلش ممتد مشخص شده است و یک فلش غیرممتد نشان‌دهنده یک گذار در صورت هرگونه استثناء است]8[ .
center2869321شکل 2-2- نمودار گذار حالت یک وظیفه ]8[
شکل SEQ شکل \* ARABIC 22-2- نمودار گذار حالت یک وظیفه0شکل 2-2- نمودار گذار حالت یک وظیفه ]8[
شکل SEQ شکل \* ARABIC 22-2- نمودار گذار حالت یک وظیفه
2-3-1 مدل وظيفه بی‌درنگیک سیستم بی‌درنگ می‌تواند شامل n وظیفه τi باشد و مجموعه وظایف آن را S می‌نامیم که عبارت‌اند از مجموعه همه وظایف موجود در سیستم که S={ τ1 ,τ2 ,τ3 ,…, τn } . هر وظیفه تعدادی مشخصه قراردادی دارد که توسط این مشخصه‌ها به سیستم‌عامل و برنامه‌نویس معرفی می‌شود.
چهار مشخصه مهم و اصلی یک وظیفه عبارت‌اند از:
Ci : بدترین حالت زمان اجرای وظیفه
Di : سررسید وظیفه
Ti : دوره تناوب وظایف تناوبی
Pi : اولویت وظایف غیرتناوبی
همچنین زمان آزاد‌شدن یک وظیفه با علامت ri نشان داده‌ می‌شود و عبارت‌انداز زمانی که وظیفه جدید از وضعیت ایجادشدن و یا از حالت مسدود خارج شده و وارد صف آماده می‌شود. وظایف تناوبی بر اساس زمان رسیدن خود شامل دو نوع هستند. یک سری وظایفی که اصطلاحاً همگام نامیده می‌شوند که به این معنی است که همه وظایف دارای زمان ورود یکسان هستند. دسته دیگر از وظایف تناوبی که ناهمگام نامیده می‌شوند، وظایفی هستند که زمان ورود مختلفی دارند و هیچکدام از وظایف آن دارای زمان ورود مشابهی نیستند]8[ .
2-3-2 دسته‌بندی وظايف بی‌درنگهمه وظایف بی‌درنگ بر اساس فرکانس آزاد‌شدن آنها به سه دسته مختلف تناوبی، غیرتناوبی و پراکنده تقسیم‌بندی می‌شوند که بصورت زیر تعریف می‌شوند ]9[ .
وظايف تناوبی:
یک وظیفه τi ،تناوبی نامیده می‌شود، هرگاه به‌صورت پیوسته و با یک نرخ ثابت تکرار شود، که این نرخ ثابت دوره تناوب ( Ti ) نامیده می‌شود، به طوری که فاصله بین آزاد شدن دو وظیفه همواره برابر است با ri j+1 – ri j = Ti
وظايف پراکنده :
برخلاف وظایف تناوبی، وظایف پراکنده که گاهی اوقات وظایف رویداد‌ محور و یا واکنش‌پذیر نیز نامیده می‌شوند، وظایفی هستند که در پاسخ به یک رویداد خارجی اجرا می‌شوند. در این حالت دوره تناوب وظایف پراکنده، حداقل زمان بین وقوع رویدادهایی که باعث آزادشدن وظیفه متناظر می‌شود را تعیین می‌کند. بنابراین فاصله بین آزادشدن هر دو وظیفه، نتیجه برآورده شدن شرط ri j+1 – ri j ≥ Ti است. از این رو یک وظیفه تناوبی در واقع یک حالت خاص از یک وظیفه پراکنده است.
وظايف غيرتناوبی:
در هر یک از دو حالت فوق ممکن است این نکته بیان شود که هردو حالت هیچ ارزش خاصی برای اجراشدن وظایف بلافاصله بعداز آزاد شدن آن‌ها و البته قبل از سررسیدشان قائل نشده‌اند. اما این نکته در وظایف غیرتناوبی صدق نمی‌کند. همان‌طور که از نام آن پیداست، وظایف غیرتناوبی فاقد مفاهیم تناوب (و گاهی سررسید) هستند، بنابراین این نوع وظایف می‌توانند در هر لحظه دلخواه وارد شوند. معمولا این نوع از وظایف برای رویدادهای بی‌درنگ نرم کاربرد دارند که معنای آن کمی متفاوت است؛ هدف آن‌ها این است که در کوتاه‌ترین زمان ممکن به درخواست‌های رویدادهای خارجی پاسخ داده‌شود، در عین حال که قابلیت حضور وظایف تناوبی و پراکنده را در سیستم دارد.
2-4 سررسيد یک محیط بی‌درنگ احتیاجات زمانی سختی را تحمیل میکند که وظیفه را مجبور به اجرا‌شدن به موقع و با موفقیت می‌کند. این احتیاجات از طریق اختصاص یک سررسید به هر وظیفه تعریف می‌شود. سررسید یکی از مهم‌ترین مشخصه‌های یک وظیفه بی‌درنگ است. سررسید Di از یک وظیفه τi ، زمانی را مشخص می‌کند که وظیفه باید تا آن لحظه اجرایش به پایان برسد. بنابراین Di سررسید یک وظیفه است که رفتار بی‌درنگ آن وظیفه را معین می‌کند.سررسیدها از دو نوع هستند:
سررسيد متناظر :
سررسید متناظر یک وظیفه به عبارتی بیشترین تاخیر قابل قبول برای پردازش و اجرای یک وظیفه است، یعنی مدت زمانی که یک وظیفه پس از شروع اجرای آن فرصت دارد تا اجرا شود.
سررسيد مطلق :
سررسید مطلق یک وظیفه لحظه‌ای است که وظیفه باید تا آن زمان اجرایش تمام شود. سررسید مطلق را با di نشان می‌دهیم و به صورت di =ri+Di تعریف می‌شود که در آن ri زمان آزاد‌شدن وظیفه و Di سررسید متناظر آن وظیفه می‌باشد.
مقایسه سررسید مطلق با سررسید متناظر را در شکل 2-3 مشاهده می‌کنید ]10[ .

شکل 2-3 سررسید متناظر و سررسید مطلق یک وظیفه ]10[
شکل SEQ شکل \* ARABIC 3شکل 2-3 سررسید متناظر و سررسید مطلق یک وظیفه [10] همچنین سررسید یک وظیفه می‌تواند تابعی از دوره‌تناوب آن باشد ]11[ . سه نوع مختلف دیگر از سررسیدها با توجه به وابستگی بین سررسید و دوره تناوب وجود دارند که عبارت انداز:
سررسيد ضمنی :
وظیفه‌ای دارای سررسید ضمنی است هرگاه سررسید متناظر آن با دوره تناوب آن برابر باشد. یک وظیفه τi با دوره تناوب Ti و سررسید Di ، یک سررسید ضمنی است هرگاه Ti= Di
سررسيد محدود :
وظیفه‌ای دارای سررسید محدود است هرگاه سررسید متناظر آن کوچکتر یا مساوی دوره تناوب آن باشد. یک وظیفه τi با دوره تناوب Ti و سررسید Di ، یک سررسید محدود است هرگاه Ti ≥ Di
سررسيد دلخواه :
در این حالت هیچ قید و بندی برای سررسید یک وظیفه وجود ندارد و سررسید آن می‌تواند کوچک‌تر، مساوی و یا بزرگتر از دوره تناوب آن وظیفه باشد، یعنی Ti ≥ Diیا Ti < Di
2-5 هسته پردازنده از زمان اختراع اولین پردازنده چندهسته‌ای، به نظر می‌رسد که استفاده از اصطلاح هسته برای واحدهای پردازشی یک سیستم به جای اصطلاح پردازنده، معقول‌تر و منطقی‌تر باشد. وقتی یک وظیفه در حالت (مرحله) “درحال اجرا” قرار می‌گیرد، دستورات آن توسط هسته‌ای که این وظیفه روی آن زمانبندی شده، اجرا می‌شود. اگر چندین وظیفه در سیستم وجود داشته باشد، در هر لحظه از زمان فقط یک وظیفه می‌تواند از نظر فیزیکی روی یک هسته اجرا شود. ممکن است عملکرد سیستم طوری باشد که به اجرای همزمان چندین وظیفه در یک لحظه از زمان نیاز داشته‌باشیم. به عنوان مثال در یک واحد کنترل پیشرفته از یک موتور احتراقی، تزریق سوخت، کنترل‌شده و همزمان از طریق تشخیص داده‌های آن ارائه می‌شود ]12[ .
با فرض داشتن فقط یک هسته، تنها راه اجرای دو وظیفه‌ای که به‌صورت همزمان وارد‌شده‌اند این است که بین اجرای این دو وظیفه سوئیچ کنیم. بنابراین در این حالت اصطلاح همزمانی به مسئله موازی بودن اشاره می‌کند. از آنجا که ممکن است وظایف دارای سررسید باشند، زمانبند باید مراقب باشد تا عملیات سوئیچ در زمان قابل قبولی انجام شود. اگر در یک سیستم تعبیه‌شده، بیش از یک هسته داشته باشیم، وظایف می‌توانند به معنای واقعی به صورت موازی و همزمان اجرا شوند. به این سیستم‌ها سیستم‌های چندهسته‌ای می‌گویند. به طور کلی تعداد زیادی از وظیفه‌ها وجود دارند که می‌توانند روی چندین هسته در یک سیستم چندهسته‌ای به صورت همزمان و موازی اجرا شوند ]12[ .
2-6 منابعبرخلاف یک هسته، یک منبع دستورات یک وظیفه را اجرا نمی‌کند. به هر حال برای یک وظیفه، ضروری است که دارای حرکت باشد تا جریانی را بوجود بیاورد. نمونه‌هایی از منابع عبارت انداز حافظه، سمافور، حسگر، محرکو…
هنگامی که دو یا چند وظیفه به یک منبع دسترسی داشته باشند، این منبع، منبع اشتراکی نامیده‌ می‌شود و نیازمند توجه بخصوصی است. فرض کنید یک وظیفه نتیجه محاسباتش را روی یک محل از حافظه بنویسد و سپس توسط وظیفه دیگری قبضه بشود که این وظیفه، روی همان محل حافظه بازنویسی کند. حال وقتی که اولین وظیفه دوباره اجرایش از سر گرفته می‌شود، به همان بخش از حافظه مراجعه کرده تا از نتیجه محاسبات قبلی‌اش استفاده کند ولی مقادیر نادرستی را از حافظه بازخوانی می‌کند. این چنین شرایطی، حالت‌ نامعین نامیده می‌شود ]12[ .
بسته به حافظه زبان برنامه‌نویسی و یا معماری آن، اثرات ناشی از حالت نامعین، ممکن است کاملا نامشخص باشد. به همین دلیل در بیشتر موارد تحت هرشرایطی سعی می‌شود که از این حالت اجتناب شود. به همین دلیل، منابع اشتراکی توسط ساختارهایی مانند سمافورها محافظت می‌شوند و روی سیاست زمانبندی تاثیر می‌گذارند. در مثال بالا اگر وظیفه، حافظه‌اش را قفل کرده‌بود و یا یک سمافوری داشت تا از محل حافظه‌اش محافظت کند، دیگر زمانبند نمی‌توانست آن را قبضه کند و درنتیجه حالت نامعین بوجود نمی‌آمد. یک منبع اشتراکی همچنین می‌تواند شامل واحدهای مختلفی باشد، مانند یک واحد چاپگر که دارای چندین دستگاه چاپگر می‌باشد. در حالت‌هایی که تعداد وظایف از تعداد منابع کمتر است، دسترسی به منابع اشتراکی به این صورت مدیریت می‌شود که اطمینان حاصل شود که هرگز دو وظیفه به صورت همزمان از یک منبع استفاده نکنند]12[ .
2-7 مفاهيم زمانبندییکی از هدف‌های اصلی سیستم‌های بی‌درنگ، زمانبندی است که از دو جنبه متفاوت می‌توان به آن نگاه کرد، یکی جنبه الگوریتمی و دیگری جنبه نرم‌افزار می‌باشد. دید الگوریتمی زمانبندی عبارت‌انداز تشخیص یک زمانبندی امکان‌پذیر از طریق یک الگوریتم زمانبندی مناسب. اما زمانبندی از دید نرم‌افزار عبارت‌انداز اعمال تصمیمات محکم سیاست زمانبندی روی سیستم‌عامل و قرار دادن وظایف به حالت اجرا در زمان مناسب توسط یک زمانبند]13[ .
یک مفهوم کلیدی که توسط زمانبند معرفی شده، بحث انحصاری بودن می‌باشد. قبضه کردن (به انحصار درآوردن) زمانی اتفاق می‌افتد که یک وظیفه درحال اجرا، توسط وقوع یک رخدادی، اجرایش متوقف و پردازنده به وظیفه دیگری اختصاص داده شود. به این عملیات اصطلاحاً سوئیچ‌کردن محتوای پردازنده می‌گویند که عملیاتی زمانبر برای پردازنده محسوب می‌شود]14[ . از دید الگوریتمی، مسئله زمانبندی شامل موارد زیر می‌باشد:
گرفتن یک مجموعه وظیفه τ شامل n وظیفه بی‌درنگ و همچنین مشخصه‌های وابسته به آن‌ها که در قسمت 2-3-1 توضیح داده‌شد، زمانبندی کردن، که برای هرلحظه مشخص می‌کند که کدام وظیفه در بین آن‌هایی که آزاد شده‌اند، باید اجرا شود. یک زمانبند تحت شرایط زیر باید مطمئن باشد که همه وظایف، به‌موقع اجراشده و تمام شوند:
الف) یک وظیفه قبل از زمان ورودش زمانبندی نشده‌است.
ب) اولویت درمیان وظایف یکسان رعایت شده‌است.
2-7-1 تعاريف مربوط به مبحث زمانبندیزمانبند :
یک زمانبند، یک بخش از سیستم عامل است که هدف اصلی آن این است که تعیین کند، کدام وظیفه، روی کدام هسته و در چه زمانی اجرا شود، حتی اگر هیچ سیستم عاملی هم وجود نداشته باشد ]15[ . به عنوان مثال در یک سیستم بسیار ساده مانند لباس‌شویی، یک سیاست زمانبندی موردنیاز است تا به سیستم اجازه دهد که بیش از یک وظیفه را دربر داشته باشد.
قابليت زمانبندی :
یک مجموعه وظیفه τ، قابلیت زمانبندی HRT توسط الگوریتم A را دارد هرگاه A همیشه یک زمانبندی امکان‌پذیر را برای τ تولید کند. (هیچ‌کدام از وظایف با الگوریتم A ، سررسیدشان را ازدست ندهند)
یک مجموعه وظیفه τ، قابلیت زمانبندی SRT توسط الگوریتم A را دارد، هرگاه حداکثر تاخیر اجرای وظایف آن کران‌دار باشد.
شدنی‌بودن :
یک مجموعه وظیفه τ روی یک بستر، امکان‌پذیر و شدنی است اگر یک الگوریتم زمانبندی‌ وجود داشته باشد که تحت آن همه وظایف τ در سررسید خود به اتمام برسند.
کلاس شدنی‌بودن :
یک مجموعه وظیفه τ تحت کلاس C از الگوریتم زمانبندی، شدنی است اگر بتواند توسط هر الگوریتم زمانبندی دیگری زمانبندی شود، به طوریکه آن الگوریتم نیز خود تحت کلاس C باشد.
بهينگی :
الگوریتم A را با توجه به کلاس C بهینه گویند، هرگاه AϵC باشد و به طور صحیحی همه وظایف سیستم که تحت کلاس C شدنی هستند را زمانبندی کند. اگر کلاس C تعیین نشده‌باشد، آنگاه معمولا فرض بر شامل بودن همه‌ی الگوریتم‌های زمانبندی ممکن می‌شود.
کارايی زمانبندی:
چیزی که مکررا در آثار و نوشته‌های مختلف استفاده‌شده، بیان می‌کند که الگوریتم A1 کارایی زمانبندی بهتری نسبت به الگوریتم A2 دارد، این به معنای توانایی الگوریتم A1 در زمانبندی‌کردن امکان‌پذیر مجموعه وظایف با عامل‌های بهره‌وری بالاتری نسبت به الگوریتم A2 است.
2-8 سيستم های چندهسته‌ای
در طول سال‌های اخیر، محققان و طراحان سیستم‌های بی‌درنگ، مدل‌ها، نظریه‌ها و نرم‌افزار‌های زیادی را برای پوشش مسئله موازی سازی بین وظیفه‌ای توسعه داده‌اند، که در آن بار کاری شامل مجموعه‌ای از وظایف مستقل متوالی است و در نتیجه افزایش تعداد هسته‌های پردازنده به سیستم ما اجازه می‌دهد تا کارهای بیشتری را اجرا کند ]16[.
واژه چندپردازنده، ما را یادآور سیستم‌های رایانه‌ای می‌کند که قابلیت انجام محاسبات بیشتر از یک واحد محاسباتی برای اجرای پردازه‌های نرم‌افزاری را دارد. چندپردازنده‌ها مفهوم جدیدی نیستند، در واقع آن‌ها از اوایل ده شصت در صنعت شناخته شده اند. اما سیستم‌های چندپردازنده در اوایل، مبتنی بر تراشه‌های فیزیکی چندگانه بودند که به یک گذرگاه اتصال ویژه احتیاج داشتند، در نتیجه بسیار گران‌قیمت و پیچیده بودند. آخرین نسل از پردازنده‌های چندهسته‌ای برای رایانه‌های رومیزی و سیستم‌های سرویس‌دهنده و سیستم‌های چندپردازنده روی تراشه (MPSoC) در سیستم‌های تعبیه شده، دچار تغییرات زیادی شده‌اند به طوری که واژه چندپردازنده را به یک واقعیت روزمره تبدیل کرده‌اند ]17[ .
امروزه، چندپردازشی به وضوح به عنوان روش اصلی برای بهره‌گیری از سطح مجتمع‌سازی بالای سیلیکون، درنظر گرفته‌شده است. این موضوع برای تقریبا هر مقیاس محاسباتی، از سیستم‌های چندهسته‌ای تعبیه‌شده و کم‌مصرف مانند تراشه‌های NVIDIA مشهور و TI-OMAP به کار رفته در لوازم الکترونیکی مصرفی، گرفته تا خوشه‌های محاسباتی باکارایی بالا، مانند پردازنده 48 هسته‌ای Intel SCC و یا پردازنده‌های گرافیکی قدرتمند خانواده NVIDIA Tesla (GPGPUs) ، به یک مدل مرجع تبدیل شده است. با این حال، در حالی که تراشه‌های چندهسته‌ای و چند پردازشی به طور کلی به عنوان استانداردی برای صنعت الکترونیک در سال‌های آینده تصدیق شده‌ هستند، اما هنوز معماری داخلی برخی پردازنده‌های چندهسته‌ای، رتبه‌دهی نشده‌اند و در حال حاضر طیف گسترده‌ای از گرایش‌های مختلف معماری این سیستم‌ها، بحث‌های فعال مطرح‌شده در هردو جامعه صنعتی و علمی هستند ]18[ .
وجود تنوع در سراسر طیف وسیعی از معماری چندهسته‌ای، صرفا یک چالش نیست. در یک سیستم واحد، معماری هسته‌ها می‌تواند متفاوت باشد، همانطور که روند کنونی چنین است و بیشتر به سمت ترکیبی از هسته‌های متفاوت می‌رود. در طراحی برخی سیستم‌ها، هسته‌ها دارای مجموعه دستورالعمل‌های مشترکی هستند ولی مشخصه‌های کارایی آن‌ها باهم متفاوت است.
از این رو، یک پردازنده با تعداد کمی هسته‌های قدرتمند ، برای برنامه‌های موازی، ناکارامد می‌باشد. اما از سوی دیگر، یک پردازنده با تعداد زیادی هسته‌های ضعیف‌، ممکن است در اجرای برنامه‌هایی که نیازمند عملیات محاسباتی ترتیبی هستند، ضعیف عمل کند. حالت دیگر در سیستم‌های چندهسته‌ای ، داشتن هسته‌هایی با مجموعه دستورالعمل‌های متفاوت برای توابع تخصصی (مانند ترکیب کردن سیستم‌های همه‌منظوره و هسته‌های DSP ) می‌باشد. از کاربردهای این حالت می‌توان به GPU ها، مدارهای واسط شبکه و دیگر کاربردهای خاص و قابل برنامه‌ریزی اشاره‌کرد.
2-9 نتيجه‌گيریدر این فصل به تعریف سیستم‌های تعبیه‌شده و کاربردهای مهم آن در زندگی روزمره پرداخته شد و مفهوم بی‌درنگ بودن و انواع سیستم‌های بی‌درنگ شرح داده شد. سپس به بیان تعاریف مفاهیم اولیه در سیستم‌های بی‌درنگ تعبیه‌شده پرداخته شد و در پایان نیز سیستم‌های چندهسته‌ای تعبیه‌شده تعریف و شرح داده‌ شدند.
-382542-61640400
فصل سوم
فصل سوم : مرور منابع و کارهای انجام‌شدهدر فصل قبل مفاهیمی مانند سیستم‌های تعبیه‌شده و تعبیه شده بی‌درنگ، اهمیت مصرف انرژی در آن‌ها و اصطلاحات مهم آن، به طور کامل تشریح شد و سپس مفهوم زمانبندی مورد بررسی قرار گرفت و در نهایت سیستم‌های چندهسته‌ای معرفی و تعریف شدند. دراین فصل ابتدا به طبقه‌بندی انواع روش‌های زمانبندی تک‌هسته‌ای و چند‌هسته‌ای می‌پردازیم، سپس انواع معماری سیستم‌های چندهسته‌ای را تشریح می‌کنیم، پس از آن، روش‌های زمانبندی مبتنی بر تنظیم فرکانس و ولتاژ را بیان می‌کنیم و در نهایت به شرح کامل روش‌های زمانبندی چندهسته‌ای ارائه شده در سال‌های گذشته می‌پردازیم و مزایا و معایب آن‌ها را تحلیل می‌کنیم.
3-1 طبقه بندی روش‌های زمانبندیدر این بخش مروری داریم بر طبقه‌بندی الگوریتم‌های زمانبندی که مگر در موارد مشخص‌شده، درهمه‌ موارد، قبضه‌ای بودن اجازه داده‌ شده‌است.
زمانبندی برخط و برون‌خط :
اولین نوع زمانبندی، براساس زمانی که زمانبندی در آن تولید می‌شود و همچنین تمایز بین زمانبندی برخط و زمانبندی برون‌خط، شکل گرفته است. در زمانبندی‌های برخط، در مورد اینکه چگونه وظایف در زمان اجرا در طول عملیات سیستم، زمانبندی شوند، تصمیم‌گیری می‌شود. بنابراین الگوریتم زمانبندی که بکار گرفته می‌شود، نشان‌دهنده نقش فعال و اساسی بخشی از نرم‌افزار است که بارها و بارها احضار می‌شود تا برای انجام زمانبندی مناسب تصمیماتی را به صورت لحظه‌ای اتخاذ کند. ( مانند آزادشدن یک وظیفه، انقضاء یک ساعت، تمام شدن یک وظیفه )
به همین دلیل الگوریتم‌های زمانبندی برخط، اگرچه بسیار انعطاف‌پذیر هستند؛ به عنوان مثال اجازه می‌دهند که یک وظیفه بی‌درنگ جدید به صورت پویا به سیستم وارد شده و زمانبندی شوند؛ ولی باعث بوجود آمدن سربار زمان اجرا می‌شوند که باید با دقت بالایی محاسبه شود. در مورد الگوریتم‌های پیچیده، در حقیقت خود الگوریتم زمانبندی ممکن است هزینه‌ها و سربارهای محاسباتی غیرقابل اغماضی را مطالبه کند، که باعث می‌شود کل سیستم (وظایف بی‌درنگ+ زمانبند) غیرقابل زمانبندی شود.اگرچه زمانبندی برخط نشان داده است که یک طرح بسیار معمولی در بیشتر سیستم‌‌های تعبیه‌شده نوین می‌باشد.
برخلاف زمانبندی برخط، در زمانبندی برون‌خط، سیاست زمانبندی در طول زمان اجرای سیستم بی‌درنگ، اعمال نمی‌شود، بلکه از آن برای گرفتن تصمیمات و ایجاد دنباله‌ای از عملیات زمانبندی، قبل از فعال‌شدن و شروع به کار سیستم استفاده می‌شود. این رویکرد که طبیعتی ایستا و غیرقابل انعطاف دارد، به طراح اجازه می‌دهد که یک تصمیم بهینه و درعین حال بسیار پیچیده‌ای بگیرد. الگوریتم‌هایی که در برخی موارد نشان‌دهنده آخرین راه‌حل می‌باشند درحالی که تقاضای محاسباتی بالا و محدودیت زمانی سخت، اجازه مطرح‌شدن پیشنهادات برخط را نمی‌دهد.
ممکن است حالتی نیز وجود داشته باشد که الگوریتم زمانبندی آن با استفاده از تجزیه‌شدن به دو مرحله، چیزی بین این دو رده‌بندی باشد. برای مثال، می‌توان الگوریتم را به یک مرحله پیش‌پردازش جدا تجزیه کرد که در آن تمام وظایف مجموعه τ، به زیرمجموعه‌های کوچکتر تقسیم شده و در مرحله زمانبندی واقعی، یک الگوریتم زمانبندی برخط بروی هرکدام از زیرمجموعه‌های شناسایی شده اعمال می‌شود. مرحله پیش‌پردازش، در این موارد ممکن است به منظور کاهش پیچیدگی مسئله و سربار زمان اجرای آن، به صورت برون‌خط باشد.
زمانبندی مبتنی بر اولویت:
الگوریتم‌های زمانبندی با توجه به نحوه تخصیص اولویت به سه دسته تقسیم می‌شوند:
الگوریتم‌های اولویت ایستا
در این شیوه به هر وظیفه یک اولویت منحصر به فرد اختصاص داده‌ می‌شود و همه‌ی نخ‌های یک وظیفه دارای اولویت یکسانی هستند. بنابراین هرگاه وظیفه T1 دارای اولویت بالاتری نسبت به وظیفه T2 داشته باشد، سپس هرزمان که هر دو وظیفه دارای نخ‌های فعالی باشند، نخ‌های وظیفه T1 بر T2 مقدم خواهد بود. نمونه‌ای از یک الگوریتم زمانبندی اولویت ایستا، الگوریتم زمانبندی نرخ یکنواخت (RMS) می‌باشد.
الگوریتم‌های اولویت پویای سطح نخ
برای جفت نخ‌های Tij و Ti,j, ، اگر Tij اولویت بالاتری نسبت به Ti,j, در برخی لحظه‌های زمانی داشته باشد، آنگاه Tij همیشه اولویت بالاتری نسبت به Ti,j, دارد. نمونه‌ای از زمانبندی که دز این کلاس قرار می‌گیرد، زمانبندی ابتدا نزدیکترین سررسید (EDF) می‌باشد.
الگوریتم‌های اولویت پویای بدون محدودیت
در این حالت هیچ محدودیتی در اولویتی که به یک وظیفه داده می‌شود وجود ندارد و اولویت مربوط به دو وظیفه ممکن است در طول زمان تغییر کند. به عنوان یک مثالی از این نوع که در هیچ‌یک از دو رده‌بندی قبل جای نمی‌گیرد، می‌توان به الگوریتم LLF اشاره کرد]19[ .
با توجه به این تعاریف الگوریتم‌های اولویت پویای بدون محدودیت یک حالت کلی از الگوریتم‌های اولویت پویای سطح نخ هستند و الگوریتم‌های اولویت پویای سطح نخ نیز یک حالت کلی از الگوریتم‌های اولویت ثابت می‌باشند.
الگوریتم‌های WCET محور :
یکی از مهم‌ترین مشخصه‌هایی که برای وظایف بی‌درنگ مطرح شده، WCET یا بدترین حالت زمان اجرای وظیفه می‌باشد. این ویژگی برای تقریبا بیشتر آزمون‌های تجزیه و تحلیل قابلیت زمانبندی شناخته‌شده ، اساسی است(تعیین پیشبینی این‌که یک الگوریتم زمانبندی، قادر به زمانبندی کردن وظیفه روی زمینه داده‌شده تحت بدترین مفروضات ممکن است یا نه). این پارامتر ممکن است در زمان اجرا توسط الگوریتم برای گرفتن تصمیمات زمانبندی موردنیاز باشد یا ممکن است نباشد.
در این رابطه ما می‌توانیم الگوریتم‌هایی که WCET محور هستند ( مانند الگوریتم LLF ) را از الگوریتم‌هایی که WCET محور نیستند ( مانند الگوریتم RMS و EDF ) را از هم تمییز دهیم. این تفاوت معمولا هنگامی که وظایف از تخمین بدترین حالت زمان اجرایشان منحرف می‌شوند، دلالت قوی بر رفتار الگوریتم‌های زمانبندی دارد.
center-66675انواع روش‌های زمانبندی
00انواع روش‌های زمانبندی

157162523622000358467225100400
67564011430مبتنی بر اولويت
00مبتنی بر اولويت
right4455زمانبندی WCET محور
00زمانبندی WCET محور

14477991352560049530014478000218122513525500
-454123278130اولويت پويای بدون محدوديت
0اولويت پويای بدون محدوديت
1547495289560اولويت پويای سطح نخ
0اولويت پويای سطح نخ
3300730315595اولويت ايستا
0اولويت ايستا

1889125271145002082802616200067310025908000251587026860500358076529273500424624528702000
2477135163195پويا
0پويا
897255146050پويا
0پويا
594360154940ايستا
0ايستا
2429510172085ايستا
0ايستا
4276090189230پويا
0پويا
4180840180340ايستا
00ايستا

شکل 3-1 تفسیم‌بندی انواع روش‌های زمانبندی ]12[

Related posts: