Subversion Repositories shark

Rev

Rev 1036 | 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>
1689 fabio 58
#include <arch/stdio.h>
59
#include <arch/string.h>
961 pj 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