Subversion Repositories shark

Rev

Rev 387 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
2 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
 *   (see the web pages for full authors list)
13
 *
14
 * ReTiS Lab (Scuola Superiore S.Anna - Pisa - Italy)
15
 *
16
 * http://www.sssup.it
17
 * http://retis.sssup.it
18
 * http://shark.sssup.it
19
 */
20
 
21
/**
22
 ------------
445 giacomo 23
 CVS :        $Id: edf.c,v 1.12 2004-02-10 17:50:04 giacomo Exp $
2 pj 24
 
25
 File:        $File$
445 giacomo 26
 Revision:    $Revision: 1.12 $
27
 Last update: $Date: 2004-02-10 17:50:04 $
2 pj 28
 ------------
29
 
30
 This file contains the scheduling module EDF (Earliest Deadline First)
31
 
32
 Read edf.h for further details.
33
 
34
**/
35
 
36
/*
38 pj 37
 * Copyright (C) 2000,2002 Paolo Gai
2 pj 38
 *
39
 * This program is free software; you can redistribute it and/or modify
40
 * it under the terms of the GNU General Public License as published by
41
 * the Free Software Foundation; either version 2 of the License, or
42
 * (at your option) any later version.
43
 *
44
 * This program is distributed in the hope that it will be useful,
45
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
46
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
47
 * GNU General Public License for more details.
48
 *
49
 * You should have received a copy of the GNU General Public License
50
 * along with this program; if not, write to the Free Software
51
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
52
 *
53
 */
54
 
55
 
56
#include <modules/edf.h>
57
#include <ll/stdio.h>
58
#include <ll/string.h>
59
#include <kernel/model.h>
60
#include <kernel/descr.h>
61
#include <kernel/var.h>
62
#include <kernel/func.h>
63
 
353 giacomo 64
#include <tracer.h>
65
 
240 giacomo 66
//#define EDF_DEBUG
38 pj 67
#define edf_printf kern_printf
2 pj 68
 
69
/*+ Status used in the level +*/
70
#define EDF_READY         MODULE_STATUS_BASE    /*+ - Ready status        +*/
71
#define EDF_WCET_VIOLATED MODULE_STATUS_BASE+2  /*+ when wcet is finished +*/
72
#define EDF_WAIT          MODULE_STATUS_BASE+3  /*+ to wait the deadline  +*/
73
#define EDF_IDLE          MODULE_STATUS_BASE+4  /*+ to wait the deadline  +*/
74
#define EDF_ZOMBIE        MODULE_STATUS_BASE+5  /*+ to wait the free time +*/
75
 
76
/*+ flags +*/
77
#define EDF_FLAG_SPORADIC    1
78
#define EDF_FLAG_NORAISEEXC  2
212 giacomo 79
#define EDF_FLAG_SLEEP       4
2 pj 80
 
81
/*+ the level redefinition for the Earliest Deadline First level +*/
82
typedef struct {
83
  level_des l;     /*+ the standard level descriptor          +*/
84
 
85
  TIME period[MAX_PROC]; /*+ The task periods; the deadlines are
86
                       stored in the priority field           +*/
87
  int deadline_timer[MAX_PROC];
88
                   /*+ The task deadline timers               +*/
89
 
90
  int flag[MAX_PROC];
91
                   /*+ used to manage the JOB_TASK_MODEL and the
92
                       periodicity                            +*/
93
 
29 pj 94
  IQUEUE ready;     /*+ the ready queue                        +*/
2 pj 95
 
96
  int flags;       /*+ the init flags...                      +*/
97
 
98
  bandwidth_t U;   /*+ the used bandwidth                     +*/
99
 
100
} EDF_level_des;
101
 
102
 
