Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
1
Sistemi za rad u realnom vremenu (Real Time Systems - RTS)
Uvod Sistemi koji rade u realnom vremenu predstavljaju kombinaciju hardvera i softvera, koja povezuje računar sa spoljašnjim procesima i događajima. Dobili su ime po specifičnom zahtevu koji moraju zadovoljiti, a koji ih razlikuje od ostalih softverskih sistema. Naime, njihov rezultat, pored toga što mora biti logički korektan, mora biti i blagovremen, tj. mora zadovoljiti i izvesna vremenska ograničenja. U zavisnosti od strogosti ovih ograničenja, sistemi za rad u relanom vremenu dele se na stroge (hard real-time systems) i manje stroge sisteme (soft RTSs). Primeri sistema koji rade u realnom vremenu su vojni komandni i kontrolni (C2) sistemi, autopiloti, svemirske stanice i ostale bespilotne letelice, automatizovana industrijska postrojenja, itd. Pomenuta koncizna definicija sistema koji rade u realnom vremenu više ukazuje na poreklo imena nego što u potpunosti opisuje ove sisteme. Zato ćemo pobrojati još neke njihove tipične karakteristike. Sistemi koji rade u realnom vremenu podrazumevaju rad sa skupom nezavisnih hardverskih uređaja, koji rade različitim brzinama, kojima se mora upravljati tako da sistem kao celina ne bude usporavan od strane sporijih uređaja, već da se optimizira iskorišćenje svih raspoloživih resursa i postignu zahtevane performanse. Sisteme koji rade u realnom vremenu neuporedivo je teže projektovati i implementirati od konvencionalnih softverskih sistema. Nabrojaćemo neke od izvora poteškoća: • Kontrola hardverskih uređaja, kao što su komunikakcione linije, merni instrumenti, računarski resursi, itd. • Obrada poruka koje pristižu u neregularnim intervalima, promenljivom brzinom i sa različitim prioritetima obrade • Upravljanje redovima čekanja i baferima za skladištenje pristiglih podataka i poruka • Paralelizam i/ili konkurentnost događaja koji se obrađuju • Modeliranje paralelnih i/ili konkurentnih događaja pomoću procesa • Dodela resursa paralelnim i/ili konkurentnim procesima • Komunikacija i sinhronizacija između paralelnih i/ili konkurentnih procesa • Zaštita integriteta deljenih podataka • Istovremeno zadovoljenje vremenskih ograničenja i strogih zahteva za performansama • Rad sa satom realnog vremena • Otežano testiranje paralelnih i/ili konkurentnih procesa • Neophodnost softverske emulacije onih hardverskih uređaja koji nisu raspoloživi u fazi testiranja • Zahtev za smanjenom osetljivošću na greške i mogućnočću oporavka, ili bar postepenog smanjenja performansi • Neophodnost timskog rada i smanjenja kompleksnosti, podelom na manje, upravljivije delove • Rad u nedeterminisanom okruženju (neprecizni, nepouzdani, neizvesni, netačni podaci), itd. Sisteme koji rade u realnom vremenu možemo okarakterisati i načinom na koji oni obično rade. Od njih se obično zahteva da rade kontinualno, u potpunosti automatizovano i sa velikim stepenom pouzdanosti. Naprimer, automatizovano industrijsko postrojenje obično radi neprekidno, gde svako zaustavljanje i remont mnogo košta, da ne pominjemo još mnogo katastrofalnije posledice grešaka u softveru za kontrolu leta ili autopilotu. Pri tome se istovremeno zahtevaju vrlo visoke performanse, tj.
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
2
vrlo kratko vreme odgovora sistema. U nekim softverskim sistemima koji rade u realnom vremenu, kao što su npr. bespilotna letelica ili termički navođeni projektili, gde verovatnoća pogotka zavisi isključivo od brzine korekcije trajektorije na bazi senzorskih podataka, efikasnost predstavlja ključni zahtev. Većina sistema koji rade u realnom vremenu su strogo namenski, ugrađeni u veći sistem, najčešće veoma složeni i sa strogim zahtevima za pouzdanošću. Da bi se obezbedio pouzdan rad, sistem mora da poseduje smanjenu osetljivost na greške i mogućnost oporavka ili postepene degradacije performansi. Dijagnostika grešaka, a posebno oporavak, podrazumeva posedovanje znanja o strukturi i funkcionalnosti sistema, kao i poznavanje operatorskih procedura kojima se prevazilaze havarijske situacije. Dakle, prirodno je da ovaj deo sistema koji radi u realnom vremenu bude realizovan pomoću tehnologije ekspertskih sistema, odnosno programiranja baziranog na znanju. Većina današnjih ekspertskih sistema podrazumeva da su ova znanja raspoloživa a priori, tj. sistemi su statički. Tendencija je, međutim, da se budući sistemi koji rade u realnom vremenu učine fleksibilnijima, tj. da se znanja o strukturi i ponašanju sistema mogu i dinamički menjati, čak i da se mogu samostalno sticati u toku rada sistema (korišćenjem raznih tehnika mašinskog učenja). Ovo predstavlja nove izazove za istraživače u oblasti ekspertskih sistema, sa kojima se neki (autori okruženja Gensym, G2, OPS5, BEST) uspešno hvataju u koštac. Sistemi koji rade u realnom vremenu obično se sastoje od konrolisanog i od kontrolišućeg dela. Na primer, u automatizovanoj fabrici automobila, kontrolisani sistem predstavljaju roboti koji sklapaju delove automobila, farbaju ih, itd., dok je kontrolišući sistem obično računar ili radna stanica sa korisničkim interfejsom, preko koga operater interaktivno, u većoj ili manjoj meri (zavisno od stepena automatizacije fabrike) upliviše na rad robota. Dakle, kontrolisani sistem može biti shvaćen kao okruženje s kojim je upravljački računar u interakciji. Ova interakcija bazira se na informacijama iz okruženja, prikupljenim pomoću senzora. Podaci se moraju blagovremeno i logički korektno protumačiti, da bi se u definisanom vremenskom prozoru generisali odgovarajući upravljački signali. Na primer, ukoliko kompjuterski kontrolisan robot ne dobije blagovremeno signal o promeni putanje, može da se sudari s drugim robotom ili statičkim objektom, pa i da izazove povrede prisutnih ljudi. Dakle, nije dovoljno da je trajektorija izračunata korektno, već i da upravljački signal, koji je vremenski kritičan, blagovremeno stigne do aktuatora. U većini sistema, aktivnosti koje se odvijaju u realnom vremenu koegzistiraju sa onima koje nemaju striktnih vremenskih ograničenja. Zato je bitno da se ove aktivnosti razluče, pa da se pri porektovanju sistema koncentriše na ispunjenje pojedinačnih vremenskih zahteva kritičnih delova sistema, dok se za ostale procese nastoji minimizirati srednje vreme odgovora. Oni procesa koji su vremenski kritični dele se na periodične i aperiodične. Aperiodični procesi imaju definisano vreme početka ili završetka izvršavanja (mada mogu biti definisana i oba ograničenja), dok se periodični procesi moraju izvršiti jednom u zadatom vremenskom intervalu, tj. sa zadatom periodom izvršavanja. Procesi niskog nivoa (najbliži hardveru), kao što su oni koji prihvataju i obrađuju informacije sa senzora, ili oni koji generišu kontrolne signale aktuatorima, obično imaju stroga vremenska ograničenja. Većina ovih procesa je po prirodi periodična. Na primer, radar koji prati avione proizvodi podatke s fiksnom učestanošću. Merač temperature na nuklearnom reaktoru se očitava regularno, da bi se blagovremeno detektovala promena. Neki od periodičnih procesa postoje od momenta inicijalizacije sistema, dok se drugi generišu dinamički. Monitor temperature na nuklearnom reaktoru je permanentan proces, koji postoji od inicijalizacije sistema za praćenje i dijagnostiku otkaza nuklearnog reaktora. Nasuprot ovom, proces koji prati određeni avion se generiše kad taj avion uđe u zonu pokrivanja određenog radara, a uništava se kad avion napusti tu zonu. U međuvremenu se aktivira periodično. Osim ovih tipičnih, postoje i procesi sa složenijim vremenskim obeležjima. Na primer, proces koji upravlja robotom koji boji školjku automobila na pokretnoj traci, mora da se aktivira posle trenutka t1 i da se završi pre trenutka t2. Dok je proces aktivan, mogu da naiđu različiti aperiodični događaji, npr. pojava prepreke na putu, ili intervencija operatera sa konzole. Pored toga, sami vremenski zahtevi mogu biti postavljeni na indirektan način, ili se striktni vremenski zahtevi u nekim situacijama mogu ublažiti. Često je slučaj da podoptimalno ali blagovremeno rešenje mnogo više znači od optimalnog ali zakasnelog. Slično, ponekad se može tolerisati kašnjenje u N upravljačkih ciklusa, dok u N+1 već postaje kritično, itd. Ovde se postavlja pitanje šta se dešava kad vremenska ograničenja nisu zadovoljena. Odgovor zavisi od vrste aplikacije. Naravno, softverski sistem za kontrolu nuklearnog reaktora ili za navođenje bespilotne letelice mora zadovoljiti sve vremenske zahteve. Resursi koji su potrebni vremenski najkritičnijim
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
3
procesima ovakvih aplikacija moraju biti unapred dodeljeni (rezervisani) za ove procese, da ne bi došlo do prekoračnja vremena odgovora, zbog čekanja na dodelu resursa. U većini manje kritičnih aplikacija, međutim, dozvoljena su povremena kašnjenja ili čak privremena blokiranja. Naprimer, u automatizovanoj fabrici automobila, ukoliko se ne može generisati korektna komanda robotu u datom vremenskom intervalu, on se može sasvim zaustaviti (da ne bi došlo do kolizije s drugim robotom ili statičnim objektom). Komanda robotu da stane je svakako lošija od komande da skrene u slučaju da nailazi na prepreku, ali zahteva kraće vreme od onog potrebnog za računanje korektne trajektorije. Dakle, ukoliko je vreme nedovoljno za optimalnu akciju, blagovremena podoptimalna akcija (zaustavljanje robota) predstavlja dobro rešenje. Slično, periodični proces koji prati trajektoriju aviona, može bez značajnijih posledica da propusti neku iteraciju, tj. da ne obradi nekoliko bafera radarskih podataka, pogotovo dok je trajektorija pravolinijska. Da rezimiramo, osnovna razlika između sistema koji rade u realnom vremenu i tradicionalnih softverskih sistema, sastoji se u eksplicitnim vremenskim ograničenjima pridruženim svakom procesu i u tome da sistem često mora da pravi kompromise između vremenske i logičke korektnosti odgovora, jer kašnjenje može imati katastrofalne posledice za kontrolisani sistem. Dakle, za razliku od konvencionalnih sistema, gde se korektnost odgovora i performanse sistema posmatraju nezavisno, u sistemima koji rade u realnom vremenu ove dve komponente su čvrsto povezane. Različite aplikacije u realnom vremenu imaju različite stepene tolerancije na eventualna kašnjenja. Međutim, bilo da je reč o vremenski kritičnijim ili manje kritičnim aplikacijama, zajedničko im je da, što se pre ustanovi da postoji mogućnost da se vremenski zahtevi ne ispune, veća je fleksibilnost u prevazilaženju ovakvih, izuzetnih stanja. Pored vremenskih ograničenja, koja su za sisteme u realnom vremenu najvažnija, postoji veliki broj drugih ograničenja koja se takođe moraju poštovati: • Resursna ograničenja; Proces može zahtevati pristup različitim resursima (ne samo procesorskoj jedinici računara), kao što su ulazno/izlazni uređaji, datoteke, baze podataka, itd. • Redosled izvršavanja procesa; Kompleksni procesi, kao što su oni koji zahtevaju korišćenje više različitih resursa, jednostavnije se programiraju, testiraju i održavaju ukoliko se razbiju u više procesa. Za ovakve procese je, međutim. obično striktno definisan redosled kojim se moraju izvršavati (precedence constraints), što predstavlja dodatno ograničenje u sistemu. • Konkurentnost; Procesima treba dozvoliti da konkurentno koriste resurse (pa i paralelno u distribuiranim ili multiprocesorskim sistemima), da bi ih što bolje iskoristili, a da se pri tom očuva konzistentnost deljenih resursa. • Dinamičnost okruženja; Veliki broj sistema u realnom vremenu radi u promenljivom okruženju, gde se vremenom menjaju i one karakteristike sistema na bazi kojih su donesene i važne projektne odluke. To znači da se neke komponente sisteme moraju dinamički rekonfigurisati, da bi se amortizovale nastale promene. Kako su hardverski resursi obično ograničeni (mada se nekad planiraju i redundantne komponente), promena obično povlači rekonfiguraciju softvera (dinamičko kreiranje i uništavanje softverskih komponenti). Rekonfiguracija softvera, međutim, povlači velike režijske troškove, što može ugroziti vremenske karakteristike sistema. • Komunikacioni zahtevi; U distribuiranim sistemima koji rade u realnom vremenu, brzina komunikacije zavisiće od topologije sistema, od primenjenog protokola, od količine podataka koji se razmenjuju, a pri tom režijski troškovi moraju da se minimiziraju da bi se zadovoljila vremenska ograničenja. • Raspodela procesa; Da bi se u distribuiranim sistemima minimizirali troškovi komunikacije i sinhronizacije među udaljenim procesima, treba obratiti pažnju pri raspodeli procesa po čvorovima. Komunikacioni troškovi se minimiziraju kad se čvrsto spregnuti procesi, koji razmenjuju veliki broj podataka, alociraju na isti čvor distribuiranog sistema. Ovako se minimiziraju troškovi komunikacije a i smanjuje zagušenje na zajedničkim resursima (magistrali, zajedničkoj memoriji, itd.).
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
4
• Alokaciona ograničenja; Pored pomenutih kriterijuma pri raspodeli procesa na čvorove distribuiranog sistema pojavljuju se i dodatna ograničenja. Naprimer, ponekad je, radi povećanja pouzdanosti sistema potrebno multiplicirati kritične procese. Klonovi se moraju rasporediti na različite čvorove u odnosu na matični proces, da bi se izbeglo da se u slučaju otkaza čvora unište sve instance kritičnog procesa. • Kritičnost; Zavisno od funkcije procesa u ukupnoj aplikaciji u realnom vremenu, varira i njihova vremenska kritičnost, kao i posledice u slučaju neispunjenja zahteva. Pri tome se ove dve vrste kritičnosti bitno razlikuju. Ponekad su manje posledice kad ne stigne da se izvrši proces koji ima strožije vremenske zahteve, nego kad se ne izvrši neki sporiji proces. Na primer, proces koji računa trajektoriju autonomnog robota u fabrici automobila je sigurno vremenski zahtevniji od onog koji reaguje na havarijsku situaciju u fabrici (izbijanje požara, npr. ), uključivanjem zvučnog alarma, ali njegovo neblagorvremeno izvršavanje ima manje posledice. • Distribuiranost; Većina sistema koji rade u realnom vremenu su inherentno distribuirani, jer je i okruženje u kojima rade razuđeno (industrijsko, C3...). Neke karakteristike različitih aplikacionih procesa su poznate unapred (statičke karakteristike), dok se druge izdiferenciraju tek u toku rada sistema (dinamičke karakteristike). Karakteristike periodičnih procesa su obično poznate unapred, dok su aperiodični procesi obično slabije determinisani. Naprimer, vremenska kritičnost procesa koji kontroliše kretanje autonomnog robota određuje se dinamički, jer zavisi od brzine kretanja, pravca, inertnosti robota, itd. Komanda robotu da se okrene desno ili levo, ili da se zaustavi, mora da bude generisana pre isteka vremena koje zavisi od pobrojanih parametara, dakle može se odrediti samo dinamički. U statičkom sistemu, karakteristike kontrolisanog sistema su unapred poznate, pa se i priroda i redosled kontrolnih aktivnosti mogu unapred planirati. Ovakvi sistemi su, međutim, prilično nefleksibilni, mada obično imaju manje režijske troškove od dinamičkih. U praksi, većina sistema poseduje i statičke i dinamičke komponente. Ako se pažljivo projektuju, ovakvi kombinovani sistemi mogu postići visoke performanse uz istovremeno veliki stepen iskorišćenja resursa. Iako veći procenat danas operativnih sistema u realnom vremenu ima statičku prirodu, normalno je očekivati da će u budućnosti preovlađivati fleksibilniji dinamički sistemi. Oni će biti veći i složeniji, verovatno i fizički distribuirani. Zahtevi za jednostavnošću održavanja i mogućnošću proširenja biće strožiji, što znači da će sistemi morati biti fleksibilniji, što dalje znači da će morati biti dinamički, a ne statički. Dakle, budući sistemi koji rade u realnom vremenu moraće biti brzi, predvidljivi, pouzdani i fleksibilni (adaptivni). Predvidljivost znači da je u trenutku aktiviranja procesa moguće pouzdano predvideti vreme njegovog završetka. Pri tom se mora uzeti u obzir stanje sistema, uključujući stanje operativnog sistema i stanje resursa kontrolisanih operativnim sistemom, kao i resursni zahtevi konkretnog procesa. Sistem ispunjava zahtev za predvidljivošću ako za svaki vremenski kritičan proces možemo pouzdano da utvrdimo da li će njegova vremenska ograničenja biti ispunjena ili ne. Pouzdanost je jedan od bitnih preduslova sistema koji rade u realnom vremenu. Ograničenja realnog vremena ne mogu biti ispunjena ako su komponente sistema nepouzdane. Ponekad je poželjno da se mogu specificirati različiti nivoi pouzdanosti sistema, te da se mogu predvideti performanse sistema zavisno od novoa pouzdanosti. Zahtevi za pouzdanošću obično unose dodatne režijske troškove koji degradiraju performanse sistema. Adaptivnost (fleksibilnost) sistema podrazumeva mogućnost prilagođenja sistema • promenama stanja sistema, tj. dinamici sistema, uključujući i preopterećenja i havarije, • promenama konfiguracije sistema, • promenama ulaznih zahteva, itd.
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
5
Adaptivnost je posebno značajna za sisteme koji rade u realnom vremenu, jer ukoliko se ne može postići zahtevano vreme odgovora sistema, onda se pravi kompromis između pouzdanosti i performansi sistema, tj. smanjuje se redundansa (samim tim pouzdanost), da bi se ostvarila zahtevana brzina rada. Ukoliko je sistem adaptivan, on se ne mora iznova definisati, nakon svake i najmanje rekonfiguracije. Adaptivnost smanjuje cenu razvoja i održavanja sistema. Da bi bio istovremeno predvidljiv i adaptivan, sistem se mora vrlo pažljivo projektovati. Jednostavnost održavanja i proširivanja sistema proizlaze iz adaptivnosti. Pošto su vremenske karakteristike sistema koji rade u realnom vremenu, posebno vremenska ograničenja pojedinih procesa, zavisne od karakteristika primenjenih hardverskih resursa, to je ponekad potrebno a priori dodeliti neke hardverske resurse vremenski kritičnim procesima. Ovo statičko dodeljivanje resursa, međutim, bitno utiče na fleksibilnost sistema. Očigledno, zavisno od složenosti kontrolisanog sistema, od toga koliko je učešće statičkih nasuprot dinamičkim komponentama i ukupne složenosti aplikacije, variraće i strategije projektovanja sistema. U poglavljima koja slede biće razmatrane različite vrste aplikacija u realnom vremenu, kao i različite vrste strategija projektovanja ovakvih sistema, kao i alata za projektovanje, operativnih sistema i programskih jezika korišćenih za implementaciju ovih sistema.
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
6
Uobičajene pogrešne predstave o sistemima u realnom vremenu Sistemi u realnom vremenu ne privlače pažnju naučnika na nivou akademskog računarstva kakvu realno zaslužuju. Ovaj nedostatak odgovarajuće pažnje se može dovesti u vezu sa nekim opštim pogrešnim predstavama o sistema u realnom vremenu. Pomenućemo, a nadam se i opovrgnuti, neke od njih.
Nema nauke u projektovanju sistema u realnom vremenu?! Potpuno je tačno da su se u prošlosti sistemi koji rade u realnom vremenu projektovali uglavnom ad hoc. To međutim ne znači da naučni pristup svim faza u životnom ciklusu ovih sistema nije moguć, a ima i dokaza da je inženjerima koji se bave sistemima u realnom vremenu potrebna pomoć. Na primer, prvi let Space Shuttle-a je bio odložen, po velikoj ceni, zbog suptilne vremenske greške koja je proistekla iz kratkotrajnog preopterećenja procesora prilikom inicijalizacije sistema. Izlišno je, dakle, pitanje da li treba pokušati razviti naučnu osnovu za verifikaciju projekta, koji bi bio, u što je moguće većoj meri, oslobođen takvih suptilnih vremenskih grešaka? Stoga problem uključivanja vremenske metrike u metode za specifikaciju sistema koji rade u realnom vremenu, kao i istraživanje semantičkih teorija za programske jezike namenjene aplikacijama koje rade u realnom vremenu, sve više zaokuplja naučnike i istraživače u oblasti računarstva, a takođe i najpoznatije softverske kuće, proizvođače CASE (Computer Aided Software Engineering) alata, operativnih sistema, prevodilaca, alata za automatizaciju procesa, itd.
Unapređenje superkompjuterskog hardvera će rešiti probleme blagovremenosti odgovora sistema u realnom vremenu?! Napredak u projektovanju superkompjutera je zasnovan na korišćenju paralelnih procesora za poboljšanje efikasnosti (throughput-a) sistema. Dovoljno brz procesor ne garantuje da će automatski biti i ispoštovana sva vremenska ograničenja u sistemu. Čak i kad se arhitektura računarskog sistema pažljivo prilagođava aplikaciji, zbog asinhronog karaktera mnogih ulaznih signala, zbog dinamičnosti okruženja i potencijalnih havarijskih situacija, procesori i njihovi komunikacioni podsistemi ne moraju uvek biti u stanju da blagovremeno odgovore na sve zahteve iz okruženja i da se izbore sa vremenski kritičnim saobraćajem i zagušenjima na komunikacionim putevima. U stvari, procesi u realnom vremenu i problemi raspoređivanja resursa i zagušenja zajedničkih resursa se čak i usložnjavaju kod superkompjutera, pošto se povećava broj hardverskih i softverskih resursa kojima treba uravnoteženo i vremenski korektno upravljati. Realno, istorija računarstva pokazuje da zahtev za većom snagom računara uvek prevazilaze postojeće mogućnosti. Ako je prošlost vodič ka budućnosti, raspolaganje računarima veće snage će samo usloviti pojavu aplikacija u realnom vremenu sa većim funkcionalnim zahtevima, otežavajući tako rešavanje problema blagovremenosti i logičke korektnosti odgovora sistema. Postoje takođe druge važne teme u oblasti projektovanja sistema u realnom vremenu koje ne mogu biti rešene samo superkompjuterskim hardverom, o čemu će biti reči u nastavku.
Računarstvo u realnom vremenu je ekvivalentno brzom računarstvu?! Pravo brzo računarstvo rešava problem minimiziranja prosečnog vremena odgovora datog skupa zadataka. Pravo računarstvo u realnom vremenu podrazumeva ispunjenje individualnog vremenskog zahteva svakog od taskova. U sistemima u realnom vremenu, značajnija osobina od brzine (što je uostalom relativan pojam) je predvidljivost, što znači da funkcionalno i vremensko ponašanje sistema treba da bude u toj meri determinisano da je moguće unapred znati da li postoji svi neophodni uslovi za zadovoljenje sistemskih specifikacija. Brzo računarstvo je korisno za ostvarivanje strogih vremenskih specifikacija, ali samo po sebi ne garantuje predvidljivost ponašanja sistema. Postoje drugi faktori, osim brzog hardvera ili algoritama, koji određuju predvidljivost. Ponekad, implementacioni jezik ne mora biti dovoljno ekspresivan da bi mogao da propiše neko vremensko ponašanje. Na primer, iskaz
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
7
delay u jeziku Ada samo postavlja donju granicu kada se sledeći task raspoređuje; ne postoji jezička podrška koja garantuje da task ne može više zakasniti od željene gornje granice. Možda najbolji odgovor onima koji izjednačavaju brzo računarstvo i računarstvo u realnom vremenu je postavljanje sledećeg pitanja: Za dati skup zahteva u realnom vremenu i implementaciju koja koristi najbrži postojeći hardver i softver, kako se može pokazati da će specificirano vremensko ponašanje stvarno biti postignuto? Testiranje nije odgovor! Zaista, pored svih laboratorijskih testova i simulacija na Space Shuttle-u, vremenska greška koja je odložila njegovo prvo poletanje je otkrivena vrlo teško; verovatnoća je bila samo 1 od 67 da kratkotrajno preopterećenje za vreme inicijalizacije može izbaciti redundantne procesore iz sinhronizacije i to se desilo. Predvidljivost ponašanja, a ne brzina, je prvenstven cilj pri projektovanju sistema u realnom vremenu.
Programiranje u realnom vremenu je asemblersko kodiranje, programiranje prioritetnih prekida i pisanje drajvera?! Da bi se ispoštovala čvrsta vremenska ograničenja, ranija praksa programiranja u realnom vremenu se oslanjala na tehnike optimizacije na mašinskom nivou. Ove tehnike, ponekad uvode dodatne vremenske pretpostavke od kojih zavisi korektnost implementacije. Preterano poverenje u vešto ručno kodovanje i teško praćenje vremenskih pretpostavki su glavni izvori grešaka u programiranju u realnom vremenu, posebno pri modifikovanju velikih programa u realnom vremenu. U istraživanjima u oblasti sistema u realnom vremenu primarno je u stvari automatizovati, korišćenjem optimalnih transformacija i teorije raspoređivanja, sintezu visoko efikasnog koda i postupka raspoređivanja resursa na osnovu vremenskih ograničenja. S druge strane, iako su asemblersko programiranje, programiranje prekidnih procedura i pisanje drajvera, značajni aspekti računarstva u realnom vremenu, oni ne predstavljaju nerešene naučne probleme - izuzev u njihovoj automatizaciji.
Svi problemi u oblasti sistema u realnom vremenu mogu biti rešeni u drugim oblastima računarske nauke ili u operacionim istraživanjima?! Iako istraživači u oblasti sistema u realnom vremenu sigurno pokušavaju da iskoriste tehnike za rešavanje problema koje se primenjuju u razvijenijim istraživačkim oblastima računarstva, postoje pojedini problemi u sistemima u realnom vremenu koji ne mogu biti rešeni ni u jednoj drugoj oblasti. Na primer, inženjering performansi u računarstvu najčešće se bavi analizom srednjih vrednosti pokazatelja performansi, dok se u sistemima u realnom vremenu razmatra da li neka stroga vremenska ograničenja mogu zasigurno biti ispoštovana ili ne. Razmatra se “najgori slučaj” a ne srednja vrednost. Slično, modeli redova ( i raspoređivanja) tradicionalno koriste pogodne stohastičke pretpostavke, koje su potvrđene čestim korišćenjem i stabilnim radnim uslovima. Analitički rezultati zasnovani na ovim pretpostavkama mogu biti sasvim beskorisni za neke aplikacije u realnom vremenu. Na primer, pojava zagušenja na uskim grlima u komunikacionoj infrastrukturi (visoko nelinearna degradacija performansi usled malih devijacija u odnosu na uniformni saobraćaj u višenivoskim komunikacionim mrežama) je verovatno katastrofalna za aplikacije sa vremenski kritičnom komunikacijom. Isto tako, u kombinatornim problemima raspoređivanja u oblasti operacionih istraživanja, svaki zadatak (task) sme da bude raspoređen samo jednom, dok u sistemima u realnom vremenu, isti task se može vraćati proizvoljno često, bilo periodično ili u neregularnim intervalima i biti sinhronizovan ili komunicirati sa više drugih taskova. Prema tome, metode raspoređivanja kakve se koriste u operacionim istraživanjima su često neprimenljive. Takođe, jedan od ključnih parametara koji se koristi pri višekriterijumskoj optimizaciji rasporeda je vreme izvršavanja zadatka, koje je u sistemima koji rade u realnom vremenu teško (ili čak nemoguće) precizno odrediti. Metode operacionih istraživanja podrazumevaju precizne vrednosti kriterijuma, pa se ovde u poslednje vreme sve više pribegava tehnikama veštačke inteligencije za predstavljanje i manipulisanje nepreciznim i nepouzdanim podacima i znanjima (faktori izvesnosti, rasplinuta logika, itd.).
Nema smisla govoriti o garanciji performansi u sistemima u realnom vremenu, zato što ne možemo garantovati da nema grešaka u hardveru i softveru ili da trenutni radni uslovi neće prekršiti postavljena ograničenja?! Opšte je poznato da svako želi da minimizira verovatnoću greške sistema kog pravi. Relevantno pitanje je, naravno, na koji način treba projektovati sistem da bismo imali najveće moguće poverenje da će on ispuniti postavljane zahteve po prihvatljivoj ceni. Pri projektovanju sistema u realnom vremenu, treba
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
8
pokušati sa optimalnim raspoređivanjem i maksimalnim iskorišćenjem resursa, kako bismo bili sigurni da se kritična vremenska ograničenja mogu ispoštovati sa raspoloživim resursima, podrazumevajući da hardver i softver funkcionišu korektno i da spoljašnje okruženje ne izlaže sistem dejstvu preko onog za šta je projektovan. Činjenica da hardver i softver ne funkcionišu uvek korektno, ili da radni uslovi nametnuti spoljašnjim okruženjem mogu prekoračiti projektovana ograničenja sa verovatnoćom različitom od nule, ne daje projektantu pravo da unosi dodatni izvor potencijalne greške time što ne vodi dovoljo računa o onim aspektima na koje može da utiče. Ako se ispoštuju sve rigorozne procedure validacije i verifikacije softverskih sistema za rad u relnom vremenu, kako pri statičkom, tako i pri dinamičkom radnom opterećenju, verovatnoća greške u operacionom radu se ipak može značajno smanjiti. Ne može se garantovati da će hardver besprekorno funkcionisati, ali se može obezbediti hardverska redundansa za kritične delove i minimizirati vreme za koje ispravna komponenta može u potpunosti preuzeti funkciju one koja je otkazala. Da rezimiramo, verujemo da će mnogi budući sistemi u realnom vremenu biti veliki i kompleksni, da će funkcionisati u distribuiranim i dinamičkim okruženjima, uključivati komponente ekspertnih sistema i veštačke inteligencije, sadržati kompleksna vremenska ograničenja čije neispunjenje može rezultirati ekonomskim, ljudskim i ekološkim katastrofama. Postizanje ovakvih karakteristika vrlo mnogo zavisi od usmerenosti i koordiniranosti napora u svim aspektima razvoja sistema, kao što su: • Tehnike specifikacije i verifikacije koje mogu zadovoljiti potrebe sistema u realnom vremenu sa velikim brojem interaktivnih komponenata, • Metodologije projektovanja koje se mogu koristiti za sintetisanje sistema sa specifičnim vremenskim svojstvima, pri čemu se ova vremenska svojstva razmatraju od početka procesa projektovanja, • Programski jezici sa eksplicitnim konstruktima za iskazivanje vremenski uslovljenog ponašanja modula i sa nedvosmislenom sematikom, • Algoritmi raspoređivanja koji mogu, u integrisanom i dinamičkom okruženju, upravljati kompleksnim strukturama procesa sa resursnim i prioritetnim ograničenjima, upravljati resursima (kao što je komunikaciona mreža ili U/I jedinica) i vremenskim ograničenjima promenljive granularnosti, • Funkcije operativnog sistema projektovane za rad sa visoko integrisanim, kooperativnim i vremenski ograničenim resursima na brz i predvidljiv način, • Komunikaciona infrastruktura i protokoli za efikasan rad sa porukama koje zahtevaju pravovremenu isporuku i • Arhitekturalna podrška smanjenoj osetljivosti na greške, funkcijama operativnog sistema, efikasnoj komunikaciji, pa i programskim jezicima namenjenim pisanju aplikacija koje rade u realnom vremenu. Očigledno je da su sistemi u realnom vremenu uticali na širok opseg naučnih disciplina u računarstvu. Može se zaključiti da se moraju koordinirati istraživački napori na univerzitetu i u institutima sa razvojnim naporima u industriji, tako da akademski istraživači budu upoznati sa ključnim problemima sa kojima se susreću oni koji razvijaju sistem, a i da oni koji razvijaju sistem budu svesni relevantnih novih teorija i tehnologija.
ARHITEKTURA I HARDVER Sistemi koji rade u realnom vremenu su obično strogo namenski i imaju originalnu hardversku arhitekturu i konfiguraciju. Uprkos tome, moguće je napraviti izvesne generalizacije i definisati neke opšte principe i pravila projektovanja hardvera za sisteme koji rade u realnom vremenu. Pobrojaćemo neke: • Namenske sisteme treba projektovati korišćenjem standardnih, komercijalno raspoloživih komponenti, koliko god je to moguće • Ne sme se redefinisati problem da bi se prilagodio postojećem hardveru, već obrnuto
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
9
• Mora se imati u vidu zahtev za smanjenom osetljivošću na greške (što često podrazumeva i hardversku redundansu) • Programski kod ponekad mora da bude smešten u ROM upravljačkog računara, pa treba voditi računa o njegovoj kompaktnosti • Hardver mora da prati funkcionalnu dekompoziciju sistema (ali ona ne sme da bude previše kruta na štetu adaptibilnosti sistema) • Mora postojati mogućnost dinamičkog testiranja sistema • Privatne memorije procesora treba koristiti za kod procesa i privatne podatke, a zajedničku memoriju za deljene podatke • Procesno opterećenje, kao i režijske troškove, treba rasporediti što ravnomernije po čvorovima sistema • Opredeliti se za statičko punjenje lokalnih memorija programima i podacima, gde god je to moguće, čime se smanjuje fluktuacija vremena izvršavanja i povećava predvidljivost sistema, itd. Mnogi sistemi za rad u realnom vremenu mogu biti sagledani kao sistemi čiji se zadatak sastoji iz tri sukcesivne aktivnosti: prikupljanja podataka, obrade podataka i izlaza ka okruženju. Arhitekture sistema za rad u realnom vremenu moraju biti projektovane tako da odražavaju ove tri komponenente sa visokom tačnošću. Za prvu i treću komponentu, arhitektura treba da obezbedi velike mogućnosti ulazaizlaza, dok za drugu komponentu treba da omogući veliku računarsku snagu i pouzdan rad. Kao što je već rečeno, arhitekture sistema za rad u realnom vremenu se često baziraju na namenskim računarima i programima. Arhitektura obično mora da se menja usled izmena u aplikacijama. Takve arhitekture niti pružaju performanse u skladu sa svojom cenom, niti su dovoljno iskorišćene. Zahvaljujući napretku u računarskim tehnologijama, postaje moguće razviti distribuiranu i/ili multiprocesorsku arhitekturu koja je pogodna za veći broj različItih klasa aplikacija u realnom vremenu. Važni aspekti takve fleksibilne, distribuirane arhitekture su topologiju veza, komunikacija među procesima, podrška operativnim sistemima za rad u realnom vremenu i otpornost na greške.
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
10
Projektovanje distribuiranih sistema za rad u realnom vremenu odvija se na dva nivoa - sistemskom i novou čvora. Na nivou čvora, svaki procesor mora posedovati odgovarajuću procesnu snagu i predvidljivost ponašanja u realnom vremenu, kao i mogućnost interakcije s okruženjem i obrade prekida. Procesorska snaga se, danas, najjednostavnije ostvaruje. Predvidljivost ponašanja podrazumeva da su izvršavanje instrukcija, pristup memoriji i U/I uredjajima i izmena konteksta procesa predvidljivog trajanja. Da bi ove, “sitne”operacije, imale predvidljivo trajanje, sistemi koji rade u realnom vremenu se često odriču prednosti “virtuelne” memorije pa i “keš” memorije (“page fault” i “cashe hit/miss” su teško predvidljivi). Naravno, često je nemoguće da se izbegne npr. keš memorije, jer smo već naglasili da je poželjno da se i namenski sistemi za rad u realnom vremenu prave od komercijalno raspoloživih elemenata što veće granulacije (najčešće nivo ploča). Čak se i savremeni procesorski čipovi prave sa ugrađenim višenivoskim keširanjem, u svrhu optimizacije performansi (u konvencionalnom smislu, dakle prosečnih performansi, a ne u RTS smislu, gde se mora razmatrati “najgori slučaj”). Na sistemskom nivou, komunkacija među čvorovima i otpornost na greške, predstavljaju glavne probleme, koji bitno utiču i na logičku i vremensku korektnost odgovora sistema kao celine, kao i na predvidljivost ponašanja i pouzdanost.
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
11
Poželjno je da topologija distribuiranog sistemua za rad u realnom vremenu ima sledeće četiri osobine. 1.
Homogenost: Zahvaljujući homogenosti, procesi mogu biti alocirani na bilo koji čvor na osnovu vremenskih ograničenja i dostupnosti resursa. To je posebno korisno kada procesi moraju biti prebačeni na druge čvorove zbog toga što su čvorovi, na koje su inicijalno bili alocirani, otkazali pre njihovog izvršenja.
2.
Skaliranje: Omogućava promenu računarske snage distribuiranog sistema u bilo kom trenutku, bez izmene bilo kog čvora i izazivanja problema usled uključivanja i isključivanja.
3.
Preživljavanje: Za dati par čvorova, u topologiji mora postojati više puteva između čvorova. To omogućava lako usmeravanje poruka u sistemu, a takođe povećava i sposobnost preživljavanja mreže u slučaju pada čvora ili veze.
4.
Eksperimentalna fleksibilnost: Onemogućavajući neke od veza u izabranoj topologiji, mnoge arhitekture mogu lako biti emulirane. Kao rezultat, svi algoritmi, koji se mogu efikasno primeniti na tim arhitekturama, se mogu lako ispitati na odabranim topologijama.
Najinteresantnije i još uvek otvorene istraživačke teme u oblasti arhitektura u realnom vremenu su sledeće: • Topologija veza za procesore i ulaz/izlaz. Usled obimnog ulaza/izlaza i velikih brzina obrade podataka koje je potrebno postići u aplikacijama u realnom vremenu, potrebno je razviti integrisane topologije veza, kako za procesore, tako i za ulaz/izlaz. Iako su procesorske topologije detaljno proučavane, malo pažnje je poklanjano distribuciji ulazno/izlaznih podataka. • Brza i pouzdana komunikacija. VLSI implementacija virtuelnog protoka može obezbediti brzu komunikaciju. Međutim, još uvek ostaje neizvesno koliko dugo će trajati uručivanje poruke. Teško je uz ovakvu neizvesnost garantovati da će sva stroga vremenska ograničenja biti ispoštovana. Pored toga, svako rešenje mora uračunati kašnjenja koja bi se mogla javiti usled otkaza. Dalja istraživanja su neophodna da bi se realizovao virtuelni protok uz razmatranje predvidljivosti i pouzdanosti isporučivanja poruka. • Podrška arhitekture obradi grešaka. Neophodno je obezbediti hardversku podršku za brzu detekciju grešaka, rekonfiguraciju i oporavak. To uključuje samoproveravajuća kola, procesor namenjen održavanju, posmatrače sistema (“watch-dog” timer), glasače, itd. Pitanje izbora ovih komponenti, kao i pitanja kada i kako ih koristiti, će biti veoma važna za performanse sistema i njegovu pouzdanost. • Podrška arhitekture algoritmima za raspoređivanje. Da bi se podržali algoritmi raspoređivanja u realnom vremenu, arhitekture bi trebalo da imaju, pored ostalih mogućnosti, brze prekide, dovoljno razuđene priorite, efikasnu podršku za strukture podataka, kao što su redovi sa prioritetima i složeno raspoređivanje uređaja za ulaz/izlaz i komunikaciju. • Podrška arhitekture operativnim sistemima u realnom vremenu. Operativni sistemi za sisteme za rad u realnom vremenu bi trebalo da koriste mogućnosti koje obezbeđuje korišćeni hardver u pogledu podrške protokolima u realnom vremenu, brze izmene konteksta procesa, upravljanja memorijom u realnom vremenu, uključujući keširanje i kompakciju memorije (sakupljanje djubreta - garbage collection), obrade prekida, sinhronizacije sata, itd. • Podrška arhitekture mogućnostima jezika. Korišćenje specijalizovanih arhitektura, projektovanih da eksplicitnije i efikasnije podržavaju jezike za programiranje u realnom vremenu, može doneti mnogo koristi u sistemima za rad u realnom vremenu. Na primer, arhitektura bi mogla pružiti pomoć prilikom procene vremena izvršavanja programa. Podrška konkuretnoj kontroli može poboljšati performanse jezika u realnom vremenu.
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
12
Komunikacija u realnom vremenu Za sisteme sledeće generacije za rad u realnom vremenu biće potrebni komunikacioni medijumi koji će predstavljati osnovu na kojoj će biti izgrađeni predvidljivi, stabilni, proširivi sistemi. Da bi bio uspešan, komunikacioni podsistem u realnom vremenu mora biti u stanju da predvidljivo zadovoljava zahteve u vezi vremenskih ograničenja za pojedinačne poruke na bilo kom nivou. Vremenska ograničenja su uslovljena ne samo komunikacijom među procesima date aplikacije, nego i vremenski ograničenim funkcijama operativnog sistema pozivanih na zahtev procesa u okviru aplikacije. U standardnom okruženju je dovoljno da se obezbedi logička ispravnost rešenja komunikacija; međutim u okruženju u realnom vremenu potrebno je, pored toga, obezbediti i ispravnost u vremenu. Iskustvo u pisanju programa pomaže u utvrđivanju logičke ispravnosti sistemskih rešenja, ali ne pomaže po pitanju ispravnosti u vremenu. Ispravnost u vremenu podrazumeva obezbeđivanje mogućnosti raspoređivanja sinhronih i sporadičnih poruka, kao i garantovanje poštovanja vremenskih ograničenja za asinhrone poruke. Obezbeđivanje ispravnosti u vremenu u dinamičkim okruženjima sledeće generacije predstavlja osnovni istraživački izazov. Iako je komunikacioni kanal samo još jedan resurs, kao procesor, postoje najmanje tri pitanja po kojima se problem raspoređivanja kanala razlikuje od problema raspoređivanja procesora: • Za razliku od procesora, koji ima samo jednu tačku pristupa, pristup kanalu je najčešće moguć iz bilo kog čvora distribuirane mreže. Zbog toga je neophodan distribuirani protokol. • Dok su algoritmi sa prekidima pogodni za raspoređivanje procesa, poruke se ne mogu prekidati, jer se moraju proslediti u celini. • Pored vremenskih ograničenja poruka, koje proističu iz semantike same aplikacije, vremenska ograničenja mogu poticati i od ograničenja bafera. Na primer, kada je samo jedan bafer dostupan, poruka iz bafera mora biti prosleđena pre nego što stigne sledeća. Dodatna istraživanja za razvoj tehnologija u oblasti komunikacija u realnom vremenu treba da uključe: • Rešenja dinamičkog usmeravanja koja garantuju ispravnost u vremenu, • Otpornost na greške i komuniciranje ograničeno u vremenu, • Raspoređivanje u mreži koje se može kombinovati sa raspoređivanjem procesora, da bi se obezbedilo rešenje problema raspoređivanja resursa na nivou celog sistema. Da sumiramo, bez obzira da li se kao fizički komunikacioni medijum koriste “broadcast” magistrale (češće u prošlosti) ili savremeni, brzi prstenovi sa žetonom (“token ring”) i direktne veze od tačke_do_tačke (“point_to_point”), u distribuiranim sistemima koji rade u realnom vremenu postoji potreba za komunikacionim protokolima koji obezbeđuju determinističko ponašanje učesnika u komunikaciji. U savremenim distribuiranim sistemima postoje namenski, mrežni procesori (“network processors”), koji su potpuno posvećeni problemima komunikacije, blagovremenog i pouzdanog uručivanja poruka, razbijanja u pakete i ponovnog asembliranja, pronalaženja najkraćih puteva od pošiljaoca i primaoca, pronalaženje alternaivnih puteva u slučaju otkaza najkraćeg, itd. Kako je oblast računarskih mreža jedna od najpropulzivnijih oblasti današnjeg računarstva i telekomunikacija, to se performanse ovih specijalizovanih računara, kao i efikasnost algoritama usmeravanja poruka, svakodnevno poboljšavaju. Definisani su neki standardni komunikacioni protokoli i načini njihove integracije u jezgra operativnih sistema, ulazno/izlazne module, drajvere uređaja, aplikacione module, itd. Naravno, viši nivoi standardizacije tek treba da se definišu.
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
13
Smanjena osetljivost na greške Ukoliko sistem mora posedovati smanjenu osetljivost na otkaze, onda se o ovom zahtevu mora od početka voditi računa, i uključiti odgovarajuću hardversku i/ili softversku redundansu. Zbog strogih zahteva za efikasnočću i velike količine podataka sa kojima se operiše, nejčešće se pribegava statičkoj redundansi. Dinamička rekonfigurabilnost predstavlja elegantnije rešenje, ali obično povlači nedozvoljeno velike režijske troškove. Računarski sistem za rad u realnom vremenu i njegovo okruženje čine nerazdvojni par. Na primer, avioni nisu u stanju da lete bez digitalnih kontrolnih računara. U takvim sistemima besmisleno je razmatrati ugrađene kontrolne računare odvojeno od samog aviona. Uska povezanost okruženja i računara za rad u realnom vremenu potiče od vremenskih ograničenja i ograničenja vezanih za pouzdanost. Osim u slučaju kada računar pruža "prihvatljive" usluge svom okruženju, uloga računara se gubi i na taj način postaje promašena ili nepostojeća. Greška se može dogoditi usled otkaza komponenti (statička greška), ili zbog nedovoljno brzog odgovora na podsticaje iz okruženja (dinamičke greške). Ova stanja moraju biti pažljivo opisana za različite aplikacije u realnom vremenu u kojima čak i definisanje vremenskih ograničenja samo po sebi predstavlja relativno neistražen problem. Na osnovu tog opisa problema u realnom vremenu, moguće je rešiti veliki broj projektantskih i analitičkih problema za računare u realnom vremenu, npr., optimalna obrada grešaka, upravljanje reduntnim komponentama i podešavanje arhitekture konkretnoj aplikaciji. Važne istraživačke teme u sistemima za rad u realnom vremenu koji su pouzdani i otporni na greške su: • Formalna specifikacija zahteva za pouzdanošću i uticaj vremenskih ograničenja na takve zahteve u složenim problemima. Na primer, NASA je propisala da verovatnoća otkaza svakog računara za kontrolu leta treba da bude manja od 10 -9 u toku 10 časova rada. Ovaj zahtev za veoma velikom pouzdanošću određuje jasnu granicu između računara za kontrolu leta i konvencionalnih računara. • Otklanjanje grešaka je obično realizovano kao uređena sekvenca koraka: detekcija greške, lokalizacija greške, rekonfiguracija sistema i oporavak. Svi ovi koraci moraju biti projektovani i analizirani u kontekstu kombinovanja performansi (uključujući vremenska ograničenja) i pouzdanosti. Međustanja između ovih koraka moraju biti pažljivo proučena. Podrška hardvera i operativnog sistema, zajedno sa njihovim uticajem na performanse i pouzdanost su važne istraživačke teme. • Mora biti pronađen pravi odnos između korišćenja hardvera i softvera radi postizanja otpornosti na greške. Hardverski pristup je brz ali zahteva preteranu količinu hardvera da bi postigao trostruku (ili četvorostruku) modularnu redundansu, zahtevanu zbog pouzdanosti u aplikacijama u realnom vremenu. Softverski pristup je sa druge strane fleksibilan, jeftin, ali spor. Ovaj odnos mora biti optimiziran tako da sistem ima cenu u skladu sa efikasnošću, pri čemu vremenska ograničenja moraju da budu zadovoljena. • Efekti radnih opterećenja u realnom vremenu na otpornost na greške još nisu adekvatno ispitani. Dobro je poznato da pouzdanost računarskih sistema veoma zavisi od radnog opterećenja. Veoma je važno opisati uticaje "reprezentativnog" radnog opterećenja u realnom vremenu na otpornost na greške.
Može se zaključiti da se arhiterkura i hardverska platforma sistema koji radi u realnom vremenu ne može posmatrati izolovano. U projektovanju sistema za rad u realnom vremenu idealno bi bilo usvojiti integralni pristup, u kome bi se aplikacija, operativni sistem i hardver razvijali sa istim ciljem poštovati vremenska ograničenja uz maksimalno iskorišćenje resursa i postizanje dobrih performansi uz umerenu cenu.
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
14
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
15
UVOD U OPERATIVNE SISTEME Vrlo je teško dati definiciju operativnog sistema na osnovu onoga što on jeste. I u stručnoj literaturi koja se bavi ovom problematikom, mnogo češće se daje definicija na osnovu onoga što on radi. Operativni sistem je program namenjen da zajedno sa hardverom računara obezbedi upotrebljiv računarski sistem. Pod tim se podrazumeva da operativni sistem treba da obezbedi korisniku udobno radno okruženje i korišćenje resursa računara na najbolji mogući način. Pored ovih, on vrši i kontrolnu funkciju - kontroliše da li se računar koristi na odgovarajući način i sprečava eventualne greške. Operativni sistem često vodi i evidenciju korišćenja resursa, događaja na sistemu, otkaza sistema i sl. Mesto operativnog sistema u okviru računarskog sistema se može prikazati šemom na slici 1. OPERATIVNI SISTEM APLIKATIVNI SOFTVER KORISNICI HARDVER
Slika 1. Struktura računarskog sistema. Najčešće se operativni sistem i definiše prema mestu koje zauzima u njoj: Operativni sistem je skup programa koji predstavljaju interfejs između korisnika i hardvera računarskog sistema [10]. Druga definicija koja se takođe često koristi je vezana je za resurse kojima operativni sistem upravlja: Operativni sistem je skup programa za upravljanje: procesorom (jednim ili više), operativnom memorijom, I/O uređajima i fajlovima [10]. Klasifikacija operativnih sistema Jedna od najčešćih podela operativnih sistema [10], vrši se na osnovu broja korisnika i programa koji u jednom trenutku koriste računarski sistem. Po ovom kriterijumu operativni sistemi se dele na: • monokorisničke/monoprogramske operativne sisteme kod kojih postoji samo jedan korisnik i jedan program koji se izvršava u bilo kom trenutku vremena. Personalni računari rade sa ovakvim operativnim sistemima - CP/M, DOS... • multikorisničke/monoprogramske operativne sisteme kod kojih više korisnika koriste jedan isti program. Ovakav operativni sistem srećemo kod namenskih uređaja - rezervisanje avionskih karata, obrada poštanskih usluga... • multikorisničke/multiprogramske operativne sisteme koji predstavljaju najopštiji slučaj. U ovom slučaju različiti korisnici izvršavaju različite programe. Izvršavanje programa je kvaziparalelno ili kako se to češće kaže konkurentno. Program se izvršava za vreme dok drugi program čeka na neki događaj (na periferiju koja je znatno sporija od procesora, ili neki resurs zauzet od strane drugog programa koji je višeg prioriteta od tekućeg). Time se obezbeđuje paralelan rad procesora i periferije što doprinosi boljoj iskorišćenosti procesora. Druga podela operativnih sistema [10] se vrši na osnovu tipa obrade i komunikacije sa korisnikom: • Operativni sistemi sa paketnom obradom su najstariji po vremenu nastanka, a ime im potiče iz vremena kada su programi unošeni putem bušenih kartica. Poslovi se izvršavaju onim redosledom kojim pristižu u red poslova spremnih za izvršavanje. Često se poslovi dele u
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
16
više redova (klasa) po hitnosti njihovog izvršavanja. Skoro svi savremeni operativni sistemi nude i ovaj tip obrade (čak i operativni sistemi namenjeni personalnim računarima). • Operativni sistemi sa raspodijeljenim vremenom ("Time Sharing") su klasa kojoj pripadaju skoro svi savremeni multiprogramski operativni sistemi. Svakom od procesa (korisnika) se dodeljuje određeni kvant vremena u kome isti dobija na korišćenje procesor - interval u kome se program izvršava. Po isteku kvanta vremena procesor se oduzima tekućem i dodeljuje drugom procesu (korisniku). • Operativni sistemi za rad u realnom vremenu predstavljaju treću klasu operativnih sistema. Njihova namena je upravljanje industrijskim procesima i mašinama, to jest obrada spoljnih asinhronih događaja. Spadaju u klasu multiprogramskih operativnih sistema od kojih se traži da ispune zahtev reakcije u nekom fiksiranom vremenskom intervalu. U slučaju da ovaj uslov nije zadovoljen mogući su gubitci vitalnih podataka i katastrofalne posledice usled nereagovanja sistema. Struktura operativnih sistema Zavisno od stepena složenosti i načina realizacije operativni sistemi po strukturi mogu biti vrlo raznoliki. • Jednostavni, mali operativni sistemi mogu imati takozvanu monolitnu strukturu, to jest predstavljati skup programa koje poziva korisnički program i koji se međusobno pozivaju u cilju obavljanja određenih funkcija. • Za veće operativne sisteme, kod kojih je broj funkcija koje se od sistema traže znatno veći, ovakva struktura je nepogodna, pa se preporučuje takozvana slojevita (spratna) struktura. Programi se grupišu u slojeve koji se označavaju brojevima: 1, 2, ..., n. Pri tome se podrazumeva da moduli sloja 5 pozivaju samo module sloja 4, moduli sloja 4, samo module sloja 3 itd. Često se ovo pravilo ne poštuje do kraja pa moduli sloja 5 mogu da pozivaju i module sloja 3, na primer. Dva primera slojevite strukture data su na slici 2.: KORISNIČKI PROGRAMI FAJL SISTEM UPRAVLJANJE I/O UREĐAJIMA GORNJI NIVO UPRAVLJANJA PROCESIMA UPRAVLJANJE OPERATIVNOM MEMORIJOM DONJI NIVO UPRAVLJANJA PROCESIMA HARDVER
6 5 4 3 2 1 0
KORISNIČKI PROGRAMI FAJL SISTEM UPRAVLJANJE I/O UREĐAJIMA UPRAVLJANJE MEMORIJOM JEZGRO PROCESIMA) HARDVER
OPERATIVNOM (UPRAVLJANJE
Slika 2. Dva primera operativnih sistema sa slojevitom srukturom.
U jednostavnijoj varijanti takozvano jezgro (kernel), sadrži samo dio za upravljanje procesima (Pod terminom upravljanje procesima podrazumeva se dodeljivanje procesora određenom procesu). Svi ostali moduli nalaze se van jezgra. Jezgro operativnog sistema se po pravilu pravi tako da radi u privilegovanom režimu rada - nijedna druga rutina ni događaj ne može prekinuti izvršavanje rutina koje mu pripadaju. • Treći pristup realizaciji operativnog sistema koristi tzv. klijent - server koncepciju. Sve funkcije operativnog sistema realizuju se pomoću procesa koji se nazivaju serveri. Korisnički programi se nazivaju klijenti i u okviru njih se vrši pozivanje funkcija i preuzimanje rezultata. Jezgro operativnog sistema pri tome služi samo za organizaciju komunikacije između klijenata i servera (slika 3.). •
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
PROCES KLIJENT 1
PROCES KLIJENT 2
17
PROCES KLIJENT N
JEZGRO OPERATIVNOG SISTEMA PROCES SERVER 1
PROCES SERVER 2
PROCES SERVER N
Slika 3. Struktura operativnog sistema sa klijent-server arhitekturom.
Komunikacija korisnika i operativnog sistema Komunikacija korisnika i operativnog sistema se odvija putem sistemskih poziva. Njima se iz korisničkog programa pokreću funkcije koje obezbeđuje operativni sistem. Sistemski pozivi u okviru korisničke aplikacije imaju izgled naredbi viših programskih jezika. Na tom mestu prevodilac ubacuje makroproširenje - niz instrukcija koje procesor mora da izvrši da bi se pokrenula funkcija operativnog sistema. Njima se obezbeđuje prenos parametara sistemskog poziva na mesto gde ih operativni sistem očekuje, poziva se funkcija operativnog sistema, i vraćaju rezultati sistemskog poziva.
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
18
OPERATIVNI SISTEMI ZA RAD U REALNOM VREMENU Operativni sistemi u realnom vremenu igraju ključnu ulogu u najvećem broju sistema za rad u realnom vremenu. Obično se zahteva da operativni sistem dobro upravlja resursima sistema, tako da se korisnik može usredsrediti na probleme koji su specifični za aplikaciju, umesto na pitanja vezana za sam sistem. Međutim, u sistemima za rad u realnom vremenu operativni sistem i aplikacija su mnogo tešnje povezani nego u klasičnim višekorisničkim sistemima. Susrećemo se sa istom dilemom koja je ranije navedena; kako da se obezbedi visok nivo apstrakcije za programere u realnom vremenu, a da se i dalje omogući rad sa vremenskim ograničenjima, koja su nerazdvojivo povezana sa samom implementacijom i okruženjem. Da bi se izbegli režijski troškovi, sistem koji radi u realnom vremenu često koristi redukovanu, optimiziranu varijantu operativnog sistema (ponekad samo jezgro sistema i osnovni ulazno/izlazni sistem), koja mora posedovati sledeće osobine: • brzo menja konteksta procesa • zauzima malo prostora • brzo odgovara na spoljnje prekide • minimizira interval u kome su prekidi zabranjeni • pri upravljanju memorijom dozvoljava i fiksne i particije promenljive dužine • omogućuje zaključavanje koda i podataka u memoriji • omogućava sekvencijalne datoteke koje akumuliraju podatke velikom brzinom • jezgro sistema podržava sat realnog vremena • omogućuje generisanje alarma pri isteku predefinisanog intervala • omogućuje zakašnjavanje, pauziranje i restauriranje procesa po isteku definisanog vremena, itd. Ostale osobine, kao multitaskig, komunikacioni i sinhronizacioni mehanizmi kao što je semafor, poštansko sanduče, signal, događaj, se podrazumevaju u savremenim operativnim sistemima, pa i u onima koji nisu namenjeni radu u realnom vremenu. Međutim, u operativnim sistemima namenjenim primenama u realnom vremenu, svi ovi mehanizmi moraju biti brzi. Naravno, brzina je relativan pojam, te i primenjivost operativnog sistema zavisi od vremenske kritičnosti konkretne aplikacije. Problem raspoređivanja procesa je ipak najkritičniji u aplikacijama koje rade u realnom vremenu. Osnovni kriterijumi pri raspoređivanju su vreme izvršavanja i prioritet procesa. Vreme izvršavanja procesa je u opštem slučaju neodređeno. Ako se uzme u obzir najgori slučaj (najduže moguće vreme izvršavanja), koje je obično mnogo duže od prosečnog vremena izvršavanja, može doći do slabog iskorišćenja resursa. Ako se obezbedi dovoljno procesorske snage (i ostalih resursa) tako da svi procesi zadovol je svoje vremenske zahteve čak i pri vršnom opterećenju, onda je vrlo verovatno da će pri prosečnom opterećenju resursi biti slabo iskorišćeni. Pri tom je neizvesno da li će u eksploataciji sistema uopšte doći do situacije, predviđene metodom najgoreg slučaja, zbog koje je sistem inicijalno predimenzionisan. Naravno, u aplikacijama kao što su kontrola vazdušnog saobraćaja ili vojni C 2 sistemi (komanda i kontrola), vrlo je važno da rade logički korektno i efikasno posebno pri vršnim opterećenjima. Rešenje mora da zadovolje zahteve najkritičnijih procesa (onih s najvećim prioritetom). Pošto obično ne postoji korelacija između zadatog vremena izvršenja i kritičnosti (prioriteta) procesa. to je raspoređivanje procesa sa ciljem maksimiranja broja vrlo kritičnih taskova koji se izvrše pre definisanog vremena (deadline) netrivijalan problem. Kao što je već rečeno, većina današnjih operativnih sistema za rad u realnom vremenu koristi raspoređivanje procesa bazirano na prioritetu. Ovo znači da se dva nekorelisana kriterijuma, kritičnost i vreme izvršavanja, moraju pretočiti u jedan - prioritet. Ovo se obično radi iterativno uz intenzivno korišćenje simulacije. Inicijalno, prioritet se dodeljuje procesu samo na bazi njegove kritičnosti i sistem se testira,. Ukoliko se neki kritični procesi ne izvrše pre definisanog vremena (deadline-a) ili je faktor iskorišćenja resursa nizak, prioriteti se koriguju ili se optimizira kod kritičnih procesa. Promene prioriteta i/ili optimizacija koda se produžava dok se ne postignu zadovoljavajuće performanse. Naravno, ove tehnike su podložne greškama. Na primer, vrlo je teško predvideti kako dinamički
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
19
aktivirani procesi komuniciraju sa ostalim aktivnim procesima, u uslovima deljenja i blokiranja resursa i vremenskih ograničenja. Blokiranja koja su neophodna zbog očuvanja konzistentnosti deljenih resursa posebno pogubno utiču na efikasnost sistema, a u slučaju asinhronih procesa, kakvih je mnogo u aplikacijama u realnom vremenu, teško je predvideti kad će doći do konflikta na deljenim resursima, koliko procesa će biti u konfliktu, koliko dugo će procesi biti blokirani, itd. Do projektnih odluka se dolazi nakon dugotrajnih i mukotrpnih simulacija i testiranja. Svaka i najmanja promena zahteva novu rundu intenzivnog testiranja, itd. Sve u svemu, celokupna filozofija projektovanja sistema u realnom vremenu, tera programere da napuštaju tehnike softverskog inženjerstva i strukturnog projektovanja, a rezultujući sistemi nisu naročito adaptivni i jednostavni za održavanje i proširivanje. S druge strane, tipično je za ove sisteme, kao što su automatizovane fabrike ili kontrola vazdušnog saobraćaja, da imaju dug vek, u toku kog se unapređuju i proširuju, pa je neophodno da bude zadovoljen uslov jednostavnosti održavanja i proširenja. Pojava operativnih sistema za rad u realnom vremenu, koji su projektovani tako da bar u izvesnoj meri garantuju odziv na spoljašnji događaj u fiksnom vremenskom intervalu, predstavljala je prekretnicu u ovoj oblasti. Pisanje i testiranje aplikacije je olakšano time što je veliki broj funkcija koje su neophodne za rad računarskog sistema već ugrađen u sam operativni sistem. Time je korisnik dobio jezgro na koje se njegova aplikacija naslanja sa već definisanim i proverenim funkcijama. Pri pisanju aplikacije za kontrolu složenijih procesa u nekom od nižih programskih jezika, najveća pažnja morala je biti posvećena podeli resursa računara, sinhronizaciji događaja, komunikaciji... U okviru operativnih sistema za rad u realnom vremenu ove funkcije već postoje kao standardne. Takođe, korišćenjem koncepta multiprogramiranja, obezbeđeno je da se računar koristi na najbolji mogući način, to jest omogućeno mu je izvršavanje više različitih poslova. Operativni sistemi za rad u realnom vremenu se mogu klasifikovatiu tri grupe: • mali, brzi, namenski operativni sistemi. U ovu klasu spadaju komercijalno raspoloživi sistemi za rad u realnom vremenu ( VRTX32, iRMX, QNX, PDOS, pSOS, VCOS,...) i operativni sistemi urađeni od strane samih pisaca aplikacije ("homegrown"). Namenjeni su takozvanim "embedded" aplikacijama kod kojih se traži brzo i pouzdano izvršavanje. • "real time" proširenja komercijalnih operativnih sistema. Ovoj klasi pripadaju komercijalni operativni sistemi prilagođeni za rad u realnom vremenu (RT-UNIX, RT-POSIX, RTMACH, CHORUS...). Za njih je karakteristično da obezbeđuju bolje razvojno okruženje i familijarnost sa korisnicima, ali su sporiji i nepouzdaniji od prethodne grupe. • treću grupu čine eksperimentalni operativni sistemi za rad u realnom vremenu. Pisani su sa zadatkom da zadovolje specifične zahteve i nisu komercijalno raspoloživi. Ova poslednja grupa operativnih sistema obično nastaje na univerzitetima i institutima i služi kao eksperimentalna platforma, za neke od važnih istraživačkih tema u oblasti operativnih sistema namenjenih sistemima koji rade u realnnom vremenu, kao što su: • Upravljanje resursima uslovljeno vremenom. Kada više procesa čeka na pristup deljivom resursu, tradicionalno se primenjuje FIFO strategija. Međutim, ova strategija u potpunosti ignoriše vremenska ograničenja procesa. Potrebno je razviti strategije alociranja koje će biti u stanju da ispoštuju zahteve raspoređivanja u realnom vremenu. Takve upravljačke strategije bi trebalo upotrebljavati ne samo kada je u pitanju procesor, već i za memorije, ulazno-izlazne i komunikacione resurse. U stvari, cela filozofija operativnih sistema, koja tretira procese i njihove zahteve za resursima kao slučajne, je pod znakom pitanja. Potrebno je razviti nove modele. • Mogućnosti operativnog sistema prilagođene potrebama specifičnog problema. Funkcije operativnog sistema u realnom vremenu bi trebalo da budu u stanju da se prilagođavaju različitim potrebama korisnika i sistema. Na primer, operativni sistem u realnom vremenu bi trebalo da obezbedi razdvajanje između "strategije" i "mehanizma" raspoređivanja. Tako bi korisnik mogao da bira algoritam za raspoređivanje resursa u realnom vremenom koji je najpogodniji za određenu aplikaciju ili situaciju. U distribuiranim aplikacijama, mehanizam transakcija izgleda
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
20
ima mnogo prednosti. Zbog toga, operativni sistem u realnom vremenu bi trebalo da podržava transakcije sa vremenskim ograničenjima. U budućim istraživanjima treba identifikovati skup efikasnih primitiva operativnog sistema potrebnih da bi se podržala integracija protokola zaključavanja, protokola odobravanja operacija i protokola oporavka - pri čemu posebno treba obratiti pažnju na vremenska ograničenja. Posebno, oporavak na osnovu jednostavnog poništavanja efekata neke operacije u mnogim situacijama nije moguće primeniti, pa se zahteva neki algoritam koji bi propagiranjem kroz sistem otklonio grešku. • Integrisana podrška raspoređivanju na nivou celog sistema. Strategije raspoređivanja u realnom vremenu se moraju primeniti na resurse sistema, procese aplikacije kao i prilikom projektovanja samog operativnog sistema. Posebnu pažnju treba posvetiti integrisanju komunikacija u realnom vremenu sa raspoređivanjem procesora u realnom vremenu, kao i sa bazama podataka u realnom vremenu za velike, složene sisteme u realnom vremenu. Da bi sekvenca akcija mogla da zadovolji vremenska ograničenja, moraju biti zadovoljena ograničenja u vezi redosleda izvršavanja, pri čemu resursi moraju biti dostupni na vreme za svaku akciju sekvence. Kašnjenja na bilo kom nivou procesa mogu prouzrokovati prekoračenja vremenskih ograničenja.
Pojam multiprogramiranja Multiprogramiranje se javilo kao rezultat potrebe da se što je moguće bolje iskoristi računarski sistem. To se postiže istovremenim unošenjem više programa u memoriju računara, pri čemu se procesor naizmenično dodeljuje svakom od njih po nekom usvojenom kriterijumu. Time se postiže da procesor u svakom trenutku ima šta da radi, čime se postiže veća iskorišćenost procesora uz istovremeno smanjenje srednjeg vremena potrebnog za izvršavanje pojedinih poslova. Kao ilustrativan primer može poslužiti sistem za akviziciju podataka. U okviru sistema se izvršavaju četiri funkcije sledećim redosledom: C n
tc
Ln
tl
• prikupljanje podataka COLLECT © • smeštaj podataka na disk LOG (L) • statistička analiza podataka STAT (S)
t
Sn
R n
tr
C n+1
tc
Slika 4. Sekvencijalno izvršavanje programa.
- štampanje rezultata obrade REPORT ® Ukoliko se u izvršavanju programa ne koristi koncept multiprogramiranja, tada je njegovo izvršavanje linijsko (sekvencijalno) i može se predstaviti dijagramom toka kao na slici 4. U okviru pojedinih faza izvršavanja postoje periodi u toku kojih procesor ne obavlja nikakvu funkciju već se vrti u petlji čekajući odziv periferije. To su: tc - vreme u kome procesor čeka rezultat sa ADC (analognodigitalnog konvertora); tl - vreme u kome procesor čeka na upis podataka na
disk; tr - vreme čekanja odziva štampača. Primenom koncepta multiprogramiranja mogu se iskoristiti ovi periodi - umesto da procesor čeka na periferiju, on u datom intervalu izvršava drugu funkciju sistema. Na primer istovremeno sa upisom podataka na disk može se pokrenuti i njihova statistička analiza. Ili istovremeno sa štampanjem izveštaja može se pokrenuti novo prikupljanje podataka. Izvršenje programa u ovom slučaju je predstavljeno dijagramom toka prikazanom na slici 5.
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
21
Na ovaj način postiže se bolja iskorišćenost procesora - povećava se količina obavljenog posla i ubrzava izvršavanje celokupne funkcije sistema. C n -1 L n -1
R n -2 S n -1
C n Ln
R n -1
t
Sn C n+1
R n
Slika 5. Multiprogramsko izvršavanje programa. Da bi se omogućilo ovakvo izvršavanje programa neophodno je konstruisati mehanizme kojima se omogućava prelazak sa jednog dela programa na drugi, razmena podataka i međusobna sinhronizacija delova programa. Pri svemu tome dio programa koji je dobio procesor ne sme osetiti nikakve posledice ovakvog načina rada - mora imati privid da procesor čitavo vreme pripada samo i isključivo njemu. Ovo je ostvareno organizovanjem delova programa u procese. Komunikacija i sinhronizacija između procesa je predata operativnom sistemu. Pojam procesa Procesom se naziva najmanji segment programa koji se može samostalno izvršavati (često se u literaturi kao sinonim koristi i pojam task). Njime se obezbeđuje jedna ili više funkcija (akcija) računarskog sistema. On predstavlja programsku celinu kojoj su dodeljeni određeni resursi (memorijski prostor za smeštaj programa i podataka, stek, strukture za sinhronizaciju i komunikaciju sa drugim procesima...) i koja konkuriše za zajedničke resurse (procesor, memorijski prostor - ukoliko ukupni prostor nije dovoljan da zadovolji potrebe svih procesa, komunikacioni kanali, diskovi, štampači...). Iako predstavlja na neki način zaokruženu celinu, jedan proces sa drugim može biti vezan i uslovljen na više načina - u obliku ulaza/izlaza, redosleda izvršavanja i td. KREIRANJE PROCESA I PRATEĆIH STRUKTURA TELO PROCESA BRISANJE PROCESA I PRATEĆIH STRUKTURA Slika 6. Tipična struktura procesa.
U opštem slučaju struktura programa organizovanog u obliku procesa izgleda kao na slici 6. Telo procesa se sastoji od naredbi kojima se ostvaruju funkcije procesa. U okviru ovih naredbi se nalaze i naredbe sistemskih poziva operativnog sistema. Njima se vrši razmena podataka i sinhronizacija sa drugim procesima ili sa apsolutnim vremenom. Oni omogućavaju predavanje procesora drugom procesu ukoliko se desi neki od sledećih slučajeva: • proces se izvršio i više nije neophodno njegovo postojanje - vrši se njegovo brisanje; • proces je u izvršavanju došao do tačke u kojoj mora da čeka na neki događaj ili na to da neki od neophodnih resursa postane raspoloživ; Poseban slučaj predstavljaju operativni sistemi sa vremenski deljenim procesorom ( ”time-sharing” ) i operativni sistemi sa dispešerom takozvanim ”preempting” dispečerom kod kojih izvršavanje procesa može biti prekinuto kao posledica prekida koji dolazi od strane tajmera ili neke druge periferije. Predavanjem procesora drugom procesu koji je spreman za izvršavanje povećava se iskorišćenost procesora. Predaja resursa računara (procesora, memorije, I/O uređaja...) jednom procesu od strane drugog, vrši se uvek posredstvom operativnog sistema. Predaja samog procesora vrši se od strane dela operativnog sistema koji se naziva dispečer (”scheduler”) na osnovu kriterijuma usvojenih od strane projektanta operativnog sistema ili samog korisnika.
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
22
Deskriptor procesa Da bi multiprogramski operativni sistem ispravno funkcionisao on mora znati stanje u kome se nalazi svaki od procesa. Pored toga proces pri dobijanju procesora mora nastaviti iz one tačke u kojoj je stao i pri tome ne detektovati da je bio prekidan. U trenutku kada se procesu oduzima procesor on mora sačuvati podatke neophodne za nastavak rada. Kako se to izvodi? U tu svrhu se koristi deskriptor procesa, odnosno Kontrolni blok procesa (Process Control Block - PCB). Svaki aktivan proces poseduje pripadajući PCB koji je njegova slika ka operativnom sistemu [10]. Šta sve jedan PCB mora da sadrži? Primer jednog Kontrolnog bloka procesa dat je na slici 7. Njegova uloga je da sačuva sve relevantne podatke o procesu u trenutku gubljenja procesora, da bi po ponovnom dobijanju procesora operativni sistem mogao da rekonstruiše stanje u kojem je proces prekinut. Ti podaci se čuvaju u delu PCB koji se naziva kontekst. Ponekad se kontekst ne nalazi u samom PCB već samo pokazivač na isti. U područje konteksta se ne smeštaju samo registri procesora (neki procesori pri prekidu automatski sačuvaju sve registre na steku). Tu mogu biti i drugi relevantni podaci - registri matematičkog procesora ukoliko postoji, podaci vezani za neku od periferija kojoj procesi pristupaju na različit način (svaki put se mora nanovo izvršiti inicijalizacija)... IDENTIFIKATOR PROCESA STANJE (STATUS) PROCESA PRIORITET PROCESA POINTERI ZA POVEZIVANJE U LISTE PODRUČJE ZA SMEŠTAJ KONTEKSTA PROCESA Slika 7. Primer Kontrolnog bloka procesa (PCB-a).
Pored konteksta PCB mora da sadrži i druge podatke neophodne za rad operativnog sistema. Tu je najpe identifikator svakog procesa - najčešće prirodan broj. Da bi se znalo u kom stanju se proces nalazi (da li je spreman za izvršavanje ili ne, a ako nije zbog čega nije) u okviru PCB se čuva i status procesa. S obzirom da većina operativnih sistema (svi operativni sistemi za rad u realnom vremenu) imaju dispečer sa algoritmom zasnovanom na dodeljivanju prioriteta svakom od procesa, to se u PCB smešta i ova veličina. Pointeri za povezivanje u liste služe, kao što im i ime kaže, za povezivanje kako PCB-a u liste tako i drugih struktura sa kojima operativni sistem radi (na primer poruka). Treba napomenuti da PCB ne mora zauzimati kontinualan blok memorije. On se može sastojati i od više tabela u okviru kojih se čuvaju podaci za sve procese. Kontinualan PCB poseduju operativni sistemi koji dozvoljavaju dinamičko kreiranje procesa. U tom slučaju, PCB se može nalaziti bilo gde u memoriji pa je praktičnije držati sve podatke na okupu. Nasuprot njima, operativni sistemi koji ne dozvoljavaju dinamičko kreiranje procesa (ili se definiše maksimalan broj procesa pri inicijalizaciji) često dele PCB na delove koje grupišu za sve procese na jednom mestu. Time se unekoliko može dobiti na brzini izvršavanja poziva operativnog sistema, ali se i gubi na zauzeću memorije od strane procesa koji ne postoje, a za koje je rezervisan prostor. Stanja procesa Da bi se definisala trenutna faza u kojoj se jedan proces nalazi uvode se takozvana stanja procesa. Njihova definicija varira zavisno od tipa operativnog sistema. U multiprogramskom okruženju, proces postoji i prelazi između sledeća 4 stanja: • stanje izvršavanja (executing); • stanje spreman za izvršavanje (ready); • stanje suspendovan (suspended) i • stanje neaktivan (dormant). Blok šema sa prikazom stanja i prelazima iz jednog u drugo data je na slici 8. U stanju izvršavanja (executing) se nalazi proces koji ima kontrolu nad procesorom i čije se instrukcije izvršavaju. U ovom stanju se može nalaziti samo jedan proces.
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
23
Execut i ng 7
2 8
1 4
Ready
9
3
5
Dor mant
Suspended 6
Slika 8. Stanja procesa i prelazi iz stanja u stanje. U stanju spreman za izvršavanje (ready) nalaze se procesi koji čekaju na dodelu procesora od strane dispečera. Oni imaju na raspolaganju sve potrebne resurse (osim procesora) i ne čekaju ni na kakav događaj. Stanje suspendovan (suspended) ima onaj proces koji čeka na neki događaj ili da traženi resurs postane raspoloživ. Suspenzija je aditivna što znači da bi proces postao spreman moraju biti uklonjeni svi pojedinačni razlozi suspenzije. Stanje neaktivan (dormant) ima proces koji još nije pokrenut ili koji je ukinut. U memoriji ne postoji PCB za ovaj proces. Izuzetak od ove definicije predstavlja takozvani nulti proces ("null", "idle") koji predstavlja proces najnižeg prioriteta. Ovaj proces ne može biti u stanjima neaktivan i suspendovan, odnosno uvek je spreman ili se izvršava. Nulti proces pokreće operativni sistem onog trenutka kada ne postoji ni jedan drugi spreman proces. U ovom procesu procesor se vrti u petlji ("praznom hodu") čekajući da neki od drugih procesa postane spreman. Prelazi između stanja procesa U multiprogramskom okruženju prelazi procesa iz jednog stanja u drugo dešavaju se pod dejstvom operativnog sistema, kao posledica spoljašnjih događaja ili poziva operativnom sistemu od strane istog ili drugih procesa. U skladu sa slikom 8. dat je pregled prelaza obeleženih brojevima za jedan referentni operativni sistem: 1.
Prelaz iz stanja spreman u stanje izvršenja vrši se putem dispečera, koji uzima proces iz liste spremnih procesa i na osnovu podataka iz pripadajućeg PCB-a prevodi proces u stanje izvršavanja. Ukoliko ne postoji nijedan spreman proces pokreće se nulti proces;
2.
Proces većeg prioriteta je u međuvremenu postao spreman, ili je istekao kvant vremena dodeljen tekućem procesu. Ovaj prelaz se dešava pri pozivu operativnog sistema ili u toku tajmerske prekidne rutine koja periodično poziva dispečer (drugi slučaj postoji samo kod nekih operativnih sistema);
3.
Proces je samog sebe suspendovao putem sistemskog poziva u kojem je tražen resurs koji nije raspoloživ ili je traženo čekanje na događaj koji se još nije desio. Neki operativni sistemi imaju i sistemski poziv kojim proces može samog sebe eksplicitno da suspenduje;
4.
Proces koji je u stanju spreman suspendovan je od strane drugog procesa (eksplicitna suspenzija);
5.
Desio se događaj na koji je proces čekao, resurs je postao raspoloživ ili je od strane drugog procesa ukinuta eksplicitna suspenzija;
6., 7., i 8. Proces je ukinut sa svoje strane ili od strane drugog procesa;
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
24
9.Proces je kreiran u toku inicijalizacije operativnog sistema ili od strane drugog procesa.
Sistemski pozivi Sistemskim pozivima se nazivaju pozivi funkcija operativnog sistema iz korisničkog programa. U korisničkim programima se ovi pozivi najčešće imaju izgled naredbi višeg programskog jezika. Na tom mestu prevodilac ubacuje makroproširenje - niz instrukcija koje procesor mora da izvrši. U tim naredbama se uglavnom obezbeđuje prenos parametara sistemskog poziva na odgovarajuće mesto gde ih operativni sistem očekuje (stek, registri, deo memorije odvojen u tu svrhu), a zatim vrši predaja upravljanja operativnom sistemu. Predaja upravljanja operativnom sistemu se izvodi na dva načina: • Osnovni način predaje upravljanja operativnom sistemu je preko naredbe koja izaziva prekid: INT n (TRAP n, SVC n). Broj n je broj prekida koji se dodeljuje sistemskim pozivima, što se čini u inicijalizaciji operativnog sistema upisom u tabelu vektora prekida. Pri ovakvom pozivu se najčešće ulazi u privilegovani režim rada. • Drugi način za poziv operativnog sistema je naredbom za poziv potprograma: JSR. Ovaj način se koristi kod procesora koji nemaju naredbu softverskog prekida (neki mikrokontroleri) i u slučajevima kada ne želimo da procesor pređe u privilegovan režim rada (da ne bi remetio rad korisnika) u kojem se zabranjuje prekid u čitavom ili kritičnom delu koda. Predaja parametara koji se koriste u sistemskom pozivu realizuje se na sledeće načine: • predaja parametara u registrima - najjednostavniji i najčešće korišćen metod. Mana ovog metoda je što je primenjiv samo u slučajevima kada je broj parametara za predaju mali; • predaja adrese područja u memoriji u kojem se nalaze parametri putem registara; • predaja parametara putem steka. Ovaj metod ima manu što remeti strukturu steka povećava neophodnu dužinu steka za svaki od proces za broj bajtova potreban za predaju parametara. U okviru nekih sistemskih poziva vrši se poziv dispečera - dela operativnog sistema koji odlučuje kada će koji proces dobiti procesor na korišćenje. Povratak iz operativnog sistema se vrši ili instrukcijom RTI - naredbom za povratak iz prekida ili instrukcijom JP I,a - naredbom za skok na indirektnu adr esu (adresu programa na kojoj je proces zaustavljen u trenutku sistemskog poziva ili oduzimanja procesora). Kreiranje i manipulacija procesima Videli smo da je proces složena struktura i da njegovo kreiranje, brisanje i manipulacija predstavlja obiman posao. Da bi se olakšao posao programeru ove funkcije se najčešće prenose na operativni sistem. U tu svrhu postoji posebna grupa sistemskih poziva za manipulaciju procesima. Njima se vrši izmena tekućeg stanja procesa od strane istog ili drugog. Sistemski pozivi se razlikuju od jednog do drugog operativnog sistema ali se najčešće implementiraju sledeći: Poziv za kreiranje procesa koji vrši kreiranje procesa i svih pratećih struktura na osnovu zadatih parametara: broja procesa, prioriteta, početne adrese, zadatog početnog stanja procesa... Poziv za brisanje procesa vrši brisanje procesa i njegovih struktura, a sve procese koji čekaju na podatke ili signal od obrisanog procesa prevodi u stanje spreman. Poziv za eksplicitnu suspenziju procesa vrši suspenziju procesa koji se trenutno izvršava ili nekog drugog procesa. Ukoliko suspenduje samog sebe, operativni sistem prevodi proces u listu suspendovanih i poziva dispečer koji pokreće proces najvećeg prioriteta.
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
25
Poziv za skidanje eksplicitne suspenzije prevodi proces suspendovan pozivom za eksplicitnu suspenziju iz reda suspendovanih u red spremnih. Ovo naravno važi samo u slučaju da ne postoji još neki izvor suspenzije procesa. Neki operativni sistemi poseduju pozive kojima se može menjati trenutni prioritet procesa, čitati trenutno stanje procesa... Pored ovih, postoje i pozivi kojima se sprečava i dozvoljava pozivanje dispečera, čime se sprečava preotimanje procesora od strane procesa višeg prioriteta u određenim kritičnim delovima koda. Zajednički resursi i kritični regioni Promenjive i uređaji kojima u okviru izvršavanja aplikacije pristupa više procesa nazivaju se zajedničkim resursima. Korisnik mora biti veoma obazriv pri njihovom korišćenju. Svaki proces može posedovati dio koda, koji se zove kritičnim regionom, u okviru koga vrši pristupanje zajedničkim resursima. Pristup kritičnom regionu mora biti uzajamno isključiv. Sve dok se proces nalazi u kritičnom regionu zabranjuje se njegovo prekidanje od strane bilo kog drugog procesa ili čak i od strane prekidne rutine. Prekidanje od strane procesa se zabranjuje ukoliko se datim resursima pristupa isključivo od strane dva ili više procesa. U tom slučaju se za zabranu prekida koriste strukture koje operativni sistem nudi za sinhronizaciju. Ukoliko se izmena stanja nekog resursa vrši od strane prekidne rutine tada se kritični region štiti zabranom prekida procesa sve dok se isti nalazi u kritičnom regionu. Komunikacija između procesa Kod multiprogramskog rada, složeni poslovi se po pravilu dele na manje module koji su jednostavniji, pregledniji, lakši za nalaženje grešaka, a uz to su i tako organizovani da imaju mogućnost paralelnog izvršavanja (vezani su za različite resurse i periferije). Svaki od njih pojedinačno predstavlja jedan proces. U svrhu razmene podataka između procesa, uveden je mehanizam koji obezbeđuje njihovu međusobnu komunikaciju. U osnovi postoje dva načina da se to izvede: • putem deljive memorije; • putem razmene poruka. Komunikacija putem deljive memorije zahteva od procesa da poseduju zajednički dio memorije. Izbor tipa i realizacija komunikacije je prepuštena autoru aplikacije. Operativni sistem je odgovoran samo za obezbeđenje zajedničke memorije. Kod drugog metoda komunikacija se odvija posredstvom operativnog sistema, odnosno sistemskih poziva za razmenu poruka. To je u mnogo slučajeva od velikog značaja jer se korisnik oslobađa razrešavanja brojnih pitanja, koja se mogu javiti pri izboru načina komunikacije između procesa: • kako se uspostavlja veza između procesa ? • može li se veza uspostaviti između više od dva procesa ? • koliko veza može postojati između svakog para procesa ? • postoji li bafer i koliki je kapacitet veze ? • da li su poruke fiksne ili promenjive dužine ? • da li je veza između procesa jednosmerna ili dvosmerna ? Zavisno od izbora projektanta operativnog sistema (odnosno programera ukoliko sam definiše komunikaciju između procesa), razlikujemo više tipova komunikacije: • direktna ili indirektna komunikacija (poruke se razmenjuju direktno između procesa ili se šalju u posebna područja zvana poštanski sandučići - procesi komuniciraju ako imaju zajedničko poštansko sanduče); • slanje procesu ili u poštansko sanduče; • simetrična ili asimetrična komunikacija (da li je veza dvosmerna ili jednosmerna);
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
26
• automatsko ili eksplicitno baferovanje (bez bafera, sa konačnim baferom i sa beskonačnim baferom); • slanje kopije ili pokazivača; • fiksna ili promenjiva dužina poruke... Svaka od ovih metoda ima svoje prednosti i mane od kojih nisu sve na prvi pogled vidljive. Stoga je mnogo bolje ukoliko brigu vezanu za izbor i eventualne probleme koji se mogu pojaviti, preuzme operativni sistem odnosno njegov projektant. Većina operativnih sistema ima već definisane načine međusobne komunikacije i njima pripadajuće strukture. Takođe mnogi operativni sistemi pružaju mogućnost definisanja maksimalnog vremena u kojem se podaci moraju razmeniti. Nakon isteka ovog vremena javlja se poruka greške procesu koji očekuje podatak. Operativni sistemi za rad u realnom vremenu najčešće koriste sledeće mehanizme za komunikaciju bazirane na razmeni poruka: Mehanizam poštanskog sandučeta ("mailbox"), Mehanizam direktne razmene poruka ("message") i Mehanizam kružnog bafera ("queue"). Mehanizam poštanskog sandučeta ("mailbox") Mehanizam poštanskog sandučeta koristi posebnu strukturu za razmenu poruka koja se naziva poštansko sanduče. Veličina zavisi od procesora i njemu pripadajućeg operativnog sistema, ali se uvek bira tako da se u njoj može smestiti pokazivač (pointer) kojim se može obuhvatiti kompletan adresni prostor (ili onaj dio memorije koji je predviđen za razmenu poruka). Pred operativnim sistemima, koji poseduju ovu strukturu kao zadatak se nameće razrešenje dve sledeće situacije: - šta uraditi ako u "mailbox" istovremeno pristignu dve poruke (ili za vreme obrade jedne od njih), a da se pri tome ne izgubi ni jedna od njih? - šta uraditi ako neki od procesa traži poruku od datog procesa za produžetak svog rada? Ili preciznije šta ako to isto zahteva više procesa istovremeno? Ovaj problem neki operativni sistemi razrešavaju time što pri kreiranju "mailbox"-a generišu i dve liste - jednu sa procesima koji upisuju poruke, a drugu sa procesima koji čekaju prispeće poruke (ukoliko je "mailbox" prazan). Pri tome se novi procesi u liste ubacuju na osnovu dva kriterijuma - na osnovu prioriteta pošiljaoca ili po FIFO kriterijumu. Drugi operativni sistemi, umesto ulazne liste koriste jednu drugačiju organizaciju - u samoj poruci nalazi se polje koje služi za međusobno povezivanje poruka. Često se i lista procesa koji čekaju na poruku izbacuje, a umesto nje se u PCB-u ubacuje polje kojim se isti povezuju. Najjednostavniji metod je da se poruke uopšte i ne povezuju, već da se njihova obrada prepusti korisniku. U slučaju da neka poruka stigne a da prethodna nije očitana, pošiljaocu poruke se prosleđuje poruka o grešci a programeru ostavi eventualna obrada greške. Ovoj strukturi se pristupa preko sistemskih poziva za upis i čitanje. Sistemski poziv za upis u "mailbox", upisuje vrednost pokazivača na poruku u "mailbox". Ukoliko već postoji prisutna poruka koja još nije obrađena tada se vrši povezivanje sa prethodnom porukom na već pomenuti način. U slučaju da postoji proces koji je suspendovan i čeka na prijem poruke, vrši se njegovo prevođenje u stanje spreman i predaje mu se pokazivač na poruku. Proces se skida iz reda odnosno liste procesa koji čekaju na poruku. Nakon ovoga se poziva dispečer koji pokreće proces sa najvećim prioritetom. Sistemski poziv za čitanje "mailbox"-a ukoliko je isti prazan vrši suspenziju procesa sve do prispeća poruke. Broj procesa se stavlja u listu za čitanje, a nakon toga poziva dispečer. Ukoliko "mailbox" nije prazan (postoji pokazivač na poruku u njemu), procesu se predaje njegov sadržaj, a sadržaj "mailbox-a" se čisti i u njega upisuje pointer na sledeću poruku. Mehanizam direktne razmene poruka ("message") Poruka je struktura fiksne ili promenjive dužine koja se koristi za razmenu podataka između dva (ili više) procesa [3]. Poruka pored dela u kome su smešteni podaci najčešće sadrži i takozvano zaglavlje poruke. U zaglavlju se smeštaju polja koja operativni sistem koristi za svoje potrebe. To su obično
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
27
dužina poruke, adrese odredišnog i procesa pošiljaoca, polje za povezivanje poruka u lanac (linkovanje) i neka komandna polja (slika 9.).
polje za povezivanje dužina poruke proces pošiljalac proces primalac komandno polje polje podataka Slika 9. Struktura poruke ("message").
Svrha polja za povezivanje je u tome što se izuzetno retko razmena poruka vrši kopiranjem njenog sadržaja, već se to čini dostavljanjem njene adrese (pokazivača). U slučaju da isti proces dobije više poruka one se povezuju u liste time što prethodna u polju za povezivanje nosi adresu sledeće. Adresa prve poruke u listi se najčešće nalazi u Kontrolnom bloku procesa, a poslednja poruka u nizu u svom polju za povezivanje ima oznaku kraja liste (nulu ili vrednost koja nikako ne može biti adresa neke poruke). Kako se prenošenje podataka putem poruka vrši bez kopiranja sadržaja, to je ovaj metod komunikacije izuzetno brz. Iz datog razloga koristi se u svim slučajevima u kojima je neophodno obezbediti brz protok informacija između dva procesa. Mehanizam kružnog bafera ("queue") Kružni bafer (slika 10) je struktura fiksne (i konačne) dužine namenjena razmeni podataka između procesa. Sastoji se od polja za smeštaj podataka (konačne dužine) i dva pokazivača - jednog za upis i drugog za čitanje. Pokazivač za upis pokazuje na prvu slobodnu lokaciju za upis podatka, a pokazivač za čitanje pokazuje na prvi nepročitani podatak. Dolaskom do kraja prostora za smeštaj podataka i jedan i drugi se ponovo vraćaju na početak. Bafer je prazan kada se pokazivač očitanih podataka izjednači sa pokazivačem Pokaziva~ za ~itanje
Najstariji podatak Najni` a adresa Najvi{a adresa
Najnoviji podatak
Pokaziva~ za upis
Slika 10. Kružni bafer upisanih. Bafer je pun i ne može da primi podatke bez njihovog prepisivanja, kada pokazivač upisa dostigne vrednost pokazivača očitanih podataka (napravi pun krug). U ovom slučaju obično se javlja poruka greške a upis se zabranjuje ili dozvoljava zavisno od realizacije rutina koje ovaj posao obavljaju. Podaci u kružni bafer mogu biti upisivani od strane više procesa, a isto tako i očitavani. Mnogo češći slučaj da upis u kružni bafer vrši jedan proces, a očitavanje takođe samo jedan proces. Ukoliko dva ili više procesa uzimaju podatke iz kružnog bafera, tada se pri odlučivanju koji će od njih prvo dobiti podatak koriste dva kriterijuma. Prvi je FIFO, a drugi je na osnovu prioriteta - podatak dobija proces sa većim prioritetom. Koji će od ova dva kriterijuma biti primenjen zavisi od operativnog
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
28
sistema. Neki operativni sistemi dozvoljavaju mogućnost izbora - kriterijum se navodi pri kreiranju ove strukture. S obzirom da se transfer podataka vrši kopiranjem i da se za svaki preneseni podatak pozivaju najmanje dva sistemska poziva (za upis i čitanje podatka), prenos podataka je sporiji neko pri prenosu poruka. Iz tog razloga se ova struktura izbegava u slučajevima kada je potrebna velika brzina prenosa podataka. Osobina ove strukture jeste da čuva hronološki redosled događaja. Zbog toga se često koristi za prihvat (ili izdavanje) podataka tipa niza karaktera koji stižu (ili se izdaju) asinhrono, kao i za druge tipove baferisanja. Ovoj strukturi se pristupa preko sistemskih poziva za čitanje i upis. Pozivi za upis u kružni bafer vrše upis podatka na kraj liste i pomeraju pokazivač za upis na prvu slobodnu lokaciju za jedno mesto (FIFO redosled upisa). Ukoliko nema slobodnog mesta, tada se prepisuje podatak i javlja poruka o grešci ili što je mnogo češće suspenduje se proces pošiljalac sve do oslobađanja prostora za smeštaj podatka. Pozivi za čitanje iz kružnog bafera vrše čitanje podatka sa vrha liste i pomeraju pokazivač pročitanih podataka za jedno mesto. Ukoliko nema podatka u kružnom baferu, tada se proces koji je uputio poziv suspenduje i kontrola predaje dispečeru. U slučaju da postoje više procesa koji čekaju na podatak iz istog kružnog bafera, tada se u trenutku upisa ovaj prosleđuje ili procesu koji najduže čeka na podatak ili procesu sa najvećim prioritetom. Sinhronizacija procesa Procesi u multiprogramskom okruženju i pored toga što predstavljaju zaokružene celine, ne postoje sami za sebe, već je njihova uslovljenost veoma često višestruka i raznovrsna. Da bi videli kakvi se sve problemi javljaju iznećemo nekoliko karakterističnih primera: • dva ili više procesa mogu da dele određeni resurs, pri čemu istovremeno samo jedan od njih može isti koristiti (na primer zajednički komunikacioni kanal); • proces se može izvršavati tek po izvršenju drugog (ili više njih), tačno određenog procesa (obrada rezultata merenja se ne može izvršiti pre samog merenja); • proces se izvršava tek po izvršenju određenog procesa čije se izvršavanje suspenduje sve dok se dati proces ne izvrši (mehanizam klackalice); • proces postaje aktivan dešavanjem bilo kog od više događaja; • više procesa postaje spremno kompletiranjem određenog procesa; • proces se suspenduje do isteka nekog vremenskog intervala; Spisak situacija sa kojima se korisnici mogu sresti je poduži, a mnogi od njih se mogu naći u literaturi. Ovde će biti reči o mehanizmima i strukturama koje omogućavaju rešavanje postavljenih problema. Najčešće korišćene strukture za sinhronizaciju su: mehanizam semafora ("semaphor") i mehanizam događaja ("flaggroup"). Pored ovih struktura za sinhronizaciju procesa se mogu koristiti i strukture za komunikaciju između procesa. Slanje poruke bez sadržaja (ili sa proizvoljnim sadržajem) u poštansko sanduče ili putem mehanizma direktne razmene poruka može se iskoristiti za signalizaciju događaja i sinhronizaciju dva ili više procesa. Operativni sistemi često ne poseduju sve navedene strukture (ili ne u njihovoj izvornoj definiciji). Razlog za takvo stanje je u činjenici da se rad pojedinih struktura može simulirati korišćenjem već postojećih struktura za sinhronizaciju i uz malo programerskog truda. Neki operativni sistemi omogućavaju i definisanje maksimalnog vremena u kojem se mora desiti sinhronizacija sa drugim procesom u svrhu sprečavanja trajnog blokiranja procesa. Mehanizam semafora ("semaphore") Semafor je celobrojna promenjiva, čiji se sadržaj koristi za sinhronizaciju između procesa na sledeći način: procesu se dozvoljava nastavak izvršavanja samo ako je sadržaj semafora pozitivan ili ima
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
29
određenu pozitivnu vrednost. U suprotnom proces se suspenduje sve dok semafor dostigne potrebnu vrednost. S obzirom da više procesa mogu pristupati istom semaforu ovoj strukturi se pridružuje i lista procesa koji čekaju na nju (ili se suspendovani procesi ulančavaju). Procesi koji čekaju, u listu se ubacuju ili po FIFO ili po kriterijumu prioriteta. Ova struktura omogućava da u slučaju da se događaj javi više puta, svaka njegova pojava ostane zabeležena. Time se omogućava procesu koji čeka na ovu strukturu, isti toliki ili odgovarajući broj izvršavanja, u slučaju da dati proces zbog niskog prioriteta ili iz nekog drugog razloga nije bio u stanju da dobije procesor u trenutku signalizacije događaja. Strukturi se pristupa preko sistemskih poziva za signalizaciju i čekanje na semafor. Signalizacija semaforu predstavlja inkrementiranje njegovog sadržaja odnosno povećanje njegove vrednosti za definisani cio broj. Pri tome sistemski poziv obuhvata sledeće akcije: ukoliko ni jedan proces ne čeka na semafor isti se inkrementira. Ukoliko postoji proces (ili više njih), koji čeka na dati semafor isti se prevodi u stanje spreman, a zatim se vrši ažuriranje semaforu pridružene liste. U ovom slučaju se ne vrši inkrementiranje semafora. Poziv za čekanje na semafor obuhvata sledeće akcije: ukoliko je vrednost semafora veća od nule, vrši se njeno dekrementiranje a proces koji je uputio poziv nastavlja sa izvršavanjem. Ukoliko je sadržaj semafora manji ili jednak nuli, proces se suspenduje i ubacuje u listu procesa koji čekaju na dati semafor. Nakon toga poziva se dispečer koji pokreće proces najvećeg prioriteta. Mehanizam događaja ("flaggroup") Mehanizam događaja se koristi u višestrukoj sinhronizaciji - sinhronizacija jednog događaja sa više drugih, odnosno pri sinhronizaciji više događaja sa jednim. Najčešće se ostvaruje preko strukture od celog broja bajtova u kojoj svaki bit predstavlja poseban fleg odnosno događaj. Fleg može imati jedno od dva stanja: setovan ("1") - događaj se desio i obrisan ("0") događaj se još nije desio. Pri tome mogu biti obezbeđena dva tipa sinhronizacije: • disjunktivna ( "OR" - "ILI") pri kojoj proces postaje spreman pri pojavi prvog od niza specificiranih događaja; • konjuktivna ( "AND" - "I") pri kojoj proces postaje spreman tek pri pojavi svih specificiranih događaja. S obzirom da više procesa istovremeno mogu čekati pojavu određenog događaja , time se omogućava da jedan proces može svima njima da pošalje obaveštenje da se događaj desio. Korisnik ovoj strukturi pristupa preko sistemskih poziva: za setovanje flega, za čekanje na fleg i brisanje flega. Poziv za setovanje flega, postavlja jedan ili više flegova definisanih maskom na jedinicu. Procesi koji su čekali na date flegove postaju spremni za izvršavanje, a upravljanje se predaje dispečeru. Ukoliko su neki od flegova već setovani, ostali se setuju a procesu se vraća poruka greške. Pozivom za čekanje na fleg, specificiraju se događaji na koje proces čeka i da li to radi disjunktivno ili konjuktivno. Ako su se traženi događaji već desili, proces nastavlja izvršavanje. U suprotnom proces se suspenduje i poziva dispečer. Pozivom za brisanje, flegovi specificirani maskom se postavljaju na nulu. Ukoliko neki od specificiranih flegova već ima vrednost nula, procesu koji je inicirao brisanje vraća se poruka greške. Organizacija memorije U okviru adresnog prostora svakog procesora smeštaju se program i podaci sa kojima trenutno radi. U multiprogramskom okruženju u memoriji se nalazi više programa i njima pripadajućih podataka kao i program koji omogućava multiprogramski rad - operativni sistem sa svojim internim (sistemskim) promenjivim. U opštem slučaju sadržaj memorije izgleda kao na slici 11.
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
Tabela vektora prekida Operativni sistem Aplikacija definisana od strane korisnika Konstante
Sistemske promjenjive Kontrolni Blokovi Procesa Sekundarne sistemske promjenjive Sistemski stek Stekovi aktivnih procesa Stek nultog procesa
30
Memorija sa kojom raspola` e korisnik
Slika 11. Sadržaj memorije multiprogramskog operativnog sistema. Prvi (šrafirani) dio predstavlja fiksni kod: Tabela vektora prekida (Interapt Vektor Tabela), kod Operativnog sistema, kod aplikacije (kodovi svih procesa) i konstante. Ovaj dio koda se skoro uvek smešta u ROM memoriju u slučaju uređaja koji rade bez jedinica magnetnog medija. Kod nekih procesora (mikrokontroleri i signal procesori) ovaj dio memorije je i fizički odvojen od prostora za smeštaj podataka - za pristup koriste različite kontrolne signale. Drugi dio predstavlja RAM memorija koja je zauzata od strane Operativnog Sistema. Ovim delom memorije isključivo upravlja Operativni Sistem, a korisniku se zabranjuje svaki direktan pristup koji može biti fatalan po aplikaciju. Naime, u ovom delu se smeštaju: • Interne promenjive Operativnog Sistema; • Kontrolni blokovi procesa svakog aktivnog procesa; • Sekundarne sistemske promenjive - promenjive nastale pri kreiranju neke od kontrolnih struktura kojima Operativni Sistem raspolaže ("mailbox", "queue", semafor, strukture za dodelu memorije...); • Sistemski stek koji Operativni Sistem koristi uvek kada se nalazi u okviru prekidne rutine; • Stekovi za svaki od procesa, kao i za nulti proces. Treći dio memorije predstavlja slobodna memorija koja se može dinamički dodeljivati procesima i vraćati od strane procesa. To je u stvari dio kojim procesi mogu raspolagati i za koji oni konkurišu ukoliko je nedovoljan da zadovolji potrebe svih njih istovremeno. Upravljanje memorijom Upravljanje memorijom obuhvata: • vođenje evidencije o svakoj ćeliji operativne memorije; • određivanje strategije dodeljivanja memorije; • mehanizam dodele memorije, to jest stavljanja na raspolaganje • mehanizam oslobađanja memorije. Ovo je oblast u okviru koje su razvijene brojne tehnike i mehanizmi. Razlog za to je u tome što memorija, posle procesora, predstavlja najvažniji resurs računara i od načina njenog efikasnog korišćenja zavise i perfomanse računarskog sistema. Najčešće korišćeni mehanizmi dodele memorije su: • dodela memorije u particijama (fiksne ili promenjive dužine); • stranična organizacija memorije;
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
31
• segmentna organizacija memorije; • segmentno-stranična organizacija memorije; • stranična virtuelna organizacija memorije; Jedna od najvećih boljki mehanizama za dodelu memorije jeste fragmentacija (usitnjavanje) memorije. Procesi uzimaju i oslobađaju memoriju u skladu sa svojim zahtevima čiji se redosled ne može predvideti. Kao posledica toga vrlo brzo se dolazi do situacije da postoji dovoljna količina slobodne memorije, ali da je ista izdeljena na veći broj delova (fragmenata), od kojih ni jedan ne poseduje dovoljnu veličinu da zadovolji novopridošli zahtev. Svi navedeni metodi sa manje ili više efikasnosti rešavaju ovaj problem ili objedinjavanjem slobodne memorije ili prihvatanjem kontolisanog obima segmentacije u okviru definisane jedinice za dodelu memorije. Da bi se neka od ovih metoda koristila u operativnim sistemima za rad u realnom vremenu, mora zadovoljiti jednu vrlo važnu osobinu. Naime sistemi za rad u realnom vremenu moraju imati ograničeno vreme odziva na događaj ili makar u fiksnom intervalu. Kod metoda koje vrše defragmentaciju spajanjem slobodne memorije ili deljenjem memorije i programa na strane i segmente vreme odziva se ne može kontrolisati niti predvideti. Iz datog razloga najčešće korišćeni metod upravljanja memorijom je sledeći: Memorija koja je predviđena za dinamičku alokaciju deli se na regione fiksne veličine koji se nazivaju particijama. Svaka od njih se dalje deli na manje delove - blokove fiksne definisane dužine. Blokovi se pri inicijalizaciji particije povezuju u listu slobodnih memorijskih blokova. Kada neki od procesa uputi zahtev za memorijom, dodeljuje mu se blok iz liste slobodnih blokova tražene particije. Ako ne postoji slobodan blok u datoj particiji, procesu se vraća odgovarajuća poruka. Kod nekih operativnih sistema, u ovakvoj situaciji sistemski poziv prouzrokuje suspenziju procesa. Memorija koja procesu nije više potrebna vraća se particiji, pri čemu se vraćeni blok uvršćuje u listu slobodnih blokova. Ovim načinom je izbegnuta eksterna fragmentacija ali ne i interna fragmentacija u okviru samog memorijskog bloka. Time je plaćena cena kompromisu da se fragmentacija mora izbeći i da odziv na zahtev za memorijom bude definisanog trajanja. Za upravljanje memorijom se koriste sledeći sistemski pozivi: Sistemski poziv za kreiranjem particije koji zauzima traženi memorijski prostor i deli ga na ulančane blokove slobodne memorije. Sistemski poziv za dodeljivanje memorije kojim operativni sistem procesu vraća adresa alociranog bloka memorije, pri čemu isti briše iz liste slobodnih blokova. Ukoliko ne postoji slobodan blok javlja se poruka greške procesu koji je uputio poziv. Neki sistemi imaju poziv za dodeljivanje memorije kojim se proces suspenduje ukoliko ne postoji slobodan blok. Sistemski poziv za oslobađanje memorije, kojim proces vraća operativnom sistemu adresu bloka koji mu više nije potreban. Operativni sistem dati blok ubacuje u listu slobodnih memorijskih blokova. Prekidi i obrada prekida Od operativnih sistema za rad u realnom vremenu se traži da imaju što je moguće kraće vreme odziva na spoljne događaje. S obzirom da su ti događaji po svojoj prirodi asinhroni, procesor sa njima komunicira mehanizmom prekida. Za njihovu obradu su zaduženi delovi programa koji se zovu prekidne rutine. Tipična sekvenca servisiranja prekida izgleda kao na slici 12. Servisiranje traje vremenski period T i periodično je sa periodom Tp. Organizacija mehanizma prekida i prekidnih rutina treba da bude takva da: • obezbedi brzo servisiranje periferija, • minimizira kašnjenje nastalo zbog pristizanja više zahteva za prekidom u isto vreme.
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
Tp
32
t
T
...
...
Glavni program
Prekidna rutina
Slika 12. Sekvenca servisiranja prekida. Da bi se ispunili navedeni uslovi neophodno je da: • vreme T bude što je moguće kraće kako ostali zahtevi za prekidom ne bi bili previše zadržavani, • procenat zauzetosti procesora od strane prekidne rutine (odnos T/Tp) bude što je moguće manji. Kao posledica ovih zahteva, prekidne rutine u sebe uključuju samo neophodne akcije: čitanje podataka, izdavanje komandi ili predaju informacija nekom od procesa na dalju obradu. Po pristizanju zahteva za prekidom neki procesori pokreću "polling" rutinu u okviru koje se vrši utvrđivanje uzroka prekida ispitivanjem svakog od mogućih izvora prekida. Dati proces je spor, pa se mnogo češće koristi mehanizam "vektorskog" prekida. U ovom slučaju svaki od izvora prekida generiše vektor koji predstavlja indeks tabele vektora prekida. Na lokaciji određenoj indeksom u tabeli vektora prekida, nalazi se adresa dela programa zaduženog za servisiranje prekida. Ovakvim pristupom smanjuje se kako trajanje prekidne rutine T tako i odnos T/Tp. Da bi se na neki način regulisala situacija vezana za slučaj pristizanja više zahteva za prekidom istovremeno ugrađen je mehanizam prioriteta. Pri servisiranju zahteva za prekidom primenjuju se dva koncepta: • Prvi pristup je da ukoliko u toku servisiranja prekida pristigne zahtev za prekidom većeg prioriteta, tekuća rutina se prekida i servisira novopridošli zahtev. Po izvršenju rutine većeg prioriteta nastavlja se izvršavanje prekinute rutine (slika 13.). Ovaj mehanizam se naziva gnežđenjem ("nesting"). t
...
... Prekidna rutina vi{eg prioriteta Prekidna rutina ni` eg prioriteta
Slika 13. Sekvenca servisiranja "vektorskog" prekida (prvi pristup). • Drugi pristup, koji daje dobre rezultate ukoliko prekidne rutine nisu predugačke, prikazan je na slici 14. Po pokretanju prekidne rutine zabranjuje se servisiranje novopristiglih prekida za svo vreme njenog trajanja. Svi zahtevi pristigli u toku ovog perioda zaustavljaju se. Po izlasku iz prekidne rutine vrši se njihovo sortiranje i prelazak na prekidnu rutinu najvišeg prioriteta od svih pristiglih. Posledica ovakvog pristupa jeste moguće uvećanje vremena odziva za iznos trajanja najduže prekidne rutine.
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
33
t Glavni program
...
... Prekidna rutina najvi{eg prioriteta
Prekidna rutina najni` eg prioriteta
Slika 14. Sekvenca servisiranja "vektorskog" prekida (pristup dva). Ova dva pristupa se razlikuju i u veličini steka neophodnoj za ispravan rad aplikacije. U oba slučaja veličina steka treba da bude takva da zadovolji pojavu najgoreg mogućeg slučaja. To je ukoliko se koristi prvi pristup suma neophodnih veličina stekova za sve prekidne rutine plus neophodna veličina steka prekinutog procesa. Ukoliko se koristi drugi pristup, neophodna veličina steka jednaka je zbiru veličina steka prekinutog procesa i steka prekidne rutine (bira se maksimalna vrednost između prekidnih rutina koje se mogu javiti). Da bi izvršavanje prekidne rutine bilo što je moguće kraće, ista ne sme biti prekinuta od strane bilo kog procesa ma koliki bio njegov prioritet (prekidna rutina može biti prekinuta samo od strane druge prekidne rutine). Da bi se to ostvarilo operativni sistem mora voditi računa o nivou ugnežđenja prekida ukoliko je pomenuti mehanizam prisutan. U tom slučaju prekidne rutine na početku i kraju moraju imati delove koda kojima se vrši ažuriranje promenjive odvojene u tu svrhu. Ovi delovi koda se često vezuju sa drugim operacijama neophodnim pri obradi prekida u sistemske pozive, da bi se olakšao rad korisniku operativnog sistema i sprečile eventualne greške. Da bi se obezbedila komunikacija i sinhronizacija prekidne rutine sa drugim procesima koriste se dva pristupa: • zabranjuju se svi sistemski pozivi u okviru prekidnih rutina izuzev u tu svrhu odvojenog poziva kojim se proces namenjen obradi prekida prevodi u stanje spreman (ovaj poziv u sebe ne uključuje poziv dispečeru pa samim tim ni preuzimanje procesora). Proces za obradu prekida je uvek vezan sa pojavom zahteva za prekidom (odnosno sa njemu pridruženim spoljnim događajem). U svrhu sinhronizacije sa ovim događajem u samom procesu je prisutan sistemski poziv čija je uloga suspenzija procesa sve do pojave prekida. Prekidna rutina i proces za obradu prekida za ovaj slučaj izgledaju kao na slici 15: Kreiranje procesa Obrada prekida (brisanje flega, I/O akcije)
Inicijalizacija
signal int_task wait int Izlaz iz prekida
Tijelo procesa
Slika 15. Struktura prekidne rutine i procesa za obradu prekida. • operativni sistem dozvoljava samo određene sistemske pozive koji ne remete strukturu operativnog sistema. Na početku i kraju prekidne rutine nalaze se sistemski pozivi čija je svrha blokiranje i deblokiranje (ovaj poslednji i pozivanje) dispečera i prelazak na sistemski stek. Da bi se omogućilo korišćenje struktura za komunikaciju i sinhhronizaciju (predaja i uzimanje podataka od drugih procesa), a istovremeno izbeglo samoblokiranje,
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
34
uvedeni su sistemski pozivi kojima se ne vrši suspenzija procesa u slučaju da traženi uslovi nisu ispunjeni, već se samo vraća poruka o grešci. Kako od redosleda izvršavanja prekidnih rutina zavisi vreme odziva, a vrlo često i sposobnost ispravnog rada sistema, to se postavlja pitanje ko je taj koji bi trebalo da odredi prioritet pojedinih prekida. Kod nekih procesora ovaj redosled je fiksan, dok drugi dozvoljavaju izvesnu izmenu redosleda. Operativni sistemi za rad u realnom vremenu koji koriste koncepciju sa procesom za obradu prekida donekle omogućavaju redefiniciju prioriteta postavljanjem prioriteta samog procesa. Ukoliko je dužina prekidne rutine mnogo manja od dužine procesa to je uticaj prioriteta procesa veći na ukupno vreme odziva. Vreme odziva Vreme odziva predstavlja period od trenutka pojave događaja (signaliziranog zahtevom za prekid) do preduzimanja akcije vezane za taj događaj. Dati period se sastoji od više komponenti, koje će biti detaljno navedene i objašnjene. Na slici 16. je prikazan primer sa pet međusobno nezavisnih prekidnih rutina. Koje su to komponente koje ulaze u vreme odziva prekidne rutine označene sa brojem 4? U najgorem slučaju, prekidna rutina nižeg prioriteta od rutine 4 je započela izvršavanje u trenutku kada je pristigao zahtev za servisiranjem prekidne rutine. Kako se posmatra najgori slučaj, bira se najduža prekidna rutina prioriteta nižeg od rutine 4. Vreme T4+ predstavlja vreme trajanja te rutine ukoliko se radi o slučaju da su prekidi suspendovani u toku čitavog vremena izvršavanja. Ukoliko se servisiranje prekida dozvoljava u toku trajanja rutine, tada T4+ predstavlja vreme u okviru prekidne rutine nižeg prioriteta koje protekne do trenutka kada se ponovo dozvoli servisiranje prekida. t Glavni program...
... T1 T2 T3
T4+
T4b
T4
Ukupno vrijeme odziva =T4+ +T1+T2+T3+T4b
Slika 16. Vreme odziva za najgori slu~aj. Drugi član u sumi na slici 16., predstavlja zbir vremena izvršavanja svih prekidnih rutina prioriteta većeg od posmatrane. Ovaj član je prisutan u sumi bez obzira da li se u okviru prekidnih rutina višeg prioriteta dozvoljava servisiranje prekida ili ne. Da bi se obezbedilo korektno funkcionisanje periferija vezanih za prekide nižeg prioriteta, neophodno je da rutine koje obrađuju prekide višeg prioriteta budu što je moguće kraće. Treći član u sumi T4b predstavlja vreme izvršavanja koda od trenutka startovanja same prekidne rutine do trenutka kada se sprovodi konkretna akcija vezana za događaj koji je signaliziran. Ovde spadaju vreme potrebno da se na stek prenesu svi neophodni registri, vreme u okviru koga se određuje koju prekidnu rutinu pokrenuti... Ukoliko se posmatra prekid najvišeg prioriteta, tada u njegovo vreme odziva treba uključiti faktore koji ne igraju tako značajnu ulogu kod prekida nižeg prioriteta. To su pre svega trajanje najdužeg "kritičnog" regiona u okviru rutina nižeg prioriteta, trajanje najduže instrukcije procesora, kao i vreme potrebno za prelazak sa glavnog programa na prekidnu rutinu. Pomenuta razmatranja nesu uzimala u obzir tip aplikacije koji se izvršava na datom računarskom sistemu. Koliko se menjaju rezultati ukoliko se koristi operativni sistem za rad u realnom vremenu.? Kako se u okviru operativnog sistema za rad u realnom vremenu akcija pokreće tek u procesu zaduženom za obradu prekida, to u drugi član sume treba dodati vremena izvršavanja svih procesa višeg prioriteta.
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
35
Uticaj učestanosti i trajanja prekidne rutine na ostvarljivost sistema Za sistem za rad u realnom vremenu se kaže da je ostvarljiv ukoliko je u stanju da sa postojećim računarskim resursima izda rezultate obrade u zadatom, unapred definisanom vremenskom intervalu. Odnos T/Tp se koristi za procenu da li je procesor u stanju da uspešno odradi sve zadatke koji se pred njim postavljaju. S obzirom da interval između dva zahteva za servisiranjem Tp može varirati, za izračunavanje ovog odnosa uzima se najgori slučaj, odnosno njegova najmanja vrednost. Isto tako, pri izboru vremena trajanja prekidne rutine T, uzima se njeno najduže moguće trajanje. U sistemu u okviru koga se vrši servisiranje n periferija putem mehanizma prekida, procentualna zauzetost procesora servisiranjem svih prekidnih rutina mora biti manja od 100%. Ova relacija se matematički izražava formulom :
T1 / Tp1 + T2 / Tp 2 + ...+ Tn / Tpn < 10 . Smisao ove relacije jeste u tome da procesor ne sme biti zauzet sve vreme obrađivanjem prekidnih rutina što se dešava kada je ova suma veća ili jednaka od 1 (čak i ukoliko je manja, ali vrlo bliska). Ova relacija predstavlja potreban uslov za ispravno funkcionisanje sistema. Uspešno servisiranje prekida zahteva mnogo više od zadovoljenja ove relacije. Kao ilustracija neka posluži slika 17. Ukoliko Tpi predstavlja period između dva uzastopna zahteva za servisiranjem prekida i t Glavni program ...
... T1 T2 T3 Tp4
Tp4
T4
Tp4 T4
T4
T4
T4+
T4+ +T1+T2+T3+T4
Slika 17. Primer servisiranja prekida ni`eg prioriteta. (za najgori slučaj), tada za ispravno funkcionisanje sistema mora biti zadovoljena relacija za svako i [9]:
Ti + + N1T1 + N 2T2 + N 3T3 + ...+ Ti < Tpi gde Nj (j=1,...,i-1) predstavlja broj zahteva za servisiranjem prekidnih rutina višeg prioriteta pristiglih u intervalu Tpi-Ti. Dati interval predstavlja vreme koje prekidna rutina i ima na raspolaganju da na odgovarajući način odgovori na zahtev i započne sa svojim izvršavanjem.
N1 = INT ((Tpi − Ti ) / Tp1 ) + 1 N 2 = INT ((Tpi − Ti ) / Tp 2 ) + 1 ... Smisao ove relacija je da suma svih prekidnih rutina koje se mogu javiti između dva uzastopna servisiranja rutine i, mora biti manja od periode pozivanja rutine i umanjenog za vreme potrebno za servisiranje same rutine. Kod aplikacija koje koriste operativne sisteme za rad u realnom potrebno je modifikovati vremena Ti na sledeći način: u vreme Ti treba da uđe i vreme izvršavanja procesa zaduženog za obradu prekida. Takođe u sumu treba da uđu i procesi višeg prioriteta od procesa zaduženog za servisiranje rutine i kao i suma svih prekidnih rutina (bez obzira na prioritet imaju prednost u odnosu na izvršavanje bilo kog procesa).
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
36
Iz prethodnog se nameće kao zaključak: Oni događaju u sistemu koji zahtevaju vrlo brz odziv treba da imaju visok prioritet. Razlog leži u tome što broj elemenata u sumi u okviru prethodne relacije direktno zavisi od prioriteta prekida, odnosno procesa. Sistemski stek Pri svakom prekidu procesor po automatizmu prebacuje sadržaj svih ili samo nekih od registara na stek. U slučaju da više prekida dođu istovremeno, usled njihovog ugnežđenja biće potrebna značajna dužina steka. Ta je dužina u najgorem slučaju jednaka proizvodu broja prekida koji se mogu javiti i dužine neophodne za smeštaj registara pri jednom od njih. Kod procesora koji pored programskog brojača i statusne reči čuvaju i druge registre ova veličina može prevazilaziti dužinu najdužeg proces steka. Primera radi ako procesor ima 9 registara veličine 1 bajta i čuva sve svoje registre pri prekidu, za njihov smeštaj bi bilo potrebno 9 bajtova. Ukoliko u sistemu u kojem se mikroprocesor koristi radimo sa pet prekida, tada minimalna dužina steka mora biti 5x9 = 45 bajtova. Ako se sistemski poziv izvodi preko softverskog poziva prekida tada treba dodati još 9 bajtova. U slučaju nepostojanja sistemskog steka ova veličina bi se morala dodati na dužinu svakog od proces stekova. Korišćenjem sistemskog steka, veličina proces steka se smanjuje na dio potreban za smeštaj registara pri skoku u potprograme i dio za smeštaj registara pri prvom prekidu. Po prispeću prvog prekida stek pointer se inicijalizuje na početak sistemskog steka. Svaki naredni prekid će koristiti ovaj stek, a ne stek prekinutog procesa. Po izlasku iz poslednje prekidne rutine i vraćanja na nivo procesa, u stek pointer se unosi vrednost koja je u njemu bila pre pojave prekida. Na kraju recimo da ukoliko koristimo nemaskirajući prekid, koji može doći u bilo kojem trenutku nezavisno od toga da li je prekid dozvoljen ili ne, dužina steka za svaki od procesa se mora povećati za veličinu neophodnu za smeštaj registara koji se čuvaju. Razlog je u tome što se ne može obezbediti maskiranje ovog zahteva za prekidom, pa samim tim on može pristići pre prelaska na korišćenje sistemskog steka, odnosno u trenutku dok se još nalazimo na steku koji pripada procesu. Algoritmi za realizaciju dispečera ("scheduler") U memoriji računara sa multiprogramskim operativnim sistemom se istovremeno nalaze više konkurentnih procesa spremnih za izvršavanje, koji čekaju na dodeljivanje procesora. U trenutku kada aktivni proces pređe u stanje čekanja (suspendovan), jedan od procesa koji su čekali na procesor postaće aktivan. Odluku o tome koji će proces postati aktivan, donosi dio operativnog sistema poznat kao dispečer. Pri njegovom projektovanju vodi se računa o tipu operativnog sistema - njegovoj nameni, o dinamici procesa, i mnogim drugim parametrima, a sve u cilju što boljeg iskorišćenja resursa računara. Blok-šema iz koje se može videti mesto dispečera u mehanizmu dodeljivanja procesora prikazana je na slici 18. START
RED SPREMNIH TASKOVA
I/O
dispe~er
KRAJ CPU
NIZ TASKOVA KOJI ^ EKAJU NA I/O
Slika 18. Blok-šema mehanizma dodeljivanja procesora. Zavisno od toga koji se cilj želi postići vrši se izbor odgovarajućeg algoritma. Ukoliko se radi o operativnim sistemima opšte namene tada je parametar od najvećeg značaja iskorišćenost računarskog sistema i vreme čekanja korisnika. U tom slučaju se ide na algoritme koji obezbeđuju maksimalnu protočnost obrade, odnosno minimalno srednje vreme čekanja - "Shorted Job First", prioritetni algoritmi, "preemtive" algoritmi, "Round Robin"... S obzirom da operativni sistemi za rad u realnom vremenu imaju svoje specifične zahteve koji se odnose na minimizaciju vremena odziva to su i algoritmi za njih nešto drugačiji od onih korišćenih u komercijalnim operativnim sistemima.
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
37
Jedan od pristupa koji se koristi kod namenski projektovanih operativnih sistema, je dispečer zasnovan na fiksnoj tabeli pokretanja. Koristi se u sistemima kod kojih su već unapred poznati broj procesa i njihova periodičnost. Na osnovu ovih podataka se pravi tabela sa vremenima kada koji proces treba pokrenuti odnosno zaustaviti. Dispečer po dostizanju zadatog vremena pokreće naredni proces iz tabele. Ovaj pristup ima smisla samo ukoliko sistem vrši obradu periodičnih događaja, a mana mu je i to što ne dozvoljava dodavanje novih procesa. Najveći broj operativnih sistema za rad u realnom vremenu koristi "preemtive" (sa preuzimanjem) algoritme zasnovane na konceptu prioriteta. Razlog za ovoliku popularnost leži u tome što se na ovaj način omogućava posredna kontrola vremena odziva sistema na spoljašnji događaj. Svakom procesu se dodeljuje broj koji označava njegov nivo prioriteta - prednosti pri izvršavanju u odnosu na druge procese. Pri odlučivanju koji proces pokrenuti, procesor se dodeljuje procesu sa najvećim nivoom prioriteta. Karakteristično za njih je da se dispečer poziva pri sistemskim pozivima koji kao rezultat imaju promenu stanja nekog od procesa (procesa pozivaoca ili nekog drugog). Za "preemtive" algoritme je pored toga karakteristično da se dispečer poziva i pri prekidu koji kao rezultat ima premeštanje nekog procesa iz reda blokiranih u red spremnih. To može imati za posledicu da prekinuti proces izgubi procesor, iako prekid ne pripada njemu. Neki operativni sistemi za rad u realnom vremenu poseduju pored navedenih i "Round Robin" algoritam zasnovan na tome da se procesor dodeljuje procesu samo određeni kvant vremena. Ovaj mehanizam se primenjuje samo na procese istog prioriteta. Po isteku zadatog vremena proces se prekida i stavlja na kraj liste spremnih procesa, a sa vrha liste se uzima sledeći proces. Time se postiže da procesi koji oduzimaju mnogo vremena budu potisnuti na kraj liste, a sa druge strane forsiraju se procesi koji se iz liste blokiranih prebacuju u listu spremnih.
Kurs programskog jezika C++ i programiranja sistema za rad u realnom vremenu
Dragan Milićev
Objektno orijentisano programiranje u realnom vremenu na jeziku C++
Beograd, 1996.
38
Programiranje u Realnom Vremenu
Deo I Objektno orijentisano programiranje i modelovanje
Skripta za Programiranje u Realnom Vremenu
39
Programiranje u Realnom Vremenu
Uvod ∗
Jezik C++ je objektno orijentisani programski jezik opšte namene. Veliki deo jezika C++ nasleđen je iz jezika C, pa C++ predstavlja (uz minimalne izuzetke) nadskup jezika C. ∗ Kurs uvodi u osnovne koncepte objektno orijentisanog programiranja i principe projektovanja objektno orijentisanih softverskih sistema, korišćenjem jezika C++ kao sredstva. ∗ Kurs je baziran na referencama [ARM] i [Milićev95]. Knjiga [Milićev95] predstavlja osnovu ovog kursa, a u ovom dokumentu se nalaze samo glavni izvodi. Kurs sadrži i najvažnije elemente jezika C.
Zašto OOP? ∗
Objektno orijentisano programiranje (Object Oriented Programming, OOP) je odgovor na tzv. krizu softvera. OOP pruža način za rešavanje (nekih) problema softverske proizvodnje. ∗ Softverska kriza je posledica sledećih problema proizvodnje softvera: 1. Zahtevi korisnika su se drastično povećali. Za ovo su uglavnom "krivi" sami programeri: oni su korisnicima pokazali šta sve računari mogu, i da mogu mnogo više nego što korisnik može da zamisli. Kao odgovor, korisnici su počeli da traže mnogo više, više nego što su programeri mogli da postignu. 2. Neophodno je povećati produktivnost programera da bi se odgovorilo na zahteve korisnika. To je moguće ostvariti najpre povećanjem broja ljudi u timu. Konvencionalno programiranje je nametalo projektvanje softvera u modulima sa relativno jakom interakcijom, a jaka interakcija između delova softvera koga pravi mnogo ljudi stvara haos u projektovanju. 3. Produktivnost se može povećati i tako što se neki delovi softvera, koji su ranije već negde korišćeni, mogu ponovo iskoristiti, bez mnogo ili imalo dorade. Laku ponovnu upotrebu koda (software reuse) tradicionalni način programiranja nije omogućavao. 4. Povećani su drastično i troškovi održavanja. Potrebno je bilo naći način da projektovani softver bude čitljiviji i lakši za nadgradnju i modifikovanje. Primer: često se dešava da ispravljanje jedne greške u programu generiše mnogo novih problema; potrebno je "lokalizovati" realizaciju nekog dela tako da se promene u realizaciji "ne šire" dalje po ostatku sistema. ∗ Tradicionalno programiranje nije moglo da odgovori na ove probleme, pa je nastala kriza proizvodnje softvera. Povećane su režije koje prate proizvodnju programa. Zato je OOP došlo kao odgovor.
Šta daju OOP i C++ kao odgovor? ∗
C++ je trenutno najpopularniji objektno orijentisani jezik. Osnovna rešenja koja pruža OOP, a C++ podržava su: 1. Apstrakcija tipova podataka (Abstract Data Types). Kao što u C-u ili nekom drugom jeziku postoje ugrađeni tipovi podataka (int, float, char, ...), u jeziku C++ korisnik može proizvoljno definisati svoje tipove i potpuno ravnopravno ih koristiti (complex, point, disk, printer, jabuka, bankovni_racun, klijent itd.). Korisnik može deklarisati proizvoljan broj promenljivih svog tipa i vršiti operacije nad njima (multiple instances, višestruke instance, pojave). 2. Enkapsulacija (encapsulation). Realizacija nekog tipa može (i treba) da se sakrije od ostatka sistema (od onih koji ga koriste). Treba korisnicima tipa precizno definisati samo šta se sa tipom može raditi, a način kako se to radi sakriva se od korisnika (definiše se interno). 3. Preklapanje operatora (operator overloading). Da bi korisnički tipovi bili sasvim ravnopravni sa ugrađenim, i za njih se mogu definisati značenja operatora koji postoje u jeziku. Na primer, ako je korisnik definisao tip complex, može pisati c1+c2 ili c1*c2, ako su c1 i c2 promenljive tog tipa; ili, ako je r promenljiva tipa racun, onda r++ može da znači "dodaj (podrazumevanu) kamatu na račun, a vrati njegovo staro stanje". 4. Nasleđivanje (inheritance). Pretpostavimo da je već formiran tip Printer koji ima operacije nalik na print_line, line_feed, form_feed, goto_xy itd. i da je njegovim korišćenjem već realizovana velika količina softvera. Novost je da je firma nabavila i štampače koji imaju bogat skup stilova pisma i želja je da se oni ubuduće iskoriste. Nepotrebno je ispočetka praviti novi tip štampača ili prepravljati stari kôd. Dovoljno je kreirati novi tip PrinterWithFonts koji je "baš kao i običan"
Skripta za Programiranje u Realnom Vremenu
40
Programiranje u Realnom Vremenu štampač, samo"još može da" menja stilove štampe. Novi tip će naslediti sve osobine starog, ali će još ponešto moći da uradi. 5. Polimorfizam (polymorphism). Pošto je PrinterWithFonts već ionako Printer, nema razloga da ostatak programa ne "vidi" njega kao i običan štampač, sve dok mu nisu potrebne nove mogućnosti štampača. Ranije napisani delovi programa koji koriste tip Printer ne moraju se uopšte prepravljati, oni će jednako dobro raditi i sa novim tipom. Pod određenim uslovima, stari delovi ne moraju se čak ni ponovo prevoditi! Karakteristika da se novi tip "odaziva" na pravi način, iako ga je korisnik "pozvao" kao da je stari tip, naziva se polimorfizam. ∗ Sve navedene osobine mogu se pojedinačno na ovaj ili onaj način realizovati i u tradicionalnom jeziku (kakav je i C), ali je realizacija svih koncepata zajedno ili teška, ili sasvim nemoguća. U svakom slučaju, realizacija nekog od ovih principa u tradicionalnom jeziku drastično povećava režije i smanjuje čitljivost programa. ∗ Jezik C++ prirodno podržava sve navedene koncepte, oni su ugrađeni u sâm jezik.
Šta se menja uvođenjem OOP? ∗
Jezik C++ nije "čisti" objektno orijentisani programski jezik (Object-Oriented Programming Language, OOPL) koji bi korisnika "naterao" da ga koristi na objektno orijentisani (OO) način. C++ može da se koristi i kao "malo bolji C", ali se time ništa ne dobija (čak se i gubi). C++ treba koristiti kao sretstvo za OOP i kao smernicu za razmišljanje. C++ ne sprečava da se pišu loši programi, već samo omogućava da se pišu mnogo bolji programi. ∗ OOP uvodi drugačiji način razmišljanja u programiranje! ∗ U OOP, mnogo više vremena troši se na projektovanje, a mnogo manje na samu implementaciju (kodovanje). ∗ U OOP, razmišlja se najpre o problemu, ne direktno o programskom rešenju. ∗ U OOP, razmišlja se o delovima sistema (objektima) koji nešto rade, a ne o tome kako se nešto radi (algoritmima). ∗ U OOP, pažnja se prebacuje sa realizacije na međusobne veze između delova. Težnja je da se te veze što više redukuju i strogo kontrolišu. Cilj OOP je da smanji interakciju između softverskih delova.
Pregled osnovnih koncepata OOP u jeziku C++ ∗
U ovoj glavi biće dât kratak i sasvim površan pregled osnovnih koncepata OOP koje podržava C++. Potpuna i precizna objašnjenja koncepata biće data kasnije, u posebnim glavama. ∗ Primeri koji se koriste u ovoj glavi nisu usmereni da budu upotrebljivi, već samo pokazni. Iz realizacije primera izbačeno je sve što bi smanjivalo preglednost osnovnih ideja. Zato su primeri često i nekompletni. ∗ Čitalac ne treba da se trudi da posle čitanja ove glave strogo zapamti sintaksu rešenja, niti da otkrije sve pojedinosti koje se kriju iza njih. Cilj je da čitalac samo stekne osećaj o osnovnim idejama OOP-a i jezika C++, da vidi šta je to novo i šta se sve može uraditi, kao i da proba da sebe "natera" da razmišlja na novi, objektni način.
Klase
/* Deklaracija klase: Klasa (class) je osnovna organizaciona jedinica programa u OOPL, pa i u jeziku C++. Klasa predstavlja strukturu u koju su grupisani podaci i funkcije: class Osoba { public: ∗ voidKlasom se definiše novi, korisnički tip za koji se mogu kreirati instance (primerci, koSi(); promenljive). /* funkcija: predstavi ∗se! */Instance klase nazivaju se objekti (objects). Svaki objekat ima one svoje sopstvene elemente koji su navedeni u deklaraciji klase. Ovi elementi klase nazivaju se članovi klase (class members). /* ... ise još nešto */operatora "." (tačka): Članovima pristupa pomoću private: char *ime; ∗/* Ako pretpostavimo klase da Osoba: su ranije, na neki način, postavljene vrednosti članova svakog od /* Korišæenje podatak: ime i */ navedenih objekata, ovaj segment programa dâje: prezime */ /*int negdegod; u programu se definišu promenljive tipa /* podatak: koliko ima osoba, */ godina */ 41 Skripta za Programiranje u Realnom Vremenu }; Osoba Pera, mojOtac, direktor;
∗*/
Programiranje u Realnom Vremenu
Ja sam Petar Markovic i imam 25 godina. Ja sam Slobodan Milicev i imam 58 godina. Ja sam Aleksandar Simic i imam 40 godina.
∗
Specifikator public: govori prevodiocu da su samo članovi koji se nalaze iza njega pristupačni spolja. Ovi članovi nazivaju se javnim. Članovi iza specifikatora private: su nedostupni korisnicima klase (ali ne i članovima klase) i nazivaju se privatnim: /* Izvan èlanova klase nije moguæe: */ Pera.ime="Petar Markovic"; nedozvoljeno */ mojOtac.god=55; takoðe nedozvoljeno */
/* /*
/* Šta bi tek bilo da je ovo dozvoljeno: */ direktor.ime="bu...., kr...., ..."; direktor.god=1000; /* a onda ga neko pita (što je dozvoljeno): */ direktor.koSi(); /* ?! */
Konstruktori i destruktori ∗
Da bi se omogućila inicijalizacija objekta, u klasi se definiše posebna funkcija koja se implicitno (automatski) poziva kada se objekat kreira (definiše). Ova funkcija se naziva konstruktor (constructor) i nosi isto ime kao i klasa: class Osoba { public: ∗/*Osoba(char Ovakav deo klase programaOsoba može dati rezultate Korišæenje sada je:koji su ranije navedeni. *ime, int */ ∗godine); Moguće /* je definisati i funkciju koja se poziva uvek kada objekar prestaje da živi. Ova funkcija naziva se destruktor. konstruktor Osoba Pera("Petar Markovic",25), /* */ poziv konstruktora osoba */ Nasleđivanje voidmojOtac("Slobodan koSi(); Milicev",58); ∗/* funkcija: Pretpostavimo da nam je potreban novi tip, Maloletnik. Maloletnik je "jedna vrsta" osobe, predstavi odnosno "poseduje sve što i osoba, samo ima još nešto", ima staratelja. Ovakva relacija između klasa Pera.koSi(); se! */ mojOtac.koSi(); naziva se nasleđivanje. ∗private: Kada nova klasa predstavlja "jednu vrstu" druge klase (a-kind-of), kaže se da je ona izvedena char *ime; iz osnovne klase: /* podatak: ime i prezime */ klasa Maloletnik ∗class Izvedena ima sve članove kao i osnovna klasa Osoba, ali ima još i Maloletnik : public Osoba god; { int staratelj članove i koJeOdgovoran. Konstruktor klase Maloletnik definiše da se objekat /* klase podatak: public: ove kreira zadavanjem imena, staratelja i godina, i to tako da se konstruktor osnovne klase koliko ima Maloletnik (char*,char*,int); Osoba (koji inicijalizuje ime i godine) poziva sa odgovarajućim argumentima. Sâm konstruktor klase godina */ /* konstruktor */ Maloletnik samo inicijalizuje };void koJeOdgovoran();staratelja. ∗private: Sada se mogu koristiti i nasleđene osobine objekata klase Maloletnik, ali su na raspolaganju i njihova posebna svojstva kojih nije bilo u klasi Osoba: char *staratelj; /* }; Svaka funkcija se Osoba mora iotac("Petar Petrovic",40); definisati: void Maloletnik::koJeOdgovoran Maloletnik dete("Milan */ (){ Petrovic","Petar Petrovic",12); cout<<"Za mene odgovara void "<<staratelj<<".\n"; 42 otac.koSi(); Skripta za Programiranje u Realnom Vremenu Osoba::koSi } dete.koSi(); () { dete.koJeOdgovoran(); cout<<"Ja otac.koJeOdgovoran(); /* sam
Programiranje u Realnom Vremenu
/* Izlaz æe biti: Ja sam Petar Petrovic i imam 40 godina. Ja sam Milan Petrovic i imam 12 godina. Za mene odgovara Petar Petrovic. */
Polimorfizam ∗
Pretpostavimo da nam je potrebna nova klasa žena, koja je "jedna vrsta" osobe, samo što još ima i devojačko prezime. Klasa Zena biće izvedena iz klase Osoba. ∗ I objekti klase Zena treba da se "odazivaju" na funkciju koSi, ali je teško pretpostaviti da će jedna dama otvoreno priznati svoje godine. Zato objekat klase Zena treba da ima funkciju koSi, samo što će ona izgledati malo drugačije, svojstveno izvedenoj klasi Zena:
Skripta za Programiranje u Realnom Vremenu
43
class Osoba { public: Osoba(char *,int) /* konstruktor */ virtual void koSi(); /* virtuelna funkcija */ protected: /* dostupno naslednicima */ char *ime; /* podatak: ime i prezime */ int god; /* podatak: koliko ima godina */ };
Programiranje u Realnom Vremenu
void Osoba::koSi () { cout<<"Ja sam "<
Skripta za Programiranje u Realnom Vremenu
44
Programiranje u Realnom Vremenu
∗
Funkcija članica koja će u izvedenim klasama imati nove verzije deklariše se u osnovnoj klasi kao virtuelna funkcija (virtual). Izvedena klasa može da dâ svoju definiciju virtuelne funkcije, ali i ne mora. U izvedenoj klasi ne mora se navoditi reč virtual. ∗ Da bi članovi osnovne klase Osoba bili dostupni izvedenoj klasi Zena, ali ne i korisnicima spolja, oni se deklarišu iza specifikatora protected: i nazivaju zaštićenim članovima. ∗ Drugi delovi programa, korisnici klase Osoba, ako su dobro projektovani, ne moraju da vide ikakvu promenu zbog uvođenja izvedene klase. Oni uopšte ne moraju da se menjaju: /* Funkcija "ispitaj" propituje osobe i ne mora da se menja: */ void ispitaj (Osoba *hejTi) { hejTi->koSi(); } /* U drugom delu programa koristimo novu klasu Zena: */ Osoba otac("Petar Petrovic",40); Zena majka("Milka Petrovic","Mitrovic",35); Maloletnik dete("Milan Petrovic","Petar Petrovic",12); ispitaj(&otac); ispitaj(&majka); ispitaj(&dete); /* Ja Ja Ja */
/* pozvaæe se Osoba::koSi() */ /* pozvaæe se Zena::koSi() */ /* pozvaæe se Osoba::koSi() */
Izlaz æe biti: sam Petar Petrovic i imam 40 godina. sam Milka Petrovic, devojacko prezime Mitrovic. sam Milan Petrovic i imam 12 godina.
∗
Funkcija ispitaj dobija pokazivač na tip Osoba. Kako je i žena osoba, C++ dozvoljava da se pokazivač na tip Zena (&majka) konvertuje (pretvori) u pokazivač na tip Osoba (hejTi). Mehanizam virtuelnih funkcija obezbeđuje da funkcija ispitaj, preko pokazivača hejTi, pozove pravu verziju funkcije koSi. Zato će se za argument &majka pozivati funkcija Zena::koSi, za argument &otac funkcija Osoba::koSi, a za argument &dete takođe funkcija Osoba::koSi, jer klasa Maloletnik nije redefinisala virtuelnu funkciju koSi. ∗ Navedeno svojstvo da se odaziva prava verzija funkcije klase čiji su naslednici dali nove verzije naziva se polimorfizam (polymorphism). Zadaci: 1. Realizovati klasu Counter koja će imati funkciju inc. Svaki objekat ove klase treba da odbrojava pozive svoje funkcije inc. Na početku svog života, vrednost brojača objekta postavlja se na nulu, a pri svakom pozivu funkcije inc povećava se za jedan, i vraća se novodobijena vrednost. 2. Modifikovati klasu iz prethodnog zadatka, tako da funkcija inc ima argument kojim se zadaje vrednost povećanja brojača, i vraća vrednost brojača pre povećanja. Sastaviti glavni program koji kreira objekte ove klase i poziva njihove funkcije inc. Pratiti debagerom stanja svih objekata u step-by-step režimu. 3. Skicirati klasu koja predstavlja člana biblioteke. Svaki član biblioteke ima svoj članski broj, ime i prezime, i trenutno stanje računa za naplatu članarine. Ova klasa treba da ima funkciju za naplatu članarine, koja će sa računa člana skinuti odgovarajuću konstantnu sumu. Biblioteka poseduje i posebnu kategoriju počasnih članova, kojima se ne naplaćuje članarina. Kreirati niz pokazivača na objekte klase članova biblioteke, i definisati funkciju za naplatu članarine svim članovima. Ova funkcija treba da prolazi kroz niz članova i vrši naplatu pozivom funkcije klase za naplatu, bez obzira što se u nizu mogu nalaziti i "obični" i počasni članovi.
Skripta za Programiranje u Realnom Vremenu
45
Programiranje u Realnom Vremenu
Pregled osnovnih koncepata nasleđenih iz jezika C ∗
Ovo poglavlje predstavlja pregled nekih osnovnih koncepata jezika C++ nasleđenih iz jezika C kao tradicionalnog jezika za strukturirano programiranje. ∗ Kao u prethodnom poglavlju, detalji su izostavljeni, a prikazani su samo najvažniji delovi jezika C.
Ugrađeni tipovi i deklaracije ∗
C++ nije čisti OO jezik: ugrađeni tipovi nisu realizovani kao klase, već kao jednostavne strukture podataka. ∗ Deklaracija uvodi neko ime u program. Ime se može koristiti samo ako je prethodno deklarisano. Deklaracija govori prevodiocu kojoj jezičkoj kategoriji neko ime pripada i šta se sa tim imenom može raditi. ∗ Definicija je ona deklaracija koja kreira objekat (alocira memorijski prostor za njega) ili daje telo funkcije. ∗ Neki osnovni ugrađeni tipovi su: ceo broj (int), znak (char) i racionalni broj (float i double). Objekat može biti inicijalizovan u deklaraciji; takva deklaracija je i definicija: int i; int j=0, k=3; float f1=2. 0, f2=0. 0; doubl e PI=3. 14; char a='a' , nul=' 0';
Pokazivači ∗
Pokazivač je objekat koji ukazuje na neki drugi objekat. Pokazivač zapravo sadrži adresu objekta na koji ukazuje. ∗ Ako pokazivač p ukazuje na objekat x, onda izraz *p označava objekat x (operacija dereferenciranja pokazivača). ∗ Rezultat izraza &x je pokazivač koji ukazuje na objekat x (operacija uzimanja adrese). ∗ Tip "pokazivač na tip T" označava se sa T*. Na primer:
Skripta za Programiranje u Realnom Vremenu
46
Programiranje u Realnom Vremenu
int i=0, j=0; // objekti i i j tipa int; int *pi; // objekat pi je tipa "pokazivaè na int" (tip: int*); pi=&i; // vrednost pokazivaèa pi je adresa objekta i, // pa pi ukazuje na i; *pi=2; // *pi oznaèava objekat i; i postaje 2; j=*pi; // j postaje jednak objektu na koji ukazuje pi, // a to je i; pi=&j; // pi sada sadrži adresu j, tj. ukazuje na j;
∗
Mogu se kreirati pokazivači na proizvoljan tip na isti način. Ako je p pokazivač koji ukazuje na objekat klase sa članom m, onda je (*p).m isto što i p->m: Osoba otac("Petar Simiæ",40); Osoba; Osoba *po; Osoba; po=&otac; otac; (*po).koSi(); objekta otac; po->koSi();
∗
// objekat otac klase // po je pokazivaè na tip // po ukazuje na objekat // poziv funkcije koSi // isto što i (*po).koSi();
Tip na koji pokazivač ukazuje može biti proizvoljan, pa i drugi pokazivač:
int i=0, j=0; // i i j tipa int; int *pi=&i; // pi je pokazivaè na int, ukazuje na i; int **ppi; // ppi je tipa "pokazivaè na - pokazivaè na int"; ppi=π // ppi ukazuje na pi; *pi=1; // pi ukazuje na i, pa i postaje 1; **ppi=2; // ppi ukazuje na pi, // pa je rezultat operacije *ppi objekat pi; // rezultat još jedne operacije * je objekat na koji ukazuje // pi, a to je i; i postaje 2; *ppi=&j; // ppi ukazuje na pi, pa pi sada ukazuje na j, // a ppi još uvek na pi; ppi=&i; // greška: ppi je pokazivaè na pokazivaè na int, // a ne pokazivaè na int!
Skripta za Programiranje u Realnom Vremenu
47
Programiranje u Realnom Vremenu
∗
Pokazivač tipa void* može ukazivati na objekat bilo kog tipa. Ne postoje objekti tipa void, ali postoje pokazivači tipa void*. ∗ Pokazivač koji ima posebnu vrednost 0 ne ukazuje ni na jedan objekat. Ovakav pokazivač se može razlikovati od bilo kog drugog pokazivača koji ukazuje na neki objekat.
Nizovi ∗
Niz je objekat koji sadrži nekoliko objekata nekog tipa. Niz je kao i pokazivač izvedeni tip. Tip "niz objekata tipa T" označava se sa T[]. ∗ Niz se deklariše na sledeći način: int a[100]; // a je objekat tipa "niz objekata tipa int" (tip: int[]); // sadrži 100 elemenata tipa int;
∗
Ovaj niz ima 100 elemenata koji se indeksiraju od 0 do 99; i+1-vi element je a[i]:
a[2]=5; // treæi element niza a postaje 5 a[0]=a[0]+a[99];
∗
Elementi mogu biti bilo kog tipa, pa čak i nizovi. Na ovaj način se kreiraju višedimenzionalni
nizovi: int m[5][7];// m je niz od 5 elemenata; // svaki element je niz od 7 elemenata tipa int; m[3][5]=0; // pristupa se èetvrtom elementu niza m; // on je niz elemenata tipa int; // pristupa se zatim njegovom šestom elementu i on postaje 0;
∗
Nizovi i pokazivači su blisko povezani u jezicima C i C++. Sledeća tri pravila povezuju nizove i pokazivače: 1. Svaki put kada se ime niza koristi u nekom izrazu, osim u operaciji uzimanja adrese (operator &), implicitno se konvertuje u pokazivač na svoj prvi element. Na primer, ako je a tipa int[], onda se on konvertuje u tip int*, sa vrednošću adrese prvog elementa niza (to je početak niza). 2. Definisana je operacija sabiranja pokazivača i celog broja, pod uslovom da su zadovoljeni sledeći uslovi: pokazivač ukazuje na element nekog niza i rezultat sabiranja je opet pokazivač koji ukazuje na element istog niza ili za jedno mesto iza poslednjeg elementa niza. Rezultat sabiranja p+i, gde je p pokazivač a i ceo broj, je pokazivač koji ukazuje i elemenata iza elementa na koji ukazuje pokazivač p. Ako navedeni uslovi nisu zadovoljeni, rezultat operacije je nedefinisan. Analogna pravila postoje za operacije oduzimanja celog broja od pokazivača, kao i inkrementiranja i dekrementiranja pokazivača. 3. Operacija a[i] je po definiciji ekvivalentna sa *(a+i). Na primer:
Skripta za Programiranje u Realnom Vremenu
48
Programiranje u Realnom Vremenu
int a[10]; // a je niz objekata tipa int; int *p=&a; // p ukazuje na a[0]; a[2]=1; // a[2] je isto što i *(a+2); a se konvertuje u pokazivaè // koji ukazuje na a[0]; rezultat sabiranja je pokazivaè // koji ukazuje na a[2]; dereferenciranje tog pokazivaèa (*) // predstavlja zapravo a[2]; a[2] postaje 1; p[3]=3; // p[3] je isto što i *(p+3), a to je a[3]; p=p+1; // p sada ukazuje na a[1]; *(p+2)=1; // a[3] postaje sada 1; p[-1]=0; // p[-1] je isto što i *(p1), a to je a[0];
Izrazi ∗
Izraz je iskaz u programu koji sadrži operande (objekte, funkcije ili literale nekog tipa), operacije nad tim operandima i proizvodi rezultat tačno definisanog tipa. Operacije se zadaju pomoću operatora ugrađenih u jezik. ∗ Operator može da prihvata jedan, dva ili tri operanda strogo definisanih tipova, i proizvodi rezultat koji se može koristiti kao operand nekog drugog operatora. Na ovaj način se formiraju složeni izrazi. ∗ Prioritet operatora definiše redosled izračunavanja operacija unutar izraza. Podrazumevani redosled izračunavanja može se promeniti pomoću zagrada (). ∗ C i C++ su prebogati operatorima. Zapravo najveći deo obrade u jednom programu predstavljaju izrazi. ∗ Mnogi ugrađeni operatori imaju sporedni efekat: pored toga što proizvode rezultat, oni menjaju vrednost nekog od svojih operanada. ∗ Postoje operatori za inkrementiranje (++) i dekrementiranje (--), u prefiksnoj i postfiksnoj formi. Ako je i nekog od numeričkih tipova ili pokazivač, i++ znači "inkrementiraj i, a kao rezultat vrati njegovu staru vrednost"; ++i znači "inkrementiraj i a kao rezultat vrati njegovu novu vrednost". Analogno važi za dekrementiranje. ∗ Dodela vrednosti se vrši pomoću operatora dodele =: a=b znači "dodeli vrednost izraza b objektu a, a kao rezultat vrati tu dodeljenu vrednost". Ovaj operator grupiše sdesna ulevo. Tako: a=b=c; // dodeli c objektu b i vrati tu vrednost; zatim dodeli tu vrednost u a; // prema tome, c je dodeljen i objektu b i objektu a;
∗
Postoji i operator složene dodele: a+=b znači isto što i a=a+b, samo što se izraz a samo jednom izračunava:
Skripta za Programiranje u Realnom Vremenu
49
Programiranje u Realnom Vremenu
a+=b; a=a+b; a-=b; b; a*=b; a=a*b; a/=b; a=a/b;
// isto što i // isto što i a=a// isto što i // isto što i
Naredbe ∗
Naredba podrazumeva neku obradu ali ne proizvodi rezultat kao izraz. Postoji samo nekoliko naredbi u jezicima C i C++. ∗ Deklaracija se sintaksno smatra naredbom. Izraz je takođe jedna vrsta naredbe. Složena naredba (ili blok) je sekvenca naredbi uokvirena u velike zagrade {}. Na primer: { (bloka); int a, c=0, d=3; a=(c++)+d; int i=a; i++; }
// poèetak složene naredbe // // // // //
deklaracija kao naredba; izraz kao naredba; deklaracija kao naredba; izraz kao naredba; kraj složene naredbe (bloka);
∗
Uslovna naredba (if naredba): if (izraz) naredba else naredba. Prvo se izračunava izraz; njegov rezultat mora biti numeričkog tipa ili pokazivač; ako je rezultat različit od nule (što se tumači kao "tačno"), izvršava se prva naredba; inače, ako je rezultat jednak nuli (što se tumači kao "netačno"), izvršava se druga naredba (else deo). Deo else je opcioni: if (a++) b=a; 0,
// inkrementiraj a; ako je a bilo razlièito od
if (c) a=c; else a=c+1;
// ako je c razlièito od 0, dodeli ga objektu a, // inaèe dodeli c+1 objektu a;
// dodeli novu vrednost a objektu b;
∗
Petlja (for naredba): for (inicijalna_naredba izraz1; izraz2) naredba. Ovo je petlja sa izlaskom na vrhu (petlja tipa while). Prvo se izvršava inicijalna_naredba samo jednom pre ulaska u petlju. Zatim se izvršava petlja. Pre svake iteracije izračunava se izraz1; ako je njegov rezultat jednak nuli, izlazi se iz petlje; inače, izvršava se iteracija petlje. Iteracija se sastoji od izvršavanja naredbe i zatim izračunavanja izraza2. Oba izraza i inicijalna_naredba su opcioni; ako se izostavi, uzima se da je vrednost izraza1 jednaka 1. Na primer: for (int i=0; i<100; i++) { //... Ova petlja se izvršava taèno 100 puta } for (;;) { //... Beskonaèna petlja }
Funkcije ∗
Funkcije su jedina vrsta potprograma u jezicima C i C++. Funkcije mogu biti članice klase ili globalne funkcije (nisu članice nijedne klase).
Skripta za Programiranje u Realnom Vremenu
50
Programiranje u Realnom Vremenu
∗
Ne postoji statičko (sintaktičko) ugnežđivanje tela funkcija. Dinamičko ugnežđivanje poziva funkcija je dozvoljeno, pa i rekurzija. ∗ Funkcija može, ali ne mora da ima argumente. Funkcija bez argumenata se deklariše sa praznim zagradama. Argumenti se prenose samo po vrednostima u jeziku C, a mogu se prenositi i po referenci u jeziku C++. ∗ Funkcija može, ali ne mora da vraća rezultat. Funkcija koja nema povratnu vrednost deklariše se sa tipom void kao tipom rezultata. ∗ Deklaracija funkcije koja nije i definicija uključuje samo zaglavlje sa tipom argumenata i rezultata; imena argumenata su opciona i nemaju značaja za program: int stringCompare (char*,char*); funkcije; char*,
// koja nema povratnu vrednost;
Definicija funkcije daje i telo funkcije. Telo funkcije je složena naredba (blok):
int Counter::inc () { int; return count++; }
∗ ∗
// prima dva argumenta tipa // a vraæa tip int; // globalna funkcija bez
void f(); argumenata
∗
// deklaracija globalne
// definicija funkcije èlanice; vraæa // vraæa se rezultat izraza;
Funkcija može vratiti vrednost koja je rezultat izraza u naredbi return. Mogu se definisati lokalna imena unutar tela funkcije (tačnije unutar svakog ugnežđenog
bloka): int Counter::inc () { int temp; // temp je lokalni objekat temp=count+1; // count je èlan klase Counter count=temp; return temp; }
∗
Funkcija članica neke klase može pristupati članovima sopstvenog objekta bez posebne specifikacije. Globalna funkcija mora specifikovati objekat čijem članu pristupa. ∗ Poziv funkcije obavlja se pomoću operatora (). Rezultat ove operacije je rezultat poziva funkcije: int f(int); funkcije Counter c; int a=0, b=1; a=b+c.inc(); vraæa int a=f(b);
∗
// deklaracija globalne // objekat c klase Counter // poziv funkcije c.inc koji // poziv globalne funkcije f
Može se deklarisati i pokazivač na funkciju:
Skripta za Programiranje u Realnom Vremenu
51
Programiranje u Realnom Vremenu
int f(int); tipa int int (*p)(int);
p=&f; int a; a=(*p)(1); funkcija f;
// f je tipa "funkcija koja prima jedan argument // // // // // //
i vraæa int"; p je tipa "pokazivaè na funkciju koja prima jedan argument tipa int i vraæa int"; p ukazuje na f;
// poziva se funkcija na koju ukazuje p, a to je
Struktura programa ∗
Program se sastoji samo od deklaracija (klasa, objekata, ostalih tipova i funkcija). Sva obrada koncentrisana je unutar tela funkcija. ∗ Program se fizički deli na odvojene jedinice prevođenja - datoteke. Datoteke se prevode odvojeno i nezavisno, a zatim se povezuju u izvršni program. U svakoj datoteci se moraju deklarisati sva imena pre nego što se koriste. ∗ Zavisnosti između modula - datoteka definišu se pomoću datoteka-zaglavlja. Zaglavlja sadrže deklaracije svih entiteta koji se koriste u datom modulu, a definisani su u nekom drugom modulu. Zaglavlja (.h) se uključuju u tekst datoteke koja se prevodi (.cpp) pomoću direktive #include. ∗ Glavni program (izvor toka kontrole) definiše se kao obavezna funkcija main. Primer jednog jednostavnog, ali kompletnog programa:
Skripta za Programiranje u Realnom Vremenu
52
Programiranje u Realnom Vremenu
class Counter { public: Counter(); int inc(int by); private: int count; }; Counter::Count er () : count(0) {} int Counter::inc (int by) { return count+=by; } void main () { Counter a,b; int i=0, j=3; i=a.inc(2)+b .inc(++j); }
Elementi jezika C++ koji nisu objektno orijentisani Oblast važenja imena ∗ ∗
Oblast važenja imena je onaj deo teksta programa u kome se deklarisano ime može koristiti. Globalna imena su imena koja se deklarišu van svih funkcija i klasa. Njihova oblast važenja je deo teksta od mesta deklaracije do kraja datoteke. ∗ Lokalna imena su imena deklarisana unutar bloka, uključujući i blok tela funkcije. Njihova oblast važenja je od mesta deklarisanja, do završetka bloka u kome su deklarisane.
Skripta za Programiranje u Realnom Vremenu
53
Programiranje u Realnom Vremenu
int x; x
// globalni
void f () { int x; // lokalni x, sakriva globalni x; x=1; // pristup lokalnom x { int x; // drugi lokalni x, sakriva prethodnog x=2; // pristup drugom lokalnom x } x=3; // pristup prvom lokalnom x } int *p=&x; // uzimanje adrese globalnog x
∗
Globalnom imenu se može pristupiti, iako je sakriveno, navođenjem operatora "::" ispred
imena: int x; x void f () { int x=0; ::x=1; globalnom x; }
// globalni
// lokalni x // pristup
∗
Za formalne argumente funkcije smatra se da su lokalni, deklarisani u krajnje spoljašnjem bloku tela funkcije: void f (int x) { int x; // pogrešno }
∗
Prvi izraz u naredbi for može da bude definicija promenljive. Tako se dobija lokalna promenljiva za blok u kome se nalazi for:
Skripta za Programiranje u Realnom Vremenu
54
{ Programiranje u Realnom Vremenu f o r ( i n t i = 0 ; i < 1 0 ; i + + ) { / / . . . i f ( a [ i ] = = x ) b r e a k ; / / . . . } i f ( i = = 1
Skripta za Programiranje u Realnom Vremenu
55
Programiranje u Realnom Vremenu
∗
Oblast važenja klase imaju svi članovi klase. To su imena deklarisana unutar deklaracije klase. Imenu koje ima oblast važenja klase, van te oblasti, može se pristupiti preko operatora " ." i "->", gde je levi operand objekat, odnosno pokazivač na objekat date klase ili klase izvedene iz date klase, ili preko operatora "::", gde je levi operand ime klase: class X { public: int x; void f(); }; void X::f () {/*...*/ } X xx; xx.x=0; xx.X::f( ); // može i ovako
∗
Oblast važenja funkcije imaju samo labele (za goto naredbe). One se mogu navesti bilo gde (i samo) unutar tela funkcije, a vide se u celoj funkciji.
Objekti i lvrednosti ∗
Objekat je neko područje u memoriji podataka, u toku izvršavanja programa. To može biti promenljiva (globalna ili lokalna), privremeni objekat koji se kreira pri izračunavanja izraza, ili jednostavno memorijska lokacija na koju pokazuje neki pokazivač. Uopšte, objekat je primerak nekog tipa (ugrađenog ili klase), ali ne i funkcija. ∗ Samo nekonstantni objekat se u jeziku C++ naziva promenljivom. ∗ lvrednost (lvalue) je izraz koji upućuje na objekat. lvalue je kovanica od "nešto što može da stoji sa leve strane znaka dodele vrednosti", iako ne mogu sve lvrednosti da stoje sa leve strane znaka =, npr. konstanta. ∗ Za svaki operator se definiše da li zahteva kao operand lvrednost, i da li vraća lvrednost kao rezultat. "Početna" lvrednost je ime objekta ili funkcije. Na taj način se rekurzivno definišu lvrednosti. ∗ Promenljiva lvrednost (modifiable lvalue) je ona lvrednost, koja nije ime funkcije, ime niza, ili konstantni objekat. Samo ovakva lvrednost može biti levi operand operatora dodele. ∗ Primeri lvrednosti:
Skripta za Programiranje u Realnom Vremenu
56
Programiranje u Realnom Vremenu
int i=0; upuæuje
// i je lvrednost, jer je ime koje // na objekat - celobrojnu promenljivu u
memoriji int *p=&i;
// i p je ime, odnosno lvrednost
*p=7; // *p je lvrednost, jer upuæuje na objekat koga // predstavlja ime i; rezultat operacije * je // lvrednost int *q[100]; *q[a+13]=7; // *q[a+13] je lvrednost
Životni vek objekata ∗
Životni vek objekta je vreme u toku izvršavanja programa za koje taj objekat postoji (u memoriji), i za koje mu se može pristupati. ∗ Na početku životnog veka, objekat se kreira (poziva se njegov konstruktor ako ga ima), a na kraju se objekat ukida (poziva se njegov destruktor ako ga ima). Sinonim za kreiranje objekta je inicijalizacija objekta. int glob=1; mu void f () { int lok=2; je do
// globalni objekat; životni vek // je do kraja programa; // lokalni objekat; životni vek mu
// izlaska iz spoljnjeg bloka funkcije; static int sl=3;// lokalni statièki objekat; oblast // važenja je funkcija, a životni vek je ceo // program; inicijalizuje se samo jednom; for (int i=0; i<sl; i++) { int j=i; // j je lokalni za for blok //... } }
∗ ∗
U odnosu na životni vek, postoje automatski, statički, dinamički i privremeni objekti. Životni vek automatskog objekta (lokalni objekat koji nije deklarisan kao static) traje od nailaska na njegovu definiciju, do napuštanja oblasti važenja tog objekta. Automatski objekat se kreira iznova pri svakom pozivu bloka u kome je deklarisan. Definicija objekta je izvršna naredba. ∗ Životni vek statičkih objekata (globalni i lokalni static objekti) traje od izvršavanja njihove definicije do kraja izvršavanja programa. Globalni statički objekti se kreiraju samo jednom, na početku izvršavanja programa, pre korišćenja bilo koje funkcije ili objekta iz istog fajla, ne obavezno pre poziva funkcije main, a prestaju da žive po završetku funkcije main. Lokalni statički objekti počinju da žive pri prvom nailasku toka programa na njihovu definiciju. ∗ Životni vek dinamičkih objekata neposredno kontroliše programer. Oni se kreiraju operatorom new, a ukidaju operatorom delete. ∗ Životni vek privremenih objekata je kratak i nedefinisan. Ovi objekti se kreiraju pri izračunavanju izraza, za odlaganje međurezultata ili privremeno smeštanje vraćene vrednosti funkcije. Najčešće se uništavaju čim više nisu potrebni.
Skripta za Programiranje u Realnom Vremenu
57
Programiranje u Realnom Vremenu
∗ ∗
Životni vek članova klase je isti kao i životni vek objekta kome pripadaju. Formalni argumenti funkcije se, pri pozivu funkcije, kreiraju kao automatski lokalni objekti i inicijalizuju se stvanim argumentima. Semantika inicijalizacije formalnog argumenta je ista kao i inicijalizacija objekta u definiciji. ∗ Primer:
Skripta za Programiranje u Realnom Vremenu
58
Programiranje u Realnom Vremenu
int a=1; void f () { int b=1; // inicija lizuje se pri svakom pozivu stati c int c=1; / / inicija lizuje se samo jednom print f(" a = %d ",a+ +); print f(" b = %d ",b+ +); print f(" c = %d\n",c ++); } void main () { while (a<4) f(); } // izlaz æe biti: // a = 1 b = 1 c = 1 // a = 2 b = 1 c = 2 // a = 3 b = 1 c = 3
O konverziji tipova ∗ ∗
C++ je strogo tipizirani jezik, što je u duhu njegove objektne orjentacije. Tipizacija znači da svaki objekat ima svoj tačno određeni tip. Svaki put kada se na nekom mestu očekuje objekat jednog tipa, a koristi se objekat drugog tipa, potrebno je izvršiti konverziju tipova.
Skripta za Programiranje u Realnom Vremenu
59
Programiranje u Realnom Vremenu
∗ ∗
Konverzija tipa znači pretvaranje objekta datog tipa u objekat potrebnog tipa. Slučajevi kada se može desiti da se očekuje jedan tip, a dostavlja se drugi, odnosno kada je potrebno vršiti konverziju su: 1. operatori za ugrađene tipove zahtevaju operande odgovarajućeg tipa; 2. neke naredbe (if, for, do, while, switch) zahtevaju izraze odgovarajućeg tipa; 3. pri pozivu funkcije, kada su stvarni argumenti drugačijeg tipa od deklarisanih formalnih argumenata; i operatori za korisničke tipove (klase) su specijalne vrste funkcija; 4. pri povratku iz funkcije, ako se u izrazu iza return koristi izraz drugačijeg tipa od deklarisanog tipa povratne vrednosti funkcije; 5. pri inicijalizaciji objekta jednog tipa pomoću objekta drugog tipa; slučaj pod 3 se može svesti u ovu grupu, jer se formalni argumenti inicijalizuju stvarnim argumentima pri pozivu funkcije; takođe, slučaj pod 4 se može svesti u ovu grupu, jer se privremeni objekat, koji prihvata vraćenu vrednost funkcije na mestu poziva, inicijalizuje izrazom iza naredbe return. ∗ Konverzija tipa može biti ugrađena u jezik (standardna konverzija) ili je definiše korisnik (programer) za svoje tipove (korisnička konverzija). ∗ Standardne konverzije su, na primer, konverzije iz tipa int u tip float, ili iz tipa char u tip int itd. ∗ Prevodilac može sam izvršiti konverziju koja mu je dozvoljena, na mestu gde je to potrebno; ovakva konverzija naziva se implicitnom. Programer može eksplicitno navesti koja konverzija treba da se izvrši; ova konverzija naziva se eksplicitnom. ∗ Jedan način zahtevanja eksplicitne konverzije je pomoću operatora cast: (tip)izraz. ∗ Primer: char f(float i, float j) { //... } int k=f(5.5,5); // najpre se vrši konverzija float(5), // a posle i konverzija vraæene vrednosti // iz char u int
Konstante ∗
Konstantni tip je izvedeni tip koji se iz nekog osnovnog tipa dobija stavljanjem specifikatora const u deklaraciju: const float pi=3.14; const char plus='+';
∗
Konstantni tip ima sve osobine osnovnog tipa, samo se objekti konstantnog tipa ne mogu menjati. Pristup konstantama kontroliše se u fazi prevođenja, a ne izvršavanja. ∗ Konstanta mora da se inicijalizuje pri definisanju. ∗ Prevodilac često ne odvaja memorijski prostor za konstantu, već njeno korišćenje razrešava u doba prevođenja. ∗ Konstante mogu da se koriste u konstantnim izrazima koje prevodilac treba da izračuna u toku prevođenja, na primer kao dimenzije nizova. ∗ Pokazivač na konstantu definiše se stavljanjem reči const ispred cele definicije. Konstantni pokazivač definiše se stavljanjem reči const ispred samog imena:
Skripta za Programiranje u Realnom Vremenu
60
Programiranje u Realnom Vremenu
const char *pk="asdfgh"; konstantu pk[3]='a'; pk="qwerty";
// pokazivaè na
char *const kp="asdfgh"; kp[3]='a'; kp="qwerty";
// konstantni pokazivaè // ispravno // pogrešno
const char *const kpk="asdfgh"; konst. kpk[3]='a'; kpk="qwerty";
// konst. pokazivaè na
// pogrešno // ispravno
// pogrešno // pogrešno
∗
Navođenjem reči const ispred deklaracije formalnog argumenta funkcije koji je pokazivač, obezbeđuje se da funkcija ne može menjati objekat na koji taj argument ukazuje: char *strcpy(char *p, const char *q); // ne može da promeni *q
∗
Navodjenjem reči const ispred tipa koji vraća funkcija, definiše se da će privremeni objekat koji se kreira od vraćene vrednosti funkcije biti konstantan, i njegovu upotrebu kontroliše prevodilac. Za vraćenu vrednost koja je pokazivač na konstantu, ne može se preko vraćenog pokazivača menjati objekat: const char* f(); *f()='a'; // greška!
∗
Preporuka je da se umesto tekstualnih konstanti koje se ostvaruju pretprocesorom (kao u jeziku C) koriste konstante na opisani način. ∗ Dosledno korišćenje konstanti u programu obezbeđuje podršku prevodioca u sprečavanju grešaka - korektnost konstantnosti.
Dinamički objekti ∗
Operator new kreira jedan dinamički objekat, a operator delete ukida dinamički objekat nekog tipa T. ∗ Operator new za svoj argument ima identifikator tipa i eventualne argumente konstruktora. Operator new alocira potreban prostor u slobodnoj memoriji za objekat datog tipa, a zatim poziva konstruktor tipa sa zadatim vrednostima. Operator new vraća pokazivač na dati tip: complex *pc1 = new complex(1.3,5.6), *pc2 = new complex(-1.0,0); *pc1=*pc1+*pc2;
∗
Objekat kreiran pomoću operatora new naziva se dinamički objekat, jer mu je životni vek poznat tek u vreme izvršavanja. Ovakav objekat nastaje kada se izvrši operator new, a traje sve dok se ne oslobodi operatorom delete (može da traje i po završetku bloka u kome je kreiran):
Skripta za Programiranje u Realnom Vremenu
61
Programiranje u Realnom Vremenu
complex *pc; void f() { pc=new complex(0.1 ,0.2); } void main () { f(); delete pc; // ukidanje objekta *pc }
∗
Operator delete ima jedan argument koji je pokazivač na neki tip. Ovaj pokazivač mora da ukazuje na objekat kreiran pomoću operatora new. Operator delete poziva destruktor za objekat na koji ukazuje pokazivač, a zatim oslobađa zauzeti prostor. Ovaj operator vraća void. ∗ Operatorom new može se kreirati i niz objekata nekog tipa. Ovakav niz ukida se operatorom delete sa parom uglastih zagrada: comlex *pc = new complex[10]; //... delete [] pc;
∗
Kada se alocira niz, nije moguće zadati inicijalizatore. Ako klasa nema definisan konstruktor, prevodilac obezbeđuje podrazumevanu inicijalizaciju. Ako klasa ima konstruktore, da bi se alocirao niz potrebno je da postoji konstruktor koji se može pozvati bez argumenata. ∗ Kada se alocira niz, operator new vraća pokazivač na prvi element alociranog niza. Sve dimenzije niza osim prve treba da budu konstantni izrazi, a prva dimenzija može da bude i promenljivi izraz, ali takav da može da se izračuna u trenutku izvršavanja naredbe sa operatorom new.
Reference ∗
U jeziku C prenos argumenata u funkciju bio je isključivo po vrednosti (call by value). Da bi neka funkcija mogla da promeni vrednost neke spoljne promenljive, trebalo je preneti pokazivač na tu promenljivu. ∗ U jeziku C++ moguć je i prenos po referenci (call by reference):
Skripta za Programiranje u Realnom Vremenu
62
Programiranje u Realnom Vremenu
void f(int i, int &j) { // i se prenosi po vrednosti, j po referenci i++; // stvarni argument se neæe promeniti j++; // stvarni argument æe se promeniti } void main () { int si=0,sj=0; f(si,sj); cout<<"si="<<si<<", sj="<<sj<<"\n"; } // Izlaz æe biti: // si=0, sj=1
∗
C++ ide još dalje, postoji izvedeni tip reference na objekat (reference type). Reference se deklarišu upotrebom znaka & ispred imena. ∗ Referenca je alternativno ime za neki objekat. Kada se definiše, referenca mora da se inicijalizuje nekim objektom na koga će upućivati. Od tada referenca postaje sinonim za objekat na koga upućuje i svaka operacija nad referencom (uključujući i operaciju dodele) je ustvari operacija nad referenciranim objektom: int i=1; i int &j=i; i=3; j=5; int *p=&j; j+=1; int k=j; i preko reference int m=*p; i preko pokazivaèa
// celobrojni objekat // // // // // //
j upuæuje na i menja se i opet se menja i isto što i &i isto što i i+=1 posredan pristup do
// posredan pristup do
∗
Referenca se realizuje kao (konstantni) pokazivač na objekat. Ovaj pokazivač pri inicijalizaciji dobija vrednost adrese objekta kojim se inicijalizuje. Svako dalje obraćanje referenci podrazumeva posredni pristup objektu preko ovog pokazivača. Nema načina da se, posle inicijalizacije, vrednost ovog pokazivača promeni. ∗ Referenca liči na pokazivač, ali se posredan pristup preko pokazivača na objekat vrši operatorom *, a preko reference bez oznaka. Uzimanje adrese (operator &) reference znači uzimanje adrese objekta na koji ona upućuje. ∗ Primeri:
Skripta za Programiranje u Realnom Vremenu
63
Programiranje u Realnom Vremenu
int &j = *new int(2); 2 int *p=&j; (*p)++; j++; delete &j;
// j upuæuje na dinamièki objekat // // // //
p je pokazivaè na isti objekat objekat postaje 3 objekat postaje 4 isto kao i delete p
∗
Ako je referenca tipa reference na konstantu, onda to znači da se referencirani objekat ne sme promeniti posredstvom te reference. ∗ Referenca može i da se vrati kao rezultat funkcije. U tom slučaju funkcija treba da vrati referencu na objekat koji traje (živi) i posle izlaska iz funkcije, da bi se mogla koristiti ta referenca: // Može ovako: int& f(int &i) { int &r=*new int(1); //... return r; // pod uslovom da nije bilo delete &r } // ili ovako: int& f(int &i) { //... return i; } // ali ne može ovako: int& f(int &i) { int r=1; //... return r; } // niti ovako: int& f(int i) { //... return i; } // niti ovako: int& f(int &i) { int r=*new int(1); //... return r; }
Skripta za Programiranje u Realnom Vremenu
64
Programiranje u Realnom Vremenu
∗
Prilikom poziva funkcije, kreiraju se objekti koji predstavljaju formalne argumente i inicijalizuju se stvarnim argumentima (semantika je ista kao i pri definisanju objekta sa inicijalizacijom). Prilikom povratka iz funkcije, kreira se privremeni objekat koji se inicijalizuje objektom koji se vraća, a zatim se koristi u izrazu iz koga je funkcija pozvana. ∗ Rezultat poziva funkcije je lvrednost samo ako funkcija vraća referencu. ∗ Ne postoje nizovi referenci, pokazivači na reference, ni reference na reference.
Funkcije Deklaracije funkcija i prenos argumenata ∗
Funkcije se deklarišu i definišu kao i u jeziku C, samo što je moguće kao tipove argumenata i rezultata navesti korisničke tipove (klase). ∗ U deklaraciji funkcije ne moraju da se navode imena formalnih argumenata. ∗ Pri pozivu funkcije, upoređuju se tipovi stvarnih argumenata sa tipovima formalnih argumenata navedenim u deklaraciji, i po potrebi vrši konverzija. Semantika prenosa argumenata jednaka je semantici inicijalizacije. ∗ Pri pozivu funkcije, inicijalizuju se formalni argumenti, kao automatski lokalni objekti pozvane funkcije. Ovi objekti se konstruišu pozivom odgovarajućih konstruktora, ako ih ima. Pri vraćanju vrednosti iz funkcije, semantika je ista: konstruiše se privremeni objekat koji prihvata vraćenu vrednost na mestu poziva: class Tip { //... public: Tip(int i); // konstrukto r }; Tip f (Tip k) { //... return 2; // poziva se konstrukto r Tip(2) } void main () { Tip k(0); k=f(1); // poziva se konstrukto r Tip(1) //... }
Neposredno ugrađivanje u kôd ∗
Često se definišu vrlo jednostavne, kratke funkcije (na primer samo presleđuju argumente drugim funkcijama). Tada je vreme koje se troši na prenos argumenata i poziv veće nego vreme izvršavanja tela same funkcije.
Skripta za Programiranje u Realnom Vremenu
65
Programiranje u Realnom Vremenu
∗
Ovakve funkcije se mogu deklarisati tako da se neposredno ugrađuju u kôd (inline funkcije). Tada se telo funkcije direktno ugrađuje u pozivajući kôd. Semantika poziva ostaje potpuno ista kao i za običnu funkciju. ∗ Ovakva funkcija deklariše se kao inline: inline int inc(int i) {return i+1;}
∗
Funkcija članica klase može biti inline ako se definiše unutar deklaracije klase, ili izvan deklaracije klase, kada se ispred njene deklaracije nalazi reč inline: class C { int i; public: int val () {return i;} // ovo je inline funkcija }; // ili: class D { int i; public: int val (); }; inline int D::val() {return i;}
∗
Prevodilac ne mora da ispoštuje zahtev za neposredno ugrađivanje u kôd. Za korisnika ovo ne treba da predstavlja nikakvu prepreku, jer je semantika ista. Inline funkcije samo mogu da ubrzaju program, a nikako da izmene njegovo izvršavanje. ∗ Ako se inline funkcija koristi u više datoteka, u svakoj datoteci mora da se nađe njena potpuna definicija (najbolje pomoću datoteke-zaglavlja).
Podrazumevane vrednosti argumenata ∗
C++ obezbeđuje i mogućnost postavljanja podrazumevanih vrednosti za argumente. Ako se pri pozivu funkcije ne navede argument za koji je definisana podrazumevana vrednost (u deklaraciji funkcije), kao vrednost stvarnog argumenta uzima se ta podrazumevana vrednost:
Skripta za Programiranje u Realnom Vremenu
66
Programiranje u Realnom Vremenu
complex::complex (float r=0, float i=0) // podrazumevana {real=r; imag=i;} // vrednost za r i i je 0 void main () { complex c; // kao da je napisano "complex c(0,0);" //... }
∗
Podrazumevani argumenti mogu da budu samo nekoliko poslednjih iz liste:
complex::complex(float r=0, float i) greška { real=r; imag=i; }
//
Preklapanje imena funkcija ∗
Često se javlja potreba da se u programu naprave funkcije koje realizuju logički istu operaciju, samo sa različitim tipovima argumenata. Za svaki od tih tipova mora, naravno, da se realizuje posebna funkcija. U jeziku C to bi moralo da se realizuje tako da te funkcije imaju različita imena. To, međutim, smanjuje čitljivost programa. ∗ U jeziku C++ moguće je definisati više različitih funkcija sa istim identifikatorom. Ovakav koncept naziva se preklapanje imena funkcija (engl. function overloading). Uslov je da im se razlikuje broj i/ili tipovi argumenata. Tipovi rezultata ne moraju da se razlikuju: char* max (const char *p, const char *q) { return (strcmp(p,q)>=0)?p:q; } double max (double i, double j) { return (i>j) ? i : j; } double r=max(1.5,2.5); // poziva se max(double,double) char *q=max("Pera","Mika"); // poziva se max(const char*,const char*)
∗
Koja će se funkcija stvarno pozvati, određuje se u fazi prevođenja prema slaganju tipova stvarnih i formalnih argumenata. Zato je potrebno da prevodilac može jednoznačno da odredi koja funkcija se poziva. ∗ Pravila za razrešavanje poziva su veoma složena [ARM, Milićev95], pa se u praksi svode samo na dovoljno razlikovanje tipova formalnih argumenata preklopljenih funkcija. Kada razrešava poziv, prevodilac otprilike ovako prioritira slaganje tipova stvarnih i formalnih argumenata: 1. najbolje odgovara potpuno slaganje tipova; tipovi T* (pokazivač na T) i T[] (niz elemenata tipa T) se ne razlikuju; 2. sledeće po odgovaranju je slaganje tipova korišćenjem standardnih konverzija; 3. sledeće po odgovaranju je slaganje tipova korišćenjem korisničkih konverzija; 4. najlošije odgovara slaganje sa tri tačke (...).
Operatori i izrazi ∗
Pregled operatora dat je u sledećoj tabeli. Operatori su grupisani po prioritetima, tako da su operatori u istoj grupi istog prioriteta, višeg od operatora koji su u narednoj grupi. U tablici su prikazane i ostale važne osobine: način grupisanja (asocijativnost, L - sleva udesno, D - sdesna ulevo), da li je rezultat lvrednost (D - da, N - nije, D/N - zavisi od nekog operanda, pogledati specifikaciju operatora u [ARM, Milićev95]), kao i način upotrebe. Prazna polja ukazuju da svojstvo grupisanja nije primereno datom operatoru.
Skripta za Programiranje u Realnom Vremenu
67
Programiranje u Realnom Vremenu
Operator :: :: [] () () . -> ++ -++ -sizeof sizeof new delete ~ ! + & * () .* ->* * / % + << >> < <= > >= == != & ^ | && || ? : = *= /= %= += -= >>= <<= &= |=
Značenje razrešavanje oblasti važenja pristup globalnom imenu indeksiranje poziv funkcije konstrukcija vrednosti pristup članu posredni pristup članu postfiksni inkrement postfiksni dekrement prefiksni inkrement prefiksni dekrement veličina objekta veličina tipa kreiranje dinamičkog objekta ukidanje dinamičkog objekta komplement po bitima logička negacija unarni minus unarni plus adresa dereferenciranje pokazivača konverzija tipa (cast) posredni pristup članu posredni pristup članu množenje deljenje ostatak sabiranje oduzimanje pomeranje ulevo pomeranje udesno manje od manje ili jednako od veće od veće ili jednako od jednako nije jednako I po bitima isključivo ILI po bitima ILI po bitovima logičko I logičko ILI uslovni operator prosto dodeljivanje množenje i dodela deljenje i dodela ostatak i dodela sabiranje i dodela oduzimanje i dodela pomeranje udesno i dodela pomeranje ulevo i dodela I i dodela ILI i dodela
Grup. L L L L L L L D D D D
D D D D D D D L L L L L L L L L L L L L L L L L L L L L D D D D D D D D D D
lvred. D/N D/N D D/N N D/N D/N N N D D N N N N N N N N N D D/N D/N D/N N N N N N N N N N N N N N N N N N N D/N D D D D D D D D D D
Skripta za Programiranje u Realnom Vremenu
Upotreba ime_klase :: član :: ime izraz[izraz] izraz(lista_izraza) ime_tipa(lista_izraza) izraz . ime izraz -> ime lvrednost++ lvrednost-++lvrednost --lvrednost sizeof izraz sizeof(tip) new tip delete izraz ~izraz !izraz -izraz +izraz &lvrednost *izraz (tip)izraz izraz .* izraz izraz ->* izraz izraz * izraz izraz / izraz izraz % izraz izraz + izraz izraz - izraz izraz << izraz izraz >> izraz izraz < izraz izraz <= izraz izraz > izraz izraz >= izraz izraz == izraz izraz != izraz izraz & izraz izraz ^ izraz izraz | izraz izraz && izraz izraz || izraz izraz ? izraz : izraz lvrednost = izraz lvrednost *= izraz lvrednost /= izraz lvrednost %= izraz lvrednost += izraz lvrednost -= izraz lvrednost >>= izraz lvrednost <<= izraz lvrednost &= izraz lvrednost |= izraz
68
Programiranje u Realnom Vremenu ^= ,
isključivo ILI i dodela sekvenca
D L
D D/N
lvrednost ^= izraz izraz , izraz
Zadaci: 4. Realizovati funkciju strclone koja prihvata pokazivač na znakove kao argument, i vrši kopiranje niza znakova na koji ukazuje taj argument u dinamički niz znakova, kreiran u dinamičkoj memoriji, na koga će ukazivati pokazivač vraćen kao rezultat funkcije. 5. Modifikovati funkciju iz prethodnog zadatka, tako da funkcija vraća pokazivač na konstantni (novoformirani) niz znakova. Analizirati mogućnosti upotrebe ove modifikovane, kao i polazne funkcije u glavnom programu, u pogledu izmene kreiranog niza znakova. Izmenu niza znakova pokušati i posredstvom vraćene vrednosti funkcije, i preko nekog drugog pokazivača, u koji se prebacuje vraćena vrednost funkcije. 6. Realizovati klasu čiji će objekti služiti za izdvajanje reči u tekstu koji je dat u nizu znakova. Jednom rečju se smatra niz znakova bez blanko znaka. Klasa treba da sadrži člana koji je pokazivač na niz znakova koji predstavlja ulazni tekst, i koji će biti inicijalizovan u konstruktoru. Klasa treba da sadrži i funkciju koja, pri svakom pozivu, vraća pokazivač na dinamički niz znakova u koji je izdvojena naredna reč teksta. Kada naiđe na kraj teksta, ova funkcija treba da vrati nula-pokazivač. U glavnom programu isprobati upotrebu ove klase, na nekoliko objekata koji deluju nad istim globalnim nizom znakova.
Klase Klase, objekti i članovi klase Pojam i deklaracija klase ∗
Klasa je je realizacija apstrakcije koja ima svoju internu predstavu (svoje atribute) i operacije koje se mogu vršiti nad njom (javne funkcije članice). Klasa definiše tip. Jedan primerak takvog tipa (instanca klase) naziva se objektom te klase (engl. class object). ∗ Podaci koji su deo klase nazivaju se podaci članovi klase (engl. data members). Funkcije koje su deo klase nazivaju se funkcije članice klase (engl. member functions). ∗ Članovi (podaci ili funkcije) klase iza ključne reči private: zaštićeni su od pristupa spolja (enkapsulirani su). Ovim članovima mogu pristupati samo funkcije članice klase. Ovi članovi nazivaju se privatnim članovima klase (engl. private class members). ∗ Članovi iza ključne reči public: dostupni su spolja i nazivaju se javnim članovima klase (engl. public class members). ∗ Članovi iza ključne reči protected: dostupni su funkcijama članicama date klase, kao i klasa izvedenih iz te klase, ali ne i korisnicima spolja, i nazivaju se zaštićenim članovima klase (engl. protected class members). ∗ Redosled sekcija public, protected i private je proizvoljan, ali se preporučuje baš navedeni redosled. Podrazumevano (ako se ne navede specifikator ispred) su članovi privatni. ∗ Kaže se još da klasa ima svoje unutrašnje stanje, predstavljeno atributima, koje menja pomoću operacija. Javne funkcije članice nazivaju se još i metodima klase, a poziv ovih funkcija - upućivanje poruke objektu klase. Objekat klase menja svoje stanje kada se pozove njegov metod, odnosno kada mu se uputi poruka. ∗ Objekat unutar svoje funkcije članice može pozivati funkciju članicu neke druge ili iste klase, odnosno uputiti poruku drugom objektu. Objekat koji šalje poruku (poziva funkciju) naziva se objekatklijent, a onaj koji je prima (čija je funkcija članica pozvana) je objekat-server. ∗ Preporuka je da se klase projektuju tako da nemaju javne podatke članove. ∗ Unutar funkcije članice klase, članovima objekta čija je funkcija pozvana pristupa se direktno, samo navođenjem njihovog imena. ∗ Kontrola pristupa članovima nije stvar objekta, nego klase: jedan objekat neke klase iz svoje funkcije članice može da pristupi privatnim članovima drugog objekta iste klase. Takođe, kontrola
Skripta za Programiranje u Realnom Vremenu
69
Programiranje u Realnom Vremenu pristupa članovima je potpuno odvojena od koncepta oblasti važenja: najpre se, na osnovu oblasti važenja, određuje entitet na koga se odnosi dato ime na mestu obraćanja u programu, a zatim se određuje da li se tom entitetu može pristupiti. ∗ Moguće je preklopiti (engl. overload) funkcije članice, uključujući i konstruktore. ∗ Deklaracijom klase smatra se deo kojim se specifikuje ono što korisnici klase treba da vide. To su uvek javni članovi. Međutim, da bi prevodilac korektno zauzimao prostor za objekte klase, mora da zna njegovu veličinu, pa u deklaraciju klase ulaze i deklaracije privatnih podataka članova: // deklaracija klase complex: class complex { public: void cAdd(complex); void cSub(complex); float cRe(); float cIm(); //... private: float real,imag; };
∗
Gore navedena deklaracija je zapravo definicija klase, ali se iz istorijskih razloga naziva deklaracijom. ∗ Pravu deklaraciju klase predstavlja samo deklaracija class S;. Pre potpune deklaracije (zapravo definicije) mogu samo da se definišu pokazivači i reference na tu klasu, ali ne i objekti te klase, jer se njihova veličina ne zna.
Pokazivač this ∗
Unutar svake funkcije članice postoji implicitni (podrazumevani, ugrađeni) lokalni objekat this. Tip ovog objekta je "konstantni pokazivač na klasu čija je funkcija članica" (ako je klasa X, this je tipa X*const). Ovaj pokazivač ukazuje na objekat čija je funkcija članica pozvana: // definicija funkcije cAdd èlanice klase complex complex complex::cAdd (complex c) { complex temp=*this; // u temp se prepisuje objekat koji je prozvan temp.real+=c.real; temp.imag+=c.imag; return temp; }
∗
Pristup članovima objekta čija je funkcija članica pozvana obavlja se neposredno; implicitno je to pristup preko pokazivača this i operatora ->. Može se i eksplicitno pristupati članovima preko ovog pokazivača unutar funkcije članice: // nova definicija funkcije cAdd èlanice klase complex complex complex::cAdd (complex c) { complex temp; temp.real=this->real+c.real; temp.imag=this->imag+c.imag; return temp; }
Skripta za Programiranje u Realnom Vremenu
70
Programiranje u Realnom Vremenu
∗
Pokazivač this je, u stvari, jedan skriveni argument funkcije članice. Poziv objekat.f() prevodilac prevodi u kôd koji ima semantiku kao f(&objekat). ∗ Pokazivač this može da se iskoristi prilikom povezivanja (uspostavljanja relacije između) dva objekta. Na primer, neka klasa X sadrži objekat klase Y, pri čemu objekat klase Y treba da "zna" ko ga sadrži (ko mu je "nadređeni"). Veza se inicijalno može uspostaviti pomoću konstruktora: class X { public: X () : y(this) {...} private: Y y; }; class Y { public: Y (X* theConta iner) : myContai ner(theC ontainer ) {...} private: X* myContai ner; };
Primerci klase ∗ ∗
Za svaki objekat klase formira se poseban komplet svih podataka članova te klase. Za svaku funkciju članicu, postoji jedinstven skup lokalnih statičkih objekata. Ovi objekti žive od prvog nailaska programa na njihovu definiciju, do kraja programa, bez obzira na broj objekata te klase. Lokalni statički objekti funkcija članica imaju sva svojstva lokalnih statičkih objekata funkcija nečlanica, pa nemaju nikakve veze sa klasom i njenim objektima. ∗ Podrazumevano se sa objektima klase može raditi sledeće: 1. definisati primerci (objekti) te klase i nizovi objekata klase; 2. definisati pokazivači na objekte i reference na objekte; 3. dodeljivati vrednosti (operator =) jednog objekta drugom; 4. uzimati adrese objekata (operator &) i posredno pristupati objektima preko pokazivača (operator *); 5. pristupati članovima i pozivati funkcije članice neposredno (operator .) ili posredno (operator ->); 6. prenositi objekti kao argumenti funkcija i to po vrednosti ili referenci, ili prenositi pokazivači na objekte; 7. vraćati objekti iz funkcija po vrednosti ili referenci, ili vraćati pokazivači na objekte. ∗ Neke od ovih operacija korisnik može redefinisati preklapanjem operatora. Ostale, ovde nenavedene operacije korisnik mora definisati posebno ako su potrebne (ne podrazumevaju se).
Konstantne funkcije članice ∗
Dobra programerska praksa je da se korisnicima klase specifikuje da li neka funkcija članica menja unutrašnje stanje objekta ili ga samo "čita" i vraća informaciju korisniku klase. ∗ Funkcije članice koje ne menjaju unutrašnje stanje objekta nazivaju se inspektori ili selektori (engl. inspector, selector). Da je funkcija članica inspektor, korisniku klase govori reč const iza
Skripta za Programiranje u Realnom Vremenu
71
Programiranje u Realnom Vremenu zaglavlja funkcije. Ovakve funkcije članice nazivaju se u jeziku C++ konstantnim funkcijama članicama (engl. constant member functions). ∗ Funkcija članica koja menja stanje objekta naziva se mutator ili modifikator (engl. mutator, modifier) i posebno se ne označava: class X { public : int read () const { return i; } int write (int j=0) { int temp=i; i=j; return temp; } privat e: int i; };
∗
Deklarisanje funkcije članice kao inspektora je samo notaciona pogodnost i "stvar lepog ponašanja prema korisniku". To je "obećanje" projektanta klase korisnicima da funkcija ne menja stanje objekta, onako kako je projektant klase definisao stanje objekta. Prevodilac nema načina da u potpunosti proveri da li inspektor menja neke podatke članove klase preko nekog posrednog obraćanja. ∗ Inspektor može da menja podatke članove, uz pomoć eksplicitne konverzije, koja "probija" kontrolu konstantnosti. To je ponekad slučaj kada inspektor treba da izračuna podatak koji vraća (npr. dužinu liste), pa ga onda sačuva u nekom članu da bi sledeći put brže vratio odgovor. ∗ U konstantnoj funkciji članici tip pokazivača this je const X*const, tako da pokazuje na konstantni objekat, pa nije moguće menjati objekat preko ovog pokazivača (svaki neposredni pristup članu je implicitni pristup preko ovog pokazivača). Takođe, za konstantne objekte klase nije dozvoljeno pozivati nekonstantnu funkciju članicu (korektnost konstantnosti). Za prethodni primer:
Skripta za Programiranje u Realnom Vremenu
72
X x; con st X cx;
Programiranje u Realnom Vremenu
Ugnežđivanje klasa x.r ead (); // u red u: kon sta ntn a fun kci ja nek ons tan tno g obj ekt a; x.w rit e() ; / / u red u: nek ons tan tna fun kci ja nek ons tan tno g obj ekt a; cx. rea d() ; / / u red u: kon sta ntn a fun kci ja kon sta ntn og obj ekt a; cx. wri te( );/ / gre
Skripta za Programiranje u Realnom Vremenu
73
Programiranje u Realnom Vremenu
∗
Klase mogu da se deklarišu i unutar deklaracije druge klase (ugnežđivanje deklaracija klasa). Na ovaj način se ugnežđena klasa nalazi u oblasti važenja okružujuće klase, pa se njenom imenu može pristupiti samo preko operatora razrešavanja oblasti važenja ::. ∗ Okružujuća klasa nema nikakva posebna prava pristupa članovima ugnežđene klase, niti ugnežđena klasa ima posebna prava pristupa članovima okružujuće klase. Ugnežđivanje je samo stvar oblasti važenja, a ne i kontrole pristupa članovima.
Skripta za Programiranje u Realnom Vremenu
74
Programiranje u Realnom Vremenu
int x,y; class Spoljna { public: int x; class Unutras nja { voi d f(int i, Spoljna *ps) { x =i; // greška: pristup Spoljna ::x nije korekta n! : :x=i; // u redu: pristup globaln om x; y =i; // u redu: pristup globaln om y; p s->x=i; // u redu: pristup Spoljna ::x objekta *ps; } }; }; Unutras nja u; // greška: Unutras nja nije u oblasti važenja ! Spoljna ::Unutr asnja u; // u redu;
Skripta za Programiranje u Realnom Vremenu
75
Programiranje u Realnom Vremenu
∗
Unutar deklaracije klase se mogu navesti i deklaracije nabrajanja (enum), i typedef deklaracije. Ugnežđivanje se koristi kada neki tip (nabrajanje ili klasa npr.) semantički pripada samo datoj klasi, a nije globalno važan i za druge klase. Ovakvo korišćenje povećava čitljivost programa i smanjuje potrebu za globalnim tipovima.
Strukture ∗
Struktura je klasa kod koje su svi članovi podrazumevano javni. Može se to promeniti eksplicitnim umetanjem public: i private: struct a { {
isto što i:
class a public: //... private: //... };
//... private: //... };
∗
Struktura se tipično koristi za definisanje slogova podataka koji ne predstavljaju apstrakciju, odnosno nemaju ponašanje (nemaju značajnije operacije). Strukture tipično poseduju samo konstruktore i eventualno destruktore kao funkcije članice.
Zajednički članovi klasa Zajednički podaci članovi ∗
Pri kreiranju objekata klase, za svaki objekat se kreira poseban komplet podataka članova. Ipak, moguće je definisati podatke članove za koje postoji samo jedan primerak za celu klasu, tj. za sve objekte klase. ∗ Ovakvi članovi nazivaju se statičkim članovima, i deklarišu se pomoću reči static: class X { public: //... private: static int i; // postoji samo jedan i za celu klasu int j; // svaki objekat ima svoj j //... };
∗
Svaki pristup statičkom članu iz bilo kog objeka klase znači pristup istom zajedničkom članu-
objektu.
∗
Statički član klase ima životni vek kao i globalni statički objekat: nastaje na početku programa i traje do kraja programa. Uopšte, statički član klase ima sva svojstva globalnog statičkog objekta, osim oblasti važenja klase i kontrole pristupa. ∗ Statički član mora da se inicijalizuje posebnom deklaracijom van deklaracije klase. Obraćanje ovakvom članu van klase vrši se preko operatora ::. Za prethodni primer:
Skripta za Programiranje u Realnom Vremenu
76
Programiranje u Realnom Vremenu
int X::i=5;
∗
Statičkom članu može da se pristupi iz funkcije članice, ali i van funkcija članica, čak i pre formiranja ijednog objekta klase (jer statički član nastaje kao i globalni objekat), naravno uz poštovanje prava pristupa. Tada mu se pristupa preko operatora :: (X::j). ∗ Zajednički članovi se uglavnom koriste kada svi primerci jedne klase treba da dele neku zajedničku informaciju, npr. kada predstavljaju neku kolekciju, odnosno kada je potrebno imati ih "sve na okupu i pod kontrolom". Na primer, svi objekti neke klase se uvezuju u listu, a glava liste je zajednički član klase. ∗ Zajednički članovi smanjuju potrebu za globalnim objektima i tako povećavaju čitljivost programa, jer je moguće ograničiti pristup njima, za razliku od globalnih objekata. Zajednički članovi logički pripadaju klasi i "upakovani" su u nju.
Zajedničke funkcije članice ∗
I funkcije članice mogu da se deklarišu kao zajedničke za celu klasu, dodavanjem reči static ispred deklaracije funkcije članice. ∗ Statičke funkcije članice imaju sva svojstva globalnih funkcija, osim oblasti važenja i kontrole pristupa. One ne poseduju pokazivač this i ne mogu neposredno (bez pominjanja konkretnog objekta klase) koristiti nestatičke članove klase. Mogu neposredno koristiti samo statičke članove te klase. ∗ Statičke funkcije članice se mogu pozivati za konkretan objekat (što nema posebno značenje), ali i pre formiranja ijednog objekta klase, preko operatora ::. ∗ Primer:
Skripta za Programiranje u Realnom Vremenu
77
class X { static int x; // statièki podatak èlan;
Programiranje u Realnom Vremenu
int y; public: static int f(X,X&); // statièka funkcija èlanica; int g(); }; int X::x=5; // definici ja statièko g podatka èlana; int X::f(X x1, X& x2){ // definici ja statièke funkcije èlanice; int i=x; // pristup statièko m èlanu X::x; int j=y; // greška: X::y nije statièki , // pa mu se ne može pristupi ti neposred no! int k=x1.y; // ovo može; return x2.x; // i ovo može, // ali se izraz "x2" ne izraèuna
Skripta za Programiranje u Realnom Vremenu
78
Programiranje u Realnom Vremenu
∗
Statičke funkcije predstavljaju operacije klase, a ne svakog posebnog objekta. Pomoću njih se definišu neke opšte usluge klase, npr. tipično kreiranje novih, dinamičkih objekata te klase (operator new je implicitno definisan kao statička funkcija klase). Na primer, na sledeći način može se obezbediti da se za datu klasu mogu kreirati samo dinamički objekti: class X { public: static X* create () { return new X; } private: X(); // konstruktor je privatan };
Prijatelji klasa ∗
Često je dobro da se klasa projektuje tako da ima i "povlašćene" korisnike, odnosno funkcije ili druge klase koje imaju pravo pristupa njenim privatnim članovima. Takve funkcije i klase nazivaju se prijateljima (enlgl. friends).
Prijateljske funkcije ∗
Prijateljske funkcije (engl. friend functions) su funkcije koje nisu članice klase, ali imaju pristup do privatnih članova klase. Te funkcije mogu da budu globalne funkcije ili članice drugih klasa. ∗ Da bi se neka funkcija proglasila prijateljem klase, potrebno je u deklaraciji te klase navesti deklaraciju te funkcije sa ključnom reči friend ispred. Prijateljska funkcija se definiše na uobičajen način:
Skripta za Programiranje u Realnom Vremenu
79
Programiranje u Realnom Vremenu
class X { friend void g (int,X&) ; // prijatel jska globalna funkcija friend void Y::h (); // prijatel jska èlanica druge klase int i; public: void f(int ip) {i=ip;} }; void g (int k, X &x) { x.i=k; // prijatel jska funkcija može da pristupa } // privatni m èlanovim a klase void main () { X x; x.f(5) ; // postavlj anje preko èlanice g(6,x) ; // postavlj anje preko prijatel ja } Skripta za Programiranje u Realnom Vremenu
80
Programiranje u Realnom Vremenu
∗
Globalne funkcije koje predstavljaju usluge neke klase ili operacije nad tom klasom (najčešće su prijatelji te klase) nazivaju se klasnim uslugama (engl. class utilities). ∗ Nema formalnih razloga da se koristi globalna (najčešće prijateljska) funkcija umesto funkcije članice. Postoje prilike kada su globalne (prijateljske) funkcije pogodnije: 1. funkcija članica mora da se pozove za objekat date klase, dok globalnoj funkciji može da se dostavi i objekat drugog tipa, koji će se konvertovati u potrebni tip; 2. kada funkcija treba da pristupa članovima više klasa, efikasnija je prijateljska globalna funkcija (primer u [Stroustrup91]); 3. ponekad je notaciono pogodnije da se koriste globalne funkcije (poziv je f(x)) nego članice (poziv je x.f()); na primer, max(a,b) je čitljivije od a.max(b); 4. kada se preklapaju operatori, često je jednostavnije definisati globalne (operatorske) funkcije neko članice. ∗ "Prijateljstvo" se ne nasleđuje: ako je funkcija f prijatelj klasi X, a klasa Y izvedena (naslednik) iz klase X, funkcija f nije prijatelj klasi Y.
Prijateljske klase ∗
Ako je potrebno da sve funkcije članice klase Y budu prijateljske funkcije klasi X, onda se klasa Y deklariše kao prijateljska klasa (friend class) klasi X. Tada sve funkcije članice klase Y mogu da pristupaju privatnim članovima klase X, ali obratno ne važi ("prijateljstvo" nije simetrična relacija): class X { friend class Y; //... };
∗
"Prijateljstvo" nije ni tranzitivna relacija: ako je klasa Y prijatelj klasi X, a klasa Z prijatelj klasi Y, klasa Z nije automatski prijatelj klasi X, već to mora eksplicitno da se naglasi (ako je potrebno). ∗ Prijateljske klase se tipično koriste kada neke dve klase imaju tešnje međusobne veze. Pri tome je nepotrebno (i loše) "otkrivati" delove neke klase da bi oni bili dostupni drugoj prijateljskoj klasi, jer će na taj način oni biti dostupni i ostalima (ruši se enkapsulacija). Tada se ove dve klase proglašavaju prijateljskim. Na primer, na sledeći način može se obezbediti da samo klasa Creator može da kreira objekte klase X:
Skripta za Programiranje u Realnom Vremenu
81
Programiranje u Realnom Vremenu
class X { public: ... private: friend class Creator; X(); // konstruk tor je dostupan samo klasi Creator ... };
Konstruktori i destruktori Pojam konstruktora ∗
Funkcija članica koja nosi isto ime kao i klasa naziva se konstruktor (engl. constructor). Ova funkcija poziva se prilikom kreiranja objekta te klase. ∗ Konstruktor nema tip koji vraća. Konstruktor može da ima argumente proizvoljnog tipa. Unutar konstruktora, članovima objekta pristupa se kao i u bilo kojoj drugoj funkciji članici. ∗ Konstruktor se uvek implicitno poziva pri kreiranju objekta klase, odnosno na početku životnog veka svakog objekta date klase. ∗ Konstruktor, kao i svaka funkcija članica, može biti preklopljen (engl. overloaded). Konstruktor koji se može pozvati bez stvarnih argumenata (nema formalne argumente ili ima sve argumente sa podrazumevanim vrednostima) naziva se podrazumevanim konstruktorom.
Kada se poziva konstruktor? ∗
Konstruktor je funkcija koja pretvara "presne" memorijske lokacije koje je sistem odvojio za novi objekat (i sve njegove podatke članove) u "pravi" objekat koji ima svoje članove i koji može da prima poruke, odnosno ima sva svojstva svoje klase i konzistentno početno stanje. Pre nego što se pozove konstruktor, objekat je u trenutku definisanja samo "gomila praznih bita" u memoriji računara. Konstruktor ima zadatak da od ovih bita napravi objekat tako što će inicijalizovati članove. ∗ Konstruktor se poziva uvek kada se kreira objekat klase, a to je u sledećim slučajevima: 1. kada se izvršava definicija statičkog objekta; 2. kada se izvršava definicija automatskog (lokalnog nestatičkog) objekta unutar bloka; formalni argumenti se, pri pozivu funkcije, kreiraju kao lokalni automatski objekti; 3. kada se kreira objekat, pozivaju se konstruktori njegovih podataka članova; 4. kada se kreira dinamički objekat operatorom new; 5. kada se kreira privremeni objekat, pri povratku iz funkcije, koji se inicijalizuje vraćenom vrednošću funkcije.
Načini pozivanja konstruktora ∗
Konstruktor se poziva kada se kreira objekat klase. Na tom mestu je moguće navesti inicijalizatore, tj. stvarne argumente konstruktora. Poziva se onaj konstruktor koji se najbolje slaže po broju i tipovima argumenata (pravila su ista kao i kod preklapanja funkcija):
Skripta za Programiranje u Realnom Vremenu
82
Programiranje u Realnom Vremenu
class X { public: X (); X (double) ; X (char*); //... }; void main () { double d=3.4; char *p="Niz znakova" ; X a(d), // poziva se X(double ) b(p) , // poziva se X(char*) c; // poziva se X() //... }
∗
Pri definisanju objekta c sa zahtevom da se poziva podrazumevani konstruktor klase X, ne treba navesti X c(); (jer je to deklaracija funkcije), već samo X d;. ∗ Pre izvršavanja samog tela konstruktora klase pozivaju se konstruktori članova. Argumenti ovih poziva mogu da se navedu iza zaglavlja definicije (ne deklaracije) konstruktora klase, iza znaka : (dvotačka):
Skripta za Programiranje u Realnom Vremenu
83
Programiranje u Realnom Vremenu
class YY { public: YY (int j) {...} //... }; class XX { YY y; int i; public: XX (int); }; XX::XX (int k) : y(k+1) , i(k-1) { // y je inicijali zovan sa k+1, a i sa k-1 // ... ostatak konstrukt ora }
∗
Prvo se pozivaju konstruktori članova, po redosledu deklarisanja u deklaraciji klase, pa se onda izvršava telo konstruktora klase. ∗ Ovaj način ne samo da je moguć, već je i jedino ispravan: navođenje inicijalizatora u zaglavlju konstruktora predstavlja specifikaciju inicijalizacije članova (koji su ugrađenog tipa ili objekti klase), što je različito od operacije dodele koja se može jedino vršiti unutar tela konstruktora. Osim toga, kada za člana korisničkog tipa ne postoji podrazumevani konstruktor, ili kada je član konstanta ili referenca, ovaj način je i jedini način inicijalizacije člana. ∗ Konstruktor se može pozvati i eksplicitno u nekom izrazu. Tada se kreira privre meni objekat klase pozivom odgovarajućeg konstruktora sa navedenim argumentima. Isto se dešava ako se u inicijalizatoru eksplicitno navede poziv konstruktora:
Skripta za Programiranje u Realnom Vremenu
84
Programiranje u Realnom Vremenu
void main () { complex c1(1,2.4),c2; c2=c1+compl ex(3.4,-1.5); // privremeni objekat complex c3=complex(0. 1,5); // opet privremeni objekat // koji se kopira u c3 }
∗
Kada se kreira niz objekata neke klase, poziva se podrazumevani konstruktor za svaku komponentu niza ponaosob, po rastućem redosledu indeksa.
Konstruktor kopije ∗
Kada se objekat x1 klase XX inicijalizuje drugim objektom x2 iste klase, C++ će podrazumevano (ugrađeno) izvršiti prostu inicijalizaciju redom članova objekta x1 članovima objekta x2. To ponekad nije dobro (često ako objekti sadrže članove koji su pokazivači ili reference), pa programer treba da ima potpunu kontrolu nad inicijalizacijom objekta drugim objektom iste klase. ∗ Za ovu svrhu služi tzv. konstruktor kopije (engl. copy constructor). To je konstruktor klase XX koji se može pozvati sa samo jednim stvarnim argumentom tipa XX. Taj konstruktor se poziva kada se objekat inicijalizuje objektom iste klase, a to je: 1. prilikom inicijalizacije objekta (pomoću znaka = ili sa zagradama); 2. prilikom prenosa argumenata u funkciju (kreira se lokalni automatski objekat); 3. prilikom vraćanja vrednosti iz funkcije (kreira se privremeni objekat). ∗ Konstruktor kopije nikad ne sme imati formalni argument tipa XX, a može argument tipa XX& ili najčešće const XX&. ∗ Primer:
Skripta za Programiranje u Realnom Vremenu
85
Programiranje u Realnom Vremenu
Destruktor class XX { public: XX (int); XX (const XX&); // konstrukt or kopije //... }; XX f(XX x1) { XX x2=x1; // poziva se konstrukt or kopije XX(XX&) za x2 //... return x2; // poziva se konstrukt or kopije za } // privremen i objekat u koji se smešta rezultat void g() { XX xa=3, xb=1; //... xa=f(xb ); // poziva se konstrukt or kopije samo za // formalni argument x1, // a u xa se samo prepisuje privremen i objekat, } // ili se poziva XX::opera tor= ako je definisan
Skripta za Programiranje u Realnom Vremenu
86
Programiranje u Realnom Vremenu
∗
Funkcija članica koja ima isto ime kao klasa, uz znak ~ ispred imena, naziva se destruktor (engl. destructor). Ova funkcija poziva se automatski, pri prestanku života objekta klase, za sve navedene slučajeve (statičkih, automatskih, klasnih članova, dinamičkih i privremenih objekata): class X { public: ~X () { cout<< "Poziv destrukt ora klase X!\n"; } } void main () { X x; //... } // ovde se poziva destrukt or objekta x
∗
Destruktor nema tip koji vraća i ne može imati argumente. Unutar destruktora, privatnim članovima pristupa se kao i u bilo kojoj drugoj funkciji članici. Svaka klasa može da ima najviše jedan destruktor. ∗ Destruktor se implicitno poziva i pri uništavanju dinamičkog objekta pomoću operatora delete. Za niz, destruktor se poziva za svaki element ponaosob. Redosled poziva destruktora je u svakom slučaju obratan redosledu poziva konstruktora. ∗ Destruktori se uglavnom koriste kada objekat treba da dealocira memoriju ili neke sistemske resurse koje je konstruktor alocirao; to je najčešće slučaj kada klasa sadrži članove koji su pokazivači. ∗ Posle izvršavanja tela destruktora, automatski se oslobađa memorija koju je objekat zauzimao. Zadaci: 7. Realizovati klasu koja implementira red čekanja (queue). Predvideti operacije stavljanja i uzimanja elementa, sve potrebne konstruktore (i konstruktor kopije) i ostale potrebne funkcije. 8. Skicirati klasu View koja će predstavljati apstrakciju svih vrsta entiteta koji se mogu pojaviti na ekranu monitora u nekom korisničkom interfejsu (prozor, meni, dijalog, itd.). Sve klase koje će realizovati pojedine entitete interfejsa biće izvedene iz ove klase. Ova klasa treba da ima virtuelnu funkciju draw, koja će predstavljati iscrtavanje entiteta pri osvežavanju (ažuriranju) izgleda ekrana (kada se nešto na ekranu promeni), i koju ne treba realizovati. Svaki objekat ove klase će se, pri kreiranju, "prijavljivati" u jednu listu svih objekata na ekranu. Klasa View treba da sadrži statičku funkciju članicu refresh koja će prolaziti kroz tu listu, pozivajući funkciju draw svakog objekta, kako bi se izgled ekrana osvežio. Redosled objekata u listi predstavlja redosled iscrtavanja, čime se dobija efekat preklapanja na ekranu. Zbog toga klasa View treba da ima funkciju članicu setFocus, koja će dati objekat postaviti na kraj liste (daje se fokus tom entitetu). Realizovati sve navedene delove klase View, osim funkcije draw.
Skripta za Programiranje u Realnom Vremenu
87
Programiranje u Realnom Vremenu
Preklapanje operatora Pojam preklapanja operatora ∗
Pretpostavimo da su nam u programu potrebni kompleksni brojevi i operacije nad njima. Treba nam struktura podataka koja će, pomoću osnovnih (u jezik ugrađenih) tipova, predstaviti strukturu kompleksnog broja, a takođe i funkcije koje će realizovati operacije nad kompleksnim brojevima. ∗ Kada je potrebna struktura podataka za koju detalji implementacije nisu bitni, već operacije koje se nad njom vrše, sve ukazuje na klasu. Klasa upravo predstavlja tip podataka za koji su definisane operacije. ∗ U jeziku C++, operatori za korisničke tipove su specijalne funkcije koje nose ime operator@, gde je @ neki operator ugrađen u jezik:
Skripta za Programiranje u Realnom Vremenu
88
Programiranje u Realnom Vremenu
class complex { public: complex(doub le,double); /* konstruktor */ friend complex operator+ (complex,compl ex); /* oparator + */ friend complex operator(complex,compl ex); /* operator */ private: double real, imag; }; complex::compl ex (double r, double i) : real(r), imag(i) {} complex operator+ (complex c1, complex c2) { complex temp(0,0); /* privremena promenljiva tipa complex */ temp.real=c1 .real+c2.real; temp.imag=c1 .imag+c2.imag; return temp; } complex operator(complex c1, complex c2) { /* može i ovako: vratiti privremenu promenljivu koja se kreira konstruktorom sa odgovarajuæim argumentima */ return complex(c1.rea lc2.real,c1.ima g-c2.imag); }
Skripta za Programiranje u Realnom Vremenu
89
Programiranje u Realnom Vremenu
∗
Operatorske funkcije se mogu koristiti u izrazima kao i operatori nad ugrađenim tipovima. Izraz t1@t2 se tumači kao t1.operator@(t2) ili operator@(t1,t2): complex c1(3,5.4),c2(0,5.4),c3(0,0); c3=c1+c2; /* poziva se operator+(c1,c2) */ c1=c2-c3; /* poziva se operator-(c2,c3) */
Operatorske funkcije Osnovna pravila ∗
U jeziku C++, pored "običnih" funkcija koje se eksplicitno pozivaju navođenjem identifikatora sa zagradama, postoje i operatorske funkcije. ∗ Operatorske funkcije su posebna vrsta funkcija koje imaju posebna imena i način pozivanja. Kao i obične funkcije, i one se mogu preklopiti za operande koji pripadaju korisničkim tipovima. Ovaj princip naziva se preklapanje operatora (engl. operator overloading). ∗ Ovaj princip omogućava da se definišu značenja operatora za korisničke tipove i formiraju izrazi sa objektima ovih tipova, na primer operacije nad kompleksnim brojevima (ca*cb+cc-cd), matricama (ma*mb+mc-md) itd. ∗ Ipak, postoje neka ograničenja u preklaanju operatora: 1. ne mogu da se preklope operatori ., .*, ::, ?: i sizeof, dok svi ostali mogu; 2. ne mogu da se redefinišu značenja operatora za ugrađene (standardne) tipove podataka; 3. ne mogu da se uvode novi simboli za operatore; 4. ne mogu da se menjaju osobine operatora koje su ugrađene u jezik: n-arnost, prioriteti i asocijativnost (smer grupisanja). ∗ Operatorske funkcije imaju imena operator@, gde je @ znak operatora. Operatorske funkcije mogu biti članice ili globalne funkcije (uglavnom prijatelji klasa) kod kojih je bar jedan argument tipa korisničke klase: complex operator+ (complex c, double d) { return complex(c.real+d,c.imag); } // ovo je globalna funkcija prijatelj complex operator** (complex c, double d) { // ovo ne može // hteli smo stepenovanje }
∗
Za korisničke tipove su unapred definisana uvek dva operatora: = (dodela vrednosti) i & (uzimanje adrese). Sve dok ih korisnik ne redefiniše, oni imaju podrazumevano značenje. ∗ Podrazumevano značenje operatora = je kopiranje objekta dodelom član po član (pozivaju se operatori = klasa kojima članovi pripadaju, ako su definisani). Ako objekat sadrži člana koji je pokazivač, kopiraće se, naravno, samo traj pokazivač, a ne i pokazivana vrednost. Ovo nekad nije odgovarajuće i korisnik treba da redefiniše operator =. ∗ Vrednosti operatorskih funkcija mogu da budu bilo kog tipa, pa i void.
Bočni efekti i veze između operatora ∗
Bočni efekti koji postoje kod operatora za ugrađene tipove nikad se ne podrazumevaju za redefinisane operatore: ++ ne mora da menja stanje objekta, niti da znači sabiranje sa 1. Isto važi i za -- i sve operatore dodele (=, +=, -=, *= itd.). ∗ Operator = (i ostali operatori dodele) ne mora da menja stanje objekta. Ipak, ovakve upotrebe treba strogo izbegavati: redefinisani operator treba da ima isto ponašanje kao i za ugrađene tipove.
Skripta za Programiranje u Realnom Vremenu
90
Programiranje u Realnom Vremenu
∗
Veze koje postoje između operatora za ugrađene tipove se ne podrazumevaju za redefinisane operatore. Na primer, a+=b ne mora da automatski znači a=a+b, ako je definisan operator +, već operator += mora posebno da se definiše. ∗ Strogo se preporučuje da operatori koje definiše korisnik imaju očekivano značenje, radi čitljivosti programa. Na primer, ako su definisani i operator += i operator +, dobro je da a+=b ima isti efekat kao i a=a+b. Treba izbegavati neočekivana značenja, na primer da operator - realizuje sabiranje matrica. ∗ Kada se definišu operatori za klasu, treba težiti da njihov skup bude kompletan. Na primer, ako su definisani operatori = i +, treba definisati i operator +=; ili, uvek treba definisati oba operatora == i !=, a ne samo jedan.
Operatorske funkcije kao članice i globalne funkcije ∗
Operatorske funkcije mogu da budu članice klasa ili (najčešće prijateljske) globalne funkcije. Ako je @ neki binarni operator (na primer +), on može da se realizuje kao funkcija članica klase X na sledeći način (mogu se argumenti prenositi i po referenci): tip operator@ (X) ili kao prijateljska globalna funkcija na sledeći način: tip operator@ (X,X) Nije dozvoljeno da se u programu nalaze obe ove funkcije. ∗ Poziv a@b se sada tumači kao: a.operator@(b) , za funkciju članicu, ili: operator@(a,b) , za globalnu funkciju. ∗ Primer:
Skripta za Programiranje u Realnom Vremenu
91
Programiranje u Realnom Vremenu
class complex { double real,imag; public: complex (double r=0, double i=0) : real(r), imag(i) {} complex operator+ (coplex c) { return complex(real+c .real,imag+c.i mag; } }; // ili, alternativno: class complex { double real,imag; public: complex (double r=0, double i=0) : real(r), imag(i) {} friend complex operator+ (complex,cople x); }; complex operator+ (complex c1, complex c2) { return complex(c1.rea l+c2.real,c1.i mag+c2.imag); } void main () { complex c1(2,3),c2(3.4 ); complex c3=c1+c2; // poziva se c1.operator+ (c2) ili // operator+ (c1,c2) //... } Skripta za Programiranje u Realnom Vremenu
92
Programiranje u Realnom Vremenu
∗
Razlozi za izbor jednog ili drugog načina (članica ili prijatelj) su isti kao i za druge funkcije. Ovde postoji još jedna razlika: ako za prethodni primer hoćemo da se može vršiti i operacija sabiranja realnog broja sa kompleksnim, treba definisati globalnu funkciju. Ako hoćemo da se može izvršiti d+c, gde je d tipa double, ne možemo definisati novu operatorsku "članicu klase double", jer ugrađeni tipovi nisu klase (C++ nije čisti OO jezik). Operatorska funkcija članica "ne dozvoljava promociju levog operanda", što znači da se neće izvršiti konverzija operanda d u tip complex. Treba izabrati drugi navedeni postupak (sa prijateljskom operatorskom funkcijom).
Unarni i binarni operatori ∗
Mnogi operatori jezika C++ (kao i jezika C) mogu da budu i unarni i binarni (unarni i binarni -, unarni &-adresa i binarni &-logičko I po bitovima itd.). Kako razlikovati unarne i binarne operatore prilikom preklapanja? ∗ Unarni operator ima samo jedan operand, pa se može realizovati kao operatorska funkcija članica bez argumenata (prvi operand je objekat čija je funkcija članica pozvana): tip operator@ () ili kao globalna funkcija sa jednim argumentom: tip operator@ (X x) ∗ Binarni operator ima dva argumenta, pa se može realizovati kao funkcija članica sa jednim argumentom (prvi operand je objekat čija je funkcija članica pozvana): tip operator@ (X xdesni) ili kao globalna funkcija sa dva argumenta: tip operator@ (X xlevi, X xdesni) ∗ Primer: class complex { double real,imag; public: complex (double r=0, double i=0) : real(r), imag(i) {} friend complex operator+ (complex,cople x); complex operator! () // unarni operator!, konjugovani broj { return complex(real,imag); } };
Neki posebni operatori Operatori new i delete ∗
Ponekad programer želi da preuzme kontrolu nad alokacijom dinamičkih objekata neke klase, a ne da je prepusti ugrađenom alokatoru. To je zgodno npr. kada su objekti klase mali i može se precizno kontrolisati njihova alokacija, tako da se smanje režije oko alokacije. ∗ Za ovakve potrebe mogu se preklopiti operatori new i delete za neku klasu. Operatorske funkcije new i delete moraju buti statičke (static) funkcije članice, jer se one pozivaju pre nego što je objekat stvarno kreiran, odnosno pošto je uništen.
Skripta za Programiranje u Realnom Vremenu
93
Programiranje u Realnom Vremenu
∗
Ako je korisnik definisao ove operatorske funkcije za neku klasu, one će se pozivati kad god se kreira dinamički objekat te klase operatorom new, odnosno kada se takav objekat dealocira operatorom delete. ∗ Unutar tela ovih operatorskih funkcija ne treba eksplicitno pozivati konstruktor, odnosno destruktor. Konstruktor se implicitno poziva posle operatorske funkcije new, a destruktor se implicitno poziva pre operatorske funkcije delete. Ove operatorske funkcije služe samo da obezbede prostor za smeštanje objekta i da ga posle oslobode, a ne da od "presnih" bita naprave objekat (što rade konstruktori), odnosno pretvore ga u "presne bite" (što radi destruktor). Operator new treba da vrati pokazivač na alocirani prostor. ∗ Ove operatorske funkcije deklarišu se na sledeći načun: void* operator new (size_t velicina) void operator delete (void* pokazivac) Tip size_t je celobrojni tip definisan u <stdlib.h> i služi za izražavanje veličina objekata. Argument velicina daje veličinu potrebnog prostora koga treba alocirati za objekat. Argument pokazivac je pokazivač na prostor koga treba osloboditi. ∗ Podrazumevani (ugrađeni) operatori new i delete mogu da se pozivaju unutar tela redefinisanih operatorskih funkcija ili eksplicitno, preko operatora ::, ili implicitno, kada se dinamički kreiraju objekti koji nisu tipa za koga su redefinisani ovi operatori. ∗ Primer: #include <stdlib.h> class XX { //... public: void* operator new (size_t sz) { return new char[sz]; } // koristi se ugraðeni new void operator delete (void *p) { delete [] p; } // koristi se ugraðeni delete //... };
Konstruktor kopije i operator dodele ∗ ∗
Inicijalizacija objekta pri kreiranju i dodela vrednosti su dve suštinski različite operacije. Inicijalizacija se vrši u svim slučajevima kada se kreira objekat (statički, automatski, klasni član, privremeni i dinamički). Tada se poziva konstruktor, iako se inicijalizacija obavlja preko znaka =. Ako je izraz sa desne strane znaka = istog tipa kao i objekat koji se kreira, poziva se konstruktor kopije, ako je definisan. Ovaj konstruktor najčešće kopira ceo složeni objekat, a ne samo članove. ∗ Dodelom se izvršava operatorska funkcija operator=. To se dešava kada se eksplicitno u nekom izrazu poziva ovaj operator. Ovaj operator najčešće prvo uništava prethodno formirane delove objekta, pa onda formira nove, uz kopiranje delova objekta sa desne strane znaka dodele. Ova operatorska funkcija mora biti nestatička funkcija članica. ∗ Inicijalizacija podrazumeva da objekat još ne postoji. Dodela podrazumeva da objekat sa leve strane operatora postoji. ∗ Ako neka klasa sadrži destruktor, konstruktor kopije ili operator dodele, sva je prilika da treba da sadrži sva tri. ∗ Primer - klasa koja realizuje niz znakova:
Skripta za Programiranje u Realnom Vremenu
94
Programiranje u Realnom Vremenu
class String { public: String(cons t char*); String(cons t String&); // konstruktor kopije String& operator= (const String&); // operator dodele //... private: char *niz; }; String::Strin g (const String &s) { if (niz=new char [strlen(s.niz )+1]) strcpy(niz,s. niz); } String& String:operat or= (const String &s) { if (&s! =this) { // provera na s=s if (niz) delete [] niz; // prvo oslobodi staro, if (niz=new char [strlen(s.niz )+1]) strcpy(niz,s. niz); } // pa onda zauzmi novo return *this; } void main () { String a("Hello world!"), b=a; // String(const String&); a=b; // operator= //... }
Skripta za Programiranje u Realnom Vremenu
95
Programiranje u Realnom Vremenu
∗
Posebno treba obratiti pažnju na karakteristične slučajeve pozivanja konstruktora kopije: 1. pri inicijalizaciji objekta izrazom istog tipa poziva se konstruktor kopije; 2. pri pozivanju funkcije, formalni argumenti se inicijalizuju stvarnim i, ako su istog tipa, poziva se konstruktor kopije; 3. pri vraćanju vrednosti iz funkcije, privremeni objekat se inicijalizuje vrednošću koja se iz funkcije vraća i, ako su istog tipa, poziva se konstruktor kopije.
Osnovni standardni ulazno/izlazni tokovi Klase istream i ostream ∗
Kao i jezik C, ni C++ ne sadrži (u jezik ugrađene) ulazno/izlazne (U/I) operacije, već se one realizuju standardnim bibliotekama. Ipak, C++ sadrži standardne U/I biblioteke realizovane u duhu OOP-a. ∗ Na raspolaganju su i stare C biblioteke sa funkcijama scanf i printf, ali njihovo korišćenje nije u duhu jezika C++. ∗ Biblioteka čije se deklaracije nalaze u zaglavlju
sadrži dve osnovne klase, istream i ostream (ulazni i izlazni tok). Svakom primerku (objektu) klasa ifstream i ofstream, koje su redom izvedene iz navedenih klasa, može da se pridruži jedna datoteka za ulaz/izlaz, tako da se datotekama pristupa isključivo preko ovakvih objekata, odnosno funkcija članica ili prijatelja ovih klasa. Time je podržan princip enkapsulacije. ∗ U ovoj biblioteci definisana su i dva korisniku dostupna (globalna) statička objekta: 1. objekat cin klase istream koji je pridružen standardnom ulaznom uređaju (obično tastatura); 2. objekat cout klase ostream koji je pridružen standardnom izlaznom uređaju (obično ekran). ∗ Klasa istream je preklopila operator >> za sve ugrađene tipove, koji služi za ulaz podataka: istream& operator>> (istream &is, tip &t); gde je tip neki ugrađeni tip objekta koji se čita. ∗ Klasa ostream je preklopila operator << za sve ugrađene tipove, koji služi za izlaz podataka: ostream& operator<< (ostream &os, tip x); gde je tip neki ugrađeni tip objekta koji se ispisuje. ∗ Ove funkcije vraćaju reference, tako da se može vršiti višestruki U/I u istoj naredbi. Osim toga, ovi operatori su asocijativni sleva, tako da se podaci ispisuju u prirodnom redosledu. ∗ Ove operatore treba koristiti za uobičajene, jednostavne U/I operacije: #include U/I void main () { int i; cin>>i; cout<<"i="<
∗
// obavezno ako se želi
// uèitava se i // ispisuje se npr.: // novi red
O detaljima klasa istream i ostream treba videti [Stroustrup91] i .
Ulazno/izlazne operacije za korisničke tipove ∗
Korisnik može da definiše značenja operatora >> i << za svoje tipove. To se radi definisanjem prijateljskih funkcija korisnikove klase, jer je prvi operand tipa istream& odnosno ostream&. ∗ Primer za klasu complex:
Skripta za Programiranje u Realnom Vremenu
96
Programiranje u Realnom Vremenu
#include class complex { double real,imag; friend ostream& operator<< (ostream&,const complex&); public: //... kao i ranije }; //... ostream& operator<< (ostream &os, const complex &c) { return os<<"("<
Nasleđivanje Izvedene klase Šta je nasleđivanje i šta su izvedene klase? ∗
U praksi se često sreće slučaj da se jedna klasa objekata (klasa B) podvrsta neke druge klase (klasa A). To znači da su objekti klase B "jedna (specijalna) vrsta" ("a-kind-of") objekata klase A, ili da objekti klase B "imaju sve osobine klase A, i još neke, sebi svojstvene". Ovakva relacija između klasa naziva se nasleđivanje (engl. inheritance): klasa B nasleđuje klasu A. ∗ Primeri: 1. "Sisari" su klasa koja je okarakterisana načinom reprodukcije. "Mesožderi" su "sisari" koji se hrane mesom. "Biljojedi" su sisari koji se hrane biljkama. Uopšte, u živom svetu odnosi "vrsta" predstavljaju relaciju nasleđivanja klasa.
Skripta za Programiranje u Realnom Vremenu
97
Programiranje u Realnom Vremenu 2. "Geometrijske figure u ravni" su klasa koja je okarakterisana koordinatama težišta. "Krug" je figura koja je okarakterisana dužinom poluprečnika. "Kvadrat" je figura koja je okarakterisana dužinom ivice. 3. "Izlazni uređaji računara" su klasa koja ima operacije pisanja jednog znaka. "Ekran" je izlazni uređaj koji ima mogućnost i crtanja, brisanja, pomeranja kurzora itd. ∗ Relacija nasleđivanja se u programskom modelu definiše u odnosu na to šta želimo da klase rade, odnosno koja svojstva i servise da imaju. Primer: da li je krug jedna vrsta elipse, ili je elipsa jedna vrsta kruga, ili su i krug i elipsa podvrste ovalnih figura? ∗ Ako je klasa B nasledila klasu A, kaže se još da je klasa A osnovna klasa (engl. base class), a klasa B izvedena klasa (engl. derived class). Ili da je klasa A nadklasa (engl. superclass), a klasa B podklasa (engl. subclass). Ili da je klasa A roditelj (engl. parent), a klasa B dete (engl. child). Relacija nasleđivanja se najčešće prikazuje (usmerenim acikličnim) grafom:
∗
Jezici koji podržavaju nasleđivanje nazivaju se objektno orijentisanim (engl. Object-Oriented Programming Languages, OOPL).
Kako se definišu izvedene klase u jeziku C++? ∗
Da bi se klasa izvela iz neke postojeće klase, nije potrebno vršiti nikakve izmene postojeće klase, pa čak ni njeno ponovno prevođenje. Izvedena klasa se deklariše navođenjem reči public i naziva osnovne klase, iza znaka : (dvotačka): class Base { int i; public: void f(); }; class Derived : public Base { int j; public: void g(); };
∗
Objekti izvedene klase imaju sve članove osnovne klase, i svoje posebne članove koji su navedeni u deklaraciji izvedene klase. ∗ Objekti izvedene klase definišu se i koriste na uobičajen način:
Skripta za Programiranje u Realnom Vremenu
98
Programiranje u Realnom Vremenu
void main () { Base b; Derived d; b.f(); b.g(); // ovo, naravno, ne može d.f(); // d ima i funkciju f, d.g(); // i funkciju g }
∗
Izvedena klasa ne nasleđuje funkciju članicu operator=.
Prava pristupa ∗
Ključna reč public u zaglavlju deklaracije izvedene klase znači da su svi javni članovi osnovne klase ujedno i javni članovi izvedene klase. ∗ Privatni članovi osnovne klase uvek to i ostaju. Funkcije članice izvedene klase ne mogu da pristupaju privatnim članovima osnovne klase. Nema načina da se "povredi privatnost" osnovne klase (ukoliko neko nije prijatelj te klase, što je zapisano u njenoj deklaraciji), jer bi to značilo da postoji mogućnost da se probije enkapsulacija koju je zamislio projektant osnovne klase. ∗ Javnim članovima osnovne klase se iz funkcija članica izvedene klase pristupa neposredno, kao i sopstvenim članovima: class Base { int pb; public: int jb; void put(int x) {pb=x;} }; class Derived : public Base { int pd; public: void write(int a, int b, int c) { pd=a; jb=b; pb=c; // ovo ne može, put(c); // veæ mora ovako } };
Skripta za Programiranje u Realnom Vremenu
99
Programiranje u Realnom Vremenu
∗
Deklaracija člana izvedene klase sakriva istoimeni član osnovne klase. Sakrivenom članu osnovne klase može da se pristupi pomoću operatora ::. Na primer, Base::jb. ∗ Često postoji potreba da nekim članovima osnovne klase mogu da pristupe funkcije članice izvedenih klasa, ali ne i korisnici klasa. To su najčešće funkcije članice koje direktno pristupaju privatnim podacima članovima. Članovi koji su dostupni samo izvedenim klasama, ali ne i korisnicima spolja, navode se iza ključne reči protected: i nazivaju se zaštićeni članovi (engl. protected members). ∗ Zaštićeni članovi ostaju zaštićeni i za sledeće izvedene klase pri sukcesivnom nasleđivanju. Uopšte, ne može se povećati pravo pristupa nekom članu koji je privatan, zaštićen ili javni. class Base { int pb; protected: int zb; public: int jb; //... }; class Derived : public Base { //... public: void write(int x) { jb=zb=x ; // može da pristupi javnom i zaštiæenom èlanu, pb=x; // ali ne i privatnom: greška! } }; void f() { Base b; b.zb=5; // odavde ne može da se pristupa zaštiæenom èlanu }
Konstruktori i destruktori izvedenih klasa ∗
Prilikom kreiranja objekta izvedene klase, poziva se konstruktor te klase, ali i konstruktor osnovne klase. U zaglavlju definicije konstruktora izvedene klase, u listi inicijalizatora, moguće je navesti i inicijalizator osnovne klase (argumente poziva konstruktora osnovne klase). To se radi navođenjem imena osnovne klase i argumenata poziva konstruktora osnovne klase:
Skripta za Programiranje u Realnom Vremenu
100
Programiranje u Realnom Vremenu
class Base { int bi; //... public: Base(int) ; // konstruktor osnovne klase //... }; Base::Base (int i) : bi(i) {/*...*/} class Derived : public Base { int di; //... public: Derived(i nt); //... }; Derived::De rived (int i) : Base(i),di( i+1) {/*...*/}
∗
Pri kreiranju objekta izvedene klase redosled poziva konstruktora je sledeći: 1. inicijalizuje se podobjekat osnovne klase, pozivom konstruktora osnovne klase; 2. inicijalizuju se podaci članovi, eventualno pozivom njihovih konstruktora, po redosledu deklarisanja; 3. izvršava se telo konstruktora izvedene klase. ∗ Pri uništavanju objekta, redosled poziva destruktora je uvek obratan.
Skripta za Programiranje u Realnom Vremenu
101
class XX { //... public: XX() {cout<<"K Polimorfizam onstrukto r klase XX.\n";} ~XX() {cout<<"D estruktor klase XX.\n";} };
Programiranje u Realnom Vremenu
class Base { //... public: Base() {cout<<"K onstrukto r osnovne klase.\n" ;} ~Base() {cout<<"D estruktor osnovne klase.\n" ;} //... }; class Derived : public Base { XX xx; //... public: Derived () {cout<<"K onstrukto r izvedene klase.\n" ;} ~Derive d() {cout<<"D estruktor izvedene klase.\n" ;} //... }; void main () { Derived d; } /* Izlaz æe biti: Konstrukt or osnovne klase. Konstrukt or klase XX.
Skripta za Programiranje u Realnom Vremenu
102
Programiranje u Realnom Vremenu
Šta je polimorfizam? ∗
Pretpostavimo da smo projektovali klasu geometrijskih figura sa namerom da sve figure imaju funkciju crtaj() kao članicu. Iz ove klase izveli smo klase kruga, kvadrata, trougla itd. Naravno, svaka izvedena klasa treba da realizuje funkciju crtanja na sebi svojstven način (krug se sasvim drugačije crta od trougla). Sada nam je potrebno da u nekom delu programa iscrtamo sve figure koje se nalaze na našem crtežu. Ovim figurama pristupamo preko niza pokazivača tipa figura*. C++ omogućava da figure jednostavno iscrtamo prostim navođenjem: void crtanje () { for (int i=0; icrtaj(); }
∗
Iako se u ovom nizu mogu naći različite figure (krugovi, trouglovi itd.), mi im jednostavno pristupamo kao figurama, jer sve vrste figura imaju zajedničku osobinu "da mogu da se nacrtaju". Ipak, svaka od figura će svoj zadatak ispuniti onako kako joj to i priliči, odnosno svaki objekat će "prepoznati" kojoj izvedenoj klasi pripada, bez obzira što mu se obraćamo "uopšteno", kao objektu osnovne klase. To je posledica naše pretpostavke da je i krug, i kvadrat i trougao takođe i figura. ∗ Svojstvo da svaki objekat izvedene klase izvršava metod tačno onako kako je to definisano u njegovoj izvedenoj klasi, kada mu se pristupa kao objektu osnovne klase, naziva se polimorfizam (engl. polymorphism).
Virtuelne funkcije ∗
Funkcije članice osnovne klase koje se u izvedenim klasama mogu realizovati specifično za svaku izvedenu klasu nazivaju se virtuelne funkcije (engl. virtual functions). ∗ Virtuelna funkcija se u osnovnoj klasi deklariše pomoću ključne reči virtual na početku deklaracije. Prilikom definisanja virtuelnih funkcija u izvedenim klasama ne mora se stavljati reč virtual. ∗ Prilikom poziva se odaziva ona funkcija koja pripada klasi kojoj i objekat koji prima poziv.
Skripta za Programiranje u Realnom Vremenu
103
Programiranje u Realnom Vremenu
class ClanBlioteke { //... protected: Racun r; //... public: virtual int platiClanarinu () // virtuelna funkcija { return r=clanarina; } //... }; class PocasniClan : public ClanBiblioteke { //... public: int platiClanarinu () { return r; } }; void main () { ClanBiblioteke *clanovi[100]; //... for (int i=0; iplatiClanarinu(); //... }
∗
Virtuelna funkcija osnovne klase ne mora da se redefiniše u svakoj izvedenoj klasi. U izvedenoj klasi u kojoj virtuelna funkcija nije definisana, važi značenje te virtuelne funkcije iz osnovne klase. ∗ Deklaracija neke virtuelne funkcije u svakoj izvedenoj klasi mora da se u potpunosti slaže sa deklaracijom te funkcije u osnovnoj klasi (broj i tipovi argumenata, kao i tip rezultata). ∗ Ako se u izvedenoj klasi deklariše neka funkcija koja ima isto ime kao i virtuelna funkcija iz osnovne klase, ali različit broj i/ili tipove argumenata, onda ona sakriva (a ne redefiniše) sve ostale funkcije sa istim imenom iz osnovne klase. To znači da u izvedenoj klasi treba ponovo definisati sve ostale funkcije sa tim imenom. Nikako nije dobro (to je greška u projektovanju) da izvedena klasa sadrži samo neke funkcije iz osnovne klase, ali ne sve: to znači da se ne radi o pravom nasleđivanju (korisnik izvedene klase očekuje da će ona ispuniti sve zadatke koje može i osnovna klasa). ∗ Virtuelne funkcije moraju biti članice svojih klasa (ne globalne), a mogu biti prijatelji drugih klasa.
Dinamičko vezivanje ∗
Pokazivač na objekat izvedene klase se može implicitno konvertovati u pokazivač na objekat osnovne klase (pokazivaču na objekat osnovne klase se može dodeliti pokazivač na objekat izvedene klase direktno, bez eksplicitne konverzije). Isto važi i za reference. Ovo je interpretacija činjenice da se objekat izvedene klase može smatrati i objektom osnovne klase.
Skripta za Programiranje u Realnom Vremenu
104
Programiranje u Realnom Vremenu
∗
Pokazivaču na objekat izvedene klase se može dodeliti pokazivač na objekat osnovne klase samo uz eksplicitnu konverziju. Ovo je interpretacija činjenice da objekat osnovne klase nema sve osobine izvedene klase. ∗ Objekat osnovne klase može se inicijalizovati objektom izvedene klase, i objektu osnovne klase može se dodeliti objekat izvedene klase bez eksplicitne konverzije. To se obavlja prostim "odsecanjem" članova izvedene klase koji nisu i članovi osnovne klase. ∗ Virtuelni mehanizam se aktivira ako se objektu pristupa preko reference ili pokazivača:
Skripta za Programiranje u Realnom Vremenu
105
class Base { //... public: virtual void f(); //... };
Programiranje u Realnom Vremenu
class Derived : public Base { //... public: void f(); }; void g1(Base b) { b.f(); } void g2(Base *pb) { pb->f(); } void g3(Base &rb) { rb.f(); } void main () { Derived d; g1(d); // poziva se Base::f g2(&d); // poziva se Derived::f g3(d); // poziva se Derived::f Base *pb=new Derived; pb->f(); // poziva se Derived::f Derived &rd=d; rd.f(); // poziva se Derived::f Base b=d; b.f(); // poziva se Base::f delete pb; pb=&b; pb->f(); // poziva se Base::f }
Skripta za Programiranje u Realnom Vremenu
106
Programiranje u Realnom Vremenu
∗
Postupak koji obezbeđuje da se funkcija koja se poziva određuje po tipu objekta, a ne po tipu pokazivača ili reference na taj objekat, naziva se dinamičko vezivanje (engl. dynamic binding). Razrešavanje koja će se verzija virtuelne funkcije (osnovne ili izvedene klase) pozvati obavlja se u toku izvršavanja programa.
Virtuelni destruktor ∗
Destruktor je jedna "specifična funkcija članica klase" koja pretvara "živi" objekat u "običnu gomilu bita u memoriji". Zbog takvog svog značenja, nema razloga da i destruktor ne može da bude virtuelna funkcija. ∗ Virtuelni mehanizam obezbeđuje da se pozove odgovarajući destruktor (osnovne ili izvedene klase) kada se objektu pristupa posredno: class Base { //... public: virtual ~Base(); //... }; class Derived : public Base { //... public: ~Derived( ); //... }; void release (Base *pb) { delete pb; } void main () { Base *pb=new Base; Derived *pd=new Derived; release(p b); // poziva se ~Base release(p d); // poziva se ~Derived }
∗
Kada neka klasa ima neku virtuelnu funkciju, sva je prilika da i njen destruktor (ako ga ima) treba da bude virtuelan. ∗ Unutar virtuelnog destruktora izvedene klase ne treba eksplicitno pozivati destruktor osnovne klase, jer se on uvek implicitno poziva. Definisanjem destruktora kao virtuelne funkcije obezbeđuje se
Skripta za Programiranje u Realnom Vremenu
107
Programiranje u Realnom Vremenu da se dinamičkim vezivanjem tačno određuje koji će destruktor (osnovne ili izvedene klase) biti prvo pozvan; destruktor osnovne klase se uvek izvršava (ili kao jedini ili posle destruktora izvedene klase). ∗ Konstruktor je funkcija koja od "obične gomile bita u memoriji" kreira "živi" objekat. Konstruktor se poziva pre nego što se objekat kreira, pa nema smisla da bude virtuelan, što C++ ni ne dozvoljava. Kada se definiše objekat, uvek se navodi i tip (klasa) kome pripada, pa je određen i konstruktor koji se poziva.
Nizovi i izvedene klase ∗
Objekat izvedene klase je jedna vrsta objekta osnovne klase. Međutim, niz objekata izvedene klase nije jedna vrsta niza objekata osnovne klase. Uopšte, neka kolekcija objekata izvedene klase nije jedna vrsta kolekcije objekata osnovne klase. ∗ Na primer, iako je automobil jedna vrsta vozila, parking za automobile nije i parking za (sve vrste) vozila, jer na parking za automobile ne mogu da stanu i kamioni (koji su takođe vozila). Ili, ako korisnik neke funkcije prosledi toj funkciji korpu banana (banana je vrsta voća), ne bi valjalo da mu ta funkcija vrati korpu u kojoj je jedna šljiva (koja je takođe vrsta voća), smatrajući da je korpa banana isto što i korpa bilo kakvog voća [FAQ]. ∗ Ako se računa sa nasleđivanjem, u programu ne treba koristiti nizove objekata, već nizove pokazivača na objekte. Ako se formira niz objekata izvedene klase i on prenese kao niz objekata osnovne klase (što po prethodno rečenom semantički nije ispravno, ali je moguće), može doći do greške: class Base { public: int bi; }; class Derived : public Base { public: int di; }; void f(Base *b) { cout<
∗
U prethodnom primeru, funkcija f smatra da je dobila niz objekata osnovne klase koji su kraći (nemaju sve članove) od objekata izvedene klase. Kada joj se prosledi niz objekata izvedene klase (koji su duži), funkcija nema načina da odredi da se niz sastoji samo od objekata izvedene klase. Rezultat je, u opštem slučaju, neodređen. Osim toga, dinamičko vezivanje važi samo za funkcije članice, a ne i za podatke. ∗ Pored navedene greške, nije fizički moguće u niz objekata osnovne klase smeštati direktno objekte izvedene klase, jer su oni duži, a za svaki element niza je odvojen samo prostor koji je dovoljan za smeštanje objekta osnovne klase.
Skripta za Programiranje u Realnom Vremenu
108
Programiranje u Realnom Vremenu
∗
Zbog svega što je rečeno, kolekcije (nizove) objekata treba kreirati kao nizove pokazivača na
objekte: void f(Base **b, int i) { cout<bi; } void main () { Base b1,b2; Derived d1,d2,d3; Base *b[5]; može konvertovati u tip b[0]=&d1; b[1]=&b1; b[2]=&d2; konverzije Derived* u Base* b[3]=&d3; b[4]=&b2; d2.bi=77; f(b,2); ispisaæe se 77 }
// b se // Base** //
//
∗
Kako je objekat izvedene klase jedna vrsta objekta osnovne klase, C++ dozvoljava implicitnu konverziju pokazivača Derived* u Base* (prethodni primer). Zbog logičkog pravila da niz objekata izvedene klase nije jedna vrsta niza objekata osnovne klase, a kako se nizovi ispravno realizuju pomoću nizova pokazivača, C++ ne dozvoljava implicitnu konverziju pokazivača Derived** (u koji se može konvertovati tip niza pokazivača na objekte izvedene klase) u Base** (u koji se može konvertovati tip niza pokazivača na objekte osnovne klase). Za prethodni primer nije dozvoljeno: void main () { Derived *d[5]; // d je tipa Derived** //... f(d,2); // nije dozvoljena konverzija Derived** u Base** }
Apstraktne klase ∗
Čest je slučaj da neka osnovna klasa nema ni jedan konkretan primerak (objekat), već samo predstavlja generalizaciju izvedenih klasa. ∗ Na primer, svi izlazni, znakovno orijentisani uređaji računara imaju funkciju za ispis jednog znaka, ali se u osnovnoj klasi izlaznog uređaja ne može definisati način ispisa tog znaka, već je to specifično za svaki uređaj posebno. Ili, ako iz osnovne klase osoba izvedemo dve klase muškaraca i žena, onda klasa osoba ne može imati primerke, jer ne postoji osoba koja nije ni muškog ni ženskog pola. ∗ Klasa koja nema instance (objekte), već su iz nje samo izvedene druge klase, naziva se apstraktna klasa (engl. abstract class). ∗ U jeziku C++, apstraktna klasa sadrži bar jednu virtuelnu funkciju članicu koja je u njoj samo deklarisana, ali ne i definisana. Definicije te funkcije daće izvedene klase. Ovakva virtuelna funkcija naziva se čistom virtuelnom funkcijom. Njena deklaracija u osnovnoj klasi završava se sa =0:
Skripta za Programiranje u Realnom Vremenu
109
Programiranje u Realnom Vremenu
class OCharDevice { //... public: virtual int put (char) =0; // èista virtuelna funkcija //... };
∗
Apstraktna klasa je klasa koja sadrži bar jednu čistu virtuelnu funkciju. Ovakva klasa ne može imati instance, već se iz nje izvode druge klase. Ako se u izvedenoj klasi ne navede definicija neke čiste virtuelne funkcije iz osnovne klase, i ova izvedena klasa je takođe apstraktna. ∗ Mogu da se formiraju pokazivači i reference na apstraktnu klasu, ali oni ukazuju na objekte izvedenih konkretnih (neapstraktnih) klasa.
Višestruko nasleđivanje Šta je višestruko nasleđivanje? ∗
Nekad postoji potreba da izvedena klasa ima osobine više osnovnih klasa istovremeno. Tada se radi o višestrukom nasleđivanju (engl. multiple inheritance). ∗ Na primer, motocikl sa prikolicom je jedna vrsta motocikla, ali i jedna vrsta vozila sa tri točka. Pri tom, motocikl nije vrsta vozila sa tri točka, niti je vozilo sa tri točka vrsta motocikla, već su ovo dve različite klase. Klasa motocikala sa prikolicom naleđuje obe ove klase. ∗ Klasa se deklariše kao naslednik više klasa tako što se u zaglavlju deklaracije, iza znaka :, navode osnovne klase razdvojene zarezima. Ispred svake osnovne klase treba da stoji reč public. Na primer: class Derived : public Base1, public Base2, public Base3 { //... };
∗
Sva navedena pravila o nasleđenim članovima važe i ovde. Konstruktori svih osnovnih klasa se pozivaju pre konstruktora članova izvedene klase i konstruktora izvedene klase. Konstruktori osnovnih klasa se pozivaju po redosledu deklarisanja. Destruktori osnovnih klasa se izvršavaju na kraju, posle destruktora osnovne klase i destruktora članova.
Virtuelne osnovne klase ∗
Posmatrajmo sledeći primer:
class B {/*...*/}; class X : public B {/*...*/}; class Y : public B {/*...*/}; class Z : public X, public Y {/*...*/};
∗
U ovom primeru klase X i Y nasleđuju klasu B, a klasa Z klase X i Y. Klasa Z ima sve što imaju X i Y. Kako svaka od klasa X i Y ima po jedan primerak članova klase B, to će klasa Z imati dva skupa članova klase B. Njih je moguće razlikovati pomoću operatora :: (npr. z.X::i ili z.Y::i).
Skripta za Programiranje u Realnom Vremenu
110
Programiranje u Realnom Vremenu
∗
Ako ovo nije potrebno, klasu B treba deklarisati kao virtuelnu osnovnu klasu:
class B {/*...*/}; class X : virtual public B {/*...*/}; class Y : virtual public B {/*...*/}; class Z : public X, public Y {/*...*/};
∗ ∗
Sada klasa Z ima samo jedan skup članova klase B. Ako neka izvedena klasa ima virtuelne i nevirtuelne osnovne klase, onda se konstruktori virtuelnih osnovnih klasa pozivaju pre konstruktora nevirtuelnih osnovnih klasa, po redosledu deklarisanja. Svi konstruktori osnovnih klasa se, naravno, pozivaju pre konstruktora članova i konstruktora izvedene klase.
Privatno i zaštićeno izvođenje Šta je privatno i zaštićeno izvođenje? ∗
Ključna reč public u zaglavlju deklaracije izvedene klase značila je da je osnovna klasa javna, odnosno da su svi javni članovi osnovne klase ujedno i javni članovi izvedene klase. Privatni članovi osnovne klase nisu dostupni izvedenoj klasi, a zaštićeni članovi osnovne klase ostaju zaštićeni i u izvedenoj klasi. Ovakvo izvođenje se u jeziku C++ naziva još i javno izvođenje. ∗ Moguće je u zaglavlje deklaracije, ispred imena osnovne klase, umesto reči public staviti reč private, što se i podrazumeva ako se ne navede ništa drugo. U ovom slučaju javni i zaštićeni članovi osnovne klase postaju privatni članovi izvedene klase. Ovakvo izvođenje se u jeziku C++ naziva privatno izvođenje. ∗ Moguće je u zaglavlje deklaracije ispred imena osnovne klase staviti reč protected. Tada javni i zaštićeni članovi osnovne klase postaju zaštićeni članovi izvedene klase. Ovakvo izvođenje se u jeziku C++ naziva zaštićeno izvođenje. ∗ U svakom slučaju, privatni članovi osnovne klase nisu dostupni izvedenoj klasi. Ona može samo nadalje "sakriti" zaštićene i javne članove osnovne klase izborom načina izvođenja. ∗ U slučaju privatnog i zaštićenog izvođenja, kada izvedena klasa smanjuje nivo prava pristupa do javnih i zaštićenih članova osnovne klase, može se ovaj nivo vratiti na početni eksplicitnim navođenjem deklaracije javnog ili zaštićenog člana osnovne klase u javnom ili zaštićenom delu izvedene klase. U svakom slučaju, izvedena klasa ne može povećati nivo vidljivosti člana osnovne klase.
Skripta za Programiranje u Realnom Vremenu
111
Programiranje u Realnom Vremenu
class Base { int bpriv; protected: int bprot; public: int bpub; }; class PrivDerived : Base { // privatno izvoðenje protected: Base::bpr ot; // vraæanje na nivo protected public: PrivDeriv ed () { bprot=2 ; bpub=3; // može se pristupiti } }; class ProtDerived : protected Base { // zaštiæeno izvoðenje public: //. .. }; void main () { PrivDeriv ed pd; pd.bpub=0 ; // greška: bpub nije javni èlan }
∗
Pokazivač na izvedenu klasu može se implicitno konvertovati u pokazivač na javnu osnovnu klasu. Pokazivač na izvedenu klasu može se implicitno konvertovati u pokazivač na privatnu osnovnu klasu samo unutar izvedene klase, jer samo se unutar nje zna da je ona izvedena. Isto važi i za reference.
Skripta za Programiranje u Realnom Vremenu
112
Programiranje u Realnom Vremenu
Semantička razlika između privatnog i javnog izvođenja ∗
Javno izvođenje realizuje koncept nasleđivanja, koji je iskazan relacijom "B je jedna vrsta A" (a-kind-of). Ova relacija podrazumeva da izvedena klasa ima sve što i osnovna, što znači da je sve što je dostupno korisniku osnovne klase, dostupno i korisniku izvedene klase. U jeziku C++ to znači da javni članovi osnovne klase treba da budu javni i u izvedenoj klasi. ∗ Privatno izvođenje ne odslikava ovu relaciju, jer korisnik izvedene klase ne može da pristupi onome čemu je mogao pristupiti u osnovnoj klasi. Javnim članovima osnovne klase mogu pristupiti samo funkcije članice izvedene klase, što znači da izvedena klasa u sebi sakriva osnovnu klasu. Zato privatno izvođenje realizuje jednu sasvim drugu relaciju, relaciju "A je deo od B" (a-part-of). Ovo je suštinski različito od relacije nasleđivanja. ∗ Pošto privatno izvođenje realizuje relaciju "A je deo od B", ono je semantički ekvivalentno sa implementacijom kada klasa B sadrži člana koji je tipa A. ∗ Prilikom projektovanja, treba strogo voditi računa o tome u kojoj su od ove dve relacije neke dve uočene klase. U zavisnosti od toga treba izabrati način izvođenja. ∗ Ako je relacija između dve klase "A je deo od B", izbor između privatnog izvođenja i članstva zavisi od manje važnih detalja: da li je potrebno redefinisati virtuelne funkcije klase A, da li je unutar klase B potrebno konvertovati pokazivače, da li klasa B treba da sadrži jedan ili više primeraka klase A i slično [FAQ]. Zadaci: 11. U klasu časovnika iz zadatka 12, dodati jednu čistu virtuelnu funkciju getTime koja vraća niz znakova. Iz ove apstraktne klase, izvesti klase koje predstavljaju časovnike koji prikazuju vreme u jednom od formata (23:50, 23.50, 11:50 pm, 11:50), tako što će imati definisanu funkciju getTime, koja vraća niz znakova koji predstavlja tekuće vreme u odgovarajućem formatu. Definisati i globalnu funkciju za ispis vremena časovnika na standardni izlaz (cout), koja koristi virtuelnu funkciju getTime. U glavnom programu kreirati nekoliko objekata pojedinih vrsta časovnika, postavljati njihova vremena, i ispisivati ih. 13. Skicirati klasu Screen koja ima operacije za brisanje ekrana, ispis jednog znaka na odgovarajuću poziciju na ekranu, i ispis niza znakova u oblast definisanu pravougaonikom na ekranu (redom red po red). Ukoliko postoji mogućnost, realizovati ovu klasu za postojeće tekstualno okruženje. Koristeći ovu klasu, realizovati klasu Window koja predstavlja prozor, kao izvedenu klasu klase View iz zadatka 14. Prozor treba da ima mogućnosti pomeranja, promene veličine, minimizacije, maksimizacije, kao i kreiranja (otvaranja) i uništavanja (zatvaranja). Definisati i virtuelnu funkciju draw. Svi prozori treba da budu uvezani u listu, po redosledu kreiranja. U glavnom programu kreirati nekoliko prozora, i vršiti operacije nad njima. 15. Realizovati klasu za jednostavnu kontrolu tastature. Ova klasa treba da ima jednu funkciju run koja će neprekidno izvršavati petlju, sve dok se ne pritisne taster za izlaz Alt-X. Ukoliko se pritisne taster F3, ova funkcija treba da kreira jedan dinamički objekat klase Window iz prethodnog zadatka. Ukoliko se pritisne taster F6, ova funkcija treba da prebaci fokus na sledeći prozor u listi prozora po redosledu kreiranja. Ukoliko se pritisne taster Alt-F3, prozor koji ima fokus treba da se zatvori. Ukoliko se pritisne neki drugi taster, ova funkcija treba da pozove čistu virtuelnu funkciju handleEvent klase View, koju treba dodati. Ovoj funkciji se prosleđuje posebna struktura podataka koja u sebi sadrži informaciju da se radi o događaju pritiska na taster, i kôd tastera koji je pritisnut. U klasi Window treba definisati funkciju handleEvent, tako da odgovara na tastere F5 (smanjenje prozora na minimum) i Shift-F5 (maksimizacija prozora). Glavni program treba da formira jedan objekat klase za kontrolu tastature, i da pozove njegovu funkciju run. 16. Skicirati klasu koja će predstavljati apstrakciju svih izveštaja koji se mogu javiti u nekoj aplikaciji. Izveštaj treba da bude interno predstavljen kao niz objekata klase Entity. Klasa Entity će predstavljati apstrakciju svih entiteta koji se mogu naći u nekom izveštaju (tekst, slika, kontrolni znaci, fajl, okviri, itd.). Ova klasa Entity ima čistu virtuelnu funkciju draw za iscrtavanje na ekranu, na odgovarajućoj poziciji, funkciju print za izlaz na štampač, i funkciju koja daje dimenzije entiteta u nekim jedinicama. Klasa izveštaja treba da ima funkciju draw za iscrtavanje izveštaja na ekranu, na poziciji koja je tekuća, funkciju za zadavanje tekuće pozicije izveštaja na ekranu, i funkciju print za štampanje izveštaja. Klasa Entity ima i funkciju doubleClick koja treba služi kao akcija na dupli
Skripta za Programiranje u Realnom Vremenu
113
Programiranje u Realnom Vremenu klik miša, kojim korisnik "ulazi" u dati entitet. Klasa izveštaja ima funkciju doubleClick, sa argumetima koji daju koordinate duplog klika. Ova funkcija treba da pronađe entitet na koji se odnosi klik i da pozove njegovu funkciju doubleClick. Skicirati klasu Entity, a u klasi izveštaja realizovati funkcije draw, print, doubleClick, i funkciju za zadavanje tekuće pozicije, kao i sve potrebne ostale pomoćne funkcije (konstruktore i destruktor).
Osnovi objektnog modelovanja Apstraktni tipovi podataka ∗
Apstraktni tipovi podataka su realizacije struktura podataka sa pridruženim protokolima (operacijama i definisanim načinom i redosledom pozivanja tih operacija). Na primer, red (engl. queue) je struktura elemenata koja ima operacije stavljanja i uzimanja elemenata u strukturu, pri čemu se elementi uzimaju po istom redosledu po kom su stavljeni. ∗ Kada se realizuju strukture podataka (apstraktni tipovi podataka), najčešće nije bitno koji je tip elementa strukture, već samo skup operacija. Načini realizacija tih operacija ne zavise od tipa elementa, već samo od tipa strukture. ∗ Za realizaciju apstraktnih tipova podataka kod kojih tip nije bitan, u jeziku C++ postoje šabloni (engl. templates). Šablon klase predstavlja definiciju čitavog skupa klasa koje se razlikuju samo po tipu elementa i eventualno po dimenzijama. Šabloni klasa se ponekad nazivaju i generičkim klasama. ∗ Konkretna klasa generisana iz šablona dobija se navođenjem stvarnog tipa elementa. ∗ Formalni argumenti šablona zadaju se u zaglavlju šablona: template class Queue { public: Queue (); ~Queue (); void put (const T&); T get (); //... };
∗
Konkretna generisana klasa dobija se samo navođenjem imena šablona, uz definisanje stvarnih argumenata šablona. Stvarni argumenti šablona su tipovi i eventualno celobrojne dimenzije. Konkretna klasa se generiše na mestu navođenja, u fazi prevođenja. Na primer, red događaja može se kreirati na sledeći način: class Event; Queue<Event *> que; que.put(e); if (que.get()>isUrgent() ) ...
∗
Generisanje je samo stvar automatskog generisanja parametrizovanog koda istog oblika, a nema nikakve veze sa izvršavanjem. Generisane klase su kao i obične klase i nemaju nikakve međusobne veze.
Skripta za Programiranje u Realnom Vremenu
114
Programiranje u Realnom Vremenu
Projektovanje apstraktnih tipova podataka ∗
Apstraktni tipovi podataka (strukture podataka) su veoma često korišćeni elementi svakog programa. Projektovanje biblioteke klasa koje realizuju standardne strukture podataka je veoma delikatan posao. Ovde će biti prikazana konstrukcija dve česte linearne strukture podataka: 1. Kolekcija (engl. collection) je linearna, neuređena struktura elemenata koja ima samo operacije stavljanja elementa i izbacivanja datog elementa iz strukture. Redosled elemenata nije bitan, a elementi se mogu i ponavljati. 2. Red (engl. queue) je linearna, uređena struktura elemenata. Elementi su uređeni po redosledu stavljanja. Operacija uzimanja vraća element koji je najdavnije stavljen u strukturu. ∗ Važan koncept pridružen strukturama je pojam iteratora (engl. iterator). Iterator je objekat pridružen linearnoj strukturi koji služi za pristup redom elementima strukture. Iterator ima operacije za postavljanje na početak strukture, za pomeranje na sledeći element strukture, za pristup do tekućeg elementa na koji ukazuje i operaciju za ispitivanje da li je došao do kraja strukture. Za svaku strukturu može se kreirati proizvoljno mnogo objekata-iteratora i svaki od njih pamti svoju poziciju. ∗ Kod realizacije biblioteke klasa za strukture podataka bitno je razlikovati protokol strukture koji definiše njenu semantiku, od njene implementacije. ∗ Protokol strukture određuje značenje njenih operacija, potreban način ili redosled pozivanja itd. ∗ Implementacija se odnosi na način smeštanja elemenata u memoriju, organizaciju njihove veze itd. Važan element implementacije je da li je ona ograničena ili nije. Ograničena realizacija se oslanja na statički dimenzionisani niz elemenata, dok se neograničena realizacija odnosi na dinamičku strukturu (tipično listu). ∗ Na primer, protokol reda izgleda otprilike ovako: ∗ Da bi se korisniku obezbedile obe realizacije (ograničena i neograničena), postoje dve template izvedene klase ograničenu (engl. bounded) realizaciju, a druga neograničenu (engl. unbounded). Na primer: Queue { ∗class Treba obratiti pažnju na način kreiranja iteratora. Korisniku je dovoljan samo opšti, zajednički public: template konkretnom sa virtual izvedenom klasom reda. Zato je definisana osnovna apstraktna klasa iteratora, iz koje su class QueueB : public izvedene klase za iteratore vezane za dve posebne realizacije reda: IteratorQueue* Queue { ∗createIterator() Izvedene klase reda kreiraće posebne, njima specifične iteratore koji se uklapaju u zajednički public: const =0; template QueueB {} virtual() void class QueueB (const put (const T&) IteratorQueue { Queue&); =0; public: virtual T ~QueueB () {} virtual get () =0; virtual Queue& operator= virtual void ~IteratorQueue () (const Queue&); clear () =0; {} virtual virtual const virtual void IteratorQueue* T& first () reset() =0; createIterator() const; const =0; virtual int virtual int next () =0; virtual void put isEmpty () const (const T& t); =0; virtual int virtual () virtual T int get isDone() const ; isFull () const =0; virtual void clear () =0; virtual const ; virtual int T* currentItem() length () const const =0; virtual const T& first =0; ()virtual const; int }; virtual(const int location isEmpty const; T&) const() =0; virtual int isFull () const; }; virtual int length () const; virtual int location (const T& t) const; 115 Skripta za Programiranje u Realnom Vremenu };
Programiranje u Realnom Vremenu
∗
Sama realizacija ograničene i neograničene strukture oslanja se na dve klase koje imaju sledeće interfejse:
Skripta za Programiranje u Realnom Vremenu
116
Programiranje u Realnom Vremenu
template class Unbounded { public: Unbounded (); Unbounded (const Unbounded&); ~Unbounded (); Unbounded& operator= (const Unbounded&); void append (const T&); void insert (const T&, int at=0); void remove (const T&); void remove (int at=0); void clear (); int isEmpty () ∗const;Definisana kolekcija se može koristiti na primer na sledeći način: int Promena isFull class Event dovoljno je promeniti samo: int Bounded length class { ∗{public: Kompletan kôd izgleda ovako: ()//... const; typedef QueueU<Event*> };const T& first EventQueue; ()Bounded const; (); const T& last Bounded (const typedef () const; Bounded&); QueueB<Event const itemAt ~Bounded *,MAXEV>T&(); (int at) const; EventQueue; T& itemAt Bounded& typedef (int at); operator= (const IteratorQueu int Bounded&); e<Event*> location Iterator;(const T&) const; void append (const T&); //... }; void insert (const T&, EventQueue int que;at=0); void remove (const que.put(e); T&); void remove (int Iterator* at=0); it=quevoid clear (); >createItera tor(); int for (; !it-isEmpty () const; >isDone(); int isFull () it->next()) const; itint length () >currentItem const; ()const T& first () >handle(); const; delete it; const T& last () const; const T& itemAt (int at) const; T& itemAt (int at); 117 int location Skripta za Programiranje u Realnom Vremenu (const T&) const; };
Programiranje u Realnom Vremenu
∗
Datoteka unbound.h:
template struct Element { T t; Element *prev, *next; Element (const templateElement (const void T&, Element* Unbounded::re next); move Element (const (Element* e) T&, Element* { prev, Element* if (e==0) next); return; }; if (e->next! =0) e->next>prev=e->prev; if (e->prev! =0) e->prevtemplate >next=e->next; Element::Eleme head=entelse (const T& e) : >next; t(e), prev(0), delete{} e; next(0) size--; } template Element::Eleme nt (const T& e, template *n) T> : t(e), void prev(0), next(n) Unbounded::co { pyif (const (n!=0) nUnbounded& r) >prev=this; { } size=0; for (Element* template cur=r.head; cur! Element::Eleme =0; cur=curnt (const T& e, >next) Element *p, append(cur->t); Element *n) } : t(e), prev(p), next(n) { template >prev=this; void if (p!=0) pUnbounded::cl >next=this; ear () { } for (Element *cur=head, *temp=0; cur!=0; cur=temp) { temp=cur>next; delete cur; } Skripta za Programiranje u Realnom Vremenu head=0; size=0; }
118
Programiranje u Realnom Vremenu
template int template::is T> Empty T& () const { const return Unbounded::it size==0; emAt (int}at) const { static T templateif (isEmpty()) int return Unbounded::is except; // Full () const Exception! { return 0; } if (at>=length()) at=length()-1; if (at<0) templateint i=0; int for Unbounded::le (Element ngth () const *cur=head; inext, i++); return cur->t; template const T& Unbounded::fi template { return T& itemAt(0); } Unbounded::it emAt (int at) { static T templateif (isEmpty()) const T& return Unbounded::la except; // st () const Exception! { if return itemAt(length()(at>=length()) 1); } at=length()-1; if (at<0) at=0; int i=0; for (Element *cur=head; inext, i++); return cur->t; } template int Unbounded::lo cation (const T& e) const { int i=0; for (Element *cur=head; cur! =0; cur=cur>next, i++) if (curSkripta za Programiranje u Realnom Vremenu >t==e) return i; return -1; }
119
template void Unbounded::ap pend (const T& t) { if (head==0) head=new Element(t); else { for (Element *cur=head; cur>next!=0; cur=cur->next); new Element(t,cur ,0); } size++; }
Programiranje u Realnom Vremenu
template void Unbounded::in sert (const T& t, int at) { if ((at>size)|| (at<0)) return; if (at==0) head=new Element(t,hea d); else if (at==size) append(t); else { int i=0; for (Element *cur=head; inext, i++); new Element(t,cur ->prev,cur); } size++; } template void Unbounded::re move (int at) { if ((at>=size)|| (at<0)) return; int i=0; for (Element *cur=head; inext, i++); remove(cur); } template Skripta za Programiranje u Realnom Vremenu void Unbounded::re move (const T& t) {
120
Programiranje u Realnom Vremenu
template Unbounded::Un bounded () : size(0), head(0) {} template Unbounded::Un bounded (const Unbounded& r) : size(0), head(0) { copy(r); } template Unbounded& Unbounded::op erator= (const Unbounded& r) { clear(); copy(r); return *this; } template Unbounded::~U nbounded () { clear(); }
Skripta za Programiranje u Realnom Vremenu
121
Programiranje u Realnom Vremenu
Skripta za Programiranje u Realnom Vremenu
122
Programiranje u Realnom Vremenu
//////////////////////////////////////////////////////////////////// / // class template IteratorUnbounded //////////////////////////////////////////////////////////////////// / template class IteratorUnbounded { public: IteratorUnbounded (const Unbounded*); IteratorUnbounded (const IteratorUnbounded&); ~IteratorUnbounded (); IteratorUnbounded& operator= (const IteratorUnbounded&); int operator== (const IteratorUnbounded&); int operator!= (const IteratorUnbounded&); void reset(); int next (); int isDone() const; const T* currentItem() const; private: template const Unbounded* theSupplier; Element* cur; IteratorUnbounded ::IteratorUnbo }; unded (const Unbounded* ub) : theSupplier(ub), cur(theSupplier>head) {} template IteratorUnbounded ::IteratorUnbo unded (const IteratorUnbounded & r) : theSupplier(r.the Supplier), cur(r.cur) {} template IteratorUnbounded & IteratorUnbounded ::operator= (const IteratorUnbounded & r) { theSupplier=r.t heSupplier; cur=r.cur; return *this; } template Skripta za Programiranje u Realnom Vremenu IteratorUnbounded ::~IteratorUnb ounded () {}
123
Programiranje u Realnom Vremenu
template int IteratorUnbounded ::operator== (const IteratorUnbounded & r) { return (theSupplier==r.t heSupplier)&&(cur ==r.cur); } template int IteratorUnbounded ::operator!= (const IteratorUnbounded & r) { return ! (*this==r); } template void IteratorUnbounded ::reset () { cur=theSupplier ->head; } template int IteratorUnbounded ::next () { if (cur!=0) cur=cur->next; return ! isDone(); } template int IteratorUnbounded ::isDone () const { return (cur==0); } template const T* IteratorUnbounded ::currentItem () const { if (isDone()) return 0; Skripta za Programiranje u Realnom Vremenu else return &(cur->t); }
124
Programiranje u Realnom Vremenu
∗
Datoteka bound.h:
template void Bounded::copy (const Bounded& r) { size=0; for (int i=0; i const T& Bounded::first () template itemAt(0); } void Bounded::clear () { template } const T& Bounded::last () const { return T, int template int Bounded::isEmpty template size==0; } const T& Bounded::itemAt (int at) const { templatestatic T except; if (isEmpty()) return int except; // Exception! Bounded::isFull () if (at>=length()) const { return size==N; at=length()-1; } if (at<0) at=0; return dep[at]; } template int template::length N> const { return size; } T& Bounded::itemAt (int at) { static T except; if (isEmpty()) return except; // Exception! if (at>=length()) at=length()-1; if (at<0) at=0; return dep[at]; } template int Bounded::location (const T& e) const { for (int i=0; i<size; i++) if (dep[i]==e) Skripta za Programiranje u Realnom Vremenu return i; return -1; }
125
Programiranje u Realnom Vremenu
template void Bounded::append (const T& t) { if (isFull()) return; dep[size++]=t; } template void Bounded::insert (const T& t, int at) { if (isFull()) return; if ((at>size)|| (at<0)) return; for (int i=size-1; i>=at; i--) dep[i+1]=dep[i]; dep[at]=t; size++; } template void Bounded::remove (int at) { if ((at>=size)|| (at<0)) return; for (int i=at+1; i<size; i++) dep[i1]=dep[i]; size--; } template void Bounded::Bounded Bounded::remove () : size(0) {} (const T& t) { remove(location(t)); } template Bounded::Bounded (const Bounded& r) : size(0) { copy(r); } template Bounded& Bounded::operator= (const Bounded& r) { clear(); copy(r); return *this; } template Bounded::~Bounded () { clear(); }
126
Programiranje u Realnom Vremenu
//////////////////////////////////////////////////////////////////// / // class template IteratorBounded //////////////////////////////////////////////////////////////////// / template class IteratorBounded { public: IteratorBounded (const Bounded*); IteratorBounded (const IteratorBounded&); ~IteratorBounded (); IteratorBounded& operator= (const IteratorBounded&); int operator== (const IteratorBounded&); int operator!= (const IteratorBounded&); void reset(); int next (); int isDone() const; const T* currentItem() const; private: const Bounded* theSupplier; int cur; };
Skripta za Programiranje u Realnom Vremenu
127
Programiranje u Realnom Vremenu
template IteratorBounded::It eratorBounded (const Bounded* b) : theSupplier(b), cur(0) {} template IteratorBounded::It eratorBounded (const IteratorBounded& r) : theSupplier(r.theSupplie r), cur(r.cur) {} template IteratorBounded& IteratorBounded::op erator= (const IteratorBounded& r) { theSupplier=r.theSuppl ier; cur=r.cur; return *this; } template IteratorBounded::~I teratorBounded () {}
template int IteratorBounded::op erator== (const IteratorBounded& r) { return (theSupplier==r.theSuppl ier)&&(cur==r.cur); } template int IteratorBounded::op erator!= (const IteratorBounded& r) { return !(*this==r); }
Skripta za Programiranje u Realnom Vremenu
128
Programiranje u Realnom Vremenu
template void IteratorBounded::re set () { cur=0; } template int IteratorBounded::ne xt () { if (!isDone()) cur++; return !isDone(); } template int IteratorBounded::is Done () const { return (cur>=theSupplier>length()); } template const T* IteratorBounded::cu rrentItem () const { if (isDone()) return 0; else return &theSupplier>itemAt(cur); }
Skripta za Programiranje u Realnom Vremenu
129
Programiranje u Realnom Vremenu
∗
Datoteka collect.h:
//////////////////////////////////////////////////////////////////// / // class template IteratorCollection //////////////////////////////////////////////////////////////////// / template class IteratorCollection { public: virtual ~IteratorCollection () {} virtual void reset() =0; virtual int next () =0; virtual int isDone() const =0; virtual const T* currentItem() const =0; };
template void Collection::c opy (const Collection& r) { for (IteratorCollect ion* it=r.createItera tor(); !it>isDone(); it>next()) if (! isFull()) add(*it>currentItem()); delete it; } template Collection& Collection::o perator= (const Collection& r) { clear(); copy(r); return *this; }
Skripta za Programiranje u Realnom Vremenu
130
Programiranje u Realnom Vremenu
//////////////////////////////////////////////////////////////////// / // class template CollectionB //////////////////////////////////////////////////////////////////// / template class CollectionB : public Collection { public: CollectionB () {} CollectionB (const Collection&); virtual ~CollectionB () {} Collection& operator= (const Collection&); virtual IteratorCollection* createIterator() const; virtual virtual virtual virtual
void void void void
add remove remove clear
virtual int rep.isEmpty(); } virtual int rep.isFull(); } virtual int rep.length(); } virtual int rep.location(t); }
(const T& t) (const T& t) (int at) ()
{ { { {
rep.append(t); } rep.remove(t); } rep.remove(at); } rep.clear(); }
isEmpty
() const
{ return
isFull
() const
{ return
length
() const
{ return
location (const T& t) const { return
private: friend class IteratorCollectionB; Bounded rep; };
//////////////////////////////////////////////////////////////////// / // class template IteratorCollectionB //////////////////////////////////////////////////////////////////// / template class IteratorCollectionB : public IteratorCollection, private IteratorBounded { public: IteratorCollectionB (const CollectionB* c) : IteratorBounded(&c->rep) {} virtual ~IteratorCollectionB () {} virtual void reset() { IteratorBounded::reset(); } virtual int next () { return IteratorBounded::next(); } virtual int isDone() const { return IteratorBounded::isDone(); } virtual const T* currentItem() const { return IteratorBounded::currentItem(); } };
Skripta za Programiranje u Realnom Vremenu
131
Programiranje u Realnom Vremenu
template CollectionB::Colle ctionB (const Collection& r) { copy(r); } template Collection& CollectionB::opera tor= (const Collection& r) { return Collection::operator =(r); } template IteratorCollection* CollectionB::creat eIterator() const { return new IteratorCollectionB(this); }
Skripta za Programiranje u Realnom Vremenu
132
Programiranje u Realnom Vremenu
//////////////////////////////////////////////////////////////////// / // class template CollectionU //////////////////////////////////////////////////////////////////// / template class CollectionU : public Collection { public: CollectionU () {} CollectionU (const Collection&); virtual ~CollectionU () {} Collection& operator= (const Collection&); virtual IteratorCollection* createIterator() const; virtual virtual virtual virtual
void void void void
add remove remove clear
(const T& t) (const T& t) (int at) ()
{ { { {
rep.append(t); } rep.remove(t); } rep.remove(at); } rep.clear(); }
virtual int isEmpty () const { return rep.isEmpty(); } virtual int isFull () const { return rep.isFull(); } virtual int length () const { return rep.length(); } virtual int location (const T& t) const { return //////////////////////////////////////////////////////////////////// rep.location(t); } / // class template IteratorCollectionU private: //////////////////////////////////////////////////////////////////// / friend class IteratorCollectionU; Unbounded