Title Optimization of Schedulability and Quality of Service in Real-Time Mixed-Criticality Systems
Title (croatian) Optimizacija rasporedivosti i kvalitete usluge u sustavima za rad u stvarnom vremenu s mješovitom kritičnošču
Author Ivan Pavić
Mentor Hrvoje Džapo (mentor)
Committee member Hrvoje Džapo (član povjerenstva)
Granter University of Zagreb Faculty of Electrical Engineering and Computing (Department of Electronic Systems and Information Processing) Zagreb
Defense date and country 2021-07-16, Croatia
Scientific / art field, discipline and subdiscipline TECHNICAL SCIENCES Electrical Engineering
Scientific / art field, discipline and subdiscipline TECHNICAL SCIENCES Computing
Universal decimal classification (UDC ) 621.3 - Electrical engineering 004 - Computer science and technology. Computing. Data processing
Abstract This thesis investigates three different methods for optimization of schedulability and quality of service in real-time mixed-criticality systems. The research is motivated by requirements of safety-critical systems, typically encountered in transportation and industrial systems, which are often represented with various real-time mixed-criticality system models. The first method is focused on the schedulability testing in the adaptive mixed-criticality system model. A novel sufficient schedulability test for adaptive mixed-criticality task systems is devised, which improves the schedulability in comparison with the existing sufficient schedulability tests. Moreover, the devised test requires significantly less computing power in comparison with exhaustive exact methods. In addition, a framework for schedulability testing was devised, which ensures comprehensive and systematic experimental evaluation of the devised test as well as the validation of the existing schedulability tests. Using this framework, errors and inconsistencies in the existing schedulability tests were corrected. The results presented in the thesis consist of extensive experimental evaluation on a large number of different synthetically generated task sets as well as on small numerical examples. The second method deals with the harmonic period assignment from period ranges, which is of great importance for maintaining schedulability and quality of service in the safety-critical real-time systems. Unlike the existing harmonic period assignment methods from period ranges, the method for harmonic period assignment devised in this research is optimal, and it enables optimization of the number of different period values in the system, which is often of practical interest in real-world applications. Moreover, the devised harmonic period assignment method enables the optimization of arbitrary utilization values. The method is validated and compared to existing methods using an extensive experimental evaluation. It was shown that the usage of this method can significantly increase schedulability and quality of service in sense of utilization in systems of interest. The third method addresses the optimization of quality of service of non-critical or low-criticality tasks. The method is based on the genetic programming method, which is often used in solving various scheduling problems. In this research, the genetic programming is exploited to generate dynamic priority assignment functions for scheduling of low-criticality tasks in the adaptive mixed-criticality environment, which is typically overloaded. The extensive experimental evaluation on synthetically generated task sets demonstrates that the proposed method can generate heuristics for various system configurations, which dominate single-variable based heuristics that can be found in the literature.
Abstract (croatian) U ovoj doktorskoj disertaciji istražene su tri različite metode za optimizaciju rasporedivosti i kvalitete usluge u sustavima za rad u stvarnom vremenu s mješovitom kritičnošću. Istraživanje je motivirano zahtjevima sigurnosno kritičnih sustava koji se tipično susreću u transportnim i industrijskim sustavima, a uz to se modeliraju različitim modelima sustava za rad u stvarnom vremenu s mješovitom kritičnošću. Fokus prve metode je ispitivanje rasporedivosti u adaptivnim sustavima s mješovitom kritičnošću. U radu je razvijen novi dovoljni test rasporedivosti za adaptivne sustave s mješovitom kritičnošću koji donosi poboljšanje rasporedivosti u usporedbi s postojećim dovoljnim testovima rasporedivosti. Nadalje, razvijeni test koristi značajno manje procesorske moći u usporedbi s preciznim testovima temeljenim na iscrpnom pretraživanju. Dodatno, razvijen je i radni okvir za evaluaciju novog testa rasporedivosti te za validaciju postojećih testova rasporedivosti. Koristeći razvijeni radni okvir otkrivene su greške i nedosljednosti u postojećim testovima rasporedivosti. Rezultati prikazani u disertaciji sastoje se od ekstenzivne eksperimentalne evaluacije na velikom broju različitih sintetički generiranih skupova zadataka kao i na malim numeričkim primjerima. Druga metoda koja je razvijena je metoda za dodjelu harmonijskih perioda iz intervala perioda. Metode za dodjelu harmonijskih perioda od iznimne su važnosti za održavanje rasporedivosti i kvalitete usluge u sigurnosno kritičnim sustavima za rad u stvarnom vremenu. Za razliku od postojećih metoda za dodjelu harmonijskih perioda iz intervala perioda, metoda za dodjelu harmonijskih perioda razvijena u ovom istraživanju je optimalna i omogućuje optimizaciju broja različitih vrijednosti perioda u konačnom rješenju što je od praktičnog interesa u stvarnim aplikacijama. Štoviše, razvijena metoda za dodjelu harmonijskih perioda omogućava optimizaciju arbitrarnih faktora zauzeća procesora. Razvijena metoda je validirana i uspoređena s postojećim metodama temeljem ekstenzivne eksperimentalne evaluacije. Pokazano je da korištenje ove metode može značajno povećati rasporedivost i kvalitetu usluge u kontekstu faktora zauzeća u sustavima od interesa. Treća metoda adresira optimizaciju kvalitete usluge nekritičnih zadataka ili zadataka s niskom kritičnošću. Razvijena metoda temelji se na genetičkom programiranju koje se često koristi za rješavanje različitih problema raspoređivanja. U ovoj disertaciji, genetičko programiranje se koristi za generiranje dinamičkih funkcija za dodjelu prioriteta za raspoređivanja zadataka s niskom kritičnošću u sustavima s adaptivnom mješovitom kritičnošću koji su tipično preopterećeni. Pomoću ekstenzivne eksperimentalne evaluacije na sintetski generiranim skupovima zadataka pokazano je da predložena metoda može generirati heuristike za različite konfiguracije sustava te da je ovakav pristup bolji od jednostavnih heuristika temeljenih na jednoj varijabli koji se mogu pronaći u literaturi.
Keywords
real-time
scheduling
mixed-criticality
period assignment
genetic programming
Keywords (croatian)
stvarno vrijeme
raspoređivanje
mješovita kritičnost
dodjela perioda
genetičko programiranje
Language english
URN:NBN urn:nbn:hr:168:733547
Study programme Title: Doctoral study programme "Electrical Engineering and Computing" Study programme type: university Study level: postgraduate Academic / professional title: doktor/doktorica znanosti, po-dručje tehničkih znanosti (doktor/doktorica znanosti, po-dručje tehničkih znanosti)
Catalog URL http://lib.fer.hr/cgi-bin/koha/opac-detail.pl?biblionumber=52613
Type of resource Text
Extent 206 str.
File origin Born digital
Access conditions Open access
Terms of use
Created on 2022-04-27 11:57:03