Subversion Repositories shark

Rev

Rev 29 | 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
 ------------
38 pj 23
 CVS :        $Id: edf.c,v 1.4 2003-01-07 17:07:50 pj Exp $
2 pj 24
 
25
 File:        $File$
38 pj 26
 Revision:    $Revision: 1.4 $
27
 Last update: $Date: 2003-01-07 17:07:50 $
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
#include <kernel/trace.h>
64
 
38 pj 65
//#define EDFDEBUG
66
#define edf_printf kern_printf
2 pj 67
 
68
/*+ Status used in the level +*/
69
#define EDF_READY         MODULE_STATUS_BASE    /*+ - Ready status        +*/
70
#define EDF_WCET_VIOLATED MODULE_STATUS_BASE+2  /*+ when wcet is finished +*/
71
#define EDF_WAIT          MODULE_STATUS_BASE+3  /*+ to wait the deadline  +*/
72
#define EDF_IDLE          MODULE_STATUS_BASE+4  /*+ to wait the deadline  +*/
73
#define EDF_ZOMBIE        MODULE_STATUS_BASE+5  /*+ to wait the free time +*/
74
 
75
/*+ flags +*/
76
#define EDF_FLAG_SPORADIC    1
77
#define EDF_FLAG_NORAISEEXC  2
78
 
79
/*+ the level redefinition for the Earliest Deadline First level +*/
80
typedef struct {
81
  level_des l;     /*+ the standard level descriptor          +*/
82
 
83
  TIME period[MAX_PROC]; /*+ The task periods; the deadlines are
84
                       stored in the priority field           +*/
85
  int deadline_timer[MAX_PROC];
86
                   /*+ The task deadline timers               +*/
87
 
88
  int flag[MAX_PROC];
89
                   /*+ used to manage the JOB_TASK_MODEL and the
90
                       periodicity                            +*/
91
 
29 pj 92
  IQUEUE ready;     /*+ the ready queue                        +*/
2 pj 93
 
94
  int flags;       /*+ the init flags...                      +*/
95
 
96
  bandwidth_t U;   /*+ the used bandwidth                     +*/
97
 
98
} EDF_level_des;
99
 
100
 
