FreeRTOS – Rate Monotonic Scheduling

U real-time okruženju svaka milisekunda je presudna i prostora za grešku nema. Postavlja se ključno pitanje: Kako organizovati periodičneprocese tako da nijedan ne propusti svoj rok izvršavanja? Na običnom Linux-u moguće je simulirati real-time okruženje i prikazati rad RMS raspoređivača, koji obezbeđuje matematičku garanciju da će svi periodični zadaci biti završeni na vreme.

U nastavku članka biće prikazane osnovne karakteristike Rate Monotonic Scheduling algoritma i objašnjeni osnovni pojmovi za rad sa real-time sistemima. Takođe, kroz par jednostavnih simulacija biće demonstriran rad periodičnih zadataka na Linux-u pomoću FreeRTOS-a.

Pregled sadržaja

U narednim sekcijama govoriće se o:

1. Real-time operativnim sistemima (RTOS): Za početak biće predstavljene osnovne karakteristike real-time operativnih sistema. Zatim će biti objašnjeno koje vrste zadataka postoje i kako se oni raspoređuju u sistemu.
2. Rate Monotonic Scheduling-u: Najpre će biti objašnjeno kako se dodeljuju prioriteti zadacima. Zatim sledi prikaz raspoređivanja zadataka tokom izvršavanja. I na kraju sekcije, biće prikazan praktičan primer kako RMS algoritam zapravo funkcioniše.
3. FreeRTOS-u: Biće objašnjena instalacija FreeRTOS-a i priprema razvojnog okruženja. Potom sledi kod RMS algoritma i rezultati izvršavanja simulacija koji su jasno prikazani i analizirani.

Real-time operativni sistemi (RTOS)

Real-time sistemi (RTOS) predstavljaju posebnu vrstu operativnih sistema koji su dizajnirani da upravljaju procesima sa preciznim vremenskim zahtevima i visokim stepenom pouzdanosti. U ovakvim sistemima, ispravnost rezultata jeste važna, ali je presudno kada se rezultat dobija – propuštanje roka izvršavanja može imati ozbiljne posledice. Najčešće se koriste u ugrađenim sistemima (embedded system).

Osnovni cilj real-time sistema je postizanje determinističkog ponašanja, koje treba da garantuje da će sistem minimizovati vremenski interval od pojave prekida zadatka do početka njegovog opsluživanja. Ovo ponašanje se postiže tako što sistem programerima daje visok stepen kontrole nad zadacima i njihovim operacijama.

Da bi operativni sistem mogao da se klasifikuje kao „real-time„, on mora da ima poznato maksimalno vreme izvršavanja svake kritične operacije koju obavlja. Sistemi koji garantuju da će sve kritične operacije završiti u predviđenom vremenu nazivaju se „hard real-time„, dok oni koji garantuju poštovanje rokova samo većinu vremena nazivaju se „soft real-time„.

Da bi se bolje razumeli ovi koncepti, razmotriće se sledeći primeri. Srčani pejsmejker mora u precizno određenim vremenskim intervalima da generiše električne impulse kako bi održao pravilan rad srca. Kašnjenje u izvršavanju ovakvog zadatka može izazvati ozbiljne, pa i fatalne posledice po pacijenta. Stoga u ovakvom okruženju neophodan je hard real-time sistem koji će garantovati da nijedna operacija neće prekoračiti vremenske rokove.

Sa druge strane, ako se dizajnira mobilni telefon koji prima streaming video sadržaj, povremeni gubitak podataka je prihvatljiv, iako je u proseku važno da video strim bude neprekidan. Za ovu primenu, soft real-time sistem bi bio pogodniji.

Primena real-time sistema je veoma široka: sistemi za kontrolu vazdušnog saobraćaja, srčani pejsmejkeri, mrežni multimedijalni sistemi, roboti u pogonima fabrika, IoT sistemi (merenje temperature, osvetljenosti i sl.) i drugi.

Zadaci (tasks)

Zadatak (task) predstavlja pojedinačan proces izvršavanja. Drugim rečima, zadatak je određena funkcija ili proces u programu koji obavlja specifičan posao, na primer: čitanje senzora, upravljanje motorom, slanje podataka ili prikaz informacija na ekranu. Njegova osnovna karakteristika je da zahteva pravovremeno reagovanje sistema.

RTOS upravlja dvema vrstama zadataka: periodični i dinamički zadaci.

Periodični zadaci

