Subversion Repositories shark

Compare Revisions

Ignore whitespace Rev 989 → Rev 990

/shark/trunk/ports/first/include/fedfstar.h
0,0 → 1,149
/*
* 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: fedfstar.h,v 1.1 2005-04-07 10:59:34 trimarchi Exp $
 
File: $File$
Revision: $Revision: 1.1 $
Last update: $Date: 2005-04-07 10:59:34 $
------------
 
Title:
EDFSTAR
 
Task Models Accepted:
HARD_TASK_MODEL - Hard Tasks (only Periodic)
wcet field and mit field must be != 0. They are used to set the wcet
and period of the tasks.
periodicity field can be only PERIODIC
drel field is ignored
Guest Models Accepted:
JOB_TASK_MODEL - a single guest task activation
Identified by an absolute deadline and a period.
period field is ignored
 
Description:
 
This module schedule his tasks following the classic EDF
scheme. This module is derived from the EDFACT Scheduling Module.
 
This module can not stay alone: when it have to schedule a task, it
simply inserts it into another master module using a
BUDGET_TASK_MODEL.
 
No Task guarantee is performed at all.
The tasks scheduled are only periodic.
All the task are put in a queue and the scheduling is based on the
deadline value.
If a task miss a deadline a counter is incremented.
If a task exausts the wcet a counter is incremented
No ZOMBIE support!!!!!!
 
Exceptions raised:
XUNVALID_GUEST XUNVALID_TASK
some primitives are not implemented:
task_sleep, task_delay, guest_endcycle, guest_sleep, guest_delay
 
XACTIVATION
If a task is actiated through task_activate or guest_activate more than
one time
Restrictions & special features:
- This level doesn't manage the main task.
- Functions to return and reset the nact, wcet and dline miss
counters are provided
 
**/
 
/*
* Copyright (C) 2001 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
*
*/
 
 
#ifndef __FEDFSTAR_H__
#define __FEDFSTAR_H__
 
#include <ll/ll.h>
#include <kernel/config.h>
#include <sys/types.h>
#include <kernel/types.h>
 
 
typedef struct {
int command;
void *param;
} FEDFSTAR_command_message;
 
/* flags... */
#define FEDFSTAR_ENABLE_GUARANTEE 1 /* Task Guarantee enabled */
#define FEDFSTAR_ENABLE_ALL 1
 
#define FEDFSTAR_FAILED_GUARANTEE 8 /* used in the module, unsettabl
in EDF_register_level... */
 
 
 
#define FEDFSTAR_LEVELNAME "FEDFSTAR base"
#define FEDFSTAR_LEVEL_CODE 166
#define FEDFSTAR_LEVEL_VERSION 1
 
 
/* Registration function:
int budget The budget used by this module (see CBSSTAR.h)
int master The master module used by FEDFSTAR
*/
LEVEL FEDFSTAR_register_level(int master);
 
/* returns respectively the number of dline, wcet or nact; -1 if error */
int FEDFSTAR_get_dline_miss(PID p);
int FEDFSTAR_get_wcet_miss(PID p);
int FEDFSTAR_get_nact(PID p);
 
/* resets respectively the number of dline, wcet miss; -1 if error */
int FEDFSTAR_reset_dline_miss(PID p);
int FEDFSTAR_reset_wcet_miss(PID p);
 
int FEDFSTAR_getbudget(LEVEL l, PID p);
int FEDFSTAR_setbudget(LEVEL l, PID p, int budget);
int FEDFSTAR_budget_has_thread(LEVEL l, int budget);
 
void FEDFSTAR_set_nopreemtive_current(LEVEL l);
void FEDFSTAR_unset_nopreemtive_current(LEVEL l);
 
#endif
 
/shark/trunk/ports/first/include/cbsnhstar.h
0,0 → 1,189
/*
* 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: cbsnhstar.h,v 1.1 2005-04-07 10:59:34 trimarchi Exp $
 
File: $File$
Revision: $Revision: 1.1 $
Last update: $Date: 2005-04-07 10:59:34 $
------------
 
This file contains the budget support for the multiapplication
scheduling algorithm proposed in the framework of the FIRST Project
 
Title:
CBSSTAR
 
Task Models Accepted:
None!
 
Guest Models Accepted:
BUDGET_TASK_MODEL - A task that is attached to a budget
int b; --> the number of the budget which the task is attached to
 
Description:
This module schedule its tasks following the CBS scheme.
Every task is inserted using the guest calls.
The module defines a limited set of budgets that the application
can use. Every guest task will use a particular budget; FIFO
scheduling is used inside a budget to schedule more than one ready
task attached to the same budget.
 
The tasks are inserted in an EDF level (or similar) with a JOB_TASK_MODEL,
and the CBS level expects that the task is scheduled with the absolute
deadline passed in the model.
 
This module tries to implement a simplified version of the guest
task interface:
- To insert a guest task, use guest_create
- When a task is dispatched, use guest_dispatch
- When a task have to be suspended, you have to use:
-> preemption: use guest_epilogue
-> synchronization, end: use guest_end
Remember: no check is done on the budget number passed with the model!!!
 
Exceptions raised:
XUNVALID_TASK
This level doesn't support normal tasks, but just guest tasks.
When a task operation is called, an exception is raised.
 
Restrictions & special features:
- This level doesn't manage the main task.
- At init time we have to specify:
. guarantee check
(when all task are created the system will check that the task_set
will not use more than the available bandwidth)
- A function to return the used bandwidth of the level is provided.
 
- A function is provided to allocate a buffer.
*/
 
/*
* Copyright (C) 2002 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
*
*/
 
 
#ifndef __CBSNHSTAR_H__
#define __CBSNHSTAR_H__
 
#include <kernel/kern.h>
 
//#include <ll/ll.h>
//#include <kernel/config.h>
//#include <sys/types.h>
//#include <kernel/types.h>
//#include <modules/codes.h>
 
/* -----------------------------------------------------------------------
BUDGET_TASK_MODEL: a model for guest tasks
----------------------------------------------------------------------- */
 
#define BUDGET_PCLASS 0x0600
typedef struct {
TASK_MODEL t;
int b;
} BUDGET_TASK_MODEL;
 
#define budget_task_default_model(m,buf) \
task_default_model((m).t, BUDGET_PCLASS), \
(m).b = (buf);
 
 
 
/* some constants for registering the Module in the right place */
#define CBSNHSTAR_LEVELNAME "CBSNHSTAR"
#define CBSNHSTAR_LEVEL_CODE 106
#define CBSNHSTAR_LEVEL_VERSION 1
 
typedef struct {
int command;
void *param;
} CBSNHSTAR_command_message;
 
typedef struct {
int budget;
TIME T,Q;
} CBSNHSTAR_mod_budget;
 
/* Registration function:
int N Maximum number of budgets allocated for the applications
LEVEL master the level that must be used as master level for the
CBS tasks
*/
LEVEL CBSNHSTAR_register_level(int n, LEVEL master);
 
/* Allocates a budget to be used for an application.
Input parameters:
Q The budget
T The period of the budget
Return value:
0..N The ID of the budget
-1 no more free budgets
-2 The budgets allocated locally to this module have bandwidth > 1
-3 wrong LEVEL id
*/
int CBSNHSTAR_setbudget(LEVEL l, TIME Q, TIME T, TIME D, LEVEL local_scheduler_level, int scheduler_id);
 
int CBSNHSTAR_removebudget(LEVEL l, int budget);
 
int CBSNHSTAR_adjust_budget(LEVEL l, TIME Q, TIME T, TIME D, int budget);
 
int CBSNHSTAR_getbudgetinfo(LEVEL l, TIME *Q, TIME *T, TIME *D, int budget);
 
int CBSNHSTAR_was_budget_overran(LEVEL l, int budget);
 
int CBSNHSTAR_is_active(LEVEL l, int budget);
 
int CBSNHSTAR_get_local_scheduler_level_from_budget(LEVEL l, int budget);
 
int CBSNHSTAR_get_local_scheduler_level_from_pid(LEVEL l, PID p);
 
int CBSNHSTAR_get_local_scheduler_id_from_budget(LEVEL l, int budget);
 
int CBSNHSTAR_get_local_scheduler_id_from_pid(LEVEL l, PID p);
 
