Abstract-I utformningen av distribuerade datorsystem anses schemaläggningsproblem vara ett viktigt problem och har behandlats av många forskare. De flesta strategier har dock inte hanterat uppgifternas tidsplanering och resursbehov. I detta dokument beskriver vi en uppsättning heuristiska algoritmer för att schemalägga uppgifter som har tidsfrister och resursbehov, i ett distribuerat system. Dessa algoritmer är dynamiska och fungerar på ett decentraliserat sätt. När en uppgift anländer till en nod, försöker den lokala schemaläggaren vid den noden att garantera att uppgiften kommer att slutföra genomförandet innan dess deadline, på den noden. Om försöket misslyckas samarbetar schemaläggningskomponenterna på enskilda noder för att avgöra vilken annan nod i systemet som har tillräckligt resursöverskott för att garantera uppgiften. I detta dokument utvärderas fyra algoritmer för samarbete. De skiljer sig åt när det gäller hur en nod behandlar en uppgift som inte kan garanteras lokalt. Den slumpmässiga schemaläggningsalgoritmen: Uppgiften skickas till en slumpmässigt vald nod. Den fokuserade adressalgoritmen: Uppgiften skickas till en nod som uppskattas ha tillräckligt med överskott för att slutföra uppgiften innan dess deadline. Anbudsalgoritmen: Uppgiften skickas till en nod baserad på de bud som mottagits för uppgiften från noder i systemet. Den flexibla algoritmen: Uppgiften skickas till en nod baserad på en teknik som kombinerar budgivning och fokuserad adressering. Simuleringsstudier utfördes för att jämföra dessa algoritmers prestanda i förhållande till varandra samt med avseende på två baslinjer. Den första baslinjen är den icke-kooperativa algoritmen där en uppgift som inte kan garanteras lokalt inte skickas till någon annan nod. Den andra är en (ideal) algoritm som beter sig exakt som budalgoritmen men inte ådrar sig några kommunikation overheads. I simuleringsstudierna undersöks hur kommunikationsfördröjningen, uppgiftens slapphet, belastningsskillnaderna på noderna och uppgiftsberäkningstiderna påverkar algoritmernas prestanda. Resultaten visar att distribuerad schemaläggning är effektiv även i en hård realtid miljö och att den relativa prestandan för dessa algoritmer är en funktion av systemet tillstånd.
Krithi Ramamritham m.fl. i REF beskriva en uppsättning heuristiker för att schemalägga uppgifter med tidsfrister i ett distribuerat system.
Distributed Scheduling of Tasks with Deadlines and Resource Requirements
{'venue': 'IEEE Trans. Computers', 'journal': 'IEEE Trans. Computers', 'mag_field_of_study': ['Computer Science']}