Subversion Repositories shark

Rev

Go to most recent revision | Details | 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
 *   (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
 ------------
23
 CVS :        $Id: cbs.c,v 1.1 2005-02-25 10:53:02 pj Exp $
24
 
25
 File:        $File$
26
 Revision:    $Revision: 1.1 $
27
 Last update: $Date: 2005-02-25 10:53:02 $
28
 ------------
29
 
30
 This file contains the aperiodic server CBS (Total Bandwidth Server)
31
 
32
 Read CBS.h for further details.
33
 
34
**/
35
 
36
/*
37
 * Copyright (C) 2000 Paolo Gai
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 <cbs/cbs/cbs.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
 
64
#include <tracer.h>
65
 
66
/*+ 4 debug purposes +*/
67
#undef CBS_TEST
68
#undef CBS_COUNTER
69
 
70
#ifdef TESTG
71
#include "drivers/glib.h"
72
TIME x,oldx;
73
extern TIME starttime;
74
#endif
75
 
76
 
77
/*+ Status used in the level +*/
78
#define CBS_IDLE          APER_STATUS_BASE   /*+ waiting the activation +*/
79
#define CBS_ZOMBIE        APER_STATUS_BASE+1 /*+ waiting the period end +*/
80
 
81
/*+ task flags +*/
82
#define CBS_SAVE_ARRIVALS 1
83
#define CBS_APERIODIC     2
84
#define CBS_SLEEP         4
85
 
86
/*+ the level redefinition for the Total Bandwidth Server level +*/
87
typedef struct {
88
  level_des l;     /*+ the standard level descriptor          +*/
89
 
90
  /* The wcet are stored in the task descriptor, but we need
91
     an array for the deadlines. We can't use the timespec_priority
92
     field because it is used by the master level!!!...
93
     Notice that however the use of the timespec_priority field
94
     does not cause any problem...                     */
95
 
96
  struct timespec cbs_dline[MAX_PROC]; /*+ CBS deadlines      +*/
97
 
98
  TIME period[MAX_PROC]; /*+ CBS activation period            +*/
99
 
100
  struct timespec reactivation_time[MAX_PROC];
101
        /*+ the time at witch  the reactivation timer is post +*/
102
  int reactivation_timer[MAX_PROC];
103
                                   /*+ the recativation timer +*/
104
 
105
  int nact[MAX_PROC]; /*+ number of pending activations       +*/
106
 
107
  BYTE flag[MAX_PROC]; /*+ task flags                         +*/
108
 
109
  int flags;       /*+ the init flags...                      +*/
110
 
111
  bandwidth_t U;   /*+ the used bandwidth by the server       +*/
112
 
113
  LEVEL scheduling_level;
114
 
115
} CBS_level_des;
116
 
117
#ifdef CBS_COUNTER
118
int cbs_counter=0;
119
int cbs_counter2=0;
120
#endif
121
 
122
 
123
static void CBS_activation(CBS_level_des *lev,
124
                           PID p,
125
                           struct timespec *acttime)
126
{
127
  JOB_TASK_MODEL job;
128
 
129
  /* we have to check if the deadline and the wcet are correct before
130
     activating a new task or an old task... */
131
 
132
  /* check 1: if the deadline is before than the actual scheduling time */
133
  /* check 2: if ( avail_time >= (cbs_dline - acttime)* (wcet/period) )
134
     (rule 7 in the CBS article!) */
135
 
136
  /* CHANGES by Anton Cervin 2004-06-23:
137
     a) only check: if ( acttime + (avail_time * period) / wcet > cbs_dline )
138
     b) without (long long) in the computation we can have an overflow!!   */
139
 
140
  TIME t;
141
  struct timespec t2;
142
 
143
  t = ((long long)lev->period[p] * (long long)proc_table[p].avail_time)
144
    / (long long)proc_table[p].wcet;
145
  t2 = *acttime;
146
  ADDUSEC2TIMESPEC(t, &t2);
147
 
148
  if (TIMESPEC_A_GT_B(&t2, &lev->cbs_dline[p])) {
149
 
150
    /* we modify the deadline ... */
151
    TIMESPEC_ASSIGN(&lev->cbs_dline[p], acttime);
152
    ADDUSEC2TIMESPEC(lev->period[p], &lev->cbs_dline[p]);
153
 
154
    /* and the capacity */
155
    proc_table[p].avail_time = proc_table[p].wcet;
156
  }
157
 
158
#ifdef TESTG
159
      if (starttime && p == 3) {
160
      oldx = x;
161
      x = ((lev->cbs_dline[p].tv_sec*1000000+lev->cbs_dline[p].tv_nsec/1000)/5000 - starttime) + 20;
162
//      kern_printf("(a%d)",lev->cbs_dline[p].tv_sec*1000000+lev->cbs_dline[p].tv_nsec/1000);
163
      if (oldx > x) kern_raise(XUNSPECIFIED_EXCEPTION, exec_shadow);
164
      if (x<640)
165
        grx_plot(x, 15, 8);
166
      }
167
#endif
168
 
169
  /* and, finally, we reinsert the task in the master level */
170
  job_task_default_model(job, lev->cbs_dline[p]);
171
  job_task_def_noexc(job);
172
  level_table[ lev->scheduling_level ]->
173
    private_insert(lev->scheduling_level, p, (TASK_MODEL *)&job);
174
}
175
 
176
static void CBS_avail_time_check(CBS_level_des *lev, PID p)
177
{
178
  /* there is a while because if the wcet is << than the system tick
179
     we need to postpone the deadline many times */
180
  while (proc_table[p].avail_time <= 0) {
181
    ADDUSEC2TIMESPEC(lev->period[p], &lev->cbs_dline[p]);
182
    proc_table[p].avail_time += proc_table[p].wcet;
183
 
184
#ifdef TESTG
185
    if (starttime && p == 3) {
186
    oldx = x;
187
    x = ((lev->cbs_dline[p].tv_sec*1000000+lev->cbs_dline[p].tv_nsec/1000)/5000 - starttime) + 20;
188
//      kern_printf("(e%d avail%d)",lev->cbs_dline[p].tv_sec*1000000+lev->cbs_dline[p].tv_nsec/1000,proc_table[p].avail_time);
189
    if (oldx > x) kern_raise(XUNSPECIFIED_EXCEPTION, exec_shadow);
190
    if (x<640)
191
      grx_plot(x, 15, 2);
192
    }
193
#endif
194
  }
195
}
196
 
197
 
198
/* this is the periodic reactivation of the task... it is posted only
199
   if the task is a periodic task */
200
static void CBS_timer_reactivate(void *par)
201
{
202
  PID p = (PID) par;
203
  CBS_level_des *lev;
204
 
205
  lev = (CBS_level_des *)level_table[proc_table[p].task_level];
206
 
207
  #ifdef CBS_COUNTER
208
    if (p==5) cbs_counter++;
209
  #endif
210
 
211
  if (lev->flag[p] & CBS_SLEEP && proc_table[p].status == CBS_IDLE) {
212
    proc_table[p].status = SLEEP;
213
    proc_table[p].avail_time = proc_table[p].wcet;
214
    NULL_TIMESPEC(&lev->cbs_dline[p]);
215
    return;
216
  }
217
 
218
  if (proc_table[p].status == CBS_IDLE) {
219
    /* the task has finished the current activation and must be
220
       reactivated */
221
    CBS_activation(lev,p,&lev->reactivation_time[p]);
222
 
223
    event_need_reschedule();
224
  }
225
  else if (lev->flag[p] & CBS_SAVE_ARRIVALS)
226
    /* the task has not completed the current activation, so we save
227
       the activation incrementing nact... */
228
    lev->nact[p]++;
229
 
230
  /* repost the event at the next period end... */
231
  ADDUSEC2TIMESPEC(lev->period[p], &lev->reactivation_time[p]);
232
  lev->reactivation_timer[p] = kern_event_post(&lev->reactivation_time[p],
233
                                               CBS_timer_reactivate,
234
                                               (void *)p);
235
  #ifdef CBS_COUNTER
236
    if (p==5) cbs_counter2++;
237
  #endif
238
  /* tracer stuff */
239
  TRACER_LOGEVENT(FTrace_EVT_task_timer,(unsigned short int)proc_table[p].context,(unsigned int)proc_table[p].task_level);
240
 
241
}
242
 
243
/*+ this function is called when a killed or ended task reach the
244
    period end +*/
245
static void CBS_timer_zombie(void *par)
246
{
247
  PID p = (PID) par;
248
  CBS_level_des *lev;
249
 
250
  lev = (CBS_level_des *)level_table[proc_table[p].task_level];
251
 
252
  /* we finally put the task in the ready queue */
253
  proc_table[p].status = FREE;
254
  iq_insertfirst(p,&freedesc);
255
 
256
  /* and free the allocated bandwidth */
257
  lev->U -= (MAX_BANDWIDTH/lev->period[p]) * proc_table[p].wcet;
258
 
259
}
260
 
261
 
262
/* The on-line guarantee is enabled only if the appropriate flag is set... */
263
static int CBS_public_guarantee(LEVEL l, bandwidth_t *freebandwidth)
264
{
265
  CBS_level_des *lev = (CBS_level_des *)(level_table[l]);
266
 
267
  if (*freebandwidth >= lev->U) {
268
    *freebandwidth -= lev->U;
269
    return 1;
270
  }
271
  else
272
    return 0;
273
}
274
 
275
static int CBS_public_create(LEVEL l, PID p, TASK_MODEL *m)
276
{
277
  CBS_level_des *lev = (CBS_level_des *)(level_table[l]);
278
  SOFT_TASK_MODEL *soft;
279
 
280
  if (m->pclass != SOFT_PCLASS) return -1;
281
  if (m->level != 0 && m->level != l) return -1;
282
  soft = (SOFT_TASK_MODEL *)m;
283
  if (!(soft->met && soft->period)) return -1;
284
 
285
  soft = (SOFT_TASK_MODEL *)m;
286
 
287
  if (lev->flags & CBS_ENABLE_GUARANTEE) {
288
    bandwidth_t b;
289
    b = (MAX_BANDWIDTH / soft->period) * soft->met;
290
 
291
    /* really update lev->U, checking an overflow... */
292
    if (MAX_BANDWIDTH - lev->U > b)
293
      lev->U += b;
294
    else
295
      return -1;
296
  }
297
 
298
  /* Enable wcet check */
299
  proc_table[p].avail_time = soft->met;
300
  proc_table[p].wcet       = soft->met;
301
  proc_table[p].control   |= CONTROL_CAP;
302
 
303
  lev->nact[p] = 0;
304
  lev->period[p] = soft->period;
305
  NULL_TIMESPEC(&lev->cbs_dline[p]);
306
 
307
  if (soft->periodicity == APERIODIC)
308
    lev->flag[p] = CBS_APERIODIC;
309
  else
310
    lev->flag[p] = 0;
311
 
312
  if (soft->arrivals == SAVE_ARRIVALS)
313
    lev->flag[p] |= CBS_SAVE_ARRIVALS;
314
 
315
  return 0; /* OK, also if the task cannot be guaranteed... */
316
}
317
 
318
static void CBS_public_detach(LEVEL l, PID p)
319
{
320
  /* the CBS level doesn't introduce any dinamic allocated new field.
321
     we have only to decrement the allocated bandwidth */
322
 
323
  CBS_level_des *lev = (CBS_level_des *)(level_table[l]);
324
 
325
  if (lev->flags & CBS_ENABLE_GUARANTEE) {
326
    lev->U -= (MAX_BANDWIDTH / lev->period[p]) * proc_table[p].wcet;
327
  }
328
}
329
 
330
static int CBS_public_eligible(LEVEL l, PID p)
331
{
332
  CBS_level_des *lev = (CBS_level_des *)(level_table[l]);
333
  JOB_TASK_MODEL job;
334
 
335
  /* we have to check if the deadline and the wcet are correct...
336
     if the CBS level schedules in background with respect to others
337
     levels, there can be the case in witch a task is scheduled by
338
     schedule_time > CBS_deadline; in this case (not covered in the
339
     article because if there is only the standard scheduling policy
340
     this never apply) we reassign the deadline */
341
 
342
  if ( TIMESPEC_A_LT_B(&lev->cbs_dline[p], &schedule_time) ) {
343
    /* we kill the current activation */
344
    level_table[ lev->scheduling_level ]->
345
      private_extract(lev->scheduling_level, p);
346
 
347
    /* we modify the deadline ... */
348
    TIMESPEC_ASSIGN(&lev->cbs_dline[p], &schedule_time);
349
    ADDUSEC2TIMESPEC(lev->period[p], &lev->cbs_dline[p]);
350
 
351
    /* and the capacity */
352
    proc_table[p].avail_time = proc_table[p].wcet;
353
 
354
    /* and, finally, we reinsert the task in the master level */
355
    job_task_default_model(job, lev->cbs_dline[p]);
356
    job_task_def_noexc(job);
357
    level_table[ lev->scheduling_level ]->
358
      private_insert(lev->scheduling_level, p, (TASK_MODEL *)&job);
359
 
360
    return -1;
361
  }
362
 
363
  return 0;
364
}
365
 
366
static void CBS_public_dispatch(LEVEL l, PID p, int nostop)
367
{
368
  CBS_level_des *lev = (CBS_level_des *)(level_table[l]);
369
  level_table[ lev->scheduling_level ]->
370
    private_dispatch(lev->scheduling_level,p,nostop);
371
}
372
 
373
static void CBS_public_epilogue(LEVEL l, PID p)
374
{
375
  CBS_level_des *lev = (CBS_level_des *)(level_table[l]);
376
  JOB_TASK_MODEL job;
377
 
378
  /* check if the wcet is finished... */
379
  if ( proc_table[p].avail_time <= 0) {
380
    /* we kill the current activation */
381
    level_table[ lev->scheduling_level ]->
382
      private_extract(lev->scheduling_level, p);
383
 
384
    /* we modify the deadline according to rule 4 ... */
385
    CBS_avail_time_check(lev, p);
386
 
387
    /* and, finally, we reinsert the task in the master level */
388
    job_task_default_model(job, lev->cbs_dline[p]);
389
    job_task_def_noexc(job);
390
    level_table[ lev->scheduling_level ]->
391
      private_insert(lev->scheduling_level, p, (TASK_MODEL *)&job);
392
//    kern_printf("epil : dl %d per %d p %d |\n",
393
//              lev->cbs_dline[p].tv_nsec/1000,lev->period[p],p);
394
 
395
  }
396
  else
397
    /* the task has been preempted. it returns into the ready queue by
398
       calling the guest_epilogue... */
399
    level_table[ lev->scheduling_level ]->
400
      private_epilogue(lev->scheduling_level,p);
401
}
402
 
403
static void CBS_public_activate(LEVEL l, PID p, struct timespec *t)
404
{
405
  CBS_level_des *lev = (CBS_level_des *)(level_table[l]);
406
 
407
  if (lev->flag[p] & CBS_SLEEP) {
408
    lev->flag[p] &= ~CBS_SLEEP;
409
    if (proc_table[p].status != SLEEP) return;
410
  }
411
 
412
  /* save activation (only if needed... */
413
  if (proc_table[p].status != SLEEP) {
414
    if (lev->flag[p] & CBS_SAVE_ARRIVALS)
415
      lev->nact[p]++;
416
    return;
417
  }
418
 
419
  CBS_activation(lev, p, t);
420
 
421
  /* Set the reactivation timer */
422
  if (!(lev->flag[p] & CBS_APERIODIC))
423
  {
424
    /* we cannot use the deadline computed by CBS_activation because
425
       the deadline may be != from actual_time + period
426
       (if we call the task_activate after a task_sleep, and the
427
       deadline was postponed a lot...) */
428
    TIMESPEC_ASSIGN(&lev->reactivation_time[p], t);
429
    ADDUSEC2TIMESPEC(lev->period[p], &lev->reactivation_time[p]);
430
//    TIMESPEC_ASSIGN(&lev->reactivation_time[p], &lev->cbs_dline[p]);
431
    lev->reactivation_timer[p] = kern_event_post(&lev->reactivation_time[p],
432
                                                 CBS_timer_reactivate,
433
                                                 (void *)p);
434
    #ifdef CBS_COUNTER
435
      if (p==5) cbs_counter2++;
436
    #endif
437
  }
438
//  kern_printf("act : %d %d |",lev->cbs_dline[p].tv_nsec/1000,p);
439
}
440
 
441
static void CBS_public_unblock(LEVEL l, PID p)
442
{
443
  CBS_level_des *lev = (CBS_level_des *)(level_table[l]);
444
  struct timespec acttime;
445
 
446
  kern_gettime(&acttime);
447
 
448
  CBS_activation(lev,p,&acttime);
449
}
450
 
451
static void CBS_public_block(LEVEL l, PID p)
452
{
453
  CBS_level_des *lev = (CBS_level_des *)(level_table[l]);
454
 
455
  /* check if the wcet is finished... */
456
  CBS_avail_time_check(lev, p);
457
 
458
  level_table[ lev->scheduling_level ]->
459
    private_extract(lev->scheduling_level,p);
460
}
461
 
462
static int CBS_public_message(LEVEL l, PID p, void *m)
463
{
464
  CBS_level_des *lev = (CBS_level_des *)(level_table[l]);
465
 
466
  switch((long)(m)) {
467
 
468
    case (long)(NULL):
469
 
470
      /* check if the wcet is finished... */
471
      CBS_avail_time_check(lev, p);
472
 
473
      if (lev->nact[p]) {
474
        /* continue!!!! */
475
        lev->nact[p]--;
476
        level_table[ lev->scheduling_level ]->
477
          private_epilogue(lev->scheduling_level,p);
478
      } else {
479
        level_table[ lev->scheduling_level ]->
480
          private_extract(lev->scheduling_level,p);
481
 
482
        if (lev->flag[p] & CBS_APERIODIC)
483
          proc_table[p].status = SLEEP;
484
        else  /* the task is soft_periodic */
485
          proc_table[p].status = CBS_IDLE;
486
      }
487
 
488
      jet_update_endcycle(); /* Update the Jet data... */
489
      TRACER_LOGEVENT(FTrace_EVT_task_end_cycle,(unsigned short int)proc_table[p].context,(unsigned int)l);
490
 
491
      break;
492
 
493
    case 1:
494
 
495
      lev->flag[p] |= CBS_SLEEP;
496
      TRACER_LOGEVENT(FTrace_EVT_task_disable,(unsigned short int)proc_table[p].context,(unsigned int)l);
497
 
498
      break;
499
 
500
  }
501
 
502
  return 0;
503
 
504
}
505
 
506
static void CBS_public_end(LEVEL l, PID p)
507
{
508
  CBS_level_des *lev = (CBS_level_des *)(level_table[l]);
509
 
510
  /* check if the wcet is finished... */
511
  CBS_avail_time_check(lev, p);
512
 
513
  level_table[ lev->scheduling_level ]->
514
    private_extract(lev->scheduling_level,p);
515
 
516
  /* we delete the reactivation timer */
517
  if (!(lev->flag[p] & CBS_APERIODIC)) {
518
    kern_event_delete(lev->reactivation_timer[p]);
519
    lev->reactivation_timer[p] = -1;
520
  }
521
 
522
  /* Finally, we post the zombie event. when the end period is reached,
523
     the task descriptor and banwidth are freed */
524
  proc_table[p].status = CBS_ZOMBIE;
525
  lev->reactivation_timer[p] = kern_event_post(&lev->cbs_dline[p],
526
                                               CBS_timer_zombie,
527
                                               (void *)p);
528
}
529
 
530
/* Registration functions */
531
 
532
/*+ Registration function:
533
    int flags                 the init flags ... see CBS.h +*/
534
LEVEL CBS_register_level(int flags, LEVEL master)
535
{
536
  LEVEL l;            /* the level that we register */
537
  CBS_level_des *lev;  /* for readableness only */
538
  PID i;              /* a counter */
539
 
540
  printk("CBS_register_level\n");
541
 
542
  /* request an entry in the level_table */
543
  l = level_alloc_descriptor(sizeof(CBS_level_des));
544
 
545
  lev = (CBS_level_des *)level_table[l];
546
 
547
  /* fill the standard descriptor */
548
  if (flags & CBS_ENABLE_GUARANTEE)
549
    lev->l.public_guarantee = CBS_public_guarantee;
550
  else
551
    lev->l.public_guarantee = NULL;
552
  lev->l.public_create    = CBS_public_create;
553
  lev->l.public_detach    = CBS_public_detach;
554
  lev->l.public_end       = CBS_public_end;
555
  lev->l.public_eligible  = CBS_public_eligible;
556
  lev->l.public_dispatch  = CBS_public_dispatch;
557
  lev->l.public_epilogue  = CBS_public_epilogue;
558
  lev->l.public_activate  = CBS_public_activate;
559
  lev->l.public_unblock   = CBS_public_unblock;
560
  lev->l.public_block     = CBS_public_block;
561
  lev->l.public_message   = CBS_public_message;
562
 
563
  /* fill the CBS descriptor part */
564
  for (i=0; i<MAX_PROC; i++) {
565
     NULL_TIMESPEC(&lev->cbs_dline[i]);
566
     lev->period[i] = 0;
567
     NULL_TIMESPEC(&lev->reactivation_time[i]);
568
     lev->reactivation_timer[i] = -1;
569
     lev->nact[i] = 0;
570
     lev->flag[i] = 0;
571
  }
572
 
573
 
574
  lev->U = 0;
575
 
576
  lev->scheduling_level = master;
577
 
578
  lev->flags = flags;
579
 
580
  return l;
581
}
582
 
583
bandwidth_t CBS_usedbandwidth(LEVEL l)
584
{
585
  CBS_level_des *lev = (CBS_level_des *)(level_table[l]);
586
 
587
  return lev->U;
588
}
589
 
590
int CBS_get_nact(LEVEL l, PID p)
591
{
592
  CBS_level_des *lev = (CBS_level_des *)(level_table[l]);
593
 
594
  return lev->nact[p];
595
}
596