Subversion Repositories shark

Rev

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

Rev Author Line No. Line
206 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
 *   Massimiliano Giorgi <massy@gandalf.sssup.it>
11
 *   Luca Abeni          <luca@gandalf.sssup.it>
211 giacomo 12
 *   Giacomo Guidi       <giacomo@gandalf.sssup.it>
13
 *   (see the web pages for full authors list)
206 giacomo 14
 *
15
 * ReTiS Lab (Scuola Superiore S.Anna - Pisa - Italy)
16
 *
17
 * http://www.sssup.it
18
 * http://retis.sssup.it
19
 * http://shark.sssup.it
20
 */
21
 
22
/*
23
 * Copyright (C) 2000 Paolo Gai
24
 *
25
 * This program is free software; you can redistribute it and/or modify
26
 * it under the terms of the GNU General Public License as published by
27
 * the Free Software Foundation; either version 2 of the License, or
28
 * (at your option) any later version.
29
 *
30
 * This program is distributed in the hope that it will be useful,
31
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
32
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
33
 * GNU General Public License for more details.
34
 *
35
 * You should have received a copy of the GNU General Public License
36
 * along with this program; if not, write to the Free Software
37
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
38
 *
39
 */
40
 
41
#include <modules/hardcbs.h>
42
#include <ll/stdio.h>
43
#include <ll/string.h>
44
#include <kernel/model.h>
45
#include <kernel/descr.h>
46
#include <kernel/var.h>
47
#include <kernel/func.h>
48
#include <kernel/trace.h>
49
 
50
/*+ Status used in the level +*/
51
#define HCBS_IDLE          APER_STATUS_BASE   /*+ waiting the activation +*/
52
#define HCBS_ZOMBIE        APER_STATUS_BASE+1 /*+ waiting the period end +*/
53
 
54
/*+ task flags +*/
55
#define HCBS_SAVE_ARRIVALS 1
56
#define HCBS_APERIODIC     2
57
#define HCBS_SLEEP         4
58
#define HCBS_OVERLOAD      8
59
 
60
/*+ the level redefinition for the Total Bandwidth Server level +*/
61
typedef struct {
62
  level_des l;     /*+ the standard level descriptor          +*/
63
 
64
  /* The wcet are stored in the task descriptor, but we need
65
     an array for the deadlines. We can't use the timespec_priority
66
     field because it is used by the master level!!!...
67
     Notice that however the use of the timespec_priority field
68
     does not cause any problem...                     */
69
 
70
  struct timespec cbs_dline[MAX_PROC]; /*+ CBS deadlines      +*/
71
 
72
  TIME period[MAX_PROC]; /*+ CBS activation period            +*/
73
 
74
  struct timespec reactivation_time[MAX_PROC];
75
        /*+ the time at witch  the reactivation timer is post +*/
76
  int reactivation_timer[MAX_PROC];
77
                                   /*+ the recativation timer +*/
78
 
79
  int nact[MAX_PROC]; /*+ number of pending activations       +*/
80
 
81
  BYTE flag[MAX_PROC]; /*+ task flags                         +*/
82
 
83
  int flags;       /*+ the init flags...                      +*/
84
 
85
  bandwidth_t U;   /*+ the used bandwidth by the server       +*/
86
 
87
  LEVEL scheduling_level;
88
 
89
} HCBS_level_des;
90
 
91
static void HCBS_activation(HCBS_level_des *lev,
211 giacomo 92
                            PID p,
93
                            struct timespec *acttime)
