Subversion Repositories shark

Rev

Rev 1116 | Rev 1176 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
1089 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
 ------------
1123 pj 23
 CVS :        $Id: cbsstar.c,v 1.4 2003-01-07 17:10:16 pj Exp $
1089 pj 24
 
25
 File:        $File$
1123 pj 26
 Revision:    $Revision: 1.4 $
27
 Last update: $Date: 2003-01-07 17:10:16 $
1089 pj 28
 ------------
29
 
30
 Read CBSSTAR.h for general details.
31
 
32
 Basically, a budget can be in 2 states:
33
 - Active -> the budget queue is not empty
34
 - Idle   -> the budget queue is empty
35
 
36
 The fact that a task into a budget is inserted into the master module depends
37
 on the value of the remaining time the tasks can spend in the period.
38
 
39
 The module does handle only one oslib event, used to enforce the
40
 temporal isolation between buffers. Note that all is implemented
41
 without using the CONTROL_CAP field.
42
 
43
 Basically, for each budget there can be at most one task inserted
44
 into the master level. Its deadline is modified according to the
45
 usage of its capacity, that is, when a budget is exausted its
46
 deadline is postponed.
47
 
48
*/
49
 
50
/*
51
 * Copyright (C) 2002 Paolo Gai
52
 *
53
 * This program is free software; you can redistribute it and/or modify
54
 * it under the terms of the GNU General Public License as published by
55
 * the Free Software Foundation; either version 2 of the License, or
56
 * (at your option) any later version.
57
 *
58
 * This program is distributed in the hope that it will be useful,
59
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
60
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
61
 * GNU General Public License for more details.
62
 *
63
 * You should have received a copy of the GNU General Public License
64
 * along with this program; if not, write to the Free Software
65
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
66
 *
67
 */
68
 
69
 
70
#include "cbsstar.h"
71
#include <ll/string.h>
72
 
73
 
74
/*
75
 * DEBUG stuffs begin
76
 */
77
 
78
//#define CBSSTAR_DEBUG
79
 
1123 pj 80
#ifdef CBSSTAR_DEBUG
1089 pj 81
 
82
static __inline__ void fake_printf(char *fmt, ...) {}
83
 
84
//#define cbsstar_printf kern_printf
85
//#define cbsstar_printf2 kern_printf
86
//#define cbsstar_printf3 kern_printf
87
 
88
#define cbsstar_printf fake_printf
89
#define cbsstar_printf2 fake_printf
90
#define cbsstar_printf3 fake_printf
91
 
92
#if 0
93
void cbsstar_printq(QQUEUE *q)
94
{
95
  PID p;
96
  kern_printf("[");
97
  p = q->first;
98
  kern_printf("->%d",p);
99
  while (p != NIL) {
100
    p = proc_table[p].next;
101
    kern_printf("->%d",p);
102
  }
103
  kern_printf("]");
104
}
105
#else
106
static __inline__ void cbsstar_printq(QQUEUE *q) {}
107
#endif
108
 
109
#if 0
110
static __inline__ void cbsstar_printblob(int x) { if (x) cputc('±'); else cputc('Û'); }
111
#else
112
static __inline__ void cbsstar_printblob(int x) {}
113
#endif
114
 
115
#endif
116
 
117
/*
118
 * DEBUG stuffs end
119
 */
120
 
121
 
122
/* this structure contains the status for a single budget */
123
struct budget_struct {
124
  TIME Q;                 /* budget */
125
  TIME T;                 /* period */
126
 
127
  struct timespec dline;  /* deadline */
128
  int dline_timer;        /* oslib event for budget reactivation*/
129
  int avail;              /* current budget */
130
 
131
  PID current;            /* the task currently put in execution */
132
 
1116 pj 133
  IQUEUE tasks;           /* a FIFO queue for the tasks handled
1089 pj 134
                             using the budget */
135
};
136
 
137
typedef struct {
138
  level_des l;               /* the standard level descriptor */
139
 
140
  struct budget_struct *b;   /* the budgets! */
141
  int n;                     /* the maximum index for the budgets */
142
  int freebudgets;           /* number of free budgets; starts from n */
143
 
144
  int tb[MAX_PROC];          /* link task->budget (used in guest_end) */
145
 
146
  bandwidth_t U;   /*+ the used bandwidth by the server       +*/
147
 
148
  LEVEL scheduling_level;
149
 
150
} CBSSTAR_level_des;
151
 
