پایان نامه رایگان درمورد الگوریتم زمانبندی

سررسید وظیفه
Ti : دوره تناوب وظایف تناوبی
Pi : اولویت51 وظایف غیرتناوبی
همچنین زمان آزاد‌شدن52 یک وظیفه با علامت ri نشان داده‌ می‌شود و عبارت‌انداز زمانی که وظیفه جدید از وضعیت ایجادشدن و یا از حالت مسدود خارج شده و وارد صف آماده53 می‌شود. وظایف تناوبی بر اساس زمان رسیدن خود شامل دو نوع هستند. یک سری وظایفی که اصطلاحاً همگام54 نامیده می‌شوند که به این معنی است که همه وظایف دارای زمان ورود یکسان هستند. دسته دیگر از وظایف تناوبی که ناهمگام55 نامیده می‌شوند، وظایفی هستند که زمان ورود مختلفی دارند و هیچکدام از وظایف آن دارای زمان ورود مشابهی نیستند]8[ .

2-3-2 دسته‌بندی وظايف بی‌درنگ
همه وظایف بی‌درنگ بر اساس فرکانس آزاد‌شدن آنها به سه دسته مختلف تناوبی، غیرتناوبی و پراکنده تقسیم‌بندی می‌شوند که بصورت زیر تعریف می‌شوند ]9[ .
وظايف تناوبی:
یک وظیفه τi ،تناوبی نامیده می‌شود، هرگاه به‌صورت پیوسته و با یک نرخ ثابت تکرار شود، که این نرخ ثابت دوره تناوب ( Ti ) نامیده می‌شود، به طوری که فاصله بین آزاد شدن دو وظیفه همواره برابر است با ri j+1 – ri j = Ti
وظايف پراکنده56 :
برخلاف وظایف تناوبی، وظایف پراکنده که گاهی اوقات وظایف رویداد‌ محور و یا واکنش‌پذیر نیز نامیده می‌شوند، وظایفی هستند که در پاسخ به یک رویداد خارجی اجرا می‌شوند. در این حالت دوره تناوب وظایف پراکنده، حداقل زمان بین وقوع رویدادهایی که باعث آزادشدن وظیفه متناظر می‌شود را تعیین می‌کند. بنابراین فاصله بین آزادشدن هر دو وظیفه، نتیجه برآورده شدن شرط ri j+1 – ri j ≥ Ti است. از این رو یک وظیفه تناوبی در واقع یک حالت خاص از یک وظیفه پراکنده است.
وظايف غيرتناوبی:
در هر یک از دو حالت فوق ممکن است این نکته بیان شود که هردو حالت هیچ ارزش خاصی برای اجراشدن وظایف بلافاصله بعداز آزاد شدن آن‌ها و البته قبل از سررسیدشان قائل نشده‌اند. اما این نکته در وظایف غیرتناوبی صدق نمی‌کند. همان‌طور که از نام آن پیداست، وظایف غیرتناوبی فاقد مفاهیم تناوب (و گاهی سررسید) هستند، بنابراین این نوع وظایف می‌توانند در هر لحظه دلخواه وارد شوند. معمولا این نوع از وظایف برای رویدادهای بی‌درنگ نرم کاربرد دارند که معنای آن کمی متفاوت است؛ هدف آن‌ها این است که در کوتاه‌ترین زمان ممکن به درخواست‌های رویدادهای خارجی پاسخ داده‌شود، در عین حال که قابلیت حضور وظایف تناوبی و پراکنده را در سیستم دارد.

2-4 سررسيد
یک محیط بی‌درنگ احتیاجات زمانی سختی را تحمیل میکند که وظیفه را مجبور به اجرا‌شدن به موقع و با موفقیت می‌کند. این احتیاجات از طریق اختصاص یک سررسید به هر وظیفه تعریف می‌شود. سررسید یکی از مهم‌ترین مشخصه‌های یک وظیفه بی‌درنگ است. سررسید Di از یک وظیفه τi ، زمانی را مشخص می‌کند که وظیفه باید تا آن لحظه اجرایش به پایان برسد. بنابراین Di سررسید یک وظیفه است که رفتار بی‌درنگ آن وظیفه را معین می‌کند.سررسیدها از دو نوع هستند:
سررسيد متناظر57 :
سررسید متناظر یک وظیفه به عبارتی بیشترین تاخیر قابل قبول برای پردازش و اجرای یک وظیفه است، یعنی مدت زمانی که یک وظیفه پس از شروع اجرای آن فرصت دارد تا اجرا شود.
سررسيد مطلق58 :
سررسید مطلق یک وظیفه لحظه‌ای است که وظیفه باید تا آن زمان اجرایش تمام شود. سررسید مطلق را با di نشان می‌دهیم و به صورت di =ri+Di تعریف می‌شود که در آن ri زمان آزاد‌شدن وظیفه و Di سررسید متناظر آن وظیفه می‌باشد.
مقایسه سررسید مطلق با سررسید متناظر را در شکل 2-3 مشاهده می‌کنید ]10[ .

شکل 2-3 سررسید متناظر و سررسید مطلق یک وظیفه ]10[
شکل 3شکل 2-3 سررسید متناظر و سررسید مطلق یک وظیفه [10]
همچنین سررسید یک وظیفه می‌تواند تابعی از دوره‌تناوب آن باشد ]11[ . سه نوع مختلف دیگر از سررسیدها با توجه به وابستگی بین سررسید و دوره تناوب وجود دارند که عبارت انداز:
سررسيد ضمنی59 :
وظیفه‌ای دارای سررسید ضمنی است هرگاه سررسید متناظر آن با دوره تناوب آن برابر باشد. یک وظیفه τi با دوره تناوب Ti و سررسید Di ، یک سررسید ضمنی است هرگاه Ti= Di
سررسيد محدود60 :
وظیفه‌ای دارای سررسید محدود است هرگاه سررسید متناظر آن کوچکتر یا مساوی دوره تناوب آن باشد. یک وظیفه τi با دوره تناوب Ti و سررسید Di ، یک سررسید محدود است هرگاه Ti ≥ Di
سررسيد دلخواه61 :
در این حالت هیچ قید و بندی برای سررسید یک وظیفه وجود ندارد و سررسید آن می‌تواند کوچک‌تر، مساوی و یا بزرگتر از دوره تناوب آن وظیفه باشد، یعنی Ti ≥ Diیا Ti Di

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

2-6 منابع63
برخلاف یک هسته، یک منبع دستورات یک وظیفه را اجرا نمی‌کند. به هر حال برای یک وظیفه، ضروری است که دارای حرکت باشد تا جریانی را بوجود بیاورد. نمونه‌هایی از منابع عبارت انداز حافظه، سمافور64، حسگر65، محرک66و…
هنگامی که دو یا چند وظیفه به یک منبع دسترسی داشته باشند، این منبع، منبع اشتراکی67 نامیده‌ می‌شود و نیازمند توجه بخصوصی است. فرض کنید یک وظیفه نتیجه محاسباتش را روی یک محل از حافظه بنویسد و سپس توسط وظیفه دیگری قبضه بشود که این وظیفه، روی همان محل حافظه بازنویسی کند. حال وقتی که اولین وظیفه دوباره اجرایش از سر گرفته می‌شود، به همان بخش از حافظه مراجعه کرده تا از نتیجه محاسبات قبلی‌اش استفاده کند ولی مقادیر نادرستی را از حافظه بازخوانی می‌کند. این چنین شرایطی، حالت‌ نامعین68 نامیده می‌شود ]12[ .
بسته به حافظه زبان برنامه‌نویسی و یا معماری آن، اثرات ناشی از حالت نامعین، ممکن است کاملا نامشخص باشد. به همین دلیل در بیشتر موارد تحت هرشرایطی سعی می‌شود که از این حالت اجتناب شود. به همین دلیل، منابع اشتراکی توسط ساختارهایی مانند سمافورها محافظت می‌شوند و روی سیاست زمانبندی تاثیر می‌گذارند. در مثال بالا اگر وظیفه، حافظه‌اش را قفل کرده‌بود و یا یک سمافوری داشت تا از محل حافظه‌اش محافظت کند، دیگر زمانبند نمی‌توانست آن را قبضه کند و درنتیجه حالت نامعین بوجود نمی‌آمد. یک منبع اشتراکی همچنین می‌تواند شامل واحدهای مختلفی باشد، مانند یک واحد چاپگر که دارای چندین دستگاه چاپگر می‌باشد. در حالت‌هایی که تعداد وظایف از تعداد منابع کمتر است، دسترسی به منابع اشتراکی به این صورت مدیریت می‌شود که اطمینان حاصل شود که هرگز دو وظیفه به صورت همزمان از یک منبع استفاده نکنند]12[ .

2-7 مفاهيم زمانبندی
یکی از هدف‌های اصلی سیستم‌های بی‌درنگ، زمانبندی است که از دو جنبه متفاوت می‌توان به آن نگاه کرد، یکی جنبه الگوریتمی و دیگری جنبه نرم‌افزار می‌باشد. دید الگوریتمی زمانبندی عبارت‌انداز تشخیص یک زمانبندی امکان‌پذیر69 از طریق یک الگوریتم زمانبندی مناسب. اما زمانبندی از دید نرم‌افزار عبارت‌انداز اعمال تصمیمات محکم سیاست زمانبندی روی سیستم‌عامل و قرار دادن وظایف به حالت اجرا در زمان مناسب توسط یک زمانبند]13[ .
یک مفهوم کلیدی که توسط زمانبند معرفی شده، بحث انحصاری بودن می‌باشد. قبضه کردن (به انحصار درآوردن) زمانی اتفاق می‌افتد که یک وظیفه درحال اجرا، توسط وقوع یک رخدادی، اجرایش متوقف و پردازنده به وظیفه دیگری اختصاص داده شود. به این عملیات اصطلاحاً سوئیچ‌کردن محتوای پردازنده70 می‌گویند که عملیاتی زمانبر برای پردازنده محسوب می‌شود]14[ . از دید الگوریتمی، مسئله زمانبندی شامل موارد زیر می‌باشد:
گرفتن یک مجموعه وظیفه τ شامل n وظیفه بی‌درنگ و همچنین مشخصه‌های وابسته به آن‌ها که در قسمت 2-3-1 توضیح داده‌شد، زمانبندی کردن، که برای هرلحظه مشخص می‌کند که کدام وظیفه در بین آن‌هایی که آزاد شده‌اند، باید اجرا شود. یک زمانبند تحت شرایط زیر باید مطمئن باشد که همه وظایف، به‌موقع اجراشده و تمام شوند:
الف) یک وظیفه قبل از زمان ورودش زمانبندی نشده‌است.
ب) اولویت درمیان وظایف یکسان رعایت شده‌است.

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

