Subversion Repositories shark

Rev

Rev 14 | Rev 38 | 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
 ------------
29 pj 23
 CVS :        $Id: posix.c,v 1.3 2002-11-11 08:32:06 pj Exp $
2 pj 24
 
25
 File:        $File$
29 pj 26
 Revision:    $Revision: 1.3 $
27
 Last update: $Date: 2002-11-11 08:32:06 $
2 pj 28
 ------------
29
 
30
 This file contains the scheduling module compatible with POSIX
31
 specifications
32
 
33
 Read posix.h for further details.
34
 
35
 RR tasks have the CONTROL_CAP bit set
36
 
37
**/
38
 
39
/*
40
 * Copyright (C) 2000 Paolo Gai
41
 *
42
 * This program is free software; you can redistribute it and/or modify
43
 * it under the terms of the GNU General Public License as published by
44
 * the Free Software Foundation; either version 2 of the License, or
45
 * (at your option) any later version.
46
 *
47
 * This program is distributed in the hope that it will be useful,
48
 * but WITHOUT ANY WARR2ANTY; without even the implied waRR2anty of
49
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
50
 * GNU General Public License for more details.
51
 *
52
 * You should have received a copy of the GNU General Public License
53
 * along with this program; if not, write to the Free Software
54
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
55
 *
56
 */
57
 
58
 
59
#include <modules/posix.h>
60
#include <ll/stdio.h>
61
#include <ll/string.h>
62
#include <kernel/model.h>
63
#include <kernel/descr.h>
64
#include <kernel/var.h>
65
#include <kernel/func.h>
66
 
67
/*+ Status used in the level +*/
68
#define POSIX_READY   MODULE_STATUS_BASE
69
 
70
/*+ the level redefinition for the Round Robin level +*/
71
typedef struct {
72
  level_des l;          /*+ the standard level descriptor          +*/
73
 
74
  int nact[MAX_PROC];   /*+ number of pending activations          +*/
29 pj 75
 
76
  int priority[MAX_PROC]; /*+ priority of each task                +*/
2 pj 77
 
29 pj 78
  IQUEUE *ready;        /*+ the ready queue array                  +*/
2 pj 79
 
80
  int slice;            /*+ the level's time slice                 +*/
81
 
82
  struct multiboot_info *multiboot; /*+ used if the level have to insert
83
                                        the main task +*/
84
  int maxpriority;      /*+ the priority are from 0 to maxpriority
85
                            (i.e 0 to 31)                          +*/
86
 
87
  int yielding;         /*+ equal to 1 when a sched_yield is called +*/
88
 
89
} POSIX_level_des;
90
 
91
static char *POSIX_status_to_a(WORD status)
92
{
93
  if (status < MODULE_STATUS_BASE)
94
    return status_to_a(status);
95
 
96
  switch (status) {
97
    case POSIX_READY: return "POSIX_Ready";
98
    default         : return "POSIX_Unknown";
99
  }
100
}
101
 
102
static int POSIX_level_accept_task_model(LEVEL l, TASK_MODEL *m)
103
{
104
  if (m->pclass == NRT_PCLASS || m->pclass == (NRT_PCLASS | l))
105
    return 0;
106
  else
107
    return -1;
108
}
109
 
110
static int POSIX_level_accept_guest_model(LEVEL l, TASK_MODEL *m)
111
{
112
    return -1;
113
}
114
 
115
static void POSIX_level_status(LEVEL l)
116
{
117
  POSIX_level_des *lev = (POSIX_level_des *)(level_table[l]);
118
  PID p;
119
 
120
  kern_printf("Slice: %d \n", lev->slice);
121
 
122
  for (p=0; p<MAX_PROC; p++)
123
    if (proc_table[p].task_level == l && proc_table[p].status != POSIX_READY
124
        && proc_table[p].status != FREE )
29 pj 125
      kern_printf("Pid: %d\t Name: %20s Prio: %3d Status: %s\n",
2 pj 126
                  p,proc_table[p].name,
29 pj 127
                  lev->priority[p],
2 pj 128
                  POSIX_status_to_a(proc_table[p].status));
129
 
130
}
131
 