103
static void EDF_timer_deadline(void *par)
104
{
105
  PID p = (PID) par;
106
  EDF_level_des *lev;
29 pj 107
  struct timespec *temp;
2 pj 108
 
109
  lev = (EDF_level_des *)level_table[proc_table[p].task_level];
110
 
240 giacomo 111
  #ifdef EDF_DEBUG
112
    edf_printf("(EDF:Dl TIMER:%d)",p);
113
  #endif
114
 
2 pj 115
  switch (proc_table[p].status) {
116
    case EDF_ZOMBIE:
117
      /* we finally put the task in the ready queue */
118
      proc_table[p].status = FREE;
29 pj 119
      iq_insertfirst(p,&freedesc);
2 pj 120
      /* and free the allocated bandwidth */
121
      lev->U -= (MAX_BANDWIDTH/lev->period[p]) * proc_table[p].wcet;
122
      break;
123
 
124
    case EDF_IDLE:
125
      /* tracer stuff */
385 giacomo 126
      TRACER_LOGEVENT(FTrace_EVT_task_timer,3,proc_table[p].context,proc_table[p].task_level);
2 pj 127
      /* similar to EDF_task_activate */
29 pj 128
      temp = iq_query_timespec(p,&lev->ready);
129
      ADDUSEC2TIMESPEC(lev->period[p], temp);
2 pj 130
      proc_table[p].status = EDF_READY;
29 pj 131
      iq_timespec_insert(p,&lev->ready);
132
      lev->deadline_timer[p] = kern_event_post(temp,
2 pj 133
                                               EDF_timer_deadline,
134
                                               (void *)p);
135
      event_need_reschedule();
136
      break;
137
 
138
    case EDF_WAIT:
139
      /* Without this, the task cannot be reactivated!!! */
140
      proc_table[p].status = SLEEP;
212 giacomo 141
 
142
      /* Reset the EDF_FLAG_SLEEP */
143
      lev->flag[p] &= ~EDF_FLAG_SLEEP;
144
 
2 pj 145
      break;
146
 
147
    default:
148
      /* else, a deadline miss occurred!!! */
445 giacomo 149
      TRACER_LOGEVENT(FTrace_EVT_task_deadline_miss,1,proc_table[p].context,0);
2 pj 150
      kern_raise(XDEADLINE_MISS,p);
151
  }
152
}
153
 
154
static void EDF_timer_guest_deadline(void *par)
155
{
156
  PID p = (PID) par;
157
 
240 giacomo 158
  #ifdef EDF_DEBUG
159
    edf_printf("(EDF:AAARRRGGGHHH!!!)");
160
  #endif
445 giacomo 161
  TRACER_LOGEVENT(FTrace_EVT_task_deadline_miss,1,proc_table[p].context,0);
2 pj 162
  kern_raise(XDEADLINE_MISS,p);
163
}
164
 
38 pj 165
/* The scheduler only gets the first task in the queue */
166
static PID EDF_public_scheduler(LEVEL l)
2 pj 167
{
168
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
29 pj 169
  return iq_query_first(&lev->ready);
2 pj 170
}
171
 
172
/* The on-line guarantee is enabled only if the appropriate flag is set... */
38 pj 173
static int EDF_public_guarantee(LEVEL l, bandwidth_t *freebandwidth)
2 pj 174
{
175
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
176
 
159 pj 177
  if (*freebandwidth >= lev->U) {
178
    *freebandwidth -= lev->U;
179
    return 1;
2 pj 180
  }
181
  else
159 pj 182
    return 0;
2 pj 183
}
184
 
38 pj 185
static int EDF_public_create(LEVEL l, PID p, TASK_MODEL *m)
2 pj 186
{
187
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
38 pj 188
  HARD_TASK_MODEL *h;
2 pj 189
 
38 pj 190
  if (m->pclass != HARD_PCLASS) return -1;
191
  if (m->level != 0 && m->level != l) return -1;
192
  h = (HARD_TASK_MODEL *)m;
193
  if (!h->wcet || !h->mit) return -1;
159 pj 194
 
195
  /* check the free bandwidth... */
196
  if (lev->flags & EDF_ENABLE_GUARANTEE) {
197
    bandwidth_t b;
198
    b = (MAX_BANDWIDTH / h->mit) * h->wcet;
199
 
200
    /* really update lev->U, checking an overflow... */
201
    if (MAX_BANDWIDTH - lev->U > b)
202
      lev->U += b;
203
    else
204
      return -1;
205
  }
206
 
38 pj 207
  /* now we know that m is a valid model */
2 pj 208
 
240 giacomo 209
  #ifdef EDF_DEBUG
210
    edf_printf("(EDF:PubCrt:%d)", p);
211
  #endif
2 pj 212
 
213
  lev->period[p] = h->mit;
212 giacomo 214
 
215
  lev->flag[p] = 0;
2 pj 216
 
217
  if (h->periodicity == APERIODIC)
212 giacomo 218
    lev->flag[p] |= EDF_FLAG_SPORADIC;
219
 
2 pj 220
  lev->deadline_timer[p] = -1;
221
 
222
  /* Enable wcet check */
223
  if (lev->flags & EDF_ENABLE_WCET_CHECK) {
224
    proc_table[p].avail_time = h->wcet;
225
    proc_table[p].wcet       = h->wcet;
226
    proc_table[p].control |= CONTROL_CAP;
227
  }
228
 
229
  return 0; /* OK, also if the task cannot be guaranteed... */
230
}
231
 