int CBSNHSTAR_get_last_reclaiming(LEVEL l, PID p);
 
int CBSNHSTAR_get_remain_capacity(LEVEL l, int budget);
 
void CBSNHSTAR_disable_server(LEVEL l, int budget);
 
int CBSNHSTAR_getrecharge_number(LEVEL l, int budget);
#endif
/shark/trunk/ports/first/modules/fedfstar.c
0,0 → 1,1098
/*
* Project: S.Ha.R.K.
*
* Coordinators:
* Giorgio Buttazzo <giorgio@sssup.it>
* Paolo Gai <pj@gandalf.sssup.it>
*
* Authors :
* Paolo Gai <pj@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
*/
 
/*
* Copyright (C) 2001 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 "ll/i386/64bit.h"
#include "fedfstar.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>
 
#include <tracer.h>
 
/* for iqueues */
/* #include "iqueue.h" Now iqueues are the only queue type available
into the kernel */
#include <kernel/iqueue.h>
 
/* for BUDGET_TASK_MODEL */
#include "fsf_configuration_parameters.h"
#include "fsf_core.h"
#include "fsf_server.h"
#include <posix/posix/comm_message.h>
 
 
/*
* DEBUG stuffs begin
*/
 
//#define FEDFSTAR_DEBUG
//#define FDB_DEBUG
 
#ifdef FEDFSTAR_DEBUG
 
static __inline__ fake_printf(char *fmt, ...) {}
 
//#define fedfstar_printf fake_printf
//#define fedfstar_printf2 fake_printf
//#define fedfstar_printf3 fake_printf
 
#define fedfstar_printf kern_printf
#define fedfstar_printf2 kern_printf
#define fedfstar_printf3 kern_printf
#endif
 
/*
* DEBUG stuffs end
*/
 
/* Status used in the level */
#define FEDFSTAR_READY MODULE_STATUS_BASE /* - Ready status */
#define FEDFSTAR_IDLE MODULE_STATUS_BASE+4 /* to wait the deadline */
 
/* flags */
#define FEDFSTAR_CHANGE_LEVEL 8
#define FEDFSTAR_FLAG_NOPREEMPT 4
#define FEDFSTAR_FLAG_NORAISEEXC 2
#define FEDFSTAR_FLAG_SPORADIC 1
 
 
/* the level redefinition for the Earliest Deadline First level */
typedef struct {
level_des l; /* the standard level descriptor */
 
TIME period[MAX_PROC]; /* The task periods; the deadlines are
stored in the priority field */
int deadline_timer[MAX_PROC];
/* The task deadline timers */
 
struct timespec deadline_timespec[MAX_PROC];
 
int dline_miss[MAX_PROC]; /* Deadline miss counter */
int wcet_miss[MAX_PROC]; /* Wcet miss counter */
 
int nact[MAX_PROC]; /* Wcet miss counter */
 
int flag[MAX_PROC];
/* used to manage the JOB_TASK_MODEL and the
periodicity */
 
IQUEUE ready; /* the ready queue */
 
PID activated; /* the task that has been inserted into the
master module */
 
int budget[MAX_PROC];
 
int scheduling_level;
 
int cap_lev;
struct timespec cap_lasttime;
 
int new_level[MAX_PROC];
int wcet[MAX_PROC]; /* save the wcet fields */
 
int ctime[MAX_PROC]; /* last computation time */
int cavg[MAX_PROC]; /* avg of computation time */
int ccount[MAX_PROC]; /* number of istance */
 
} FEDFSTAR_level_des;
 
#define HISTORY_BACK 4
#define GRANULARITY 5 // in microseconds
 
typedef bandwidth_t inv_bandwidth_t;
 
static long long int delta_new;
static long long int tita[HISTORY_BACK][FSF_MAX_N_SERVERS];
static bandwidth_t u[HISTORY_BACK][FSF_MAX_N_SERVERS];
 
void init_feedbackstruct(void) {
int i=0, j=0;
for (i=0; i<FSF_MAX_N_SERVERS; i++)
for (j=0; j<HISTORY_BACK; j++) {
u[j][i]=0;
tita[j][i]=0;
}
}
 
 
long long int FDB_sample(int sched_error, TIME server_period, TIME cavg)
{
static long long int delta_old=0;
static int sched_error_prev=0;
long long int temp,temp1;
int beta_1; //Not really this value
int gamma_1;
int beta_2;
int gamma_2;
 
#ifdef FDB_DEBUG
kern_printf("(FDB:sample:period:%d:cavg:%d:sched_error:%d)",(int)server_period,(int)cavg, sched_error);
#endif
 
temp=1000*server_period/cavg;
beta_1=temp*6/5;
gamma_1=temp*(-93)/100;
beta_2=temp/5;
gamma_2=temp*7/100;
 
#ifdef FDB_DEBUG
kern_printf("(FDB:sample:b1:%d:g1:%d:b2:%d:g2:%d:temp:%d)",beta_1,gamma_1,beta_2,gamma_2, (int)temp);
#endif
 
if ((long long int)sched_error>=(long long int)server_period) {
temp=beta_1*(long long int)sched_error/server_period;
temp1=gamma_1*(long long int)sched_error_prev/server_period;
delta_new=delta_old-temp-temp1;
}
else {
temp=beta_2*(long long int)sched_error/server_period;
temp1=gamma_2*(long long int)sched_error_prev/server_period;
delta_new=delta_old-temp-temp1;
}
#ifdef FDB_DEBUG
kern_printf("(FDB1:sched_error:%d:delta_new:%d)",sched_error, (int)delta_new);
#endif
 
delta_old=delta_new;
sched_error_prev=sched_error;
 
return(delta_new);
}
 
 
/* This function preditcs the value of the next execution time based on the history of the task.
The algorithm is known as LMS and minimizes the square error.
It has to add the blocking time if the task may be block
And to determine the bandwidth it has to add the bandwidth determine in the previous function
*/
TIME FDB_activate(fsf_server_id_t server, TIME server_period, TIME blk_time, TIME c_time, TIME c_avg, bandwidth_t bw)
{
//Filter coefficients
static int mu=2000; //convergence factor
static long long int u_predicted=0;
static long long int pred_error=0;
bandwidth_t u_avg;
bandwidth_t unew;
int i;
TIME Q_new;
long long int u_new;
static long long int u_p_avg=0;
static int nro=0;
//u_avg=server_bandwidth_avg;
 
 
nro++;
pred_error=u_predicted-(long long int)u[0][server];
 
for (i=0;i<HISTORY_BACK;i++) {
long long int temp=0;
temp=pred_error*(long long int)u[i][server];
tita[i][server]=tita[i][server]-temp;
}
u_predicted=0;
for (i=0;i<HISTORY_BACK;i++)
u_predicted+=((tita[i][server]*(long long int)u[i][server]))/MAX_BANDWIDTH/MAX_BANDWIDTH/mu;
for (i=0; i<(HISTORY_BACK-1); i++)
u[i+1][server]=u[i][server];
u_p_avg=(u_p_avg*(nro-1)+u_predicted)/nro; //OK
 
if (c_avg!=0)
mul32div32to32(MAX_BANDWIDTH,c_avg,server_period,u_avg);
else
u_avg=bw;
 
kern_printf("(FDB:act_int:cavg:%d:sp:%d)", c_avg, server_period, u_avg);
mul32div32to32(MAX_BANDWIDTH,c_time,server_period,u[0][server]); // last real computation value
// c_predicted+=blk_time;
/* What follows is the update of the server budget based on the FDB_sample return value and the prediction function
*/
delta_new=MAX_BANDWIDTH*(delta_new/1000);
u_new=delta_new+(long long int)u_avg;
if (u_new<0) exit(-1);
if (u_new>MAX_BANDWIDTH) exit(-1);
unew=(bandwidth_t)u_new;
 
mul32div32to32(server_period,unew, MAX_BANDWIDTH, Q_new);
 
//Q_new=server_period*1000/u;
//#ifdef FDB_DEBUG
kern_printf("(FDB:act_int:unew:%d:delta_new:%d:uavg:%d)",unew, delta_new, u_avg);
//#endif
kern_printf("(FDB:act_int:qnew:%ld)",Q_new);
return(Q_new);
}
 
 
static void capacity_handler(void *l)
{
FEDFSTAR_level_des *lev = l;
lev->cap_lev = NIL;
event_need_reschedule();
}
 
