Subversion Repositories shark

Rev

Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
1624 giacomo 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
 *   (see the web pages for full authors list)
11
 *
12
 * ReTiS Lab (Scuola Superiore S.Anna - Pisa - Italy)
13
 *
14
 * http://www.sssup.it
15
 * http://retis.sssup.it
16
 * http://shark.sssup.it
17
 */
18
 
19
/**
20
 ------------
21
 CVS :        $Id: edfstar.c,v 1.1.1.1 2004-05-24 17:54:51 giacomo Exp $
22
 
23
 File:        $File$
24
 Revision:    $Revision: 1.1.1.1 $
25
 Last update: $Date: 2004-05-24 17:54:51 $
26
 ------------
27
**/
28
 
29
/*
30
 * Copyright (C) 2001 Paolo Gai
31
 *
32
 * This program is free software; you can redistribute it and/or modify
33
 * it under the terms of the GNU General Public License as published by
34
 * the Free Software Foundation; either version 2 of the License, or
35
 * (at your option) any later version.
36
 *
37
 * This program is distributed in the hope that it will be useful,
38
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
39
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
40
 * GNU General Public License for more details.
41
 *
42
 * You should have received a copy of the GNU General Public License
43
 * along with this program; if not, write to the Free Software
44
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
45
 *
46
 */
47
 
48
#include "edfstar.h"
49
#include <ll/stdio.h>
50
#include <ll/string.h>
51
#include <kernel/model.h>
52
#include <kernel/descr.h>
53
#include <kernel/var.h>
54
#include <kernel/func.h>
55
 
56
/* for iqueues */
57
/* #include "iqueue.h" Now iqueues are the only queue type available
58
   into the kernel */
59
#include <kernel/iqueue.h>
60
 
61
/* for BUDGET_TASK_MODEL */
62
#include "cbsstar.h"
63
 
64
/*
65
 * DEBUG stuffs begin
66
 */
67
 
68
//#define EDFSTAR_DEBUG
69
 
70
#ifdef EDFSTAR_DEBUF
71
 
72
static __inline__ fake_printf(char *fmt, ...) {}
73
 
74
#define edfstar_printf fake_printf
75
#define edfstar_printf2 fake_printf
76
#define edfstar_printf3 fake_printf
77
 
78
//#define edfstar_printf kern_printf
79
//#define edfstar_printf2 kern_printf
80
//#define edfstar_printf3 kern_printf
81
#endif
82
 
83
/*
84
 * DEBUG stuffs end
85
 */
86
 
87
/* Status used in the level */
88
#define EDFSTAR_READY         MODULE_STATUS_BASE    /* - Ready status        */
89
#define EDFSTAR_IDLE          MODULE_STATUS_BASE+4  /* to wait the deadline  */
90
 
91
/* flags */
92
#define EDFSTAR_FLAG_NORAISEEXC  2
93
 
94
/* the level redefinition for the Earliest Deadline First level */
95
typedef struct {
96
  level_des l;     /* the standard level descriptor          */
97
 
98
  TIME period[MAX_PROC]; /* The task periods; the deadlines are
99
                       stored in the priority field           */
100
  int deadline_timer[MAX_PROC];
101
                   /* The task deadline timers               */
102
 
103
  struct timespec deadline_timespec[MAX_PROC];
104
 
105
  int dline_miss[MAX_PROC]; /* Deadline miss counter */
106
  int wcet_miss[MAX_PROC];  /* Wcet miss counter */
107
 
108
  int nact[MAX_PROC];       /* Wcet miss counter */
109
 
110
  int flag[MAX_PROC];
111
                   /* used to manage the JOB_TASK_MODEL and the
112
                       periodicity                            */
113
 
114
  IQUEUE ready;     /* the ready queue                        */
115
 
116
  PID activated;   /* the task that has been inserted into the
117
                       master module */
118
 
119
  int budget;
120
 
121
  int scheduling_level;
122
} EDFSTAR_level_des;
123
 
