Subversion Repositories shark

Rev

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

Rev Author Line No. Line
221 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
 *   Trimarchi Michael   <trimarchi@gandalf.sssup.it>
10
 *   (see the web pages for full authors list)
11
 *
12
 * ReTiS Lab (Scuola Superiore S.Anna - Pisa - Italy)
13
 *
14
 * http://www.sssup.it
15
 * http://retis.sssup.it
16
 * http://shark.sssup.it
17
 */
18
 
19
/*
20
 * Copyright (C) 2000 Paolo Gai
21
 *
22
 * This program is free software; you can redistribute it and/or modify
23
 * it under the terms of the GNU General Public License as published by
24
 * the Free Software Foundation; either version 2 of the License, or
25
 * (at your option) any later version.
26
 *
27
 * This program is distributed in the hope that it will be useful,
28
 * but WITHOUT ANY WARR2ANTY; without even the implied waRR2anty of
29
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
30
 * GNU General Public License for more details.
31
 *
32
 * You should have received a copy of the GNU General Public License
33
 * along with this program; if not, write to the Free Software
34
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
35
 *
36
 */
37
 
38
 
39
#include <ll/stdio.h>
40
#include <ll/string.h>
41
#include <kernel/model.h>
42
#include <kernel/descr.h>
43
#include <kernel/var.h>
44
#include <kernel/func.h>
45
#include <kernel/trace.h>
46
#include "posixstar.h"
47
#include "cbsstar.h"
48
#include "comm_message.h"
49
 
50
//#define POSIXSTAR_DEBUG
51
 
52
/*+ Status used in the level +*/
53
#define POSIXSTAR_READY   MODULE_STATUS_BASE
54
 
55
#define POSIXSTAR_CHANGE_LEVEL 1
56
 
57
/*+ the level redefinition for the Round Robin level +*/
58
typedef struct {
59
  level_des l;          /*+ the standard level descriptor          +*/
60
 
61
  int nact[MAX_PROC];   /*+ number of pending activations          +*/
62
 
63
  int priority[MAX_PROC]; /*+ priority of each task                +*/
64
 
65
  IQUEUE *ready;        /*+ the ready queue array                  +*/
66
 
67
  int slice;            /*+ the level's time slice                 +*/
68
 
69
//  the multiboot is not usefull for this module
70
//  struct multiboot_info *multiboot; /*+ used if the level have to insert
71
//                                        the main task +*/
72
 
73
  int maxpriority;      /*+ the priority are from 0 to maxpriority
74
                            (i.e 0 to 31)                          +*/
75
 
76
  int yielding;         /*+ equal to 1 when a sched_yield is called +*/
77
 
78
  int budget[MAX_PROC];
79
 
80
  PID activated;
81
  int scheduling_level;
82
 
83
  int flag[MAX_PROC];
84
 
85
  int new_level[MAX_PROC];
86
  int new_slice[MAX_PROC];
87
  int new_control[MAX_PROC];
88
 
89
} POSIXSTAR_level_des;
90
 
91
/* the private scheduler choice a task and insert in cbsstar module */
92
/* This is not efficient but very fair :-)
93
   The need of all this stuff is because if a task execute a long time
94
   due to (shadow!) priority inheritance, then the task shall go to the
95
   tail of the queue many times... */
96
 
