زمانبند نرخ یکنواخت

در علوم کامپیوتر، زمان‌بند Rate-monotonic(برنامه‌ریز نرخ یکنواخت یا RMS)^[۱] به عنوان یک الگوریتم زمان‌بندی بر اساس اولویت با استفاده از یک کلاس اولویت ایستا است؛ که در سیستم عامل‌های بی‌درنگ (RTOS) استفاده می‌شود.^[۲] اولویت‌های ایستا در این روش بر اساس زمان مورد نیاز برای انجام شدن یک چرخه کامل کار (وظیفه) تعیین می‌شود پس هرچه زمان مورد نیاز برای چرخه کار کمتر باشد اولویت آن کار (وظیفه) بیشتر است.

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

معرفی

در نسخه ساده تجزیه و تحلیل نرخ مونوتونیک rate-monotonic analysis فرض می‌شود رشته‌ها دارای ویژگی‌های زیر باشند:

هیچ منبع اشتراکی بین رشته‌ها وجود نداشته باشد (بین پردازه‌ها منبع مشترکی نباشد این منابع اشتراکی می‌توانند سخت‌افزار، صف اولویت، یا هر نوع نشان‌بر مسدود کننده یا غیر مسدود کننده (مشغول به انتظار) باشند)
مهلت‌های قطعی دقیقاً برابر با دوره‌ها هستند
اولویت‌ها ایستا (استاتیک) هستند (وظیفه ای که بالاترین اولویت را دارد کمترین زمان اجرا را خواهد داشت و بلافاصله قابل اجراست و تمامی وظایف دیگر را قبضه کرده و اجرا می‌شود)
اولویت‌های استاتیک با توجه به کنوانسیون‌های نرخ مونوتونیک (وظایف با دوره‌های کوتاه / ضرب‌العجل‌ها اولویت‌های بیشتر دارند)
زمان برگردان متن(Context switch) و دیگر عملیات مرتبط با رشته ناچیز هستند و بر مدل تأثیری ندارند

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

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

(Liu و Layland 1973) اثبات کردند که برای مجموعه‌ای از وظایف دوره‌ای مانند $n$ با دوره‌های منحصر به فرد، یک برنامه‌ریزی شدنی به طوریکه تمامی مهلت‌های پایان را رعایت کند وجود دارد اگر میزان مصرف از پردازنده از یک حد مشخص کمتر باشد که این حد به تعداد وظایف وابسته است

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

که در این رابطه $C i$ زمان مورد نیاز وظیفه i ام برای پردازش است، $T i$ دوره آزادسازی پردازه iام است که مهلت پایان آن یک دوره بعد است، و $n$ تعداد فرایندهای برنامه‌ریزی شده‌است. به عنوان مثال، $U \leq ۰٫۸۲۸۴$ برای دو فرایند است.

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

\lim _{n\rightarrow \infty }n({\sqrt[{n}]{2}}-1)=\ln 2\approx 0.693147\ldots

بنابراین، برآورد تقریبی این است که RMS می‌تواند تمام مهلت‌های پایان مقرر را در صورتی که نرخ بهره‌وری CPU کمتر از ۶۹٫۳۲٪ باشد برآورده کند. ۳۰٫۷٪ باقی از CPU را می‌توان به وظایف غیر بی‌درنگ کم اولویت اختصاص داد.

می‌دانیم که یک سیستم وظیفه که به صورت تصادفی تولید می‌شود زمانی که بهره‌وری پردازنده ۸۵٪ یا کمتر باشد تمامی مهلت پایان‌ها را برآورده خواهدکرد،^[۳] با این حال این واقعیت به دانستن دقیق آمار و اطلاعات وظایف (مانند دوره‌ها، مهلت‌ها) بستگی دارد که نمی‌توان تأمین این اطلاعات را برای تمام مجموعه‌های کار تضمین کرد.

محدودیت هایپربولیک^[۴] یک شرط کافی با محدودیت شدیدتر نسبت یه روش ارائه لی(Liu) و لیلند (Layland) برای بازه قابلیت برنامه‌ریزی است

