Subversion Repositories shark

Rev

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