206 giacomo 94
{
95
  JOB_TASK_MODEL job;
96
 
97
  /* we have to check if the deadline and the wcet are correct before
98
     activating a new task or an old task... */
99
 
100
  /* check 1: if the deadline is before than the actual scheduling time */
101
 
102
  /* check 2: if ( avail_time >= (cbs_dline - acttime)* (wcet/period) )
103
     (rule 7 in the CBS article!) */
104
  TIME t;
105
  struct timespec t2,t3;
106
 
107
  t = (lev->period[p] * proc_table[p].avail_time) / proc_table[p].wcet;
108
  t3.tv_sec = t / 1000000;
109
  t3.tv_nsec = (t % 1000000) * 1000;
110
 
111
  SUBTIMESPEC(&lev->cbs_dline[p], acttime, &t2);
112
 
113
  if (/* 1 */ TIMESPEC_A_LT_B(&lev->cbs_dline[p], acttime) ||
114
      /* 2 */ TIMESPEC_A_GT_B(&t3, &t2) ) {
211 giacomo 115
/*    if (TIMESPEC_A_LT_B(&lev->cbs_dline[p], acttime) )
116
      kern_printf("$");
117
    else
118
      kern_printf("(Ûdline%d.%d act%d.%d wcet%d per%d avail%dÛ)",
119
                  lev->cbs_dline[p].tv_sec,lev->cbs_dline[p].tv_nsec/1000,
120
                  acttime->tv_sec, acttime->tv_nsec/1000,
121
                  proc_table[p].wcet, lev->period[p], proc_table[p].avail_time);
122
*/  /* we modify the deadline ... */
206 giacomo 123
    TIMESPEC_ASSIGN(&lev->cbs_dline[p], acttime);
124
    ADDUSEC2TIMESPEC(lev->period[p], &lev->cbs_dline[p]);
125
 
126
    /* and the capacity */
127
    proc_table[p].avail_time = proc_table[p].wcet;
128
  }
129
 
130
  /* and, finally, we reinsert the task in the master level */
131
  job_task_default_model(job, lev->cbs_dline[p]);
132
  job_task_def_noexc(job);
133
  level_table[ lev->scheduling_level ]->
134
    private_insert(lev->scheduling_level, p, (TASK_MODEL *)&job);
211 giacomo 135
}
206 giacomo 136
 
211 giacomo 137
static void HCBS_reload(HCBS_level_des *lev, PID p)
138
{
139
 
140
  proc_table[p].avail_time += proc_table[p].wcet;
141
 
206 giacomo 142
}
143
 
144
static void HCBS_avail_time_check(HCBS_level_des *lev, PID p)
145
{
211 giacomo 146
  /* Only one time due to hard reservation */
147
  if (proc_table[p].avail_time < 0)
206 giacomo 148
    ADDUSEC2TIMESPEC(lev->period[p], &lev->cbs_dline[p]);
149
 
150
}
151
 
152
 
153
/* this is the periodic reactivation of the task... it is posted only
154
   if the task is a periodic task */
155
static void HCBS_timer_reactivate(void *par)
156
{
157
  PID p = (PID) par;
158
  HCBS_level_des *lev;
159
 
160
  lev = (HCBS_level_des *)level_table[proc_table[p].task_level];
161
 
162
  if (lev->flag[p] & HCBS_SLEEP && proc_table[p].status == HCBS_IDLE) {
163
    proc_table[p].status = SLEEP;
211 giacomo 164
    proc_table[p].avail_time = proc_table[p].wcet;
165
    NULL_TIMESPEC(&lev->cbs_dline[p]);
206 giacomo 166
    return;
167
  }
168
 
211 giacomo 169
  /* Hard reservation avail_time reload */
170
  HCBS_reload(lev, p);
171
 
206 giacomo 172
  if (proc_table[p].status == HCBS_IDLE) {
173
    /* the task has finished the current activation and must be
174
       reactivated */
175
    HCBS_activation(lev,p,&lev->reactivation_time[p]);
176
 
177
    event_need_reschedule();
178
  }
179
  else if (lev->flag[p] & HCBS_SAVE_ARRIVALS)
180
    /* the task has not completed the current activation, so we save
181
       the activation incrementing nact... */
182
    lev->nact[p]++;
183
 
211 giacomo 184
  /* repost the event at the next period end... */
185
  ADDUSEC2TIMESPEC(lev->period[p], &lev->reactivation_time[p]);
186
  lev->reactivation_timer[p] = kern_event_post(&lev->reactivation_time[p],
206 giacomo 187
                                               HCBS_timer_reactivate,
188
                                               (void *)p);
189
 
190
  /* tracer stuff */
191
  trc_logevent(TRC_INTACTIVATION,&p);
192
 
193
}
194
 