38 pj 232
static void EDF_public_detach(LEVEL l, PID p)
2 pj 233
{
234
  /* the EDF level doesn't introduce any dinamic allocated new field.
159 pj 235
     we have only to decrement the allocated bandwidth */
2 pj 236
 
237
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
238
 
240 giacomo 239
  #ifdef EDF_DEBUG
240
    edf_printf("(EDF:PubDet:%d)", p);
241
  #endif
38 pj 242
 
159 pj 243
  if (lev->flags & EDF_ENABLE_GUARANTEE) {
2 pj 244
    lev->U -= (MAX_BANDWIDTH / lev->period[p]) * proc_table[p].wcet;
159 pj 245
  }
2 pj 246
}
247
 
38 pj 248
static void EDF_public_dispatch(LEVEL l, PID p, int nostop)
2 pj 249
{
250
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
251
 
240 giacomo 252
  #ifdef EDF_DEBUG
253
    edf_printf("(EDF:PubDsp:%d)",p);
254
  #endif
2 pj 255
 
256
  /* the task state is set EXE by the scheduler()
257
     we extract the task from the ready queue
258
     NB: we can't assume that p is the first task in the queue!!! */
29 pj 259
  iq_extract(p, &lev->ready);
2 pj 260
}
261
 
38 pj 262
static void EDF_public_epilogue(LEVEL l, PID p)
2 pj 263
{
264
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
265
 
240 giacomo 266
  #ifdef EDF_DEBUG
267
    edf_printf("(EDF:PubEpi:%d)",p);
268
  #endif
2 pj 269
 
270
  /* check if the wcet is finished... */
271
  if ((lev->flags & EDF_ENABLE_WCET_CHECK) && proc_table[p].avail_time <= 0) {
272
    /* if it is, raise a XWCET_VIOLATION exception */
445 giacomo 273
    TRACER_LOGEVENT(FTrace_EVT_task_wcet_violation,1,proc_table[p].context,0);
2 pj 274
    kern_raise(XWCET_VIOLATION,p);
275
    proc_table[p].status = EDF_WCET_VIOLATED;
276
  }
277
  else {
278
    /* the task has been preempted. it returns into the ready queue... */
29 pj 279
    iq_timespec_insert(p,&lev->ready);
2 pj 280
    proc_table[p].status = EDF_READY;
281
  }
282
}
283
 
38 pj 284
static void EDF_public_activate(LEVEL l, PID p)
2 pj 285
{
286
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
29 pj 287
  struct timespec *temp;
2 pj 288
 
240 giacomo 289
  #ifdef EDF_DEBUG
290
    edf_printf("(EDF:PubAct:%d)", p);
291
  #endif
38 pj 292
 
212 giacomo 293
  if (lev->flag[p] & EDF_FLAG_SLEEP) {
294
    lev->flag[p] &= ~EDF_FLAG_SLEEP;
295
    if (!(lev->flag[p] & EDF_FLAG_SPORADIC))
296
      proc_table[p].status = EDF_IDLE;
297
    return;
298
  }
299
 
2 pj 300
  if (proc_table[p].status == EDF_WAIT) {
301
    kern_raise(XACTIVATION,p);
302
    return;
303
  }
212 giacomo 304
 
2 pj 305
  /* Test if we are trying to activate a non sleeping task    */
306
  /* Ignore this; the task is already active                  */
307
  if (proc_table[p].status != SLEEP &&
308
      proc_table[p].status != EDF_WCET_VIOLATED)
309
    return;
310
 
311
 
312
  /* see also EDF_timer_deadline */
29 pj 313
  temp = iq_query_timespec(p, &lev->ready);
38 pj 314
  kern_gettime(temp);
29 pj 315
  ADDUSEC2TIMESPEC(lev->period[p], temp);
2 pj 316
 
317
  /* Insert task in the correct position */
318
  proc_table[p].status = EDF_READY;
29 pj 319
  iq_timespec_insert(p,&lev->ready);
2 pj 320
 
321
  /* Set the deadline timer */
29 pj 322
  lev->deadline_timer[p] = kern_event_post(temp,
2 pj 323
                                           EDF_timer_deadline,
324
                                           (void *)p);
325
}
326
 