static void FEDFSTAR_check_preemption(FEDFSTAR_level_des *lev)
{
PID first=NIL;
 
#ifdef FEDFSTAR_DEBUG
edfstar_printf("(E:chk)");
#endif
/* check if the task is preempteble or not */
if (lev->activated != NIL && lev->flag[lev->activated] & FEDFSTAR_FLAG_NOPREEMPT) return;
 
if ((first = iq_query_first(&lev->ready)) != lev->activated) {
if (lev->activated != NIL)
level_table[ lev->scheduling_level ]->
private_extract(lev->scheduling_level, lev->activated);
 
lev->activated = first;
 
if (first != NIL) {
BUDGET_TASK_MODEL b;
budget_task_default_model(b, lev->budget[first]);
 
level_table[ lev->scheduling_level ]->
private_insert(lev->scheduling_level, first, (TASK_MODEL *)&b);
}
}
}
 
static void FEDFSTAR_timer_deadline(void *par);
 
static void FEDFSTAR_internal_activate(FEDFSTAR_level_des *lev, PID p,
struct timespec *t)
{
TIME Q, D, T;
int budget;
bandwidth_t bw;
 
#ifdef FEDFSTAR_DEBUG
edfstar_printf("(E:iact)");
#endif
 
ADDUSEC2TIMESPEC(lev->period[p], t);
 
*iq_query_timespec(p, &lev->ready) = *t;
lev->deadline_timespec[p] = *t;
 
/* Insert task in the correct position */
proc_table[p].status = FEDFSTAR_READY;
iq_timespec_insert(p,&lev->ready);
proc_table[p].control &= ~CONTROL_CAP;
 
budget=lev->budget[p];
SERVER_getbudgetinfo(lev->scheduling_level, &Q, &T, &D, budget);
 
mul32div32to32(MAX_BANDWIDTH, Q, T, bw);
 
Q=FDB_activate(budget, T, 0, lev->ctime[p], lev->cavg[p], bw);
SERVER_adjust_budget(lev->scheduling_level, Q, T, D, budget);
 
 
/* check for preemption */
FEDFSTAR_check_preemption(lev);
}
 
static void FEDFSTAR_timer_deadline(void *par)
{
PID p = (PID) par;
FEDFSTAR_level_des *lev;
 
lev = (FEDFSTAR_level_des *)level_table[proc_table[p].task_level];
lev->deadline_timer[p] = NIL;
 
switch (proc_table[p].status) {
case FEDFSTAR_IDLE:
/* set the request time */
if (!(lev->flag[p] & FEDFSTAR_FLAG_SPORADIC))
FEDFSTAR_internal_activate(lev,p,iq_query_timespec(p, &lev->ready));
 
event_need_reschedule();
break;
 
default:
#ifdef FEDFSTAR_DEBUG
kern_printf("(E:Dl:%d)",p);
#endif
/* else, a deadline miss occurred!!! */
lev->dline_miss[p]++;
TRACER_LOGEVENT(FTrace_EVT_task_deadline_miss,proc_table[p].context,proc_table[p].task_level);
 
/* the task is into another state */
if (!(lev->flag[p] & FEDFSTAR_FLAG_SPORADIC)) {
lev->nact[p]++;
ADDUSEC2TIMESPEC(lev->period[p], &lev->deadline_timespec[p]);
}
}
 
/* Set the deadline timer */
if (!(lev->flag[p] & FEDFSTAR_FLAG_SPORADIC))
lev->deadline_timer[p] = kern_event_post(&lev->deadline_timespec[p],
FEDFSTAR_timer_deadline,
(void *)p);
 
}
 
static int FEDFSTAR_private_change_level(LEVEL l, PID p)
{
 
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
 
/* Change task level */
if (lev->flag[p] & FEDFSTAR_CHANGE_LEVEL) {
#ifdef FEDFSTAR_DEBUG
edfstar_printf("(E:clev)");
#endif
STD_command_message msg;
proc_table[p].status = SLEEP;
lev->flag[p] &= ~ FEDFSTAR_CHANGE_LEVEL;
level_table[lev->scheduling_level]->private_extract(lev->scheduling_level,p);
iq_extract(p,&lev->ready);
if (lev->deadline_timer[p] != -1)
kern_event_delete(lev->deadline_timer[p]);
lev->deadline_timer[p]=NIL;
FEDFSTAR_check_preemption(lev);
lev->nact[p] = 0;
lev->budget[p] = -1;
proc_table[p].task_level = lev->new_level[p];
/* Send change level command to local scheduler */
 
msg.command = STD_ACTIVATE_TASK;
msg.param = NULL;
 
level_table[ lev->new_level[p] ]->public_message(lev->new_level[p],p,&msg);
return 1;
 
}
 
return 0;
 
}
 
 
static void FEDFSTAR_timer_guest_deadline(void *par)
{
PID p = (PID) par;
 
#ifdef FEDFSTAR_DEBUG
edfstar_printf("(E:gdl)");
#endif
 
kern_raise(XDEADLINE_MISS,p);
}
 
static int FEDFSTAR_public_create(LEVEL l, PID p, TASK_MODEL *m)
{
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
 
/* if the FEDFSTAR_task_create is called, then the pclass must be a
valid pclass. */
HARD_TASK_MODEL *h;
 
if (m->pclass != HARD_PCLASS) return -1;
if (m->level != 0 && m->level != l) return -1;
h = (HARD_TASK_MODEL *)m;
if (!h->wcet || !h->mit) return -1;
/* now we know that m is a valid model */
 
#ifdef FEDFSTAR_DEBUG
edfstar_printf("(E:Crt)");
#endif
 
lev->period[p] = h->mit;
 
lev->flag[p] = 0;
 
if (h->periodicity == APERIODIC)
lev->flag[p] |= FEDFSTAR_FLAG_SPORADIC;
 
lev->deadline_timer[p] = -1;
lev->dline_miss[p] = 0;
lev->wcet_miss[p] = 0;
lev->nact[p] = 0;
 
/* Enable wcet check */
proc_table[p].avail_time = h->wcet;
proc_table[p].wcet = h->wcet;
proc_table[p].status = SLEEP;
 
return 0; /* OK, also if the task cannot be guaranteed... */
}
 
 
static void FEDFSTAR_account_capacity(FEDFSTAR_level_des *lev, PID p)
{
struct timespec ty;
TIME tx;
 
 
SUBTIMESPEC(&schedule_time, &lev->cap_lasttime, &ty);
tx = TIMESPEC2USEC(&ty);
 
proc_table[p].avail_time -= tx;
}
 
static int FEDFSTAR_public_eligible(LEVEL l, PID p)
{
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
 
#ifdef FEDFSTAR_DEBUG
edfstar_printf2("(E:eli:%d)",p);
#endif
 
return level_table[ lev->scheduling_level ]->
private_eligible(lev->scheduling_level,p);
 
}
 
static void FEDFSTAR_public_dispatch(LEVEL l, PID p, int nostop)
{
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
struct timespec ty;
 
#ifdef FEDFSTAR_DEBUG
edfstar_printf("(E:dis)");
#endif
if (!nostop || proc_table[exec].task_level==l) {
TIMESPEC_ASSIGN(&ty, &schedule_time);
TIMESPEC_ASSIGN(&lev->cap_lasttime, &schedule_time);
 
/* ...and finally, we have to post a capacity event on exec task because the shadow_task consume
* * capacity on exe task always */
if (proc_table[exec].avail_time > 0) {
ADDUSEC2TIMESPEC(proc_table[exec].avail_time ,&ty);
lev->cap_lev = kern_event_post(&ty,capacity_handler, lev);
}
level_table[lev->scheduling_level]->private_dispatch(lev->scheduling_level, p, nostop);
}
else
level_table[proc_table[exec].task_level]->public_dispatch(proc_table[exec].task_level, p, nostop);
 
}
 