195
/*+ this function is called when a killed or ended task reach the
196
    period end +*/
197
static void HCBS_timer_zombie(void *par)
198
{
199
  PID p = (PID) par;
211 giacomo 200
  HCBS_level_des *lev;
201
 
202
  lev = (HCBS_level_des *)level_table[proc_table[p].task_level];
203
 
204
  /* we finally put the task in the ready queue */
206 giacomo 205
  proc_table[p].status = FREE;
206
  iq_insertfirst(p,&freedesc);
207
 
208
}
209
 
211 giacomo 210
 
206 giacomo 211
/* The on-line guarantee is enabled only if the appropriate flag is set... */
212
static int HCBS_public_guarantee(LEVEL l, bandwidth_t *freebandwidth)
213
{
214
  HCBS_level_des *lev = (HCBS_level_des *)(level_table[l]);
215
 
216
  if (*freebandwidth >= lev->U) {
217
    *freebandwidth -= lev->U;
218
    return 1;
219
  }
220
  else
221
    return 0;
222
}
223
 
224
static int HCBS_public_create(LEVEL l, PID p, TASK_MODEL *m)
225
{
226
  HCBS_level_des *lev = (HCBS_level_des *)(level_table[l]);
227
  SOFT_TASK_MODEL *soft;
228
 
229
  if (m->pclass != SOFT_PCLASS) return -1;
230
  if (m->level != 0 && m->level != l) return -1;
231
  soft = (SOFT_TASK_MODEL *)m;
232
  if (!(soft->met && soft->period)) return -1;
233
 
234
  soft = (SOFT_TASK_MODEL *)m;
235
 
236
  if (lev->flags & HCBS_ENABLE_GUARANTEE) {
237
    bandwidth_t b;
238
    b = (MAX_BANDWIDTH / soft->period) * soft->met;
239
 
240
    /* really update lev->U, checking an overflow... */
241
    if (MAX_BANDWIDTH - lev->U > b)
242
      lev->U += b;
243
    else
244
      return -1;
245
  }
246
 
247
  /* Enable wcet check */
248
  proc_table[p].avail_time = soft->met;
249
  proc_table[p].wcet       = soft->met;
250
  proc_table[p].control   |= CONTROL_CAP;
251
 
252
  lev->nact[p] = 0;
253
  lev->period[p] = soft->period;
254
  NULL_TIMESPEC(&lev->cbs_dline[p]);
255
 
256
  if (soft->periodicity == APERIODIC)
257
    lev->flag[p] = HCBS_APERIODIC;
258
  else
259
    lev->flag[p] = 0;
260
 
261
  if (soft->arrivals == SAVE_ARRIVALS)
262
    lev->flag[p] |= HCBS_SAVE_ARRIVALS;
263
 
264
  return 0; /* OK, also if the task cannot be guaranteed... */
265
}
266
 
267
static void HCBS_public_detach(LEVEL l, PID p)
268
{
269
  /* the CBS level doesn't introduce any dinamic allocated new field.
270
     we have only to decrement the allocated bandwidth */
271
 
272
  HCBS_level_des *lev = (HCBS_level_des *)(level_table[l]);
273
 
274
  if (lev->flags & HCBS_ENABLE_GUARANTEE) {
275
    lev->U -= (MAX_BANDWIDTH / lev->period[p]) * proc_table[p].wcet;
276
  }
277
}
278
 
