ایستا
شکل ۳-۱ تفسیم‌بندی انواع روش‌های زمانبندی ]۱۲[
شکل ۴شکل ۳-۱ تفسیم‌بندی انواع روش‌های زمانبندی
طبقه بندی انواع روش‌های زمانبندی را در شکل ۳-۱ مشاهده می‌کنید.
۳-۲ الگوریتم‌های زمانبندی بی‌درنگ تک پردازنده
یکی از معروفترین الگوریتم‌های زمانبندی روی یک هسته، الگوریتم EDF است که از نوع الگوریتم‌های اولویت پویا می‌باشد. این روش بطور کلی از توان محاسباتی پردازنده استفاده کرده و زمانبندی را بصورت دینامیک و درصورت فعال شدن هر وظیفه در زمان اجرا انجام می­دهد. فرض اولیه برای EDF این ‌است که در هر نقطه از زمان، اولویت یک وظیفه فعال شده ثابت نیست و به زمان بستگی دارد و در زمان فعال شدن وظیفه بعدی ممکن است تغییر یابد. اولویت،طبق سیاست EDF بدین صورت تعریف می­ شود که وظیفه درحال اجرا باید کمترین زمان باقی مانده تا درخواست بعدی را از بین تمامی وظایف فعال در صف آماده، داشته باشد، به عبارتی اولویت اجرا با وظیفه ­ای است که نزدیکترین سررسید را داشته باشد، یعنی سررسید مطلق کوچکتری داشته باشد]۲۰[ . وظیفه ­ای که بیشترین اولویت (کمترین سررسید) را دارا می­باشد زودتر اجرا می­ شود.

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

الگوریتم EDF ، از دید کارایی زمانبندی، با توجه به ماهیت پویای آن، دارای عملکرد بهتری نسبت به الگوریتم‌‌های اولویت ایستا می‌باشد. مثالی از این نوع الگوریتم در شکل ۳-۲ نشان داده‌شده است]۲۱[ .

بهره وری

سررسید

WCET

دوره تناوب

وظیفه

۰٫۵

۱۰

۵

۱۰

T1

۰٫۴

۱۵

۶

۱۵

T2

شکل ۳-۲ مثالی از کاربرد زمانبندی تک هسته‌ای با بهره گرفتن از الگوریتم EDF ]21[
شکل ۵شکل ۳-۲ مثالی از کاربرد زمانبندی تک هسته‌ای با بهره گرفتن از الگوریتم EDF [21]
در یک حالت خاص از سیستم‌های تک‌پردازنده، EDF یک الگوریتم زمانبندی بهینه محسوب می‌شود. در واقع الگوریتم EDF یک الگوریتم بهینه برای زمانبندی وظایف تناوبی انحصاری می‌باشد. در حالتی که بهره‌وری یک وظیفه به صورت نسبت WCET بر دوره تناوب وظیفه تعریف می‌شود، EDF می‌تواند برای حالتی که مجموع بهره‌وری همه وظایف کمتر از یک باشد، ملاقات همه سررسیدهای وظایف را تضمین کند]۲۲[ . در یک حالت عام‌تر که دارای وظایف پراکنده با سررسید غیر ضمنی می‌باشد، یک مجموعه وظیفه، قابل زمانبندی می‌باشد اگر( اما نه ضرورتا تنها اگر) ظرفیت[۱۰۰] آن کوچک‌تر یا مساوی یک باشد (≤۱ Δ ) ]۲۱[ .
میزان بهینه‌بودن EDF می‌تواند با بهره گرفتن از روش مبادله برشی[۱۰۱] ، که بر اساس این اصل است که هر زمانبندی معتبر برای هر مجموعه وظیفه را می‌توان به یک زمانبندی EDF معتبر تبدیل نمود، بهبود یابد:
(۱)
که در آن Ci بدترین حالت زمان اجرا، Ti دوره تناوب هر وظیفه و Di سررسید هر وظیفه می‌باشد.
همچنین می‌توان گفت که EDF در صورتی بهینه است که برای زمانبندی وظایف روی پردازنده‌ای استفاده شود که در آن انحصاری بودن مجاز باشد و وظایف نگران منابع نباشند ]۲۳[ .
الگوریتم EDF در سیستم‌های تک‌پردازنده ، نوعا به دیگر الگوریتم‌های اولویت پویای بدون محدودیت، ترجیح داده‌ می‌شود. به هر حال EDF یک نمونه کلیدی از الگوریتم‌های غیرآگاه به WCET می‌باشد، به این صورت که اولویت وظایف را در هنگام آزادشدن آن‌ها اختصاص داده و منحصرا به سررسید مطلق آن‌ها بستگی دارد]۲۱[ .
یکی دیگر از الگوریتم‌های زمانبندی معروف، الگوریتم زمانبندی نرخ یکنواخت است که الگوریتمی اولویت‌دار و ایستا (زمانبندی در زمان کامپایل مشخص می­ شود) می‌باشد. این الگوریتم اولویت­ها را براساس دوره تناوب اختصاص می‌دهد، طوریکه وظیفه با کوتاهترین دوره تناوب و یا بالاترین نرخ اجرا، بالاترین اولویت را پیدا می‌کند. Liu و Layland نشان دادند که درصورتی‌که تخصیص اولویت RMS امکان پذیر نباشد در اینصورت مجموعه ­ای از وظایف قابل زمانبندی نیستند]۲۴[ .
در این الگوریتم فرض می‌شود که تمامی وظایف به‌صورت دوره‌‌ای تکرار می‌شوند، همچنین همزمانی[۱۰۲] ، اشتراک منابع و مبادله[۱۰۳] و تغییر داده در وظایف وجود ندارد. طبق این الگوریتم تمامی وظایف با مشخصه بی‌درنگ سخت درصورتیکه شرط زیر برقرار باشد همواره در سررسید متناظرشان اجرا می‌شوند]۲۴[ :
که در آن n تعداد وظایف، بدترین حالت زمان اجرای هر وظیفه و دوره تناوب هر وظیفه می‌باشد.
زمانیکه مقدار و این یعنی برای اینکه تمامی وظایف بی‌درنگ سخت در زمان مناسب اجرا شوند، پردازنده باید ۷۰% زمان خود را صرف این وظایف کند و این درحالی است که پردازنده، قادر به اختصاص ۱۰۰% زمان خود به وظایف بی‌درنگ نرم می­باشد بنابراین این ویژگی خوب نیست چراکه در این‌صورت زمانی برای تغییر کدها و مشخصه­های اضافه‌شده نداریم. در واقع باید سیستمی طراحی کرد که کمتر از ۶۰% تا ۷۰% از زمان پردازنده به اجرای وظایف اختصاص یابد. علاوه بر مشکلات گفته‌شده در صورتی‌که وظیفه با بالاترین نرخ اجرا، بالاترین اولویت را داشته باشد ممکن است وظیفه ­ای که خیلی مهم نیست و درعین حال زیاد اجرا می­ شود بالاترین اولویت را بگیرد و این باعث وقوع قحطی در وظایف مهم‌تر با نرخ اجرای کمتر می­ شود]۲۴[ و ]۲۵[ .
۳-۳ طبقه‌بندی معماری سیستم‌های چندهسته‌ای
در میان تعداد زیادی از انواع مدل‌های چندپردازنده، چه طراحی‌های سخت‌افزاری چه طراحی‌های نرم‌افزاری، دو نوع طرح معماری مرجع وجود دارد که یکی پردازنده‌های چندهسته‌ای همگن(SMP)[104] و دیگری پردازنده‌های چندهسته‌ای ناهمگن (AMP)[105] نام دارد.
SMP یک مجموعه به هم متصل دارای معماری پردازنده‌های یکسان است که از طریق یک گذرگاه مشترک باهم ارتباط دارند. (شکل ۳-۳ ) در این سیستم‌ها، تمامی پردازنده‌ها دارای نسخه یکسانی از سیستم‌عامل هستند و در هنگام نیاز با هم ارتباط برقرار می‌کنند.
این طرح که بصورت گسترده در کامپیوترهای شخصی و رومیزی استفاده می­ شود عموماً برای کنترل و هموار کردن مسیر تعادل بارگذاری پویا در محاسبات کاربردهای چند وظیفه ­ای، بصورت بسیار رایجی استفاده می­ شود. ارزش مدل برنامه­نویسی واضح­تر (دید حافظه یکنواخت) توسط تعداد زیادی از شیوه ­های سخت­افزاری تخصیص داده شده بیان می­ شود. بعنوان مثال مدیریت وابستگی حافظه نهان[۱۰۶]، مسیریابی IRQ [۱۰۷] (که می ­تواند برای سیستم­های تعبیه­شده، هم به سبب نیازمندی­های مساحت و هم نیازمندی­های توان، بسیار هزینه بر باشد.). بنابراین در مقیاس کوچک و سیستم­های تعبیه­شده بسیار مجتمع­شده، AMP، اغلب بعنوان راهنمایی برای انتخاب استفاده می­ شود.
AMP می ­تواند بصورت یک طرح چندپردازنده­ای (شکل ۳-۳- ب) که در آن تمامی پردازنده­ها مستقل بوده و نیازی به اشتراک­گذاری تمامی حافظه فیزیکی نیست، بیان شود. بطور نمونه اکثر شیوه ­های اتصال برای ارتباطات داخلی پردازنده، توسط سخت­افزار ارائه می­ شود. این محدودیت، یک تأثیر قوی و شایان برروی سازماندهی نرم­افزار سراسری دارد که نیازمند راهکارهایی برای توزیع و از حالت متمرکز درآوردن، می­باشد. بعنوان مثال یک سیستم­عامل مشخص باید بصورت مستقل برروی هر پردازنده، اجرا شده و بصورت جداگانه و بدون هیچ حمایت مستقیمی، عملیاتش را انجام دهد. پردازنده‌های چندهسته‌ای ناهمگن از هسته‌هایی تشکیل شده اند که مجموعه دستورات یکسانی را پشتیبانی می‌کنند اما دارای کارایی متفاوتی هستند، این هسته‌ها در فرکانس کاری، توان مصرفی، در اندازه حافظه نهان و بعضی صفات ساختاری دیگر باهم متفاوت هستند. عدم تقارن می‌تواند به صورت هدفمند و طی فرایند ساخت مجزا و برنامه‌ریزی شده یا به دلیل رخداد انحراف در فرایند ساخت حادث شود، یا ناشی از تنظیم فرکانس ساعت باشد]۴[ .

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


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