/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); |
} |