279
static int HCBS_public_eligible(LEVEL l, PID p)
280
{
281
  HCBS_level_des *lev = (HCBS_level_des *)(level_table[l]);
282
  JOB_TASK_MODEL job;
283
 
284
  /* we have to check if the deadline and the wcet are correct...
285
     if the CBS level schedules in background with respect to others
286
     levels, there can be the case in witch a task is scheduled by
287
     schedule_time > CBS_deadline; in this case (not covered in the
288
     article because if there is only the standard scheduling policy
289
     this never apply) we reassign the deadline */
290
 
291
  if ( TIMESPEC_A_LT_B(&lev->cbs_dline[p], &schedule_time) ) {
292
    /* we kill the current activation */
293
    level_table[ lev->scheduling_level ]->
294
      private_extract(lev->scheduling_level, p);
295
 
296
    /* we modify the deadline ... */
297
    TIMESPEC_ASSIGN(&lev->cbs_dline[p], &schedule_time);
298
    ADDUSEC2TIMESPEC(lev->period[p], &lev->cbs_dline[p]);
299
 
300
    /* and the capacity */
301
    proc_table[p].avail_time = proc_table[p].wcet;
302
 
303
    /* and, finally, we reinsert the task in the master level */
304
    job_task_default_model(job, lev->cbs_dline[p]);
305
    job_task_def_noexc(job);
306
    level_table[ lev->scheduling_level ]->
307
      private_insert(lev->scheduling_level, p, (TASK_MODEL *)&job);
308
 
309
    return -1;
310
  }
211 giacomo 311
 
206 giacomo 312
  return 0;
313
}
314
 
315
static void HCBS_public_dispatch(LEVEL l, PID p, int nostop)
316
{
317
  HCBS_level_des *lev = (HCBS_level_des *)(level_table[l]);
318
  level_table[ lev->scheduling_level ]->
319
    private_dispatch(lev->scheduling_level,p,nostop);
320
}
321
 
322
static void HCBS_public_epilogue(LEVEL l, PID p)
323
{
324
  HCBS_level_des *lev = (HCBS_level_des *)(level_table[l]);
325
 
326
  /* check if the wcet is finished... */
327
  if ( proc_table[p].avail_time <= 0) {
328
 
211 giacomo 329
    /* Set the overload flag */
206 giacomo 330
    lev->flag[p] |= HCBS_OVERLOAD;
331
 
332
    /* we kill the current activation */
333
    level_table[ lev->scheduling_level ]->
334
      private_extract(lev->scheduling_level, p);
335
 
211 giacomo 336
    /* we modify the deadline according to rule 4 ... */
337
    HCBS_avail_time_check(lev, p);
338
 
206 giacomo 339
    /* Hard Reservation: The avail_time will be reloaded in the
340
       next reactivation event. The task is suspended */
341
    proc_table[p].status = HCBS_IDLE;
342
    if (lev->flag[p] & HCBS_APERIODIC) {
343
 
344
      ADDUSEC2TIMESPEC(lev->period[p], &lev->reactivation_time[p]);
345
      lev->reactivation_timer[p] = kern_event_post(&lev->reactivation_time[p],
346
                                                 HCBS_timer_reactivate,
347
                                                 (void *)p);
348
    }
211 giacomo 349
 
206 giacomo 350
  }
351
  else
352
    /* the task has been preempted. it returns into the ready queue by
353
       calling the guest_epilogue... */
354
    level_table[ lev->scheduling_level ]->
355
      private_epilogue(lev->scheduling_level,p);
356
}
357
 
358
static void HCBS_public_activate(LEVEL l, PID p)
359
{
360
  HCBS_level_des *lev = (HCBS_level_des *)(level_table[l]);
361
  struct timespec t;
362
 
363
  if (lev->flag[p] & HCBS_SLEEP) {
364
    lev->flag[p] &= ~HCBS_SLEEP;
365
    if (proc_table[p].status != SLEEP) return;
366
  }
367
 
368
  /* save activation (only if needed... */
369
  if (proc_table[p].status != SLEEP) {
370
    if (lev->flag[p] & HCBS_SAVE_ARRIVALS)
371
      lev->nact[p]++;
372
    return;
373
  }
374
 
375
  kern_gettime(&t);
376
 
377
  HCBS_activation(lev, p, &t);
378
 
379
  /* Set the reactivation timer */
380
  if (!(lev->flag[p] & HCBS_APERIODIC))
381
  {
382
    /* we cannot use the deadline computed by CBS_activation because
383
       the deadline may be != from actual_time + period
384
       (if we call the task_activate after a task_sleep, and the
385
       deadline was postponed a lot...) */
386
    TIMESPEC_ASSIGN(&lev->reactivation_time[p], &t);
387
    ADDUSEC2TIMESPEC(lev->period[p], &lev->reactivation_time[p]);
388
//    TIMESPEC_ASSIGN(&lev->reactivation_time[p], &lev->cbs_dline[p]);
389
    lev->reactivation_timer[p] = kern_event_post(&lev->reactivation_time[p],
390
                                                 HCBS_timer_reactivate,
391
                                                 (void *)p);
392
  }
211 giacomo 393
//  kern_printf("act : %d %d |",lev->cbs_dline[p].tv_nsec/1000,p);
206 giacomo 394
}
395
 