\prod _{i=1}^{n}(U_{i}+1)\leq 2

که در این رابطه $U i$ کارایی پردازنده برای هر وظیفه است.

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

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

علاوه بر این، زمانبندی مونوتنیک ضرب‌الاجل زمانی مطلوب است که ضرب‌الاجل کمتر از دوره باشد.^[۵] الگوریتم Audsley که دارای تست برنامه‌ریزی دقیق برای این مدل است، برای یک مدل کاری که در آن ضرب‌الاجل می‌تواند بیشتر از دوره باشد، یک تخصیص اولویت بهینه را تعیین می‌کند.^[۶]

اجتناب از عدم رعایت اولویت

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

در عمل این مشکل را با غیرفعال کردن امکان قبضه یا ارث بری اولویت‌ها حل می‌کنند.

همچنین روش‌های جایگزینی وجود دارد مانند استفاده از الگوریتم‌های بدون قفل یا اجتناب از اشتراک (mutex) یا نشان‌بر(semaphore) بین رشته‌های دارای اولویت مختلف، که در وهله اول اینکار می‌تواند باعث جلوگیری از تداخل منابع شود.

غیرفعال کردن عملکرد غیر انحصاری

OS_ENTER_CRITICAL() و OS_EXIT_CRITICAL() دستورهایی هستند که از وقوع وقفه در سیستم عامل‌های بی‌درنگ جلوگیری می‌کنند مانند MicroC / OS-II
خانواده ای از دستورهای splx() که از آنها برای کنترل اولویت استفاده می‌شود، ممکن است از آنها برای ایجاد وقفه‌های کم اولویت استفاده شود (FreeBSD 5.x / 6.x)

ارث بری اولویت

پروتکل ارث بری اولویت اولیه،^[۷] در زمان درخواست منابع به وظیفه‌ای که منبع را در اختیار دارد اولویت بالاتری از وظیفه‌ای که همان منبع را درخواست می‌کند، تخصیص می‌دهد؛ و بعد از رهاسازی منابع اولویت‌های تغییر یافته را به همان حالت قبلی برمی‌گرداند. این روش از بن‌بست جلوگیری نمی‌کند و از مسدود شدن زنجیره‌ای رنج می‌برد. به این معنی که اگر یک کار با اولویت بالا به چندین منبع به صورت متوالی دسترسی داشته باشد ممکن است مجبور شود تا در انتظار بماند یا به عبارتی بلوکه شود تا زمانی که منابع از وظایف دارای اولویت کمتر آزاد شود.^[۸] پچ زمان واقعی برای هسته لینوکس شامل پیاده‌سازی‌هایی از این پروتکل است.^[۹]
پروتکل سقف اولویت،^[۱۰] پروتکل ارث بری اولویت اولیه را با اختصاص یک سقف اولویت برای هر نشان‌بر بهبود می‌بخشد که این سقف اولویت، همان اولویت مهم‌ترین‌ترین کاری است که در نهایت به سمافر دسترسی پیدا خواهد کرد. یک وظیفه اگر اولویتی پایین‌تر از سقف اولویت داشته باشد نمی‌تواند وقتی پردازنده در ناحیه بحرانی قرار دارد پردازنده را از وظیفه دیگر پس بگیرد این روش از وقوع بن‌بست جلوگیری می‌کند و زمان انتظار و بلوکه شدن را حداکثر به طول یک محدوده بحرانی برای یک وظیفه کم اولویت محدود می‌کند این روش می‌تواند یک روش بهینه غیر سراسری باشد به عبارتی این روش بهینه است اما می‌تواند باعث مسدود شدن غیر ضروری شود. از پروتکل سقف اولویت در هسته سیستم بی‌درنگ VxWorks استفاده شده‌است نام دیگر این پروتکل Highest Locker است (HLP).^[۱۱]

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

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

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

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

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

	بدبینانه	خوش‌بینانه
فوری	`OS_ENTER_CRITICAL()` / `OS_EXIT_CRITICAL()`	`splx()` ، بالاترین locker
تنبل		پروتکل سقف اولویت، پروتکل ارث بری اولویت اولیه

