Subversion Repositories shark

Rev

Rev 29 | Go to most recent revision | 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
 ------------
38 pj 23
 CVS :        $Id: ds.c,v 1.4 2003-01-07 17:07:50 pj Exp $
2 pj 24
 
25
 File:        $File$
38 pj 26
 Revision:    $Revision: 1.4 $
27
 Last update: $Date: 2003-01-07 17:07:50 $
2 pj 28
 ------------
29
 
30
 This file contains the aperiodic server DS (Deferrable Server)
31
 
32
 This module is directly derived from the Polling server one.
33
 All the notes writed for the PS are valid for the DS.
34
 
35
 The difference between DS and PS is that when there are not task to
36
 schedule the capacity is not reset to 0...
37
 
38
**/
39
 
40
/*
41
 * Copyright (C) 2000 Paolo Gai
42
 *
43
 * This program is free software; you can redistribute it and/or modify
44
 * it under the terms of the GNU General Public License as published by
45
 * the Free Software Foundation; either version 2 of the License, or
46
 * (at your option) any later version.
47
 *
48
 * This program is distributed in the hope that it will be useful,
49
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
50
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
51
 * GNU General Public License for more details.
52
 *
53
 * You should have received a copy of the GNU General Public License
54
 * along with this program; if not, write to the Free Software
55
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
56
 *
57
 */
58
 
59
 
60
#include <modules/ds.h>
61
#include <ll/stdio.h>
62
#include <ll/string.h>
63
#include <kernel/model.h>
64
#include <kernel/descr.h>
65
#include <kernel/var.h>
66
#include <kernel/func.h>
38 pj 67
#include <kernel/trace.h>
2 pj 68
 
69
/*+ Status used in the level +*/
70
#define DS_WAIT          APER_STATUS_BASE    /*+ waiting the service   +*/
71
 
72
/*+ the level redefinition for the Total Bandwidth Server level +*/
73
typedef struct {
74
  level_des l;     /*+ the standard level descriptor          +*/
75
 
76
  /* The wcet are stored in the task descriptor's priority
77
     field, so no other fields are needed                      */
78
 
79
  int nact[MAX_PROC]; /*+ number of pending activations       +*/
80
 
81
  struct timespec lastdline; /*+ the last deadline assigned to
82
                                 a DS task                    +*/
83
 
84
  int Cs;          /*+ server capacity                        +*/
85
  int availCs;     /*+ server avail time                      +*/
86
 
29 pj 87
  IQUEUE wait;      /*+ the wait queue of the DS              +*/
2 pj 88
  PID activated;   /*+ the task inserted in another queue     +*/
89
 
90
  int flags;       /*+ the init flags...                      +*/
91
 
92
  bandwidth_t U;   /*+ the used bandwidth by the server       +*/
93
  int period;
94
 
95
  LEVEL scheduling_level;
96
 
97
} DS_level_des;
98
 
99
/* This static function activates the task pointed by lev->activated) */
100
static __inline__ void DS_activation(DS_level_des *lev)
101
{
102
    PID p;                     /* for readableness    */
103
    JOB_TASK_MODEL j;          /* the guest model     */
104
    LEVEL m;                   /* the master level... only for readableness*/
105
 
106
    p = lev->activated;
107
    m = lev->scheduling_level;
108
    job_task_default_model(j,lev->lastdline);
109
    job_task_def_period(j,lev->period);
38 pj 110
    level_table[m]->private_insert(m,p,(TASK_MODEL *)&j);
2 pj 111
//    kern_printf("(%d %d)",lev->lastdline.tv_sec,lev->lastdline.tv_nsec);
112
}
113
 
114
static void DS_deadline_timer(void *a)
115
{
116
  DS_level_des *lev = (DS_level_des *)(level_table[(LEVEL)a]);
117
 
118
  ADDUSEC2TIMESPEC(lev->period, &lev->lastdline);
119
 
120
//  kern_printf("(%d:%d %d)",lev->lastdline.tv_sec,lev->lastdline.tv_nsec, lev->period);
121
  if (lev->availCs >= 0)
122
    lev->availCs = lev->Cs;
123
  else
124
    lev->availCs += lev->Cs;
125
 
126
  /* availCs may be <0 because a task executed via a shadow fo many time
127
     lev->activated == NIL only if the prec task was finished and there
128
     was not any other task to be put in the ready queue
129
     ... we are now activating the next task */
130
  if (lev->availCs > 0 && lev->activated == NIL) {
29 pj 131
      if (iq_query_first(&lev->wait) != NIL) {
132
        lev->activated = iq_getfirst(&lev->wait);
2 pj 133
        DS_activation(lev);
134
        event_need_reschedule();
135
      }
136
  }
137
 
138
  kern_event_post(&lev->lastdline, DS_deadline_timer, a);
139
//  kern_printf("!");
140
}
141
 