132
 
133
/* This is not efficient but very fair :-)
134
   The need of all this stuff is because if a task execute a long time
135
   due to (shadow!) priority inheritance, then the task shall go to the
136
   tail of the queue many times... */
137
static PID POSIX_level_scheduler(LEVEL l)
138
{
139
  POSIX_level_des *lev = (POSIX_level_des *)(level_table[l]);
140
 
141
  PID p;
142
 
143
  int prio;
144
 
145
  prio = lev->maxpriority;
146
 
147
  for (;;) {
29 pj 148
    p = iq_query_first(&lev->ready[prio]);
2 pj 149
    if (p == NIL) {
150
      if (prio) {
151
        prio--;
152
        continue;
153
      }
154
      else
155
        return NIL;
156
    }
157
 
158
    if ((proc_table[p].control & CONTROL_CAP) &&
159
        (proc_table[p].avail_time <= 0)) {
160
      proc_table[p].avail_time += proc_table[p].wcet;
29 pj 161
      iq_extract(p,&lev->ready[prio]);
162
      iq_insertlast(p,&lev->ready[prio]);
2 pj 163
    }
164
    else
165
      return p;
166
  }
167
}
168
 
169
static int POSIX_level_guarantee(LEVEL l, bandwidth_t *freebandwidth)
170
{
171
  /* the POSIX level always guarantee... the function is defined because
172
     there can be an aperiodic server at a level with less priority than
173
     the POSIX that need guarantee (e.g., a TBS server) */
174
  return 1;
175
}
176
 
177
 
178
static int POSIX_task_create(LEVEL l, PID p, TASK_MODEL *m)
179
{
180
  POSIX_level_des *lev = (POSIX_level_des *)(level_table[l]);
181
  NRT_TASK_MODEL *nrt = (NRT_TASK_MODEL *)m;
182
 
183
  /* the task state is set at SLEEP by the general task_create */
184
 
185
  /* I used the wcet field because using wcet can account if a task
186
     consume more than the timeslice... */
187
 
188
  if (nrt->inherit == NRT_INHERIT_SCHED &&
189
      proc_table[exec_shadow].task_level == l) {
190
    /* We inherit the scheduling properties if the scheduling level
191
       *is* the same */
29 pj 192
    lev->priority[p] = lev->priority[exec_shadow];
2 pj 193
 
194
    proc_table[p].avail_time = proc_table[exec_shadow].avail_time;
195
    proc_table[p].wcet       = proc_table[exec_shadow].wcet;
196
 
197
    proc_table[p].control = (proc_table[p].control & ~CONTROL_CAP) |
198
                            (proc_table[exec_shadow].control & CONTROL_CAP);
199
 
200
    lev->nact[p] = (lev->nact[exec_shadow] == -1) ? -1 : 0;
201
  }
202
  else {
29 pj 203
    lev->priority[p] = nrt->weight;
2 pj 204
 
205
    if (nrt->slice) {
206
      proc_table[p].avail_time = nrt->slice;
207
      proc_table[p].wcet       = nrt->slice;
208
    }
209
    else {
210
      proc_table[p].avail_time = lev->slice;
211
      proc_table[p].wcet       = lev->slice;
212
    }
213
 
214
    if (nrt->policy == NRT_RR_POLICY)
215
      proc_table[p].control   |= CONTROL_CAP;
216
 
217
    if (nrt->arrivals == SAVE_ARRIVALS)
218
      lev->nact[p] = 0;
219
    else
220
      lev->nact[p] = -1;
221
  }
222
 
223
  return 0; /* OK */
224
}
225
 
226
static void POSIX_task_detach(LEVEL l, PID p)
227
{
228
  /* the POSIX level doesn't introduce any new field in the TASK_MODEL
229
     so, all detach stuffs are done by the task_create
230
     The task state is set at FREE by the general task_create */
231
}
232
 
233
static int POSIX_task_eligible(LEVEL l, PID p)
234
{
235
  return 0; /* if the task p is chosen, it is always eligible */
236
}
237
 
