In many embedded control systems, data is passed from sensors to actuators through chains of task, which are called cause-effect chains. Control system performance is often dependent on the end-to-end latency of these chains, and ways to modify a system in order to control and reduce this latency are vital for guaranteeing high performance. One such modification which can be made is to introduce job-level dependencies, which enforce a temporal ordering of specific task instances (jobs). An algorithm for constraining end- to-end latency using this type of dependencies was proposed in a paper by Becker et al. in 2016. This thesis seeks to extend this method to include the timing information given by rate-monotonic scheduling, and also increase its schedulability, as it sometimes produces dependencies which lead to an unschedulable task set. In this thesis, two different algorithms are proposed for doing this. The first one adds job-level dependencies to a task set in a way which reflects rate-monotonic scheduling. The second one constrains end-to-end latency of cause-effect chains by finding data propagation paths which violate their latency constraints, and forcing them to use data produced at a later time than that of the currently used data. These two methods and the original one from the 2016 paper are evaluated on task sets and cause- effect chains generated using common automotive benchmarks. Both impact on end-to-end latency and schedulability are measured. The results indicate that the algorithm which mimics rate-monotonic scheduling does reduce end- to-end latency on its own, but that this actually has a negative impact on the performance of the original latency reducing method of Becker et al. On the new latency constraining algorithm presented in this report, it instead has a positive impact. However, this new method underperforms severely in reducing latency compared to the old one from 2016, and is not a viable alternative to it.

I många inbygda reglersystem skickas data från sensorer till aktuatorer genom en kedja av tasks, i något som kan kallas dataöverföringskedja. Den maximala tiden mellan det första och sista tasket i en sådan kedja (även kallat end- to-end-latens) kan ha stor påverkan på hur väl styrningen fungerar i ett reglersystem. Därför finns ett stort behov av metoder för att modifiera den här typen av system så att end-to-end-latensen hålls under en viss nivå. Det finns olika parametrar som kan ändras för att uppnå detta, och en av dem är ordningen mellan individuella instanser av tasks (här kallade jobb). Dessa kan styras genom så kallade “beroenden mellan jobb”, som tvingar två olika jobb att alltid exekveras i en viss ordning. I en artikel av Becker et al. från 2016 presenterades en algoritm för att lägga till den här sortens beroenden i dataöverföringskedjor, för att minska deras end-to-end-latens. Målet med det här examensarbetet är att utöka denna metod så att den dels använder sig av den tidsrelaterade information som fås av rate-monoton schemaläggning, och dels tar större hänsyn till schemaläggningsbarhet. För detta presenteras här två nya algoritmer. Den första lägger till beroenden mellan jobb på ett sätt som avspeglar rate-monoton schemaläggning. Den andra minskar end-to- end-latensen i dataöverföringskedjor genom att hitta kedjor som inte klarar sina latenskrav och tvinga dem att använda data som produceras senare i tiden än den de använder i nuläget. Dessa två metoder testas och jämförs med den från 2016 på taskset och dataöverföringskedjor som genererats i enlighet med vanliga riktmärken för inbyggda system inom bilindustrin. Både schemaläggningsbarhet och minskning i latens mäts upp och jämförs. Resultaten visar att algoritmen som efterliknar rate-monoton schemaläggning delvis minskar kedjors latens på egen hand, men att den försämrar prestandan hos den gamla latensminskningsalgoritmen från Becker et al. när dessa kombineras. Vid kombination med den nya latensminskningsalgoritmen från den här rapporten blir effekten istället förbättrad, men den nya metoden är så dålig på att minska end-to-end-latens att den ändå inte är något dugligt alternativ till den från 2016.