نمایش مبدأ برای زمانبند Rate-monotonic

#تغییر_مسیر [[زمانبند نرخ یکنواخت]]{{DISPLAYTITLE:زمانبند نرخ یکنواخت}}

در [[علوم رایانه|علوم کامپیوتر]] ، زمان‌بند Rate-monotonic(برنامه‌ریز نرخ یکنواخت یا '''RMS''' ) <ref>{{Citation|first=C. L.|last=Liu|author-link=Chung Laung Liu|first2=J.|last2=Layland|title=Scheduling algorithms for multiprogramming in a hard real-time environment|journal=Journal of the ACM|volume=20|number=1|year=1973|pages=46–61|doi=10.1145/321738.321743}}</ref> به عنوان یک الگوریتم زمان‌بندی بر اساس اولویت با استفاده از یک کلاس اولویت ایستا است. که در سیستم عامل‌های بلادرنگ (RTOS) استفاده می‌شود.<ref>{{Citation|first=Daniel P.|last=Bovet|first2=Marco|last2=Cesati|title=Understanding the Linux Kernel}}, http://oreilly.com/catalog/linuxkernel/chapter/ch10.html#85347 {{Webarchive|url=https://web.archive.org/web/20140921000832/http://oreilly.com/catalog/linuxkernel/chapter/ch10.html|date=2014-09-21}}.</ref> اولویت های ایستا در این روش بر اساس زمان مورد نیاز برای انجام شدن یک چرخه کامل کار(وظیفه) تعیین می‌شود پس هرچه زمان مورد نیاز برای چرخه کار کمتر باشد اولویت آن کار (وظیفه) بیشتر است. 

این سیستم عامل‌ها عموماً [[قبضه‌کردن (رایانش)|انحصاری(قبضه ای)]] است و تضمین قطعی برای زمان اجرا دارد.در این سیستم‌ها از تحلیل نرخ یکنواخت (Rate monotonic analysis) برای به دست آوردن تضمین زمان بندی در یک برنامه خاص استفاده می‌شود.  

== معرفی ==
در نسخه ساده تجزیه و تحلیل نرخ مونوتونیک rate-monotonic analysis فرض می‌شود رشته‌ها دارای ویژگی‌های زیر باشند: 
* هیچ منبع اشتراکی بین رشته‌ها وجود نداشته باشد ( بین پردازه‌ها منبع مشترکی نباشد این منابع اشتراکی می‌توانند [[سخت‌افزار رایانه|سخت افزار]]، صف اولویت، یا هر نوع [[سمافور]] مسدود کننده یا غیر مسدود کننده ( [[انتظار مشغول|مشغول به انتظار]] ) باشند) 
* مهلت‌های قطعی دقیقاً برابر با دوره‌ها هستند 
* اولویت‌ها ایستا(استاتیک) هستند (وظیفه ای که بالاترین اولویت را دارد کمترین زمان اجرا را خواهد داشت و بلافاصله قابل اجراست و تمامی وظایف دیگر را قبضه کرده و اجرا می شود) 
* اولویت های استاتیک با توجه به کنوانسیون های ''نرخ مونوتونیک'' (وظایف با دوره های کوتاه / ضرب‌العجل‌ها اولویت های بیشتر دارند) 
* زمان برگردان متن(Context switch) و دیگر عملیات مرتبط با رشته ناچیز هستند و بر مدل تاثیری ندارند 

این یک مدل ریاضی است که شامل یک شبیه سازی محاسبه شده از دوره‌ها در یک سیستم بسته است، در جایی که [[زمان‌بندی نوبت گردشی|زمانبندهای راند رابین(نوبت گردشی)]] و [[اشتراک زمانی]] در برآورد کردن نیازهای زمانبندی ناتوان هستند. 

زمان بند rate monotonic مدل اجرایی همه رشته های موجود در سیستم را  بررسی می‌کند و از روی این بررسی انجام شده تعیین می‌کند چه مقدار زمان برای تضمین مجموعه رشته‌های درخواستی مورد نیاز است 

{{Harvard citation text|Liu|Layland|1973}} اثبات کردند که برای مجموعه‌ای از وظایف دوره‌ای مانند  {{Mvar|n}} با دوره‌های منحصر به فرد،یک برنامه ریزی شدنی به طوریکه تمامی مهلت‌های پایان را رعایت کند وجود دارد اگر میزان مصرف از پردازنده از یک حد مشخص کمتر باشد که این حد به تعداد وظایف وابسته است  

تست برنامه ریزی برای RMS از رایطه زیر به دست می‌آید: 

