Кіріспе

Компьютерлік ғылымдағы жоспарлау техникасы
Компьютерлік ғылымда жылдамдық монотонды жоспарлау (RMS) — статикалық басымдық жоспарлау класы бар нақты уақыт операциялық жүйелерінде (RTOS) қолданылатын басымдық тағайындау алгоритмі. Статикалық басымдықтар тапсырманың орындалу периодына сәйкес тағайындалады, сондықтан орындалу периоды қысқа болса, тапсырманың басымдығы жоғары болады. Бұл операциялық жүйелер көбінесе үзіліске қабілетті және жауап беру уақыты бойынша детерминистік кепілдіктерге ие. Жылдамдық монотонды талдау осы жүйелермен бірге нақты қолданба үшін жоспарлау кепілдіктерін қамтамасыз ету үшін қолданылады.

Кіріспе

Жай монотонды бағалау талдауының қарапайым нұсқасы жіптердің келесідей қасиеттерге ие болуын болжайды:

Ресурстарды бөлісу жоқ (процестер ресурстарды бөліспейді, мысалы, аппараттық ресурс, кезек немесе кез келген түрдегі семафор – тоқтату немесе тоқтатусыз (күту циклі))
Детерминистік мерзімдер кезеңдерге дәл тең
Статикалық басымдықтар (іске қосыла алатын ең жоғары статикалық басымдыққа ие тапсырма бірден басқа барлық тапсырмаларға басымдық береді)
Статикалық басымдықтар монотонды бағалау конвенцияларына сәйкес тағайындалады (қысқа кезеңдері/мерзімдері бар тапсырмаларға жоғары басымдық беріледі)
Контексттік ауысу уақыты және басқа жіп операциялары тегін және модельге әсер етпейді.

Бұл жабық жүйеде кезеңдердің есептелген симуляциясын қамтитын математикалық модель, онда дөңгелек кезеңді және уақытты бөлісу кестелері басқа жағдайда жоспарлау қажеттіліктерін қанағаттандыра алмайды. Монотонды бағалау кестесі жүйедегі барлық жіптердің жұмыс істеуін модельдеуді қарастырады және сұрақ туындаған жіптер жинағы үшін кепілдіктерді орындау үшін қанша уақыт қажет екенін анықтайды.

Оптималдылық

Берілген болжамдар бойынша жылдамдық бойынша монотонды басымдық тағайындау оңтайлы, яғни егер кез келген статикалық басымдыққа ие жоспарлау алгоритмі барлық уақыт шектерін сақтаса, онда жылдамдық бойынша монотонды алгоритм де сақтай алады. Егер кезеңдер мен уақыт шектері тең болса, мерзімдік монотонды жоспарлау алгоритмі де оңтайлы болады, шындығында бұл жағдайда алгоритмдер бірдей; сонымен қатар, мерзімдік монотонды жоспарлау уақыт шектері кезеңдерден кем болғанда оңтайлы. Уақыт шектері кезеңдерден үлкен болуы мүмкін тапсырмалар моделі үшін, Аудсли алгоритмі осы модель үшін дәл жоспарлану тестімен қамтамасыз етілген оңтайлы басымдық тағайындауды ұсынады.

Ең төменгі жоғарғы шек

n кезеңдік тапсырмалар жиынтығы үшін, егер процессордың (CPU) жүктемесі белгілі бір шектен төмен болса (тапсырмалар санына байланысты), барлық мерзімдерді сақтауға мүмкіндік беретін кесте бар екені дәлелденді. RMS-тің жоспарлану тесті:

мұнда U – жүктеме коэффициенті, Ci – i процесінің есептеу уақыты, Ti – i процесінің шығарылу кезеңі (мерзімі бір кезеңнен кейін), ал n – жоспарланатын процестердің саны. Мысалы, екі процесс үшін U ≤ 0,8284. Процестер саны шексізге жақындағанда, бұл өрнек:

Сондықтан, шамамен алғанда, егер жалпы процессордың жүктемесі, U, 70%-дан кем болса, RMS барлық мерзімдерді орындай алады. Қалған 30% процессорлық қуатты төменгі басымдылықтағы, нақты уақытқа қатысты емес тапсырмаларға жұмсауға болады. n-нің кіші мәндері үшін немесе U осы шамаға жақын болған жағдайда, есептелген жүктеме шегі қолданылуы керек. Іс жүзінде, процесс үшін Ci ең нашар жағдайды (яғни ең ұзақ) есептеу уақытын, ал Ti барлық өңдеуді орындау қажет ең нашар жағдайдың соңғы мерзімін (яғни ең қысқа кезеңді) көрсетеді.

Гармоникалық тапсырмалар жиынтығының жоғарғы шегі

Лю мен Лейланд бұл шектің 1.0 ең жоғары мүмкін мәніне дейін босатылуы мүмкін екенін атап өтті, егер тапсырмалар үшін , мұнда және , - бүтін санға еселенсе, яғни барлық тапсырмалардың периоды ең қысқа периодтың, , еселігі ғана емес, сонымен қатар кез келген тапсырманың периоды барлық қысқарақ периодтардың еселігі болса. Бұл үйлесімді тапсырмалар жиынтығы деп аталады. Мысалы: Лю мен Лейланд әрқашан үйлесімді тапсырмалар жиынтығын алу мүмкін емес екенін мойындайды және практикада басқа жеңілдету шаралары, мысалы жұмсақ уақыт шектері бар тапсырмалар үшін буферлеу немесе жоғары шекті рұқсат ету үшін динамикалық басымдық тағайындау тәсілі қолданылуы мүмкін.