static void FEDFSTAR_public_epilogue(LEVEL l, PID p)
{
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
 
#ifdef FEDFSTAR_DEBUG
edfstar_printf("(E:epi ");
#endif
 
if (lev->cap_lev!=NIL) {
kern_event_delete(lev->cap_lev);
lev->cap_lev=NIL;
}
 
if ( proc_table[exec].task_level==l ) {
if (proc_table[exec].avail_time > 0) FEDFSTAR_account_capacity(lev,exec);
 
if (FEDFSTAR_private_change_level(l, p)) return;
 
/* check if the wcet is finished... */
if (proc_table[exec].avail_time < 0) {
/* wcet finished: disable wcet event and count wcet miss */
 
#ifdef FEDFSTAR_DEBUG
edfstar_printf2("W%d",p);
#endif
//proc_table[p].control &= ~CONTROL_CAP;
lev->wcet_miss[exec]++;
proc_table[exec].avail_time = 0;
TRACER_LOGEVENT(FTrace_EVT_task_wcet_violation,proc_table[exec].context,proc_table[exec].task_level);
}
 
#ifdef FEDFSTAR_DEBUG
edfstar_printf(")");
#endif
 
level_table[ lev->scheduling_level ]->
private_epilogue(lev->scheduling_level,p);
 
proc_table[exec].status = FEDFSTAR_READY;
} else
level_table[proc_table[exec].task_level]->public_epilogue(proc_table[exec].task_level,p);
 
}
 
static void FEDFSTAR_public_activate(LEVEL l, PID p, struct timespec *o)
{
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
struct timespec t;
 
#ifdef FEDFSTAR_DEBUG
edfstar_printf("(E:act:%d)",p);
#endif
 
/* Test if we are trying to activate a non sleeping task */
/* save activation (only if needed... */
if (proc_table[p].status != SLEEP) {
/* a periodic task cannot be activated when it is already active */
/* but aperiodic task can be reactivate before */
if (lev->flag[p] & FEDFSTAR_FLAG_SPORADIC) {
if (proc_table[p].status != FEDFSTAR_IDLE) {
lev->nact[p]++;
//kern_printf("(Inc nact %d)",p);
//kern_printf("(%d STATUS %d %ds %dns)", p, proc_table[p].status, o->tv_sec, o->tv_nsec/1000);
return;
}
} else {
return;
//kern_raise(XACTIVATION,p);
}
}
 
kern_gettime(&t);
 
FEDFSTAR_internal_activate(lev,p, &t);
 
/* Set the deadline timer */
lev->deadline_timer[p] = kern_event_post(&lev->deadline_timespec[p],
FEDFSTAR_timer_deadline,
(void *)p);
 
}
 
static void FEDFSTAR_public_unblock(LEVEL l, PID p)
{
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
 
#ifdef FEDFSTAR_DEBUG
edfstar_printf("(E:ins)");
#endif
 
/* Insert task in the correct position */
proc_table[p].status = FEDFSTAR_READY;
iq_timespec_insert(p,&lev->ready);
 
/* and check for preemption! */
FEDFSTAR_check_preemption(lev);
 
}
 
static void FEDFSTAR_public_block(LEVEL l, PID p)
{
 
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
 
#ifdef FEDFSTAR_DEBUG
edfstar_printf("(E:ext)");
#endif
 
/* the task is blocked on a synchronization primitive. we have to
remove it from the master module -and- from the local queue! */
iq_extract(p,&lev->ready);
 
/* and finally, a preemption check! (it will also call guest_end) */
FEDFSTAR_check_preemption(lev);
}
 
static int FEDFSTAR_public_message(LEVEL l, PID p, void *m)
{
 
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
struct timespec temp;
STD_command_message *msg;
HARD_TASK_MODEL *h;
TIME Q, D, T;
struct timespec t,diff;
int sched_error_act;
int budget;
#ifdef FEDFSTAR_DEBUG
edfstar_printf("(E:ecy ");
#endif
 
switch ((long)(m)) {
 
/* Task EndCycle */
case (long)(NULL):
 
if (FEDFSTAR_private_change_level(l,p)) return 0;
sched_error_act=0;
budget=FEDFSTAR_getbudget(l,p);
SERVER_getbudgetinfo(lev->scheduling_level, &Q, &T, &D, budget);
SERVER_getdeadline(lev->scheduling_level, budget, &t);
//rnumber=CBSNHSTAR_getrecharge_number(lev->scheduling_level, budget);
/* check if the deadline has already expired */
temp = *iq_query_timespec(p, &lev->ready);
kern_printf("(dt sec %ld, us %ld)", temp.tv_sec, temp.tv_nsec/1000);
kern_printf("(ds sec %ld, us %ld)", t.tv_sec, t.tv_nsec/1000);
if (/* 1 */ TIMESPEC_A_LT_B(&t,&temp)) {
SUBTIMESPEC(&temp, &t, &diff);
sched_error_act=-TIMESPEC2USEC(&diff);
}
else {
SUBTIMESPEC(&t, &temp, &diff);
sched_error_act=TIMESPEC2USEC(&diff);
}
if (proc_table[p].avail_time > 0) FEDFSTAR_account_capacity(lev,p);
 
/* we call guest_end directly here because the same task may
be reinserted in the queue before calling the preemption check! */
level_table[ lev->scheduling_level ]->
private_extract(lev->scheduling_level,p);
lev->activated = NIL;
 
iq_extract(p,&lev->ready);
 
/* we reset the capacity counters... */
proc_table[p].avail_time = proc_table[p].wcet;
 
lev->ctime[p]=proc_table[p].wcet-proc_table[p].avail_time;
 
lev->cavg[p]=(lev->ctime[p]+(lev->cavg[p])*(lev->ccount[p]))/(lev->ccount[p]+1);
lev->ccount[p]=(lev->ccount[p]%INT_MAX)+1;
delta_new=FDB_sample(sched_error_act, T, lev->cavg[p]);
 
if (lev->nact[p] > 0) {
#ifdef FEDFSTAR_DEBUG
kern_printf("E%d",p);
#endif
/* Pending activation: reactivate the thread!!! */
lev->nact[p]--;
/* see also FEDFSTAR_timer_deadline */
kern_gettime(&temp);
FEDFSTAR_internal_activate(lev,p, &temp);
/* check if the deadline has already expired */
temp = *iq_query_timespec(p, &lev->ready);
if (TIMESPEC_A_LT_B(&temp, &schedule_time)) {
/* count the deadline miss */
lev->dline_miss[p]++;
kern_event_delete(lev->deadline_timer[p]);
lev->deadline_timer[p] = NIL;
}
 
} else {
 
#ifdef FEDFSTAR_DEBUG
edfstar_printf("e%d",p);
#endif
/* the task has terminated his job before it consume the wcet. All OK! */
if (lev->flag[p] & FEDFSTAR_FLAG_SPORADIC)
proc_table[p].status = SLEEP;
else
proc_table[p].status = FEDFSTAR_IDLE;
if (lev->flag[p] & FEDFSTAR_FLAG_SPORADIC && lev->deadline_timer[p] != NIL) {
kern_event_delete(lev->deadline_timer[p]);
lev->deadline_timer[p] = NIL;
}
/* and finally, a preemption check! */
FEDFSTAR_check_preemption(lev);
/* when the deadline timer fire, it recognize the situation and set
correctly all the stuffs (like reactivation, etc... ) */
}
 
#ifdef FEDFSTAR_DEBUG
edfstar_printf(")");
#endif
 
TRACER_LOGEVENT(FTrace_EVT_task_end_cycle,proc_table[p].context,proc_table[p].task_level);
jet_update_endcycle(); /* Update the Jet data... */
break;
 
default:
msg = (STD_command_message *)m;
#ifdef FEDFSTAR_DEBUG
edfstar_printf("(E:MSG %d)",msg->command);
#endif
switch(msg->command) {
case STD_SET_NEW_MODEL:
/* if the FEDFSTAR_task_create is called, then the pclass must be a
valid pclass. */
h=(HARD_TASK_MODEL *)(msg->param);
/* now we know that m is a valid model */
lev->wcet[p] = h->wcet;
lev->period[p] = h->mit;
 
#ifdef FEDFSTAR_DEBUG
kern_printf("(EDF:NM p%d w%d m%d)", p, h->wcet, h->mit);
#endif
lev->flag[p] = 0;
lev->deadline_timer[p] = -1;
lev->dline_miss[p] = 0;
lev->wcet_miss[p] = 0;
lev->nact[p] = 0;
 
break;
 
case STD_SET_NEW_LEVEL:
lev->flag[p] |= FEDFSTAR_CHANGE_LEVEL;
lev->new_level[p] = (int)(msg->param);
 
break;
 
case STD_ACTIVATE_TASK:
#ifdef FEDFSTAR_DEBUG
kern_printf("(EDF:SA)");
#endif
/* Enable wcet check */
proc_table[p].avail_time = lev->wcet[p];
proc_table[p].wcet = lev->wcet[p];
proc_table[p].control &= ~CONTROL_CAP;
FEDFSTAR_public_activate(l, p,NULL);
break;
 
}
 
break;
}
return 0;
}
 