152
 
153
static void CBSSTAR_activation(CBSSTAR_level_des *lev,
154
                           PID p,
155
                           struct timespec *acttime)
156
{
157
  JOB_TASK_MODEL job;
158
  struct budget_struct *b = &lev->b[lev->tb[p]];
159
 
160
  /* we have to check if the deadline and the wcet are correct before
161
     activating a new task or an old task... */
162
 
163
  /* check 1: if the deadline is before than the actual scheduling time */
164
 
165
  /* check 2: if ( avail_time >= (cbs_dline - acttime)* (wcet/period) )
166
     (rule 7 in the CBS article!) */
167
  TIME t;
168
  struct timespec t2,t3;
169
 
170
  t = (b->T * b->avail) / b->Q;
171
  t3.tv_sec = t / 1000000;
172
  t3.tv_nsec = (t % 1000000) * 1000;
173
 
174
  SUBTIMESPEC(&b->dline, acttime, &t2);
175
 
176
  if (/* 1 */ TIMESPEC_A_LT_B(&b->dline, acttime) ||
177
      /* 2 */ TIMESPEC_A_GT_B(&t3, &t2) ) {
178
/*    if (TIMESPEC_A_LT_B(&lev->cbs_dline[p], acttime) )
179
      kern_printf("$");
180
    else
181
      kern_printf("(Ûdline%d.%d act%d.%d wcet%d per%d avail%dÛ)",
182
                  lev->cbs_dline[p].tv_sec,lev->cbs_dline[p].tv_nsec/1000,
183
                  acttime->tv_sec, acttime->tv_nsec/1000,
184
                  proc_table[p].wcet, lev->period[p], proc_table[p].avail_time);
185
*/  /* we modify the deadline ... */
186
    TIMESPEC_ASSIGN(&b->dline, acttime);
187
    ADDUSEC2TIMESPEC(b->T, &b->dline);
188
 
189
    /* and the capacity */
190
    b->avail = b->Q;
191
 
192
#ifdef CBSSTAR_DEBUG
193
    cbsstar_printf3("±%d±",lev->tb[p]);
194
    cbsstar_printblob(lev->tb[p]);
195
#endif
196
  }
197
 
198
  /* record the current task inserted in the master module */
199
  b->current = p;
200
 
201
#ifdef CBSSTAR_DEBUG
202
  cbsstar_printf("(C:iact p%d %ld.%ld av=%d)",p,b->dline.tv_sec,b->dline.tv_nsec/1000, b->avail);
203
#endif
204
 
205
  /* and, finally, we reinsert the task in the master level */
206
  job_task_default_model(job, b->dline);
207
  job_task_def_noexc(job);
208
  level_table[ lev->scheduling_level ]->
1123 pj 209
    private_insert(lev->scheduling_level, p, (TASK_MODEL *)&job);
1089 pj 210
}
211
 
212
 
213
static void CBSSTAR_account_capacity(CBSSTAR_level_des *lev, PID p)
214
{
215
  struct timespec ty;
216
  TIME tx;
217
 
218
  SUBTIMESPEC(&schedule_time, &cap_lasttime, &ty);
219
  tx = TIMESPEC2USEC(&ty);
220
  lev->b[lev->tb[p]].avail -= tx;
221
 
222
#ifdef CBSSTAR_DEBUG
223
  cbsstar_printf2("(C:cap p%d av=%d)", p, lev->b[lev->tb[p]].avail);
224
#endif
225
}
226
 
227
 
228
/* The on-line guarantee is enabled only if the appropriate flag is set... */
1123 pj 229
static int CBSSTAR_public_guarantee(LEVEL l, bandwidth_t *freebandwidth)
1089 pj 230
{
231
  CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
232
 
233
#ifdef CBSSTAR_DEBUG
234
  cbsstar_printf("(C:gua)");
235
#endif
236
 
237
  if (*freebandwidth >= lev->U) {
238
    *freebandwidth -= lev->U;
239
    return 1;
240
  }
241
  else
242
    return 0;
243
}
244
 
