زمانبند Rate-monotonic

تغییرمسیر به:

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

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

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

معرفی

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

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

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

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

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

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

که در این رابطه الگو:Mvar زمان مورد نیاز وظیفه i ام برای پردازش است، الگو:Mvar دوره آزادسازی پردازه iام  است که مهلت پایان آن یک دوره بعد است ، و الگو:Mvar تعداد فرایندهای برنامه ریزی شده است. به عنوان مثال، الگو:Mvar برای دو فرایند است.

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

$\underset{n\to \mathrm{\infty }}{\lim }n(\sqrt[n]{2}-1)=\ln 2\approx 0.693147\dots$

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

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

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

$\prod _{i=1}^n(U_i+1)\le 2$

که در این رابطه الگو:Mvar کارایی پردازنده برای هر وظیفه است.

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

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

علاوه بر این، زمانبندی مونوتنیک ضرب‌العجل زمانی مطلوب است که ضرب‌العجل کمتر از دوره باشد. الگوریتم 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	1	8
P2	2	5
P3	2	10

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

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

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

$U=3(2^{\frac{1}{3}}-1)=0.77976\dots$

از آنجاییکه $0.725<0.77976\dots$ سیستم مطمئناً قابل برنامه ریزی است

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

مطالعه بیشتر

• الگو:Citation .
• الگو:Citation الگو:Citation
• الگو:Citation ، فصل 6
• الگو:Citation .
• الگو:Citation

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

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