static void FEDFSTAR_public_end(LEVEL l, PID p)
{
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
 
#ifdef FEDFSTAR_DEBUG
edfstar_printf("(E:end)");
#endif
 
iq_extract(p,&lev->ready);
level_table[ lev->scheduling_level ]->
private_extract(lev->scheduling_level, p);
 
 
/* we finally put the task in the ready queue */
proc_table[p].status = FREE;
iq_insertfirst(p,&freedesc);
lev->activated=NIL;
if (lev->deadline_timer[p] != -1) {
kern_event_delete(lev->deadline_timer[p]);
lev->deadline_timer[p] = NIL;
}
 
/* and finally, a preemption check! (it will also call guest_end) */
FEDFSTAR_check_preemption(lev);
}
 
/* Guest Functions
These functions manages a JOB_TASK_MODEL, that is used to put
a guest task in the FEDFSTAR ready queue. */
 
static void FEDFSTAR_private_insert(LEVEL l, PID p, TASK_MODEL *m)
{
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
JOB_TASK_MODEL *job;
 
if (m->pclass != JOB_PCLASS || (m->level != 0 && m->level != l) ) {
kern_raise(XINVALID_TASK, p);
return;
}
 
job = (JOB_TASK_MODEL *)m;
 
/* if the FEDFSTAR_guest_create is called, then the pclass must be a
valid pclass. */
 
*iq_query_timespec(p, &lev->ready) = job->deadline;
lev->deadline_timer[p] = -1;
lev->dline_miss[p] = 0;
lev->wcet_miss[p] = 0;
lev->nact[p] = 0;
 
if (job->noraiseexc)
lev->flag[p] |= FEDFSTAR_FLAG_NORAISEEXC;
else {
lev->flag[p] &= ~FEDFSTAR_FLAG_NORAISEEXC;
lev->deadline_timer[p] = kern_event_post(iq_query_timespec(p, &lev->ready),
FEDFSTAR_timer_guest_deadline,
(void *)p);
}
 
lev->period[p] = job->period;
 
/* Insert task in the correct position */
iq_timespec_insert(p,&lev->ready);
proc_table[p].status = FEDFSTAR_READY;
 
/* check for preemption */
FEDFSTAR_check_preemption(lev);
 
/* there is no bandwidth guarantee at this level, it is performed
by the level that inserts guest tasks... */
}
 
static void FEDFSTAR_private_dispatch(LEVEL l, PID p, int nostop)
{
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
 
level_table[ lev->scheduling_level ]->
private_dispatch(lev->scheduling_level,p,nostop);
}
 
static void FEDFSTAR_private_epilogue(LEVEL l, PID p)
{
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
 
/* the task has been preempted. it returns into the ready queue... */
level_table[ lev->scheduling_level ]->
private_epilogue(lev->scheduling_level,p);
 
proc_table[p].status = FEDFSTAR_READY;
}
 
static void FEDFSTAR_private_extract(LEVEL l, PID p)
{
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
 
#ifdef FEDFSTAR_DEBUG
kern_printf("FEDFSTAR_guest_end: dline timer %d\n",lev->deadline_timer[p]);
#endif
 
iq_extract(p, &lev->ready);
 
/* we remove the deadline timer, because the slice is finished */
if (lev->deadline_timer[p] != NIL) {
#ifdef FEDFSTAR_DEBUG
kern_printf("FEDFSTAR_guest_end: dline timer %d\n",lev->deadline_timer[p]);
#endif
kern_event_delete(lev->deadline_timer[p]);
lev->deadline_timer[p] = NIL;
}
 
/* and finally, a preemption check! (it will also call guest_end() */
FEDFSTAR_check_preemption(lev);
}
 
/* Registration functions */
 
/* Registration function:
int flags the init flags ... see FEDFSTAR.h */
 
LEVEL FEDFSTAR_register_level(int master)
{
LEVEL l; /* the level that we register */
FEDFSTAR_level_des *lev; /* for readableness only */
PID i; /* a counter */
 
#ifdef FEDFSTAR_DEBUG
printk("FEDFSTAR_register_level\n");
#endif
 
/* request an entry in the level_table */
l = level_alloc_descriptor(sizeof(FEDFSTAR_level_des));
 
lev = (FEDFSTAR_level_des *)level_table[l];
 
/* fill the standard descriptor */
lev->l.private_insert = FEDFSTAR_private_insert;
lev->l.private_extract = FEDFSTAR_private_extract;
lev->l.private_dispatch = FEDFSTAR_private_dispatch;
lev->l.private_epilogue = FEDFSTAR_private_epilogue;
 
lev->l.public_guarantee = NULL;
lev->l.public_eligible = FEDFSTAR_public_eligible;
lev->l.public_create = FEDFSTAR_public_create;
lev->l.public_end = FEDFSTAR_public_end;
lev->l.public_dispatch = FEDFSTAR_public_dispatch;
lev->l.public_epilogue = FEDFSTAR_public_epilogue;
lev->l.public_activate = FEDFSTAR_public_activate;
lev->l.public_unblock = FEDFSTAR_public_unblock;
lev->l.public_block = FEDFSTAR_public_block;
lev->l.public_message = FEDFSTAR_public_message;
 
/* fill the FEDFSTAR descriptor part */
for(i=0; i<MAX_PROC; i++) {
lev->period[i] = 0;
lev->deadline_timer[i] = -1;
lev->flag[i] = 0;
lev->dline_miss[i] = 0;
lev->wcet_miss[i] = 0;
lev->nact[i] = 0;
lev->budget[i] = NIL;
lev->new_level[i] = -1;
lev->ctime[i] = 0;
lev->cavg[i] = 0;
lev->ccount[i] = 0;
}
 
iq_init(&lev->ready, NULL, IQUEUE_NO_PRIORITY);
lev->activated = NIL;
 
lev->scheduling_level = master;
lev->cap_lev = NIL;
NULL_TIMESPEC(&lev->cap_lasttime);
 
return l;
}
 
int FEDFSTAR_get_dline_miss(PID p)
{
LEVEL l = proc_table[p].task_level;
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
return lev->dline_miss[p];
}
 
int FEDFSTAR_get_wcet_miss(PID p)
{
LEVEL l = proc_table[p].task_level;
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
 
return lev->wcet_miss[p];
}
 
int FEDFSTAR_get_nact(PID p)
{
LEVEL l = proc_table[p].task_level;
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
 
return lev->nact[p];
}
 
int FEDFSTAR_reset_dline_miss(PID p)
{
LEVEL l = proc_table[p].task_level;
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
 
lev->dline_miss[p] = 0;
return 0;
}
 
int FEDFSTAR_reset_wcet_miss(PID p)
{
LEVEL l = proc_table[p].task_level;
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
 
lev->wcet_miss[p] = 0;
return 0;
}
 
int FEDFSTAR_setbudget(LEVEL l, PID p, int budget)
{
 
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
lev->budget[p] = budget;
 
return 0;
 
}
 
int FEDFSTAR_getbudget(LEVEL l, PID p)
{
 
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
 
return lev->budget[p];
 
}
 
void FEDFSTAR_set_nopreemtive_current(LEVEL l) {
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
lev->flag[lev->activated]|=FEDFSTAR_FLAG_NOPREEMPT;
}
 
