Sammanfattning — Detta dokument presenterar en algoritm för offline schemaläggning av kommunikationsuppgifter med företräde och uteslutning begränsningar i distribuerade hårda realtidssystem. Uppgifter antas kommunicera via meddelandepassage baserat på ett tidsbundet kommunikationsparadigm, såsom realtidskanalen [1]. Algoritmen använder en gren-och-bunden (B&B) teknik för att söka efter ett aktivitetsschema genom att minimera maximal aktivitetsfördröjning (definierad som skillnaden mellan uppgiftsfullbordandetid och uppgiftsdeadline) och utnyttjar samspelet mellan aktivitets- och meddelandeschemaläggning för att förbättra kvaliteten på lösningen. Det genererar ett komplett schema vid varje vertex i sökträdet, och kan göras för att ge en genomförbar schema (finns innan man når en optimal lösning), eller gå vidare tills en optimal aktivitet schema finns. Vi har genomfört en omfattande simuleringsstudie för att utvärdera den föreslagna algoritmens prestanda. Algoritmen visas skala väl med avseende på systemstorlek och graden av intertask interaktioner. Det erbjuder också bra prestanda för arbetsbelastningar med ett brett utbud av CPU-användningar och applikationskonvergens. För större system och högre laster introducerar vi en girig heuristisk som är snabbare men inte har några optimala egenskaper. Vi har också utökat algoritmen till en mer allmän resursfast modell och därmed breddat dess applikationsdomän.
Algoritmen i REF är en schemaläggningsalgoritm i realtid för uppgifter med företrädesbegränsning, men den stöder inte feltolerans.
Combined Task and Message Scheduling in Distributed Real-Time Systems
{'venue': 'ICDCS', 'journal': None, 'mag_field_of_study': ['Computer Science']}