که در این رابطه {{Mvar|C<sub>i</sub>}} زمان مورد نیاز وظیفه i ام برای پردازش است، {{Mvar|T<sub>i</sub>}} دوره آزادسازی پردازه iام  است که مهلت پایان آن یک دوره بعد است ، و {{Mvar|n}} تعداد فرایندهای برنامه ریزی شده است. به عنوان مثال، {{Mvar|U&nbsp;≤&nbsp;0.8284}} برای دو فرایند است. 

هنگامی که تعداد فرایندها به سمت [[بی‌نهایت|بی نهایت]] تمایل پیدا می کند، این عبارت به سمت مقدار زیر میل می‌کند: 

: <math>\lim_{n \rightarrow \infty} n(\sqrt[n]{2} - 1) = \ln 2 \approx 0.693147\ldots</math> 

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

میدانیم که یک سیستم وظیفه که به صورت تصادفی تولید می شود زمانی که بهره‌وری پردازنده 85٪ یا کمتر باشد تمامی مهلت پایان ها را برآورده خواهدکرد، <ref>{{Citation|first=J.|last=Lehoczky|first2=L.|last2=Sha|first3=Y.|last3=Ding|contribution=The rate monotonic scheduling algorithm: exact characterization and average case behavior|title=IEEE Real-Time Systems Symposium|pages=166–171|year=1989|doi=10.1109/REAL.1989.63567|isbn=978-0-8186-2004-1}}.</ref> با این حال این واقعیت به دانستن دقیق آمار و اطلاعات وظایف (مانند دوره‌ها، مهلت‌ها) بستگی دارد که نمی‌توان تامین این اطلاعات را برای تمام مجموعه‌های کار تضمین کرد. 

محدودیت هایپربولیک <ref>{{Citation|last=Enrico Bini, Giorgio C. Buttazzo and Giuseppe M. Buttazzo|title=Rate Monotonic Analysis: the Hyperbolic Bound|journal=IEEE Transactions on Computers|year=2003|volume=52|number=7|pages=933–942|doi=10.1109/TC.2003.1214341}}</ref> یک شرط کافی با محدودیت شدیدتر نسبت یه روش ارائه لی(Liu) و لیلند (Layland) برای بازه قابلیت برنامه‌ریزی است 

: <math>\prod_{i=1}^n (U_i +1) \leq 2</math> 

که در این رابطه  {{Mvar|U<sub>i</sub>}} کارایی پردازنده برای هر وظیفه است. 

تخصیص اولویت نرخ مونوتونیک بهینه است، به این معنی که اگر هر الگوریتم برنامه ریزی استاتیک اولویت دیگری بتواند تمام ضربالعجل‌ها را برآورده کند، الگوریتم نرخ مونوتونی نیز می تواند. 

الگوریتم [[:en:Deadline-monotonic_scheduling|زمانبندی مونوتونیک مهلت]] برای دوره‌ها و ضرب‌العجل‌های برابر نیز بهینه است، در واقع در این مورد الگوریتم‌ها یکسان هستند؛  

علاوه بر این، زمانبندی مونوتنیک ضرب‌العجل زمانی مطلوب است که ضرب‌العجل کمتر از دوره باشد. <ref>{{Citation|first=J. Y.|last=Leung|first2=J.|last2=Whitehead|title=On the complexity of fixed-priority scheduling of periodic, real-time tasks|journal=Performance Evaluation|volume=2|number=4|pages=237–250|year=1982|doi=10.1016/0166-5316(82)90024-4}}.</ref> الگوریتم Audsley که دارای تست برنامه‌ریزی دقیق برای این مدل است، برای یک مدل کاری که در آن ضرب‌العجل می‌تواند بیشتر از دوره باشد، یک تخصیص اولویت بهینه را تعیین می‌کند. <ref>{{Citation|last=Alan Burns and Andy Wellings|title=Real-Time Systems and Programming Languages|year=2009|publisher=Addison-Wesley|edition=4th|isbn=978-0-321-41745-9|pages=391,397}}</ref> 

== اجتناب از عدم رعایت اولویت ==
در بسیاری از کاربردهای عملی، منابع به اشتراک گذاشته می شوند و RMS بدون تغییر،باعث میشود در معرض خطر [[معکوس کردن اولویت|عدم رعایت اولویت]] و همچنین در معرض خطر وقوع [[بن‌بست (علوم رایانه)|بن بست]] قرار گیرد. 

در عمل این مشکل را با غیر فعال کردن امکان قبضه یا [[:en:Priority_inheritance|ارث بری اولویت‌ها]] حل می‌کنند. 