void FEDFSTAR_unset_nopreemtive_current(LEVEL l) {
 
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
 
lev->flag[lev->activated]&=~FEDFSTAR_FLAG_NOPREEMPT;
}
int FEDFSTAR_budget_has_thread(LEVEL l, int budget)
{
 
FEDFSTAR_level_des *lev = (FEDFSTAR_level_des *)(level_table[l]);
int i;
 
for(i = 0; i< MAX_PROC; i++)
if (lev->budget[i] == budget) return 1;
 
return 0;
 
}
/shark/trunk/ports/first/modules/cbsnhstar.c
0,0 → 1,787
/*
* 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
*/
 
/*
* Copyright (C) 2002 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 "cbsnhstar.h"
#include "ll/i386/64bit.h"
#include <tracer.h>
#include <fsf.h>
 
/*
* DEBUG stuffs begin
*/
//#define CBSNHSTAR_DEBUG
#ifdef CBSNHSTAR_DEBUG
 
static __inline__ void fake_printf(char *fmt, ...) {}
 
#define cbsnhstar_printf kern_printf
#define cbsnhstar_printf2 kern_printf
#define cbsnhstar_printf3 kern_printf
 
//#define cbsnhstar_printf fake_printf
//#define cbsnhstar_printf2 fake_printf
//#define cbsnhstar_printf3 fake_printf
 
#endif
/*
* DEBUG stuffs end
*/
 
/* this structure contains the status for a single budget */
struct budget_struct {
TIME Q; /* budget */
TIME T; /* period */
TIME D; /* deadline */
 
/* Negotiate parameter */
TIME N_Q; /* Negotiate budget */
TIME N_T; /* Negotiate Period */
TIME N_D; /* Negotiate Deadline */
 
 
struct timespec dline; /* deadline */
struct timespec replenish; /* server period */
 
int avail; /* current budget */
LEVEL l; /* Current CBSNHSTAR level */
int loc_sched_id; /* Local scheduler id */
LEVEL loc_sched_level; /* Local scheduler level */
PID current; /* the task currently put in execution */
int flags;
int recharge_count; /* count of the recharge when avail <=0 */
 
IQUEUE tasks; /* a FIFO queue for the tasks handled
using the budget */
 
int negotiation;
 
};
 
#define CBSNHSTAR_NOACTIVE 0
#define CBSNHSTAR_ACTIVE 1
 
 
 
typedef struct {
level_des l; /* the standard level descriptor */
 
struct budget_struct *b; /* the budgets! */
int n; /* the maximum index for the budgets */
int freebudgets; /* number of free budgets; starts from n */
 
int tb[MAX_PROC]; /* link task->budget (used in guest_end) */
 
bandwidth_t U; /*+ the used bandwidth by the server +*/
 
int cap_lev;
struct timespec cap_lasttime;
 
int negotiation_in_progress;
 
LEVEL scheduling_level;
 
} CBSNHSTAR_level_des;
 
 
 
static void CBSNHSTAR_activation(CBSNHSTAR_level_des *lev,
PID p,
struct timespec *acttime)
{
JOB_TASK_MODEL job;
struct budget_struct *b = &lev->b[lev->tb[p]];
/* we have to check if the deadline and the wcet are correct before
activating a new task or an old task... */
 
/* we have to check if the deadline and the wcet are correct before
* activating a new task or an old task... */
 
/* check 1: if the deadline is before than the actual scheduling time */
 
/* check 2: if ( avail_time >= (cbs_dline - acttime)* (wcet/period) )
* (rule 7 in the CBSNH article!) */
TIME t;
struct timespec t2,t3;
mul32div32to32(b->D,b->avail,b->Q,t);
t3.tv_sec = t / 1000000;
t3.tv_nsec = (t % 1000000) * 1000;
SUBTIMESPEC(&b->dline, acttime, &t2);
 
TRACER_LOGEVENT(FTrace_EVT_server_active,0,(unsigned int)b);
 
if (/* 1 */ TIMESPEC_A_LT_B(&b->dline, acttime) ||
/* 2 */ TIMESPEC_A_GT_B(&t3, &t2) ) {
if (b->negotiation) {
lev->negotiation_in_progress--;
b->negotiation=0;
b->Q=b->N_Q;
b->T=b->N_T;
b->D=b->N_D;
b->N_Q=0;
b->N_T=0;
b->N_D=0;
}
b->recharge_count=0;
TIMESPEC_ASSIGN(&b->replenish, acttime);
ADDUSEC2TIMESPEC(b->T, &b->replenish);
TIMESPEC_ASSIGN(&b->dline, acttime);
ADDUSEC2TIMESPEC(b->D, &b->dline);
b->avail=b->Q;
b->flags=CBSNHSTAR_ACTIVE;
kern_printf("((1)ds sec %ld, us %ld)", b->dline.tv_sec, b->dline.tv_nsec/1000);
}
 
/* record the current task inserted in the master module */
b->current = p;
 
job_task_default_model(job, b->dline);
job_task_def_noexc(job);
level_table[ lev->scheduling_level ]->
private_insert(lev->scheduling_level, p, (TASK_MODEL *)&job);
 
}
 
static void CBSNHSTAR_account_capacity(CBSNHSTAR_level_des *lev, PID p)
{
struct timespec ty;
TIME tx;
struct budget_struct *b = &lev->b[lev->tb[p]];
 
if (lev->cap_lev != NIL) {
kern_event_delete(lev->cap_lev);
lev->cap_lev = NIL;
}
 
tx=0;
 
if (TIMESPEC_A_LT_B(&lev->cap_lasttime,&schedule_time)) {
SUBTIMESPEC(&schedule_time, &lev->cap_lasttime, &ty);
tx = TIMESPEC2USEC(&ty);
}
 
b->avail -= tx;
 
// #ifdef CBSNHSTAR_DEBUG
kern_printf("(CS:Cap p%d av=%d tx=%d)", p, b->avail,tx);
//#endif
/*
if (b->avail <= 0) {
b->flags = CBSNHSTAR_NOACTIVE;
TRACER_LOGEVENT(FTrace_EVT_server_exhaust,0,(unsigned int)(b));
}
 
if (TIMESPEC_A_LT_B(&b->dline, &schedule_time)) {
TIMESPEC_ASSIGN(&b->dline, &schedule_time);
ADDUSEC2TIMESPEC(b->D, &b->dline);
TIMESPEC_ASSIGN(&b->replenish, &schedule_time);
ADDUSEC2TIMESPEC(b->T, &b->replenish);
}
*/
if (b->avail <= 0) {
b->recharge_count++;
if (b->negotiation) {
lev->negotiation_in_progress--;
b->negotiation=0;
b->Q=b->N_Q;
b->T=b->N_T;
b->D=b->N_D;
 
b->N_Q=0;
b->N_T=0;
b->N_D=0;
}
TIMESPEC_ASSIGN(&b->replenish, &schedule_time);
ADDUSEC2TIMESPEC(b->T, &b->replenish);
TIMESPEC_ASSIGN(&b->dline, &schedule_time);
ADDUSEC2TIMESPEC(b->D, &b->dline);
b->avail=b->Q;
b->flags=CBSNHSTAR_ACTIVE;
kern_printf("((2)ds sec %ld, us %ld)", b->dline.tv_sec, b->dline.tv_nsec/1000);
}
}
 
 
/* The on-line guarantee is enabled only if the appropriate flag is set... */
static int CBSNHSTAR_public_guarantee(LEVEL l, bandwidth_t *freebandwidth)
{
CBSNHSTAR_level_des *lev = (CBSNHSTAR_level_des *)(level_table[l]);
 
#ifdef CBSNHSTAR_DEBUG
cbsnhstar_printf("(CS:Gua)");
#endif
 
if (*freebandwidth >= lev->U) {
*freebandwidth -= lev->U;
return 1;
}
else
return 0;
}
 
static void capacity_handler(void *l)
{
CBSNHSTAR_level_des *lev = l;
lev->cap_lev = NIL;
event_need_reschedule();
}
 