Стохастикалық шектер

Кездейсоқ түрде жасалған мерзімді тапсырмалар жүйесінің көбінесе 88% немесе одан төмен пайдалану шамасында барлық уақыт шектеріне сәйкес келетіні дәлелденді, бірақ бұл факт нақты тапсырма статистикасын (кезеңдер, уақыт шектері) білуге байланысты, және барлық тапсырмалар жиыны үшін мұндай статистиканы кепілдеу мүмкін емес. Кейбір жағдайларда авторлар пайдалану шамасы Лю және Лейланд ұсынған ең жоғарғы шекке жеткенін анықтады.

Ресурстарды ортақтастыру

Көптеген практикалық қолданбаларда ресурстар ортақ пайдаланылады және өзгертілмеген RMS басымдық инверсиясы және тұйықталу қатеріне тап болады. Іс жүзінде, бұл алдын алуды өшіру арқылы немесе басымдық мұрагерлігі арқылы шешіледі. Балама әдістерге құлыптамасыз алгоритмдерді пайдалану немесе әртүрлі басымдықтарға ие жіптер арасында мутекс/семафорды ортақ пайдаланудан қашу жатады. Осылайша, ресурстардың қақтығысы бастапқыда болмайды.

Алдын ала сатып алуды рұқсатсыз ету

Нақты уақыт ядросында CPU үзілістерін тоқтатуға арналған OS ENTER CRITICAL және OS EXIT CRITICAL примитивтері, мысалы, MicroC/OS II, сондай-ақ құрылғы үзілістерін біртіндеп тоқтатуға арналған splx примитивтері отбасы (FreeBSD 5. x/6. x).

Қызмет ретімен айналысуды тоқтату

Барлық үзіліс қызметтік процедуралары (ISR), олардың қатаң уақыт талабы болсын болмасын, ISR-лердің жоспарлаушымен басқарылатын барлық тапсырмалардан жоғары басымдыққа ие болған жағдайларда, жоспарлану мүмкіндігін анықтау үшін RMS талдауына енгізілуі тиіс. Егер оның өңдеу периоды ең қысқа ISR емес процестен қысқа болса, ISR-ге RMS ережелеріне сәйкес дұрыс басымдық берілген болуы мүмкін. Дегенмен, өңдеу периоды/мерзімі кез келген маңызды мерзімі бар ISR емес процестен ұзын болса, онда RMS бұзылады және тапсырмалар жинағының жоспарлану мүмкіндігін анықтау үшін есептелген шекараларды пайдалануға кедерес келтіреді.

Басымдықты дұрыс емес ISR-ді азайту

Дұрыс басымдықталмаған ISR-ді азайтудың бір жолы – мүмкін болса, ISR кезеңін ең қысқа кезеңге теңдестіріп талдауды реттеу. Бұл қысқа кезеңді қолдану RMS-ке сәйкес басымдыққа ие болуды қамтамасыз етеді, бірақ ISR үшін де, демек, жалпы жүктеме үшін де жоғары жүктеме коэффициентіне әкеледі, бұл рұқсат етілген шектен төмен болуы мүмкін, сондықтан жоспарлануды дәлелдеуге болады. Мысал ретінде, 500 микросекундық есептеу уақыты және 4 миллисекундық кезеңі бар аппараттық ISR-ді қарастырайық. Егер ең қысқа жоспарлаушы басқаратын тапсырманың кезеңі 1 миллисекунд болса, онда ISR-дің басымдығы жоғарырақ, бірақ жылдамдығы төмендейді, бұл RMS-ті бұзады. Жоспарлануды дәлелдеу үшін ISR үшін жүктеме коэффициентін орнатып, қайта есептеңіз (бұл сонымен қатар жалпы жүктеме коэффициентін арттырады). Бұл жағдайда жүктеме коэффициенті өзгеріп, болады. Бұл жүктеме коэффициенті тапсырмалар жиынтығының жалпы жүктемесін есептегенде және жоспарлануды дәлелдеу үшін жоғарғы шекпен салыстырғанда қолданылады. ISR кезеңін реттеу тек талдау үшін ғана екенін, ал ISR-дің нақты кезеңі өзгермейтінін атап өткен жөн. Дұрыс басымдықталмаған ISR-ді азайтудың тағы бір жолы – ISR-ді жаңа семафорды/мьютексті орнату үшін ғана пайдалану, ал көп уақытты қажет ететін өңдеуді RMS арқылы дұрыс басымдықталған жаңа процеске көшіру, ол жаңа семафорда/мьютексте тоқталады. Жоспарлануды анықтау кезінде ISR қызметіне байланысты CPU жүктемесінің ең төменгі жоғарғы шегінен шегерілуі керек. Жүктемесі өте аз ISR-лерді ескермеуге болады.

Гармоникалық тапсырмалар жиынтығын талдау

Себебі, 2- және 3-тапсырмаларды үйлесімді тапсырмалардың кіші жиынтығы деп қарастыруға болады. 1-тапсырма өздігінен үйлесімді тапсырмалардың кіші жиынтығын құрайды. Сондықтан, үйлесімді тапсырмалардың кіші жиынтықтарының саны, K, 2-ге тең. Жоғарыда есептелген жалпы жүктеме коэффициентін (0,81875) пайдалану арқылы, жүйенің орындалатыны анықталды.