Ai : زمان ورود یک وظیفه غیر تناوبی
Di : سررسید هر وظیفه
DMS : الگوریتم زمانبندی سررسید یکنواخت
در هر دو حالت تناوبی و غیرتناوبی، وظایف قابل دسترسی که اولویت بالاتری داشته باشند، پردازش می‌شوند.
الگوریتم RBound-FF :
Rbound یک شرایط قابل زمانبندی تک پردازنده‌ای برای RMS است، که با بهره گرفتن از دوره‌تناوب وظایف تناوبی، بهره‌وری بالایی برای پردازنده ایجاد میکند. مجموعه وظایف ورودی T با m وظیفه، بوسیله Rbound شدن، مطابق الگوریتم scale task set که در شکل ۳-۹ آورده‌شده است، تبدیل به مجموعه T’ میشود. این الگوریتم، مجموعه وظایفی را پیدا میکند که نسبت حداکثر و حداقل دوره تناوب‌هایش، کمتر از ۲ باشد. در واقع یک اجازه‌ای بر اساس Rbound برای T’ صادر میشود. R را به عنوان نسبت کمترین به بیشترین دوره تناوب بین همه وظایف در سیستم تعریف می‌کنیم. بنابراین با r<2 در پایان الگوریتم برای m وظیفه داریم:
(۶) -۱) + URbound (r,m) = (m-1)(
Rbound می‌گوید که اگر T’ خروجی الگوریتم ScaleTaskSet باشد و عبارت
(۷) ≤ URbound (r,m)
برقرار باشد(r= )، آنگاه T یک مجموعه وظیفه قابل زمانبندی روی یک تک پردازنده بوسیله RMS است.
Scale TaskSet(Input: T)
Begin
Sort the tasks in T by increasing period
While T1 ≤ Tm /۲
Ci = ۲ Ci
Ti = ۲ Ti
Sort the task in T by increasing period
End while
Return (T’)
end
شکل ۱۲شکل ۳-۹ الگوریتم ScaleTaskSet [35]
شکل ۳-۹ الگوریتم ScaleTaskSet ]35[
جزبندی با Rbound :
بیشتر الگوریتم‌های پیشنهاد شده با RMS اولویت‌دار، براساس جزبندی‌کردن هستند، بنابراین زمانبندی عمومی با RMS اولویت‌دار میتواند بازده کمی در بدترین حالت روی بهره‌وری پردازنده داشته باشد. استراتژی جزبندی شامل دو قسمت زیر است:
-
- تخصیص دادن وظایف به هسته‌ها
-
- زمانبندی وظایف روی هر پردازنده
در الگوریتم RBound ، زمانی که r مربوط به هر وظیفه، به عدد ۱ نزدیک میشود، این نوع وظایف به هسته یکسانی فرستاده می‌شوند، در نتیجه بهره‌وری پردازنده به ۱۰۰ درصد میرسد (صرف نظر از تعداد وظایف). برای نزدیک شدن r به ۱ باید وظایفی که نزدیکترین دوره تناوب را دارند، در مجموعه وظایف مندرج شده T’ قرار داد شوند و این کار با مرتب‌کردن وظایف در T’ براساس افزایش دوره تناوب و سپس فرستادن وظایف به پردازنده با روش‌های Next-Fit و یا First-Fit امکان‌پذیر میباشد. در اینجا برای وظایف تناوبی از روش First-Fit استفاده شده است، زیرا First-Fit به خاطر جستجو در یک مجموعه جهانی[۱۳۶] از بین پردازنده‌های جستجو شده بوسیله Next-Fit ، بهتر از Next-Fit عمل میکند. در سیستم‌هایی با وظایف تناوبی، عمل تخصیص وظایف، زمانی اتفاق می‌افتد که یک وظیفه جدیدی بوجود می آید. به هر حال RBound-FF وقتی که مجموعه وظایف تناوبی سیستم، بر اساس دوره تناوب، مرتب شوند، میتواند بیشترین بهره‌وری پردازنده را به ما بدهد. بنابراین در اینجا فقط وظایف تناوبی، در مرحله مقداردهی اولیه وظیفه، به هسته‌های مناسب محدود می‌شوند و سپس وقتی که این وظایف به طور کامل ایجاد شدند، به هسته‌ها اختصاص مییابند.
RBound-FF_init(Input: T,p)
Begin
ScaleTaskSet(T , T’)
For (i=1 ; i≤m ,i++)
For (j=1 ; j≤pn ; j++)
If ( τi can be admitted by Rbound an pj )
Bound τi to pj
Else
If (j== pn) return(REJECT)
Endif
Endfor
Endfor
Return(ACCEPT)
end
شکل ۳-۱۰ شبه کد الگوریتم RBound-FF ]35[
شکل ۱۳شکل ۳-۱۰ شبه کد الگوریتم RBound-FF [35]
بهره‌وری RBound برای وظایف غیرتناوبی:
برای وظایف غیرتناوبی، مجموعه V(t) به عنوان مجموعه همه وظایف درگیری که وارد شده‌اند، اما سررسیدشان سپری نشده است، به صورت زیر تعریف می‌شوند:
V(t) = { Ti | Ai ≤ t < Ai + Di } (۸)
S(t) که زیرمجموعه V(t) است، شامل فقط وظایفی در V(t) است که بعداز شروع آخرین دوره تناوب زمان بیکاری پردازنده، وارد شوند. و در نهایت می‌رسیم به تعریف بهره‌وری ترکیبی که عبارت انداز:
