Subversion Repositories shark

Rev

Rev 3 | Go to most recent revision | Details | 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
 ------------
23
 CVS :        $Id: rr2.c,v 1.1.1.1 2002-03-29 14:12:52 pj Exp $
24
 
25
 File:        $File$
26
 Revision:    $Revision: 1.1.1.1 $
27
 Last update: $Date: 2002-03-29 14:12:52 $
28
 ------------
29
 
30
 This file contains the scheduling module RR2 (Round Robin) version 2
31
 
32
 Read rr2.h for further details.
33
 
34
**/
35
 
36
/*
37
 * Copyright (C) 2000 Paolo Gai
38
 *
39
 * This program is free software; you can redistribute it and/or modify
40
 * it under the terms of the GNU General Public License as published by
41
 * the Free Software Foundation; either version 2 of the License, or
42
 * (at your option) any later version.
43
 *
44
 * This program is distributed in the hope that it will be useful,
45
 * but WITHOUT ANY WARR2ANTY; without even the implied waRR2anty of
46
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
47
 * GNU General Public License for more details.
48
 *
49
 * You should have received a copy of the GNU General Public License
50
 * along with this program; if not, write to the Free Software
51
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
52
 *
53
 */
54
 
55
 
56
#include <modules/rr2.h>
57
#include <ll/stdio.h>
58
#include <ll/string.h>
59
#include <kernel/model.h>
60
#include <kernel/descr.h>
61
#include <kernel/var.h>
62
#include <kernel/func.h>
63
 
64
/*+ Status used in the level +*/
65
#define RR2_READY   MODULE_STATUS_BASE
66
#define RR2_DELAY   MODULE_STATUS_BASE+1
67
 
68
/*+ the level redefinition for the Round Robin level +*/
69
typedef struct {
70
  level_des l;     /*+ the standard level descriptor          +*/
71
 
72
  int nact[MAX_PROC]; /*+ number of pending activations       +*/
73
 
74
  QQUEUE ready;    /*+ the ready queue                        +*/
75
 
76
  int slice;       /*+ the level's time slice                 +*/
77
 
78
  struct multiboot_info *multiboot; /*+ used if the level have to insert
79
                                        the main task +*/
80
} RR2_level_des;
81
 
82
 
83
static char *RR2_status_to_a(WORD status)
84
{
85
  if (status < MODULE_STATUS_BASE)
86
    return status_to_a(status);
87
 
88
  switch (status) {
89
    case RR2_READY: return "RR2_Ready";
90
    case RR2_DELAY: return "RR2_Delay";
91
    default      : return "RR2_Unknown";
92
  }
93
}
94
 
95
/*+ this function is called when a task finish his delay +*/
96
static void RR2_timer_delay(void *par)
97
{
98
  PID p = (PID) par;
99
  RR2_level_des *lev;
100
 
101
  lev = (RR2_level_des *)level_table[proc_table[p].task_level];
102
 
103
  proc_table[p].status = RR2_READY;
104
  qq_insertlast(p,&lev->ready);
105
 
106
  proc_table[p].delay_timer = NIL;  /* Paranoia */
107
 
108
//  kern_printf(" DELAY TIMER %d ", p);
109
 
110
  event_need_reschedule();
111
}
112
 
113
 
114
static int RR2_level_accept_task_model(LEVEL l, TASK_MODEL *m)
115
{
116
  if (m->pclass == NRT_PCLASS || m->pclass == (NRT_PCLASS | l))
117
    return 0;
118
  else
119
    return -1;
120
}
121
 
122
static int RR2_level_accept_guest_model(LEVEL l, TASK_MODEL *m)
123
{
124
    return -1;
125
}
126
 
127
static void RR2_level_status(LEVEL l)
128
{
129
  RR2_level_des *lev = (RR2_level_des *)(level_table[l]);
130
  PID p = qq_queryfirst(&lev->ready);
131
 
132
  kern_printf("Slice: %d \n", lev->slice);
133
 
134
  while (p != NIL) {
135
    kern_printf("Pid: %d\t Name: %20s Status: %s\n",p,proc_table[p].name,
136
              RR2_status_to_a(proc_table[p].status));
137
    p = proc_table[p].next;
138
  }
139
 
140
  for (p=0; p<MAX_PROC; p++)
141
    if (proc_table[p].task_level == l && proc_table[p].status != RR2_READY
142
        && proc_table[p].status != FREE )
143
      kern_printf("Pid: %d\t Name: %20s Status: %s\n",p,proc_table[p].name,
144
                RR2_status_to_a(proc_table[p].status));
145
 
146
}
147
 
148
 
149
/* This is not efficient but very fair :-)
150
   The need of all this stuff is because if a task execute a long time
151
   due to (shadow!) priority inheritance, then the task shall go to the
152
   tail of the queue many times... */
153
static PID RR2_level_scheduler(LEVEL l)
154
{
155
  RR2_level_des *lev = (RR2_level_des *)(level_table[l]);
156
 
157
  PID p;
158
 
159
  for (;;) {
160
    p = qq_queryfirst(&lev->ready);
161
    if (p == -1)
162
      return p;
163
 
164
    if (proc_table[p].avail_time <= 0) {
165
      proc_table[p].avail_time += proc_table[p].wcet;
166
      qq_extract(p,&lev->ready);
167
      qq_insertlast(p,&lev->ready);
168
    }
169
    else
170
      return p;
171
  }
172
}
173
 
174
static int RR2_level_guarantee(LEVEL l, bandwidth_t *freebandwidth)
175
{
176
  /* the RR2 level always guarantee... the function is defined because
177
     there can be an aperiodic server at a level with less priority than
178
     the RR2 that need guarantee (e.g., a TBS server) */
179
  return 1;
180
}
181
 
182
 
183
static int RR2_task_create(LEVEL l, PID p, TASK_MODEL *m)
184
{
185
  RR2_level_des *lev = (RR2_level_des *)(level_table[l]);
186
  NRT_TASK_MODEL *nrt = (NRT_TASK_MODEL *)m;
187
 
188
  /* the task state is set at SLEEP by the general task_create
189
     the only thing to set remains the capacity stuffs that are set
190
     to the values passed in the model... */
191
 
192
  /* I used the wcet field because using wcet can account if a task
193
     consume more than the timeslice... */
194
 
195
  if (nrt->slice) {
196
    proc_table[p].avail_time = nrt->slice;
197
    proc_table[p].wcet       = nrt->slice;
198
  }
199
  else {
200
    proc_table[p].avail_time = lev->slice;
201
    proc_table[p].wcet       = lev->slice;
202
  }
203
  proc_table[p].control   |= CONTROL_CAP;
204
 
205
  if (nrt->arrivals == SAVE_ARRIVALS)
206
    lev->nact[p] = 0;
207
  else
208
    lev->nact[p] = -1;
209
 
210
  return 0; /* OK */
211
}
212
 
213
static void RR2_task_detach(LEVEL l, PID p)
214
{
215
  /* the RR2 level doesn't introduce any new field in the TASK_MODEL
216
     so, all detach stuffs are done by the task_create
217
     The task state is set at FREE by the general task_create */
218
}
219
 
220
static int RR2_task_eligible(LEVEL l, PID p)
221
{
222
  return 0; /* if the task p is chosen, it is always eligible */
223
}
224
 
225
#ifdef __TEST1__
226
extern int testactive;
227
extern struct timespec s_stime[];
228
extern TIME s_curr[];
229
extern TIME s_PID[];
230
extern int useds;
231
#endif
232
 
233
static void RR2_task_dispatch(LEVEL l, PID p, int nostop)
234
{
235
  RR2_level_des *lev = (RR2_level_des *)(level_table[l]);
236
 
237
  /* the task state is set EXE by the scheduler()
238
     we extract the task from the ready queue
239
     NB: we can't assume that p is the first task in the queue!!! */
240
  qq_extract(p, &lev->ready);
241
 
242
 
243
  #ifdef __TEST1__
244
  if (testactive)
245
  {
246
    TIMESPEC_ASSIGN(&s_stime[useds],&schedule_time);
247
    s_curr[useds] = proc_table[p].avail_time;
248
    s_PID[useds]  = p;
249
    useds++;
250
  }
251
  #endif
252
}
253
 
254
static void RR2_task_epilogue(LEVEL l, PID p)
255
{
256
  RR2_level_des *lev = (RR2_level_des *)(level_table[l]);
257
 
258
  /* check if the slice is finished and insert the task in the coRR2ect
259
     qqueue position */
260
  if (proc_table[p].avail_time <= 0) {
261
    proc_table[p].avail_time += proc_table[p].wcet;
262
    qq_insertlast(p,&lev->ready);
263
  }
264
  else
265
    /* cuRR2 is >0, so the running task have to run for another cuRR2 usec */
266
    qq_insertfirst(p,&lev->ready);
267
 
268
  proc_table[p].status = RR2_READY;
269
}
270
 
271
static void RR2_task_activate(LEVEL l, PID p)
272
{
273
  RR2_level_des *lev = (RR2_level_des *)(level_table[l]);
274
 
275
  /* Test if we are trying to activate a non sleeping task    */
276
  /* save activation (only if needed... */
277
  if (proc_table[p].status != SLEEP) {
278
    if (lev->nact[p] != -1)
279
      lev->nact[p]++;
280
    return;
281
  }
282
 
283
  ll_gettime(TIME_EXACT, &proc_table[p].request_time);
284
 
285
  /* Insert task in the coRR2ect position */
286
  proc_table[p].status = RR2_READY;
287
  qq_insertlast(p,&lev->ready);
288
}
289
 
290
static void RR2_task_insert(LEVEL l, PID p)
291
{
292
  RR2_level_des *lev = (RR2_level_des *)(level_table[l]);
293
 
294
  /* Similar to RR2_task_activate, but we don't check in what state
295
     the task is and we don't set the request_time */
296
 
297
  /* Insert task in the coRR2ect position */
298
  proc_table[p].status = RR2_READY;
299
  qq_insertlast(p,&lev->ready);
300
}
301
 
302
static void RR2_task_extract(LEVEL l, PID p)
303
{
304
  /* Extract the running task from the level
305
     . we have already extract it from the ready queue at the dispatch time.
306
     . the capacity event have to be removed by the generic kernel
307
     . the wcet don't need modification...
308
     . the state of the task is set by the calling function
309
 
310
     So, we do nothing!!!
311
  */
312
}
313
 
314
static void RR2_task_endcycle(LEVEL l, PID p)
315
{
316
  RR2_level_des *lev = (RR2_level_des *)(level_table[l]);
317
 
318
  if (lev->nact[p] > 0) {
319
    /* continue!!!! */
320
    ll_gettime(TIME_EXACT, &proc_table[p].request_time);
321
    lev->nact[p]--;
322
    qq_insertfirst(p,&lev->ready);
323
    proc_table[p].status = RR2_READY;
324
  }
325
  else
326
    proc_table[p].status = SLEEP;
327
}
328
 
329
static void RR2_task_end(LEVEL l, PID p)
330
{
331
  RR2_level_des *lev = (RR2_level_des *)(level_table[l]);
332
 
333
  lev->nact[p] = -1;
334
 
335
  /* then, we insert the task in the free queue */
336
  proc_table[p].status = FREE;
337
  q_insert(p,&freedesc);
338
}
339
 
340
static void RR2_task_sleep(LEVEL l, PID p)
341
{
342
  RR2_level_des *lev = (RR2_level_des *)(level_table[l]);
343
  if (lev->nact[p] >= 0) lev->nact[p] = 0;
344
  proc_table[p].status = SLEEP;
345
}
346
 
347
static void RR2_task_delay(LEVEL l, PID p, TIME usdelay)
348
{
349
//  RR2_level_des *lev = (RR2_level_des *)(level_table[l]);
350
  struct timespec wakeuptime;
351
 
352
  /* equal to RR2_task_endcycle */
353
  proc_table[p].status = RR2_DELAY;
354
 
355
  /* we need to delete this event if we kill the task while it is sleeping */
356
  ll_gettime(TIME_EXACT,&wakeuptime);
357
  ADDUSEC2TIMESPEC(usdelay,&wakeuptime);
358
  proc_table[p].delay_timer = kern_event_post(&wakeuptime,
359
                                              RR2_timer_delay,
360
                                              (void *)p);
361
}
362
 
363
 
364
static int RR2_guest_create(LEVEL l, PID p, TASK_MODEL *m)
365
{ kern_raise(XUNVALID_GUEST,exec_shadow); return 0; }
366
 
367
static void RR2_guest_detach(LEVEL l, PID p)
368
{ kern_raise(XUNVALID_GUEST,exec_shadow); }
369
 
370
static void RR2_guest_dispatch(LEVEL l, PID p, int nostop)
371
{ kern_raise(XUNVALID_GUEST,exec_shadow); }
372
 
373
static void RR2_guest_epilogue(LEVEL l, PID p)
374
{ kern_raise(XUNVALID_GUEST,exec_shadow); }
375
 
376
static void RR2_guest_activate(LEVEL l, PID p)
377
{ kern_raise(XUNVALID_GUEST,exec_shadow); }
378
 
379
static void RR2_guest_insert(LEVEL l, PID p)
380
{ kern_raise(XUNVALID_GUEST,exec_shadow); }
381
 
382
static void RR2_guest_extract(LEVEL l, PID p)
383
{ kern_raise(XUNVALID_GUEST,exec_shadow); }
384
 
385
static void RR2_guest_endcycle(LEVEL l, PID p)
386
{ kern_raise(XUNVALID_GUEST,exec_shadow); }
387
 
388
static void RR2_guest_end(LEVEL l, PID p)
389
{ kern_raise(XUNVALID_GUEST,exec_shadow); }
390
 
391
static void RR2_guest_sleep(LEVEL l, PID p)
392
{ kern_raise(XUNVALID_GUEST,exec_shadow); }
393
 
394
static void RR2_guest_delay(LEVEL l, PID p,DWORD tickdelay)
395
{ kern_raise(XUNVALID_GUEST,exec_shadow); }
396
 
397
 
398
 
399
 
400
/* Registration functions */
401
 
402
/*+ This init function install the "main" task +*/
403
static void RR2_call_main(void *l)
404
{
405
  LEVEL lev;
406
  PID p;
407
  NRT_TASK_MODEL m;
408
  void *mb;
409
 
410
  lev = (LEVEL)l;
411
 
412
  nrt_task_default_model(m);
413
  nrt_task_def_level(m,lev); /* with this we are sure that the task aRR2ives
414
                                to the coRR2ect level */
415
 
416
  mb = ((RR2_level_des *)level_table[lev])->multiboot;
417
  nrt_task_def_arg(m,mb);
418
  nrt_task_def_usemath(m);
419
  nrt_task_def_nokill(m);
420
  nrt_task_def_ctrl_jet(m);
421
 
422
  p = task_create("Main", __init__, (TASK_MODEL *)&m, NULL);
423
 
424
  if (p == NIL)
425
    printk("\nPanic!!! can't create main task...\n");
426
 
427
  RR2_task_activate(lev,p);
428
}
429
 
430
 
431
/*+ Registration function:
432
    TIME slice                the slice for the Round Robin queue
433
    int createmain            1 if the level creates the main task 0 otherwise
434
    struct multiboot_info *mb used if createmain specified   +*/
435
void RR2_register_level(TIME slice,
436
                       int createmain,
437
                       struct multiboot_info *mb)
438
{
439
  LEVEL l;            /* the level that we register */
440
  RR2_level_des *lev;  /* for readableness only */
441
  PID i;
442
 
443
  printk("RR2_register_level\n");
444
 
445
  /* request an entry in the level_table */
446
  l = level_alloc_descriptor();
447
 
448
  /* alloc the space needed for the RR2_level_des */
449
  lev = (RR2_level_des *)kern_alloc(sizeof(RR2_level_des));
450
 
451
  printk("    lev=%d\n",(int)lev);
452
 
453
  /* update the level_table with the new entry */
454
  level_table[l] = (level_des *)lev;
455
 
456
  /* fill the standard descriptor */
457
  strncpy(lev->l.level_name,  RR2_LEVELNAME, MAX_LEVELNAME);
458
  lev->l.level_code               = RR2_LEVEL_CODE;
459
  lev->l.level_version            = RR2_LEVEL_VERSION;
460
 
461
  lev->l.level_accept_task_model  = RR2_level_accept_task_model;
462
  lev->l.level_accept_guest_model = RR2_level_accept_guest_model;
463
  lev->l.level_status             = RR2_level_status;
464
  lev->l.level_scheduler          = RR2_level_scheduler;
465
  lev->l.level_guarantee          = RR2_level_guarantee;
466
 
467
  lev->l.task_create              = RR2_task_create;
468
  lev->l.task_detach              = RR2_task_detach;
469
  lev->l.task_eligible            = RR2_task_eligible;
470
  lev->l.task_dispatch            = RR2_task_dispatch;
471
  lev->l.task_epilogue            = RR2_task_epilogue;
472
  lev->l.task_activate            = RR2_task_activate;
473
  lev->l.task_insert              = RR2_task_insert;
474
  lev->l.task_extract             = RR2_task_extract;
475
  lev->l.task_endcycle            = RR2_task_endcycle;
476
  lev->l.task_end                 = RR2_task_end;
477
  lev->l.task_sleep               = RR2_task_sleep;
478
  lev->l.task_delay               = RR2_task_delay;
479
 
480
  lev->l.guest_create             = RR2_guest_create;
481
  lev->l.guest_detach             = RR2_guest_detach;
482
  lev->l.guest_dispatch           = RR2_guest_dispatch;
483
  lev->l.guest_epilogue           = RR2_guest_epilogue;
484
  lev->l.guest_activate           = RR2_guest_activate;
485
  lev->l.guest_insert             = RR2_guest_insert;
486
  lev->l.guest_extract            = RR2_guest_extract;
487
  lev->l.guest_endcycle           = RR2_guest_endcycle;
488
  lev->l.guest_end                = RR2_guest_end;
489
  lev->l.guest_sleep              = RR2_guest_sleep;
490
  lev->l.guest_delay              = RR2_guest_delay;
491
 
492
  /* fill the RR2 descriptor part */
493
  for (i = 0; i < MAX_PROC; i++)
494
    lev->nact[i] = -1;
495
 
496
  qq_init(&lev->ready);
497
 
498
  if (slice < RR2_MINIMUM_SLICE) slice = RR2_MINIMUM_SLICE;
499
  if (slice > RR2_MAXIMUM_SLICE) slice = RR2_MAXIMUM_SLICE;
500
  lev->slice      = slice;
501
 
502
  lev->multiboot  = mb;
503
 
504
  if (createmain)
505
    sys_atrunlevel(RR2_call_main,(void *) l, RUNLEVEL_INIT);
506
}
507
 
508