Subversion Repositories shark

Rev

Rev 240 | 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
 ------------
353 giacomo 23
 CVS :        $Id: edf.c,v 1.9 2003-12-10 16:55:00 giacomo Exp $
2 pj 24
 
25
 File:        $File$
353 giacomo 26
 Revision:    $Revision: 1.9 $
27
 Last update: $Date: 2003-12-10 16:55:00 $
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 */
353 giacomo 126
      TRACER_LOGEVENT(FTrace_EVT_task_timer,3,p,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!!! */
149
      kern_raise(XDEADLINE_MISS,p);
150
  }
151
}
152
 
153
static void EDF_timer_guest_deadline(void *par)
154
{
155
  PID p = (PID) par;
156
 
240 giacomo 157
  #ifdef EDF_DEBUG
158
    edf_printf("(EDF:AAARRRGGGHHH!!!)");
159
  #endif
2 pj 160
  kern_raise(XDEADLINE_MISS,p);
161
}
162
 
38 pj 163
/* The scheduler only gets the first task in the queue */
164
static PID EDF_public_scheduler(LEVEL l)
2 pj 165
{
166
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
29 pj 167
  return iq_query_first(&lev->ready);
2 pj 168
}
169
 
170
/* The on-line guarantee is enabled only if the appropriate flag is set... */
38 pj 171
static int EDF_public_guarantee(LEVEL l, bandwidth_t *freebandwidth)
2 pj 172
{
173
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
174
 
159 pj 175
  if (*freebandwidth >= lev->U) {
176
    *freebandwidth -= lev->U;
177
    return 1;
2 pj 178
  }
179
  else
159 pj 180
    return 0;
2 pj 181
}
182
 
38 pj 183
static int EDF_public_create(LEVEL l, PID p, TASK_MODEL *m)
2 pj 184
{
185
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
38 pj 186
  HARD_TASK_MODEL *h;
2 pj 187
 
38 pj 188
  if (m->pclass != HARD_PCLASS) return -1;
189
  if (m->level != 0 && m->level != l) return -1;
190
  h = (HARD_TASK_MODEL *)m;
191
  if (!h->wcet || !h->mit) return -1;
159 pj 192
 
193
  /* check the free bandwidth... */
194
  if (lev->flags & EDF_ENABLE_GUARANTEE) {
195
    bandwidth_t b;
196
    b = (MAX_BANDWIDTH / h->mit) * h->wcet;
197
 
198
    /* really update lev->U, checking an overflow... */
199
    if (MAX_BANDWIDTH - lev->U > b)
200
      lev->U += b;
201
    else
202
      return -1;
203
  }
204
 
38 pj 205
  /* now we know that m is a valid model */
2 pj 206
 
240 giacomo 207
  #ifdef EDF_DEBUG
208
    edf_printf("(EDF:PubCrt:%d)", p);
209
  #endif
2 pj 210
 
211
  lev->period[p] = h->mit;
212 giacomo 212
 
213
  lev->flag[p] = 0;
2 pj 214
 
215
  if (h->periodicity == APERIODIC)
212 giacomo 216
    lev->flag[p] |= EDF_FLAG_SPORADIC;
217
 
2 pj 218
  lev->deadline_timer[p] = -1;
219
 
220
  /* Enable wcet check */
221
  if (lev->flags & EDF_ENABLE_WCET_CHECK) {
222
    proc_table[p].avail_time = h->wcet;
223
    proc_table[p].wcet       = h->wcet;
224
    proc_table[p].control |= CONTROL_CAP;
225
  }
226
 
227
  return 0; /* OK, also if the task cannot be guaranteed... */
228
}
229
 
38 pj 230
static void EDF_public_detach(LEVEL l, PID p)
2 pj 231
{
232
  /* the EDF level doesn't introduce any dinamic allocated new field.
159 pj 233
     we have only to decrement the allocated bandwidth */
2 pj 234
 
235
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
236
 
240 giacomo 237
  #ifdef EDF_DEBUG
238
    edf_printf("(EDF:PubDet:%d)", p);
239
  #endif
38 pj 240
 
159 pj 241
  if (lev->flags & EDF_ENABLE_GUARANTEE) {
2 pj 242
    lev->U -= (MAX_BANDWIDTH / lev->period[p]) * proc_table[p].wcet;
159 pj 243
  }
2 pj 244
}
245
 
38 pj 246
static void EDF_public_dispatch(LEVEL l, PID p, int nostop)
2 pj 247
{
248
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
249
 
240 giacomo 250
  #ifdef EDF_DEBUG
251
    edf_printf("(EDF:PubDsp:%d)",p);
252
  #endif
2 pj 253
 
254
  /* the task state is set EXE by the scheduler()
255
     we extract the task from the ready queue
256
     NB: we can't assume that p is the first task in the queue!!! */
29 pj 257
  iq_extract(p, &lev->ready);
2 pj 258
}
259
 
38 pj 260
static void EDF_public_epilogue(LEVEL l, PID p)
2 pj 261
{
262
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
263
 
240 giacomo 264
  #ifdef EDF_DEBUG
265
    edf_printf("(EDF:PubEpi:%d)",p);
266
  #endif
2 pj 267
 
268
  /* check if the wcet is finished... */
269
  if ((lev->flags & EDF_ENABLE_WCET_CHECK) && proc_table[p].avail_time <= 0) {
270
    /* if it is, raise a XWCET_VIOLATION exception */
271
    kern_raise(XWCET_VIOLATION,p);
272
    proc_table[p].status = EDF_WCET_VIOLATED;
273
  }
274
  else {
275
    /* the task has been preempted. it returns into the ready queue... */
29 pj 276
    iq_timespec_insert(p,&lev->ready);
2 pj 277
    proc_table[p].status = EDF_READY;
278
  }
279
}
280
 
38 pj 281
static void EDF_public_activate(LEVEL l, PID p)
2 pj 282
{
283
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
29 pj 284
  struct timespec *temp;
2 pj 285
 
240 giacomo 286
  #ifdef EDF_DEBUG
287
    edf_printf("(EDF:PubAct:%d)", p);
288
  #endif
38 pj 289
 
212 giacomo 290
  if (lev->flag[p] & EDF_FLAG_SLEEP) {
291
    lev->flag[p] &= ~EDF_FLAG_SLEEP;
292
    if (!(lev->flag[p] & EDF_FLAG_SPORADIC))
293
      proc_table[p].status = EDF_IDLE;
294
    return;
295
  }
296
 
2 pj 297
  if (proc_table[p].status == EDF_WAIT) {
298
    kern_raise(XACTIVATION,p);
299
    return;
300
  }
212 giacomo 301
 
2 pj 302
  /* Test if we are trying to activate a non sleeping task    */
303
  /* Ignore this; the task is already active                  */
304
  if (proc_table[p].status != SLEEP &&
305
      proc_table[p].status != EDF_WCET_VIOLATED)
306
    return;
307
 
308
 
309
  /* see also EDF_timer_deadline */
29 pj 310
  temp = iq_query_timespec(p, &lev->ready);
38 pj 311
  kern_gettime(temp);
29 pj 312
  ADDUSEC2TIMESPEC(lev->period[p], temp);
2 pj 313
 
314
  /* Insert task in the correct position */
315
  proc_table[p].status = EDF_READY;
29 pj 316
  iq_timespec_insert(p,&lev->ready);
2 pj 317
 
318
  /* Set the deadline timer */
29 pj 319
  lev->deadline_timer[p] = kern_event_post(temp,
2 pj 320
                                           EDF_timer_deadline,
321
                                           (void *)p);
322
}
323
 
38 pj 324
static void EDF_public_unblock(LEVEL l, PID p)
2 pj 325
{
326
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
327
 
38 pj 328
  /* Similar to EDF_task_activate,
329
     but we don't check in what state the task is */
2 pj 330
 
331
  /* Insert task in the coEDFect position */
332
  proc_table[p].status = EDF_READY;
29 pj 333
  iq_timespec_insert(p,&lev->ready);
2 pj 334
}
335
 
38 pj 336
static void EDF_public_block(LEVEL l, PID p)
2 pj 337
{
338
  /* Extract the running task from the level
339
     . we have already extract it from the ready queue at the dispatch time.
340
     . the capacity event have to be removed by the generic kernel
341
     . the wcet don't need modification...
342
     . the state of the task is set by the calling function
343
     . the deadline must remain...
344
 
345
     So, we do nothing!!!
346
  */
347
}
348
 