124
static void EDFSTAR_check_preemption(EDFSTAR_level_des *lev)
125
{
126
  PID first;
127
 
128
#ifdef EDFSTAR_DEBUG
129
  edfstar_printf("(E:chk)");
130
#endif
131
 
132
  if ((first = iq_query_first(&lev->ready)) != lev->activated) {
133
    if (lev->activated != NIL)
134
      level_table[ lev->scheduling_level ]->
135
        private_extract(lev->scheduling_level, lev->activated);
136
 
137
    lev->activated = first;
138
 
139
    if (first != NIL) {
140
      BUDGET_TASK_MODEL b;
141
      budget_task_default_model(b, lev->budget);
142
 
143
      level_table[ lev->scheduling_level ]->
144
        private_insert(lev->scheduling_level, first, (TASK_MODEL *)&b);
145
    }
146
  }
147
}
148
 
149
static void EDFSTAR_timer_deadline(void *par);
150
 
151
static void EDFSTAR_internal_activate(EDFSTAR_level_des *lev, PID p,
152
                                      struct timespec *t)
153
{
154
#ifdef EDFSTAR_DEBUG
155
  edfstar_printf("(E:iact)");
156
#endif
157
 
158
  ADDUSEC2TIMESPEC(lev->period[p], t);
159
 
160
  *iq_query_timespec(p, &lev->ready) = *t;
161
  lev->deadline_timespec[p] = *t;
162
 
163
  /* Insert task in the correct position */
164
  proc_table[p].status = EDFSTAR_READY;
165
  iq_timespec_insert(p,&lev->ready);
166
 
167
  /* needed because when there is a wcet miss I disable CONTROL_CAP */
168
  proc_table[p].control |= CONTROL_CAP;
169
 
170
  /* check for preemption */
171
  EDFSTAR_check_preemption(lev);
172
}
173
 
174
static void EDFSTAR_timer_deadline(void *par)
175
{
176
  PID p = (PID) par;
177
  EDFSTAR_level_des *lev;
178
 
179
#ifdef EDFSTAR_DEBUG
180
//  edfstar_printf("(E:tdl ");
181
#endif
182
 
183
  lev = (EDFSTAR_level_des *)level_table[proc_table[p].task_level];
184
 
185
  switch (proc_table[p].status) {
186
    case EDFSTAR_IDLE:
187
#ifdef EDFSTAR_DEBUG
188
//      edfstar_printf2("I%d",p);
189
#endif
190
      /* set the request time */
191
      EDFSTAR_internal_activate(lev,p,iq_query_timespec(p, &lev->ready));
192
 
193
      event_need_reschedule();
194
      break;
195
 
196
    default:
197
#ifdef EDFSTAR_DEBUG
198
//      edfstar_printf2("D%d",p);
199
#endif
200
      /* else, a deadline miss occurred!!! */
201
      lev->dline_miss[p]++;
202
 
203
      /* the task is into another state */
204
      lev->nact[p]++;
205
 
206
      /* Set the deadline timer */
207
      ADDUSEC2TIMESPEC(lev->period[p], &lev->deadline_timespec[p]);
208
  }
209
 
210
  /* Set the deadline timer */
211
  lev->deadline_timer[p] = kern_event_post(&lev->deadline_timespec[p],
212
                                           EDFSTAR_timer_deadline,
213
                                           (void *)p);
214
 
215
#ifdef EDFSTAR_DEBUG
216
//  edfstar_printf(")");
217
#endif
218
}
219
 
220
static void EDFSTAR_timer_guest_deadline(void *par)
221
{
222
  PID p = (PID) par;
223
 
224
#ifdef EDFSTAR_DEBUG
225
  edfstar_printf("(E:gdl)");
226
#endif
227
 
228
  kern_raise(XDEADLINE_MISS,p);
229
}
230
 