97
static void POSIXSTAR_private_scheduler(POSIXSTAR_level_des * lev)
98
{
99
  /* the old posix scheduler select the private job for CBS */
100
  PID p = NIL;
101
 
102
  int prio;
103
 
104
  prio = lev->maxpriority;
105
 
106
  for (;;) {
107
    p = iq_query_first(&lev->ready[prio]);
108
    if (p == NIL) {
109
      if (prio) {
110
        prio--;
111
        continue;
112
      }
113
      else {
114
        p=NIL;
115
	break;
116
      }
117
    }
118
 
119
    if ((proc_table[p].control & CONTROL_CAP) &&
120
        (proc_table[p].avail_time <= 0)) {
121
      if (proc_table[p].avail_time<=0)
122
  	proc_table[p].avail_time += proc_table[p].wcet;
123
      iq_extract(p,&lev->ready[prio]);
124
      iq_insertlast(p,&lev->ready[prio]);
125
    }
126
    else {
127
      break;
128
    }
129
  }
130
 
131
  if (p!=lev->activated) {
132
    if (lev->activated != NIL )  {
133
     level_table[ lev->scheduling_level ]->
134
       private_extract(lev->scheduling_level, lev->activated);
135
   }
136
   lev->activated = p;
137
 
138
   if (p != NIL) {
139
     BUDGET_TASK_MODEL b;
140
     budget_task_default_model(b, lev->budget[p]);
141
     #ifdef POSIXSTAR_DEBUG
142
       kern_printf("(PS:SchAct:%d:%d)",p,lev->budget[p]);
143
     #endif
144
     level_table[ lev->scheduling_level ]->
145
       private_insert(lev->scheduling_level, p, (TASK_MODEL *)&b);
146
   }
147
 }
148
}
149
 
150
static int POSIXSTAR_public_eligible(LEVEL l, PID p)
151
{
152
  POSIXSTAR_level_des *lev = (POSIXSTAR_level_des *)(level_table[l]);
153
  if (p==lev->activated) {
154
    return level_table[ lev->scheduling_level ]->
155
      private_eligible(lev->scheduling_level,p);
156
  }
157
  return 0;
158
}
159
 
160
 
161
static int POSIXSTAR_public_create(LEVEL l, PID p, TASK_MODEL *m)
162
{
163
  POSIXSTAR_level_des *lev = (POSIXSTAR_level_des *)(level_table[l]);
164
  NRT_TASK_MODEL *nrt;
165
 
166
  /* DEBUG */
167
  #ifdef POSIXSTAR_DEBUG
168
    kern_printf("(PS:Crt:%d)",p);
169
  #endif
170
 
171
  if (m->pclass != NRT_PCLASS) return -1;
172
  if (m->level != 0 && m->level != l) return -1;
173
 
174
  nrt = (NRT_TASK_MODEL *)m;
175
 
176
  /* the task state is set at SLEEP by the general task_create */
177
 
178
  /* I used the wcet field because using wcet can account if a task
179
     consume more than the timeslice... */
180
 
181
  if (nrt->inherit == NRT_INHERIT_SCHED &&
182
      proc_table[exec_shadow].task_level == l) {
183
    /* We inherit the scheduling properties if the scheduling level
184
       *is* the same */
185
    lev->priority[p] = lev->priority[exec_shadow];
186
 
187
    proc_table[p].avail_time = proc_table[exec_shadow].avail_time;
188
    proc_table[p].wcet       = proc_table[exec_shadow].wcet;
189
 
190
    proc_table[p].control = (proc_table[p].control & ~CONTROL_CAP) |
191
                            (proc_table[exec_shadow].control & CONTROL_CAP);
192
 
193
    lev->nact[p] = (lev->nact[exec_shadow] == -1) ? -1 : 0;
194
  }
195
  else {
196
    if (nrt->weight<=lev->maxpriority)
197
      lev->priority[p] = nrt->weight;
198
    else lev->priority[p]=lev->maxpriority;
199
 
200
    if (nrt->slice) {
201
      proc_table[p].avail_time = nrt->slice;
202
      proc_table[p].wcet       = nrt->slice;
203
    }
204
    else {
205
      proc_table[p].avail_time = lev->slice;
206
      proc_table[p].wcet       = lev->slice;
207
    }
208
 
209
    if (nrt->policy == NRT_RR_POLICY) {
210
      proc_table[p].control   |= CONTROL_CAP;
211
    }
212
 
213
    if (nrt->arrivals == SAVE_ARRIVALS)
214
      lev->nact[p] = 0;
215
    else
216
      lev->nact[p] = -1;
217
 
218
  }
219
 
220
  return 0; /* OK */
221
}
222
 
