انجام پروژه متلب بهینه سازی زمان بندی وظایف و منابع

برای انجام پروژه متلب بهینه سازی زمان بندی وظایف و منابع با بهترین کیفیت و زمان و هزینه با شماره 09190090258 در ارتباط باشید.

مساله به هنگام‌بودن، یکی از کلیدی‌ترین اصل در طراحی سیستم‌های بی‌درنگ می‌باشد. مسئله به‌هنگام‌بودن، دو جنبه کمی دارد؛ یکی اینکه سیستم باید در زمان مشخص و تعیین‌شده، وظیفه موردنظر را اجرا کند و دیگری اینکه باید علاوه‌ بر به‌موقع بودن، درستی و مفید بودن اجرا را نیز درنظر بگیرد. یعنی باید رابطه بین زمانی که نتایج تولید می‌شوند و مفید بودن این نتایج تولید‌شده را نیز درنظر گرفت. این رابطه می‌تواند بوسیله توابع ریاضی نشان داده‌شود.

بهره‌وری یک وظیفه معمولی ( غیربی‌درنگ) کاملا مستقل از زمان است. نمودار تابع بهره‌وری نسبت به زمان در یک سیستم با وظیفه غیربی‌درنگ را در  مشاهده می‌کنید. بهره‌وری یک وظیفه بی‌درنگ نرم تابعی است که بعد از فرارسیدن سررسید مربوطه، به تدریج کاهش یافته تا به صفر می‌رسد.(شکل 2-1- ب) نمونه‌هایی از وظایف بی‌درنگ نرم می‌توان به  تلویزیون دیجیتال، کنفرانس ویدئویی و بسیاری از سیستم‌های چندرسانه‌ای دیگر اشاره کرد. اما در مورد یک وظیفه بی‌درنگ سخت، دو مورد باید قابل تشخیص باشد؛ اولین مورد که معمول‌تر است، این است که با فرارسیدن سررسید مربوطه، تابع بهره‌وری بلافاصله مستقیم به صفر سقوط کند. (شکل 2-1- ج) و مورد دوم که بسیار بدتر از حالت اول است این است که تابع بهره‌وری بعداز فرارسیدن سررسید، به منفی بی‌نهایت (∞-) سقوط کند (شکل 2-1- د ). از نمونه‌های این حالت می‌توان به سیستم‌های نظامی اشاره کرد که در آن عواقب یک عملی که درست و بموقع انجام نشود، می‌تواند حتی بدتر از انجام ندادن آن عمل باشد.

 

وظيفه

کنترل نرم‌افزاری سخت‌افزار یک سیستم بی‌درنگ، نقش مهمی در بهبود عملکرد سیستم دارد. به عنوان مثال در یک ماشین‌لباس‌شویی، کنترل قسمت‌های مکانیکی و نمایش زمان باقی‌مانده برنامه شستشو و… نمونه‌ کارهایی هستند که توسط یک سیستم تعبیه‌شده موجود در لباس‌شویی اجرا می‌شوند. به منظور فشرده سازی کارهای مختلف و بهبود قابلیت استفاده مجدد و نگهداشت‌پذیری، کارها از زیربخش‌هایی تشکیل شده‌اند که به هر کدام از این زیربخش‌ها، وظیفه گفته‌می‌شود.

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

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

مدل وظيفه بی‌درنگ

 

یک سیستم بی‌درنگ می‌تواند شامل n وظیفه τ _i باشد و مجموعه وظایف آن را S می‌نامیم که عبارت‌اند از مجموعه همه وظایف موجود در سیستم که S={ τ ₁ ,τ _{2 ,} τ _{3 ,} …, τ _n } . هر وظیفه تعدادی مشخصه قراردادی دارد که توسط این مشخصه‌ها به سیستم‌عامل و برنامه‌نویس معرفی می‌شود.

چهار مشخصه مهم و اصلی یک وظیفه عبارت‌اند از:

C _i : بدترین حالت زمان اجرای وظیفه

D _i : سررسید وظیفه

T _i : دوره تناوب وظایف تناوبی

P _i : اولویت وظایف غیرتناوبی

همچنین زمان آزاد‌شدن یک وظیفه با علامت r _i نشان داده‌ می‌شود و عبارت‌انداز زمانی که وظیفه جدید از وضعیت ایجادشدن و یا از حالت مسدود خارج شده و وارد صف آماده می‌شود. وظایف تناوبی بر اساس زمان رسیدن خود شامل دو نوع هستند. یک سری وظایفی که اصطلاحاً همگام نامیده می‌شوند که به این معنی است که همه وظایف دارای زمان ورود یکسان هستند. دسته دیگر از وظایف تناوبی که ناهمگام نامیده می‌شوند، وظایفی هستند که زمان ورود مختلفی دارند و هیچکدام از وظایف آن دارای زمان ورود مشابهی نیستند.

دسته‌بندی وظايف بی‌درنگ

 

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

وظايف تناوبی:

یک وظیفه τ _i ،تناوبی نامیده می‌شود، هرگاه به‌صورت پیوسته و با یک نرخ ثابت تکرار شود، که این نرخ ثابت دوره تناوب ( T _i ) نامیده می‌شود، به طوری که فاصله بین آزاد شدن دو وظیفه همواره برابر است با  r _i ^j+1 – r _i ^j = T _i

وظايف پراکنده :

برخلاف وظایف تناوبی، وظایف پراکنده که گاهی اوقات وظایف رویداد‌ محور و یا واکنش‌پذیر نیز نامیده می‌شوند، وظایفی هستند که در پاسخ به یک رویداد خارجی اجرا می‌شوند. در این حالت دوره تناوب وظایف پراکنده، حداقل زمان بین وقوع رویدادهایی که باعث آزادشدن وظیفه متناظر می‌شود را تعیین می‌کند. بنابراین فاصله بین آزادشدن هر دو وظیفه، نتیجه برآورده شدن شرط r _i ^j+1 – r _i ^j ≥ T _i است. از این رو یک وظیفه تناوبی در واقع یک حالت خاص از یک وظیفه پراکنده است.

وظايف غيرتناوبی:

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

سررسيد

 

یک محیط بی‌درنگ احتیاجات زمانی سختی را تحمیل میکند که وظیفه را مجبور به اجرا‌شدن به موقع و با موفقیت می‌کند. این احتیاجات از طریق اختصاص یک سررسید به هر وظیفه تعریف می‌شود. سررسید یکی از مهم‌ترین مشخصه‌های یک وظیفه بی‌درنگ است. سررسید D _i از یک وظیفه τ _i ، زمانی را مشخص می‌کند که وظیفه باید تا آن لحظه اجرایش به پایان برسد. بنابراین D _i سررسید یک وظیفه است که رفتار بی‌درنگ آن وظیفه را معین می‌کند.سررسیدها از دو نوع هستند:

سررسيد متناظر :

سررسید متناظر یک وظیفه به عبارتی بیشترین تاخیر قابل قبول برای پردازش و اجرای یک وظیفه است، یعنی مدت زمانی که یک وظیفه پس از شروع اجرای آن فرصت دارد تا اجرا شود.

سررسيد مطلق :

سررسید مطلق یک وظیفه لحظه‌ای است که وظیفه باید تا آن زمان اجرایش تمام شود. سررسید مطلق را با d _i نشان می‌دهیم و به صورت d _i =r _i +D _i تعریف می‌شود که در آن r _i زمان آزاد‌شدن وظیفه و D _i سررسید متناظر آن وظیفه می‌باشد.

مقایسه سررسید مطلق با سررسید متناظر را در شکل 2-3 مشاهده می‌کنید .

 

 

سررسيد ضمنی :

وظیفه‌ای دارای سررسید ضمنی است هرگاه سررسید متناظر آن با دوره تناوب آن برابر باشد. یک وظیفه τ _i با دوره تناوب T _i و سررسید D _i ، یک سررسید ضمنی است هرگاه T _i = D _i

سررسيد محدود :

وظیفه‌ای دارای سررسید محدود است هرگاه سررسید متناظر آن کوچکتر یا مساوی دوره تناوب آن باشد. یک وظیفه τ _i با دوره تناوب T _i و سررسید D _i ، یک سررسید محدود است هرگاه T _i ≥    D _i

سررسيد دلخواه :

در این حالت هیچ قید و بندی برای سررسید یک وظیفه وجود ندارد و سررسید آن می‌تواند کوچک‌تر، مساوی و یا بزرگتر از دوره تناوب آن وظیفه باشد، یعنی T _i ≥    D _i یا T _i <    D _i

هسته پردازنده

 

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

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

منابع

 

برخلاف یک هسته، یک منبع دستورات یک وظیفه را اجرا نمی‌کند. به هر حال برای یک وظیفه، ضروری است که دارای حرکت باشد تا جریانی را بوجود بیاورد. نمونه‌هایی از منابع عبارت انداز حافظه و…

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

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

مفاهيم زمانبندی

 

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

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

گرفتن یک مجموعه وظیفه τ شامل n وظیفه بی‌درنگ و همچنین مشخصه‌های وابسته به آن‌ها که در قسمت 2-3-1 توضیح داده‌شد، زمانبندی کردن، که برای هرلحظه مشخص می‌کند که کدام وظیفه در بین آن‌هایی که آزاد شده‌اند، باید اجرا شود. یک زمانبند تحت شرایط زیر باید مطمئن باشد که همه وظایف، به‌موقع اجراشده و تمام شوند:

الف) یک وظیفه قبل از زمان ورودش زمانبندی نشده‌است.

ب) اولویت درمیان وظایف یکسان رعایت شده‌است.

 

تعاريف مربوط به مبحث زمانبندی

 

زمانبند :

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

قابليت زمانبندی :

یک مجموعه وظیفه τ، قابلیت زمانبندی HRT توسط الگوریتم A را دارد هرگاه A همیشه یک زمانبندی امکان‌پذیر را برای τ تولید کند. (هیچ‌کدام از وظایف با الگوریتم A ، سررسیدشان را ازدست ندهند)