Periodični zadaci se izvršavaju u pravilnim vremenskim intervalima, a svaki od njih se može opisati pomoću četiri osnovne karakteristike:

• Release time: Trenutak kada zadatak postaje spreman za izvršenje.
• Execution time: Procesorsko vreme koje je potrebno za izvršenje zadatka.
• Deadline: Krajnji vremenski trenutak do kog mora da se završi zadatak.
• Time period: Vremenski interval između dva release time-a.

Dinamički zadaci

Dinamički zadaci se izvršavaju u nepredvidivim vremenskim intervalima, kao odgovor na događaje. Događaji mogu da budu spoljašnje (npr. pritisak tastera) ili unutrašnje prirode (npr. uzrokovani od strane drugih procesa). Dele se na: aperiodične i sporadične zadatke.

• Aperiodični zadaci: Imaju fleksibilne rokove za izvršenje ili ih uopšte nemaju.
• Sporadični zadaci: Imaju strogo definisane rokove koje moraju da ispune.

Raspoređivač (scheduler) zadataka

Kao i kod svakog drugog operativnog sistema, unutar kernela se nalazi raspoređivač (scheduler).

Raspoređivač je mali program koji odlučuje o tome koji zadatak će se izvršavati u datom trenutku, a tu odluku donosi na osnovu prioriteta zadataka i izabrane politike raspoređivanja.

Postoje dva načina rada raspoređivača: prekidno i neprekidnoraspoređivanje.

Rate Monotonic Scheduling

Rate Monotonic Scheduling (RMS) je algoritam za određivanje prioriteta periodičnih zadataka u real-time sistemima koji koriste prekidni raspoređivač. RMS je statički algoritam, što znači da se prioriteti zadataka određuju pre početka izvršavanja i ostaju nepromenjeni tokom rada sistema.

Osnovni cilj RMS algoritma jeste da obezbedi da se svi nezavisni periodični zadaci izvrše unutar definisanih vremenskih ograničenja.

Dodeljivanje prioriteta

Algoritam (RMS) dodeljuje prioritete zadacima u skladu sa njihovim vremenskim periodom izvršavanja.

Prioritet zadatka je obrnuto proporcionalan njegovom vremenskom periodu, što zapravo predstavlja njegovu učestalost (frekvenciju) izvršavanja. Na taj način, zadatak sa najkraćim periodom ima najveći prioritet, dok zadatak sa najdužim periodom ima najmanji prioritet pri raspoređivanju.

Na grafiku je na x-osi predstavljena učestalost izvršavanja, dok je na y-osi predstavljen prioritet. Iz toga se vidi da je prioritet zadatka u monotonom odnosu sa učestalošću izvršavanja. Dakle, sa povećanjem učestalosti, dolazi i do povećanja prioriteta, i obrnuto.

Raspoređivanje zadataka

Kako bi se proverilo da li se skup zadataka može uspešno rasporediti pomoću RMS raspoređivača, uvodi se sledeća teorema.

Teorema 1: Za skup od n nezavisnih periodičnih zadataka, koji se raspoređuju pomoću Rate Monotonic algoritma, uvek će postojati izvodljiv raspored izvršavanja, tako da se svi zadaci izvrše unutar zadatog vremenskog ograničenja, ako je iskorišćenost CPU-a ispod određene granice. Testi izvodljivosti za RMS je:

\(\frac{C_1}{T_1} + \frac{C_2}{T_2} + \cdots + \frac{C_n}{T_n} \leq n(2^{1/n} – 1)\),

gde je C_i vreme izvršavanja zadatka, T_i period, a n ukupan broj zadataka. U formuli se iskorišćenost CPU-a od strane zadatka Z_ipredstavlja odnosom \(\frac{C_i}{T_i}\).

Kada broj zadataka n postane beskonačnoveliki, vrednost \(n(2^{1/n} – 1)\) postane približno jednaka ln 2, što je približno 0.69%. To je zato što:

Dakle, u sistemu sa beskonačnim brojem zadataka, RMS raspoređivač može uspešno da rasporedi sve zadatke tako da maksimalna iskorišćenost CPU-a konvergira ka 69%. Međutim, ako sistem ima konačanbroj zadataka, raspoređivač će uspešno da rasporedi zadatke samo ako je ukupna iskorišćenost CPU-a manja ili jednaka maksimalnoj iskorišćenosti CPU-a prikazanoj u tabeli ispod.

Na Tabeli 4 prikazana je maksimalna iskorišćenost procesora u zavisnosti od broja zadataka unutar sistema.