231
static int EDFSTAR_public_create(LEVEL l, PID p, TASK_MODEL *m)
232
{
233
  EDFSTAR_level_des *lev = (EDFSTAR_level_des *)(level_table[l]);
234
 
235
  /* if the EDFSTAR_task_create is called, then the pclass must be a
236
     valid pclass. */
237
  HARD_TASK_MODEL *h;
238
 
239
  if (m->pclass != HARD_PCLASS) return -1;
240
  if (m->level != 0 && m->level != l) return -1;
241
  h = (HARD_TASK_MODEL *)m;
242
  if (!h->wcet || !h->mit || h->periodicity != PERIODIC) return -1;
243
  /* now we know that m is a valid model */
244
 
245
 
246
#ifdef EDFSTAR_DEBUG
247
  edfstar_printf("(E:tcr)");
248
#endif
249
 
250
  lev->period[p] = h->mit;
251
 
252
  lev->flag[p] = 0;
253
  lev->deadline_timer[p] = -1;
254
  lev->dline_miss[p]     = 0;
255
  lev->wcet_miss[p]      = 0;
256
  lev->nact[p]           = 0;
257
 
258
  /* Enable wcet check */
259
  proc_table[p].avail_time = h->wcet;
260
  proc_table[p].wcet       = h->wcet;
261
  proc_table[p].control |= CONTROL_CAP;
262
 
263
  return 0; /* OK, also if the task cannot be guaranteed... */
264
}
265
 
266
static int EDFSTAR_public_eligible(LEVEL l, PID p)
267
{
268
  EDFSTAR_level_des *lev = (EDFSTAR_level_des *)(level_table[l]);
269
 
270
#ifdef EDFSTAR_DEBUG
271
  edfstar_printf2("(E:eli)");
272
#endif
273
 
274
  return level_table[ lev->scheduling_level ]->
275
    private_eligible(lev->scheduling_level,p);
276
}
277
 
278
static void EDFSTAR_public_dispatch(LEVEL l, PID p, int nostop)
279
{
280
  EDFSTAR_level_des *lev = (EDFSTAR_level_des *)(level_table[l]);
281
 
282
#ifdef EDFSTAR_DEBUG
283
  edfstar_printf("(E:dis)");
284
 
285
  edfstar_printf3("(%d %d)",
286
                  iq_query_timespec(p, &lev->ready)->tv_nsec/1000000,
287
                  schedule_time.tv_nsec/1000000);
288
#endif
289
 
290
  level_table[ lev->scheduling_level ]->
291
    private_dispatch(lev->scheduling_level,p,nostop);
292
}
293
 
294
static void EDFSTAR_public_epilogue(LEVEL l, PID p)
295
{
296
  EDFSTAR_level_des *lev = (EDFSTAR_level_des *)(level_table[l]);
297
 
298
#ifdef EDFSTAR_DEBUG
299
  edfstar_printf("(E:epi ");
300
#endif
301
 
302
  /* check if the wcet is finished... */
303
  if (proc_table[p].avail_time <= 0 && proc_table[p].control&CONTROL_CAP) {
304
    /* wcet finished: disable wcet event and count wcet miss */
305
#ifdef EDFSTAR_DEBUG
306
    edfstar_printf2("W%d",p);
307
#endif
308
    proc_table[p].control &= ~CONTROL_CAP;
309
    lev->wcet_miss[p]++;
310
  }
311
#ifdef EDFSTAR_DEBUG
312
  edfstar_printf(")");
313
#endif
314
 
315
  level_table[ lev->scheduling_level ]->
316
    private_epilogue(lev->scheduling_level,p);
317
 
318
  proc_table[p].status = EDFSTAR_READY;
319
}
320
 
321
static void EDFSTAR_public_activate(LEVEL l, PID p)
322
{
323
  EDFSTAR_level_des *lev = (EDFSTAR_level_des *)(level_table[l]);
324
  struct timespec t;
325
 
326
#ifdef EDFSTAR_DEBUG
327
  edfstar_printf("(E:act)");
328
#endif
329
 
330
  /* Test if we are trying to activate a non sleeping task    */
331
  /* save activation (only if needed... */
332
  if (proc_table[p].status != SLEEP) {
333
    /* a periodic task cannot be activated when it is already active */
334
    kern_raise(XACTIVATION,p);
335
    return;
336
  }
337
 
338
  kern_gettime(&t);
339
 
340
  EDFSTAR_internal_activate(lev,p, &t);
341
 
342
  /* Set the deadline timer */
343
  lev->deadline_timer[p] = kern_event_post(&lev->deadline_timespec[p],
344
                                           EDFSTAR_timer_deadline,
345
                                           (void *)p);
346
 
347
}
348
 