223
static void POSIXSTAR_public_dispatch(LEVEL l, PID p, int nostop)
224
{
225
  POSIXSTAR_level_des *lev = (POSIXSTAR_level_des *)(level_table[l]);
226
 
227
  /* the task state is set EXE by the scheduler()
228
     we extract the task from the ready queue
229
     NB: we can't assume that p is the first task in the queue!!! */
230
 
231
  #ifdef POSIXSTAR_DEBUG
232
     kern_printf("(PS:Dsp:%d)",p);
233
  #endif
234
 
235
  if (p==lev->activated)
236
    level_table[lev->scheduling_level]->private_dispatch(lev->scheduling_level, p, nostop);
237
 
238
}
239
 
240
static void POSIXSTAR_public_epilogue(LEVEL l, PID p)
241
{
242
  POSIXSTAR_level_des *lev = (POSIXSTAR_level_des *)(level_table[l]);
243
 
244
  #ifdef POSIXSTAR_DEBUG
245
    kern_printf("(PS:Epi:%d)",p);
246
  #endif
247
 
248
  /* Change task level */
249
  if (lev->flag[p] & POSIXSTAR_CHANGE_LEVEL) {
250
 
251
    STD_command_message msg;
252
 
253
    proc_table[p].status = SLEEP;
254
    iq_extract(p,&lev->ready[lev->priority[p]]);
255
    POSIXSTAR_private_scheduler(lev);
256
    lev->budget[p] = -1;
257
    proc_table[p].task_level = lev->new_level[p];
258
    msg.command = STD_ACTIVATE_TASK;
259
    level_table[lev->new_level[p]] -> public_message(lev->new_level[p],p,&msg);
260
    return;
261
  }
262
 
263
  if (p==lev->activated) {
264
    if (lev->yielding) {
265
      lev->yielding = 0;
266
      iq_extract(p,&lev->ready[lev->priority[p]]);
267
      iq_insertlast(p,&lev->ready[lev->priority[p]]);
268
    }
269
    /* check if the slice is finished and insert the task in the coPOSIXect
270
       qqueue position */
271
    else if (proc_table[p].control & CONTROL_CAP &&
272
           proc_table[p].avail_time <= 0) {
273
 
274
      iq_extract(p,&lev->ready[lev->priority[p]]);
275
      iq_insertlast(p,&lev->ready[lev->priority[p]]);
276
 
277
      POSIXSTAR_private_scheduler(lev);
278
      if (p==lev->activated)
279
	level_table[lev->scheduling_level]->private_epilogue(lev->scheduling_level,p);
280
 
281
    }
282
    else  {
283
 
284
      level_table[lev->scheduling_level]->private_epilogue(lev->scheduling_level,p);
285
 
286
      POSIXSTAR_private_scheduler(lev);
287
 
288
    }
289
 
290
    proc_table[p].status = POSIXSTAR_READY;
291
 
292
  }
293
 
294
 
295
}
296
 
297
static void POSIXSTAR_internal_activate(POSIXSTAR_level_des *lev, PID p)
298
{
299
 
300
  /* Insert task in the correct position */
301
  proc_table[p].status = POSIXSTAR_READY;
302
  iq_insertlast(p,&lev->ready[lev->priority[p]]);
303
 
304
}
305
 
306
 
307
static void POSIXSTAR_public_activate(LEVEL l, PID p)
308
{
309
  POSIXSTAR_level_des *lev = (POSIXSTAR_level_des *)(level_table[l]);
310
 
311
  /* Test if we are trying to activate a non sleeping task    */
312
  /* save activation (only if needed...) */
313
  if (proc_table[p].status != SLEEP) {
314
    if (lev->nact[p] != -1)
315
      lev->nact[p]++;
316
    return;
317
  }
318
 
319
  #ifdef POSIXSTAR_DEBUG
320
    kern_printf("(PS:Act:%d)",p);
321
  #endif
322
 
323
  POSIXSTAR_internal_activate(lev, p);
324
  POSIXSTAR_private_scheduler(lev);
325
 
326
}
327
 
328
 
