Deadline-monotonisk schemaläggning
Deadline-monotonisk prioriteringstilldelning är en prioriterad tilldelningspolicy som används med förebyggande schemaläggning med fast prioritet .
Med deadline - monotont prioriteringsuppdrag tilldelas uppgifterna prioritet enligt deras deadlines . Uppgiften med kortast deadline tilldelas högsta prioritet. Denna prioriterade tilldelningspolicy är optimal för en uppsättning periodiska eller sporadiska uppgifter som överensstämmer med följande systemmodell:
- Alla uppgifter har deadlines som är mindre än eller lika med deras lägsta inter-ankomsttider (eller perioder).
- Alla uppgifter har worst-case execution times (WCET) som är mindre än eller lika med deras deadlines.
- Alla uppgifter är oberoende och blockerar därför inte varandras exekvering (t.ex. genom att komma åt ömsesidigt uteslutande delade resurser ) .
- Ingen uppgift avbryter sig själv frivilligt.
- Det finns någon tidpunkt, kallad ett kritiskt ögonblick, där alla uppgifter blir redo att utföras samtidigt.
- Schemaläggningskostnader (växling från en uppgift till en annan) är noll.
- Alla uppgifter har noll release- jitter (tiden från det att uppgiften anländer tills den blir redo att utföras).
Om restriktion 7 hävs är monoton prioritetstilldelning "deadline minus jitter" optimal.
Om restriktion 1 hävs, vilket tillåter deadlines som är längre än perioder, kan Audsleys optimala prioritetstilldelningsalgoritm användas för att hitta den optimala prioritetstilldelningen.
Deadline monoton prioritetstilldelning är inte optimal för icke-förebyggande schemaläggning med fast prioritet.
En fast prioritetstilldelningspolicy P hänvisas till som optimal om det inte finns någon uppgiftsuppsättning som kan schemaläggas med en annan prioritetstilldelningspolicy som inte också kan schemaläggas med prioritetstilldelningspolicy P. Eller med andra ord: Deadline-monotonic priority assignment (DMPA) policy är optimal om någon processuppsättning, Q, som kan schemaläggas av prioritetsschema W, också är schemaläggningsbar av DMPA
Se även