Hur hanterar man schemaläggning av beroende och oberoende, periodiska och aperiodiska uppgifter i realtidssystem?

Schemaläggning i realtidssystem kompliceras markant när uppgifter har beroenden mellan varandra eller när de anländer aperiodiskt. När uppgifter är beroende av varandra i ett periodiskt system blir planeringen snabbt ett NP-komplett problem. För små uppgiftsmängder kan ingenjörer försöka skapa schemat manuellt. Ett alternativ är att implementera dynamiska varianter av existerande algoritmer, som exempelvis EDF (Earliest Deadline First), som enkelt kan anpassas för dynamisk schemaläggning inom operativsystemet. Men det finns inga garantier för att deadlines kommer att uppfyllas när beroenden förekommer. Det enda som återstår är att använda simuleringar och emuleringar för att undersöka om algoritmen fungerar under specifika scenarier – en metod som saknar formella bevis för allmängiltighet.

När uppgifter är oberoende men aperiodiska, det vill säga att deras ankomsttid inte är känd i förväg, måste systemet använda dynamisk schemaläggning. Två algoritmer används främst: dynamisk EDF och Least Laxity (LL). Den dynamiska EDF fungerar som den statiska, men med en kö som uppdateras i realtid. Varje ny uppgift får sin deadline beräknad och placeras i kön efter deadline. Om uppgiftens deadline är tidigare än den pågående uppgiftens, avbryts den aktuella och den nya påbörjas. Om inte, infogas den nya i korrekt ordning. När en uppgift är klar, tas den bort och nästa i kön startas.

LL-algoritmen prioriterar uppgifter efter deras "slacktid" eller laxitet – skillnaden mellan deadline och återstående exekveringstid. Laxiteten för alla uppgifter, utom den som exekveras, minskar varje tidssteg. Därför kräver LL konstant omräkning av laxiteten för varje uppgift i kön. Om en annan uppgift får lägre laxitet än den som exekveras, avbryts den pågående och den andra startas. Exempelvis: vid tidpunkt n har T1 kvar 1 exekveringsenhet och deadline n+4, medan T2 har 3 kvar och deadline n+5. Deras laxitet är 3 respektive 2, så T2 körs. Men efter två steg minskar T1:s laxitet och blir lägre än T2:s. T1 får då prioritet. Utan avbrott hade T1 kanske missat sin deadline på grund av processorns overhead. LL undviker detta genom att ge förtur åt uppgifter med minst slacktid.

Vid aperiodiska beroende uppgifter blir komplexiteten ännu större. Varje uppgift har en individuell deadline, men också implicita beroenden av föregående uppgifter. En uppgift j kan inte börja förrän alla uppgifter som j beror på är klara. Om T11 exempelvis beror direkt eller indirekt på T1 till T10, måste alla dessa slutföras i tid för att T11 ska hinna exekvera innan sin deadline. Liknande gäller för T10, som i sin tur beror på T3, T4, T7 och T8.

Sådana beroenden modelleras som ett beroendegraf. De enklaste teknikerna för schemaläggning i dessa fall är ASAP (as-soon-as-possible) och ALAP (as-late-as-possible). ASAP bygger ett träd från oberoende till beroende noder, och tilldelar starttider så tidigt som möjligt. ALAP gör motsatsen – den räknar bakåt från uppgifter som inte påverkar andra, till de som är beroenden. ASAP motsvarar en traversal från löv till rot i beroendeträdet, ALAP motsvarar rot-till-löv.

Det som är viktigt att förstå är att schemaläggning i realtid inte bara är en fråga om att sortera uppgifter i en lista baserat på tider. Det handlar om att ta hänsyn till dynamiska förändringar, systemresurser, möjligheten till avbrott, samt interaktioner mellan beroenden som kan påverka hela uppgiftsträdet. En liten förändring i exekveringstid eller ett oväntat avbrott kan få kaskadeffekter genom hela systemet. Därför är robust simulering och analys avgörande, särskilt i system där missade deadlines innebär allvarliga konsekvenser.