1123 pj 245
static int CBSSTAR_private_eligible(LEVEL l, PID p)
1089 pj 246
{
247
  CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
248
  struct budget_struct *b = &lev->b[lev->tb[p]];
249
  JOB_TASK_MODEL job;
250
 
251
#ifdef CBSSTAR_DEBUG
252
  cbsstar_printf("(C:eli %d",p);
253
#endif
254
 
255
  /* we have to check if the deadline and the wcet are correct...
256
     if the CBSSTAR level schedules in background with respect to others
257
     levels, there can be the case in witch a task is scheduled by
258
     schedule_time > CBSSTAR_deadline; in this case (not covered in the
259
     article because if there is only the standard scheduling policy
260
     this never apply) we reassign the deadline */
261
 
262
  if ( TIMESPEC_A_LT_B(&b->dline, &schedule_time) ) {
263
    /* we kill the current activation */
264
    level_table[ lev->scheduling_level ]->
1123 pj 265
      private_extract(lev->scheduling_level, p);
1089 pj 266
 
267
    /* we modify the deadline ... */
268
    TIMESPEC_ASSIGN(&b->dline, &schedule_time);
269
    ADDUSEC2TIMESPEC(b->T, &b->dline);
270
 
271
    /* and the capacity */
272
    b->avail = b->Q;
273
 
274
#ifdef CBSSTAR_DEBUG
275
    cbsstar_printf2(" %ld.%ld av=%d)",b->dline.tv_sec,b->dline.tv_nsec/1000, b->Q);
276
    cbsstar_printf3("±%d±",lev->tb[p]);
277
    cbsstar_printblob(lev->tb[p]);
278
#endif
279
 
280
    /* and, finally, we reinsert the task in the master level */
281
    job_task_default_model(job, b->dline);
282
    job_task_def_noexc(job);
283
    level_table[ lev->scheduling_level ]->
1123 pj 284
      private_insert(lev->scheduling_level, p, (TASK_MODEL *)&job);
1089 pj 285
 
286
    return -1;
287
  }
288
#ifdef CBSSTAR_DEBUG
289
  cbsstar_printf(")");
290
#endif
291
 
292
  return 0;
293
}
294
 
1123 pj 295
static void CBSSTAR_private_insert(LEVEL l, PID p, TASK_MODEL *m)
1089 pj 296
{
297
  /* A task has been activated for some reason. Basically, the task is
298
  inserted in the queue if the queue is empty, otherwise the task is
299
  inserted into the master module, and an oslib event is posted. */
300
 
301
  CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
1123 pj 302
  BUDGET_TASK_MODEL *budget;
1089 pj 303
 
1123 pj 304
  if (m->pclass != BUDGET_PCLASS ||
305
      (m->level != 0 && m->level != l)) {
306
    kern_raise(XINVALID_TASK, p);
307
    return;
308
  }
309
  budget = (BUDGET_TASK_MODEL *)m;
310
 
1089 pj 311
#ifdef CBSSTAR_DEBUG
312
  cbsstar_printf("(C:gcr %d b%d", p, budget->b);
313
#endif
314
 
315
  lev->tb[p] = budget->b;
316
 
317
  if (lev->b[budget->b].current == NIL) {
318
    /* This is the first task in the budget,
319
       the task have to be inserted into the master module */
320
    struct timespec t;
1123 pj 321
    kern_gettime(&t);
1089 pj 322
    CBSSTAR_activation(lev,p,&t);
323
  } else {
324
    /* The budget is not empty, another task is already into the
325
       master module, so the task is inserted at the end of the budget
326
       queue */
1116 pj 327
    iq_insertlast(p,&lev->b[budget->b].tasks);
1089 pj 328
#ifdef CBSSTAR_DEBUG
329
    cbsstar_printf(" ilast");
330
    cbsstar_printq(&lev->b[budget->b].tasks);
331
#endif
332
  }
333
#ifdef CBSSTAR_DEBUG
334
  cbsstar_printf(")");
335
#endif
336
}
337
 