38 pj 142
static PID DS_public_schedulerbackground(LEVEL l)
2 pj 143
{
144
  /* the DS catch the background time to exec aperiodic activities */
145
  DS_level_des *lev = (DS_level_des *)(level_table[l]);
146
 
147
  lev->flags |= DS_BACKGROUND;
148
 
149
  if (lev->flags & DS_BACKGROUND_BLOCK)
150
    return NIL;
151
  else
29 pj 152
    return iq_query_first(&lev->wait);
2 pj 153
}
154
 
155
/* The on-line guarantee is enabled only if the appropriate flag is set... */
38 pj 156
static int DS_public_guaranteeEDF(LEVEL l, bandwidth_t *freebandwidth)
2 pj 157
{
158
  DS_level_des *lev = (DS_level_des *)(level_table[l]);
159
 
160
  if (*freebandwidth >= lev->U) {
161
    *freebandwidth -= lev->U;
162
    return 1;
163
  }
164
  else
165
    return 0;
166
}
167
 
38 pj 168
static int DS_public_guaranteeRM(LEVEL l, bandwidth_t *freebandwidth)
2 pj 169
{
170
  DS_level_des *lev = (DS_level_des *)(level_table[l]);
171
 
172
  if (*freebandwidth > lev->U + RM_MINFREEBANDWIDTH) {
173
    *freebandwidth -= lev->U;
174
    return 1;
175
  }
176
  else
177
    return 0;
178
}
179
 
38 pj 180
static int DS_public_create(LEVEL l, PID p, TASK_MODEL *m)
2 pj 181
{
182
  DS_level_des *lev = (DS_level_des *)(level_table[l]);
183
 
38 pj 184
  SOFT_TASK_MODEL *s;
2 pj 185
 
38 pj 186
  if (m->pclass != SOFT_PCLASS) return -1;
187
  if (m->level != 0 && m->level != l) return -1;
188
  s = (SOFT_TASK_MODEL *)m;
189
  if (s->periodicity != APERIODIC) return -1;
190
 
191
  s = (SOFT_TASK_MODEL *)m;
192
 
2 pj 193
  if (s->arrivals == SAVE_ARRIVALS)
194
    lev->nact[p] = 0;
195
  else
196
    lev->nact[p] = -1;
197
 
198
  return 0; /* OK, also if the task cannot be guaranteed... */
199
}
200
 
38 pj 201
static void DS_public_dispatch(LEVEL l, PID p, int nostop)
2 pj 202
{
203
  DS_level_des *lev = (DS_level_des *)(level_table[l]);
204
  struct timespec ty;
205
 
206
//  if (nostop) kern_printf("NOSTOP!!!!!!!!!!!!");
207
  /* there is at least one task ready inserted in an EDF or similar
208
     level note that we can't check the status because the scheduler set it
209
     to exe before calling task_dispatch. we have to check
210
     lev->activated != p instead */
211
  if (lev->activated != p) {
29 pj 212
    iq_extract(p, &lev->wait);
2 pj 213
    //kern_printf("#%d#",p);
214
  }
215
  else {
216
    //if (nostop) kern_printf("(gd status=%d)",proc_table[p].status);
217
    level_table[ lev->scheduling_level ]->
38 pj 218
      private_dispatch(lev->scheduling_level,p,nostop);
2 pj 219
  }
220
 
221
  /* set the capacity timer */
222
  if (!nostop) {
223
    TIMESPEC_ASSIGN(&ty, &schedule_time);
224
    ADDUSEC2TIMESPEC(lev->availCs,&ty);
225
    cap_timer = kern_event_post(&ty, capacity_timer, NULL);
226
  }
227
 
228
//  kern_printf("(disp %d %d)",ty.tv_sec, ty.tv_nsec);
229
}
230
 