38 pj 349
static int EDF_public_message(LEVEL l, PID p, void *m)
2 pj 350
{
351
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
352
 
240 giacomo 353
  /* task_message evaluation */
212 giacomo 354
  switch((long)(m)) {
2 pj 355
 
240 giacomo 356
    /* task_endcycle */
212 giacomo 357
    case (long)(NULL):
2 pj 358
 
240 giacomo 359
      #ifdef EDF_DEBUG
360
        edf_printf("(EDF:EndCyc:%d)",p);
212 giacomo 361
      #endif
2 pj 362
 
212 giacomo 363
      /* the task has terminated his job before it consume the wcet. All OK! */
364
      if (!(lev->flag[p] & EDF_FLAG_SPORADIC) &&
365
          !(lev->flag[p] & EDF_FLAG_SLEEP))
366
        proc_table[p].status = EDF_IDLE;
367
      else
368
        proc_table[p].status = EDF_WAIT;
38 pj 369
 
212 giacomo 370
      /* we reset the capacity counters... */
371
      if (lev->flags & EDF_ENABLE_WCET_CHECK)
372
        proc_table[p].avail_time = proc_table[p].wcet;
38 pj 373
 
212 giacomo 374
      jet_update_endcycle(); /* Update the Jet data... */
353 giacomo 375
      TRACER_LOGEVENT(FTrace_EVT_task_end_cycle,3,p,l);
212 giacomo 376
 
377
      break;
378
 
240 giacomo 379
    /* task_disable */
212 giacomo 380
    case 1:
381
 
240 giacomo 382
      #ifdef EDF_DEBUG
383
        edf_printf("(EDF:Dis:%d)",p);
212 giacomo 384
      #endif
385
 
386
      /* Set the EDF_FLAG_SLEEP, in the next endcycle the task will
387
         be set in EDF_WAIT */
388
      lev->flag[p] |= EDF_FLAG_SLEEP;
389
 
390
      /* If the task is EDF_IDLE, set to EDF_WAIT now */
391
      if (proc_table[p].status == EDF_IDLE)
392
        proc_table[p].status = EDF_WAIT;
393
 
353 giacomo 394
      TRACER_LOGEVENT(FTrace_EVT_task_disable,3,p,l);
214 giacomo 395
 
212 giacomo 396
      break;
397
 
398
  }
399
 
38 pj 400
  return 0;
212 giacomo 401
 
2 pj 402
}
403
 
38 pj 404
static void EDF_public_end(LEVEL l, PID p)
2 pj 405
{
406
  proc_table[p].status = EDF_ZOMBIE;
407
 
408
  /* When the deadline timer fire, it put the task descriptor in
409
     the free queue, and free the allocated bandwidth... */
410
}
411
 
38 pj 412
static void EDF_private_insert(LEVEL l, PID p, TASK_MODEL *m)
2 pj 413
{
414
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
38 pj 415
  JOB_TASK_MODEL *job;
2 pj 416
 
38 pj 417
  if (m->pclass != JOB_PCLASS || (m->level != 0 && m->level != l) ) {
418
    kern_raise(XINVALID_TASK, p);
419
    return;
420
  }
2 pj 421
 
38 pj 422
  job = (JOB_TASK_MODEL *)m;
2 pj 423
 
38 pj 424
  /* Insert task in the correct position */
29 pj 425
  *iq_query_timespec(p, &lev->ready) = job->deadline;
38 pj 426
  iq_timespec_insert(p,&lev->ready);
427
  proc_table[p].status = EDF_READY;
2 pj 428
 
429
  lev->deadline_timer[p] = -1;
430
 
38 pj 431
  lev->period[p] = job->period;
432
 
433
  /* Set the deadline timer */
434
  if (!(job->noraiseexc))
2 pj 435
    lev->flag[p] = EDF_FLAG_NORAISEEXC;
38 pj 436
  else {
2 pj 437
    lev->flag[p] = 0;
38 pj 438
    lev->deadline_timer[p] = kern_event_post(iq_query_timespec(p, &lev->ready),
439
                                             EDF_timer_guest_deadline,
440
                                             (void *)p);
441
  }
2 pj 442
}
443
 