238
static void POSIX_task_dispatch(LEVEL l, PID p, int nostop)
239
{
240
  POSIX_level_des *lev = (POSIX_level_des *)(level_table[l]);
241
 
242
  /* the task state is set EXE by the scheduler()
243
     we extract the task from the ready queue
244
     NB: we can't assume that p is the first task in the queue!!! */
29 pj 245
  iq_extract(p, &lev->ready[lev->priority[p]]);
2 pj 246
}
247
 
248
static void POSIX_task_epilogue(LEVEL l, PID p)
249
{
250
  POSIX_level_des *lev = (POSIX_level_des *)(level_table[l]);
251
 
252
  if (lev->yielding) {
253
    lev->yielding = 0;
29 pj 254
    iq_insertlast(p,&lev->ready[lev->priority[p]]);
2 pj 255
  }
256
  /* check if the slice is finished and insert the task in the coPOSIXect
257
     qqueue position */
258
  else if (proc_table[p].control & CONTROL_CAP &&
259
           proc_table[p].avail_time <= 0) {
260
    proc_table[p].avail_time += proc_table[p].wcet;
29 pj 261
    iq_insertlast(p,&lev->ready[lev->priority[p]]);
2 pj 262
  }
263
  else
29 pj 264
    iq_insertfirst(p,&lev->ready[lev->priority[p]]);
2 pj 265
 
266
  proc_table[p].status = POSIX_READY;
267
}
268
 
269
static void POSIX_task_activate(LEVEL l, PID p)
270
{
271
  POSIX_level_des *lev = (POSIX_level_des *)(level_table[l]);
272
 
273
  /* Test if we are trying to activate a non sleeping task    */
274
  /* save activation (only if needed...) */
275
  if (proc_table[p].status != SLEEP) {
276
    if (lev->nact[p] != -1)
277
      lev->nact[p]++;
278
    return;
279
  }
280
 
281
  ll_gettime(TIME_EXACT, &proc_table[p].request_time);
282
 
283
  /* Insert task in the correct position */
284
  proc_table[p].status = POSIX_READY;
29 pj 285
  iq_insertlast(p,&lev->ready[lev->priority[p]]);
2 pj 286
}
287
 
288
static void POSIX_task_insert(LEVEL l, PID p)
289
{
290
  POSIX_level_des *lev = (POSIX_level_des *)(level_table[l]);
291
 
292
  /* Similar to POSIX_task_activate, but we don't check in what state
293
     the task is and we don't set the request_time */
294
 
295
  /* Insert task in the coPOSIXect position */
296
  proc_table[p].status = POSIX_READY;
29 pj 297
  iq_insertlast(p,&lev->ready[lev->priority[p]]);
2 pj 298
}
299
 
300
static void POSIX_task_extract(LEVEL l, PID p)
301
{
302
  /* Extract the running task from the level
303
     . we have already extract it from the ready queue at the dispatch time.
304
     . the capacity event have to be removed by the generic kernel
305
     . the wcet don't need modification...
306
     . the state of the task is set by the calling function
307
 
308
     So, we do nothing!!!
309
  */
310
}
311
 
312
static void POSIX_task_endcycle(LEVEL l, PID p)
313
{
314
  POSIX_level_des *lev = (POSIX_level_des *)(level_table[l]);
315
 
316
  if (lev->nact[p] > 0) {
317
    /* continue!!!! */
318
    ll_gettime(TIME_EXACT, &proc_table[p].request_time);
319
    lev->nact[p]--;
29 pj 320
    iq_insertfirst(p,&lev->ready[lev->priority[p]]);
2 pj 321
    proc_table[p].status = POSIX_READY;
322
  }
323
  else
324
    proc_table[p].status = SLEEP;
325
}
326
 
327
static void POSIX_task_end(LEVEL l, PID p)
328
{
329
  POSIX_level_des *lev = (POSIX_level_des *)(level_table[l]);
330
 
331
  lev->nact[p] = -1;
332
 
333
  /* then, we insert the task in the free queue */
334
  proc_table[p].status = FREE;
29 pj 335
  iq_priority_insert(p,&freedesc);
2 pj 336
}
337
 