static int CBSNHSTAR_private_eligible(LEVEL l, PID p)
{
CBSNHSTAR_level_des *lev = (CBSNHSTAR_level_des *)(level_table[l]);
struct budget_struct *b = &lev->b[lev->tb[p]];
JOB_TASK_MODEL job;
 
/* we have to check if the deadline and the wcet are correct...
if the CBSNHSTAR level schedules in background with respect to others
levels, there can be the case in witch a task is scheduled by
schedule_time > CBSNHSTAR_deadline; in this case (not covered in the
article because if there is only the standard scheduling policy
this never apply) we reassign the deadline */
if ( TIMESPEC_A_LT_B(&b->dline, &schedule_time)) {
if (lev->cap_lev!=NIL) {
kern_event_delete(lev->cap_lev);
lev->cap_lev=NIL;
}
if (b->negotiation) {
lev->negotiation_in_progress--;
b->negotiation=0;
b->Q=b->N_Q;
b->T=b->N_T;
b->D=b->N_D;
b->N_Q=0;
b->N_T=0;
b->N_D=0;
}
 
/* we kill the current activation */
level_table[ lev->scheduling_level ]->
private_extract(lev->scheduling_level, p);
/* we modify the deadline ... */
kern_gettime(&b->replenish);
TIMESPEC_ASSIGN(&b->dline, &b->replenish);
ADDUSEC2TIMESPEC(b->D, &b->dline);
ADDUSEC2TIMESPEC(b->T, &b->replenish);
kern_printf("((3)ds sec %ld, us %ld)", b->dline.tv_sec, b->dline.tv_nsec/1000);
 
/* and the capacity */
b->avail = b->Q;
 
b->flags = CBSNHSTAR_ACTIVE;
 
/* Tracer */
TRACER_LOGEVENT(FTrace_EVT_server_replenish,0,(unsigned int)(b));
/* and, finally, we reinsert the task in the master level */
job_task_default_model(job, b->dline);
job_task_def_noexc(job);
level_table[ lev->scheduling_level ]->
private_insert(lev->scheduling_level, p, (TASK_MODEL *)&job);
return -1;
}
 
return 0;
 
}
 
static void CBSNHSTAR_private_insert(LEVEL l, PID p, TASK_MODEL *m)
{
/* A task has been activated for some reason. Basically, the task is
inserted in the queue if the queue is empty, otherwise the task is
inserted into the master module, and an oslib event is posted. */
 
CBSNHSTAR_level_des *lev = (CBSNHSTAR_level_des *)(level_table[l]);
BUDGET_TASK_MODEL *budget;
 
if (m->pclass != BUDGET_PCLASS ||
(m->level != 0 && m->level != l)) {
kern_raise(XINVALID_TASK, p);
return;
}
budget = (BUDGET_TASK_MODEL *)m;
 
#ifdef CBSNHSTAR_DEBUG
cbsnhstar_printf("(CS:PriIns:%d:%d", p, budget->b);
#endif
if (budget->b == -1)
return;
 
lev->tb[p] = budget->b;
 
if (lev->b[budget->b].current == NIL && lev->b[budget->b].flags ) {
/* This is the first task in the budget,
the task have to be inserted into the master module */
struct timespec t;
kern_gettime(&t);
CBSNHSTAR_activation(lev,p,&t);
} else {
/* The budget is not empty, another task is already into the
master module, so the task is inserted at the end of the budget
queue */
iq_insertlast(p,&lev->b[budget->b].tasks);
}
 
#ifdef CBSNHSTAR_DEBUG
cbsnhstar_printf(")");
#endif
 
}
 
static void CBSNHSTAR_private_extract(LEVEL l, PID p)
{
CBSNHSTAR_level_des *lev = (CBSNHSTAR_level_des *)(level_table[l]);
 
#ifdef CBSNHSTAR_DEBUG
kern_printf("(CS:Ext:%d)", p);
#endif
 
/* a task is removed from execution for some reasons. It must be
that it is the first in its budget queue (only the first task in
a budget queue is put into execution!) */
 
/* remove the task from execution (or from the ready queue) */
if (lev->b[lev->tb[p]].current == p) {
//struct timespec t;
 
CBSNHSTAR_account_capacity(lev,p);
/* remove the task from the master module */
level_table[ lev->scheduling_level ]->
private_extract(lev->scheduling_level, p);
 
/* check if the buffer has someone else to schedule */
if (iq_query_first(&lev->b[lev->tb[p]].tasks) == NIL) {
/* the buffer has no tasks! */
lev->b[lev->tb[p]].current = NIL;
}
else if (lev->b[lev->tb[p]].flags) {
/* if so, insert the new task into the master module */
PID n;
struct timespec t;
kern_gettime(&t);
n = iq_getfirst(&lev->b[lev->tb[p]].tasks);
CBSNHSTAR_activation(lev,n,&t); // it modifies b[lev->tb[p]].current
}
else
lev->b[lev->tb[p]].current=NIL;
 
}
else {
iq_extract(p, &lev->b[lev->tb[p]].tasks);
}
}
 
static void CBSNHSTAR_private_dispatch(LEVEL l, PID p, int nostop)
{
CBSNHSTAR_level_des *lev = (CBSNHSTAR_level_des *)(level_table[l]);
struct timespec ty;
 
#ifdef CBSNHSTAR_DEBUG
kern_printf("(CS:Dsp:%d)", p);
#endif
 
/* the current task (that is the only one inserted in the master module
for the corresponding budget) is dispatched. Note that the current
task is not inserted in any FIFO queue, so the task does not have to
be extracted! */
 
/* ... then, we dispatch it to the master level */
if (!nostop)
level_table[ lev->scheduling_level ]->
private_dispatch(lev->scheduling_level,p,nostop);
 
/* ...and finally, we have to post a capacity event */
TIMESPEC_ASSIGN(&ty, &schedule_time);
TIMESPEC_ASSIGN(&lev->cap_lasttime, &schedule_time);
ADDUSEC2TIMESPEC(lev->b[lev->tb[exec]].avail,&ty);
lev->cap_lev = kern_event_post(&ty,capacity_handler, lev);
 
}
 
static void CBSNHSTAR_private_epilogue(LEVEL l, PID p)
{
CBSNHSTAR_level_des *lev = (CBSNHSTAR_level_des *)(level_table[l]);
struct budget_struct *b;
int skip_epilog;
skip_epilog = 0;
 
#ifdef CBSNHSTAR_DEBUG
kern_printf("(CS:Epi:%d)",p);
#endif
 
if (p==exec) b = &lev->b[lev->tb[p]];
else if (lev->tb[exec]!=NIL) {
b = &lev->b[lev->tb[exec]];
p=exec;
skip_epilog=1;
}
else return;
CBSNHSTAR_account_capacity(lev,p);
 
// L'evento di capacità va cancellato perchè sarà ripristinato nella successiva dispatch
/* we have to check if the capacity is still available */
// if (b->flags) {
/* there is capacity available, maybe it is simply a preemption;
the task have to return to the ready queue */
if (!skip_epilog)
level_table[ lev->scheduling_level ]->
private_epilogue(lev->scheduling_level,p);
//} else {
/* we kill the current activation */
//level_table[ lev->scheduling_level ]->
// private_extract(lev->scheduling_level, p);
//iq_insertfirst(p, &b->tasks);
//b->current = NIL;
//}
}
 
/* Registration functions }*/
 
/*+ Registration function:
int flags the init flags ... see CBSNHSTAR.h +*/
LEVEL CBSNHSTAR_register_level(int n, LEVEL master)
{
LEVEL l; /* the level that we register */
CBSNHSTAR_level_des *lev; /* for readableness only */
PID i; /* a counter */
 
printk("CBSNHSTAR_register_level\n");
 
/* request an entry in the level_table */
l = level_alloc_descriptor(sizeof(CBSNHSTAR_level_des));
 
lev = (CBSNHSTAR_level_des *)level_table[l];
 
/* fill the standard descriptor */
lev->l.private_insert = CBSNHSTAR_private_insert;
lev->l.private_extract = CBSNHSTAR_private_extract;
lev->l.private_eligible = CBSNHSTAR_private_eligible;
lev->l.private_dispatch = CBSNHSTAR_private_dispatch;
lev->l.private_epilogue = CBSNHSTAR_private_epilogue;
 
lev->l.public_guarantee = CBSNHSTAR_public_guarantee;
 
/* fill the CBSNHSTAR descriptor part */
lev->b = (struct budget_struct *)kern_alloc(sizeof(struct budget_struct)*n);
 
for (i=0; i<n; i++) {
lev->b[i].Q = 0;
lev->b[i].T = 0;
lev->b[i].D = 0;
 
lev->b[i].N_Q = 0;
lev->b[i].N_T = 0;
lev->b[i].N_D = 0;
 
NULL_TIMESPEC(&lev->b[i].dline);
NULL_TIMESPEC(&lev->b[i].replenish);
lev->b[i].avail = 0;
lev->b[i].current = -1;
lev->b[i].flags = CBSNHSTAR_ACTIVE;
lev->b[i].l=l;
lev->b[i].negotiation = 0;
lev->b[i].recharge_count=0;
iq_init(&lev->b[i].tasks, /* &freedesc */NULL, 0);
}
 
lev->n = n;
lev->freebudgets = 0;
 
for (i=0; i<MAX_PROC; i++)
lev->tb[i] = NIL;
 
lev->U = 0;
lev->cap_lev = NIL;
NULL_TIMESPEC(&lev->cap_lasttime);
lev->scheduling_level = master;
 
return l;
 
}
 
