Rev 1036 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
961 | pj | 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 | * Paolo Gai <pj@gandalf.sssup.it> |
||
10 | * Massimiliano Giorgi <massy@gandalf.sssup.it> |
||
11 | * Luca Abeni <luca@gandalf.sssup.it> |
||
12 | * Anton Cervin |
||
1036 | tullio | 13 | * Tullio Facchinetti <tullio.facchinetti@unipv.it> |
961 | pj | 14 | * |
15 | * ReTiS Lab (Scuola Superiore S.Anna - Pisa - Italy) |
||
16 | * |
||
17 | * http://www.sssup.it |
||
18 | * http://retis.sssup.it |
||
19 | * http://shark.sssup.it |
||
20 | */ |
||
21 | |||
22 | /** |
||
23 | ------------ |
||
1036 | tullio | 24 | CVS : $Id: edf.c,v 1.2 2006-03-22 16:06:19 tullio Exp $ |
961 | pj | 25 | |
26 | File: $File$ |
||
1036 | tullio | 27 | Revision: $Revision: 1.2 $ |
28 | Last update: $Date: 2006-03-22 16:06:19 $ |
||
961 | pj | 29 | ------------ |
30 | |||
31 | This file contains the scheduling module EDF (Earliest Deadline First) |
||
32 | |||
33 | Read edf.h for further details. |
||
34 | |||
35 | **/ |
||
36 | |||
37 | /* |
||
38 | * Copyright (C) 2000,2002 Paolo Gai |
||
39 | * |
||
40 | * This program is free software; you can redistribute it and/or modify |
||
41 | * it under the terms of the GNU General Public License as published by |
||
42 | * the Free Software Foundation; either version 2 of the License, or |
||
43 | * (at your option) any later version. |
||
44 | * |
||
45 | * This program is distributed in the hope that it will be useful, |
||
46 | * but WITHOUT ANY WARRANTY; without even the implied warranty of |
||
47 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
||
48 | * GNU General Public License for more details. |
||
49 | * |
||
50 | * You should have received a copy of the GNU General Public License |
||
51 | * along with this program; if not, write to the Free Software |
||
52 | * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA |
||
53 | * |
||
54 | */ |
||
55 | |||
56 | |||
57 | #include <edf/edf/edf.h> |
||
58 | #include <ll/stdio.h> |
||
59 | #include <ll/string.h> |
||
60 | #include <kernel/model.h> |
||
61 | #include <kernel/descr.h> |
||
62 | #include <kernel/var.h> |
||
63 | #include <kernel/func.h> |
||
64 | #include <tracer.h> |
||
65 | |||
66 | //#define EDF_DEBUG |
||
67 | #define edf_printf kern_printf |
||
68 | #ifdef EDF_DEBUG |
||
69 | char *pnow() { |
||
70 | static char buf[40]; |
||
71 | struct timespec t; |
||
72 | sys_gettime(&t); |
||
73 | sprintf(buf, "%ld.%06ld", t.tv_sec, t.tv_nsec/1000); |
||
74 | return buf; |
||
75 | } |
||
76 | char *ptime1(struct timespec *t) { |
||
77 | static char buf[40]; |
||
78 | sprintf(buf, "%ld.%06ld", t->tv_sec, t->tv_nsec/1000); |
||
79 | return buf; |
||
80 | } |
||
81 | char *ptime2(struct timespec *t) { |
||
82 | static char buf[40]; |
||
83 | sprintf(buf, "%ld.%06ld", t->tv_sec, t->tv_nsec/1000); |
||
84 | return buf; |
||
85 | } |
||
86 | #endif |
||
87 | |||
88 | /* Statuses used in the level */ |
||
89 | #define EDF_READY MODULE_STATUS_BASE /* ready */ |
||
90 | #define EDF_IDLE MODULE_STATUS_BASE+1 /* idle, waiting for offset/eop */ |
||
91 | #define EDF_WAIT MODULE_STATUS_BASE+2 /* to sleep, waiting for eop */ |
||
92 | #define EDF_ZOMBIE MODULE_STATUS_BASE+3 /* to free, waiting for eop */ |
||
93 | |||
94 | /* Task flags */ |
||
95 | #define EDF_FLAG_SPORADIC 1 /* the task is sporadic */ |
||
96 | #define EDF_FLAG_SPOR_LATE 2 /* sporadic task with period overrun */ |
||
97 | |||
98 | |||
99 | /* Task descriptor */ |
||
100 | typedef struct { |
||
101 | int flags; /* task flags */ |
||
102 | TIME period; /* period (or inter-arrival interval) */ |
||
103 | TIME rdeadline; /* relative deadline */ |
||
104 | TIME offset; /* release offset */ |
||
105 | struct timespec release; /* release time of current instance */ |
||
106 | struct timespec adeadline; /* latest assigned deadline */ |
||
107 | int dl_timer; /* deadline timer */ |
||
108 | int eop_timer; /* end of period timer */ |
||
109 | int off_timer; /* timer offset */ |
||
110 | int dl_miss; /* deadline miss counter */ |
||
111 | int wcet_miss; /* WCET miss counter */ |
||
112 | int act_miss; /* activation miss counter */ |
||
113 | int nact; /* number of pending periodic jobs */ |
||
114 | } EDF_task_des; |
||
115 | |||
116 | |||
117 | /* Level descriptor */ |
||
118 | typedef struct { |
||
119 | level_des l; /* standard level descriptor */ |
||
120 | int flags; /* level flags */ |
||
121 | IQUEUE ready; /* the ready queue */ |
||
122 | bandwidth_t U; /* used bandwidth */ |
||
123 | EDF_task_des tvec[MAX_PROC]; /* vector of task descriptors */ |
||
124 | } EDF_level_des; |
||
125 | |||
126 | |||
127 | /* Module function cross-references */ |
||
128 | static void EDF_intern_release(PID p, EDF_level_des *lev); |
||
129 | |||
130 | |||
131 | /**** Timer event handler functions ****/ |
||
132 | |||
133 | /* This timer event handler is called at the end of the period */ |
||
134 | static void EDF_timer_endperiod(void *par) |
||
135 | { |
||
136 | PID p = (PID) par; |
||
137 | EDF_level_des *lev = (EDF_level_des *)level_table[proc_table[p].task_level]; |
||
138 | EDF_task_des *td = &lev->tvec[p]; |
||
139 | |||
140 | td->eop_timer = -1; |
||
141 | |||
142 | if (proc_table[p].status == EDF_ZOMBIE) { |
||
143 | /* put the task in the FREE state */ |
||
144 | proc_table[p].status = FREE; |
||
145 | iq_insertfirst(p,&freedesc); |
||
146 | /* free the allocated bandwidth */ |
||
147 | lev->U -= (MAX_BANDWIDTH/td->rdeadline) * proc_table[p].wcet; |
||
148 | return; |
||
149 | } |
||
150 | |||
151 | if (proc_table[p].status == EDF_WAIT) { |
||
152 | proc_table[p].status = SLEEP; |
||
153 | return; |
||
154 | } |
||
155 | |||
156 | if (td->flags & EDF_FLAG_SPORADIC) { |
||
157 | /* the task is sporadic and still busy, mark it as late */ |
||
158 | td->flags |= EDF_FLAG_SPOR_LATE; |
||
159 | } else { |
||
160 | /* the task is periodic, release/queue another instance */ |
||
161 | EDF_intern_release(p, lev); |
||
162 | } |
||
163 | } |
||
164 | |||
165 | /* This timer event handler is called when a task misses its deadline */ |
||
166 | static void EDF_timer_deadline(void *par) |
||
167 | { |
||
168 | PID p = (PID) par; |
||
169 | EDF_level_des *lev = (EDF_level_des *)level_table[proc_table[p].task_level]; |
||
170 | EDF_task_des *td = &lev->tvec[p]; |
||
171 | |||
172 | td->dl_timer = -1; |
||
173 | |||
174 | TRACER_LOGEVENT(FTrace_EVT_task_deadline_miss, |
||
175 | (unsigned short int)proc_table[p].context,0); |
||
176 | |||
177 | if (lev->flags & EDF_ENABLE_DL_EXCEPTION) { |
||
178 | kern_raise(XDEADLINE_MISS,p); |
||
179 | } else { |
||
180 | td->dl_miss++; |
||
181 | } |
||
182 | } |
||
183 | |||
184 | /* This timer event handler is called after waiting for an offset */ |
||
185 | static void EDF_timer_offset(void *par) |
||
186 | { |
||
187 | PID p = (PID) par; |
||
188 | EDF_level_des *lev; |
||
189 | lev = (EDF_level_des *)level_table[proc_table[p].task_level]; |
||
190 | EDF_task_des *td = &lev->tvec[p]; |
||
191 | |||
192 | td->off_timer = -1; |
||
193 | |||
194 | /* release the task now */ |
||
195 | EDF_intern_release(p, lev); |
||
196 | |||
197 | } |
||
198 | |||
199 | /* This function is called when a guest task misses its deadline */ |
||
200 | static void EDF_timer_guest_deadline(void *par) |
||
201 | { |
||
202 | PID p = (PID) par; |
||
203 | EDF_level_des *lev = (EDF_level_des *)level_table[proc_table[p].task_level]; |
||
204 | EDF_task_des *td = &lev->tvec[p]; |
||
205 | |||
206 | td->dl_timer = -1; |
||
207 | |||
208 | TRACER_LOGEVENT(FTrace_EVT_task_deadline_miss, |
||
209 | (unsigned short int)proc_table[p].context,0); |
||
210 | |||
211 | kern_raise(XDEADLINE_MISS,p); |
||
212 | |||
213 | } |
||
214 | |||
215 | |||
216 | /**** Internal utility functions ****/ |
||
217 | |||
218 | /* Release (or queue) a task, post deadline and endperiod timers */ |
||
219 | static void EDF_intern_release(PID p, EDF_level_des *lev) |
||
220 | { |
||
221 | struct timespec temp; |
||
222 | EDF_task_des *td = &lev->tvec[p]; |
||
223 | |||
224 | /* post deadline timer */ |
||
225 | if (lev->flags & EDF_ENABLE_DL_CHECK) { |
||
226 | temp = td->release; |
||
1036 | tullio | 227 | if (td->rdeadline == td->period) ADDUSEC2TIMESPEC((td->rdeadline - 1), &temp); |
228 | else ADDUSEC2TIMESPEC(td->rdeadline, &temp); |
||
961 | pj | 229 | if (td->dl_timer != -1) { |
230 | kern_event_delete(td->dl_timer); |
||
231 | td->dl_timer = -1; |
||
232 | } |
||
233 | td->dl_timer = kern_event_post(&temp,EDF_timer_deadline,(void *)p); |
||
234 | } |
||
235 | |||
236 | /* release or queue next job */ |
||
237 | if (proc_table[p].status == EDF_IDLE) { |
||
238 | /* assign deadline, insert task in the ready queue */ |
||
239 | proc_table[p].status = EDF_READY; |
||
240 | *iq_query_timespec(p,&lev->ready) = td->adeadline; |
||
241 | iq_timespec_insert(p,&lev->ready); |
||
242 | #ifdef EDF_DEBUG |
||
243 | edf_printf("At %s: releasing %s with deadline %s\n", pnow(), |
||
244 | proc_table[p].name, ptime1(&td->adeadline)); |
||
245 | #endif |
||
246 | /* increase assigned deadline */ |
||
247 | ADDUSEC2TIMESPEC(td->period, &td->adeadline); |
||
248 | /* reschedule */ |
||
249 | event_need_reschedule(); |
||
250 | } else { |
||
251 | /* queue */ |
||
252 | td->nact++; |
||
253 | } |
||
254 | |||
255 | /* increase release time */ |
||
256 | ADDUSEC2TIMESPEC(td->period, &td->release); |
||
257 | /* post end of period timer */ |
||
258 | if (td->eop_timer != -1) { |
||
259 | kern_event_delete(td->eop_timer); |
||
260 | td->eop_timer = -1; |
||
261 | } |
||
262 | |||
263 | td->eop_timer = kern_event_post(&td->release, EDF_timer_endperiod,(void *)p); |
||
264 | |||
265 | TRACER_LOGEVENT(FTrace_EVT_task_timer, |
||
266 | (unsigned short int)proc_table[p].context, |
||
267 | (unsigned int)proc_table[p].task_level); |
||
268 | } |
||
269 | |||
270 | |||
271 | /**** Public generic kernel interface functions ****/ |
||
272 | |||
273 | /* Returns the first task in the ready queue */ |
||
274 | static PID EDF_public_scheduler(LEVEL l) |
||
275 | { |
||
276 | EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
||
277 | return iq_query_first(&lev->ready); |
||
278 | } |
||
279 | |||
280 | /* Checks and decreases the available system bandwidth */ |
||
281 | static int EDF_public_guarantee(LEVEL l, bandwidth_t *freebandwidth) |
||
282 | { |
||
283 | EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
||
284 | |||
285 | if (*freebandwidth >= lev->U) { |
||
286 | *freebandwidth -= lev->U; |
||
287 | return 1; |
||
288 | } |
||
289 | else |
||
290 | return 0; |
||
291 | } |
||
292 | |||
293 | /* Called by task_create: Checks task model and creates a task */ |
||
294 | static int EDF_public_create(LEVEL l, PID p, TASK_MODEL *m) |
||
295 | { |
||
296 | EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
||
297 | EDF_task_des *td = &lev->tvec[p]; |
||
298 | HARD_TASK_MODEL *h; |
||
299 | |||
300 | if (m->pclass != HARD_PCLASS) return -1; |
||
301 | if (m->level != 0 && m->level != l) return -1; |
||
302 | h = (HARD_TASK_MODEL *)m; |
||
303 | if (!h->wcet || !h->mit) return -1; |
||
304 | if (h->drel > h->mit) return -1; /* only D <= T supported */ |
||
305 | |||
306 | if (!h->drel) { |
||
307 | td->rdeadline = h->mit; |
||
308 | } else { |
||
309 | td->rdeadline = h->drel; |
||
310 | } |
||
311 | |||
312 | /* check the free bandwidth... */ |
||
313 | if (lev->flags & EDF_ENABLE_GUARANTEE) { |
||
314 | bandwidth_t b; |
||
315 | b = (MAX_BANDWIDTH / td->rdeadline) * h->wcet; |
||
316 | |||
317 | /* really update lev->U, checking an overflow... */ |
||
318 | if (MAX_BANDWIDTH - lev->U > b) { |
||
319 | lev->U += b; |
||
320 | } else { |
||
321 | return -1; |
||
322 | } |
||
323 | } |
||
324 | |||
325 | td->flags = 0; |
||
326 | if (h->periodicity == APERIODIC) { |
||
327 | td->flags |= EDF_FLAG_SPORADIC; |
||
328 | } |
||
329 | td->period = h->mit; |
||
1036 | tullio | 330 | |
331 | td->offset = h->offset; |
||
961 | pj | 332 | td->dl_timer = -1; |
333 | td->eop_timer = -1; |
||
334 | td->off_timer = -1; |
||
335 | td->dl_miss = 0; |
||
336 | td->wcet_miss = 0; |
||
337 | td->act_miss = 0; |
||
338 | td->nact = 0; |
||
339 | |||
340 | /* Enable wcet check */ |
||
341 | if (lev->flags & EDF_ENABLE_WCET_CHECK) { |
||
342 | proc_table[p].avail_time = h->wcet; |
||
343 | proc_table[p].wcet = h->wcet; |
||
344 | proc_table[p].control |= CONTROL_CAP; /* turn on measurement */ |
||
345 | } |
||
346 | |||
347 | return 0; /* OK, also if the task cannot be guaranteed... */ |
||
348 | } |
||
349 | |||
350 | /* Reclaim the bandwidth used by the task */ |
||
351 | static void EDF_public_detach(LEVEL l, PID p) |
||
352 | { |
||
353 | EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
||
354 | EDF_task_des *td = &lev->tvec[p]; |
||
355 | |||
356 | if (lev->flags & EDF_ENABLE_GUARANTEE) { |
||
357 | lev->U -= (MAX_BANDWIDTH / td->rdeadline) * proc_table[p].wcet; |
||
358 | } |
||
359 | } |
||
360 | |||
361 | /* Extracts the running task from the ready queue */ |
||
362 | static void EDF_public_dispatch(LEVEL l, PID p, int nostop) |
||
363 | { |
||
364 | EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
||
365 | iq_extract(p, &lev->ready); |
||
366 | } |
||
367 | |||
368 | /* Called when the task is preempted or when its budget is exhausted */ |
||
369 | static void EDF_public_epilogue(LEVEL l, PID p) |
||
370 | { |
||
371 | EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
||
372 | EDF_task_des *td = &lev->tvec[p]; |
||
373 | |||
374 | /* check if the wcet is finished... */ |
||
375 | if (lev->flags & EDF_ENABLE_WCET_CHECK) { |
||
376 | if (proc_table[p].avail_time <= 0) { |
||
377 | TRACER_LOGEVENT(FTrace_EVT_task_wcet_violation, |
||
378 | (unsigned short int)proc_table[p].context,0); |
||
379 | if (lev->flags & EDF_ENABLE_WCET_EXCEPTION) { |
||
380 | kern_raise(XWCET_VIOLATION,p); |
||
381 | } else { |
||
382 | proc_table[p].control &= ~CONTROL_CAP; |
||
383 | td->wcet_miss++; |
||
384 | } |
||
385 | } |
||
386 | } |
||
387 | |||
388 | /* the task returns to the ready queue */ |
||
389 | iq_timespec_insert(p,&lev->ready); |
||
390 | proc_table[p].status = EDF_READY; |
||
391 | |||
392 | } |
||
393 | |||
394 | /* Called by task_activate or group_activate: Activates the task at time t */ |
||
395 | static void EDF_public_activate(LEVEL l, PID p, struct timespec *t) |
||
396 | { |
||
397 | struct timespec clocktime; |
||
398 | EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
||
399 | EDF_task_des *td = &lev->tvec[p]; |
||
400 | |||
401 | kern_gettime(&clocktime); |
||
402 | |||
403 | /* check if we are not in the SLEEP state */ |
||
404 | if (proc_table[p].status != SLEEP) { |
||
405 | if (lev->flags & EDF_ENABLE_ACT_EXCEPTION) { |
||
406 | /* too frequent or wrongful activation: raise exception */ |
||
407 | kern_raise(XACTIVATION,p); |
||
408 | } else { |
||
409 | /* skip the sporadic job, but increase a counter */ |
||
410 | #ifdef EDF_DEBUG |
||
411 | edf_printf("At %s: activation of %s skipped\n", pnow(), |
||
412 | proc_table[p].name); |
||
413 | #endif |
||
414 | td->act_miss++; |
||
415 | } |
||
416 | return; |
||
417 | } |
||
418 | |||
419 | /* set the release time to the activation time + offset */ |
||
420 | td->release = *t; |
||
421 | ADDUSEC2TIMESPEC(td->offset, &td->release); |
||
422 | |||
423 | /* set the absolute deadline to the activation time + offset + rdeadline */ |
||
424 | td->adeadline = td->release; |
||
425 | ADDUSEC2TIMESPEC(td->rdeadline, &td->adeadline); |
||
426 | |||
427 | /* Check if release > clocktime. If yes, release it later, |
||
428 | otherwise release it now. */ |
||
429 | |||
430 | proc_table[p].status = EDF_IDLE; |
||
431 | |||
432 | if (TIMESPEC_A_GT_B(&td->release, &clocktime)) { |
||
433 | /* release later, post an offset timer */ |
||
434 | if (td->off_timer != -1) { |
||
435 | kern_event_delete(td->off_timer); |
||
436 | td->off_timer = -1; |
||
437 | } |
||
438 | td->off_timer = kern_event_post(&td->release,EDF_timer_offset,(void *)p); |
||
439 | } else { |
||
440 | /* release now */ |
||
441 | EDF_intern_release(p, lev); |
||
442 | } |
||
443 | } |
||
444 | |||
445 | /* Reinserts a task that has been blocked into the ready queue */ |
||
446 | static void EDF_public_unblock(LEVEL l, PID p) |
||
447 | { |
||
448 | EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
||
449 | |||
450 | /* Insert task in the correct position */ |
||
451 | proc_table[p].status = EDF_READY; |
||
452 | iq_timespec_insert(p,&lev->ready); |
||
453 | } |
||
454 | |||
455 | /* Called when a task experiences a synchronization block */ |
||
456 | static void EDF_public_block(LEVEL l, PID p) |
||
457 | { |
||
458 | /* Extract the running task from the level |
||
459 | . we have already extract it from the ready queue at the dispatch time. |
||
460 | . the capacity event have to be removed by the generic kernel |
||
461 | . the wcet don't need modification... |
||
462 | . the state of the task is set by the calling function |
||
463 | . the deadline must remain... |
||
464 | |||
465 | So, we do nothing!!! |
||
466 | */ |
||
467 | } |
||
468 | |||
469 | /* Called by task_endcycle or task_sleep: Ends the current instance */ |
||
470 | static int EDF_public_message(LEVEL l, PID p, void *m) |
||
471 | { |
||
472 | EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
||
473 | EDF_task_des *td = &lev->tvec[p]; |
||
474 | |||
475 | switch((long)(m)) { |
||
476 | /* task_endcycle() */ |
||
477 | case 0: |
||
478 | /* if there are no pending jobs */ |
||
479 | if (td->nact == 0) { |
||
480 | /* remove deadline timer, if any */ |
||
481 | if (td->dl_timer != -1) { |
||
482 | kern_event_delete(td->dl_timer); |
||
483 | td->dl_timer = -1; |
||
484 | } |
||
485 | if (td->flags & EDF_FLAG_SPORADIC) { |
||
486 | /* sporadic task */ |
||
487 | if (!(td->flags & EDF_FLAG_SPOR_LATE)) { |
||
488 | proc_table[p].status = EDF_WAIT; |
||
489 | } else { |
||
490 | /* it's late, move it directly to SLEEP */ |
||
491 | proc_table[p].status = SLEEP; |
||
492 | td->flags &= ~EDF_FLAG_SPOR_LATE; |
||
493 | } |
||
494 | } else { |
||
495 | /* periodic task */ |
||
496 | proc_table[p].status = EDF_IDLE; |
||
497 | } |
||
498 | } else { |
||
499 | /* we are late / there are pending jobs */ |
||
500 | td->nact--; |
||
501 | /* compute and assign absolute deadline */ |
||
502 | *iq_query_timespec(p,&lev->ready) = td->adeadline; |
||
503 | iq_timespec_insert(p,&lev->ready); |
||
504 | /* increase assigned deadline */ |
||
505 | ADDUSEC2TIMESPEC(td->period, &td->adeadline); |
||
506 | #ifdef EDF_DEBUG |
||
507 | edf_printf("(Late) At %s: releasing %s with deadline %s\n", |
||
508 | pnow(),proc_table[p].name,ptime1(&td->adeadline)); |
||
509 | #endif |
||
510 | } |
||
511 | break; |
||
512 | |||
513 | /* task_sleep() */ |
||
514 | case 1: |
||
515 | /* remove deadline timer, if any */ |
||
516 | if (td->dl_timer != -1) { |
||
517 | kern_event_delete(td->dl_timer); |
||
518 | td->dl_timer = -1; |
||
519 | } |
||
520 | if (td->flags & EDF_FLAG_SPORADIC) { |
||
521 | /* sporadic task */ |
||
522 | if (!(td->flags & EDF_FLAG_SPOR_LATE)) { |
||
523 | proc_table[p].status = EDF_WAIT; |
||
524 | } else { |
||
525 | /* it's late, move it directly to SLEEP */ |
||
526 | proc_table[p].status = SLEEP; |
||
527 | td->flags &= ~EDF_FLAG_SPOR_LATE; |
||
528 | } |
||
529 | } else { |
||
530 | /* periodic task */ |
||
531 | if (!(td->nact > 0)) { |
||
532 | /* we are on time. go to the EDF_WAIT state */ |
||
533 | proc_table[p].status = EDF_WAIT; |
||
534 | } else { |
||
535 | /* we are late. delete pending activations and go to SLEEP */ |
||
536 | td->nact = 0; |
||
537 | proc_table[p].status = SLEEP; |
||
538 | /* remove end of period timer */ |
||
539 | if (td->eop_timer != -1) { |
||
540 | kern_event_delete(td->eop_timer); |
||
541 | td->eop_timer = -1; |
||
542 | } |
||
543 | } |
||
544 | } |
||
545 | break; |
||
546 | } |
||
547 | |||
548 | if (lev->flags & EDF_ENABLE_WCET_CHECK) { |
||
549 | proc_table[p].control |= CONTROL_CAP; |
||
550 | } |
||
551 | jet_update_endcycle(); /* Update the Jet data... */ |
||
552 | proc_table[p].avail_time = proc_table[p].wcet; |
||
553 | TRACER_LOGEVENT(FTrace_EVT_task_end_cycle, |
||
554 | (unsigned short int)proc_table[p].context,(unsigned int)l); |
||
555 | |||
556 | return 0; |
||
557 | |||
558 | } |
||
559 | |||
560 | /* End the task and free the resources at the end of the period */ |
||
561 | static void EDF_public_end(LEVEL l, PID p) |
||
562 | { |
||
563 | EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
||
564 | EDF_task_des *td = &lev->tvec[p]; |
||
565 | |||
566 | if (!(td->flags & EDF_FLAG_SPOR_LATE)) { |
||
567 | /* remove the deadline timer (if any) */ |
||
568 | if (td->dl_timer != -1) { |
||
569 | kern_event_delete(td->dl_timer); |
||
570 | td->dl_timer = -1; |
||
571 | } |
||
572 | proc_table[p].status = EDF_ZOMBIE; |
||
573 | } else { |
||
574 | /* no endperiod timer will be fired, free the task now! */ |
||
575 | proc_table[p].status = FREE; |
||
576 | iq_insertfirst(p,&freedesc); |
||
577 | /* free the allocated bandwidth */ |
||
578 | lev->U -= (MAX_BANDWIDTH/td->rdeadline) * proc_table[p].wcet; |
||
579 | } |
||
580 | } |
||
581 | |||
582 | /**** Private generic kernel interface functions (guest calls) ****/ |
||
583 | |||
584 | /* Insert a guest task */ |
||
585 | static void EDF_private_insert(LEVEL l, PID p, TASK_MODEL *m) |
||
586 | { |
||
587 | EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
||
588 | EDF_task_des *td = &lev->tvec[p]; |
||
589 | JOB_TASK_MODEL *job; |
||
590 | |||
591 | if (m->pclass != JOB_PCLASS || (m->level != 0 && m->level != l) ) { |
||
592 | kern_raise(XINVALID_TASK, p); |
||
593 | return; |
||
594 | } |
||
595 | |||
596 | job = (JOB_TASK_MODEL *)m; |
||
597 | |||
598 | /* Insert task in the correct position */ |
||
599 | *iq_query_timespec(p, &lev->ready) = job->deadline; |
||
600 | iq_timespec_insert(p,&lev->ready); |
||
601 | proc_table[p].status = EDF_READY; |
||
602 | |||
603 | if (td->dl_timer != -1) { |
||
604 | kern_event_delete(td->dl_timer); |
||
605 | td->dl_timer = -1; |
||
606 | } |
||
607 | |||
608 | td->period = job->period; |
||
609 | |||
610 | if (!job->noraiseexc) { |
||
611 | td->dl_timer = kern_event_post(iq_query_timespec(p, &lev->ready), |
||
612 | EDF_timer_guest_deadline,(void *)p); |
||
613 | } |
||
614 | } |
||
615 | |||
616 | /* Dispatch a guest task */ |
||
617 | static void EDF_private_dispatch(LEVEL l, PID p, int nostop) |
||
618 | { |
||
619 | EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
||
620 | |||
621 | /* the task state is set to EXE by the scheduler() |
||
622 | we extract the task from the ready queue |
||
623 | NB: we can't assume that p is the first task in the queue!!! */ |
||
624 | iq_extract(p, &lev->ready); |
||
625 | } |
||
626 | |||
627 | /* Called when a guest task is preempted/out of budget */ |
||
628 | static void EDF_private_epilogue(LEVEL l, PID p) |
||
629 | { |
||
630 | EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
||
631 | |||
632 | /* the task has been preempted. it returns into the ready queue... */ |
||
633 | iq_timespec_insert(p,&lev->ready); |
||
634 | proc_table[p].status = EDF_READY; |
||
635 | } |
||
636 | |||
637 | /* Extract a guest task */ |
||
638 | static void EDF_private_extract(LEVEL l, PID p) |
||
639 | { |
||
640 | EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
||
641 | EDF_task_des *td = &lev->tvec[p]; |
||
642 | |||
643 | if (proc_table[p].status == EDF_READY) |
||
644 | iq_extract(p, &lev->ready); |
||
645 | |||
646 | /* we remove the deadline timer, because the slice is finished */ |
||
647 | if (td->dl_timer != -1) { |
||
648 | kern_event_delete(td->dl_timer); |
||
649 | td->dl_timer = -1; |
||
650 | } |
||
651 | |||
652 | } |
||
653 | |||
654 | |||
655 | /**** Level registration function ****/ |
||
656 | |||
657 | LEVEL EDF_register_level(int flags) |
||
658 | { |
||
659 | LEVEL l; /* the level that we register */ |
||
660 | EDF_level_des *lev; /* for readableness only */ |
||
661 | int i; |
||
662 | |||
663 | printk("EDF_register_level\n"); |
||
664 | |||
665 | /* request an entry in the level_table */ |
||
666 | l = level_alloc_descriptor(sizeof(EDF_level_des)); |
||
667 | |||
668 | lev = (EDF_level_des *)level_table[l]; |
||
669 | |||
670 | /* fill the standard descriptor */ |
||
671 | lev->l.private_insert = EDF_private_insert; |
||
672 | lev->l.private_extract = EDF_private_extract; |
||
673 | lev->l.private_dispatch = EDF_private_dispatch; |
||
674 | lev->l.private_epilogue = EDF_private_epilogue; |
||
675 | |||
676 | lev->l.public_scheduler = EDF_public_scheduler; |
||
677 | if (flags & EDF_ENABLE_GUARANTEE) |
||
678 | lev->l.public_guarantee = EDF_public_guarantee; |
||
679 | else |
||
680 | lev->l.public_guarantee = NULL; |
||
681 | |||
682 | lev->l.public_create = EDF_public_create; |
||
683 | lev->l.public_detach = EDF_public_detach; |
||
684 | lev->l.public_end = EDF_public_end; |
||
685 | lev->l.public_dispatch = EDF_public_dispatch; |
||
686 | lev->l.public_epilogue = EDF_public_epilogue; |
||
687 | lev->l.public_activate = EDF_public_activate; |
||
688 | lev->l.public_unblock = EDF_public_unblock; |
||
689 | lev->l.public_block = EDF_public_block; |
||
690 | lev->l.public_message = EDF_public_message; |
||
691 | |||
692 | iq_init(&lev->ready, &freedesc, 0); |
||
693 | |||
694 | lev->flags = flags; |
||
695 | if (lev->flags & EDF_ENABLE_WCET_EXCEPTION) { |
||
696 | lev->flags |= EDF_ENABLE_WCET_CHECK; |
||
697 | } |
||
698 | if (lev->flags & EDF_ENABLE_DL_EXCEPTION) { |
||
699 | lev->flags |= EDF_ENABLE_DL_CHECK; |
||
700 | } |
||
701 | |||
702 | lev->U = 0; |
||
703 | |||
704 | for (i=0;i<MAX_PROC;i++) { |
||
705 | EDF_task_des *td = &lev->tvec[i]; |
||
706 | td->flags = 0; |
||
707 | td->dl_timer = -1; |
||
708 | td->eop_timer = -1; |
||
709 | td->off_timer = -1; |
||
710 | td->dl_miss = 0; |
||
711 | td->wcet_miss = 0; |
||
712 | td->act_miss = 0; |
||
713 | td->nact = 0; |
||
714 | } |
||
715 | |||
716 | return l; |
||
717 | } |
||
718 | |||
719 | |||
720 | /**** Public utility functions ****/ |
||
721 | |||
722 | /* Get the bandwidth used by the level */ |
||
723 | bandwidth_t EDF_usedbandwidth(LEVEL l) |
||
724 | { |
||
725 | EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
||
726 | |||
727 | return lev->U; |
||
728 | } |
||
729 | |||
730 | /* Get the number of missed deadlines for a task */ |
||
731 | int EDF_get_dl_miss(PID p) |
||
732 | { |
||
733 | LEVEL l = proc_table[p].task_level; |
||
734 | EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
||
735 | EDF_task_des *td = &lev->tvec[p]; |
||
736 | |||
737 | return td->dl_miss; |
||
738 | } |
||
739 | |||
740 | /* Get the number of execution overruns for a task */ |
||
741 | int EDF_get_wcet_miss(PID p) |
||
742 | { |
||
743 | LEVEL l = proc_table[p].task_level; |
||
744 | EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
||
745 | EDF_task_des *td = &lev->tvec[p]; |
||
746 | |||
747 | return td->wcet_miss; |
||
748 | } |
||
749 | |||
750 | /* Get the number of skipped activations for a task */ |
||
751 | int EDF_get_act_miss(PID p) |
||
752 | { |
||
753 | LEVEL l = proc_table[p].task_level; |
||
754 | EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
||
755 | EDF_task_des *td = &lev->tvec[p]; |
||
756 | |||
757 | return td->act_miss; |
||
758 | } |
||
759 | |||
760 | /* Get the current number of queued activations for a task */ |
||
761 | int EDF_get_nact(PID p) |
||
762 | { |
||
763 | LEVEL l = proc_table[p].task_level; |
||
764 | |||
765 | EDF_level_des *lev = (EDF_level_des *)(level_table[l]); |
||
766 | EDF_task_des *td = &lev->tvec[p]; |
||
767 | |||
768 | return td->nact; |
||
769 | } |
||
770 |