در عمل هیچ تفاوت ریاضی (از لحاظ استفاده از سیستم Liu-Layland محدود) بین الگوریتم‌های تنبل و فوری وجود ندارد و الگوریتم‌های فوری برای پیاده‌سازی کارآمدتر هستند و بنابراین در سیستم‌های عملی معمولاً از آنها استفاده می‌شوند. ^{^{[نیازمند منبع]}}

یک نمونه از استفاده از وراثت اولیه (ساده) اولویت مربوط به "خطای بازنشانی پیمایش مریخ " است^[۱۲]^[۱۳]

مثال

پردازه	زمان اجرا	دوره زمانی
P1	۱	۸
P2	۲	۵
P3	۲	۱۰

بهره‌وری برابر است با:

{\frac {1}{8}}+{\frac {2}{5}}+{\frac {2}{10}}=0.725

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

از آنجاییکه سیستم مطمئناً قابل برنامه‌ریزی است

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

جستارهای وابسته

Deos، یک زمان و فضای سیستم تقسیم زمان واقعی سیستم شامل یک برنامه زمانبندی مونوبون کارایی.
زمانبندی مونیتونی
برنامه‌ریزی اولویت پویا
اولین برنامه زمانبندی اولیه مهلت
RTEMS، یک سیستم عامل آفلاین در زمان واقعی، حاوی یک برنامه زمانبندی کارکردی مونوتنیک است.
برنامه‌ریزی (محاسبات)

منابع

↑ Liu, C. L.; Layland, J. (1973), "Scheduling algorithms for multiprogramming in a hard real-time environment", Journal of the ACM, 20 (1): 46–61, doi:10.1145/321738.321743
↑ Bovet, Daniel P.; Cesati, Marco, Understanding the Linux Kernel, http://oreilly.com/catalog/linuxkernel/chapter/ch10.html#85347 بایگانی‌شده در ۲۰۱۴-۰۹-۲۱ توسط Wayback Machine.
↑ Lehoczky, J.; Sha, L.; Ding, Y. (1989), "The rate monotonic scheduling algorithm: exact characterization and average case behavior", IEEE Real-Time Systems Symposium, pp. 166–171, doi:10.1109/REAL.1989.63567, ISBN 978-0-8186-2004-1.
↑ Enrico Bini, Giorgio C. Buttazzo and Giuseppe M. Buttazzo (2003), "Rate Monotonic Analysis: the Hyperbolic Bound", IEEE Transactions on Computers, 52 (7): 933–942, doi:10.1109/TC.2003.1214341
↑ Leung, J. Y.; Whitehead, J. (1982), "On the complexity of fixed-priority scheduling of periodic, real-time tasks", Performance Evaluation, 2 (4): 237–250, doi:10.1016/0166-5316(82)90024-4.
↑ Alan Burns and Andy Wellings (2009), Real-Time Systems and Programming Languages (4th ed.), Addison-Wesley, pp. 391, 397, ISBN 978-0-321-41745-9
↑ Lampson, B. W.; Redell, D. D. (1980), "Experience with processes and monitors in Mesa", Communications of the ACM, 23 (2): 105–117, doi:10.1145/358818.358824.
↑ Buttazzo, Giorgio (2011), Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications (Third ed.), New York, NY: Springer, p. 225
↑ "Real-Time Linux Wiki". kernel.org. 2008-03-26. Retrieved 2014-03-14.
↑ Sha, L.; Rajkumar, R.; Lehoczky, J. P. (1990), "Priority inheritance protocols: an approach to real-time synchronization", IEEE Transactions on Computers, 39 (9): 1175–1185, doi:10.1109/12.57058.
↑ Buttazzo, Giorgio (2011), Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications (Third ed.), New York, NY: Springer, p. 212
↑ http://research.microsoft.com/~mbj/Mars_Pathfinder/
↑ «نسخه آرشیو شده». بایگانی‌شده از اصلی در 5 اكتبر 2011. دریافت‌شده در 18 مه 2019. تاریخ وارد شده در |archive-date= را بررسی کنید (کمک)