38 pj 231
static void DS_public_epilogue(LEVEL l, PID p)
2 pj 232
{
233
  DS_level_des *lev = (DS_level_des *)(level_table[l]);
234
  struct timespec ty;
235
  TIME tx;
236
 
237
  /* update the server capacity */
238
  if (lev->flags & DS_BACKGROUND)
239
    lev->flags &= ~DS_BACKGROUND;
240
  else {
241
    SUBTIMESPEC(&schedule_time, &cap_lasttime, &ty);
242
    tx = TIMESPEC2USEC(&ty);
243
    lev->availCs -= tx;
244
  }
245
 
246
//  kern_printf("(epil %d %d)",lev->availCs, proc_table[p].avail_time);
247
 
248
  /* check if the server capacity is finished... */
249
  if (lev->availCs < 0) {
250
//    kern_printf("(epil Cs%d %d:%d act%d p%d)",
251
//              lev->availCs,proc_table[p].timespec_priority.tv_sec,
252
//              proc_table[p].timespec_priority.tv_nsec,
253
//              lev->activated,p);
254
    /* the server slice has finished... do the task_end!!!
255
       a first version of the module used the task_endcycle, but it was
256
       not conceptually correct because the task didn't stop because it
257
       finished all the work but because the server didn't have budget!
258
       So, if the task_endcycle is called, the task remain into the
259
       master level, and we can't wake him up if, for example, another
260
       task point the shadow to it!!!*/
261
    if (lev->activated == p)
262
      level_table[ lev->scheduling_level ]->
38 pj 263
        private_extract(lev->scheduling_level,p);
29 pj 264
    iq_insertfirst(p, &lev->wait);
2 pj 265
    proc_table[p].status = DS_WAIT;
266
    lev->activated = NIL;
267
  }
268
  else
269
    /* the task has been preempted. it returns into the ready queue or to the
270
       wait queue by calling the guest_epilogue... */
271
    if (lev->activated == p) {//kern_printf("Û1");
272
      level_table[ lev->scheduling_level ]->
38 pj 273
        private_epilogue(lev->scheduling_level,p);
2 pj 274
    } else { //kern_printf("Û2");
29 pj 275
      iq_insertfirst(p, &lev->wait);
2 pj 276
      proc_table[p].status = DS_WAIT;
277
    }
278
}
279
 
38 pj 280
static void DS_public_activate(LEVEL l, PID p)
2 pj 281
{
282
  DS_level_des *lev = (DS_level_des *)(level_table[l]);
283
 
284
  if (lev->activated == p || proc_table[p].status == DS_WAIT) {
285
    if (lev->nact[p] != -1)
286
      lev->nact[p]++;
287
  }
288
  else if (proc_table[p].status == SLEEP) {
289
 
290
    if (lev->activated == NIL && lev->availCs > 0) {
291
      lev->activated = p;
292
      DS_activation(lev);
293
    }
294
    else {
29 pj 295
      iq_insertlast(p, &lev->wait);
2 pj 296
      proc_table[p].status = DS_WAIT;
297
    }
298
  }
299
  else
300
  {  kern_printf("DS_REJ%d %d %d %d ",p, proc_table[p].status, lev->activated, lev->wait.first);
301
     return; }
302
 
303
}
304
 
38 pj 305
static void DS_public_unblock(LEVEL l, PID p)
2 pj 306
{
307
  DS_level_des *lev = (DS_level_des *)(level_table[l]);
308
 
309
  lev->flags &= ~DS_BACKGROUND_BLOCK;
310
 
311
  lev->activated = -1;
312
 
313
  /* when we reinsert the task into the system, the server capacity
314
     is always 0 because nobody executes with the DS before... */
29 pj 315
  iq_insertfirst(p, &lev->wait);
2 pj 316
  proc_table[p].status = DS_WAIT;
317
}
318
 
38 pj 319
static void DS_public_block(LEVEL l, PID p)
2 pj 320
{
321
  DS_level_des *lev = (DS_level_des *)(level_table[l]);
322
 
323
  /* update the server capacity */
324
  lev->availCs = 0;
325
 
326
  lev->flags |= DS_BACKGROUND_BLOCK;
327
 
328
  if (lev->activated == p)
329
    level_table[ lev->scheduling_level ]->
38 pj 330
      private_extract(lev->scheduling_level,p);
2 pj 331
}
332
 
38 pj 333
static int DS_public_message(LEVEL l, PID p, void *m)
2 pj 334
{
335
  DS_level_des *lev = (DS_level_des *)(level_table[l]);
336
  struct timespec ty;
337
  TIME tx;
338
 
339
  /* update the server capacity */
340
  if (lev->flags & DS_BACKGROUND)
341
    lev->flags &= ~DS_BACKGROUND;
342
  else {
343
    SUBTIMESPEC(&schedule_time, &cap_lasttime, &ty);
344
    tx = TIMESPEC2USEC(&ty);
345
    lev->availCs -= tx;
346
  }
347
 
348
  if (lev->activated == p)
349
    level_table[ lev->scheduling_level ]->
38 pj 350
      private_extract(lev->scheduling_level,p);
2 pj 351
  else
29 pj 352
    iq_extract(p, &lev->wait);
2 pj 353
 
354
  if (lev->nact[p] > 0)
355
  {
356
    lev->nact[p]--;
29 pj 357
    iq_insertlast(p, &lev->wait);
2 pj 358
    proc_table[p].status = DS_WAIT;
359
  }
360
  else
361
    proc_table[p].status = SLEEP;
362
 
29 pj 363
  lev->activated = iq_getfirst(&lev->wait);
2 pj 364
  if (lev->activated != NIL)
365
    DS_activation(lev);
38 pj 366
 
367
  jet_update_endcycle(); /* Update the Jet data... */
368
  trc_logevent(TRC_ENDCYCLE,&exec_shadow); /* tracer stuff */
369
 
370
  return 0;
2 pj 371
}
372
 