396
static void HCBS_public_unblock(LEVEL l, PID p)
397
{
398
  HCBS_level_des *lev = (HCBS_level_des *)(level_table[l]);
399
  struct timespec acttime;
400
 
401
  kern_gettime(&acttime);
402
 
403
  HCBS_activation(lev,p,&acttime);
404
}
405
 
406
static void HCBS_public_block(LEVEL l, PID p)
407
{
408
  HCBS_level_des *lev = (HCBS_level_des *)(level_table[l]);
409
 
410
  /* check if the wcet is finished... */
411
  HCBS_avail_time_check(lev, p);
412
 
413
  level_table[ lev->scheduling_level ]->
414
    private_extract(lev->scheduling_level,p);
415
}
416
 
417
static int HCBS_public_message(LEVEL l, PID p, void *m)
418
{
211 giacomo 419
  HCBS_level_des *lev = (HCBS_level_des *)(level_table[l]);
206 giacomo 420
  HCBS_command_message *msg;
421
 
422
  switch((long)(m)) {
423
 
424
    case (long)(NULL):
425
 
211 giacomo 426
      /* check if the wcet is finished... */
427
      HCBS_avail_time_check(lev, p);
428
 
429
      if (lev->flag[p] & HCBS_OVERLOAD) {
430
        lev->nact[p]++;
206 giacomo 431
        lev->flag[p] &= ~HCBS_OVERLOAD;
432
      }
433
 
434
      if (lev->nact[p]) {
435
        /* continue!!!! */
436
        lev->nact[p]--;
437
        level_table[ lev->scheduling_level ]->
438
          private_epilogue(lev->scheduling_level,p);
439
      } else {
440
        level_table[ lev->scheduling_level ]->
441
          private_extract(lev->scheduling_level,p);
442
 
443
        if (lev->flag[p] & HCBS_APERIODIC)
444
          proc_table[p].status = SLEEP;
445
        else  /* the task is soft_periodic */
446
          proc_table[p].status = HCBS_IDLE;
447
      }
448
 
449
      jet_update_endcycle(); /* Update the Jet data... */
450
      trc_logevent(TRC_ENDCYCLE,&exec_shadow); /* tracer stuff */
451
 
452
      break;
453
 
211 giacomo 454
    case 1:
206 giacomo 455
 
456
      lev->flag[p] |= HCBS_SLEEP;
457
 
458
      break;
459
 
460
    /* Set/Get Met/Period */
461
    default:
462
 
463
      msg = (HCBS_command_message *)(m);
464
 
465
      switch (msg->command) {
466
        case HCBS_SET_PERIOD:
467
          lev->U -= (bandwidth_t)(MAX_BANDWIDTH / lev->period[p]
468
                * proc_table[p].wcet);
469
          lev->period[p] = msg->param;
470
          lev->U += (bandwidth_t)(MAX_BANDWIDTH / lev->period[p]
471
                * proc_table[p].wcet);
472
          break;
473
        case HCBS_GET_PERIOD:
474
          msg->param = lev->period[p];
475
          break;
476
        case HCBS_SET_MET:
477
          lev->U -= (bandwidth_t)(MAX_BANDWIDTH / lev->period[p]
478
                * proc_table[p].wcet);
479
          proc_table[p].wcet = msg->param;
480
          lev->U += (bandwidth_t)(MAX_BANDWIDTH / lev->period[p]
481
                * proc_table[p].wcet);
482
          break;
483
        case HCBS_GET_MET:
484
          msg->param = proc_table[p].wcet;
485
          break;
486
      }
487
 
488
  }
489
 
490
  return 0;
211 giacomo 491
 
206 giacomo 492
}
493
 