Hur skapas och hanteras kommunikation i inbyggda system?

Inbyggda system, ofta osynliga i vår vardag, har en fundamental roll i att upprätthålla funktionalitet i en mängd olika applikationer. Dessa system kan kommunicera på många olika sätt beroende på deras funktion och krav. Moderna bilar är ett exempel där systemens kommunikation är en kombination av både trådbundna och trådlösa metoder. Trådbundna serielänkar mellan modulerna inuti bilen används för intern kommunikation, medan trådlösa standarder som Bluetooth möjliggör kommunikation med omvärlden. Denna flexibilitet gör att inbyggda system kan uppfylla en rad komplexa krav i ett nätverk av enheter.

En viktig del av inbyggda system är trådlösa sensornätverk (WSN), som innebär nätverk av sensornoder spridda över stora geografiska områden. Exempel på användningsområden för WSN är jordbrukssystem för bevattning och övervakning av grödor, geologiska system för jordbävningsdetektion och djurobservation. De individuella noderna i ett WSN är grundläggande inbyggda system som, även om de är enkla till sin natur, ändå är en del av ett större system. Kommunikation mellan dessa noder – eller mellan noder och en gateway eller sänka – är en avgörande aspekt som skiljer dessa system från mer grundläggande inbyggda system där ingen kommunikation sker mellan flera enheter.

Det är också viktigt att förstå att dessa nätverk inte bara handlar om fysiska anslutningar utan även om informationsflöden. För ingenjörerna bakom dessa system är det nödvändigt att ha kunskap om nätverkskoncept och vara väl förtrogna med olika kommunikationsprotokoll. Trots att ämnet nätverkskommunikation i inbyggda system kan vara ett eget specialistområde, är det här viktigt att ge en inblick i de mest relevanta begreppen som ingenjören kommer att behöva i designen och implementeringen av systemen.

När man designar ett system för meddelandeöverföring måste man börja med att bestämma vilket innehåll och format meddelandena ska ha. Detta innebär att man inte enbart ser till den information som överförs utan även till hur själva meddelandet är strukturerat. I detta skede av designprocessen, när man använder modeller som SDL (Specification and Description Language), är det avgörande att definiera de processer som kommer att kommunicera med varandra genom meddelanden. Det kan röra sig om processer som exekveras på samma plattform eller på olika fysiska enheter.

Vidare krävs en noggrann övervägning av hur systemet hanterar samtidiga processer. SDL-modeller representerar ofta parallella processer som inte använder delat minne, utan som kommunicerar via meddelanden. Detta kan leda till komplexitet i hanteringen av meddelandena, eftersom varje process måste förstå och hantera de meddelanden den tar emot i rätt kontext. Att säkerställa att alla nödvändiga parametrar och protokoll är korrekt definierade blir därför avgörande för systemets stabilitet och funktionalitet.

För att effektivt designa och implementera inbyggda system är det också viktigt att förstå de olika kommunikationsprotokollen som är vanliga i sådana system. Detta innefattar bland annat standarder för trådlös kommunikation som Zigbee, Bluetooth och Wi-Fi, men även protokoll för trådbundna system som I2C och SPI. Att välja rätt protokoll för den specifika applikationen är inte bara en fråga om hastighet och räckvidd utan också om säkerhet, strömförbrukning och tillförlitlighet.

För att ett inbyggt system ska fungera optimalt, behöver ingenjören även ta hänsyn till hur kommunikationen mellan enheter påverkar systemets övergripande prestanda. Om exempelvis ett WSN är utformat för att samla in data från flera sensorer och överföra dessa till en central server, måste nätverket vara tillräckligt robust för att hantera både stora mängder data och de specifika krav som ställs på systemet, såsom låg energiförbrukning och hög tillförlitlighet.

Förutom att förstå meddelandeformat och protokoll är det också avgörande att noggrant överväga hur systemet ska hantera fel. Vad händer om en nod inte kan skicka ett meddelande? Hur ska systemet återhämta sig från en nätverksavbrott? En noggrann planering för dessa scenarier är också en viktig del av designprocessen.