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

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

۲-۴ سررسید
یک محیط بی‌درنگ احتیاجات زمانی سختی را تحمیل میکند که وظیفه را مجبور به اجرا‌شدن به موقع و با موفقیت می‌کند. این احتیاجات از طریق اختصاص یک سررسید به هر وظیفه تعریف می‌شود. سررسید یکی از مهم‌ترین مشخصه‌ های یک وظیفه بی‌درنگ است. سررسید D_i از یک وظیفه τ_i ، زمانی را مشخص می‌کند که وظیفه باید تا آن لحظه اجرایش به پایان برسد. بنابراین D_i سررسید یک وظیفه است که رفتار بی‌درنگ آن وظیفه را معین می‌کند.سررسیدها از دو نوع هستند:
سررسید متناظر^[۵۷] :
سررسید متناظر یک وظیفه به عبارتی بیشترین تاخیر قابل قبول برای پردازش و اجرای یک وظیفه است، یعنی مدت زمانی که یک وظیفه پس از شروع اجرای آن فرصت دارد تا اجرا شود.
سررسید مطلق^[۵۸] :
سررسید مطلق یک وظیفه لحظه‌ای است که وظیفه باید تا آن زمان اجرایش تمام شود. سررسید مطلق را با d_i نشان می‌دهیم و به صورت d_i =r_i+D_i تعریف می‌شود که در آن r_i زمان آزاد‌شدن وظیفه و D_i سررسید متناظر آن وظیفه می‌باشد.
مقایسه سررسید مطلق با سررسید متناظر را در شکل ۲-۳ مشاهده می‌کنید ]۱۰[ .
شکل ۲-۳ سررسید متناظر و سررسید مطلق یک وظیفه ]۱۰[
شکل ۳شکل ۲-۳ سررسید متناظر و سررسید مطلق یک وظیفه [۱۰]
همچنین سررسید یک وظیفه می‌تواند تابعی از دوره‌تناوب آن باشد ]۱۱[ . سه نوع مختلف دیگر از سررسیدها با توجه به وابستگی بین سررسید و دوره تناوب وجود دارند که عبارت انداز:
سررسید ضمنی^[۵۹] :
وظیفه‌ای دارای سررسید ضمنی است هرگاه سررسید متناظر آن با دوره تناوب آن برابر باشد. یک وظیفه τ_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 وظیفه بی‌درنگ و همچنین مشخصه‌ های وابسته به آن‌ ها که در قسمت ۲-۳-۱ توضیح داده‌شد، زمانبندی کردن، که برای هرلحظه مشخص می‌کند که کدام وظیفه در بین آن‌هایی که آزاد شده‌اند، باید اجرا شود. یک زمانبند تحت شرایط زیر باید مطمئن باشد که همه وظایف، به‌موقع اجراشده و تمام شوند:
الف) یک وظیفه قبل از زمان ورودش زمانبندی نشده‌است.
ب) اولویت درمیان وظایف یکسان رعایت شده‌است.
۲-۷-۱ تعاریف مربوط به مبحث زمانبندی
زمانبند^[۷۱] :
یک زمانبند، یک بخش از سیستم عامل است که هدف اصلی آن این است که تعیین کند، کدام وظیفه، روی کدام هسته و در چه زمانی اجرا شود، حتی اگر هیچ سیستم عاملی هم وجود نداشته باشد ]۱۵[ . به عنوان مثال در یک سیستم بسیار ساده مانند لباس‌شویی، یک سیاست زمانبندی موردنیاز است تا به سیستم اجازه دهد که بیش از یک وظیفه را دربر داشته باشد.
قابلیت زمانبندی^[۷۲] :
یک مجموعه وظیفه τ، قابلیت زمانبندی HRT^[73] توسط الگوریتم A را دارد هرگاه A همیشه یک زمانبندی امکان‌پذیر را برای τ تولید کند. (هیچ‌کدام از وظایف با الگوریتم A ، سررسیدشان را ازدست ندهند)
یک مجموعه وظیفه τ، قابلیت زمانبندی ^[۷۴]SRT توسط الگوریتم A را دارد، هرگاه حداکثر تاخیر اجرای وظایف آن کران‌دار^[۷۵] باشد.
شدنی‌بودن^[۷۶] :
یک مجموعه وظیفه τ روی یک بستر، امکان‌پذیر و شدنی است اگر یک الگوریتم زمانبندی‌ وجود داشته باشد که تحت آن همه وظایف τ در سررسید خود به اتمام برسند.
کلاس شدنی‌بودن^[۷۷] :
یک مجموعه وظیفه τ تحت کلاس C از الگوریتم زمانبندی، شدنی است اگر بتواند توسط هر الگوریتم زمانبندی دیگری زمانبندی شود، به طوریکه آن الگوریتم نیز خود تحت کلاس C باشد.
بهینگی^[۷۸] :
الگوریتم A را با توجه به کلاس C بهینه گویند، هرگاه AϵC باشد و به طور صحیحی همه وظایف سیستم که تحت کلاس C شدنی هستند را زمانبندی کند. اگر کلاس C تعیین نشده‌باشد، آنگاه معمولا فرض بر شامل بودن همه‌ی الگوریتم‌های زمانبندی ممکن می‌شود.
کارایی زمانبندی:
چیزی که مکررا در آثار و نوشته‌های مختلف استفاده‌شده، بیان می‌کند که الگوریتم A₁ کارایی زمانبندی بهتری نسبت به الگوریتم A₂ دارد، این به معنای توانایی الگوریتم A₁ در زمانبندی‌کردن امکان‌پذیر مجموعه وظایف با عامل‌های بهره‌وری بالاتری نسبت به الگوریتم A₂ است.
۲-۸ سیستم های چندهسته‌ای
در طول سال‌های اخیر، محققان و طراحان سیستم‌های بی‌درنگ، مدل‌ها، نظریه‌ها و نرم‌افزار‌های زیادی را برای پوشش مسئله موازی سازی بین وظیفه‌ای^[۷۹] توسعه داده‌اند، که در آن بار کاری شامل مجموعه‌ای از وظایف مستقل متوالی است و در نتیجه افزایش تعداد هسته‌های پردازنده به سیستم ما اجازه می‌دهد تا کارهای بیشتری را اجرا کند ]۱۶[.
واژه چندپردازنده، ما را یادآور سیستم‌های رایانه‌ای می‌کند که قابلیت انجام محاسبات بیشتر از یک واحد محاسباتی برای اجرای پردازه‌های نرم‌افزاری را دارد. چندپردازنده‌ها مفهوم جدیدی نیستند، در واقع آن‌ ها از اوایل ده شصت در صنعت شناخته شده اند. اما سیستم‌های چندپردازنده در اوایل، مبتنی بر تراشه‌های فیزیکی چندگانه بودند که به یک گذرگاه^[۸۰] اتصال ویژه احتیاج داشتند، در نتیجه بسیار گران‌قیمت و پیچیده بودند. آخرین نسل از پردازنده‌های چندهسته‌ای برای رایانه‌های رومیزی^[۸۱] و سیستم‌های سرویس‌دهنده و سیستم‌های چندپردازنده روی تراشه (MPSoC)^[82] در سیستم‌های تعبیه شده، دچار تغییرات زیادی شده‌اند به طوری که واژه چندپردازنده را به یک واقعیت روزمره تبدیل کرده‌اند ]۱۷[ .
امروزه، چندپردازشی به وضوح به عنوان روش اصلی برای بهره‌گیری از سطح مجتمع‌سازی^[۸۳] بالای سیلیکون، درنظر گرفته‌شده است. این موضوع برای تقریبا هر مقیاس محاسباتی، از سیستم‌های چندهسته‌ای تعبیه‌شده و کم‌مصرف مانند تراشه‌های NVIDIA مشهور و ^[۸۴] TI-OMAP به کار رفته در لوازم الکترونیکی مصرفی، گرفته تا خوشه‌های محاسباتی^[۸۵] باکارایی بالا، مانند پردازنده ۴۸ هسته‌ای Intel SCC و یا پردازنده‌های گرافیکی قدرتمند خانواده NVIDIA Tesla (GPGPUs)^[86] ، به یک مدل مرجع تبدیل شده است. با این حال، در حالی که تراشه‌های چندهسته‌ای و چند پردازشی به طور کلی به عنوان استانداردی برای صنعت الکترونیک در سال‌های آینده تصدیق شده‌ هستند، اما هنوز معماری داخلی برخی پردازنده‌های چندهسته‌ای، رتبه‌دهی نشده‌اند و در حال حاضر طیف گسترده‌ای از گرایش‌های مختلف معماری این سیستم‌ها، بحث‌های فعال مطرح‌شده در هردو جامعه صنعتی و علمی هستند ]۱۸[ .