پایان نامه رایگان درمورد الگوریتم زمانبندی، اجرای برنامه، جامعه صنعتی

دانلود پایان نامه ارشد

سیستم‌های رایانه‌ای می‌کند که قابلیت انجام محاسبات بیشتر از یک واحد محاسباتی برای اجرای پردازه‌های نرم‌افزاری را دارد. چندپردازنده‌ها مفهوم جدیدی نیستند، در واقع آن‌ها از اوایل ده شصت در صنعت شناخته شده اند. اما سیستم‌های چندپردازنده در اوایل، مبتنی بر تراشه‌های فیزیکی چندگانه بودند که به یک گذرگاه80 اتصال ویژه احتیاج داشتند، در نتیجه بسیار گران‌قیمت و پیچیده بودند. آخرین نسل از پردازنده‌های چندهسته‌ای برای رایانه‌های رومیزی81 و سیستم‌های سرویس‌دهنده و سیستم‌های چندپردازنده روی تراشه (MPSoC)82 در سیستم‌های تعبیه شده، دچار تغییرات زیادی شده‌اند به طوری که واژه چندپردازنده را به یک واقعیت روزمره تبدیل کرده‌اند ]17[ .
امروزه، چندپردازشی به وضوح به عنوان روش اصلی برای بهره‌گیری از سطح مجتمع‌سازی83 بالای سیلیکون، درنظر گرفته‌شده است. این موضوع برای تقریبا هر مقیاس محاسباتی، از سیستم‌های چندهسته‌ای تعبیه‌شده و کم‌مصرف مانند تراشه‌های NVIDIA مشهور و 84 TI-OMAP به کار رفته در لوازم الکترونیکی مصرفی، گرفته تا خوشه‌های محاسباتی85 باکارایی بالا، مانند پردازنده 48 هسته‌ای Intel SCC و یا پردازنده‌های گرافیکی قدرتمند خانواده NVIDIA Tesla (GPGPUs)86 ، به یک مدل مرجع تبدیل شده است. با این حال، در حالی که تراشه‌های چندهسته‌ای و چند پردازشی به طور کلی به عنوان استانداردی برای صنعت الکترونیک در سال‌های آینده تصدیق شده‌ هستند، اما هنوز معماری داخلی برخی پردازنده‌های چندهسته‌ای، رتبه‌دهی نشده‌اند و در حال حاضر طیف گسترده‌ای از گرایش‌های مختلف معماری این سیستم‌ها، بحث‌های فعال مطرح‌شده در هردو جامعه صنعتی و علمی هستند ]18[ .
وجود تنوع در سراسر طیف وسیعی از معماری چندهسته‌ای، صرفا یک چالش نیست. در یک سیستم واحد، معماری هسته‌ها می‌تواند متفاوت باشد، همانطور که روند کنونی چنین است و بیشتر به سمت ترکیبی از هسته‌های متفاوت می‌رود. در طراحی برخی سیستم‌ها، هسته‌ها دارای مجموعه دستورالعمل‌های مشترکی هستند ولی مشخصه‌های کارایی آن‌ها باهم متفاوت است.
از این رو، یک پردازنده با تعداد کمی هسته‌های قدرتمند ، برای برنامه‌های موازی، ناکارامد می‌باشد. اما از سوی دیگر، یک پردازنده با تعداد زیادی هسته‌های ضعیف‌، ممکن است در اجرای برنامه‌هایی که نیازمند عملیات محاسباتی ترتیبی هستند، ضعیف عمل کند. حالت دیگر در سیستم‌های چندهسته‌ای ، داشتن هسته‌هایی با مجموعه دستورالعمل‌های متفاوت برای توابع تخصصی (مانند ترکیب کردن سیستم‌های همه‌منظوره و هسته‌های DSP ) می‌باشد. از کاربردهای این حالت می‌توان به GPU ها، مدارهای واسط شبکه و دیگر کاربردهای خاص و قابل برنامه‌ریزی اشاره‌کرد.

2-9 نتيجه‌گيری
در این فصل به تعریف سیستم‌های تعبیه‌شده و کاربردهای مهم آن در زندگی روزمره پرداخته شد و مفهوم بی‌درنگ بودن و انواع سیستم‌های بی‌درنگ شرح داده شد. سپس به بیان تعاریف مفاهیم اولیه در سیستم‌های بی‌درنگ تعبیه‌شده پرداخته شد و در پایان نیز سیستم‌های چندهسته‌ای تعبیه‌شده تعریف و شرح داده‌ شدند.

فصل سوم
فصل سوم : مرور منابع و کارهای انجام‌شده

در فصل قبل مفاهیمی مانند سیستم‌های تعبیه‌شده و تعبیه شده بی‌درنگ، اهمیت مصرف انرژی در آن‌ها و اصطلاحات مهم آن، به طور کامل تشریح شد و سپس مفهوم زمانبندی مورد بررسی قرار گرفت و در نهایت سیستم‌های چندهسته‌ای معرفی و تعریف شدند. دراین فصل ابتدا به طبقه‌بندی انواع روش‌های زمانبندی تک‌هسته‌ای و چند‌هسته‌ای می‌پردازیم، سپس انواع معماری سیستم‌های چندهسته‌ای را تشریح می‌کنیم، پس از آن، روش‌های زمانبندی مبتنی بر تنظیم فرکانس و ولتاژ را بیان می‌کنیم و در نهایت به شرح کامل روش‌های زمانبندی چندهسته‌ای ارائه شده در سال‌های گذشته می‌پردازیم و مزایا و معایب آن‌ها را تحلیل می‌کنیم.

3-1 طبقه بندی روش‌های زمانبندی
در این بخش مروری داریم بر طبقه‌بندی الگوریتم‌های زمانبندی که مگر در موارد مشخص‌شده، درهمه‌ موارد، قبضه‌ای بودن اجازه داده‌ شده‌است.
زمانبندی برخط87 و برون‌خط88 :
اولین نوع زمانبندی، براساس زمانی که زمانبندی در آن تولید می‌شود و همچنین تمایز بین زمانبندی برخط و زمانبندی برون‌خط، شکل گرفته است. در زمانبندی‌های برخط، در مورد اینکه چگونه وظایف در زمان اجرا در طول عملیات سیستم، زمانبندی شوند، تصمیم‌گیری می‌شود. بنابراین الگوریتم زمانبندی که بکار گرفته می‌شود، نشان‌دهنده نقش فعال و اساسی بخشی از نرم‌افزار است که بارها و بارها احضار می‌شود تا برای انجام زمانبندی مناسب تصمیماتی را به صورت لحظه‌ای اتخاذ کند. ( مانند آزادشدن یک وظیفه، انقضاء یک ساعت، تمام شدن یک وظیفه )
به همین دلیل الگوریتم‌های زمانبندی برخط، اگرچه بسیار انعطاف‌پذیر هستند؛ به عنوان مثال اجازه می‌دهند که یک وظیفه بی‌درنگ جدید به صورت پویا به سیستم وارد شده و زمانبندی شوند؛ ولی باعث بوجود آمدن سربار89 زمان اجرا می‌شوند که باید با دقت بالایی محاسبه شود. در مورد الگوریتم‌های پیچیده، در حقیقت خود الگوریتم زمانبندی ممکن است هزینه‌ها و سربارهای محاسباتی غیرقابل اغماضی را مطالبه کند، که باعث می‌شود کل سیستم (وظایف بی‌درنگ+ زمانبند) غیرقابل زمانبندی شود.اگرچه زمانبندی برخط نشان داده است که یک طرح بسیار معمولی در بیشتر سیستم‌‌های تعبیه‌شده نوین می‌باشد.
برخلاف زمانبندی برخط، در زمانبندی برون‌خط، سیاست زمانبندی در طول زمان اجرای سیستم بی‌درنگ، اعمال نمی‌شود، بلکه از آن برای گرفتن تصمیمات و ایجاد دنباله‌ای از عملیات زمانبندی، قبل از فعال‌شدن و شروع به کار سیستم استفاده می‌شود. این رویکرد که طبیعتی ایستا و غیرقابل انعطاف دارد، به طراح اجازه می‌دهد که یک تصمیم بهینه و درعین حال بسیار پیچیده‌ای بگیرد. الگوریتم‌هایی که در برخی موارد نشان‌دهنده آخرین راه‌حل می‌باشند درحالی که تقاضای محاسباتی بالا و محدودیت زمانی سخت، اجازه مطرح‌شدن پیشنهادات برخط را نمی‌دهد.
ممکن است حالتی نیز وجود داشته باشد که الگوریتم زمانبندی آن با استفاده از تجزیه‌شدن به دو مرحله، چیزی بین این دو رده‌بندی باشد. برای مثال، می‌توان الگوریتم را به یک مرحله پیش‌پردازش90 جدا تجزیه کرد که در آن تمام وظایف مجموعه τ، به زیرمجموعه‌های کوچکتر تقسیم شده و در مرحله زمانبندی واقعی، یک الگوریتم زمانبندی برخط بروی هرکدام از زیرمجموعه‌های شناسایی شده اعمال می‌شود. مرحله پیش‌پردازش، در این موارد ممکن است به منظور کاهش پیچیدگی مسئله و سربار زمان اجرای آن، به صورت برون‌خط باشد.
زمانبندی مبتنی بر اولویت:
الگوریتم‌های زمانبندی با توجه به نحوه تخصیص اولویت به سه دسته تقسیم می‌شوند:
الگوریتم‌های اولویت ایستا91
در این شیوه به هر وظیفه یک اولویت منحصر به فرد اختصاص داده‌ می‌شود و همه‌ی نخ‌های92 یک وظیفه دارای اولویت یکسانی هستند. بنابراین هرگاه وظیفه T1 دارای اولویت بالاتری نسبت به وظیفه T2 داشته باشد، سپس هرزمان که هر دو وظیفه دارای نخ‌های فعالی باشند، نخ‌های وظیفه T1 بر T2 مقدم خواهد بود. نمونه‌ای از یک الگوریتم زمانبندی اولویت ایستا، الگوریتم زمانبندی نرخ یکنواخت (RMS) 93 می‌باشد.
الگوریتم‌های اولویت پویای سطح نخ94
برای جفت نخ‌های Tij و Ti,j, ، اگر Tij اولویت بالاتری نسبت به Ti,j, در برخی لحظه‌های زمانی داشته باشد، آنگاه Tij همیشه اولویت بالاتری نسبت به Ti,j, دارد. نمونه‌ای از زمانبندی که دز این کلاس قرار می‌گیرد، زمانبندی ابتدا نزدیکترین سررسید (EDF)95 می‌باشد.
الگوریتم‌های اولویت پویای بدون محدودیت96
در این حالت هیچ محدودیتی در اولویتی که به یک وظیفه داده می‌شود وجود ندارد و اولویت مربوط به دو وظیفه ممکن است در طول زمان تغییر کند. به عنوان یک مثالی از این نوع که در هیچ‌یک از دو رده‌بندی قبل جای نمی‌گیرد، می‌توان به الگوریتم LLF 97 اشاره کرد]19[ .
با توجه به این تعاریف الگوریتم‌های اولویت پویای بدون محدودیت یک حالت کلی از الگوریتم‌های اولویت پویای سطح نخ هستند و الگوریتم‌های اولویت پویای سطح نخ نیز یک حالت کلی از الگوریتم‌های اولویت ثابت می‌باشند.
الگوریتم‌های WCET 98 محور :
یکی از مهم‌ترین مشخصه‌هایی که برای وظایف بی‌درنگ مطرح شده، WCET یا بدترین حالت زمان اجرای وظیفه می‌باشد. این ویژگی برای تقریبا بیشتر آزمون‌های تجزیه و تحلیل قابلیت زمانبندی99 شناخته‌شده ، اساسی است(تعیین پیشبینی این‌که یک الگوریتم زمانبندی، قادر به زمانبندی کردن وظیفه روی زمینه داده‌شده تحت بدترین مفروضات ممکن است یا نه). این پارامتر ممکن است در زمان اجرا توسط الگوریتم برای گرفتن تصمیمات زمانبندی موردنیاز باشد یا ممکن است نباشد.
در این رابطه ما می‌توانیم الگوریتم‌هایی که WCET محور هستند ( مانند الگوریتم LLF ) را از الگوریتم‌هایی که WCET محور نیستند ( مانند الگوریتم RMS و EDF ) را از هم تمییز دهیم. این تفاوت معمولا هنگامی که وظایف از تخمین بدترین حالت زمان اجرایشان منحرف می‌شوند، دلالت قوی بر رفتار الگوریتم‌های زمانبندی دارد.

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

3-2 الگوريتم‌های زمانبندی بی‌درنگ تک پردازنده
یکی از معروفترین الگوریتم‌های زمانبندی روی یک هسته، الگوریتم EDF است که از نوع الگوریتم‌های اولویت پویا می‌باشد. این روش بطور کلی از توان محاسباتی پردازنده استفاده کرده و زمانبندی را بصورت دینامیک و درصورت فعال شدن هر وظیفه در زمان اجرا انجام میدهد. فرض اولیه برای EDF این ‌است که در هر نقطه از زمان، اولویت یک وظیفه فعال شده ثابت نیست و به زمان بستگی دارد و در زمان فعال شدن وظیفه بعدی ممکن است تغییر یابد. اولویت،طبق سیاست EDF بدین صورت تعریف میشود که وظیفه درحال اجرا باید کمترین زمان باقی مانده تا درخواست بعدی را از بین تمامی وظایف فعال در صف آماده، داشته باشد، به عبارتی اولویت اجرا با وظیفهای است که نزدیکترین سررسید را داشته باشد، یعنی سررسید مطلق کوچکتری داشته باشد]20[ . وظیفهای که بیشترین اولویت (کمترین سررسید) را دارا میباشد زودتر اجرا میشود.
الگوریتم EDF ، از دید کارایی زمانبندی، با توجه به ماهیت پویای آن، دارای عملکرد بهتری نسبت به الگوریتم‌‌های اولویت ایستا می‌باشد. مثالی از این نوع الگوریتم در شکل 3-2 نشان داده‌شده است]21[ .
بهره وری
سررسيد
WCET
دوره تناوب
وظيفه
0.5
10
5
10
T1
0.4
15
6
15
T2

شکل 3-2 مثالی از کاربرد زمانبندی تک هسته‌ای با استفاده از الگوریتم EDF ]21[
شکل 5شکل 3-2 مثالی از کاربرد زمانبندی تک هسته‌ای با استفاده از الگوریتم EDF [21]
در یک حالت خاص از سیستم‌های تک‌پردازنده، EDF یک الگوریتم زمانبندی بهینه محسوب می‌شود. در واقع الگوریتم EDF یک الگوریتم بهینه برای زمانبندی وظایف تناوبی انحصاری می‌باشد. در حالتی که بهره‌وری یک وظیفه به صورت نسبت WCET بر دوره تناوب وظیفه تعریف می‌شود، EDF می‌تواند برای حالتی که مجموع بهره‌وری همه وظایف کمتر از یک باشد، ملاقات همه سررسیدهای وظایف را تضمین کند]22[ . در یک حالت عام‌تر که دارای وظایف پراکنده با سررسید غیر ضمنی می‌باشد، یک مجموعه وظیفه، قابل زمانبندی می‌باشد اگر( اما نه ضرورتا تنها اگر) ظرفیت100 آن کوچک‌تر یا مساوی یک باشد (≤1 Δ ) ]21[ .
میزان بهینه‌بودن EDF می‌تواند با استفاده از روش مبادله برشی101 ، که بر اساس این اصل است که هر زمانبندی معتبر برای هر مجموعه وظیفه را می‌توان به یک زمانبندی EDF معتبر تبدیل نمود، بهبود یابد:
“U=” ∑_”i=1″ ^”N” ▒(“C” _”i” ” ” )/(“T” “” _”i” ” ” ) ” ≤” “U” _”EDF” “=1 Δ=” ∑_”i=1″ ^”N” ▒(“C” _”i” ” “

پایان نامه
Previous Entries پایان نامه رایگان درمورد الگوریتم زمانبندی Next Entries پایان نامه رایگان درمورد الگوریتم زمانبندی، اشتراک منابع، عدم تقارن