Kako funkcioniše algoritam?

(Prvi primer) Neka je dat skup sa tri periodična zadatka:

Prvo je potrebno proveriti da li se zadaci u skupu mogu uspešno rasporediti korišćenjem RMS raspoređivača. Provera se vrši pomoću formule:

U = \(\frac{C_1}{T_1} + \frac{C_2}{T_2} + \cdots + \frac{C_n}{T_n} \leq n(2^{1/n} – 1)\).

Kada se zamene vrednosti, važi da je ukupno vreme izvršavanja jednako 0.5/3 + 1/4 + 2/6 = 0.16 + 0.25 + 0.33 = 0.75. Na osnovu toga, ukupna iskorišćenost procesora iznosi 75%. Pošto je ta vrednost manja od granične vrednosti od 77%, zaključuje se da je zadatke moguće uspešno rasporediti.

Na slici 5 prikazano je raspoređivanje zadataka iz skupa prikazanog u Tabeli 1. Objašnjenje je sledeće:

1. Prema algoritmu raspoređivanja, zadatak sa kraćim periodom ima veći prioritet. Dakle, Z1 ima najveći prioritet, Z2 srednji, a Z3 najmanji prioritet. U trenutku t = 0, svi zadaci su pokrenuti. Pošto Z1 ima najveći prioritet, on se prvi izvršava, i to do t = 0.5.
2. U trenutku t = 0.5, zadatak Z2 ima veći prioritet od Z3, pa se on sledeći izvršava u trajanju od jedne jedinice vremena, do t = 1.5. Nakon što se Z2 završi, u sistemu ostaje samo Z3 koji tada počinje sa izvršavanjem i radi do t = 3.
3. Na t = 3, Z1 se ponovo pokreće, a pošto ima veći prioritet od Z3, on prekida njegovo izvršavanje i radi do t = 3.5. Nakon toga, Z3 nastavlja sa izvršavanjem svog preostalog dela.
4. Na t = 4, Z2 se ponovo pokreće i završava svoje izvršavanje, jer u tom trenutku nema drugih aktivnih zadataka u sistemu.
5. Na t = 6, Z1 i Z3 se pokreću u isto vreme, ali Z1 ima veći prioritet zbog kraćeg perioda, pa prekida Z3 i izvršava se do t = 6.5. Nakon toga, Z3 nastavlja i izvršava se do t = 8.
6. Na t = 8, Z2 se pokreće i, budući da ima veći prioritet od Z3, prekida njegovo izvršavanje i počinje sa sopstvenim.
7. Na t = 9, Z1 se ponovo pokreće i ponovo prekida Z3 da bi se izvršio prvi zadatak, zatim, na t = 9.5, Z3 nastavlja i završava svoj preostali deo.

Na isti način, izvršavanje se nastavlja prema istom obrascu.

FreeRTOS

FreeRTOS je besplatnireal-time sistem otvorenog koda koji je dizajniran da radi na mikrokontrolerima. FreeRTOS obezbeđuje osnovne funkcionalnosti real-time operativnih sistema:

• raspoređivanje,
• komunikaciju između zadataka,
• merenje vremena,
• i mehanizme sinhronizacije.

Zbog ograničenog broja funkcionalnosti, FreeRTOS se naziva još i jezgro real-time operativnih sistema (kernel RTOS) ili izvršni sistem realnog vremena (real-time executive). Ukoliko su potrebne dodatne funkcionalnosti, one se mogu dodati kao posebni moduli.

Instalacija FreeRTOS-a

• Instalacija osnovnih razvojnih alata – git, cmake, gdb.

sudo apt update
sudo apt install build-essential cmake git gdb

• Kloniranje FreeRTOS repozitorijuma.

git clone https://github.com/FreeRTOS/FreeRTOS.git --recurse-submodules

Kloniranjem repozitorijuma završena je instalacija FreeRTOS-a. Da bi se testirao Rate Monotonic algoritam unutar sistema neophodno je da pristupimo Posix_GCC folderu.

cd FreeRTOS/FreeRTOS/Demo/Posix_GCC

Posix_GCC folder predstavlja port FreeRTOS kernela za POSIX operativne sisteme (Linux, MacOS). Port omogućava da FreeRTOS radi kao običan program na računaru, koristeći POSIX funkcije za emulaciju zadataka, tajmera i prekida. Konkretno, folder Posix_GCC sadrži fajlove koji mapiraju FreeRTOS API pozive na POSIX funkcije, podešavaju kernel i primere koji su demonstrativne prirode.