38 pj 373
static void DS_public_end(LEVEL l, PID p)
2 pj 374
{
375
  DS_level_des *lev = (DS_level_des *)(level_table[l]);
376
  struct timespec ty;
377
  TIME tx;
378
 
379
  /* update the server capacity */
380
  if (lev->flags & DS_BACKGROUND)
381
    lev->flags &= ~DS_BACKGROUND;
382
  else {
383
    SUBTIMESPEC(&schedule_time, &cap_lasttime, &ty);
384
    tx = TIMESPEC2USEC(&ty);
385
    lev->availCs -= tx;
386
  }
387
 
388
  if (lev->activated == p)
389
    level_table[ lev->scheduling_level ]->
38 pj 390
      private_extract(lev->scheduling_level,p);
2 pj 391
 
392
  proc_table[p].status = FREE;
29 pj 393
  iq_insertfirst(p,&freedesc);
2 pj 394
 
29 pj 395
  lev->activated = iq_getfirst(&lev->wait);
2 pj 396
  if (lev->activated != NIL)
397
    DS_activation(lev);
398
}
399
 
400
/* Registration functions */
401
 
402
 
403
/*+ This init function install the DS deadline timer
404
    +*/
405
static void DS_dline_install(void *l)
406
{
407
  DS_level_des *lev = (DS_level_des *)(level_table[(LEVEL)l]);
408
 
38 pj 409
  kern_gettime(&lev->lastdline);
2 pj 410
  ADDUSEC2TIMESPEC(lev->period, &lev->lastdline);
411
 
412
  kern_event_post(&lev->lastdline, DS_deadline_timer, l);
413
}
414
 
415
 
416
 
417
/*+ Registration function:
418
    int flags                 the init flags ... see DS.h +*/
38 pj 419
LEVEL DS_register_level(int flags, LEVEL master, int Cs, int per)
2 pj 420
{
421
  LEVEL l;            /* the level that we register */
422
  DS_level_des *lev;  /* for readableness only */
423
  PID i;              /* a counter */
424
 
425
  printk("DS_register_level\n");
426
 
427
  /* request an entry in the level_table */
38 pj 428
  l = level_alloc_descriptor(sizeof(DS_level_des));
2 pj 429
 
38 pj 430
  lev = (DS_level_des *)level_table[l];
2 pj 431
 
432
  printk("    lev=%d\n",(int)lev);
433
 
434
  /* fill the standard descriptor */
435
 
436
  if (flags & DS_ENABLE_BACKGROUND)
38 pj 437
    lev->l.public_scheduler = DS_public_schedulerbackground;
2 pj 438
 
439
  if (flags & DS_ENABLE_GUARANTEE_EDF)
38 pj 440
    lev->l.public_guarantee = DS_public_guaranteeEDF;
2 pj 441
  else if (flags & DS_ENABLE_GUARANTEE_RM)
38 pj 442
    lev->l.public_guarantee = DS_public_guaranteeRM;
2 pj 443
  else
38 pj 444
    lev->l.public_guarantee = NULL;
2 pj 445
 
38 pj 446
  lev->l.public_create    = DS_public_create;
447
  lev->l.public_end       = DS_public_end;
448
  lev->l.public_dispatch  = DS_public_dispatch;
449
  lev->l.public_epilogue  = DS_public_epilogue;
450
  lev->l.public_activate  = DS_public_activate;
451
  lev->l.public_unblock   = DS_public_unblock;
452
  lev->l.public_block     = DS_public_block;
453
  lev->l.public_message   = DS_public_message;
2 pj 454
 
455
  /* fill the DS descriptor part */
456
 
457
  for (i=0; i<MAX_PROC; i++)
458
     lev->nact[i] = -1;
459
 
460
  lev->Cs = Cs;
461
  lev->availCs = 0;
462
 
463
  lev->period = per;
464
 
29 pj 465
  iq_init(&lev->wait, &freedesc, 0);
2 pj 466
  lev->activated = NIL;
467
 
468
  lev->U = (MAX_BANDWIDTH / per) * Cs;
469
 
470
  lev->scheduling_level = master;
471
 
472
  lev->flags = flags & 0x07;
473
 
474
  sys_atrunlevel(DS_dline_install,(void *) l, RUNLEVEL_INIT);
38 pj 475
 
476
  return l;
2 pj 477
}
478
 
479
bandwidth_t DS_usedbandwidth(LEVEL l)
480
{
481
  DS_level_des *lev = (DS_level_des *)(level_table[l]);
38 pj 482
  return lev->U;
2 pj 483
}
484