یک مجموعه وظیفه τ، قابلیت زمانبندی SRT توسط الگوریتم A را دارد، هرگاه حداکثر تاخیر اجرای وظایف آن کران‌دارباشد.

شدنی‌بودن:

یک مجموعه وظیفه τ روی یک بستر، امکان‌پذیر و شدنی است اگر یک الگوریتم زمانبندی‌ وجود داشته باشد که تحت آن همه وظایف τ در سررسید خود به اتمام برسند.

کلاس شدنی‌بودن:

یک مجموعه وظیفه τ تحت کلاس C از الگوریتم زمانبندی، شدنی است اگر بتواند توسط هر الگوریتم زمانبندی دیگری زمانبندی شود، به طوریکه آن الگوریتم نیز خود تحت کلاس C باشد.

 

بهينگی:

الگوریتم A را با توجه به کلاس C بهینه گویند، هرگاه AϵC باشد و به طور صحیحی همه وظایف سیستم که تحت کلاس C شدنی هستند را زمانبندی کند. اگر کلاس C تعیین نشده‌باشد، آنگاه معمولا فرض بر شامل بودن همه‌ی الگوریتم‌های زمانبندی ممکن می‌شود.

کارايی زمانبندی:

چیزی که مکررا در آثار و نوشته‌های مختلف استفاده‌شده، بیان می‌کند که الگوریتم A ₁ کارایی زمانبندی بهتری نسبت به الگوریتم A ₂ دارد، این به معنای توانایی الگوریتم A ₁ در زمانبندی‌کردن امکان‌پذیر مجموعه وظایف با عامل‌های بهره‌وری بالاتری نسبت به الگوریتم A ₂ است.

سيستم های چندهسته‌ای

 

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

واژه چندپردازنده، ما را یادآور  سیستم‌های رایانه‌ای می‌کند که  قابلیت انجام محاسبات بیشتر از یک واحد محاسباتی  برای اجرای پردازه‌های نرم‌افزاری را دارد. چندپردازنده‌ها مفهوم جدیدی نیستند، در واقع آن‌ها از اوایل ده شصت در صنعت شناخته شده اند. اما سیستم‌های چندپردازنده در اوایل، مبتنی بر تراشه‌های فیزیکی چندگانه بودند که به یک گذرگاه اتصال ویژه احتیاج داشتند، در نتیجه بسیار گران‌قیمت و پیچیده بودند. آخرین نسل از پردازنده‌های چندهسته‌ای برای رایانه‌های رومیزیو سیستم‌های سرویس‌دهنده و سیستم‌های چندپردازنده روی تراشه (MPSoC) در سیستم‌های تعبیه شده، دچار تغییرات زیادی شده‌اند به طوری که واژه چندپردازنده را به یک واقعیت روزمره تبدیل کرده‌اند.

امروزه، چندپردازشی به وضوح به عنوان روش اصلی برای بهره‌گیری از سطح مجتمع‌سازی بالای سیلیکون، درنظر گرفته‌شده است. این موضوع برای تقریبا هر مقیاس محاسباتی، از سیستم‌های چندهسته‌ای تعبیه‌شده و کم‌مصرف مانند تراشه‌های NVIDIA مشهور و  به کار رفته در لوازم الکترونیکی مصرفی، گرفته تا خوشه‌های محاسباتی باکارایی بالا، مانند پردازنده 48 هسته‌ای Intel SCC و یا پردازنده‌های گرافیکی قدرتمند خانواده NVIDIA Tesla ، به یک مدل مرجع تبدیل شده است. با این  حال، در حالی که تراشه‌های چندهسته‌ای و چند پردازشی به طور کلی به عنوان استانداردی برای صنعت الکترونیک در سال‌های آینده تصدیق شده‌ هستند، اما هنوز معماری داخلی برخی پردازنده‌های چندهسته‌ای، رتبه‌دهی نشده‌اند و در حال حاضر طیف گسترده‌ای از گرایش‌های مختلف معماری این سیستم‌ها، بحث‌های فعال مطرح‌شده در هردو جامعه صنعتی و علمی هستند .

وجود تنوع در سراسر طیف وسیعی از معماری چندهسته‌ای، صرفا یک چالش نیست. در یک سیستم واحد، معماری هسته‌ها می‌تواند متفاوت باشد، همانطور که روند کنونی چنین است و بیشتر به سمت ترکیبی از هسته‌های متفاوت می‌رود. در طراحی برخی سیستم‌ها، هسته‌ها دارای مجموعه دستورالعمل‌های مشترکی هستند ولی مشخصه‌های کارایی آن‌ها باهم متفاوت است.

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

خانه متلب اولین و بهترین سایت در زمینه انجام پروژه های متلب است. در خانه متلب هیچ گونه واسطه ای وجود ندارد و به صورت مستقیم می توانید با مجری در ارتباط باشید.

 

بر روی لینک های زیر کلیک نمایید:

آموزش رایگان متلب دانلود کد متلب گروه تلگرام متلب