338
static void POSIX_task_sleep(LEVEL l, PID p)
339
{
340
  POSIX_level_des *lev = (POSIX_level_des *)(level_table[l]);
341
  lev->nact[p] = 0;
342
  proc_table[p].status = SLEEP;
343
}
344
 
345
 
346
 
347
static int POSIX_guest_create(LEVEL l, PID p, TASK_MODEL *m)
14 pj 348
{ kern_raise(XINVALID_GUEST,exec_shadow); return 0; }
2 pj 349
 
350
static void POSIX_guest_detach(LEVEL l, PID p)
14 pj 351
{ kern_raise(XINVALID_GUEST,exec_shadow); }
2 pj 352
 
353
static void POSIX_guest_dispatch(LEVEL l, PID p, int nostop)
14 pj 354
{ kern_raise(XINVALID_GUEST,exec_shadow); }
2 pj 355
 
356
static void POSIX_guest_epilogue(LEVEL l, PID p)
14 pj 357
{ kern_raise(XINVALID_GUEST,exec_shadow); }
2 pj 358
 
359
static void POSIX_guest_activate(LEVEL l, PID p)
14 pj 360
{ kern_raise(XINVALID_GUEST,exec_shadow); }
2 pj 361
 
362
static void POSIX_guest_insert(LEVEL l, PID p)
14 pj 363
{ kern_raise(XINVALID_GUEST,exec_shadow); }
2 pj 364
 
365
static void POSIX_guest_extract(LEVEL l, PID p)
14 pj 366
{ kern_raise(XINVALID_GUEST,exec_shadow); }
2 pj 367
 
368
static void POSIX_guest_endcycle(LEVEL l, PID p)
14 pj 369
{ kern_raise(XINVALID_GUEST,exec_shadow); }
2 pj 370
 
371
static void POSIX_guest_end(LEVEL l, PID p)
14 pj 372
{ kern_raise(XINVALID_GUEST,exec_shadow); }
2 pj 373
 
374
static void POSIX_guest_sleep(LEVEL l, PID p)
14 pj 375
{ kern_raise(XINVALID_GUEST,exec_shadow); }
2 pj 376
 
377
 
378
/* Registration functions */
379
 
380
/*+ This init function install the "main" task +*/
381
static void POSIX_call_main(void *l)
382
{
383
  LEVEL lev;
384
  PID p;
385
  NRT_TASK_MODEL m;
386
  void *mb;
387
 
388
  lev = (LEVEL)l;
389
 
390
  nrt_task_default_model(m);
391
  nrt_task_def_level(m,lev); /* with this we are sure that the task aPOSIXives
392
                                to the coPOSIXect level */
393
 
394
  mb = ((POSIX_level_des *)level_table[lev])->multiboot;
395
  nrt_task_def_arg(m,mb);
396
  nrt_task_def_usemath(m);
397
  nrt_task_def_nokill(m);
398
  nrt_task_def_ctrl_jet(m);
399
  nrt_task_def_weight(m,0);
400
  nrt_task_def_policy(m,NRT_RR_POLICY);
401
  nrt_task_def_inherit(m,NRT_EXPLICIT_SCHED);
402
 
403
  p = task_create("Main", __init__, (TASK_MODEL *)&m, NULL);
404
 
405
  if (p == NIL)
406
    printk("\nPanic!!! can't create main task...\n");
407
 
408
  POSIX_task_activate(lev,p);
409
}
410
 
411
 
412
/*+ Registration function:
413
    TIME slice                the slice for the Round Robin queue
414
    int createmain            1 if the level creates the main task 0 otherwise
415
    struct multiboot_info *mb used if createmain specified   +*/
416
void POSIX_register_level(TIME slice,
417
                       int createmain,
418
                       struct multiboot_info *mb,
419
                       int prioritylevels)
