2 svar
206 visningar
TB16 182 – Fd. Medlem
Postad: 11 aug 2019 12:54

Rate-monotonic scheduling

Uppgift: 

Consider three periodic tasks, T1, T2 and T3, with periods and processing requirements of p1 = 60, t1 = 20, p2 = 30, t2 = 5, p3 = 120, and t3 = 40, respectively. 

(i) Can they be scheduled using rate-monotonic scheduling? 

(ii) Can they be scheduled using the earliest-deadline-first (EDF) scheduling? 

Explain carefully why or why not in both questions.

Min fråga berör första deluppgiften, dvs schemaläggning genom att använda rate-monotonic. Enligt min skiss verkar alla tre tasks möta sina deadlines (deadline = period) så verkar det funka:
Enligt skissen så verkar rate-monotonic kunna användas, men enligt svaret till denna uppgift så fungerar inte rate-monotonic. Någon som ser varför? Behöver jag göra en längre tidslinje för att se det kanske?

(OBS! En ruta motsvarar 10 tidsenheter)


Laguna Online 30472
Postad: 11 aug 2019 15:11

Jag kan inte svara på frågan. Din skiss verkar vettig. Eftersom allting upprepar sig efter tiden 120 så kan det inte löna sig att gå längre.

Man kan nog inte förutsätta att allting blir redo att köra samtidigt, men hur man hittar ett scenario som inte fungerar vet jag inte. De båda tillräckliga kriterierna som står på engelska wikipedia-sidan är inte uppfyllda, men de är ju tillräckliga, inte nödvändiga.

Jag känner viss osäkerhet för begreppen period och deadline (och release) så jag har kanske inte förstått algoritmen. 

TB16 182 – Fd. Medlem
Postad: 13 aug 2019 15:01
Laguna skrev:

Jag kan inte svara på frågan. Din skiss verkar vettig. Eftersom allting upprepar sig efter tiden 120 så kan det inte löna sig att gå längre.

Man kan nog inte förutsätta att allting blir redo att köra samtidigt, men hur man hittar ett scenario som inte fungerar vet jag inte. De båda tillräckliga kriterierna som står på engelska wikipedia-sidan är inte uppfyllda, men de är ju tillräckliga, inte nödvändiga.

Jag känner viss osäkerhet för begreppen period och deadline (och release) så jag har kanske inte förstått algoritmen. 


I svaret till uppgiften står det "RM cannot do it; apply it and show with Gantt chart that some task misses its deadline".  Perioden är väl hur ofta processen skall köras en viss tid. Så om perioden är 4 tidsenheter och körtiden är 1 tidsenhet så kommer processen köra en tidsenhet under varje period. Enligt Rate-monotonic så är Deadline = period så att om exempelvis en process med period = 4 och körtid = 1 får köra sin första gång efter att 5 tidsenheter passerat, så har processen missat sin deadline.  

Svara
Close