Srinidhi Srinivasan

Real-time systems zijn systemen waarbij de correctheid niet alleen afhangt van het produceren van een correct resultaat, maar ook van het produceren van dit resultaat binnen de benodigde tijdsgrenzen. In veel moderne systemen, waaronder veiligheids- en bedrijfskritieke toepassingen, kunnen schendingen van tijdsbeperkingen leiden tot onacceptabele gevolgen, zelfs als de onderliggende berekening correct is. Om die reden is het waarborgen van de consistente naleving van deze tijdsbeperkingen alvorens inzet van zulke systemen een fundamentele uitdaging in het ontwerp en de analyse van real-time systems.

De analyse van het timingsgedrag van deze systemen is uitdagend, omdat de uitvoering ervan kan variëren, afhankelijk van vele mogelijke scenario’s. Variabiliteit in factoren zoals taak vrijgavetijden, uitvoeringsduren, precedentierelaties tussen taken, onderbrekingsintervallen wanneer taken wachten op externe computaties of communicatie, kunnen elk leiden tot een groot aantal mogelijke uitvoeringsscenario’s, waarvan elk mogelijk een andere planning produceert, die resulteert in andere timingseigenschappen. Naarmate systemen complexer worden, groeit het aantal van deze scenario’s snel, wat redeneren over alle mogelijke uitkomsten op een systematische wijze bemoeilijkt.

Het primaire doel van dit proefschrift is het verbeteren van de analyse van timingsgedrag van realistische real-time systems. Moderne systemen omvatten veelal complex taakgedrag, waar taken uit verschillende delen met precedentierelaties kunnen bestaan of tijdelijk kunnen pauzeren, wachtende op externe handelingen. Ze hangen ook in toenemende mate af van communicatienetwerken, om data tussen verschillende delen van een systeem uit te wisselen. Samen met de toenemende schaal van zulke systemen, bemoeilijken deze factoren de analyse van tijdsbeperkingen. Om die reden introduceert dit proefschrift methodes die systematische timingsanalyse over verschillende uitdagende scenario’s mogelijk maken.

De eerste contributie van dit proefschrift is gerelateerd aan de analyse van real-time systems waarvan de taken expressief applicatieniveaugedrag vertonen. In vele werkelijke systemen kunnen taken niet simpelweg met terugkerende patronen beschreven worden: hun activaties kunnen afhangen van evenementen, interacties met andere taken of vertragingen tussen opeenvolgende uitvoeringen. Zulk gedrag verhoogt het aantal en de diversiteit van de mogelijke uitvoeringsscenario’s, wat systematische timingsanalyse bemoeilijkt. Dit proefschrift beschrijft methodes voor de analyse van timingsgedrag van real-time systems waarin taken uit meerdere delen met precedentierelaties mogen bestaan, en waarbij deze taken zichzelf mogen pauzeren, wachtende op externe handelingen. De voorgestelde technieken modelleren deze precedentierelaties en pauzeringsintervallen expliciet, en redeneren systematisch over de uitvoeringsscenario’s die voortkomen uit zulk taakgedrag.

De tweede contributie van dit proefschrift betreft de analyse van timingsgedrag in communicatienetwerken gebaseerd op Time-Sensitive Networking (TSN). Binnen deze systemen zijn de entiteiten die gepland worden netwerkberichten, in plaats van processortaken; timingsgaranties moeten behouden worden voor pakkettransmissies over communicatielinks. Het analyseren van berichtenvertraging in zulke netwerken is uitdagend, vanwege het feit dat berichtenstromen op elkaar inwerken over meerdere links, traffic-shaping mechanismes reguleren hoe pakketten vrijgegeven en verzonden worden, en dat de interne structuur van netwerkswitches beïnvloedt hoe pakketten in de wachtrij worden geplaatst en verzonden worden. Deze factoren introduceren complexe afhankelijkheden die end-to-end communicatievertragingen beïnvloeden. Om die reden onderzoekt dit proefschrift hoe communicatie timingseigenschappen binnen TSN netwerken op systematische wijze geanalyseerd kunnen worden. Deze methodes bieden analysetechnieken voor het beredeneren over hoe verschillende traffic-shaping mechanismes berichtenvertraging beïnvloeden, en ondersteunen de analyse van zowel individuele netwerkswitches, als end-to-end vertraging over hele communicatiepaden.

De derde contributie is gerelateerd aan de schaalbaarheid van timingsanalyses voor steeds complexer wordende real-time systems. Naarmate het aantal taken, bronnen van timingsvariabiliteit, en wisselwerkingen tussen systeemcomponenten groeit, kan het aantal scenario’s dat moet worden overwogen significant toenemen. Dit maakt het uitdagend om zowel grote systemen te analyseren, evenals volledige dekking van relevante planningsmogelijkheden te behouden. Daarom onderzoekt dit proefschrift technieken die schaalbare timingsanalyse mogelijk maken, waarbij correctheid behouden blijft. Deze technieken verminderen het aantal uitvoeringsscenario’s die meegenomen moeten worden, maar waarborgen toch een complete dekking van relevante planningsgedragen.

Om bovenstaande analyses mogelijk te maken, bouwt dit proefschrift voort op het Schedule Abstraction Graph (SAG) framework, geïntroduceerd in [46, 48], dat een abstractie-gebaseerde aanpak biedt voor het redeneren over planningsgedrag. Het kernidee van SAG is het representeren van de mogelijke systeemplanningen als een grafiek, die relevante uitvoeringsscenario’s vastlegt, zonder het individueel analyseren van ieder scenario. In plaats van dat elk concreet uitvoeringsscenario concreet wordt gerepresenteerd, groepeert het framework scenario’s met gelijk planningsgedrag in abstracte staten, en verkent het hun overgangen. Dit geeft de mogelijkheid tot systematische analyse van timingsgedrag over een grote verscheidenheid aan uitvoeringsscenario’s.

Gebruikmakend van deze abstractie-gebaseerde aanpak, breidt dit proefschrift de analyse uit naar taakmodellen met precedentierelaties en pauzeringsintervallen, stemt het dit framework af op het analyseren van berichtentransmissies in Time-Sensitive Networking, en ontwikkelt het technieken die de schaalbaarheid van de analyse bij grotere systemen verbeteren. Samengevat, verbeteren bovengenoemde contributies het vermogen om tijdsgedrag van realistische real-time systems te analyseren binnen verschillende uitdagende omgevingen.