Simulacije RMS algoritma

Cilj narednih simulacija jeste provera da li će sistem zaista da se ponaša u skladu sa prethodnim objašnjenjima.

Napomena: Simulacije su testirane na Ubuntu, verzije 24.04.3 LTS.

Učitavanje biblioteka

U okviru direktorijuma Posix_GCC kreiran je fajl, sa proizvoljnim nazivom – main_RMS.c. Na početku fajla učitavaju se neophodne biblioteke koje sadrže funkcije za rad sa standarnim ulazom/izlazom i FreeRTOS kernelom:

include < stdio.h >
include "FreeRTOS.h"
include "task.h"

Nakon učitanih biblioteka, definiše se struktura Task_Params, koja sadrži osnovne parametre jednog periodičnog zadatka, kao što su: naziv, vreme izvršavanja, period izvršavanja, prioritet, početno vreme izvršavanja, kao i preostalo vreme nakon prekida.

typedef struct
{
    const char *name;
    TickType_t execTime;
    TickType_t period;
    UBaseType_t priority;
    TickType_t release_time;
    TickType_t remaining_time;
} Task_Params;

Dodela prioriteta zadacima

Zadaci se sortiraju rastuće po periodu izvršavanja, tj. od najkraćeg ka najdužem. Algoritam sortiranja je implementiran pomoću jednostavnog Bubble sort-a.

Nakon sortiranja, zadaci dobijaju prioritete prema RMS pravilu: zadatak sa najkraćim periodom dobija najveći prioritet, a zadatak sa najdužim periodom najmanji.

void rms_algorithm(Task_Params *tasks, size_t numTasks)
{
    size_t i, j;
    Task_Params temp;
    for (i = 0; i < numTasks - 1; i++) {
        for (j = 0; j < numTasks - i - 1; j++) {
            if (tasks[j].period > tasks[j + 1].period) {
                temp = tasks[j];
                tasks[j] = tasks[j + 1];
                tasks[j + 1] = temp;
            }
        }
    }

    for (size_t i = 0; i < numTasks; i++) {
        tasks[i].priority = (UBaseType_t)(numTasks - i); 
    }
}

Funkcija Task

Task je funkcija koju izvršava svaka nit (task), pri čemu svaki zadatak prosleđuje svoje parametre. Kod funkcije je dat u nastavku.

void Task(void *pvParameters)
{
    Task_Params *params = (Task_Params *)pvParameters;

    for (;;)
    {
        if (params->remaining_time == 0)
            params->remaining_time = params->execTime;

        printf("| %-8s | %5lu | %5lu | Početak       |\n",
               params->name,
               (unsigned long)xTaskGetTickCount(),
               (unsigned long)params->remaining_time);

        TickType_t lastTick = xTaskGetTickCount();

        while (params->remaining_time > 0)
        {
            TickType_t currentTick = xTaskGetTickCount();

            if (currentTick > lastTick)
            {
                params->remaining_time -= 1;
            }
            
            lastTick = currentTick;
        }

        printf("| %-8s | %5lu | %5s | Kraj          |\n",
               params->name,
               (unsigned long)lastTick,
               "/");

        vTaskDelayUntil(¶ms->release_time, params->period);
    }
}

Funkcija Task ima sledeće korake:

1. Inicijalizacija parametara – funkcija prihvata ulazne vrednosti.
2. Provera preostalog vremena – ako je remaining_time nula, resetuje se na execTime.
3. Početak izvršavanja zadatka – ispisuje se početak rada i čuva se trenutni tick u varijabli lastTick.
4. Simulacija rada – unutar while petlje simulira se kontinuirani rad zadatka, proverava se prolazak tick-ova i oduzima vreme izvršavanja.
5. Završetak izvršavanja – zadatak ispisuje kraj i prelazi u blokirano stanje.
6. Periodično buđenje zadataka – kernel koristi promenljivu period za precizno planiranje sledećeg buđenja.

Glavna funkcija (main_RMS)

U glavnoj (main_RMS) funkciji se vrši inicijalizacija zadataka, dodela prioriteta i na kraju pokretanje zadataka i raspoređivača. U nastavku je data funkcija sa prethodno navedenim funkcionalnostima.