38 pj 444
static void EDF_private_dispatch(LEVEL l, PID p, int nostop)
2 pj 445
{
446
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
447
 
448
  /* the task state is set to EXE by the scheduler()
449
     we extract the task from the ready queue
450
     NB: we can't assume that p is the first task in the queue!!! */
29 pj 451
  iq_extract(p, &lev->ready);
2 pj 452
}
453
 
38 pj 454
static void EDF_private_epilogue(LEVEL l, PID p)
2 pj 455
{
456
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
457
 
458
  /* the task has been preempted. it returns into the ready queue... */
29 pj 459
  iq_timespec_insert(p,&lev->ready);
2 pj 460
  proc_table[p].status = EDF_READY;
461
}
462
 
38 pj 463
static void EDF_private_extract(LEVEL l, PID p)
2 pj 464
{
465
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
466
 
467
  if (proc_table[p].status == EDF_READY)
29 pj 468
    iq_extract(p, &lev->ready);
2 pj 469
 
470
  /* we remove the deadline timer, because the slice is finished */
471
  if (lev->deadline_timer[p] != NIL) {
38 pj 472
    kern_event_delete(lev->deadline_timer[p]);
2 pj 473
    lev->deadline_timer[p] = NIL;
474
  }
475
 
476
}
477
 
478
 
479
/* Registration functions */
480
 
481
/*+ Registration function:
482
    int flags                 the init flags ... see edf.h +*/
38 pj 483
LEVEL EDF_register_level(int flags)
2 pj 484
{
485
  LEVEL l;            /* the level that we register */
486
  EDF_level_des *lev;  /* for readableness only */
487
  PID i;              /* a counter */
488
 
489
  printk("EDF_register_level\n");
490
 
491
  /* request an entry in the level_table */
38 pj 492
  l = level_alloc_descriptor(sizeof(EDF_level_des));
2 pj 493
 
38 pj 494
  lev = (EDF_level_des *)level_table[l];
2 pj 495
 
496
  printk("    lev=%d\n",(int)lev);
497
 
498
  /* fill the standard descriptor */
38 pj 499
  lev->l.private_insert   = EDF_private_insert;
500
  lev->l.private_extract  = EDF_private_extract;
501
  lev->l.private_dispatch = EDF_private_dispatch;
502
  lev->l.private_epilogue = EDF_private_epilogue;
2 pj 503
 
38 pj 504
  lev->l.public_scheduler = EDF_public_scheduler;
2 pj 505
  if (flags & EDF_ENABLE_GUARANTEE)
38 pj 506
    lev->l.public_guarantee = EDF_public_guarantee;
2 pj 507
  else
38 pj 508
    lev->l.public_guarantee = NULL;
2 pj 509
 
38 pj 510
  lev->l.public_create    = EDF_public_create;
511
  lev->l.public_detach    = EDF_public_detach;
512
  lev->l.public_end       = EDF_public_end;
513
  lev->l.public_dispatch  = EDF_public_dispatch;
514
  lev->l.public_epilogue  = EDF_public_epilogue;
515
  lev->l.public_activate  = EDF_public_activate;
516
  lev->l.public_unblock   = EDF_public_unblock;
517
  lev->l.public_block     = EDF_public_block;
518
  lev->l.public_message   = EDF_public_message;
2 pj 519
 
520
  /* fill the EDF descriptor part */
521
  for(i=0; i<MAX_PROC; i++) {
522
    lev->period[i]         = 0;
523
    lev->deadline_timer[i] = -1;
524
    lev->flag[i]          = 0;
525
  }
526
 
29 pj 527
  iq_init(&lev->ready, &freedesc, 0);
159 pj 528
  lev->flags = flags;
2 pj 529
  lev->U     = 0;
38 pj 530
 
531
  return l;
2 pj 532
}
533
 
534
bandwidth_t EDF_usedbandwidth(LEVEL l)
535
{
536
  EDF_level_des *lev = (EDF_level_des *)(level_table[l]);
38 pj 537
 
538
  return lev->U;
2 pj 539
}
540