SISTEMI REALNOG VREMENA
Operativni sistem realnog vremena
(RTOS)
Raspoređivanje procesa
Vanr.prof. Dr. Lejla BanjanovićMehmedović
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
1
Šta je operativni sistem?
•
•
•
•
OS je skup softverskih proizvoda koji udruženo
kontrolišu sistemske resurse i procese unutar jednog
računara
OS je program koji se izvršava svo vrijeme na
računaru sa svim drugim postojećim aplikacionim i
sistemskim programima
OS je program koji nadgleda računarski hardver
Predstavlja bazu za izvršavanje aplikacionih programa
i čini posrednika između računarskog hardvera i
računarskog korisnika.
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
2
Real-Time Operativni sistemi

Ukoliko kontrola rada zadovoljava skup
specificiranih vremenskih ograničenja,
operativni sistem se zove Real-Time
Operativni Sistem (RTOS).
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
3
Tipovi operativnih sistema


Real-time operativni sistemi (npr. let aviona,
kontrolni algoritam koji se izvršava 40 puta/sec)
Ne real-time operativni sistemi (npr. rezervacija
avionskih karata)
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
4
Tipovi operativnih sistema



Statički operativni sistemi (broj taskova mora biti
tačno definisan prije vremena izvršenja i nema
promjena)
Dinamički operativni sistemi (broj taskova nije
unaprijed poznat, kreiraju se i uništavaju u toku rada
sistema)
Real-time aplikacije operativnih sistema su
često ugrađene (embedded), jer su storirane u ROMu kompjuterskog sistema, koji je dio većeg sistema,
=> real-time sistemi statički.
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
5
Funkcije Real-Time Operativnog
sistema
•
RTOS je dio softvera, koji implementira sljedeće
funkcije:
•
•
•
Raspoređivanje procesa (Task scheduling)- određuje
koji proces će se izvršavati
Uzajamno isključenje procesa (Task dispatching) - vrši
neophodne pripreme za početak izvođenja zadatka, problem
kritične sekcije
Komunikacija između procesa (Intertask
communication) – prenos podataka i sinhronizacija
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
6
Real-time OS
•
•
Najveći broj slučajeva: OS Kernel se
podudara sa Real-Time OS
RTOS omogućava kontrolu pri raspodjeli
vremena dopuštajući nam manipulaciju
procesima u zavisnosti koji proces ima prioritet.
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
7
Real-Time Operativni sistemi


Tipični RTOS sistemi rješavaju kompleksne
probleme dekompozicijom u veći broj manjih
jednostavnijih zadataka, tzv. taskova.
Nekoliko važnih aspekata multitasking dizajna
podrazumjevaju:




raspoređivanje izvršenja taskova
djeljenje resursa između taskova
sinhronizaciju taskova
razmjenu/djeljenje podataka između taskova
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
8
Šta je proces?



Program - pasivna, statična sekvenca instrukcija, koja
može predstavljati hardverske i softverske resurse
sistema.
Stvarno izvršenje programa je aktivni, dinamički događaj,
kod kojeg se različita svojstva mjenjaju sa vremenom pri
izvršenju instrukcije.
Proces (često se naziva i task u nekim ugrađenim
sistemima) se kreira od strane OS–a, kako bi objedinio
sve informacije, koje su uključene pri izvršenju
programa ( i stek i izvorni kod i podatke). Ovo znači da
je program samo dio taska.
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
9
OS proces
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
10
Unitask - multitasking
okruženje

Ugrađeni OS sistemi upravljaju kompletnim
ugrađenim softverom koristeći taskove, ili u
unitasking ili multitasking okruženju.
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
11
Multitasking sistemi


Zasebni procesi djele jedan procesor ili više procesora
Svaki proces se izvršava unutar vlastitog okvira





Posjeduje procesor
Vidi vlastite varijable
Može biti interaptiran
Procesi mogu interreagovati u cilju izvršenja
kompletnog programa
Primjer Multitasking sistema - softver navigacionog
sistema
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
12
Multitasking sistemi
•
•
•
•
Promjena sadržaja (Context switching) – kada CPU
prelazi sa obrade jednog procesa na drugi
Proces čuvanja MINIMALNIH informacija o real-time
procesima kako bi se isti procesi mogli ponovo
postaviti za izvođenje nakon sto su prekinuti (primjer
knjige: ime, strana, paragraf, riječ...)
U toku promjene sadržaja, interapti su onemogućeni
Real-Time sistemi zahtjevaju minimalno vrijeme za
promjenu sadržaja
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
13
Multitasking OS
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
14
Thredovi