329
static void POSIXSTAR_public_unblock(LEVEL l, PID p)
330
{
331
  POSIXSTAR_level_des *lev = (POSIXSTAR_level_des *)(level_table[l]);
332
 
333
  /* Similar to POSIX_task_activate, but we don't check in what state
334
     the task is */
335
 
336
  #ifdef POSIXSTAR_DEBUG
337
    kern_printf("(PS:UnBlk:%d)",p);
338
  #endif
339
  /* Insert task in the coPOSIXect position */
340
  proc_table[p].status = POSIXSTAR_READY;
341
  iq_insertlast(p,&lev->ready[lev->priority[p]]);
342
  POSIXSTAR_private_scheduler(lev);
343
 
344
}
345
 
346
static void POSIXSTAR_public_block(LEVEL l, PID p)
347
{
348
  POSIXSTAR_level_des *lev = (POSIXSTAR_level_des *)(level_table[l]);
349
 
350
  /* Extract the running task from the level
351
     . we have already extract it from the ready queue at the dispatch time.
352
     . the capacity event have to be removed by the generic kernel
353
     . the wcet don't need modification...
354
     . the state of the task is set by the calling function
355
 
356
     So, we do nothing!!!
357
  */
358
 
359
  #ifdef POSIXSTAR_DEBUG
360
    kern_printf("(PS:Blk:%d)", p);
361
  #endif
362
 
363
  iq_extract(p,&lev->ready[lev->priority[p]]);
364
  if (p==lev->activated) lev->activated = NIL;
365
  POSIXSTAR_private_scheduler(lev);
366
 
367
}
368
 
369
static int POSIXSTAR_public_message(LEVEL l, PID p, void *m)
370
{
371
  POSIXSTAR_level_des *lev = (POSIXSTAR_level_des *)(level_table[l]);
372
  STD_command_message *msg;
373
  NRT_TASK_MODEL *nrt;
374
 
375
  #ifdef POSIXSTAR_DEBUG
376
    kern_printf("(PS:Msg:%d)",p);
377
  #endif
378
 
379
  switch ((long)(m)) {
380
 
381
    /* Task EndCycle */
382
    case (long)(NULL):
383
 
384
      if (lev->nact[p] > 0) {
385
        /* continue!!!! */
386
        lev->nact[p]--;
387
        iq_extract(p,&lev->ready[lev->priority[p]]);
388
        iq_insertfirst(p,&lev->ready[lev->priority[p]]);
389
        proc_table[p].status = POSIXSTAR_READY;
390
      }
391
      else {
392
        proc_table[p].status = SLEEP;
393
        iq_extract(p,&lev->ready[lev->priority[p]]);
394
      }
395
 
396
      jet_update_endcycle(); /* Update the Jet data... */
397
      trc_logevent(TRC_ENDCYCLE,&exec_shadow); /* tracer stuff */
398
      POSIXSTAR_private_scheduler(lev);
399
 
400
      break;
401
 
402
    /* Task Disable */
403
    case (long)(1):
404
 
405
      break;
406
 
407
    default:
408
 
409
      msg = (STD_command_message *)m;
410
 
411
      switch(msg->command) {
412
        case STD_SET_NEW_LEVEL:
413
 
414
          lev->flag[p] |= POSIXSTAR_CHANGE_LEVEL;
415
          lev->new_level[p] = (int)(msg->param);
416
 
417
          break;
418
        case STD_SET_NEW_MODEL:
419
 
420
          nrt = (NRT_TASK_MODEL *)(msg->param);
421
 
422
          lev->priority[p] = nrt->weight;
423
 
424
          if (nrt->slice) {
425
            lev->new_slice[p] = nrt->slice;
426
          } else {
427
            lev->new_slice[p] = 0;
428
          }
429
 
430
          if (nrt->policy == NRT_RR_POLICY)
431
            lev->new_control[p] |= CONTROL_CAP;
432
 
433
          if (nrt->arrivals == SAVE_ARRIVALS)
434
            lev->nact[p] = 0;
435
          else
436
            lev->nact[p] = -1;
437
 
438
          lev->flag[p] = 0;
439
 
440
          break;
441
       case STD_ACTIVATE_TASK:
442
 
443
         if (lev->new_slice[p]) {
444
           proc_table[p].avail_time = lev->new_slice[p];
445
           proc_table[p].wcet = lev->new_slice[p];
446
         } else {
447
           proc_table[p].avail_time = lev->slice;
448
           proc_table[p].wcet = lev->slice;
449
         }
450
 
224 giacomo 451
         proc_table[p].control |= lev->new_control[p];
221 giacomo 452
 
453
         POSIXSTAR_public_activate(l,p);
454
 
455
         break;
456
 
457
      }
458
 
459
  }
460
 
461
  return 0;
462
 
463
}
464
 