زمانبند71 :
یک زمانبند، یک بخش از سیستم عامل است که هدف اصلی آن این است که تعیین کند، کدام وظیفه، روی کدام هسته و در چه زمانی اجرا شود، حتی اگر هیچ سیستم عاملی هم وجود نداشته باشد ]15[ . به عنوان مثال در یک سیستم بسیار ساده مانند لباس‌شویی، یک سیاست زمانبندی موردنیاز است تا به سیستم اجازه دهد که بیش از یک وظیفه را دربر داشته باشد.
قابليت زمانبندی72 :
یک مجموعه وظیفه τ، قابلیت زمانبندی HRT73 توسط الگوریتم A را دارد هرگاه A همیشه یک زمانبندی امکان‌پذیر را برای τ تولید کند. (هیچ‌کدام از وظایف با الگوریتم A ، سررسیدشان را ازدست ندهند)
یک مجموعه وظیفه τ، قابلیت زمانبندی 74SRT توسط الگوریتم A را دارد، هرگاه حداکثر تاخیر اجرای وظایف آن کران‌دار75 باشد.
شدنی‌بودن76 :
یک مجموعه وظیفه τ روی یک بستر، امکان‌پذیر و شدنی است اگر یک الگوریتم زمانبندی‌ وجود داشته باشد که تحت آن همه وظایف τ در سررسید خود به اتمام برسند.
کلاس شدنی‌بودن77 :
یک مجموعه وظیفه τ تحت کلاس C از الگوریتم زمانبندی، شدنی است اگر بتواند توسط هر الگوریتم زمانبندی دیگری زمانبندی شود، به طوریکه آن الگوریتم نیز خود تحت کلاس C باشد.

بهينگی78 :
الگوریتم A را با توجه به کلاس C بهینه گویند، هرگاه AϵC باشد و به طور صحیحی همه وظایف سیستم که تحت کلاس C شدنی هستند را زمانبندی کند. اگر کلاس C تعیین نشده‌باشد، آنگاه معمولا فرض بر شامل بودن همه‌ی الگوریتم‌های زمانبندی ممکن می‌شود.
کارايی زمانبندی:
چیزی که مکررا در آثار و نوشته‌های مختلف استفاده‌شده، بیان می‌کند که الگوریتم A1 کارایی زمانبندی بهتری نسبت به الگوریتم A2 دارد، این به معنای توانایی الگوریتم A1 در زمانبندی‌کردن امکان‌پذیر مجموعه وظایف با عامل‌های بهره‌وری بالاتری نسبت به الگوریتم A2 است.

2-8 سيستم های چندهسته‌ای
در طول سال‌های اخیر، محققان و طراحان سیستم‌های بی‌درنگ، مدل‌ها، نظریه‌ها و نرم‌افزار‌های زیادی را برای پوشش مسئله موازی سازی بین وظیفه‌ای79 توسعه داده‌اند، که در آن بار کاری شامل مجموعه‌ای از وظایف مستقل متوالی است و در نتیجه افزایش تعداد هسته‌های پردازنده به سیستم ما اجازه می‌دهد تا کارهای بیشتری را اجرا کند ]16[.
واژه چندپردازنده، ما را یادآور