برای مطالعهٔ بیشتر

Buttazzo, Giorgio (2011), Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications, New York, NY: Springer.
Alan Burns and Andy Wellings (2009), Real-Time Systems and Programming Languages (4th ed.), Addison-Wesley, ISBN 978-0-321-41745-9 Alan Burns and Andy Wellings (2009), Real-Time Systems and Programming Languages (4th ed.), Addison-Wesley, ISBN 978-0-321-41745-9
Liu, Jane W.S. (2000), Real-time systems, Upper Saddle River, NJ: Prentice Hall، فصل ۶
Joseph, M.; Pandya, P. (1986), "Finding response times in real-time systems", BCS Computer Journal, 29 (5): 390–395, doi:10.1093/comjnl/29.5.390.
Sha, Lui; Goodenough, John B. (April 1990), "Real-Time Scheduling Theory and Ada", IEEE Computer, 23 (4): 53–62, doi:10.1109/2.55469

پیوند به بیرون

خط مشی مریخ Pathfinder از تحقیق @ مایکروسافت
آنچه واقعاً در مریخ روبر پاتفیندر توسط مایک جونز از The Risks Digest, Vol. 19، شماره ۴۹

[1] Liu, C. L.; Layland, J. (1973), "Scheduling algorithms for multiprogramming in a hard real-time environment", Journal of the ACM, 20 (1): 46–61, doi:10.1145/321738.321743

[2] Bovet, Daniel P.; Cesati, Marco, Understanding the Linux Kernel, http://oreilly.com/catalog/linuxkernel/chapter/ch10.html#85347 بایگانی‌شده در ۲۰۱۴-۰۹-۲۱ توسط Wayback Machine.

[3] Lehoczky, J.; Sha, L.; Ding, Y. (1989), "The rate monotonic scheduling algorithm: exact characterization and average case behavior", IEEE Real-Time Systems Symposium, pp. 166–171, doi:10.1109/REAL.1989.63567, ISBN 978-0-8186-2004-1.

[4] Enrico Bini, Giorgio C. Buttazzo and Giuseppe M. Buttazzo (2003), "Rate Monotonic Analysis: the Hyperbolic Bound", IEEE Transactions on Computers, 52 (7): 933–942, doi:10.1109/TC.2003.1214341

[5] Leung, J. Y.; Whitehead, J. (1982), "On the complexity of fixed-priority scheduling of periodic, real-time tasks", Performance Evaluation, 2 (4): 237–250, doi:10.1016/0166-5316(82)90024-4.

[6] Alan Burns and Andy Wellings (2009), Real-Time Systems and Programming Languages (4th ed.), Addison-Wesley, pp. 391, 397, ISBN 978-0-321-41745-9

[7] Lampson, B. W.; Redell, D. D. (1980), "Experience with processes and monitors in Mesa", Communications of the ACM, 23 (2): 105–117, doi:10.1145/358818.358824.

[8] Buttazzo, Giorgio (2011), Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications (Third ed.), New York, NY: Springer, p. 225

[9] "Real-Time Linux Wiki". kernel.org. 2008-03-26. Retrieved 2014-03-14.

[10] Sha, L.; Rajkumar, R.; Lehoczky, J. P. (1990), "Priority inheritance protocols: an approach to real-time synchronization", IEEE Transactions on Computers, 39 (9): 1175–1185, doi:10.1109/12.57058.

[11] Buttazzo, Giorgio (2011), Hard Real-Time Computing Systems: Predictable Scheduling Algorithms and Applications (Third ed.), New York, NY: Springer, p. 212

[12] ttp://research.microsoft.com/~mbj/Mars_Pathfinder/

[13] «نسخه آرشیو شده». بایگانی‌شده از اصلی در 5 اكتبر 2011. دریافت‌شده در 18 مه 2019. تاریخ وارد شده در |archive-date= را بررسی کنید (کمک)

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]

[۱۰]

[۱۱]

[۱۲]

[۱۳]