420
{
421
  LEVEL l;            /* the level that we register */
422
  POSIX_level_des *lev;  /* for readableness only */
423
  PID i;              /* a counter */
424
  int x;              /* a counter */
425
 
426
  printk("POSIX_register_level\n");
427
 
428
  /* request an entry in the level_table */
429
  l = level_alloc_descriptor();
430
 
431
  printk("    alloco descrittore %d %d\n",l,(int)sizeof(POSIX_level_des));
432
 
433
  /* alloc the space needed for the POSIX_level_des */
434
  lev = (POSIX_level_des *)kern_alloc(sizeof(POSIX_level_des));
435
 
436
  printk("    lev=%d\n",(int)lev);
437
 
438
  /* update the level_table with the new entry */
439
  level_table[l] = (level_des *)lev;
440
 
441
  /* fill the standard descriptor */
442
  strncpy(lev->l.level_name,  POSIX_LEVELNAME, MAX_LEVELNAME);
443
  lev->l.level_code               = POSIX_LEVEL_CODE;
444
  lev->l.level_version            = POSIX_LEVEL_VERSION;
445
 
446
  lev->l.level_accept_task_model  = POSIX_level_accept_task_model;
447
  lev->l.level_accept_guest_model = POSIX_level_accept_guest_model;
448
  lev->l.level_status             = POSIX_level_status;
449
  lev->l.level_scheduler          = POSIX_level_scheduler;
450
  lev->l.level_guarantee          = POSIX_level_guarantee;
451
 
452
  lev->l.task_create              = POSIX_task_create;
453
  lev->l.task_detach              = POSIX_task_detach;
454
  lev->l.task_eligible            = POSIX_task_eligible;
455
  lev->l.task_dispatch            = POSIX_task_dispatch;
456
  lev->l.task_epilogue            = POSIX_task_epilogue;
457
  lev->l.task_activate            = POSIX_task_activate;
458
  lev->l.task_insert              = POSIX_task_insert;
459
  lev->l.task_extract             = POSIX_task_extract;
460
  lev->l.task_endcycle            = POSIX_task_endcycle;
461
  lev->l.task_end                 = POSIX_task_end;
462
  lev->l.task_sleep               = POSIX_task_sleep;
463
 
464
  lev->l.guest_create             = POSIX_guest_create;
465
  lev->l.guest_detach             = POSIX_guest_detach;
466
  lev->l.guest_dispatch           = POSIX_guest_dispatch;
467
  lev->l.guest_epilogue           = POSIX_guest_epilogue;
468
  lev->l.guest_activate           = POSIX_guest_activate;
469
  lev->l.guest_insert             = POSIX_guest_insert;
470
  lev->l.guest_extract            = POSIX_guest_extract;
471
  lev->l.guest_endcycle           = POSIX_guest_endcycle;
472
  lev->l.guest_end                = POSIX_guest_end;
473
  lev->l.guest_sleep              = POSIX_guest_sleep;
474
 
475
  /* fill the POSIX descriptor part */
476
  for (i = 0; i < MAX_PROC; i++)
477
    lev->nact[i] = -1;
478
 
479
  lev->maxpriority = prioritylevels -1;
480
 
29 pj 481
  lev->ready = (IQUEUE *)kern_alloc(sizeof(IQUEUE) * prioritylevels);
2 pj 482
 
483
  for (x = 0; x < prioritylevels; x++)
29 pj 484
    iq_init(&lev->ready[x], &freedesc, 0);
2 pj 485
 
486
  if (slice < POSIX_MINIMUM_SLICE) slice = POSIX_MINIMUM_SLICE;
487
  if (slice > POSIX_MAXIMUM_SLICE) slice = POSIX_MAXIMUM_SLICE;
488
  lev->slice      = slice;
489
 
490
  lev->multiboot  = mb;
491
 
492
  if (createmain)
493
    sys_atrunlevel(POSIX_call_main,(void *) l, RUNLEVEL_INIT);
494
}
495
 
496
/*+ this function forces the running task to go to his queue tail;
497
    (it works only on the POSIX level) +*/