Neki multitask operativni sistemi obezbjeđuju
tzv. thread-ove.
Thread je sekvencijalno izvršivi stream unutar
vlastitog taska; thread je ograničen taskom
Ovisno o OS-u, task može posjedovati 1 ili
više threadova.
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
15
Taskovi i thredovi
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
16
Multitasking i upravljanje
procesima
Raspodjela taskova
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
17
Raspoređivanje procesa


Raspoređivač (eng. sheduler) je komponenta
operativnog sistema koja “rukuje” preusmjeravanjem
(switching) sa jednog taska na druge taskove.
Ključni faktori koji utiču na efektnost i perfomanse
algoritma raspoređivanja:
 Prioritet
 Vrijeme kompletiranja taska
 Propusnost
 Vrijeme čekanja
 Vrijeme odgovora
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
18
Task model

1.
2.
3.
4.
Moguća stanja procesa:
Spreman (Ready)
Izvršavanje (Executing)
Obustavljeno
(Suspended)
Neaktivan,mirujući
(Dormant)
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
19
Task-Control Block Model

•
•
Task Control Block (TCB) ili Process
Control Block (PCB)
Najpopularnija metoda za implementaciju
komercijalnih, potpuno opremljenih, real-time
operativnih sistema
Glavna mana task-control blok modela jeste u
tome kada je veliki broj modela zadataka
kreiran, dodatak raspoređivača uzima puno
procesorskog (CPU) vremena!
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
20
TCB model
•
•
•
Svaki task (proces) opisan je sa:
• Startna adresa taska
• Identifikacijskim stringom ili brojem
• Startna adresa i veličina steka
• Sadržajem (kontekstom)
• Statusom i
• Prioritetom ako je primjenjiv
Struktura Task-control block (ili TCB)
Linkana lista
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
21
Struktura TCB modela
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
22
Linkane liste
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
23
Task menadžment
•
•
•
•
•
OS – odgovoran za održavanje linkane liste svih TCB i
spremnih i suspendovanih zadataka
OS provjerava listu spremnih TCB => od trenutno
izvršnog zadatka trenutni zadatak pomaknut prema
kraju ready liste
Novi zadatak je uklonjen sa ready liste i u izvršnom je
stanju
OS – određuje novi raspored i provjeravanje statuse
svih resursa u suspendiranoj listi
Ako resurs postane raspoloživ prema zadatku na
čekanju, tada su tabele resursa ažurirane i zadatak je
pomaknut iz suspendirane liste prema ready listi.
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
24
Dijagram stanja taskova
•
Promjena sadržaja (Context switching) kada CPU
prelazi sa obrade jednog procesa na drugi
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
25
Tranzicije





Novi -> Spreman: task poslat u red čekanja i
raspoređen za izvršenje;
Spreman -> Izvršenje: na onovu kernelovog
algoritma raspoređivanja, task selektovan za izvršenje;
Izvršenje -> Spreman: task je izvršen što se tiče
CPU-a i vraćen u red čekanja za sljedeći put;
Izvršenje -> Blokiran: može se desiti neki događaj
koji će pomjeriti task u red Blokade, sve dok se ne desi
novi događaj, tj. dok ne bude razrješen problem
Blokiran -> Izvršenje: blokirani task čeka na
izvršenje te kad se desi događaj prebacuje se u red
Spreman.
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
26
Real-Time strategije
raspoređivanja procesa
•
•
•
•
•
Sistemi prozivke (eng. POLLED LOOP
systems)
Sistemi vođeni prekidom (INTERRUPT
DRIVEN systems)
Multitasking sistemi
Foreground/ Background sistemi
Potpuno opremljeni real-time sistemi (eng.
FULL-FEATURED)
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
27
Sistemi prozivke
•
•
•
Najjednostavniji real-time kerneli
Ponavljajući set instrukcija koriste se za testiranje
zastavice(flag), koja pokazuje da li se neki događaj
desio.
Kako postoji samo jedan proces, nije potrebno imati
raspoređivanje procesa i međusobnu komunikaciju
između procesa
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
28
Sistemi prozivke
Prednosti:


Jednostavne za implementiranje i debagiranje
Lako odrediti vrijeme odziva
Mane:



Troše CPU vrijeme, posebno kada se događaj
javlja rijetko
Nisu dovoljne za rukovanje komplikovanim
sistemima
Često mogu pogriješiti, jer razvoj događaja nije
uzet u obzir
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
29
Sistemi vođeni prekidom