همچنین  روش های جایگزینی وجود دارد مانند استفاده از [[:en:Lock-free_and_wait-free_algorithms|الگوریتم‌های بدون قفل]] یا اجتناب از اشتراک (mutex) یا سمافور(semaphore ) بین رشته‌های دارای اولویت مختلف، که در وهله اول اینکار می‌تواند باعث جلوگیری از تداخل منابع شود. 

=== غیر فعال کردن عملکرد غیر انحصاری ===
* <code>OS_ENTER_CRITICAL()</code> و <code>OS_EXIT_CRITICAL()</code> دستورهایی هستند که از وقوع وقفه در سیستم عامل‌های بلادرنگ جلوگیری می‌کنند مانند [[:en:MicroC/OS-II|MicroC / OS-II]] 
* خانواده ای از دستورهای <code>splx()</code> که از آنها برای کنترل اولویت استفاده میشود , ممکن است از آنها برای ایجاد وقفه های کم اولویت استفاده شود  (FreeBSD 5.x / 6.x) 

=== ارث بری اولویت ===
* ''پروتکل ارث بری اولویت اولیه'' <ref>{{Citation|first=B. W.|last=Lampson|author-link=Butler Lampson|first2=D. D.|last2=Redell|title=Experience with processes and monitors in Mesa|journal=Communications of the ACM|volume=23|number=2|year=1980|pages=105–117|doi=10.1145/358818.358824}}.</ref> ،در زمان درخواست منابع به وظیفه‌ای که منبع را در اختیار دارد اولویت بالاتری از وظیفه‌ای که همان منبع را درخواست می‌کند، تخصیص می‌دهد. و بعد از رها سازی منابع اولویت‌های تغییر یافته را به همان حالت قبلی برمی‌گرداند. این روش از بن‌بست جلوگیری نمی‌کند و از مسدود شدن زنجیره‌ای رنج می برد. به این معنی که اگر یک کار با اولویت بالا به چندین منبع به صورت متوالی دسترسی داشته باشد ممکن است مجبور شود تا در انتظار بماند یا به عبارتی بلوکه شود تا زمانی که منابع از وظایف دارای اولویت کمتر آزاد شود. <ref>{{Citation|last=Buttazzo|first=Giorgio|title=Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications|publisher=Springer|place=New York, NY|year=2011|edition=Third|page=225}}</ref> [https://rt.wiki.kernel.org/index.php/Main_Page پچ زمان واقعی] برای [[هسته لینوکس]] شامل پیاده سازی‌هایی از این پروتکل است. <ref>{{Cite web|url=https://rt.wiki.kernel.org/index.php/Frequently_Asked_Questions#How_does_the_CONFIG_PREEMPT_RT_patch_work.3F|title=Real-Time Linux Wiki|date=2008-03-26|accessdate=2014-03-14|publisher=kernel.org}}</ref> 
* [[:en:Priority_ceiling_protocol|پروتکل سقف اولویت]] <ref>{{Citation|first=L.|last=Sha|first2=R.|last2=Rajkumar|first3=J. P.|last3=Lehoczky|title=Priority inheritance protocols: an approach to real-time synchronization|journal=IEEE Transactions on Computers|volume=39|number=9|year=1990|pages=1175–1185|doi=10.1109/12.57058}}.</ref> ،  پروتکل ارث بری اولویت اولیه را با اختصاص یک سقف اولویت برای هر سمافور بهبود میبخشد که این سقف اولویت، همان اولویت مهم‌ترین ترین کاری است که در نهایت به سمافر دسترسی پیدا خواهد کرد.یک وظیفه اگر اولویتی پایین تر از سقف اولویت داشته باشد نمی‌تواند وقتی پردازنده در ناحیه بحرانی قرار دارد پردازنده را از وظیفه دیگر پس بگیرد این روش از وقوع بن بست جلوگیری می‌کند و زمان انتظار و بلوکه شدن را حداکثر به طول یک محدوده بحرانی برای یک وظیفه کم اولویت محدود می‌کند این روش میتواند یک روش بهینه غیر سراسری باشد به عبارتی این روش بهینه است اما می تواند باعث مسدود شدن غیر ضروری شود. از پروتکل سقف اولویت در هسته سیستم بلادرنگ [[:en:VxWorks|VxWorks]] استفاده شده است نام دیگر این پروتکل ''Highest Locker'' است (HLP). <ref>{{Citation|last=Buttazzo|first=Giorgio|title=Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications|publisher=Springer|place=New York, NY|year=2011|edition=Third|page=212}}</ref> 

الگوریتم‌های ارث بری اولویت می‌توانند با دو ویژگی مشخص شوند. 

ویژگی اول وراثت تنبل یا فوری(بلافاصله):

تنبل (فقط زمانی اعمال می‌شود که ضروری است) یا وراثت بلافاصله (افزایش اولویت قبل از وقوع یک تداخل)

ویژگی دوم اولویت خوش بین یا بدبین:

اولویت خوش بینانه (افزایش به اندازه حداقل مقدار) بدبینانه (افزایش بیشتر از حداقل مقدار)  

{| class="wikitable"
!
! بدبینانه 
! خوش بینانه 
|-
! فوری 
| <code>OS_ENTER_CRITICAL()</code> / <code>OS_EXIT_CRITICAL()</code> 
| <code>splx()</code> ،  
بالاترین locker 
|-
! تنبل 
|
| پروتکل سقف اولویت،  
پروتکل ارث بری اولویت اولیه 
|-
|}
در عمل هیچ تفاوت ریاضی (از لحاظ استفاده از سیستم Liu-Layland محدود) بین الگوریتم‌های تنبل و فوری وجود ندارد و الگوریتم‌های فوری برای پیاده سازی کارآمدتر هستند و بنابراین در سیستم‌های عملی معمولاً از آنها استفاده می‌شوند.  {{مدرک|date=October 2007}}   

یک نمونه از استفاده از وراثت اولیه(ساده) اولویت مربوط به "خطای بازنشانی [[رهیاب مریخ|پیمایش مریخ]] " است <ref>http://research.microsoft.com/~mbj/Mars_Pathfinder/</ref> <ref>http://anthology.spacemonkeys.ca/archives/770-Mars-Pathfinder-Reset-Bug.html</ref>  

== مثال ==
{| class="wikitable"
! پردازه 
! زمان اجرا 
! دوره زمانی 
|-
! P1 
| 1 
| 8 
|-
! P2 
| 2 
| 5 
|-
! P3 
| 2 
| 10 
|-
|}
بهره وری برابر است با: 

:<span data-segmentid="102" class="cx-segment"><math>\frac{1}{8} + \frac{2}{5} + \frac{2}{10} = 0.725</math></span>

شرایط کافی برای 3 فرایند، که می‌توان نتیجه گرفت که سیستم قابل برنامه‌ریزی و زمانبندی است: 

<span data-segmentid="104" class="cx-segment"><math>U = 3(2^\frac{1}{3} - 1) = 0.77976\ldots</math></span> 

از آنجاییکه  <span data-segmentid="105" class="cx-segment"><math>0.725 < 0.77976\ldots</math></span> سیستم مطمئناً قابل برنامه ریزی است  

اما به یاد داشته باشید، این شرط لازم نیست. بنابراین ما نمی‌توانیم بگوییم که یک سیستم با بهره‌وری بیشتر با این الگوریتم زمانبندی قابل برنامه ریزی نیست یا نه. 

== منابع ==
{{پانویس|30em}}

== مطالعه بیشتر ==
* {{Citation|last=Buttazzo|first=Giorgio|title=Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications|publisher=Springer|place=New York, NY|year=2011}}  . 
* {{Citation|last=Alan Burns and Andy Wellings|title=Real-Time Systems and Programming Languages|year=2009|publisher=Addison-Wesley|edition=4th|isbn=978-0-321-41745-9}} <bdi> {{Citation|last=Alan Burns and Andy Wellings|title=Real-Time Systems and Programming Languages|year=2009|publisher=Addison-Wesley|edition=4th|isbn=978-0-321-41745-9}} </bdi>
* {{Citation|last=Liu|first=Jane W.S.|title=Real-time systems|publisher=Prentice Hall|place=Upper Saddle River, NJ|year=2000}}  ، فصل 6 
* {{Citation|first=M.|last=Joseph|first2=P.|last2=Pandya|title=Finding response times in real-time systems|journal=BCS Computer Journal|volume=29|number=5|pages=390–395|year=1986|doi=10.1093/comjnl/29.5.390}}  . 
* {{Citation|first=Lui|last=Sha|first2=John B.|last2=Goodenough|title=Real-Time Scheduling Theory and Ada|journal=IEEE Computer|pages=53–62|date=April 1990|volume=23|number=4|doi=10.1109/2.55469}} 

== پیوند به بیرون ==
* [http://research.microsoft.com/~mbj/Mars_Pathfinder/Authoritative_Account.html خط مشی مریخ Pathfinder] از تحقیق @ مایکروسافت 
* [http://catless.ncl.ac.uk/Risks/19.49.html#subj1 آنچه واقعاً در مریخ روبر پاتفیندر توسط مایک جونز] از The Risks Digest، Vol. 19، شماره 49 
[[رده:رایانش بی‌درنگ]]