From 3909278d5cb6c06907df1c542a60e09e2ded4e37 Mon Sep 17 00:00:00 2001 From: "Bjoern B. Brandenburg" Date: Sun, 7 Oct 2007 01:41:46 -0400 Subject: adaptive: introduce fixed point math Introduces fixed point math header stuff and start of predictor support in sched_adaptive.c --- include/linux/fpmath.h | 79 ++++++++++++++++++++++++++++++++++++++++++ include/linux/rt_param.h | 41 ++++++++++++++++------ include/linux/sched_adaptive.h | 34 ++++++++++++++++++ 3 files changed, 143 insertions(+), 11 deletions(-) create mode 100644 include/linux/fpmath.h create mode 100644 include/linux/sched_adaptive.h (limited to 'include/linux') diff --git a/include/linux/fpmath.h b/include/linux/fpmath.h new file mode 100644 index 0000000000..73d89ba210 --- /dev/null +++ b/include/linux/fpmath.h @@ -0,0 +1,79 @@ +#ifndef __FP_MATH_H__ +#define __FP_MATH_H__ + +#define FP_SHIFT 16 +#define ROUND_BIT (FP_SHIFT - 1) +#define ONE FP(1) + +#define _fp(x) ((fp_t) {x}) + +static inline fp_t FP(long x) +{ + return _fp(((long long) x) << FP_SHIFT); +} + +static inline long _floor(fp_t x) +{ + return x.val >> FP_SHIFT; +} + +/* FIXME: negative rounding */ +static inline long _round(fp_t x) +{ + return _floor(x) + ((x.val >> ROUND_BIT) & 1); +} + +/* divide two integers to obtain a fixed point value */ +static inline fp_t _frac(long a, long b) +{ + return _fp(FP(a).val / (b)); +} + +/* multiply two fixed point values */ +static inline fp_t _mul(fp_t a, fp_t b) +{ + return _fp((a.val * b.val) >> FP_SHIFT); +} + +static inline fp_t _div(fp_t a, fp_t b) +{ + return _fp(FP(a.val).val / b.val); +} + +static inline fp_t _add(fp_t a, fp_t b) +{ + return _fp(a.val + b.val); +} + +static inline fp_t _sub(fp_t a, fp_t b) +{ + return _fp(a.val - b.val); +} + +static inline fp_t _neg(fp_t x) +{ + return _fp(-x.val); +} + +static inline int _leq(fp_t a, fp_t b) +{ + return a.val <= b.val; +} + +static inline int _geq(fp_t a, fp_t b) +{ + return a.val >= b.val; +} + +static inline int _lt(fp_t a, fp_t b) +{ + return a.val < b.val; +} + +static inline int _gt(fp_t a, fp_t b) +{ + return a.val > b.val; +} + + +#endif diff --git a/include/linux/rt_param.h b/include/linux/rt_param.h index 69aa781a40..c275565835 100644 --- a/include/linux/rt_param.h +++ b/include/linux/rt_param.h @@ -23,13 +23,26 @@ typedef struct rt_param { task_class_t class; } rt_param_t; +/* fixed point wrapper to force compiler + * errors in case of misuse of a fixed point value + */ +typedef struct +{ + long long val; +} fp_t; + typedef struct { - unsigned long exec_cost; + fp_t weight; unsigned long period; - /* fixed point */ - unsigned long utility; + fp_t value; } service_level_t; +typedef struct { + fp_t error; + fp_t estimate; + fp_t accumulated; +} predictor_state_t; + typedef struct { /* when will this task be release the next time? */ jiffie_t release; @@ -111,14 +124,14 @@ typedef struct task_rt_param { * section support. * TODO: What happens on fork? */ - __user short* np_flag; + __user short* np_flag; /* For the FMLP under PSN-EDF, it is required to make the task * non-preemptive from kernel space. In order not to interfere with * user space, this counter indicates the kernel space np setting. * kernel_np > 0 => task is non-preemptive */ - unsigned int kernel_np; + unsigned int kernel_np; /* put information for feedback control stuff and * information about the performance of the task here @@ -126,15 +139,15 @@ typedef struct task_rt_param { struct { /* How many non-tardy jobs since the last tardy job? */ unsigned int nontardy_jobs_ctr; - long accumulated_error; + long accumulated_error; } stats; - rt_times_t times; + rt_times_t times; /* This is currently only used by the PFAIR code * and a prime candidate for cleanup. */ - rt_times_t backup; + rt_times_t backup; /* This field can be used by plugins to store where the task * is currently scheduled. It is the responsibility of the @@ -155,9 +168,13 @@ typedef struct task_rt_param { /* Adaptive support. Adaptive tasks will store service levels * in this (dynamically allocated) structure. */ - service_level_t* service_level; - unsigned int no_service_levels; - unsigned int cur_service_level; + service_level_t* service_level; + unsigned int no_service_levels; + unsigned int cur_service_level; + + /* Adaptive support. Store state for weight estimation. + */ + predictor_state_t predictor_state; } task_rt_param_t; /* Possible RT flags */ @@ -180,6 +197,8 @@ typedef struct task_rt_param { #define get_deadline(t) ((t)->rt_param.times.deadline) #define get_class(t) ((t)->rt_param.basic_params.class) +#define get_est_weight(t) ((t)->rt_param.predictor_state.estimate) + #define is_realtime(t) ((t)->rt_param.is_realtime) #define is_subject_to_srp(t) ((t)->rt_param.subject_to_srp) #define is_hrt(t) \ diff --git a/include/linux/sched_adaptive.h b/include/linux/sched_adaptive.h new file mode 100644 index 0000000000..eac2f90652 --- /dev/null +++ b/include/linux/sched_adaptive.h @@ -0,0 +1,34 @@ +#ifndef __ADAPTIVE_H__ +#define __ADAPTIVE_H__ + +static inline unsigned long ideal_allocation(fp_t weight, unsigned long delta_t) +{ + return _floor(_mul(weight, FP(delta_t))); +} + +/* this makes a whole bunch of linearity assumptions */ +static inline fp_t weight_transfer(fp_t from_val, fp_t to_val, + fp_t slope, fp_t intercept, fp_t act_weight) +{ + fp_t rel_from, rel_to; + rel_from = _add(intercept, _mul(from_val, slope)); + rel_to = _add(intercept, _mul(to_val, slope)); + return _div(_mul(act_weight, rel_to), rel_from); +} + +static inline void update_estimate(predictor_state_t *state, fp_t actual_weight, + fp_t a, fp_t b, fp_t c) +{ + fp_t err, new, delta_err; + + err = _sub(actual_weight, state->estimate); + state->accumulated = _add(state->accumulated, err); + delta_err = _sub(err, state->error); + new = _add(_add(_mul(a, err), + _mul(b, state->accumulated)), + _mul(c, delta_err)); + state->estimate = new; + state->error = err; +} + +#endif -- cgit v1.2.2