Abstract-Real-time system innehåller allt mer processenheter med flera kärnor. För att kunna använda denna extra beräkningskraft i hårda deadline-miljöer behöver man schemaläggningstester för uppgiftsmodeller som representerar möjligheterna att parallellt utföra jobb av en uppgift. En standardmodell är att representera en (sporadiskt) återkommande uppgift med en riktad acyklisk graf (DAG). DAG:s knutpunkter motsvarar uppgifternas arbetstillfällen. Alla sådana jobb frigörs samtidigt, måste slutföras inom någon gemensam relativ deadline, och vissa par av jobb är kopplade till en företrädesbegränsning, dvs. en båge av DAG. Detta innebär nya utmaningar för att analysera om ett uppgiftssystem är genomförbart, särskilt för de vanliga online-algoritmerna Earliest Deadline First (EDF) och Deadline Monotonic (DM I detta arbete, sluter vi helt gapet mellan algoritmisk förståelse av genomförbarhetsanalys för den vanliga sporadiska uppgiftsmodellen och fallet där varje sporadisk uppgift är en DAG. Vi visar för DAG uppgifter att EDF har en snäv hastighetsbegränsning på 2 - 1/m, där m är antalet processorer, medan DM har en hastighetsbegränsning på högst 3 - 1/m. Dessutom presenterar vi polynomiska och pseudopolynomiska tidstester, av olika effektivitet, för att avgöra om en uppsättning sporadiska DAG-uppgifter kan schemaläggas av EDF eller DM för att uppfylla alla tidsfrister på ett visst antal processorer. Vi noterar att effektiviteten i vissa av våra tester matchar de mest kända algoritmerna för vanliga sporadiska uppgifter uppsättningar, vilket minskar gapet.
Bonifaci m.fl. REF utvecklade senare genomförbarhetstester för uppgiftssystem med flera DAG-uppgifter, planerade enligt G-EDF och G-DM.
Feasibility Analysis in the Sporadic DAG Task Model
{'venue': '2013 25th Euromicro Conference on Real-Time Systems', 'journal': '2013 25th Euromicro Conference on Real-Time Systems', 'mag_field_of_study': ['Computer Science']}