38 pj 327
static void EDF_public_unblock(LEVEL l, PID p)
2 pj 328
{
329
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
330
 
38 pj 331
  /* Similar to EDF_task_activate,
332
     but we don't check in what state the task is */
2 pj 333
 
334
  /* Insert task in the coEDFect position */
335
  proc_table[p].status = EDF_READY;
29 pj 336
  iq_timespec_insert(p,&lev->ready);
2 pj 337
}
338
 
38 pj 339
static void EDF_public_block(LEVEL l, PID p)
2 pj 340
{
341
  /* Extract the running task from the level
342
     . we have already extract it from the ready queue at the dispatch time.
343
     . the capacity event have to be removed by the generic kernel
344
     . the wcet don't need modification...
345
     . the state of the task is set by the calling function
346
     . the deadline must remain...
347
 
348
     So, we do nothing!!!
349
  */
350
}
351
 
38 pj 352
static int EDF_public_message(LEVEL l, PID p, void *m)
2 pj 353
{
354
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
355
 
240 giacomo 356
  /* task_message evaluation */
212 giacomo 357
  switch((long)(m)) {
2 pj 358
 
240 giacomo 359
    /* task_endcycle */
212 giacomo 360
    case (long)(NULL):
2 pj 361
 
240 giacomo 362
      #ifdef EDF_DEBUG
363
        edf_printf("(EDF:EndCyc:%d)",p);
212 giacomo 364
      #endif
2 pj 365
 
212 giacomo 366
      /* the task has terminated his job before it consume the wcet. All OK! */
367
      if (!(lev->flag[p] & EDF_FLAG_SPORADIC) &&
368
          !(lev->flag[p] & EDF_FLAG_SLEEP))
369
        proc_table[p].status = EDF_IDLE;
370
      else
371
        proc_table[p].status = EDF_WAIT;
38 pj 372
 
212 giacomo 373
      /* we reset the capacity counters... */
374
      if (lev->flags & EDF_ENABLE_WCET_CHECK)
375
        proc_table[p].avail_time = proc_table[p].wcet;
38 pj 376
 
212 giacomo 377
      jet_update_endcycle(); /* Update the Jet data... */
385 giacomo 378
      TRACER_LOGEVENT(FTrace_EVT_task_end_cycle,3,proc_table[p].context,l);
212 giacomo 379
 
380
      break;
381
 
240 giacomo 382
    /* task_disable */
212 giacomo 383
    case 1:
384
 
240 giacomo 385
      #ifdef EDF_DEBUG
386
        edf_printf("(EDF:Dis:%d)",p);
212 giacomo 387
      #endif
388
 
389
      /* Set the EDF_FLAG_SLEEP, in the next endcycle the task will
390
         be set in EDF_WAIT */
391
      lev->flag[p] |= EDF_FLAG_SLEEP;
392
 
393
      /* If the task is EDF_IDLE, set to EDF_WAIT now */
394
      if (proc_table[p].status == EDF_IDLE)
395
        proc_table[p].status = EDF_WAIT;
396
 
385 giacomo 397
      TRACER_LOGEVENT(FTrace_EVT_task_disable,3,proc_table[p].context,l);
214 giacomo 398
 
212 giacomo 399
      break;
400
 
401
  }
402
 
38 pj 403
  return 0;
212 giacomo 404
 
2 pj 405
}
406
 
38 pj 407
static void EDF_public_end(LEVEL l, PID p)
2 pj 408
{
409
  proc_table[p].status = EDF_ZOMBIE;
410
 
411
  /* When the deadline timer fire, it put the task descriptor in
412
     the free queue, and free the allocated bandwidth... */
413
}
414
 
38 pj 415
static void EDF_private_insert(LEVEL l, PID p, TASK_MODEL *m)
2 pj 416
{
417
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
38 pj 418
  JOB_TASK_MODEL *job;
2 pj 419
 
38 pj 420
  if (m->pclass != JOB_PCLASS || (m->level != 0 && m->level != l) ) {
421
    kern_raise(XINVALID_TASK, p);
422
    return;
423
  }
2 pj 424
 
38 pj 425
  job = (JOB_TASK_MODEL *)m;
2 pj 426
 
38 pj 427
  /* Insert task in the correct position */
29 pj 428
  *iq_query_timespec(p, &lev->ready) = job->deadline;
38 pj 429
  iq_timespec_insert(p,&lev->ready);
430
  proc_table[p].status = EDF_READY;
2 pj 431
 
432
  lev->deadline_timer[p] = -1;
433
 
38 pj 434
  lev->period[p] = job->period;
435
 
436
  /* Set the deadline timer */
387 giacomo 437
  if (job->noraiseexc)
2 pj 438
    lev->flag[p] = EDF_FLAG_NORAISEEXC;
38 pj 439
  else {
2 pj 440
    lev->flag[p] = 0;
38 pj 441
    lev->deadline_timer[p] = kern_event_post(iq_query_timespec(p, &lev->ready),
442
                                             EDF_timer_guest_deadline,
443
                                             (void *)p);
444
  }
2 pj 445
}
446
 
