Rev 3 |
Blame |
Compare with Previous |
Last modification |
View Log
| RSS feed
/*
* Project: S.Ha.R.K.
*
* Coordinators:
* Giorgio Buttazzo <giorgio@sssup.it>
* Paolo Gai <pj@gandalf.sssup.it>
*
* Authors :
* Paolo Gai <pj@gandalf.sssup.it>
* Massimiliano Giorgi <massy@gandalf.sssup.it>
* Luca Abeni <luca@gandalf.sssup.it>
* (see the web pages for full authors list)
*
* ReTiS Lab (Scuola Superiore S.Anna - Pisa - Italy)
*
* http://www.sssup.it
* http://retis.sssup.it
* http://shark.sssup.it
*/
/**
------------
CVS : $Id: tbs.c,v 1.2 2002-10-28 07:55:55 pj Exp $
File: $File$
Revision: $Revision: 1.2 $
Last update: $Date: 2002-10-28 07:55:55 $
------------
This file contains the aperiodic server TBS (Total Bandwidth Server)
Read tbs.h for further details.
**/
/*
* Copyright (C) 2000 Paolo Gai
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
*/
#include <modules/tbs.h>
#include <ll/stdio.h>
#include <ll/string.h>
#include <kernel/model.h>
#include <kernel/descr.h>
#include <kernel/var.h>
#include <kernel/func.h>
/*+ 4 debug purposes +*/
#undef TBS_TEST
/*+ Status used in the level +*/
#define TBS_WCET_VIOLATED APER_STATUS_BASE+2 /*+ when wcet is finished +*/
#define TBS_WAIT APER_STATUS_BASE /*+ waiting the service +*/
/*+ task flags +*/
#define TBS_SAVE_ARRIVALS 1
/*+ the level redefinition for the Total Bandwidth Server level +*/
typedef struct {
level_des l
; /*+ the standard level descriptor +*/
/* The wcet are stored in the task descriptor's priority
field. */
int nact
[MAX_PROC
]; /*+ used to record activations +*/
BYTE flag
[MAX_PROC
];
struct timespec lastdline
; /*+ the last deadline assigned to
a TBS task +*/
QQUEUE wait
; /*+ the wait queue of the TBS +*/
PID activated
; /*+ the task inserted in another queue +*/
int flags
; /*+ the init flags... +*/
bandwidth_t U
; /*+ the used bandwidth by the server +*/
int band_num
;
int band_den
;
LEVEL scheduling_level
;
} TBS_level_des
;
static char *TBS_status_to_a
(WORD status
)
{
if (status
< MODULE_STATUS_BASE
)
return status_to_a
(status
);
switch (status
) {
case TBS_WCET_VIOLATED
: return "TBS_Wcet_Violated";
case TBS_WAIT
: return "TBS_Wait";
default : return "TBS_Unknown";
}
}
#ifdef TESTG
#include "drivers/glib.h"
#endif
/* This static function activates the task pointed by lev->activated) */
static __inline__
void TBS_activation
(TBS_level_des
*lev
)
{
PID p
; /* for readableness */
JOB_TASK_MODEL j
; /* the guest model */
TIME drel
; /* the relative deadline of the task */
LEVEL m
; /* the master level... only for readableness */
#ifdef TESTG
TIME x
;
extern TIME starttime
;
#endif
p
= lev
->activated
;
/* we compute a suitable deadline for the task */
drel
= (proc_table
[p
].
wcet * lev
->band_den
) / lev
->band_num
;
if (TIMESPEC_A_GT_B
(&proc_table
[p
].
request_time, &lev
->lastdline
))
TIMESPEC_ASSIGN
(&lev
->lastdline
, &proc_table
[p
].
request_time );
ADDUSEC2TIMESPEC
(drel
, &lev
->lastdline
);
#ifdef TESTG
if (starttime
) {
x
= ((lev
->lastdline.
tv_sec*1000000+lev
->lastdline.
tv_nsec/1000)/5000 - starttime
) + 20;
if (x
<640)
grx_plot
(x
, 15, 7);
}
#endif
/* and we insert the task in another level */
m
= lev
->scheduling_level
;
job_task_default_model
(j
,lev
->lastdline
);
level_table
[m
]->guest_create
(m
,p
,(TASK_MODEL
*)&j
);
level_table
[m
]->guest_activate
(m
,p
);
#ifdef TBS_TEST
kern_printf
("TBS_activation: lastdline %ds %dns\n",lev
->lastdline.
tv_sec,lev
->lastdline.
tv_nsec);
#endif
}
/* This static function reclaims the unused time of the task p */
static __inline__
void TBS_bandwidth_reclaiming
(TBS_level_des
*lev
, PID p
)
{
TIME reclaimed
;
struct timespec r
, sos
;
// kern_printf("%d ", proc_table[p].avail_time);
reclaimed
= (proc_table
[p
].
avail_time * lev
->band_den
) / lev
->band_num
;
r.
tv_nsec = (reclaimed
% 1000000) * 1000;
r.
tv_sec = reclaimed
/ 1000000;
SUBTIMESPEC
(&lev
->lastdline
, &r
, &sos
);
TIMESPEC_ASSIGN
(&lev
->lastdline
, &sos
);
#ifdef TBS_TEST
kern_printf
("TBS_bandwidth_reclaiming: lastdline %ds %dns, reclaimed %d, avail %d\n",
lev
->lastdline.
tv_sec, lev
->lastdline.
tv_nsec, reclaimed
, proc_table
[p
].
avail_time);
#endif
}
static int TBS_level_accept_task_model
(LEVEL l
, TASK_MODEL
*m
)
{
if (m
->pclass
== SOFT_PCLASS
|| m
->pclass
== (SOFT_PCLASS
| l
) ) {
SOFT_TASK_MODEL
*s
= (SOFT_TASK_MODEL
*)m
;
if (s
->wcet
&& s
->periodicity
== APERIODIC
)
return 0;
}
return -1;
}
static int TBS_level_accept_guest_model
(LEVEL l
, TASK_MODEL
*m
)
{
return -1;
}
static char *onoff
(int i
)
{
if (i
)
return "On ";
else
return "Off";
}
static void TBS_level_status
(LEVEL l
)
{
TBS_level_des
*lev
= (TBS_level_des
*)(level_table
[l
]);
PID p
= qq_queryfirst
(&lev
->wait
);
kern_printf
("Wcet Check : %s\n",
onoff
(lev
->flags
& TBS_ENABLE_WCET_CHECK
));
kern_printf
("On-line guarantee : %s\n",
onoff
(lev
->flags
& TBS_ENABLE_GUARANTEE
));
kern_printf
("Used Bandwidth : %u/%u\n",
lev
->U
, MAX_BANDWIDTH
);
kern_printf
("Last deadline : %lds %ldns\n",lev
->lastdline.
tv_sec,
lev
->lastdline.
tv_nsec);
if (lev
->activated
!= -1)
kern_printf
("Activated: Pid: %2d Name: %10s Dl: %ld.%9ld nact: %d Stat: %s\n",
lev
->activated
,
proc_table
[lev
->activated
].
name,
proc_table
[lev
->activated
].
timespec_priority.
tv_sec,
proc_table
[lev
->activated
].
timespec_priority.
tv_nsec,
lev
->nact
[lev
->activated
],
TBS_status_to_a
(proc_table
[lev
->activated
].
status));
while (p
!= NIL
) {
kern_printf
("Pid: %2d Name: %10s Stat: %s\n",
p
,
proc_table
[p
].
name,
TBS_status_to_a
(proc_table
[p
].
status));
p
= proc_table
[p
].
next;
}
}
static PID TBS_level_scheduler
(LEVEL l
)
{
/* the TBS don't schedule anything...
it's an EDF level or similar that do it! */
return NIL
;
}
/* The on-line guarantee is enabled only if the appropriate flag is set... */
static int TBS_level_guarantee
(LEVEL l
, bandwidth_t
*freebandwidth
)
{
TBS_level_des
*lev
= (TBS_level_des
*)(level_table
[l
]);
if (*freebandwidth
>= lev
->U
) {
*freebandwidth
-= lev
->U
;
return 1;
}
else
return 0;
}
static int TBS_task_create
(LEVEL l
, PID p
, TASK_MODEL
*m
)
{
TBS_level_des
*lev
= (TBS_level_des
*)(level_table
[l
]);
/* if the TBS_task_create is called, then the pclass must be a
valid pclass. */
SOFT_TASK_MODEL
*s
= (SOFT_TASK_MODEL
*)m
;
proc_table
[p
].
wcet = s
->wcet
;
/* Enable wcet check */
if (lev
->flags
& TBS_ENABLE_WCET_CHECK
) {
proc_table
[p
].
avail_time = s
->wcet
;
proc_table
[p
].
control |= CONTROL_CAP
;
}
lev
->nact
[p
] = 0;
if (s
->arrivals
== SAVE_ARRIVALS
)
lev
->flag
[p
] = TBS_SAVE_ARRIVALS
;
return 0; /* OK, also if the task cannot be guaranteed... */
}
static void TBS_task_detach
(LEVEL l
, PID p
)
{
/* the TBS level doesn't introduce any dinamic allocated new field. */
}
static int TBS_task_eligible
(LEVEL l
, PID p
)
{
return 0; /* if the task p is chosen, it is always eligible */
}
#ifdef __TEST1__
extern int testactive
;
extern struct timespec s_stime
[];
extern TIME s_curr
[];
extern TIME s_PID
[];
extern int useds
;
#endif
static void TBS_task_dispatch
(LEVEL l
, PID p
, int nostop
)
{
TBS_level_des
*lev
= (TBS_level_des
*)(level_table
[l
]);
/* there is at least one task ready inserted in an EDF or similar
level */
level_table
[ lev
->scheduling_level
]->
guest_dispatch
(lev
->scheduling_level
,p
,nostop
);
#ifdef __TEST1__
if (testactive
)
{
TIMESPEC_ASSIGN
(&s_stime
[useds
], &schedule_time
);
s_curr
[useds
] = proc_table
[p
].
avail_time;
s_PID
[useds
] = p
;
useds
++;
}
#endif
}
static void TBS_task_epilogue
(LEVEL l
, PID p
)
{
TBS_level_des
*lev
= (TBS_level_des
*)(level_table
[l
]);
/* check if the wcet is finished... */
if ((lev
->flags
& TBS_ENABLE_WCET_CHECK
) && proc_table
[p
].
avail_time <= 0) {
/* if it is, raise a XWCET_VIOLATION exception */
kern_raise
(XWCET_VIOLATION
,p
);
proc_table
[p
].
status = TBS_WCET_VIOLATED
;
/* the current task have to die in the scheduling queue, and another
have to be put in place... this code is identical to the
TBS_task_end */
level_table
[ lev
->scheduling_level
]->
guest_end
(lev
->scheduling_level
,p
);
/* we reclaim an avail time that can be <0 due to the timer
approximations -> we have to postpone the deadline a little!
we can use the ADDUSEC2TIMESPEC because the time postponed is
less than 55ms */
ADDUSEC2TIMESPEC
((-proc_table
[p
].
avail_time * lev
->band_den
)
/ lev
->band_num
, &lev
->lastdline
);
#ifdef TBS_TEST
kern_printf
("TBS_task_epilogue: Deadline posponed to %ds %dns\n",
lev
->lastdline.
tv_sec, lev
->lastdline.
tv_nsec);
#endif
lev
->activated
= qq_getfirst
(&lev
->wait
);
if (lev
->activated
!= NIL
)
TBS_activation
(lev
);
}
else
/* the task has been preempted. it returns into the ready queue by
calling the guest_epilogue... */
level_table
[ lev
->scheduling_level
]->
guest_epilogue
(lev
->scheduling_level
,p
);
}
static void TBS_task_activate
(LEVEL l
, PID p
)
{
TBS_level_des
*lev
= (TBS_level_des
*)(level_table
[l
]);
if (proc_table
[p
].
status == SLEEP
||
proc_table
[p
].
status == TBS_WCET_VIOLATED
) {
ll_gettime
(TIME_EXACT
, &proc_table
[p
].
request_time);
if (lev
->activated
== NIL
) {
/* This is the first task in the level, so we activate it immediately */
lev
->activated
= p
;
TBS_activation
(lev
);
}
else {
proc_table
[p
].
status = TBS_WAIT
;
qq_insertlast
(p
, &lev
->wait
);
}
}
else if (lev
->flag
[p
] & TBS_SAVE_ARRIVALS
)
lev
->nact
[p
]++;
/* else
kern_printf("TBSREJ!!!");*/
}
static void TBS_task_insert
(LEVEL l
, PID p
)
{
TBS_level_des
*lev
= (TBS_level_des
*)(level_table
[l
]);
level_table
[ lev
->scheduling_level
]->
guest_insert
(lev
->scheduling_level
,p
);
}
static void TBS_task_extract
(LEVEL l
, PID p
)
{
TBS_level_des
*lev
= (TBS_level_des
*)(level_table
[l
]);
level_table
[ lev
->scheduling_level
]->
guest_extract
(lev
->scheduling_level
,p
);
}
static void TBS_task_endcycle
(LEVEL l
, PID p
)
{
TBS_level_des
*lev
= (TBS_level_des
*)(level_table
[l
]);
/* a task activation is finished, but we are using a JOB_TASK_MODEL
that implements a single activation, so we have to call
the guest_end, that representsa single activation... */
level_table
[ lev
->scheduling_level
]->
guest_end
(lev
->scheduling_level
,p
);
TBS_bandwidth_reclaiming
(lev
,p
);
/* we reset the capacity counters... */
if (lev
->flags
& TBS_ENABLE_WCET_CHECK
)
proc_table
[p
].
avail_time = proc_table
[p
].
wcet;
if (lev
->nact
[p
]) {
// lev->nact[p] can be >0 only if the SAVE_ARRIVALS bit is set
lev
->nact
[p
]--;
proc_table
[p
].
status = TBS_WAIT
;
qq_insertlast
(p
, &lev
->wait
);
}
else
proc_table
[p
].
status = SLEEP
;
lev
->activated
= qq_getfirst
(&lev
->wait
);
if (lev
->activated
!= NIL
)
TBS_activation
(lev
);
}
static void TBS_task_end
(LEVEL l
, PID p
)
{
TBS_level_des
*lev
= (TBS_level_des
*)(level_table
[l
]);
level_table
[ lev
->scheduling_level
]->
guest_end
(lev
->scheduling_level
,p
);
TBS_bandwidth_reclaiming
(lev
,p
);
proc_table
[p
].
status = FREE
;
q_insertfirst
(p
,&freedesc
);
lev
->activated
= qq_getfirst
(&lev
->wait
);
if (lev
->activated
!= NIL
)
TBS_activation
(lev
);
}
static void TBS_task_sleep
(LEVEL l
, PID p
)
{
TBS_level_des
*lev
= (TBS_level_des
*)(level_table
[l
]);
/* a task activation is finished, but we are using a JOB_TASK_MODEL
that implements a single activation, so we have to call
the guest_end, that representsa single activation... */
level_table
[ lev
->scheduling_level
]->
guest_end
(lev
->scheduling_level
,p
);
TBS_bandwidth_reclaiming
(lev
,p
);
/* we reset the capacity counters... */
if (lev
->flags
& TBS_ENABLE_WCET_CHECK
)
proc_table
[p
].
avail_time = proc_table
[p
].
wcet;
proc_table
[p
].
status = SLEEP
;
lev
->nact
[p
] = 0;
lev
->activated
= qq_getfirst
(&lev
->wait
);
if (lev
->activated
!= NIL
)
TBS_activation
(lev
);
}
static void TBS_task_delay
(LEVEL l
, PID p
, TIME usdelay
)
{
TBS_level_des
*lev
= (TBS_level_des
*)(level_table
[l
]);
level_table
[ lev
->scheduling_level
]->
guest_delay
(lev
->scheduling_level
,p
,usdelay
);
}
static int TBS_guest_create
(LEVEL l
, PID p
, TASK_MODEL
*m
)
{ kern_raise
(XINVALID_GUEST
,exec_shadow
); return 0; }
static void TBS_guest_detach
(LEVEL l
, PID p
)
{ kern_raise
(XINVALID_GUEST
,exec_shadow
); }
static void TBS_guest_dispatch
(LEVEL l
, PID p
, int nostop
)
{ kern_raise
(XINVALID_GUEST
,exec_shadow
); }
static void TBS_guest_epilogue
(LEVEL l
, PID p
)
{ kern_raise
(XINVALID_GUEST
,exec_shadow
); }
static void TBS_guest_activate
(LEVEL l
, PID p
)
{ kern_raise
(XINVALID_GUEST
,exec_shadow
); }
static void TBS_guest_insert
(LEVEL l
, PID p
)
{ kern_raise
(XINVALID_GUEST
,exec_shadow
); }
static void TBS_guest_extract
(LEVEL l
, PID p
)
{ kern_raise
(XINVALID_GUEST
,exec_shadow
); }
static void TBS_guest_endcycle
(LEVEL l
, PID p
)
{ kern_raise
(XINVALID_GUEST
,exec_shadow
); }
static void TBS_guest_end
(LEVEL l
, PID p
)
{ kern_raise
(XINVALID_GUEST
,exec_shadow
); }
static void TBS_guest_sleep
(LEVEL l
, PID p
)
{ kern_raise
(XINVALID_GUEST
,exec_shadow
); }
static void TBS_guest_delay
(LEVEL l
, PID p
,DWORD tickdelay
)
{ kern_raise
(XINVALID_GUEST
,exec_shadow
); }
/* Registration functions */
/*+ Registration function:
int flags the init flags ... see TBS.h +*/
void TBS_register_level
(int flags
, LEVEL master
, int num
, int den
)
{
LEVEL l
; /* the level that we register */
TBS_level_des
*lev
; /* for readableness only */
PID i
; /* a counter */
printk
("TBS_register_level\n");
/* request an entry in the level_table */
l
= level_alloc_descriptor
();
printk
(" alloco descrittore %d %d\n",l
,(int)sizeof(TBS_level_des
));
/* alloc the space needed for the TBS_level_des */
lev
= (TBS_level_des
*)kern_alloc
(sizeof(TBS_level_des
));
printk
(" lev=%d\n",(int)lev
);
/* update the level_table with the new entry */
level_table
[l
] = (level_des
*)lev
;
/* fill the standard descriptor */
strncpy(lev
->l.
level_name, TBS_LEVELNAME
, MAX_LEVELNAME
);
lev
->l.
level_code = TBS_LEVEL_CODE
;
lev
->l.
level_version = TBS_LEVEL_VERSION
;
lev
->l.
level_accept_task_model = TBS_level_accept_task_model
;
lev
->l.
level_accept_guest_model = TBS_level_accept_guest_model
;
lev
->l.
level_status = TBS_level_status
;
lev
->l.
level_scheduler = TBS_level_scheduler
;
if (flags
& TBS_ENABLE_GUARANTEE
)
lev
->l.
level_guarantee = TBS_level_guarantee
;
else
lev
->l.
level_guarantee = NULL
;
lev
->l.
task_create = TBS_task_create
;
lev
->l.
task_detach = TBS_task_detach
;
lev
->l.
task_eligible = TBS_task_eligible
;
lev
->l.
task_dispatch = TBS_task_dispatch
;
lev
->l.
task_epilogue = TBS_task_epilogue
;
lev
->l.
task_activate = TBS_task_activate
;
lev
->l.
task_insert = TBS_task_insert
;
lev
->l.
task_extract = TBS_task_extract
;
lev
->l.
task_endcycle = TBS_task_endcycle
;
lev
->l.
task_end = TBS_task_end
;
lev
->l.
task_sleep = TBS_task_sleep
;
lev
->l.
task_delay = TBS_task_delay
;
lev
->l.
guest_create = TBS_guest_create
;
lev
->l.
guest_detach = TBS_guest_detach
;
lev
->l.
guest_dispatch = TBS_guest_dispatch
;
lev
->l.
guest_epilogue = TBS_guest_epilogue
;
lev
->l.
guest_activate = TBS_guest_activate
;
lev
->l.
guest_insert = TBS_guest_insert
;
lev
->l.
guest_extract = TBS_guest_extract
;
lev
->l.
guest_endcycle = TBS_guest_endcycle
;
lev
->l.
guest_end = TBS_guest_end
;
lev
->l.
guest_sleep = TBS_guest_sleep
;
lev
->l.
guest_delay = TBS_guest_delay
;
/* fill the TBS descriptor part */
for (i
= 0; i
< MAX_PROC
; i
++) {
lev
->nact
[i
] = 0;
lev
->flag
[i
] = 0;
}
NULL_TIMESPEC
(&lev
->lastdline
);
qq_init
(&lev
->wait
);
lev
->activated
= NIL
;
lev
->U
= (MAX_BANDWIDTH
/ den
) * num
;
lev
->band_num
= num
;
lev
->band_den
= den
;
lev
->scheduling_level
= master
;
lev
->flags
= flags
& 0x07;
}
bandwidth_t TBS_usedbandwidth
(LEVEL l
)
{
TBS_level_des
*lev
= (TBS_level_des
*)(level_table
[l
]);
if (lev
->l.
level_code == TBS_LEVEL_CODE
&&
lev
->l.
level_version == TBS_LEVEL_VERSION
)
return lev
->U
;
else
return 0;
}
int TBS_get_nact
(LEVEL l
, PID p
)
{
TBS_level_des
*lev
= (TBS_level_des
*)(level_table
[l
]);
if (lev
->l.
level_code == TBS_LEVEL_CODE
&&
lev
->l.
level_version == TBS_LEVEL_VERSION
)
return lev
->nact
[p
];
else
return -1;
}