494
static void HCBS_public_end(LEVEL l, PID p)
495
{
496
  HCBS_level_des *lev = (HCBS_level_des *)(level_table[l]);
497
 
498
  /* check if the wcet is finished... */
499
  HCBS_avail_time_check(lev, p);
500
 
501
  level_table[ lev->scheduling_level ]->
502
    private_extract(lev->scheduling_level,p);
503
 
211 giacomo 504
  /* and free the allocated bandwidth */
206 giacomo 505
  lev->U -= (MAX_BANDWIDTH/lev->period[p]) * proc_table[p].wcet;
506
 
507
  /* we delete the reactivation timer */
508
  if (!(lev->flag[p] & HCBS_APERIODIC)) {
509
    kern_event_delete(lev->reactivation_timer[p]);
510
    lev->reactivation_timer[p] = -1;
511
  }
512
 
513
  /* Finally, we post the zombie event. when the end period is reached,
514
     the task descriptor and banwidth are freed */
515
  proc_table[p].status = HCBS_ZOMBIE;
516
  lev->reactivation_timer[p] = kern_event_post(&lev->cbs_dline[p],
517
                                               HCBS_timer_zombie,
518
                                               (void *)p);
519
}
520
 
521
/* Registration functions */
522
 
523
/*+ Registration function:
524
    int flags                 the init flags ... see CBS.h +*/
525
LEVEL HCBS_register_level(int flags, LEVEL master)
526
{
527
  LEVEL l;            /* the level that we register */
528
  HCBS_level_des *lev;  /* for readableness only */
529
  PID i;              /* a counter */
530
 
531
  printk("HCBS_register_level\n");
532
 
533
  /* request an entry in the level_table */
534
  l = level_alloc_descriptor(sizeof(HCBS_level_des));
535
 
536
  lev = (HCBS_level_des *)level_table[l];
537
 
538
  printk("    lev=%d\n",(int)lev);
539
 
540
  /* fill the standard descriptor */
541
  if (flags & HCBS_ENABLE_GUARANTEE)
542
    lev->l.public_guarantee = HCBS_public_guarantee;
543
  else
544
    lev->l.public_guarantee = NULL;
545
  lev->l.public_create    = HCBS_public_create;
546
  lev->l.public_detach    = HCBS_public_detach;
547
  lev->l.public_end       = HCBS_public_end;
548
  lev->l.public_eligible  = HCBS_public_eligible;
549
  lev->l.public_dispatch  = HCBS_public_dispatch;
550
  lev->l.public_epilogue  = HCBS_public_epilogue;
551
  lev->l.public_activate  = HCBS_public_activate;
552
  lev->l.public_unblock   = HCBS_public_unblock;
553
  lev->l.public_block     = HCBS_public_block;
554
  lev->l.public_message   = HCBS_public_message;
555
 
556
  /* fill the CBS descriptor part */
557
  for (i=0; i<MAX_PROC; i++) {
558
     NULL_TIMESPEC(&lev->cbs_dline[i]);
559
     lev->period[i] = 0;
560
     NULL_TIMESPEC(&lev->reactivation_time[i]);
561
     lev->reactivation_timer[i] = -1;
562
     lev->nact[i] = 0;
563
     lev->flag[i] = 0;
564
  }
565
 
566
 
567
  lev->U = 0;
568
 
569
  lev->scheduling_level = master;
570
 
571
  lev->flags = flags;
572
 
573
  return l;
574
}
575
 
576
bandwidth_t HCBS_usedbandwidth(LEVEL l)
577
{
578
  HCBS_level_des *lev = (HCBS_level_des *)(level_table[l]);
579
 
580
  return lev->U;
581
}
582
 
583
int HCBS_get_nact(LEVEL l, PID p)
584
{
585
  HCBS_level_des *lev = (HCBS_level_des *)(level_table[l]);
586
 
587
  return lev->nact[p];
588
}
589