38 pj 447
static void EDF_private_dispatch(LEVEL l, PID p, int nostop)
2 pj 448
{
449
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
450
 
451
  /* the task state is set to EXE by the scheduler()
452
     we extract the task from the ready queue
453
     NB: we can't assume that p is the first task in the queue!!! */
29 pj 454
  iq_extract(p, &lev->ready);
2 pj 455
}
456
 
38 pj 457
static void EDF_private_epilogue(LEVEL l, PID p)
2 pj 458
{
459
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
460
 
461
  /* the task has been preempted. it returns into the ready queue... */
29 pj 462
  iq_timespec_insert(p,&lev->ready);
2 pj 463
  proc_table[p].status = EDF_READY;
464
}
465
 
38 pj 466
static void EDF_private_extract(LEVEL l, PID p)
2 pj 467
{
468
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
469
 
470
  if (proc_table[p].status == EDF_READY)
29 pj 471
    iq_extract(p, &lev->ready);
2 pj 472
 
473
  /* we remove the deadline timer, because the slice is finished */
474
  if (lev->deadline_timer[p] != NIL) {
38 pj 475
    kern_event_delete(lev->deadline_timer[p]);
2 pj 476
    lev->deadline_timer[p] = NIL;
477
  }
478
 
479
}
480
 
481
 
482
/* Registration functions */
483
 
484
/*+ Registration function:
485
    int flags                 the init flags ... see edf.h +*/
38 pj 486
LEVEL EDF_register_level(int flags)
2 pj 487
{
488
  LEVEL l;            /* the level that we register */
489
  EDF_level_des *lev;  /* for readableness only */
490
  PID i;              /* a counter */
491
 
492
  printk("EDF_register_level\n");
493
 
494
  /* request an entry in the level_table */
38 pj 495
  l = level_alloc_descriptor(sizeof(EDF_level_des));
2 pj 496
 
38 pj 497
  lev = (EDF_level_des *)level_table[l];
2 pj 498
 
499
  /* fill the standard descriptor */
38 pj 500
  lev->l.private_insert   = EDF_private_insert;
501
  lev->l.private_extract  = EDF_private_extract;
502
  lev->l.private_dispatch = EDF_private_dispatch;
503
  lev->l.private_epilogue = EDF_private_epilogue;
2 pj 504
 
38 pj 505
  lev->l.public_scheduler = EDF_public_scheduler;
2 pj 506
  if (flags & EDF_ENABLE_GUARANTEE)
38 pj 507
    lev->l.public_guarantee = EDF_public_guarantee;
2 pj 508
  else
38 pj 509
    lev->l.public_guarantee = NULL;
2 pj 510
 
38 pj 511
  lev->l.public_create    = EDF_public_create;
512
  lev->l.public_detach    = EDF_public_detach;
513
  lev->l.public_end       = EDF_public_end;
514
  lev->l.public_dispatch  = EDF_public_dispatch;
515
  lev->l.public_epilogue  = EDF_public_epilogue;
516
  lev->l.public_activate  = EDF_public_activate;
517
  lev->l.public_unblock   = EDF_public_unblock;
518
  lev->l.public_block     = EDF_public_block;
519
  lev->l.public_message   = EDF_public_message;
2 pj 520
 
521
  /* fill the EDF descriptor part */
522
  for(i=0; i<MAX_PROC; i++) {
523
    lev->period[i]         = 0;
524
    lev->deadline_timer[i] = -1;
525
    lev->flag[i]          = 0;
526
  }
527
 
29 pj 528
  iq_init(&lev->ready, &freedesc, 0);
159 pj 529
  lev->flags = flags;
2 pj 530
  lev->U     = 0;
38 pj 531
 
532
  return l;
2 pj 533
}
534
 
535
bandwidth_t EDF_usedbandwidth(LEVEL l)
536
{
537
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
38 pj 538
 
539
  return lev->U;
2 pj 540
}
541