349
static void EDFSTAR_public_unblock(LEVEL l, PID p)
350
{
351
  EDFSTAR_level_des *lev = (EDFSTAR_level_des *)(level_table[l]);
352
 
353
#ifdef EDFSTAR_DEBUG
354
  edfstar_printf("(E:ins)");
355
#endif
356
 
357
  /* Insert task in the correct position */
358
  proc_table[p].status = EDFSTAR_READY;
359
  iq_timespec_insert(p,&lev->ready);
360
 
361
  /* and check for preemption! */
362
  EDFSTAR_check_preemption(lev);
363
}
364
 
365
static void EDFSTAR_public_block(LEVEL l, PID p)
366
{
367
  EDFSTAR_level_des *lev = (EDFSTAR_level_des *)(level_table[l]);
368
 
369
#ifdef EDFSTAR_DEBUG
370
  edfstar_printf("(E:ext)");
371
#endif
372
 
373
  /* the task is blocked on a synchronization primitive. we have to
374
     remove it from the master module -and- from the local queue! */
375
  iq_extract(p,&lev->ready);
376
 
377
  /* and finally, a preemption check! (it will also call guest_end) */
378
  EDFSTAR_check_preemption(lev);
379
}
380
 
381
static int EDFSTAR_public_message(LEVEL l, PID p, void *m)
382
{
383
  EDFSTAR_level_des *lev = (EDFSTAR_level_des *)(level_table[l]);
384
  struct timespec temp;
385
 
386
#ifdef EDFSTAR_DEBUG
387
  edfstar_printf("(E:ecy ");
388
#endif
389
 
390
  /* we call guest_end directly here because the same task may
391
     be reinserted in the queue before calling the preemption check! */
392
  level_table[ lev->scheduling_level ]->
393
    private_extract(lev->scheduling_level,p);
394
  lev->activated = NIL;
395
 
396
  iq_extract(p,&lev->ready);
397
 
398
  /* we reset the capacity counters... */
399
  proc_table[p].avail_time = proc_table[p].wcet;
400
 
401
  if (lev->nact[p] > 0) {
402
#ifdef EDFSTAR_DEBUG
403
    edfstar_printf2("E%d",p);
404
#endif
405
 
406
    /* Pending activation: reactivate the thread!!! */
407
    lev->nact[p]--;
408
 
409
    /* see also EDFSTAR_timer_deadline */
410
    kern_gettime(&temp);
411
 
412
    EDFSTAR_internal_activate(lev,p, &temp);
413
 
414
    /* check if the deadline has already expired */
415
    temp = *iq_query_timespec(p, &lev->ready);
416
    if (TIMESPEC_A_LT_B(&temp, &schedule_time)) {
417
      /* count the deadline miss */
418
      lev->dline_miss[p]++;
419
      kern_event_delete(lev->deadline_timer[p]);
420
    }
421
 
422
  }
423
  else {
424
#ifdef EDFSTAR_DEBUG
425
    edfstar_printf("e%d",p);
426
#endif
427
 
428
    /* the task has terminated his job before it consume the wcet. All OK! */
429
    proc_table[p].status = EDFSTAR_IDLE;
430
 
431
    /* and finally, a preemption check! */
432
    EDFSTAR_check_preemption(lev);
433
 
434
    /* when the deadline timer fire, it recognize the situation and set
435
       correctly all the stuffs (like reactivation, etc... ) */
436
  }
437
#ifdef EDFSTAR_DEBUG
438
  edfstar_printf(")");
439
#endif
440
 
441
  jet_update_endcycle(); /* Update the Jet data... */
442
 
443
  return 0;
444
}
445
 
446
static void EDFSTAR_public_end(LEVEL l, PID p)
447
{
448
  EDFSTAR_level_des *lev = (EDFSTAR_level_des *)(level_table[l]);
449
 
450
#ifdef EDFSTAR_DEBUG
451
  edfstar_printf("(E:end)");
452
#endif
453
 
454
  iq_extract(p,&lev->ready);
455
 
456
  /* we finally put the task in the ready queue */
457
  proc_table[p].status = FREE;
458
 
459
  iq_insertfirst(p,&freedesc);
460
 
461
  if (lev->deadline_timer[p] != -1) {
462
    kern_event_delete(lev->deadline_timer[p]);
463
  }
464
 
465
  /* and finally, a preemption check! (it will also call guest_end) */
466
  EDFSTAR_check_preemption(lev);
467
}
468
 