Različiti procesi u sistemu su raspoređeni preko hardverskog ili
softverskog interrupta, dok se uzajamno isključenje izvodi pomoću
rutina za rukovanje interaptima.
Konkurentne aplikacije koriste interapte, koji mogu biti trigerovani
eksternim uređajima ili građeni pomoću tajmera.
Eksterni interapti – koriste se za reagovanje na eksterne senzore
(brojanje tikova iz enkodera).
Vremenski interapti se koriste za implementaciju periodično
ponavljajućih taskova sa fiksnim vremenskim okvirom, kao što su
kontrolne rutine motora.
Ponekad se interapti aktiviraju softverom umjesto hardverskim
uređajem. Najvažniji od softverskih interapta su vremenski
interapti, koji se dešavaju u regularnim vremenskim intervalima.
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
30
Sistemi vođeni prekidom
void timer()
{ AUBeep(); /* background task */
}
int main()
{ TimerHandle t; int i=0;
t = OSAttachTimer(100, timer);
/* foreground task: loop until key press */
while (!KEYRead()) LCDPrintf("%d\n", i++);
OSDetachTimer(t);
return 0;
}
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
31
Multitasking raspoređivanje
procesa

Postoje dva osnovna koncepta
algoritma raspoređivanja, koji se
implementiraju u ugrađenim OS
sistemima:


Ne-preduhitrivi algoritmi (non-preemptive)
Preduhitrivi algoritmi (Preemptive)
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
32
Ne-preduhitrivi algoritmi



Prvi došao – prvi servisiran, izvršiv do
kompletiranja (First Come- First Serve FCFS)/
Run-To Completion
Najkraći proces slijedeći, izvršiv do
kompletiranja (Shortest Process Next (SPN)
Run-To-Completion)
Kooperativni (Cooperative)
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
33
Prvi došao – prvi servisiran
Tekući
task
TN


T2
T1
Raspoređivač
Master CPU
Pozivi statičkim redom procesa
Prednost:


T3
Jednostavan za implementaciju (intenzivno se koristi u
kompleksnim sistemima, sigurnosno kritičnim)
Mana


Nije efikasan u sveopštoj upotrebi CPU procesiranja
Ne obezbjeđuje optimalno vrijeme odgovora
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
34
Najkraći proces slijedeći
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
35
Kooperativni raspoređivač
Tekući
task
TN
T3
T1
T2
T1 T2
Raspoređivač
Master CPU
Samo tekuće izvršivi task može
forsirati promjenu sadržaja prije
kompletiranja

Kooperativni znači da se svaki paralelni task treba
“dobro ponašati” i izvršavati transfer kontrolu
eksplicitno prema sljedećem thread-u koji čeka.
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
36
Kooperativni raspoređivač












#include "eyebot.h"
#define SSIZE 4096
struct tcb *task1, *task2;
void mytask()
{ int id, i;
id = OSGetUID(0); /* read slave id no. */
for (i=1; i<=100; i++)
{ LCDPrintf("task %d : %d\n", id, i);
OSReschedule(); /* transfer control */
}
OSKill(0); /* terminate thread */
}
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
37
Kooperativni raspoređivač





int main()
{ OSMTInit(COOP); /* init multitasking */
task1 = OSSpawn("t1", mytask, SSIZE, MIN_PRI, 1);
task2 = OSSpawn("t2", mytask, SSIZE, MIN_PRI, 2);
if(!task1 || !task2) OSPanic("spawn failed");
OSReady(task1); /* set state of task1 to READY */
OSReady(task2);
OSReschedule(); /* start multitasking */
/* --------------------------------------------*/
/* proc. returns HERE, when no READY thread left */
LCDPrintf("back to main");
return 0;








};
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
38
Kooperativni raspoređivač











Sistemski izlaz:
task 2 : 1
task 1 : 1
task 2 : 2
task 1 : 2
task 2 : 3
task 1 : 3
...
task 2 : 100
task 1 : 100
back to main
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
39
Preduhitrivi algoritmi



