Rev 691 | Rev 700 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
671 | giacomo | 1 | /* |
2 | * Project: S.Ha.R.K. |
||
3 | * |
||
4 | * Coordinators: |
||
5 | * Giorgio Buttazzo <giorgio@sssup.it> |
||
6 | * Paolo Gai <pj@gandalf.sssup.it> |
||
7 | * |
||
8 | * Authors : |
||
9 | * Giacomo Guidi <giacomo@gandalf.sssup.it> |
||
10 | * Mauro Marinoni |
||
11 | * Anton Cervin |
||
12 | * |
||
13 | * ReTiS Lab (Scuola Superiore S.Anna - Pisa - Italy) |
||
14 | * |
||
15 | * http://www.sssup.it |
||
16 | * http://retis.sssup.it |
||
17 | * http://shark.sssup.it |
||
18 | */ |
||
19 | |||
20 | /* |
||
21 | * This program is free software; you can redistribute it and/or modify |
||
22 | * it under the terms of the GNU General Public License as published by |
||
23 | * the Free Software Foundation; either version 2 of the License, or |
||
24 | * (at your option) any later version. |
||
25 | * |
||
26 | * This program is distributed in the hope that it will be useful, |
||
27 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
||
28 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
||
29 | * GNU General Public License for more details. |
||
30 | * |
||
31 | * You should have received a copy of the GNU General Public License |
||
32 | * along with this program; if not, write to the Free Software |
||
33 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
||
34 | * |
||
35 | */ |
||
36 | |||
37 | #include <kernel/model.h> |
||
38 | #include <kernel/descr.h> |
||
39 | #include <kernel/var.h> |
||
40 | #include <kernel/func.h> |
||
41 | |||
42 | #include <stdlib.h> |
||
43 | |||
44 | #include <modules/elastic.h> |
||
45 | |||
46 | #include <tracer.h> |
||
47 | |||
673 | giacomo | 48 | #define ELASTIC_EMPTY_SLOT 0 |
49 | #define ELASTIC_PRESENT 1 |
||
671 | giacomo | 50 | |
683 | giacomo | 51 | #define ELASTIC_IDLE APER_STATUS_BASE |
52 | |||
691 | anton | 53 | //#define ELASTIC_DEBUG |
676 | giacomo | 54 | |
671 | giacomo | 55 | typedef struct { |
56 | |||
697 | anton | 57 | /* Task parameters (set/changed by the user) */ |
58 | |||
59 | TIME Tmin; /* The nominal (minimum) period */ |
||
60 | TIME Tmax; /* The maximum tolerable period */ |
||
61 | TIME C; /* The declared worst-case execution time */ |
||
62 | int E; /* The elasticity coefficient */ |
||
63 | int beta; /* PERIOD_SCALING or WCET_SCALING */ |
||
64 | |||
65 | /* Task variables (changed by the module) */ |
||
66 | |||
67 | struct timespec dline; /* The current absolute deadline */ |
||
671 | giacomo | 68 | |
697 | anton | 69 | bandwidth_t Umax; /* The maximum utilization, Umax = C/Tmin */ |
70 | bandwidth_t Umin; /* The minimum utilization, Umin = C/Tmax */ |
||
671 | giacomo | 71 | |
697 | anton | 72 | bandwidth_t U; /* The current utilization */ |
73 | TIME T; /* The current period, T = C/U */ |
||
673 | giacomo | 74 | |
671 | giacomo | 75 | int flags; |
76 | |||
77 | } ELASTIC_task_descr; |
||
78 | |||
79 | typedef struct { |
||
80 | level_des l; /*+ the standard level descriptor +*/ |
||
81 | |||
691 | anton | 82 | bandwidth_t U; /*+ the bandwidth reserved for elastic tasks +*/ |
671 | giacomo | 83 | |
697 | anton | 84 | ELASTIC_task_descr elist[MAX_PROC]; |
671 | giacomo | 85 | |
86 | LEVEL scheduling_level; |
||
87 | |||
88 | LEVEL current_level; |
||
89 | |||
90 | int flags; |
||
91 | |||
92 | } ELASTIC_level_des; |
||
93 | |||
673 | giacomo | 94 | |
697 | anton | 95 | /* Checks feasability and computes new utilizations for the task set */ |
96 | |||
97 | static int ELASTIC_compress(ELASTIC_level_des *lev) { |
||
98 | |||
676 | giacomo | 99 | PID i; |
697 | anton | 100 | ELASTIC_task_descr *t; |
101 | int ok; |
||
102 | |||
103 | ext_bandwidth_t Umin; // minimum utilization |
||
104 | ext_bandwidth_t Umax; // nominal (maximum) utilization of compressable tasks |
||
676 | giacomo | 105 | |
697 | anton | 106 | ext_bandwidth_t Uf; // amount of non-compressable utilization |
107 | int Ev; // sum of elasticity among compressable tasks |
||
108 | |||
109 | Umin = 0; |
||
110 | Umax = 0; |
||
111 | |||
676 | giacomo | 112 | for (i=0; i<MAX_PROC; i++) { |
697 | anton | 113 | t = &lev->elist[i]; |
114 | if (t->flags & ELASTIC_PRESENT) { |
||
115 | if (t->E == 0) { |
||
116 | Umin += t->U; |
||
117 | } else { |
||
118 | Umin += t->Umin; |
||
119 | t->U = t->Umax; // reset previous saturations |
||
120 | } |
||
691 | anton | 121 | } |
676 | giacomo | 122 | } |
697 | anton | 123 | |
124 | if (Umin > lev->U) return -1; // NOT FEASIBLE |
||
676 | giacomo | 125 | |
697 | anton | 126 | do { |
127 | Uf = 0; |
||
128 | Ev = 0; |
||
129 | Umax = 0; |
||
673 | giacomo | 130 | |
697 | anton | 131 | for (i=0; i<MAX_PROC; i++) { |
132 | t = &lev->elist[i]; |
||
133 | if (t->flags & ELASTIC_PRESENT) { |
||
134 | if (t->E == 0 || t->U == t->Umin) { |
||
135 | Uf += t->U; |
||
136 | } else { |
||
137 | Ev += t->E; |
||
138 | Umax += t->Umax; |
||
139 | } |
||
140 | } |
||
141 | } |
||
142 | |||
143 | ok = 1; |
||
144 | |||
145 | for (i=0; i<MAX_PROC; i++) { |
||
146 | t = &lev->elist[i]; |
||
147 | if (t->flags & ELASTIC_PRESENT) { |
||
148 | if (t->E > 0 && t->U > t->Umin) { |
||
149 | t->U = t->Umax - (Umax - lev->U + Uf) * t->E / Ev; |
||
150 | if (t->U < t->Umin) { |
||
151 | t->U = t->Umin; |
||
152 | ok = 0; |
||
153 | } |
||
154 | t->T = ((long long)t->C * (long long)MAX_BANDWIDTH) / t->U; |
||
155 | } |
||
156 | } |
||
157 | } |
||
673 | giacomo | 158 | |
697 | anton | 159 | } while (ok == 0); |
673 | giacomo | 160 | |
697 | anton | 161 | cprintf("New periods: "); |
691 | anton | 162 | for (i=0; i<MAX_PROC; i++) { |
697 | anton | 163 | t = &lev->elist[i]; |
164 | if (t->flags & ELASTIC_PRESENT) { |
||
165 | cprintf("%s:%d ", proc_table[i].name, t->T); |
||
691 | anton | 166 | } |
167 | } |
||
697 | anton | 168 | cprintf("\n"); |
691 | anton | 169 | |
697 | anton | 170 | return 0; // FEASIBLE |
691 | anton | 171 | |
673 | giacomo | 172 | } |
173 | |||
697 | anton | 174 | |
671 | giacomo | 175 | static void ELASTIC_activation(ELASTIC_level_des *lev, |
176 | PID p, |
||
177 | struct timespec *acttime) |
||
178 | { |
||
179 | JOB_TASK_MODEL job; |
||
674 | giacomo | 180 | |
181 | /* Job deadline */ |
||
182 | TIMESPEC_ASSIGN(&(lev->elist[p].dline),acttime); |
||
691 | anton | 183 | ADDUSEC2TIMESPEC(lev->elist[p].T,&(lev->elist[p].dline)); |
674 | giacomo | 184 | |
691 | anton | 185 | proc_table[p].avail_time = lev->elist[p].C; |
186 | proc_table[p].wcet = lev->elist[p].C; |
||
683 | giacomo | 187 | |
674 | giacomo | 188 | /* Job insertion */ |
189 | job_task_default_model(job, lev->elist[p].dline); |
||
671 | giacomo | 190 | level_table[ lev->scheduling_level ]-> |
191 | private_insert(lev->scheduling_level, p, (TASK_MODEL *)&job); |
||
192 | |||
674 | giacomo | 193 | } |
671 | giacomo | 194 | |
674 | giacomo | 195 | static void ELASTIC_timer_act(void *arg) { |
697 | anton | 196 | |
674 | giacomo | 197 | PID p = (PID)(arg); |
198 | ELASTIC_level_des *lev; |
||
199 | struct timespec acttime; |
||
683 | giacomo | 200 | |
201 | #ifdef ELASTIC_DEBUG |
||
202 | printk("(ELASTIC:Timer:%d)",p); |
||
203 | #endif |
||
697 | anton | 204 | |
674 | giacomo | 205 | kern_gettime(&acttime); |
697 | anton | 206 | |
674 | giacomo | 207 | lev = (ELASTIC_level_des *)level_table[proc_table[p].task_level]; |
697 | anton | 208 | |
209 | ELASTIC_activation(lev, p, &acttime); |
||
210 | |||
683 | giacomo | 211 | event_need_reschedule(); |
212 | |||
213 | /* Next activation */ |
||
214 | kern_event_post(&(lev->elist[p].dline), ELASTIC_timer_act, (void *)(p)); |
||
215 | |||
671 | giacomo | 216 | } |
217 | |||
218 | /* The on-line guarantee is enabled only if the appropriate flag is set... */ |
||
219 | static int ELASTIC_public_guarantee(LEVEL l, bandwidth_t *freebandwidth) |
||
220 | { |
||
221 | ELASTIC_level_des *lev = (ELASTIC_level_des *)(level_table[l]); |
||
222 | |||
691 | anton | 223 | if (*freebandwidth >= lev->U) { |
224 | *freebandwidth -= lev->U; |
||
225 | return 1; |
||
226 | } else { |
||
227 | return 0; |
||
228 | } |
||
671 | giacomo | 229 | } |
230 | |||
697 | anton | 231 | /* Checks if the current task set is feasible. Returns 1=yes, 0=no */ |
232 | static int ELASTIC_feasible(ELASTIC_level_des *lev) |
||
233 | { |
||
234 | ext_bandwidth_t Umin = 0; |
||
235 | PID i; |
||
691 | anton | 236 | |
697 | anton | 237 | for (i=0; i<MAX_PROC; i++) { |
238 | if (lev->elist[i].flags & ELASTIC_PRESENT) { |
||
239 | if (lev->elist[i].E == 0) { |
||
240 | /* The task is not elastic. Use current utilization U */ |
||
241 | Umin += lev->elist[i].U; |
||
242 | } else { |
||
243 | /* The task is elastic. Use minimum utilization Umin */ |
||
244 | Umin += lev->elist[i].Umin; |
||
245 | } |
||
246 | } |
||
247 | } |
||
248 | if (Umin > lev->U) { |
||
249 | return 0; |
||
250 | } else { |
||
251 | return 1; |
||
252 | } |
||
253 | } |
||
254 | |||
255 | |||
671 | giacomo | 256 | static int ELASTIC_public_create(LEVEL l, PID p, TASK_MODEL *m) |
257 | { |
||
258 | ELASTIC_level_des *lev = (ELASTIC_level_des *)(level_table[l]); |
||
691 | anton | 259 | ELASTIC_TASK_MODEL *elastic = (ELASTIC_TASK_MODEL *)m; |
671 | giacomo | 260 | |
261 | if (m->pclass != ELASTIC_PCLASS) return -1; |
||
262 | if (m->level != 0 && m->level != l) return -1; |
||
263 | |||
691 | anton | 264 | if (elastic->C == 0) return -1; |
673 | giacomo | 265 | if (elastic->Tmin > elastic->Tmax) return -1; |
266 | if (elastic->Tmax == 0) return -1; |
||
267 | |||
268 | lev->elist[p].flags |= ELASTIC_PRESENT; |
||
269 | |||
270 | NULL_TIMESPEC(&(lev->elist[p].dline)); |
||
271 | lev->elist[p].Tmin = elastic->Tmin; |
||
272 | lev->elist[p].Tmax = elastic->Tmax; |
||
691 | anton | 273 | lev->elist[p].C = elastic->C; |
274 | lev->elist[p].E = elastic->E; |
||
673 | giacomo | 275 | lev->elist[p].beta = elastic->beta; |
276 | |||
697 | anton | 277 | lev->elist[p].Umax = ((long long)MAX_BANDWIDTH * (long long)elastic->C) |
278 | / elastic->Tmin; |
||
279 | lev->elist[p].Umin = ((long long)MAX_BANDWIDTH * (long long)elastic->C) |
||
280 | / elastic->Tmax; |
||
673 | giacomo | 281 | |
697 | anton | 282 | lev->elist[p].U = lev->elist[p].Umax; |
283 | lev->elist[p].T = lev->elist[p].Tmin; |
||
284 | |||
285 | if (ELASTIC_compress(lev) == -1) { |
||
691 | anton | 286 | lev->elist[p].flags = ELASTIC_EMPTY_SLOT; |
287 | return -1; |
||
288 | } |
||
289 | |||
290 | proc_table[p].avail_time = elastic->C; |
||
291 | proc_table[p].wcet = elastic->C; |
||
674 | giacomo | 292 | proc_table[p].control |= CONTROL_CAP; |
673 | giacomo | 293 | |
697 | anton | 294 | return 0; |
671 | giacomo | 295 | } |
296 | |||
697 | anton | 297 | |
671 | giacomo | 298 | static void ELASTIC_public_detach(LEVEL l, PID p) |
299 | { |
||
300 | ELASTIC_level_des *lev = (ELASTIC_level_des *)(level_table[l]); |
||
301 | |||
302 | } |
||
303 | |||
304 | static int ELASTIC_public_eligible(LEVEL l, PID p) |
||
305 | { |
||
306 | ELASTIC_level_des *lev = (ELASTIC_level_des *)(level_table[l]); |
||
307 | |||
308 | return 0; |
||
309 | |||
310 | } |
||
311 | |||
312 | static void ELASTIC_public_dispatch(LEVEL l, PID p, int nostop) |
||
313 | { |
||
314 | ELASTIC_level_des *lev = (ELASTIC_level_des *)(level_table[l]); |
||
674 | giacomo | 315 | |
683 | giacomo | 316 | #ifdef ELASTIC_DEBUG |
317 | printk("(ELASTIC:Dsp:%d)",p); |
||
318 | #endif |
||
319 | |||
671 | giacomo | 320 | level_table[ lev->scheduling_level ]-> |
321 | private_dispatch(lev->scheduling_level,p,nostop); |
||
674 | giacomo | 322 | |
671 | giacomo | 323 | } |
324 | |||
325 | static void ELASTIC_public_epilogue(LEVEL l, PID p) |
||
326 | { |
||
327 | ELASTIC_level_des *lev = (ELASTIC_level_des *)(level_table[l]); |
||
328 | |||
683 | giacomo | 329 | #ifdef ELASTIC_DEBUG |
330 | printk("(ELASTIC:Epi:%d)",p); |
||
331 | #endif |
||
332 | |||
674 | giacomo | 333 | /* check if the wcet is finished... */ |
334 | if (proc_table[p].avail_time <= 0) { |
||
335 | |||
336 | TRACER_LOGEVENT(FTrace_EVT_task_wcet_violation,(unsigned short int)proc_table[p].context,0); |
||
337 | kern_raise(XWCET_VIOLATION,p); |
||
338 | |||
339 | } |
||
691 | anton | 340 | |
674 | giacomo | 341 | level_table[ lev->scheduling_level ]-> |
342 | private_epilogue(lev->scheduling_level,p); |
||
343 | |||
671 | giacomo | 344 | } |
345 | |||
346 | static void ELASTIC_public_activate(LEVEL l, PID p, struct timespec *t) |
||
347 | { |
||
348 | ELASTIC_level_des *lev = (ELASTIC_level_des *)(level_table[l]); |
||
349 | |||
674 | giacomo | 350 | #ifdef ELASTIC_DEBUG |
351 | printk("(ELASTIC:Act:%d)", p); |
||
352 | #endif |
||
353 | |||
354 | /* check if we are not in the SLEEP state */ |
||
355 | if (proc_table[p].status != SLEEP) { |
||
356 | |||
357 | return; |
||
358 | |||
359 | } |
||
360 | |||
361 | ELASTIC_activation(lev,p,t); |
||
362 | |||
363 | /* Next activation */ |
||
364 | kern_event_post(&(lev->elist[p].dline), ELASTIC_timer_act, (void *)(p)); |
||
365 | |||
671 | giacomo | 366 | } |
367 | |||
368 | static void ELASTIC_public_unblock(LEVEL l, PID p) |
||
369 | { |
||
370 | ELASTIC_level_des *lev = (ELASTIC_level_des *)(level_table[l]); |
||
371 | struct timespec acttime; |
||
372 | |||
373 | kern_gettime(&acttime); |
||
374 | |||
375 | ELASTIC_activation(lev,p,&acttime); |
||
376 | |||
377 | } |
||
378 | |||
379 | static void ELASTIC_public_block(LEVEL l, PID p) |
||
380 | { |
||
381 | ELASTIC_level_des *lev = (ELASTIC_level_des *)(level_table[l]); |
||
382 | |||
383 | level_table[ lev->scheduling_level ]-> |
||
384 | private_extract(lev->scheduling_level,p); |
||
385 | |||
386 | } |
||
387 | |||
388 | static int ELASTIC_public_message(LEVEL l, PID p, void *m) |
||
389 | { |
||
390 | ELASTIC_level_des *lev = (ELASTIC_level_des *)(level_table[l]); |
||
676 | giacomo | 391 | struct timespec acttime; |
671 | giacomo | 392 | |
393 | switch((long)(m)) { |
||
394 | |||
395 | case (long)(NULL): |
||
396 | |||
683 | giacomo | 397 | #ifdef ELASTIC_DEBUG |
398 | printk("(ELASTIC:EndCyc:%d)",p); |
||
399 | #endif |
||
400 | |||
676 | giacomo | 401 | level_table[ lev->scheduling_level ]-> |
402 | private_extract(lev->scheduling_level,p); |
||
403 | |||
683 | giacomo | 404 | proc_table[p].status = ELASTIC_IDLE; |
676 | giacomo | 405 | |
671 | giacomo | 406 | jet_update_endcycle(); /* Update the Jet data... */ |
407 | TRACER_LOGEVENT(FTrace_EVT_task_end_cycle,(unsigned short int)proc_table[p].context,(unsigned int)l); |
||
408 | |||
409 | break; |
||
410 | |||
411 | case 1: |
||
412 | |||
683 | giacomo | 413 | #ifdef ELASTIC_DEBUG |
414 | printk("(ELASTIC:Disable:%d)",p); |
||
415 | #endif |
||
416 | |||
676 | giacomo | 417 | level_table[ lev->scheduling_level ]-> |
418 | private_extract(lev->scheduling_level,p); |
||
419 | |||
420 | proc_table[p].status = SLEEP; |
||
421 | |||
671 | giacomo | 422 | TRACER_LOGEVENT(FTrace_EVT_task_disable,(unsigned short int)proc_table[p].context,(unsigned int)l); |
423 | |||
424 | break; |
||
425 | |||
426 | } |
||
427 | |||
428 | return 0; |
||
429 | |||
430 | } |
||
431 | |||
432 | static void ELASTIC_public_end(LEVEL l, PID p) |
||
433 | { |
||
434 | ELASTIC_level_des *lev = (ELASTIC_level_des *)(level_table[l]); |
||
435 | |||
436 | level_table[ lev->scheduling_level ]-> |
||
437 | private_extract(lev->scheduling_level,p); |
||
438 | |||
439 | } |
||
440 | |||
441 | /*+ Registration function +*/ |
||
691 | anton | 442 | LEVEL ELASTIC_register_level(int flags, LEVEL master, bandwidth_t U) |
671 | giacomo | 443 | { |
444 | LEVEL l; /* the level that we register */ |
||
445 | ELASTIC_level_des *lev; /* for readableness only */ |
||
446 | PID i; |
||
447 | |||
448 | printk("ELASTIC_register_level\n"); |
||
449 | |||
450 | /* request an entry in the level_table */ |
||
451 | l = level_alloc_descriptor(sizeof(ELASTIC_level_des)); |
||
452 | |||
453 | lev = (ELASTIC_level_des *)level_table[l]; |
||
454 | |||
455 | /* fill the standard descriptor */ |
||
456 | if (flags & ELASTIC_ENABLE_GUARANTEE) |
||
457 | lev->l.public_guarantee = ELASTIC_public_guarantee; |
||
458 | else |
||
459 | lev->l.public_guarantee = NULL; |
||
460 | lev->l.public_create = ELASTIC_public_create; |
||
461 | lev->l.public_detach = ELASTIC_public_detach; |
||
462 | lev->l.public_end = ELASTIC_public_end; |
||
463 | lev->l.public_eligible = ELASTIC_public_eligible; |
||
464 | lev->l.public_dispatch = ELASTIC_public_dispatch; |
||
465 | lev->l.public_epilogue = ELASTIC_public_epilogue; |
||
466 | lev->l.public_activate = ELASTIC_public_activate; |
||
467 | lev->l.public_unblock = ELASTIC_public_unblock; |
||
468 | lev->l.public_block = ELASTIC_public_block; |
||
469 | lev->l.public_message = ELASTIC_public_message; |
||
470 | |||
676 | giacomo | 471 | /* fill the ELASTIC task descriptor part */ |
671 | giacomo | 472 | for (i=0; i<MAX_PROC; i++) { |
473 | NULL_TIMESPEC(&(lev->elist[i].dline)); |
||
474 | lev->elist[i].Tmin = 0; |
||
475 | lev->elist[i].Tmax = 0; |
||
691 | anton | 476 | lev->elist[i].T = 0; |
697 | anton | 477 | lev->elist[i].U = 0; |
691 | anton | 478 | lev->elist[i].C = 0; |
479 | lev->elist[i].E = 0; |
||
671 | giacomo | 480 | lev->elist[i].beta = 0; |
481 | lev->elist[i].flags = ELASTIC_EMPTY_SLOT; |
||
482 | } |
||
483 | |||
691 | anton | 484 | lev->U = U; |
671 | giacomo | 485 | |
486 | lev->scheduling_level = master; |
||
487 | |||
488 | lev->current_level = l; |
||
489 | |||
490 | lev->flags = flags; |
||
491 | |||
492 | return l; |
||
493 | } |
||
494 |