469
/* Guest Functions
470
   These functions manages a JOB_TASK_MODEL, that is used to put
471
   a guest task in the EDFSTAR ready queue. */
472
 
473
static void EDFSTAR_private_insert(LEVEL l, PID p, TASK_MODEL *m)
474
{
475
  EDFSTAR_level_des *lev = (EDFSTAR_level_des *)(level_table[l]);
476
  JOB_TASK_MODEL *job;
477
 
478
  if (m->pclass != JOB_PCLASS || (m->level != 0 && m->level != l) ) {
479
    kern_raise(XINVALID_TASK, p);
480
    return;
481
  }
482
 
483
  job = (JOB_TASK_MODEL *)m;
484
 
485
  /* if the EDFSTAR_guest_create is called, then the pclass must be a
486
     valid pclass. */
487
 
488
  *iq_query_timespec(p, &lev->ready) = job->deadline;
489
 
490
  lev->deadline_timer[p] = -1;
491
  lev->dline_miss[p]     = 0;
492
  lev->wcet_miss[p]      = 0;
493
  lev->nact[p]           = 0;
494
 
495
  if (job->noraiseexc)
496
    lev->flag[p] = EDFSTAR_FLAG_NORAISEEXC;
497
  else {
498
    lev->flag[p] = 0;
499
    lev->deadline_timer[p] = kern_event_post(iq_query_timespec(p, &lev->ready),
500
                                             EDFSTAR_timer_guest_deadline,
501
                                             (void *)p);
502
  }
503
 
504
  lev->period[p] = job->period;
505
 
506
  /* Insert task in the correct position */
507
  iq_timespec_insert(p,&lev->ready);
508
  proc_table[p].status = EDFSTAR_READY;
509
 
510
  /* check for preemption */
511
  EDFSTAR_check_preemption(lev);
512
 
513
  /* there is no bandwidth guarantee at this level, it is performed
514
     by the level that inserts guest tasks... */
515
}
516
 
517
static void EDFSTAR_private_dispatch(LEVEL l, PID p, int nostop)
518
{
519
  EDFSTAR_level_des *lev = (EDFSTAR_level_des *)(level_table[l]);
520
 
521
  level_table[ lev->scheduling_level ]->
522
    private_dispatch(lev->scheduling_level,p,nostop);
523
}
524
 
525
static void EDFSTAR_private_epilogue(LEVEL l, PID p)
526
{
527
  EDFSTAR_level_des *lev = (EDFSTAR_level_des *)(level_table[l]);
528
 
529
  /* the task has been preempted. it returns into the ready queue... */
530
  level_table[ lev->scheduling_level ]->
531
    private_epilogue(lev->scheduling_level,p);
532
 
533
  proc_table[p].status = EDFSTAR_READY;
534
}
535
 
536
static void EDFSTAR_private_extract(LEVEL l, PID p)
537
{
538
  EDFSTAR_level_des *lev = (EDFSTAR_level_des *)(level_table[l]);
539
 
540
#ifdef EDFSTAR_DEBUG
541
  //kern_printf("EDFSTAR_guest_end: dline timer %d\n",lev->deadline_timer[p]);
542
#endif
543
 
544
  iq_extract(p, &lev->ready);
545
 
546
  /* we remove the deadline timer, because the slice is finished */
547
  if (lev->deadline_timer[p] != NIL) {
548
#ifdef EDFSTAR_DEBUG
549
//    kern_printf("EDFSTAR_guest_end: dline timer %d\n",lev->deadline_timer[p]);
550
#endif
551
    kern_event_delete(lev->deadline_timer[p]);
552
    lev->deadline_timer[p] = NIL;
553
  }
554
 
555
  /* and finally, a preemption check! (it will also call guest_end() */
556
  EDFSTAR_check_preemption(lev);
557
}
558
 
