Vi presenterar en modell, uppgiftsautomata, för realtidssystem med icke-uniformt återkommande beräkningsuppgifter. Det är en utökad version av tidsinställd automata med asynkrona processer som är beräkningsuppgifter som genereras (eller utlöses) av tidsinställda händelser. Jämfört med klassiska aktivitetsmodeller för realtidssystem, kan task automata användas för att beskriva uppgifter (1) som genereras icke-deterministiskt enligt tidsbegränsningar i tidsinställda automata, (2) som kan ha intervallutförandetider som representerar bästa fall och värsta fall utförandetider, och (3) vars slutförandetider kan påverka utgivningen av aktivitetsfall. Vi generaliserar den klassiska uppfattningen om schedulability till uppgift automata. En aktivitetsautomaton kan schemaläggas om det finns en schemaläggningsstrategi så att alla möjliga sekvenser av händelser som genereras av automaten kan schemaläggas i den meningen att alla tillhörande uppgifter kan beräknas inom sina tidsfrister. Vårt första tekniska resultat är att schemaläggningen för en viss schemaläggningsstrategi kan kontrolleras algoritmiskt för den klass av uppgiftsautomata när det bästa fallet och det värsta fallet utförande tider av uppgifter är lika. Beviset är baserat på en decibel klass av fjädring automata: tidsinställd automata med begränsad subtraktion där klockor kan uppdateras genom subtraktioner inom en avgränsad zon. Vi kommer också att studera gränslinjen mellan fall som kan avgöras och fall som inte kan avgöras. Vårt andra tekniska resultat visar att problemet med schemaläggningskontroll kommer att vara obeslutbart om följande tre villkor gäller: (1) uppgifternas utförandetider är intervaller, (2) den exakta avslutningstiden för en aktivitetsinstans kan påverka nya aktivitetsutgåvor, och (3) en uppgift tillåts föregripa en annan köruppgift.
Vid förebyggande schemaläggning kan klockorna i aktivitetsautomata från REF uppdateras genom subtraktion, som kan ses som en typ av stoppurssimulering.
Task Automata: Schedulability, Decidability and Undecidability
{'venue': None, 'journal': None, 'mag_field_of_study': ['Computer Science']}