Sammanfattning I det här dokumentet presenterar vi ett exakt schematiskt test för sporadiska realtidsuppgifter som schemalagts av Global Fixed Priority Fullt förebyggande schemaläggare på ett multiprocessorsystem. Analysen består i att modellera systemet som en Linjär Hybrid Automaton, och i att utföra en nåbarhetsanalys för stater som representerar deadline miss villkor. För att mildra problemet med statsrymdexplosion föreslår vi en förordningsrelation över modellens symboliska tillstånd: tillstånd som simuleras av andra kan säkert elimineras från statsrymden. Vi formulerar också begreppet decisionability intervall med avseende på en uppsättning begränsade-deadline sporadiska uppgifter på multiprocessor. Decledability intervallet är ett begränsat tidsintervall så att om en deadline miss inträffar i schemat, då är det möjligt att hitta en konfiguration av ankomsttider för uppgifterna så att deadline miss sker inom det avgränsade intervallet. Vice versa, om ingen konfiguration av ankomsttider ger en deadline miss i det avgränsade intervallet, då är ingen deadline miss någonsin möjligt i schemat. Därför bevisar vi att problemet med schepulability analys är decledable, och vi ger en formel för att beräkna decledability intervallet. Såvitt vi vet är detta första gången ett sådant tidsintervall föreslås för sporadiska uppgifter som körs på multiprocessor. Det föreslagna Detta är en utökad version av en tidigare RTNS 2014 papper (Sun och Lipari 2014b). Schedulerbarhetsanalys har implementerats i ett programvaruverktyg. För första gången bedömer vi pessimismen i toppmoderna ungefärliga schedulability test genom experiment. Dessutom visar vi att användningen av den föreslagna modellen gör det möjligt att analysera uppgifter med mer allmänna parametervärden än andra exakta algoritmer i litteraturen. Men även med vårt tillvägagångssätt är komplexiteten fortfarande för hög för att kunna analysera praktiska uppgifter med mer än sju uppgifter.
Dessutom lyckades REF bevisa att den exakta analysen av en uppsättning sporadiska uppgifter under en G-FP schemaläggare kan beslutas inom ett begränsat tidsintervall.
A pre-order relation for exact schedulability test of sporadic tasks on multiprocessor Global Fixed-Priority scheduling
{'venue': 'Real-Time Systems', 'journal': 'Real-Time Systems', 'mag_field_of_study': ['Computer Science']}