559
/* Registration functions */
560
 
561
/* Registration function:
562
    int flags                 the init flags ... see EDFSTAR.h */
563
LEVEL EDFSTAR_register_level(int budget, int master)
564
{
565
  LEVEL l;            /* the level that we register */
566
  EDFSTAR_level_des *lev;  /* for readableness only */
567
  PID i;              /* a counter */
568
 
569
#ifdef EDFSTAR_DEBUG
570
  printk("EDFSTAR_register_level\n");
571
#endif
572
 
573
  /* request an entry in the level_table */
574
  l = level_alloc_descriptor(sizeof(EDFSTAR_level_des));
575
 
576
  lev = (EDFSTAR_level_des *)level_table[l];
577
 
578
  printk("    lev=%d\n",(int)lev);
579
 
580
  /* fill the standard descriptor */
581
  lev->l.private_insert   = EDFSTAR_private_insert;
582
  lev->l.private_extract  = EDFSTAR_private_extract;
583
  lev->l.private_dispatch = EDFSTAR_private_dispatch;
584
  lev->l.private_epilogue = EDFSTAR_private_epilogue;
585
 
586
  lev->l.public_guarantee = NULL;
587
  lev->l.public_eligible  = EDFSTAR_public_eligible;
588
  lev->l.public_create    = EDFSTAR_public_create;
589
  lev->l.public_end       = EDFSTAR_public_end;
590
  lev->l.public_dispatch  = EDFSTAR_public_dispatch;
591
  lev->l.public_epilogue  = EDFSTAR_public_epilogue;
592
  lev->l.public_activate  = EDFSTAR_public_activate;
593
  lev->l.public_unblock   = EDFSTAR_public_unblock;
594
  lev->l.public_block     = EDFSTAR_public_block;
595
  lev->l.public_message   = EDFSTAR_public_message;
596
 
597
  /* fill the EDFSTAR descriptor part */
598
  for(i=0; i<MAX_PROC; i++) {
599
    lev->period[i]         = 0;
600
    lev->deadline_timer[i] = -1;
601
    lev->flag[i]           = 0;
602
    lev->dline_miss[i]     = 0;
603
    lev->wcet_miss[i]      = 0;
604
    lev->nact[i]           = 0;
605
  }
606
 
607
  iq_init(&lev->ready, NULL, IQUEUE_NO_PRIORITY);
608
  lev->activated = NIL;
609
 
610
  lev->budget = budget;
611
  lev->scheduling_level = master;
612
 
613
  return l;
614
}
615
 
616
int EDFSTAR_get_dline_miss(PID p)
617
{
618
  LEVEL l = proc_table[p].task_level;
619
  EDFSTAR_level_des *lev = (EDFSTAR_level_des *)(level_table[l]);
620
 
621
  return lev->dline_miss[p];
622
}
623
 
624
int EDFSTAR_get_wcet_miss(PID p)
625
{
626
  LEVEL l = proc_table[p].task_level;
627
  EDFSTAR_level_des *lev = (EDFSTAR_level_des *)(level_table[l]);
628
 
629
  return lev->wcet_miss[p];
630
}
631
 
632
int EDFSTAR_get_nact(PID p)
633
{
634
  LEVEL l = proc_table[p].task_level;
635
  EDFSTAR_level_des *lev = (EDFSTAR_level_des *)(level_table[l]);
636
 
637
  return lev->nact[p];
638
}
639
 
640
int EDFSTAR_reset_dline_miss(PID p)
641
{
642
  LEVEL l = proc_table[p].task_level;
643
  EDFSTAR_level_des *lev = (EDFSTAR_level_des *)(level_table[l]);
644
 
645
  lev->dline_miss[p] = 0;
646
  return 0;
647
}
648
 
649
int EDFSTAR_reset_wcet_miss(PID p)
650
{
651
  LEVEL l = proc_table[p].task_level;
652
  EDFSTAR_level_des *lev = (EDFSTAR_level_des *)(level_table[l]);
653
 
654
  lev->wcet_miss[p] = 0;
655
  return 0;
656
}
657