101
static void EDF_timer_deadline(void *par)
102
{
103
  PID p = (PID) par;
104
  EDF_level_des *lev;
29 pj 105
  struct timespec *temp;
2 pj 106
 
38 pj 107
#ifdef EDFDEBUG
2 pj 108
  edf_printf("$");
38 pj 109
#endif
2 pj 110
 
111
  lev = (EDF_level_des *)level_table[proc_table[p].task_level];
112
 
113
  switch (proc_table[p].status) {
114
    case EDF_ZOMBIE:
115
      /* we finally put the task in the ready queue */
116
      proc_table[p].status = FREE;
29 pj 117
      iq_insertfirst(p,&freedesc);
2 pj 118
      /* and free the allocated bandwidth */
119
      lev->U -= (MAX_BANDWIDTH/lev->period[p]) * proc_table[p].wcet;
120
      break;
121
 
122
    case EDF_IDLE:
123
      /* tracer stuff */
124
      trc_logevent(TRC_INTACTIVATION,&p);
125
      /* similar to EDF_task_activate */
29 pj 126
      temp = iq_query_timespec(p,&lev->ready);
127
      ADDUSEC2TIMESPEC(lev->period[p], temp);
2 pj 128
      proc_table[p].status = EDF_READY;
29 pj 129
      iq_timespec_insert(p,&lev->ready);
130
      lev->deadline_timer[p] = kern_event_post(temp,
2 pj 131
                                               EDF_timer_deadline,
132
                                               (void *)p);
38 pj 133
#ifdef EDFDEBUG
29 pj 134
      edf_printf("(dline p%d ev%d %d.%d)",(int)p,(int)lev->deadline_timer[p],(int)temp->tv_sec,(int)temp->tv_nsec/1000);
38 pj 135
#endif
2 pj 136
      event_need_reschedule();
137
      break;
138
 
139
    case EDF_WAIT:
140
      /* Without this, the task cannot be reactivated!!! */
141
      proc_table[p].status = SLEEP;
142
      break;
143
 
144
    default:
145
      /* else, a deadline miss occurred!!! */
38 pj 146
#ifdef EDFDEBUG
2 pj 147
      edf_printf("\nstatus %d\n", (int)proc_table[p].status);
148
      edf_printf("timer_deadline:AAARRRGGGHHH!!!");
38 pj 149
#endif
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
 
38 pj 158
#ifdef EDFDEBUG
2 pj 159
  edf_printf("AAARRRGGGHHH!!!");
38 pj 160
#endif
2 pj 161
  kern_raise(XDEADLINE_MISS,p);
162
}
163
 
38 pj 164
/* The scheduler only gets the first task in the queue */
165
static PID EDF_public_scheduler(LEVEL l)
2 pj 166
{
167
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
168
 
38 pj 169
#ifdef EDFDEBUG
170
  edf_printf("(s%d)", iq_query_first(&lev->ready));
171
#endif
2 pj 172
 
29 pj 173
  return iq_query_first(&lev->ready);
2 pj 174
}
175
 
176
/* The on-line guarantee is enabled only if the appropriate flag is set... */
38 pj 177
static int EDF_public_guarantee(LEVEL l, bandwidth_t *freebandwidth)
2 pj 178
{
179
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
180
 
181
  if (lev->flags & EDF_FAILED_GUARANTEE) {
182
    *freebandwidth = 0;
183
    return 0;
184
  }
185
  else
186
    if (*freebandwidth >= lev->U) {
187
      *freebandwidth -= lev->U;
188
      return 1;
189
    }
190
    else
191
      return 0;
192
 
193
}
194
 
38 pj 195
static int EDF_public_create(LEVEL l, PID p, TASK_MODEL *m)
2 pj 196
{
197
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
38 pj 198
  HARD_TASK_MODEL *h;
2 pj 199
 
38 pj 200
  if (m->pclass != HARD_PCLASS) return -1;
201
  if (m->level != 0 && m->level != l) return -1;
202
  h = (HARD_TASK_MODEL *)m;
203
  if (!h->wcet || !h->mit) return -1;
204
  /* now we know that m is a valid model */
2 pj 205
 
38 pj 206
#ifdef EDFDEBUG
207
  edf_printf("(cr%d)", p);
208
#endif
2 pj 209
 
210
  lev->period[p] = h->mit;
211
 
212
  if (h->periodicity == APERIODIC)
213
    lev->flag[p] = EDF_FLAG_SPORADIC;
214
  else
215
    lev->flag[p] = 0;
216
  lev->deadline_timer[p] = -1;
217
 
218
  /* Enable wcet check */
219
  if (lev->flags & EDF_ENABLE_WCET_CHECK) {
220
    proc_table[p].avail_time = h->wcet;
221
    proc_table[p].wcet       = h->wcet;
222
    proc_table[p].control |= CONTROL_CAP;
223
  }
224
 
225
  /* update the bandwidth... */
226
  if (lev->flags & EDF_ENABLE_GUARANTEE) {
227
    bandwidth_t b;
228
    b = (MAX_BANDWIDTH / h->mit) * h->wcet;
229
 
230
    /* really update lev->U, checking an overflow... */
231
    if (MAX_BANDWIDTH - lev->U > b)
232
      lev->U += b;
233
    else
234
      /* The task can NOT be guaranteed (U>MAX_BANDWIDTH)...
235
         in this case, we don't raise an exception... in fact, after the
236
         EDF_task_create the task_create will call level_guarantee that return
237
         -1... return -1 in EDF_task_create isn't correct, because:
238
           . generally, the guarantee must be done when also the resources
239
             are registered
240
           . returning -1 will cause the task_create to return with an errno
241
             ETASK_CREATE instead of ENO_GUARANTEE!!!
242
 
243
         Why I use the flag??? because if the lev->U overflows, if i.e. I set
244
         it to MAX_BANDWIDTH, I lose the correct allocated bandwidth...
245
      */
246
      lev->flags |= EDF_FAILED_GUARANTEE;
247
  }
248
 
249
  return 0; /* OK, also if the task cannot be guaranteed... */
250
}
251
 
38 pj 252
static void EDF_public_detach(LEVEL l, PID p)
2 pj 253
{
254
  /* the EDF level doesn't introduce any dinamic allocated new field.
255
     we have only to reset the NO_GUARANTEE FIELD and decrement the allocated
256
     bandwidth */
257
 
258
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
259
 
38 pj 260
#ifdef EDFDEBUG
261
  edf_printf("(det%d)", p);
262
#endif
263
 
2 pj 264
  if (lev->flags & EDF_FAILED_GUARANTEE)
265
    lev->flags &= ~EDF_FAILED_GUARANTEE;
266
  else
267
    lev->U -= (MAX_BANDWIDTH / lev->period[p]) * proc_table[p].wcet;
268
}
269
 
38 pj 270
static void EDF_public_dispatch(LEVEL l, PID p, int nostop)
2 pj 271
{
272
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
273
 
38 pj 274
#ifdef EDFDEBUG
2 pj 275
  edf_printf("(disp p%d %d.%d)",(int)p,(int)schedule_time.tv_sec,(int)schedule_time.tv_nsec/1000);
38 pj 276
#endif
2 pj 277
 
278
  /* the task state is set EXE by the scheduler()
279
     we extract the task from the ready queue
280
     NB: we can't assume that p is the first task in the queue!!! */
29 pj 281
  iq_extract(p, &lev->ready);
2 pj 282
}
283
 
38 pj 284
static void EDF_public_epilogue(LEVEL l, PID p)
2 pj 285
{
286
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
287
 
38 pj 288
#ifdef EDFDEBUG
2 pj 289
  edf_printf("(epil p%d %d.%d)",p,(int)schedule_time.tv_sec,(int)schedule_time.tv_nsec/1000);
38 pj 290
#endif
2 pj 291
 
292
  /* check if the wcet is finished... */
293
  if ((lev->flags & EDF_ENABLE_WCET_CHECK) && proc_table[p].avail_time <= 0) {
294
    /* if it is, raise a XWCET_VIOLATION exception */
295
    kern_raise(XWCET_VIOLATION,p);
296
    proc_table[p].status = EDF_WCET_VIOLATED;
297
  }
298
  else {
299
    /* the task has been preempted. it returns into the ready queue... */
29 pj 300
    iq_timespec_insert(p,&lev->ready);
2 pj 301
    proc_table[p].status = EDF_READY;
302
  }
303
}
304
 
38 pj 305
static void EDF_public_activate(LEVEL l, PID p)
2 pj 306
{
307
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
29 pj 308
  struct timespec *temp;
2 pj 309
 
38 pj 310
#ifdef EDFDEBUG
311
  edf_printf("(act%d)", p);
312
#endif
313
 
2 pj 314
  if (proc_table[p].status == EDF_WAIT) {
315
    kern_raise(XACTIVATION,p);
316
    return;
317
  }
318
 
319
  /* Test if we are trying to activate a non sleeping task    */
320
  /* Ignore this; the task is already active                  */
321
  if (proc_table[p].status != SLEEP &&
322
      proc_table[p].status != EDF_WCET_VIOLATED)
323
    return;
324
 
325
 
326
  /* see also EDF_timer_deadline */
29 pj 327
  temp = iq_query_timespec(p, &lev->ready);
38 pj 328
  kern_gettime(temp);
29 pj 329
  ADDUSEC2TIMESPEC(lev->period[p], temp);
2 pj 330
 
331
  /* Insert task in the correct position */
332
  proc_table[p].status = EDF_READY;
29 pj 333
  iq_timespec_insert(p,&lev->ready);
2 pj 334
 
335
  /* Set the deadline timer */
29 pj 336
  lev->deadline_timer[p] = kern_event_post(temp,
2 pj 337
                                           EDF_timer_deadline,
338
                                           (void *)p);
38 pj 339
#ifdef EDFDEBUG
29 pj 340
  edf_printf("(dline p%d ev%d %d.%d)",p,(int)lev->deadline_timer[p],(int)temp->tv_sec,(int)temp->tv_nsec/1000);
38 pj 341
#endif
2 pj 342
}
343
 
38 pj 344
static void EDF_public_unblock(LEVEL l, PID p)
2 pj 345
{
346
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
347
 
38 pj 348
  /* Similar to EDF_task_activate,
349
     but we don't check in what state the task is */
2 pj 350
 
351
  /* Insert task in the coEDFect position */
352
  proc_table[p].status = EDF_READY;
29 pj 353
  iq_timespec_insert(p,&lev->ready);
2 pj 354
}
355
 
38 pj 356
static void EDF_public_block(LEVEL l, PID p)
2 pj 357
{
358
  /* Extract the running task from the level
359
     . we have already extract it from the ready queue at the dispatch time.
360
     . the capacity event have to be removed by the generic kernel
361
     . the wcet don't need modification...
362
     . the state of the task is set by the calling function
363
     . the deadline must remain...
364
 
365
     So, we do nothing!!!
366
  */
367
}
368
 
38 pj 369
static int EDF_public_message(LEVEL l, PID p, void *m)
2 pj 370
{
371
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
372
 
38 pj 373
#ifdef EDFDEBUG
2 pj 374
  edf_printf("(ecyc p%d %d.%d)",p,(int)schedule_time.tv_sec,(int)schedule_time.tv_nsec/1000);
38 pj 375
#endif
2 pj 376
 
377
  /* the task has terminated his job before it consume the wcet. All OK! */
38 pj 378
  if (!lev->flag[p] & EDF_FLAG_SPORADIC)
379
    proc_table[p].status = EDF_IDLE;
380
  else
2 pj 381
    proc_table[p].status = EDF_WAIT;
382
 
383
  /* we reset the capacity counters... */
384
  if (lev->flags & EDF_ENABLE_WCET_CHECK)
385
    proc_table[p].avail_time = proc_table[p].wcet;
386
 
38 pj 387
  jet_update_endcycle(); /* Update the Jet data... */
388
  trc_logevent(TRC_ENDCYCLE,&exec_shadow); /* tracer stuff */
389
 
2 pj 390
  /* when the deadline timer fire, it recognize the situation and set
38 pj 391
     correctly all the stuffs (like reactivation, sleep, etc... ) */
392
 
393
  return 0;
2 pj 394
}
395
 
38 pj 396
static void EDF_public_end(LEVEL l, PID p)
2 pj 397
{
398
  proc_table[p].status = EDF_ZOMBIE;
399
 
400
  /* When the deadline timer fire, it put the task descriptor in
401
     the free queue, and free the allocated bandwidth... */
402
}
403
 
38 pj 404
static void EDF_private_insert(LEVEL l, PID p, TASK_MODEL *m)
2 pj 405
{
406
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
38 pj 407
  JOB_TASK_MODEL *job;
2 pj 408
 
38 pj 409
  if (m->pclass != JOB_PCLASS || (m->level != 0 && m->level != l) ) {
410
    kern_raise(XINVALID_TASK, p);
411
    return;
412
  }
2 pj 413
 
38 pj 414
  job = (JOB_TASK_MODEL *)m;
2 pj 415
 
38 pj 416
  /* Insert task in the correct position */
29 pj 417
  *iq_query_timespec(p, &lev->ready) = job->deadline;
38 pj 418
  iq_timespec_insert(p,&lev->ready);
419
  proc_table[p].status = EDF_READY;
2 pj 420
 
421
  lev->deadline_timer[p] = -1;
422
 
38 pj 423
  lev->period[p] = job->period;
424
 
425
  /* Set the deadline timer */
426
  if (!(job->noraiseexc))
2 pj 427
    lev->flag[p] = EDF_FLAG_NORAISEEXC;
38 pj 428
  else {
2 pj 429
    lev->flag[p] = 0;
38 pj 430
    lev->deadline_timer[p] = kern_event_post(iq_query_timespec(p, &lev->ready),
431
                                             EDF_timer_guest_deadline,
432
                                             (void *)p);
433
  }
2 pj 434
}
435
 
38 pj 436
static void EDF_private_dispatch(LEVEL l, PID p, int nostop)
2 pj 437
{
438
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
439
 
440
  /* the task state is set to EXE by the scheduler()
441
     we extract the task from the ready queue
442
     NB: we can't assume that p is the first task in the queue!!! */
29 pj 443
  iq_extract(p, &lev->ready);
2 pj 444
}
445
 
38 pj 446
static void EDF_private_epilogue(LEVEL l, PID p)
2 pj 447
{
448
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
449
 
450
  /* the task has been preempted. it returns into the ready queue... */
29 pj 451
  iq_timespec_insert(p,&lev->ready);
2 pj 452
  proc_table[p].status = EDF_READY;
453
}
454
 
38 pj 455
static void EDF_private_extract(LEVEL l, PID p)
2 pj 456
{
457
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
458
 
38 pj 459
#ifdef EDFDEBUG
460
  edf_printf("EDF_guest_end: dline timer %d\n",lev->deadline_timer[p]);
461
#endif
2 pj 462
  if (proc_table[p].status == EDF_READY)
29 pj 463
    iq_extract(p, &lev->ready);
2 pj 464
 
465
  /* we remove the deadline timer, because the slice is finished */
466
  if (lev->deadline_timer[p] != NIL) {
38 pj 467
    kern_event_delete(lev->deadline_timer[p]);
2 pj 468
    lev->deadline_timer[p] = NIL;
469
  }
470
 
471
}
472
 
473
 
474
/* Registration functions */
475
 
476
/*+ Registration function:
477
    int flags                 the init flags ... see edf.h +*/
38 pj 478
LEVEL EDF_register_level(int flags)
2 pj 479
{
480
  LEVEL l;            /* the level that we register */
481
  EDF_level_des *lev;  /* for readableness only */
482
  PID i;              /* a counter */
483
 
484
  printk("EDF_register_level\n");
485
 
486
  /* request an entry in the level_table */
38 pj 487
  l = level_alloc_descriptor(sizeof(EDF_level_des));
2 pj 488
 
38 pj 489
  lev = (EDF_level_des *)level_table[l];
2 pj 490
 
491
  printk("    lev=%d\n",(int)lev);
492
 
493
  /* fill the standard descriptor */
38 pj 494
  lev->l.private_insert   = EDF_private_insert;
495
  lev->l.private_extract  = EDF_private_extract;
496
  lev->l.private_dispatch = EDF_private_dispatch;
497
  lev->l.private_epilogue = EDF_private_epilogue;
2 pj 498
 
38 pj 499
  lev->l.public_scheduler = EDF_public_scheduler;
2 pj 500
  if (flags & EDF_ENABLE_GUARANTEE)
38 pj 501
    lev->l.public_guarantee = EDF_public_guarantee;
2 pj 502
  else
38 pj 503
    lev->l.public_guarantee = NULL;
2 pj 504
 
38 pj 505
  lev->l.public_create    = EDF_public_create;
506
  lev->l.public_detach    = EDF_public_detach;
507
  lev->l.public_end       = EDF_public_end;
508
  lev->l.public_dispatch  = EDF_public_dispatch;
509
  lev->l.public_epilogue  = EDF_public_epilogue;
510
  lev->l.public_activate  = EDF_public_activate;
511
  lev->l.public_unblock   = EDF_public_unblock;
512
  lev->l.public_block     = EDF_public_block;
513
  lev->l.public_message   = EDF_public_message;
2 pj 514
 
515
  /* fill the EDF descriptor part */
516
  for(i=0; i<MAX_PROC; i++) {
517
    lev->period[i]         = 0;
518
    lev->deadline_timer[i] = -1;
519
    lev->flag[i]          = 0;
520
  }
521
 
29 pj 522
  iq_init(&lev->ready, &freedesc, 0);
2 pj 523
  lev->flags = flags & 0x07;
524
  lev->U     = 0;
38 pj 525
 
526
  return l;
2 pj 527
}
528
 
529
bandwidth_t EDF_usedbandwidth(LEVEL l)
530
{
531
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
38 pj 532
 
533
  return lev->U;
2 pj 534
}
535