Deadline monotonic scheduling
Hej, jag har suttit med detta problem i några dagar och jag har väldigt svårt att förstå hur jag skall lösa det. Detta är problemet:
Lösningsförslaget är väldigt förvirrande då den inte förklarar vart siffrorna kommer från. Hittills vet jag bara att prioritetsordningen kommer vara T1 > T3 > T2 pga deadline. Jag vet inte hur jag skall fortsätta härifrån.
Är du med på vad alla termer är?
Deadline verkar du begripa, hänger du med på execution time och period?
Dracaena skrev:Är du med på vad alla termer är?
Deadline verkar du begripa, hänger du med på execution time och period?
Execution time = Hur många tids enheter det tar att slutföra en uppgift
Period = inom vilken tidsram uppgiften måste slutföras
Jag tror det är såhär i alla fall, oftast brukar väl bara den maximala perioden vara mest relevant, i detta fall 14?
Jag blev rätt osäker själv på hur man skall lösa uppgiften. Bilden är rätt suddig också. Kan du ladda upp en bild på hela facit med bättre upplösning? Vi kanske kan pussla ihop det ändå om du fortfarande behöver hjälp med uppgiften.
Jag laddar upp frågan och facit här igen:
Facit:
Det som jag vet just nu är att prioritetsordningen är T1 > T3 > T2 och att den maximala tiden är 14 tidsenheter pga T3 som har den längsta perioden. Jag blev lite förvirrad på det första steget när det står att: 8/10 = 1 och sedan resterande del av lösningen hänger jag inte heller riktigt med.
Eftersom vi vil ha worst case, så måste vi ta hänsyn till att man kan släppa task T3 så att den exekverar före T2.
R2 för T2 måste du vara summan av dens egna samt alla andras tasks Exeuction time (den väntar ju):
C1+C2+C3, men om den ska hinna inom sin deadline, så måste det gälla att:
, och då har vi ett intervall på [0, 3].
Hänger du med?
Eller kanske lite mer utförligt förklarat:
vid t=0 har vi 3 tasks som kan köras.
T1 har lägst deadline och exekveras först. Detta tar 2 tidsenheter.
Nu är det T3s tur att köra. Den tar x tidsenheter.
Nu körs äntligen T2 och detta tar 4 tidsenheter.
Det har nu gått 2+x+4 tidsenheter. T1 når alltid sin deadline. Notera nu att eftersom D2 > D3 måste vi välja execution time för T3 så att det är inom deadlinen för T2. Annars kommer inte T2 att nå sin deadline.
Om T2 når sin deadline, så kommer T3 också nå sin deadline, så vi behöver inte ta hänsyn till något annat än T2.
Detta ger att exekveringstidenn för T3 kan som värst vara 3 sekunder om T2 och T3 ska hinna med sin deadline.
Dracaena skrev:Eftersom vi vil ha worst case, så måste vi ta hänsyn till att man kan släppa task T3 så att den exekverar före T2.
R2 för T2 måste du vara summan av dens egna samt alla andras tasks Exeuction time (den väntar ju):
C1+C2+C3, men om den ska hinna inom sin deadline, så måste det gälla att:
, och då har vi ett intervall på [0, 3].
Hänger du med?
Eller kanske lite mer utförligt förklarat:
vid t=0 har vi 3 tasks som kan köras.
T1 har lägst deadline och exekveras först. Detta tar 2 tidsenheter.
Nu är det T3s tur att köra. Den tar x tidsenheter.
Nu körs äntligen T2 och detta tar 4 tidsenheter.
Det har nu gått 2+x+4 tidsenheter. T1 når alltid sin deadline. Notera nu att eftersom D2 > D3 måste vi välja execution time för T3 så att det är inom deadlinen för T2. Annars kommer inte T2 att nå sin deadline.
Om T2 når sin deadline, så kommer T3 också nå sin deadline, så vi behöver inte ta hänsyn till något annat än T2.
Detta ger att exekveringstidenn för T3 kan som värst vara 3 sekunder om T2 och T3 ska hinna med sin deadline.
Du får gärna bara rätta mig så jag inte förstått fel, jag illustrerade detta genom att rita upp en tidsaxel där jag fyllde ut T1 och T2 först, sedan såg jag att det skapades ett mellanrum på 3 tidsenheter. Har jag förstått din logik rätt nu? Tänker att detta borde stämma då de uppfyller alla kraven:
Det är bara tidsaxeln här som spelar roll tänk inte på ekvationerna.
Ja, precis. Där syns det tydligt att om T3 tar längre tid än 3 tidsenheter så kommer inte T2 och T3 hinna med sin deadline.
Dracaena skrev:Ja, precis. Där syns det tydligt att om T3 tar längre tid än 3 tidsenheter så kommer inte T2 och T3 hinna med sin deadline.
Tack så mycket, du förklara det väldigt tydligt. Höll på att bli galen på det lösningsförslaget som läraren har gett...