void main_RMS(void)
{
    // 1. Inicijalizacija zadataka
    Task_Params taskSet[] = {
        {"Z1", pdMS_TO_TICKS(500),  pdMS_TO_TICKS(3000), 0, xTaskGetTickCount(), 0},
        {"Z2", pdMS_TO_TICKS(1000), pdMS_TO_TICKS(4000), 0, xTaskGetTickCount(), 0},
        {"Z3", pdMS_TO_TICKS(2000), pdMS_TO_TICKS(6000), 0, xTaskGetTickCount(), 0}
    };

    const size_t numTasks = sizeof(taskSet) / sizeof(taskSet[0]);

    // 2. Sortiranje zadataka po periodu (za RMS) i dodeljivanje prioriteta
    rms_algorithm(taskSet, numTasks);


    // 3. Kreiranje zadataka
    for (size_t i = 0; i < numTasks; i++) {
        xTaskCreate(Task, 
                    taskSet[i].name, 
                    configMINIMAL_STACK_SIZE, 
                    &taskSet[i],
                    taskSet[i].priority,
                    NULL);
    }
 
    printf("\n");
    printf("+----------+-------+-------+---------------+\n");
    printf("| Zadatak  | Izvr. | Preos.| Akcija        |\n");
    printf("|          | (ms)  |(ticks)|               |\n");
    printf("+----------+-------+-------+---------------+\n");
 
    // 4. Pokretanje raspoređivača
    vTaskStartScheduler();
}

Pokretanje simulacije

Pokretanje programa se postiže kompajliranjem koda i kreiranjem izvršnog fajla pomoću komande make.

:~/FreeRTOS/FreeRTOS/Demo/Posix_GCC$ make

Izvršni fajl se nalazi u direktorijumu build/posix_demoi pokreće se pomoću sledeće komande:

:~/FreeRTOS/FreeRTOS/Demo/Posix_GCC$ ./build/posix_demo

Rezultat simulacije

Rezultat izvršavanja, dat je u sledećoj tabeli:

Objašnjenje je sledeće:

1. U trenutku t = 0, svi zadaci su pokrenuti. Prema algoritmu raspoređivanja, zadatak Z1 ima najveći prioritet, Z2 srednji, a Z3 najmanji prioritet. Pošto Z1 ima najveći prioritet, on se prvi izvršava, i to 500 jedinica vremena, odnosno do t = 500.
2. U trenutku t = 500, zadatak Z2 ima veći prioritet od Z3, pa se on sledeći izvršava u trajanju od 1000 jedinica vremena, do t = 1500. Nakon što se Z2 završi, u sistemu ostaje samo Z3, koji tada počinje sa izvršavanjem i radi do t = 3000.
3. Na t = 3000, Z1 se ponovo pokreće, a pošto ima veći prioritet od Z3, on prekida njegovo izvršavanje i radi do t = 3500. Nakon toga, Z3 nastavlja sa izvršavanjem svog preostalog dela. Međutim, zbog izvršavanja koda raspoređivača, zadatak Z3 nema na raspolaganju svih 500 jedinica vremena, što će prouzrokovati prolongiranje izvršavanja.
4. U trenutku t = 4000 zadatak Z2 se ponovo pokreće, prekida zadatak Z3 i izvršava se narednih 1000 jedinica vremena. Nakon toga, procesor ponovo preuzima zadatak Z3, koji odmah završava svoje izvršavanje jer mu je preostala jedna jedinica vremena.
5. Na t = 6000, Z1 i Z3 se pokreću u isto vreme, ali Z1 ima veći prioritet zbog kraćeg perioda, pa prekida Z3 i izvršava se do t = 6500. Nakon toga, Z3 nastavlja i izvršava se do t = 8000.
6. Na t = 8000, Z2 se pokreće i, budući da ima veći prioritet od Z3, prekida njegovo izvršavanje i počinje sa sopstvenim.
7. Na t = 9000, Z1 se ponovo pokreće i prekida Z2, zatim, na t = 9500, Z1 ispisuje poruku o završetku, a nakon toga Z2 dobija procesor i izvršava preostalu jednu jedinicu vremena u kojoj ispisuje poruku o završetku. Potom, Z3 nastavlja svoj rad i završava svoj preostali deo.

Simulacija gotovo u potpunosti prati teorijski opis izvršavanja zadataka. Međutim, javljaju se mala kašnjenja jer se, osim zadataka, u simulaciji izvršava i raspoređivač.

(Drugi primer) Sledeći primer pokazuje ponašanje sistema kada zadaci ne mogu uspešno da se rasporede pomoću RMS algoritma.
Neka je dat sledeći skup zadataka:

Razlika u odnosu na prethodni skup jeste u tome što zadatak Z1 ima duže vreme izvršavanja (Execution time).

Primenom formule dobija se da je ukupno vreme iskorišćenja procesora jednako 1/3 + 1/4 + 2/6 = 0.33 + 0.25 + 0.33 = 0.92, odnosno 92%. Pošto je ta vrednost veća od granične vrednosti od 77%, zaključuje se da zadatke nije moguće uspešno rasporediti.

Ova pretpostavka može da se dokaže u simulaciji.

Izmene u kodu podrazumevaju isključivo izmene parametara zadataka.

void main_RMS(void)
{
    // 1. Inicijalizacija zadataka
    Task_Params taskSet[] = {
        {"Z1", pdMS_TO_TICKS(1000),  pdMS_TO_TICKS(3000), 0, xTaskGetTickCount(), 0},
        {"Z2", pdMS_TO_TICKS(1000), pdMS_TO_TICKS(4000), 0, xTaskGetTickCount(), 0},
        {"Z3", pdMS_TO_TICKS(2000), pdMS_TO_TICKS(6000), 0, xTaskGetTickCount(), 0}
    };

    const size_t numTasks = sizeof(taskSet) / sizeof(taskSet[0]);

    // 2. Sortiranje zadataka po periodu (za RMS) i dodeljivanje prioriteta
    rms_algorithm(taskSet, numTasks);


    // 3. Kreiranje zadataka
    for (size_t i = 0; i < numTasks; i++) {
        xTaskCreate(Task, 
                    taskSet[i].name, 
                    configMINIMAL_STACK_SIZE, 
                    &taskSet[i],
                    taskSet[i].priority,
                    NULL);
    }
 
    printf("\n");
    printf("+----------+-------+-------+---------------+\n");
    printf("| Zadatak  | Izvr. | Preos.| Akcija        |\n");
    printf("|          | (ms)  |(ticks)|               |\n");
    printf("+----------+-------+-------+---------------+\n");
 
    // 4. Pokretanje schedulera
    vTaskStartScheduler();
}

Izlaz simulacije je dat u tabeli ispod:

Objašnjenje je sledeće:

1. U trenutku t = 0, svi zadaci su pokrenuti. Prema algoritmu raspoređivanja, zadatak Z1 ima najveći prioritet, Z2 srednji, a Z3 najmanji prioritet. Pošto Z1 ima najveći prioritet, on se prvi izvršava, i to 1000 jedinica vremena, odnosno do t = 1000.
2. U trenutku t = 1000, zadatak Z2 ima veći prioritet od Z3, pa se on sledeći izvršava u trajanju od 1000 jedinica vremena, do t = 2000. Nakon što se Z2 završi, u sistemu ostaje samo Z3, koji tada počinje sa izvršavanjem i radi do t = 3000.
3. Na t = 3000, Z1 se ponovo pokreće, a pošto ima veći prioritet od Z3, on prekida njegovo izvršavanje i radi do t = 4000.
4. U trenutku t = 4000 zadatak Z2 se ponovo pokreće i završava svoje izvršavanje u t = 5000. Nakon toga, zadatak Z3 ponovno preuzima procesor i u tom trenutku ima preostalih 1000 jedinica za izvršavanje.
5. Na t = 6000, Z1 i Z3 se pokreću u isto vreme, ali Z1 ima veći prioritet zbog kraćeg perioda, pa prekida Z3 i izvršava se do t = 7000. Nakon toga, Z3 dobija procesor i ispisuje poruku o završetku rada. Međutim, ovde nastaje problem. Zadatak Z3 je propustio svoj rok (deadline).

Na osnovu prethodne simulacije, dokazuje se da zadaci koji se raspoređuju prema RMS algoritmu ne mogu uspešno da se izvrše ukoliko ne zadovoljavaju prethodno opisanu teoremu (Teorema 1).

Kompletan kod se nalazi u sledećem GitHub repozitorijumu.

Rezime

U članku su predstavljeni osnovni koncepti real-time operativnih sistema, uključujući tipove zadataka i njihove načine raspoređivanja. Objašnjen je RMS algoritam i prikazana je njegova praktična primena u FreeRTOS simulatoru. Simulacije demonstriraju situacije u kojima sistem može/ne može uspešno da izvrši zadatke čiji su prioriteti dodeljeni putem algoritma.

Reference

Autor: Miloš Đuričić

Student završne godine Informatike na Prirodno-matematičkom fakultetu Univerziteta u Kragujevcu.

Linkedin | Github