|
|
|
|
| LEADER |
09575nam a22002177a 4500 |
| 005 |
20180503151646.0 |
| 008 |
140409s2014 ci ||||| |||| 00| 0 hrv d |
| 040 |
|
|
|a HR-ZaFER
|b hrv
|c HR-ZaFER
|e ppiak
|
| 041 |
|
|
|b eng
|
| 044 |
|
|
|a ci
|
| 080 |
|
|
|9 34103
|a 004.451.82.031.43
|j Višerazinska izgradnja. Stvarno vrijeme
|
| 100 |
|
|
|9 34092
|a Poleš, Damir
|
| 245 |
|
|
|a Multilevel scheduling in complex real-time systems:
|b doctoral thesis /
|c Damir Poleš ; mentor Leo Budin
|
| 260 |
|
|
|a Zagreb:
|b D. Poleš ; Fakultet elektrotehnike i računarstva,
|c 2014
|
| 300 |
|
|
|a 162 str.:
|b ilustr.;
|c 30 cm +
|e CD
|
| 504 |
|
|
|a bibliografija: 155-162 str.
|
| 520 |
|
|
|a Današnji računalni sustavi su dovoljno snažni za pokretanje više složenih aplikacija istovremeno. Svaka složena aplikacija sastoji se od višestrukih aktivnosti i može se podijeliti na dijelove koji su povezani s aktivnostima koje aplikacija provodi. Podjela se može izvršiti na način da svaka aktivnost obavlja specifičnu funkciju, na pr. ulazno-izlazne operacije, računanje i predstavljanje, odnosno vizualizaciju podataka. Sa stajališta aplikacija postoje različite funkcije prema kojima se aplikacije mogu podijeliti u zadatke funkcionalnih razina. S druge strane, sa stajališta izvođenja postoje različite okoline izvođenja prema kojima se aplikacija može podijeliti u zadatke funkcionalnih razina. Različite okoline izvođenja mogu predstavljati fizički različite naprave ili različite okoline izvođenja kod operacijskih sustava. Kod sustava za rad u stvarnom vremenu, sustava kod kojih je vremenska dimenzija rezultata važna koliko i sam rezultat, istovremena upotreba složenih aplikacija donosi nove mogućnosti, no i izazove. Posebni izazovi postavljaju se na raspoređivanje koje se smatra najvažnijom aktivnošću kod sustava za rad u stvarnom vremenu glede zadovoljavanja vremenskih ograničenja. Većina razvijenih pristupa raspoređivanja za rad s višestrukim istovremenim aplikacijama u stvarnom vremenu zasniva se na dvorazinskom raspoređivanju. Na višoj razini dodjele se sredstva aplikacijama, koje onda ta dodijeljena sredstva raspodjeljuju unutar aplikacija što je zadaća raspoređivača niže razine, aplikacijskih raspoređivača. Ova disertacija zastupa drugačiji pristup, podjelu aplikacija u funkcionalne zadatke koja se zasniva na različitim okolinama izvođenja te raspoređivanje po okolinama izvođenja.
U disertaciji je razvijen pristup višerazinskog raspoređivanja koji podržava raspoređivanje višestrukih složenih aplikacija za rad u stvarnom vremenu. Višerazinsko raspoređivanje zasniva se na dekompoziciji aplikacija u zadatke funkcionalne razine, funkcionalne zadatke, gdje svaki funkcionalni zadatak predstavlja jedinicu raspoređivanja, a ne aplikacija.
Razvijena su i predstavljena dva nova pristupa raspoređivanja zasnovana na modelu nepreciznog računanja, jednorazinsko i dvorazinsko raspoređivanje. Model nepreciznog računanja pruža mogućnost biranja između kvalitete rezultata i vremenskih zahtjeva računanja i kao takav samom definicijom podržava pristup dvorazinskog raspoređivanja. U modelu nepreciznog računanja svaki zadatak se dijeli na mandatorni i opcionalni podzadatak, samo mandatorni podzadatak mora se završiti na vrijeme.
Jednorazinsko raspoređivanje zasniva se na proširenju skupa obveznih podzadataka s ciljem minimiziranja ukupne težinske greške i ukupne greške. Raspoređivač se zasniva na earliest deadline first (EDF) i rate monotonic (RM) algoritmima raspoređivanja. Dvorazinsko raspoređivanje se sastoji od dva raspoređivača zasnovana na prioritetima, raspoređivač više i niže razine. Raspoređivač više razine raspoređuje mandatorne podzadatke, dok raspoređivač niže razine raspoređuje opcionalne podzadatke optimirajući pri tom cilj raspoređivanja. Raspoređivač više razine zasniva se na EDF i RM algoritmima raspoređivanja. Za analizu ponašanja pojedinih pristupa raspoređivanja, kao i njihovu usporedbu razvijeno je simulacijsko okruženje u Matlab-u. Intenzivne simulacije su se izvodile za analizu rasporedljivosti, korištenja i ukupne težinske greške za pojedine pristupe raspoređivanja, te usporedbu dvaju pristupa na osnovu istih parametara. Predložena su i područja primjene za različite algoritme raspoređivanja (EDF i RM) unutar jednorazinskog i dvorazinskog raspoređivanja te područje primjene jednorazinskog ili dvorazinskog raspoređivanja. Oba pristupa minimiziraju ukupnu težinsku i ukupnu grešku.
Nadalje, razvijeno je okruženje višerazinskog raspoređivanja za kompozitni sustav zadataka koje se zasniva na dekompoziciji zadataka u funkcionalne zadatke. Okružje višerazinskog raspoređivanja sastoji se od tri dijela: procesa dekompozicije aplikacija u funkcionalne zadatke, višerazinskog raspoređivača i analize rasporedivosti. Predstavljen je proces dekompozicije aplikacije u funkcionalne zadatke na više razina i formiranje višefunkcionalnog sustava zadataka, raspoređivanje kojeg se proučava. Razvijeni višerazinski raspoređivač sastoji se od prioritetom zasnovanih raspoređivača. Broj raspoređivača jednak je broju funkcionalnih zadataka na koje se dijeli aplikacija. Svaki raspoređivač okarakteriziran je prioritetom, politikom raspoređivanja, dostupnošću procesora i sustavom zadataka koje treba rasporediti. Za svaki od raspoređivača pretpostavljeni su EDF, RM i FIFO algoritmi raspoređivanja. Osim EDF i RM, koji su dobro poznati algoritmi raspoređivanja kod sustava za rad u stvarnom vremenu, uključen je i FIFO algoritam raspoređivanja koji nije tipičan za upotrebu kod sustava za rad u stvarnom vremenu, no pojavljuje se kod mnogih okolina izvođenja (na pr. ulazno-izlazne operacije). Rasporedivost se zasniva na funkciji dostupnosti procesora i novi je pristup. Svaka funkcijska razina okarakterizirana je funkcijom dostupnosti procesora na osnovu koje se radi analiza rasporedivosti za pojedine raspoređivače uključujući sve algoritme raspoređivanja. Predstavljena je i analiza odzivnosti kako za pojedine algoritme i raspoređivače, tako i za ukupni višefunkcionalni sustav zadataka.
U disertaciji se pretpostavlja upotreba jednoprocesorskog modela.
sustavi za rad u stvarnom vremenu, jednorazinsko raspoređivnaje, dvorazinsko raspoređivanje, višerazinsko raspoređivanje, rasporedivost, analiza odzivnosti, raspoređivači (jednorazinski, dvorazinski, višerazinski), funkcionalni zadaci, proces razlaganja zadataka, funkcija opskrbe procesora, model nepreciznog računanja.
|
| 520 |
|
|
|a Nowadays, computing systems are powerful enough to run several, complex applications concurrently each of which consists of multiple activities. A complex application can be divided in a number of parts, i.e. activities. A division can be done in a way that each activity performs specific function, e.g. I/O operation, calculation, visualization. From application point of view there are different functions according to which an application can be decomposed in the functional level tasks. On the other side, from execution point of view there are different execution environments (different devices or operating system’s execution environments) according to which an application can be decomposed in functional level tasks.
In this dissertation, we develop the multilevel scheduling approach that supports the scheduling of multiple complex applications in real-time based on their decomposition in functional level tasks, where each functional level task is considered as a scheduling entity, not an application.
We propose two new scheduling approaches based on the imprecise computation model, the one-level and the two-level scheduling. The one-level scheduling is based on the use of earliest deadline first (EDF) and rate monotonic (RM), whereas the two-level scheduling comprises two priority based schedulers, high and low level scheduler. The high level scheduler is based on the use of EDF and RM scheduling algorithms. The complexity, the response time analysis, the results of simulations and their analysis for both approaches are provided. Both approaches tend to minimize the total-weighted or total error.
Further, the multilevel scheduling is provided based on the decomposition of applications in functional level tasks. It comprises different execution environments for multi-functional level task system in a prioritized manner. In order to get multi-functional level task systems from applications the decomposition process is introduced. As the main part of multilevel execution framework responsible for the implementation of different execution environments a multilevel, priority based scheduler has been developed. Each scheduling level is characterized by its priority, scheduling algorithm, processor availability and task system workload. EDF, RM and first-in-first-out (FIFO) scheduling algorithms are supposed to be used at any scheduling level (one at time). Provided schedulability and response time analysis are based on the processor availability, i.e. processor supply function and worst-case response time analysis for each of assumed scheduling algorithms. Single preemptive processor model is assumed.
real-time systems, one-level scheduling, two-level scheduling, multilevel scheduling, schedulability, response time analysis, schedulers (one-level, two-level, multilevel), functional level tasks, task decomposition process, processor supply function, imprecise computation model.
|
| 700 |
|
|
|4 ths
|9 4006
|a Budin, Leo
|
| 942 |
|
|
|2 udc
|c D
|
| 999 |
|
|
|c 43119
|d 43119
|