Abstrakt. I detta papper exend timed automata med asynkrona processer d.v.s. uppgifter som utlöses av händelser som modell för realtidssystem. Modellen är tillräckligt uttrycksfull för att beskriva överensstämmelse och synkronisering, och realtidsuppgifter som kan vara periodiska, sporadiska, förebyggande eller icke förebyggande. Vi generaliserar den klassiska uppfattningen om schedulability till timed automata. En automaton kan schemaläggas om det finns en schemaläggningsstrategi så att alla möjliga sekvenser av händelser som accepteras av automaten kan schemaläggas i den meningen att alla tillhörande uppgifter kan beräknas inom sina tidsfrister. Vi tror att modellen kan fungera som en bro mellan schemaläggningsteori och automatiserade teoretiska metoder för systemmodellering och analys. Vårt främsta resultat är att problemet med kontroll av ansvarighet kan lösas. Enligt vår kunskap är detta den första allmänna decledability resultat på tät-tid modeller för realtid schemaläggning utan att anta att företräden förekommer endast vid heltal tidpunkter. Beviset är baserat på en decidable klass av updatable automata: tidsinställd automata med subtraktion där klockor kan uppdateras genom subtraktioner inom en avgränsad zon. Den avgörande iakttagelsen är att problemet med kontroll av lastbarheten kan kodas som ett problem för sådan automata. Baserat på beviset har vi utvecklat en symbolisk teknik och ett prototypverktyg för schemaläggningsanalys.
Det verkar som om beräkningsmodellen bakom förebyggande schemaläggningsstrategier är stopwatch automata, för vilken det är känt att tillgänglighetsproblemet är obeslutbart, men i REF visas att Schepulability problem för förlängd tid automatisera är decimedable för förebyggande schemaläggning strategier.
Timed automata with asynchronous processes: schedulability and decidability
{'venue': 'In Proceedings of TACAS 2002', 'journal': None, 'mag_field_of_study': ['Computer Science']}