465
static void POSIXSTAR_public_end(LEVEL l, PID p)
466
{
467
  POSIXSTAR_level_des *lev = (POSIXSTAR_level_des *)(level_table[l]);
468
 
469
  #ifdef POSIXSTAR_DEBUG
470
    kern_printf("(PS:End:%d)", p);
471
  #endif
472
 
473
  lev->nact[p] = -1;
474
 
475
  /* then, we insert the task in the free queue */
476
  proc_table[p].status = FREE;
477
  iq_priority_insert(p,NULL);
478
  POSIXSTAR_private_scheduler(lev);
479
 
480
}
481
 
482
/* Registration functions */
483
 
484
/*+ Registration function:
485
    TIME slice                the slice for the Round Robin queue +*/
486
LEVEL POSIXSTAR_register_level(int master, TIME slice,
487
                       int prioritylevels)
488
{
489
  LEVEL l;            /* the level that we register */
490
  POSIXSTAR_level_des *lev;  /* for readableness only */
491
  PID i;              /* a counter */
492
  int x;              /* a counter */
493
 
494
  #ifdef POSIXSTRA_DEBUG
495
    kern_printf("POSIXSTAR_register_level\n");
496
  #endif
497
 
498
  l = level_alloc_descriptor(sizeof(POSIXSTAR_level_des));
499
 
500
  lev = (POSIXSTAR_level_des *)level_table[l];
501
 
502
  lev->l.public_create    = POSIXSTAR_public_create;
503
  lev->l.public_end       = POSIXSTAR_public_end;
504
  lev->l.public_dispatch  = POSIXSTAR_public_dispatch;
505
  lev->l.public_epilogue  = POSIXSTAR_public_epilogue;
506
  lev->l.public_activate  = POSIXSTAR_public_activate;
507
  lev->l.public_unblock   = POSIXSTAR_public_unblock;
508
  lev->l.public_block     = POSIXSTAR_public_block;
509
  lev->l.public_message   = POSIXSTAR_public_message;
510
  lev->l.public_eligible  = POSIXSTAR_public_eligible;
511
 
512
  /* fill the POSIX descriptor part */
513
  for (i = 0; i < MAX_PROC; i++) {
514
    lev->nact[i] = -1;
515
    lev->budget[i] = -1;
516
    lev->flag[i] = 0;
517
 
518
    lev->new_level[i] = 0;
519
    lev->new_slice[i] = 0;
520
    lev->new_control[i] = 0;
521
 
522
  }
523
 
524
  lev->maxpriority = prioritylevels - 1;
525
 
526
  lev->ready = (IQUEUE *)kern_alloc(sizeof(IQUEUE) * prioritylevels);
527
 
528
  for (x = 0; x < prioritylevels; x++)
529
    iq_init(&lev->ready[x], NULL, 0);
530
 
531
  if (slice < POSIXSTAR_MINIMUM_SLICE) slice = POSIXSTAR_MINIMUM_SLICE;
532
  if (slice > POSIXSTAR_MAXIMUM_SLICE) slice = POSIXSTAR_MAXIMUM_SLICE;
533
  lev->slice = slice;
534
  lev->activated = NIL;
535
  lev->scheduling_level = master;
536
 
537
  return l;
538
 
539
}
540
 
541
int POSIXSTAR_setbudget(LEVEL l, PID p, int budget)
542
{
543
 
544
  POSIXSTAR_level_des *lev = (POSIXSTAR_level_des *)(level_table[l]);
545
 
546
  lev->budget[p] = budget;
547
 
548
  return 0;
549
 
550
}
551
 