498
int POSIX_sched_yield(LEVEL l)
499
{
500
  POSIX_level_des *lev = (POSIX_level_des *)(level_table[l]);
501
 
502
  if (l < 0 || l >= sched_levels)
503
    return -1;
504
 
505
  if (level_table[l]->level_code    != POSIX_LEVEL_CODE    ||
506
      level_table[l]->level_version != POSIX_LEVEL_VERSION )
507
    return -1;
508
 
509
  if (proc_table[exec_shadow].task_level != l)
510
    return -1;
511
 
512
  proc_table[exec_shadow].context = kern_context_save();
513
  lev->yielding = 1;
514
  scheduler();
515
  kern_context_load(proc_table[exec_shadow].context);
516
  return 0;
517
}
518
 
519
/*+ this function returns the maximum level allowed for the POSIX level +*/
520
int POSIX_get_priority_max(LEVEL l)
521
{
522
  POSIX_level_des *lev = (POSIX_level_des *)(level_table[l]);
523
  return lev->maxpriority;
524
}
525
 
526
/*+ this function returns the default timeslice for the POSIX level +*/
527
int POSIX_rr_get_interval(LEVEL l)
528
{
529
  POSIX_level_des *lev = (POSIX_level_des *)(level_table[l]);
530
  return lev->slice;
531
}
532
 
533
/*+ this functions returns some paramaters of a task;
534
    policy must be NRT_RR_POLICY or NRT_FIFO_POLICY;
535
    priority must be in the range [0..prioritylevels]
536
    returns ENOSYS or ESRCH if there are problems +*/
537
int POSIX_getschedparam(LEVEL l, PID p, int *policy, int *priority)
538
{
539
  if (l < 0 || l >= sched_levels)
540
    return ENOSYS;
541
 
542
  if (level_table[l]->level_code    != POSIX_LEVEL_CODE    ||
543
      level_table[l]->level_version != POSIX_LEVEL_VERSION )
544
    return ENOSYS;
545
 
546
  if (p<0 || p>= MAX_PROC || proc_table[p].status == FREE)
547
    return ESRCH;
548
 
549
  if (proc_table[p].task_level != l)
550
    return ENOSYS;
551
 
552
  if (proc_table[p].control & CONTROL_CAP)
553
    *policy = NRT_RR_POLICY;
554
  else
555
    *policy = NRT_FIFO_POLICY;
556
 
29 pj 557
  *priority = ((POSIX_level_des *)(level_table[l]))->priority[p];
2 pj 558
 
559
  return 0;
560
}
561
 
562
/*+ this functions sets paramaters of a task +*/
563
int POSIX_setschedparam(LEVEL l, PID p, int policy, int priority)
564
{
565
  POSIX_level_des *lev = (POSIX_level_des *)(level_table[l]);
566
 
567
  if (l < 0 || l >= sched_levels)
568
    return ENOSYS;
569
 
570
  if (level_table[l]->level_code    != POSIX_LEVEL_CODE    ||
571
      level_table[l]->level_version != POSIX_LEVEL_VERSION )
572
    return ENOSYS;
573
 
574
  if (p<0 || p>= MAX_PROC || proc_table[p].status == FREE)
575
    return ESRCH;
576
 
577
  if (proc_table[p].task_level != l)
578
    return ENOSYS;
579
 
580
  if (policy == SCHED_RR)
581
    proc_table[p].control |= CONTROL_CAP;
582
  else if (policy == SCHED_FIFO)
583
    proc_table[p].control &= ~CONTROL_CAP;
584
  else
585
    return EINVAL;
586
 
29 pj 587
  if (lev->priority[p] != priority) {
2 pj 588
    if (proc_table[p].status == POSIX_READY) {
29 pj 589
      iq_extract(p,&lev->ready[lev->priority[p]]);
590
      lev->priority[p] = priority;
591
      iq_insertlast(p,&lev->ready[priority]);
2 pj 592
    }
593
    else
29 pj 594
      lev->priority[p] = priority;
2 pj 595
  }
596
 
597
  return 0;
598
}
599
 
600
 
601