Round Robin/prvi došao-prvi obrađen (FIFOFirst In, First Out) raspoređivač
Preduhitrivi Prioritetni (Priority Preemptivni)
raspoređivač
EDF (Earliest deadline First/Clock Driven
Scheduling) raspoređivač
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
40
Round – Robin sistemi
•
•
•
Nekoliko procesa se izvodi sekvencijalno do završetka.
Svaki proces koji se izvodi je određen fiksnim
vremenskim iznosom.
Proces se izvodi
•
•
•
dok se ne završi ili
dok ne istekne njegovo vrijeme izvršenja izdavanjem clock
interapta.
Ako se proces nije izvršio do kraja, njegov sadržaj se
mora sačuvati. Proces se tada premješta na kraj liste
gdje se nalaze procesi za izvršavanje.
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
41
Round – Robin sistemi
t1 [t2, t3]
t2 [t3, t1]
t3 [t1, t2]
...
Vremenski raspored 3 taska (procesa)
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
42
Preduhitrivi prioritetni sistemi
•
•
•

Za procese višeg prioriteta se kaže da su
preduhitrivi (preemptivni) u odnosu na
procese nižeg prioriteta ako oni prekidaju
procese nižeg prioriteta.
Proces nižeg prioriteta se i dalje izvodi dok se
proces višeg prioriteta priprema za početak
Sistemi koji ovo koriste umjesto Round-Robin
odlučivanja zovu se preduhitrivi prioritetni sistemi
Prioriteti interapta mogu biti

Fiksni ili dinamični
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
43
Preduhitrivi prioritetni sistemi
Preemptivni raspored 3 procesa (taska)
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
44
Preduhitrivi prioritetni sistemi
•
Primjer : navigacioni sistem aviona
•
•
•
Visoko prioritetni proces: skupljanje podataka
sa akcelometra svakih 5ms
Proces srednjeg prioriteta: sakupljanje
podataka sa žiroskopa i kompenzira ove
podatke i podatke sa akcelometra svakih 40ms
Proces niskog prioriteta: prikaza updata
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
45
Preduhitrivi prioritetni sistemi




Multitasking nije perfektan!
Visoko prioritetni taskovi mogu zauzeti
resurse i “blokirati” procese niskog prioriteta
Nisko-prioritetni procesi djele resurse sa
visoko-prioritetnim procesima, pa je jasan
koncept blokiranja.
Šta u ovom slučaju čini RTOS?

Promjena prioriteta!!!
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
46
Raspoređivač tipa prvi proces sa
najskorijim vremenom završetka

Određuje prioritet procesa na osnovu tri
parametra:



frekvencije
granice izvršenja
trajanja
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
47
Prednje/pozadinski sistemi
raspoređivanja procesa
•
•
Najpogodnije hibridno
rješenje za ugrađene
aplikacije.
Uključuju:
• set procesa sa
prekidima - prednji
(foreground)
•
grupu procesa bez
prekida - pozadinski
(background)
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
48
Prednje/pozadinski sistemi
raspoređivanja procesa


Sva Real-Time rješenja su specijalni slučaji
FOREGROUND/BACKGROUND sistema:
 Prozivka (Polled loops) – samo pozadinski procesi
 Prekidom vođeni sisitemi (Interrupt-only systems)
– samo prednji procesi
Ništa kritično se ne dešava u pozadini (Pozadinski
procesi su procesi sa najnižim prioritetom)!
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
49
Hibridni sistemi
•
Kombinuje sve rečeno o:
•
•
•
Sistemima prozivke
Prekidom vođenim sistemima
Multitaskingu



Ciklični izvršivi sistemi
Round-Robin sistemi
Preduhitrivi prioritetni sistemi
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
50
Potpuno opremljeni real-time
sistemi
•
•
Dostupni kao komercijalni proizvodi
Oslanjaju se na kompleksne operativne
sisteme koristeći round-robin, prioritetne
preduhitrive forme ili kombinaciju ova dva
načina raspoređivanja
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
51
Napraviti ili kupiti
•
•
•
Jedno od često postavljanih pitanja - „Da li da se
komercijalni real-time kernel koristi ili da se
samostalno kreira?
Kako odgovor zavisi od situacije, o slijedećim
ključnim tačkama treba voditi računa:
Komercijalni kerneli jesu čest izbor zbog toga
što:



pružaju robusne usluge
laki su za korištenje
rastavljivi (prenosivi)
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
52
Napraviti ili kupiti
•
•
Komercijalna rješenja su često sporija od
potrebnog (strahovit trošak primijene TCB
modela)!
Obmane proizvođača –vrijeme odziva!
Sistemi realnog
vremena 9
Copyright: Lejla BanjanovićMehmedović
53
Download

SISTEMI REALNOG VREMENA Operativni sistem realnog vremena