552
int POSIXSTAR_getbudget(LEVEL l, PID p)
553
{
554
 
555
  POSIXSTAR_level_des *lev = (POSIXSTAR_level_des *)(level_table[l]);
556
 
557
  return lev->budget[p];
558
 
559
}
560
 
561
int POSIXSTAR_budget_has_thread(LEVEL l, int budget)
562
{
563
 
564
  POSIXSTAR_level_des *lev = (POSIXSTAR_level_des *)(level_table[l]);
565
  int i;
566
 
567
  for(i = 0; i< MAX_PROC; i++)
568
    if (lev->budget[i] == budget) return 1;
569
 
570
  return 0;
571
 
572
}
573
 
574
/*+ this function forces the running task to go to his queue tail;
575
    (it works only on the POSIX level) +*/
576
int POSIXSTAR_sched_yield(LEVEL l)
577
{
578
  POSIXSTAR_level_des *lev = (POSIXSTAR_level_des *)(level_table[l]);
579
 
580
  if (proc_table[exec_shadow].task_level != l)
581
    return -1;
582
 
583
  proc_table[exec_shadow].context = kern_context_save();
584
  lev->yielding = 1;
585
  scheduler();
586
  kern_context_load(proc_table[exec_shadow].context);
587
  return 0;
588
}
589
 
590
/*+ this function returns the maximum level allowed for the POSIX level +*/
591
int POSIXSTAR_get_priority_max(LEVEL l)
592
{
593
  POSIXSTAR_level_des *lev = (POSIXSTAR_level_des *)(level_table[l]);
594
  return lev->maxpriority;
595
}
596
 
597
/*+ this function returns the default timeslice for the POSIX level +*/
598
int POSIXSTAR_rr_get_interval(LEVEL l)
599
{
600
  POSIXSTAR_level_des *lev = (POSIXSTAR_level_des *)(level_table[l]);
601
  return lev->slice;
602
}
603
 
604
/*+ this functions returns some paramaters of a task;
605
    policy must be NRT_RR_POLICY or NRT_FIFO_POLICY;
606
    priority must be in the range [0..prioritylevels]
607
    returns ENOSYS or ESRCH if there are problems +*/
608
int POSIXSTAR_getschedparam(LEVEL l, PID p, int *policy, int *priority)
609
{
610
  if (p<0 || p>= MAX_PROC || proc_table[p].status == FREE)
611
    return ESRCH;
612
 
613
  if (proc_table[p].task_level != l)
614
    return ENOSYS;
615
 
616
  if (proc_table[p].control & CONTROL_CAP)
617
    *policy = NRT_RR_POLICY;
618
  else
619
    *policy = NRT_FIFO_POLICY;
620
 
621
  *priority = ((POSIXSTAR_level_des *)(level_table[l]))->priority[p];
622
 
623
  return 0;
624
}
625
 
626
/*+ this functions sets paramaters of a task +*/
627
int POSIXSTAR_setschedparam(LEVEL l, PID p, int policy, int priority)
628
{
629
  POSIXSTAR_level_des *lev = (POSIXSTAR_level_des *)(level_table[l]);
630
 
631
  if (p<0 || p>= MAX_PROC || proc_table[p].status == FREE)
632
    return ESRCH;
633
 
634
  if (proc_table[p].task_level != l)
635
    return ENOSYS;
636
 
637
  if (policy == SCHED_RR)
638
    proc_table[p].control |= CONTROL_CAP;
639
  else if (policy == SCHED_FIFO)
640
    proc_table[p].control &= ~CONTROL_CAP;
641
  else
642
    return EINVAL;
643
 
644
  if (lev->priority[p] != priority) {
645
    if (proc_table[p].status == POSIXSTAR_READY) {
646
      iq_extract(p,&lev->ready[lev->priority[p]]);
647
      lev->priority[p] = priority;
648
      iq_insertlast(p,&lev->ready[priority]);
649
    }
650
    else
651
      lev->priority[p] = priority;
652
  }
653
 
654
  return 0;
655
}
656