1123 pj 338
static void CBSSTAR_private_extract(LEVEL l, PID p)
1089 pj 339
{
340
  CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
341
 
342
#ifdef CBSSTAR_DEBUG
343
  cbsstar_printf("(C:gend p%d c%d av=%d)", p, lev->b[lev->tb[p]].current, lev->b[lev->tb[p]].avail);
344
  cbsstar_printq(&lev->b[lev->tb[p]].tasks);
345
#endif
346
 
347
  /* a task is removed from execution for some reasons. It must be
348
     that it is the first in its budget queue (only the first task in
349
     a budget queue is put into execution!) */
350
  CBSSTAR_account_capacity(lev,p);
351
 
352
  /* remove the task from execution (or from the ready queue) */
353
  if (lev->b[lev->tb[p]].current == p) {
354
    /* remove the task from the master module */
355
    level_table[ lev->scheduling_level ]->
1123 pj 356
      private_extract(lev->scheduling_level, p);
1089 pj 357
 
358
#ifdef CBSSTAR_DEBUG
359
    cbsstar_printq(&lev->b[lev->tb[p]].tasks);
360
#endif
361
 
362
    /* check if the buffer has someone else to schedule */
1116 pj 363
    if (iq_query_first(&lev->b[lev->tb[p]].tasks) == NIL) {
1089 pj 364
      /* the buffer has no tasks! */
365
      lev->b[lev->tb[p]].current = NIL;
366
    }
367
    else {
368
      /* if so, insert the new task into the master module */
369
      PID n;
370
      struct timespec t;
371
 
1123 pj 372
      kern_gettime(&t);
1116 pj 373
      n = iq_getfirst(&lev->b[lev->tb[p]].tasks);
1089 pj 374
#ifdef CBSSTAR_DEBUG
375
      cbsstar_printf("{p%d n%d}",p,n);
376
#endif
377
      CBSSTAR_activation(lev,n,&t);  // it modifies b[lev->tb[p]].current
378
    }
379
  }
380
  else
1116 pj 381
    iq_extract(p, &lev->b[lev->tb[p]].tasks);
1089 pj 382
}
383
 
1123 pj 384
static void CBSSTAR_private_dispatch(LEVEL l, PID p, int nostop)
1089 pj 385
{
386
  CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
387
  struct timespec ty;
388
 
389
#ifdef CBSSTAR_DEBUG
390
  cbsstar_printf("(C:gdisp p%d c%d av=%d)", p, lev->b[lev->tb[p]].current, lev->b[lev->tb[p]].avail);
391
  cbsstar_printq(&lev->b[lev->tb[p]].tasks);
392
#endif
393
 
394
  /* the current task (that is the only one inserted in the master module
395
     for the corresponding budget) is dispatched. Note that the current
396
     task is not inserted in any FIFO queue, so the task does not have to
397
     be extracted! */
398
 
399
  /* ... then, we dispatch it to the master level */
400
  level_table[ lev->scheduling_level ]->
1123 pj 401
    private_dispatch(lev->scheduling_level,p,nostop);
1089 pj 402
 
403
  /* ...and finally, we have to post a capacity event */
404
  if (!nostop) {
405
    TIMESPEC_ASSIGN(&ty, &schedule_time);
406
    ADDUSEC2TIMESPEC(lev->b[lev->tb[p]].avail,&ty);
407
    cap_timer = kern_event_post(&ty, capacity_timer, NULL);
408
  }
409
}
410
 
1123 pj 411
static void CBSSTAR_private_epilogue(LEVEL l, PID p)
1089 pj 412
{
413
  CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
414
  struct budget_struct *b = &lev->b[lev->tb[p]];
415
 
416
#ifdef CBSSTAR_DEBUG
417
  cbsstar_printf("(C:gepi %d",p);
418
#endif
419
 
420
  CBSSTAR_account_capacity(lev,p);
421
 
422
  /* we have to check if the capacity is still available */
423
  if (b->avail > 0) {
424
    /* there is capacity available, maybe it is simply a preemption;
425
       the task have to return to the ready queue */
426
    level_table[ lev->scheduling_level ]->
1123 pj 427
      private_epilogue(lev->scheduling_level,p);
1089 pj 428
#ifdef CBSSTAR_DEBUG
429
    cbsstar_printf2(" *av=%d", b->avail);
430
#endif
431
  } else {
432
    /* The capacity is exausted; the deadline have to be postponed and
433
       the task have to be reinserted in the master module */
434
    JOB_TASK_MODEL job;
435
 
436
    /* we kill the current activation */
437
    level_table[ lev->scheduling_level ]->
1123 pj 438
      private_extract(lev->scheduling_level, p);
1089 pj 439
 
440
    /* we modify the deadline according to rule 4 ... */
441
    /* there is a while because if the wcet is << than the system tick
442
       we need to postpone the deadline many times */
443
    while (b->avail <= 0) {
444
      ADDUSEC2TIMESPEC(b->T, &b->dline);
445
      b->avail += b->Q;
446
#ifdef CBSSTAR_DEBUG
447
      cbsstar_printf3("±%d±",lev->tb[p]);
448
      cbsstar_printblob(lev->tb[p]);
449
#endif
450
    }
451
 
452
#ifdef CBSSTAR_DEBUG
453
    cbsstar_printf2(" %ld.%ld av=%d",b->dline.tv_sec,b->dline.tv_nsec/1000, b->avail);
454
#endif
455
 
456
    /* and, finally, we reinsert the task in the master level */
457
    job_task_default_model(job, b->dline);
458
    job_task_def_noexc(job);
459
    level_table[ lev->scheduling_level ]->
1123 pj 460
      private_insert(lev->scheduling_level, p, (TASK_MODEL *)&job);
1089 pj 461
  }
462
#ifdef CBSSTAR_DEBUG
463
  cbsstar_printf(")");
464
#endif
465
}
466
 
