پایگاه علمی سعید سان دانلود رایگان مقالات علمی کنفرانس و ژورنال
دانلود ترجمه و آنالیز زمانبندی سیستم های بلادرنگ چند پردازنده‌ای با مکانیزم تحمل‌پذیری خطا
آنالیز مقاله1
Simulation of fault tolerant scheduling on real-time multiprocessor systems using primary backup overloading
- ایده اصلی مقاله
طرح این مقاله این برای تحمل پذیری خطا، روش پشتیبان اصلی (primary/backup) است. طوری این روش را گسترش داده شده که بتواند بر نقاط ضعف آن (مانند عدم آزاد سازی پردازنده ای که نسخه پشتیبان در آن قرار دارد یا عدم توانایی کار با وظایف غیر متناوب) فایق آید. در این روش وظیفه اصلی در یک پردازنده و وظیفه پشتیبان را در پردازنده دیگری قرار داده میشود. این نسخه پشتیبان طوری قرار داده میشود که بتواند با پشتیبان وظایف دیگر، هم پوشانی داشته باشد و این سبب استفاده بهینه از پردازنده‌های موجود میشود.
- مزیت طرح
دو مزیت اصلی این طرح یکی استفاده بهینه از پردازنده‌ها به علت هم پوشانی زمان اجرای نسخه‌های پشتیبان و دیگری آزاد سازی نسخه‌های پشتیبان است به این معنی که وقتی وظیفه ای با موفقیت به پایان برسد نسخه پشتیبان آن حذف میشود و این سبب آزاد شدن فضای اختصاص داده شده به نسخه پشتیبان میشود که میتواند برای زمانبندی وظایف دیگر مورد استفاده قرار گیرد.
نویسندگان ادعا دارند که این روش میتواند 86% خطاهای گذرا را تحمل کند.
Abstract
Time-critical applications require dynamic scheduling with predictable performance. Tasks
corresponding to these applications have deadlines to be met despite the presence of faults. This paper
discusses and implements the combination of a successful fault tolerant algorithm with the EDF algorithm
for multiprocessors running in parallel and executing real-time applications. The algorithm is based on a
popular fault-tolerant technique called primary/backup (PB) fault tolerance. The algorithm has been
extended to include and consider tasks arriving dynamically unlike the PB technique which only
accommodated static tasks. The backup overloading Hengming-Farnam Algorithm implements
mechanisms which have helped in overcoming the limitations of the primary/backup technique. It has
been successfully shown by the simulation results that primary backup overloading increases system
utilization and also increases efficiency.
این فایل ورد (word) ترجمه در 3 صفحه و فایل اصلی لاتین pdf مقاله در 10 صفحه به خدمتتون ارائه میشود.
آنالیز مقاله2
A Novel Fault Tolerant Scheduling Technique In Real-Time Heterogeneous Distributed Systems Using Distributed Recovery Block
1-ایده اصلی مقاله
تحمل پذیری خطا در سیستمهای بلادرنگ توزیع شده به علت وجود محدودیتهای زمانی امری حیاتی و بسیار مهم است. در سیستمهای RTDS (Real-time Distributed systems) تشخیص خطا و ترمیم آن باید بموقع انجام شود زیرا با وجود اینکه خطا رخ داده است، باید خروجی سیستم در زمان مورد نظر آماده باشد.
تکنیک زمانبندی وظایف میتواند برای داشتن تحمل پذیری خطا در سیستمهای بلادرنگ استفاده شود. این روش، به علت داشتن افزونگی کم، روش مناسبی است. تحمل پذیری خطا میتواند با برنامه ریزی کپی‌های وظایف که مازاد بر خود وظایف ایجاد شده اند انجام شود.
این مقاله طرحی برای تحمل پذیری خطا در سیستمهای توزیع شده ناهمگن ارائه کرده است که از تکنیکهای نرم افزاری بر اساس بلاک ترمیم توزیع شده (DRB) استفاده می‌‌کند.
در هر سیستم دو صف در نظر گرفته می شود یکی برای وظایف اصلی و دیگری پشتیبان و یک صف مرکزی نیز وجود دارد که ابتدا وظایف وارد آن میشوند سپس به صورت رندم یکی از پردازنده‌ها برای اجرای این وظیفه در نظر گرفته میشود که این وظایف به صف پردازنده مورد نظر اضافه می شود. در صف پردازنده‌ها از تکنیک EDF استفاده میشود به این صورت که وظیفه‌ای که نزدیک‌ترین ضرب العجل را دارد زودتر اجرا میشود.
در این طرح هر وظیفه به زیر وظایفی تقسیم بندی میشود. هر زیر وظیفه ای که در بلاک اصلی اجرا میشود آن زیر وظیفه در بلاک پشتیبان به روز میشود تا هرگاه وظیفه در بلاک اصلی با مشکل مواجه شد وظیفه موجود در بلاک پشتیبان از آخرین زیر وظیفه ای که به روز شده کار را ادامه دهد.
Proceedings of National Conference “VISION’07” on “High Performance Computing” 2nd April’07
Government College of Engineering, Department of CSE, Tirunelveli, Tamil Nadu, INDIA
A Novel Fault Tolerant Scheduling Technique In Real-Time Heterogeneous
Distributed Systems Using Distributed Recovery Block
| Bibhudatta Sahoo Senior Lecturer Department of CSE, NIT Rourkela |
Aser Avinash Ekka JRF (CS-HDS) Department of CSE, NIT Rourkela |
Abstract
Fault-tolerance is an important requirement for real-time
distributed system, which is designed to provide solutions
in a stringent timing constraint. This paper considers
fault-tolerant scheme on heterogeneous multi-component
distributed system architecture using a software technique
based on Distributed Recovery Block (DRB). The
experiment shows that, the proposed scheme based on
DRB with Random-EDF heuristic tolerates about 10% to
20% number of permanent failures and an arbitrary
number of timing failures.
این فایل ورد (word) ترجمه در 3 صفحه و فایل اصلی لاتین pdf مقاله در 6 صفحه به خدمتتون ارائه میشود.
آنالیز مقاله3
A Novel Intelligent Algorithm for Fault-Tolerant Task Scheduling in Real Time Multiprocessor Systems
1-ایده اصلی مقاله
یکی از روشهای تحمل پذیری خطا در سیستمهای بلادرنگ استفاده از روش پشتیبان است که در آن دو نسخه از یک وظیفه در دو پردازنده متفاوت زمانبندی میشوند. این سیستم باید به گونه ای زمانبندی شود که در صورت رخداد خطا در نسخه اصلی نسخه پشتیبان بتواند کار آن را در زمان مشخص شده ادامه دهد. روشهای سنتی نمی‌‌توانند در تمامی مواقع برنامه ریزی قابل قبولی داشته باشند بنابراین اخیراً روشهای اکتشافی متعددی مطرح شده است.
در این رویکرد الگوریتم زمانبند تحمل پذیر خطا بر اساس الگوریتم ژنتیک و نسخه پشتیبان وظایف ارائه شده است که تا حد امکان از تمامی‌‌پردازنده‌ها به طور مساوی استفاده میشود.
این الگوریتم در سیستم بلادرنگ نرم چندپردازنده‌ای که در آن وظایف غیر انحصاری و متناوب هستند و هیچ وابستگی الویت داری بین وظایف وجود ندارد طراحی شده است.
A Novel Intelligent Algorithm for Fault-Tolerant Task Scheduling in RealTime Multiprocessor Systems
Golbarg Zarinzad*, Amir masoud Rahmani and Nikta Dayhim
Islamic Azad University, Science and Research Branch, Tehran, Iran
*Dept of computer Lavasani Hospital, Social Security Organization
{Golbarg_zar@yahoo.com, Rahmani@sr.iau.ac.ir, Nikta_day18@yahoo.ca}
Abstract
The scheduling problem for real-time tasks on
multiprocessor is one of NP-hard problems. In faulttolerant real-time systems, tasks have deadlines to be
met in spite of the presence of fault. Many attempts such
as classical algorithms and intelligent methods have
been made to solve this problem. Primary-Backup (PB)
scheme is one of the most important classical
algorithms that have been employed for fault-tolerant
scheduling for real-time tasks, wherein each task has
two versions and the versions must be scheduled on two
different processors. In this paper a novel scheduling
algorithm is proposed based on Genetic Algorithm
(GA) which uses PB for tolerating faults since all tasks
employ the processors equally as much as possible.
Keywords: Real-Time system, Multiprocessor, Static
scheduling, Genetic Algorithm, Fault-Tolerant
این فایل ورد (word) ترجمه در 3 صفحه و فایل اصلی لاتین pdf مقاله در 6 صفحه به خدمتتون ارائه میشود.
زمانبندی سیستم های بلادرنگ چند پردازنده‌ای با مکانیزم تحمل‌پذیری خطا
چکیده:
سیستم بلادرنگ (Real-time) سیستمی است که در آن زمان پاسخگویی به وقایع از اهمیت بسیار بالایی برخوردار است. تحمل پذیری خطا در سیستمهای بلادرنگ چندپردازنده‌ای به علت وجود محدودیتهای زمانی امری حیاتی و بسیار مهم است. در این گونه سیستمها، خطا باید هر چه سریع تر کشف و ترمیم شود تا وظایف بتوانند در ضرب العجل (deadline) تعیین شده کار خود را به اتمام رسانند.
برای اینکه سیستمی تحمل پذیر خطا باشد نیاز به افزونگی دارد. یکی از انواع افزونگی‌ها افزونگی نرم افزاری است که نوع خاصی از آن به نام پشتیبان اصلی (primary backup) برای زمانبندی سیستم چند پردازنده‌ای بلادرنگ استفاده میشود. در این مقاله به بررسی سه رویکرد جدید برای زمانبندی وظایف در سیستمهای بلادرنگ تحمل پذیر خطا پرداخته‌ایم. مزایا و معایب هر کدام را بیان کرده و مقایسه‌ای بین آنها انجام داده‌ایم .
کلمات کلیدی: تحمل پذیری خطا، سیستمهای بلادرنگ، وظایف، نسخه پشتیبان، چندپردازنده‌ای
1-مقدمه
سیستم بلادرنگ سیستمی است که در آن وظایف باید در مدت زمان معینی به اتمام برسند تا سیستم بتواند به طور مطلوب کار کند. به عبارت دیگر در این سیستمها صحت سیستم نه تنها به نتایج منطقی محاسبات، بلکه به زمانی که طی آن نتایج تولید شده است نیز بستگی دارد. سیستمهای بلادرنگ به دو قسمت عمده سیستمهای بلادرنگ سخت و سیستمهای بلادرنگ نرم تقسیم میشوند. در سیستم بلادرنگ سخت، کار انجام شده توسط سیستم بایستی دقیقا به موقع انجام شود و هیچ گونه تاخیری قابل قبول نیست وگر نه سبب ناتوانی سیستم میشود مانند سیستم کنترل موشک، ولی در سیستم بلادرنگ نرم (مانند پخش موسیقی) زمان پاسخگویی به پردازش مهم است ولی مانند بلادرنگ سخت, حیاتی نیست. همچنین وظایف در سیستمهای بلادرنگ دو گونه هستند: متناوب (Periodic) و غیر متناوب (Aperiodic). در حالت متناوب، وظایف با دوره تناوب مشخص تکرار میشوند مانند اندازه گیری دما در یک محیط در فاصله‌های زمانی مشخص، ولی وظایف غیر متناوب به صورت تصادفی رخ می‌‌دهند و زمان رخداد مشخصی ندارند.
در سیستمهای تحمل پذیر خطای بلادرنگ تشخیص خطا و ترمیم آن باید به موقع صورت گیرد چون سیستم باید علی رغم وجود خطا پاسخ درستی در زمان معین شده ایجاد نماید. برای تکنیکهای تحمل پذیر خطا، زمان تشخیص، تاخیر و ترمیم از معیارهای نشان دهنده کارایی هستند. یک تکنیک تحمل پذیر خطا در سیستمهای بلادرنگ، زمانی میتواند مفید باشد که از جهت زمانی به سختی محدود شده باشد تا بتواند قابل استفاده در سیستم های بلادرنگ باشد.
یکی از مواردی که در سیستم های بلادرنگ چند پردازنده‌ای مطرح است مسئله زمانبندی وظایف است. مشکل زمانبندی وظایف سیستم های بلادرنگ این است که باید تشخیص دهیم یک وظیفه مشخص چه زمانی و در کدام پردازنده باید اجرا شود. روشهای زمانبندی بلادرنگ به دو دسته کلی پویا و ایستا تقسیم میشوند. در حالت ایستا قبل از شروع به کار سیستم, تصمیمات زمانبندی گرفته میشود ولی در حالت پویا تصمیمات زمانبندی در زمان اجرای سیستم گرفته میشود. الگوریتمهای زمانبندی ایستا اغلب روی وظایف متناوب اجرا میشوند و قابلیت اجرا روی وظایف غیر متناوب را که زمان ورود و ضرب العجل آنها از قبل مشخص نیست، ندارند. زمانبندی چنین وظایفی نیاز به زمانبند پویا دارد. در زمانبندی پویا وقتی مجموعه جدیدی از وظایف وارد سیستم میشوند زمانبند با توجه به مشخصات و قابلیت انعطاف آنها تصمیم گیری می‌‌کند.
در سیستم های بلادرنگ وظایف با وجود خطا و خرابی در سیستم باید در ضرب العجل تعیین شده به اتمام رسند بنابراین نیاز به الگوریتمهایی داریم که بتوانند با فرض خرابی در سیستم در زمان مشخص پاسخ مطلوب را ارائه نمایند و در واقع تحمل پذیری خطا داشته باشند.
انواع خطاهایی که در سیستم ممکن است رخ دهد به صورت خطاهای ماندگار، خطاهای گذرا و خطاهای متناوب می‌‌باشند. تحمل پذیری خطا در سیستم های چند پردازنده‌ای مهم تر است زیرا چندین پردازنده به صورت موازی در حال کار کردن هستند و خرابی یکی از آنها ممکن است در اجرای بقیه تاثیر بگذارد [1]. البته از نگاه دیگر یک از مزایای سیستم های توزیع شده این است که می‌‌توان خطای قطعات خراب را تحمل کند بدون این که کار بقیه قطعات مختل شود[2]
تحمل پذیری خطا میتواند با استفاده از افزونگی صورت پذیرد. این افزونگی میتواند به صورت افزونگی سخت افرازی، افزونگی نرم افزاری، افزونگی اطلاعات و یا افزونگی زمانی باشد. در روشهای ارائه شده در این مقاله از افزونگی نرم افزاری استفاده شده است.
الگوریتمهای زمانبندی که قابلیت تحمل پذیری خطا را دارند هر دو گروه ترمیم روبه جلو (forward) و ترمیم رو به عقب (backward) را در بر می‌‌گیرند. الگوریتمهای زمانبندی که تکرار وظایف را در بر دارند شامل ترمیم رو به جلو هستند. یکی از رویکرد‌های رو به جلو که در زمانبندی تحمل پذیر خطا مورد استفاده قرار می‌‌گیرد مدل PB یا پشتیبان اصلی (primary backup) است. در این مدل دو نسخه از وظایف در دو پردازنده مختلف زمانبندی میشوند و یک تست پذیرش نیز استفاده میشود تا از صحت پاسخها اطمینان حاصل نماید. در این روش نسخه پشتیبان فقط زمانی اجرا میشود که نسخه اصلی دچار خرابی شود.
در ادامه در قسمت 2 به بررسی سه رویکرد مختلف برای زمانبندی وظایف با استفاده از روش PB می‌‌پردازیم. در قسمت 3 این روشها را با هم مقایسه می‌‌کنیم، در قسمت 4 نتیجه گیری می‌‌نماییم و در قسمت 5 ایده جدیدی مطرح کرده‌ایم که دز صورت پیاده سازی موفق میتواند بر معایب روش های مطرح شده فائق آید.
به همراه فایل ورد 9 صفحه ای دیگر + پاورپوینت 15 اسلایدی