int CBSNHSTAR_setbudget(LEVEL l, TIME Q, TIME T, TIME D, LEVEL local_scheduler_level, int scheduler_id)
{
CBSNHSTAR_level_des *lev = (CBSNHSTAR_level_des *)(level_table[l]);
int r;
 
// #ifdef CBSNHSTAR_DEBUG
kern_printf("(CS:SetBud)");
//#endif
 
for (r = 0; r < lev->n; r++)
if (lev->b[r].Q == 0) break;
 
if (r != lev->n) {
bandwidth_t b;
mul32div32to32(MAX_BANDWIDTH, Q, T, b);
/* b = (MAX_BANDWIDTH / T) * Q; */
/* really update lev->U, checking an overflow... */
if (Q< T /* && MAX_BANDWIDTH - lev->U > b */) {
lev->U += b;
lev->freebudgets++;
lev->b[r].Q = Q;
lev->b[r].T = T;
lev->b[r].D = D;
 
lev->b[r].N_Q = 0;
lev->b[r].N_T = 0;
lev->b[r].N_D = 0;
 
lev->b[r].avail = Q;
lev->b[r].flags = CBSNHSTAR_ACTIVE;
lev->b[r].negotiation=0;
lev->b[r].loc_sched_id = scheduler_id;
lev->b[r].loc_sched_level = local_scheduler_level;
lev->b[r].recharge_count=0;
return r;
}
else
return -2;
}
else
return -1;
}
 
int CBSNHSTAR_get_remain_capacity(LEVEL l, int budget)
{
struct timespec actual,ty;
int tx;
CBSNHSTAR_level_des *lev = (CBSNHSTAR_level_des *)(level_table[l]);
kern_gettime(&actual);
SUBTIMESPEC(&actual, &schedule_time, &ty);
tx = TIMESPEC2USEC(&ty);
// the remain capacity is from the first dispatch so is less then
// actual capacity
return (lev->b[budget].avail-tx);
 
}
 
int CBSNHSTAR_removebudget(LEVEL l, int budget)
{
 
CBSNHSTAR_level_des *lev = (CBSNHSTAR_level_des *)(level_table[l]);
 
bandwidth_t b;
b = (MAX_BANDWIDTH / lev->b[budget].T) * lev->b[budget].Q;
 
lev->U -= b;
 
lev->b[budget].Q = 0;
lev->b[budget].T = 0;
lev->b[budget].D = 0;
 
lev->b[budget].N_Q = 0;
lev->b[budget].N_T = 0;
lev->b[budget].N_D = 0;
 
lev->b[budget].recharge_count=0;
NULL_TIMESPEC(&lev->b[budget].dline);
NULL_TIMESPEC(&lev->b[budget].replenish);
lev->b[budget].avail = 0;
lev->b[budget].current = -1;
lev->b[budget].negotiation=0;
lev->b[budget].flags = CBSNHSTAR_ACTIVE;
 
return 0;
 
}
 
int CBSNHSTAR_adjust_budget(LEVEL l, TIME Q, TIME T, TIME D, int budget)
{
 
CBSNHSTAR_level_des *lev = (CBSNHSTAR_level_des *)(level_table[l]);
 
lev->b[budget].N_Q = Q;
lev->b[budget].N_T = T;
lev->b[budget].N_D = D;
 
if (lev->b[budget].current!=NIL && !(lev->b[budget].Q==Q && lev->b[budget].T==T)) {
lev->b[budget].N_Q = Q;
lev->b[budget].N_T = T;
lev->b[budget].N_D = D;
if (!lev->b[budget].negotiation) {
lev->negotiation_in_progress++;
lev->b[budget].negotiation=1;
}
} else {
lev->b[budget].Q = Q;
lev->b[budget].T = T;
lev->b[budget].D = D;
}
 
return 0;
 
}
 
int CBSNHSTAR_getbudgetinfo(LEVEL l, TIME *Q, TIME *T, TIME *D, int budget)
{
 
CBSNHSTAR_level_des *lev = (CBSNHSTAR_level_des *)(level_table[l]);
*Q = lev->b[budget].Q;
*T = lev->b[budget].T;
*D = lev->b[budget].D;
 
return 0;
 
}
 
int CBSNHSTAR_get_last_reclaiming(LEVEL l, PID p)
{
 
return 0;
 
}
 
int CBSNHSTAR_is_active(LEVEL l, int budget)
{
CBSNHSTAR_level_des *lev = (CBSNHSTAR_level_des *)(level_table[l]);
 
return lev->b[budget].flags;
 
}
 
int CBSNHSTAR_get_local_scheduler_level_from_budget(LEVEL l, int budget)
{
CBSNHSTAR_level_des *lev = (CBSNHSTAR_level_des *)(level_table[l]);
 
return lev->b[budget].loc_sched_level;
 
}
 
int CBSNHSTAR_get_local_scheduler_level_from_pid(LEVEL l, PID p)
{
CBSNHSTAR_level_des *lev = (CBSNHSTAR_level_des *)(level_table[l]);
 
return lev->b[lev->tb[p]].loc_sched_level;
 
}
 
int CBSNHSTAR_get_local_scheduler_id_from_budget(LEVEL l, int budget)
{
CBSNHSTAR_level_des *lev = (CBSNHSTAR_level_des *)(level_table[l]);
 
return lev->b[budget].loc_sched_id;
 
}
 
int CBSNHSTAR_get_local_scheduler_id_from_pid(LEVEL l, PID p)
{
CBSNHSTAR_level_des *lev = (CBSNHSTAR_level_des *)(level_table[l]);
 
return lev->b[lev->tb[p]].loc_sched_id;
 
}
 
void CBSNHSTAR_disable_server(LEVEL l, int budget)
{
CBSNHSTAR_level_des *lev = (CBSNHSTAR_level_des *)(level_table[l]);
int avail_budget;
int spare;
 
/* force a hard reservation event */
avail_budget=lev->b[lev->tb[exec]].avail;
lev->b[lev->tb[exec]].flags = CBSNHSTAR_NOACTIVE;
//kern_printf("(CBSNH DS %d)", exec);
/* save the unused capacity */
spare=avail_budget+lev->b[lev->tb[exec]].avail;
if (spare<=0) spare=0;
}
 
int CBSNHSTAR_getrecharge_number(LEVEL l, int budget) {
 
CBSNHSTAR_level_des *lev = (CBSNHSTAR_level_des *)(level_table[l]);
//kern_printf("CBSNH:rn:budget:%d:rnumber:%d", budget, lev->b[budget].recharge_count);
 
return lev->b[budget].recharge_count;
 
}
 
int CBSNHSTAR_get_renegotiation_status(LEVEL l, int budget)
{
CBSNHSTAR_level_des *lev = (CBSNHSTAR_level_des *)(level_table[l]);
if (lev->negotiation_in_progress) return 1;
else return 0;
}
 
bandwidth_t CBSNHSTAR_get_bandwidth(LEVEL l)
{
CBSNHSTAR_level_des *lev = (CBSNHSTAR_level_des *)(level_table[l]);
return lev->U;
 
}
 
void CBSNHSTAR_getdeadline(LEVEL l, int budget, struct timespec *t) {
CBSNHSTAR_level_des *lev = (CBSNHSTAR_level_des *)(level_table[l]);
 
TIMESPEC_ASSIGN(t,&lev->b[budget].dline);
}