467
 
468
/* Registration functions */
469
 
470
/*+ Registration function:
471
    int flags                 the init flags ... see CBSSTAR.h +*/
472
LEVEL CBSSTAR_register_level(int n, LEVEL master)
473
{
474
  LEVEL l;            /* the level that we register */
475
  CBSSTAR_level_des *lev;  /* for readableness only */
476
  PID i;              /* a counter */
477
 
478
#ifdef CBSSTAR_DEBUG
479
  cbsstar_printf("CBSSTAR_register_level\n");
480
#endif
481
 
482
  /* request an entry in the level_table */
1123 pj 483
  l = level_alloc_descriptor(sizeof(CBSSTAR_level_des));
1089 pj 484
 
1123 pj 485
  lev = (CBSSTAR_level_des *)level_table[l];
1089 pj 486
 
1123 pj 487
  printk("    lev=%d\n",(int)lev);
1089 pj 488
 
489
  /* fill the standard descriptor */
1123 pj 490
  lev->l.private_insert   = CBSSTAR_private_insert;
491
  lev->l.private_extract  = CBSSTAR_private_extract;
492
  lev->l.private_eligible = CBSSTAR_private_eligible;
493
  lev->l.private_dispatch = CBSSTAR_private_dispatch;
494
  lev->l.private_epilogue = CBSSTAR_private_epilogue;
1089 pj 495
 
1123 pj 496
  lev->l.public_guarantee = CBSSTAR_public_guarantee;
1089 pj 497
 
498
  /* fill the CBSSTAR descriptor part */
499
  lev->b = (struct budget_struct *)kern_alloc(sizeof(struct budget_struct)*n);
500
 
501
  for (i=0; i<n; i++) {
502
    lev->b[i].Q = 0;
503
    lev->b[i].T = 0;
504
    NULL_TIMESPEC(&lev->b[i].dline);
505
    lev->b[i].dline_timer = 0;
506
    lev->b[i].avail = 0;
507
    lev->b[i].current = -1;
1116 pj 508
    iq_init(&lev->b[i].tasks, &freedesc, 0);
1089 pj 509
  }
510
 
511
  lev->n = n;
512
  lev->freebudgets = 0;
513
 
514
  for (i=0; i<MAX_PROC; i++)
515
    lev->tb[i] = NIL;
516
 
517
  lev->U = 0;
518
 
519
  lev->scheduling_level = master;
520
 
521
  return l;
522
}
523
 
524
int CBSSTAR_setbudget(LEVEL l, TIME Q, TIME T)
525
{
526
  CBSSTAR_level_des *lev = (CBSSTAR_level_des *)(level_table[l]);
527
 
528
#ifdef CBSSTAR_DEBUG
529
  cbsstar_printf("(C:sbud)");
530
#endif
531
 
1123 pj 532
  if (lev->freebudgets != lev->n) {
533
    bandwidth_t b;
534
    b = (MAX_BANDWIDTH / T) * Q;
535
 
536
    /* really update lev->U, checking an overflow... */
537
    if (Q< T && MAX_BANDWIDTH - lev->U > b) {
538
      int r = lev->freebudgets;  // the return value
1089 pj 539
 
1123 pj 540
      lev->U += b;
541
      lev->freebudgets++;
542
 
543
      lev->b[r].Q = Q;
544
      lev->b[r].T = T;
545
 
546
      return r;
1089 pj 547
    }
548
    else
1123 pj 549
      return -2;
1089 pj 550
  }
551
  else
1123 pj 552
    return -1;
1089 pj 553
}