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