PFAIR scheduling added

3 files changed, 149 insertions, 19 deletions

diff --git a/include/linux/pfair_common.h b/include/linux/pfair_common.h
new file mode 100644
index 0000000000..67e18c601a
--- /dev/null
+++ b/include/linux/pfair_common.h
@@ -0,0 +1,40 @@
+/* PFAIR common data structures and utility functions shared by all PFAIR 
+ * based scheduler plugins
+ */
+
+#ifndef __UNC_PFAIR_COMMON_H__
+#define __UNC_PFAIR_COMMON_H__
+
+#include <linux/queuelock.h>
+#include <linux/cpumask.h>
+
+typedef struct _pfair_domain {
+        /* Global lock to protect the data structures */
+        queuelock_t                     pfair_lock;
+        /* runnable rt tasks are in here */
+        struct list_head                ready_queue; 
+
+        /* real-time tasks waiting for release are in here */
+        struct list_head                release_queue;
+        
+        /*  CPU's in the domain */
+        cpumask_t domain_cpus;
+
+} pfair_domain_t;
+
+#define next_ready(pfair) \
+        (list_entry((pfair)->ready_queue.next, struct task_struct, rt_list))
+void pfair_domain_init(pfair_domain_t *pfair);
+void  pfair_add_ready(pfair_domain_t* pfair, struct task_struct *new);
+struct task_struct* __pfair_take_ready(pfair_domain_t* pfair);
+void pfair_add_release(pfair_domain_t* pfair, struct task_struct *task);
+void pfair_try_release_pending(pfair_domain_t* pfair);
+void __pfair_prepare_new_release(struct task_struct *t, jiffie_t start);
+
+void pfair_prepare_next_job(struct task_struct *t);
+void pfair_prepare_next_subtask(struct task_struct *t);
+
+void pfair_prepare_new_releases(pfair_domain_t *pfair, jiffie_t start);
+
+#endif
+
diff --git a/include/linux/pfair_math.h b/include/linux/pfair_math.h
new file mode 100644
index 0000000000..6eef12433c
--- /dev/null
+++ b/include/linux/pfair_math.h
@@ -0,0 +1,75 @@
+/*      PFAIR Mathematical functions */
+#ifndef __UNC_PFAIR_MATH_H__
+#define __UNC_PFAIR_MATH_H__
+
+#include <linux/rt_param.h>
+#include <asm/div64.h>
+#include <linux/litmus.h>
+#include <linux/sched.h>
+
+/*
+* This file defines  mathematical functions "ceiling", "floor",
+* and PFAIR specific functions for computing the release and
+* the deadline of a subtask, as well as tie breakers:
+* b-bit and group deadline.
+*/
+static inline quantum_t FLOOR(quantum_t a, unsigned long b)
+{
+        BUG_ON( b == 0);
+        do_div(a, b);
+        return a;       
+}
+static inline quantum_t CEIL(quantum_t a, unsigned long  b)
+{
+        quantum_t t = FLOOR(a, b);
+        return (quantum_t)((t * b == a)?t:(t + 1));
+}
+
+
+/*
+*       invariant - i-1=get_passed_quanta(t)
+*
+*       release time of i-th subtask of j-th job is
+*       r_{ij}+\lfloor i-1/wt(T) \rfloor
+*       This operation should be robust to wrap-around
+*       so we can compare the result with jiffies safely
+*/
+static inline quantum_t release_time(struct task_struct * t)
+{
+        quantum_t e = get_exec_cost(t);
+        quantum_t p = get_rt_period(t);
+        return FLOOR((get_passed_quanta(t)) * p, e);
+}
+/*
+*       deadline time of i-th subtask of j-th job is
+*       r_{ij}+\lceil i/wt(T) \rceil
+*       This operation should be robust to wrap-around
+*       so we can compare the result with jiffies safely
+*/
+static inline quantum_t pfair_deadline(struct task_struct * t)
+{
+        quantum_t e = get_exec_cost(t);
+        quantum_t p = get_rt_period(t);
+        return CEIL((get_passed_quanta(t) + 1) * p, e);
+}
+/*      In PFAIR b-bit is defined as 
+*       \lceil i/wt(T) \rceil-\lfloor i/wt(T) \rfloor
+*/
+static inline int b_bit(struct task_struct *t)
+{
+        quantum_t e = get_exec_cost(t);
+        quantum_t p = get_rt_period(t);
+        return CEIL((get_passed_quanta(t) + 1) * p, e)-
+                FLOOR((get_passed_quanta(t) + 1)* p, e);
+}
+/*
+*       Group deadline 
+*/
+static inline quantum_t group_deadline(struct task_struct * t)
+{
+        quantum_t p = get_rt_period(t);
+        quantum_t e = get_exec_cost(t);
+        return CEIL(CEIL(CEIL((get_passed_quanta(t)+1)*p, e)*(p-e), p)*p, p-e);
+}
+
+#endif /*       __UNC_PFAIR_MATH_H__    */
diff --git a/include/linux/rt_param.h b/include/linux/rt_param.h
index 1247a2ab22..0c5facd005 100644
--- a/include/linux/rt_param.h
+++ b/include/linux/rt_param.h
@@ -21,6 +21,30 @@ typedef struct rt_param {
         task_class_t    class;
 } rt_param_t;
 
+typedef struct {
+        /* when will this task be release the next time? */
+        jiffie_t        release;
+        /* time instant the last job was released  */
+        jiffie_t        last_release;
+        /* what is the current deadline? */
+        jiffie_t        deadline;
+        /* b-bit tie breaker for PFAIR, it is ignored in EDF */
+        int             b_bit;
+        /* group deadline tie breaker, it is ignored in EDF */
+        jiffie_t        group_deadline;
+        /* how long has this task executed so far? 
+         * In case of capacity sharing a job completion cannot be
+         * detected by checking time_slice == 0 as the job may have
+         * executed while using another capacity. Use this counter
+         * to keep track of the time spent on a CPU by a job.
+         *
+         * In other words: The number of consumed quanta since the
+         *                  last job release.
+         */
+        unsigned int    exec_time;
+} in_times_t;
+
+
 /*      RT task parameters for scheduling extensions    
  *      These parameters are inherited during clone and therefore must
  *      be explicitly set up before the task set is launched.
@@ -32,25 +56,6 @@ typedef struct task_rt_param {
         rt_param_t              basic_params;
         /* is the task sleeping? */
         unsigned int            flags;
-        struct {
-                /* when will this task be release the next time? */
-                jiffie_t        release;
-                /* time instant the last job was released  */
-                jiffie_t        last_release;
-                /* what is the current deadline? */
-                jiffie_t        deadline;
-
-                /* how long has this task executed so far? 
-                 * In case of capacity sharing a job completion cannot be
-                 * detected by checking time_slice == 0 as the job may have
-                 * executed while using another capacity. Use this counter
-                 * to keep track of the time spent on a CPU by a job.
-                 *
-                 * In other words: The number of consumed quanta since the
-                 *                  last job release.
-                 */
-                unsigned int    exec_time;
-        } times;
         
         /* put information for feedback control stuff and 
          * information about the performance of the task here
@@ -59,6 +64,9 @@ typedef struct task_rt_param {
                 /* How many non-tardy jobs since the last tardy job? */
                 unsigned int    nontardy_jobs_ctr;
         } stats;
+        
+        in_times_t times;
+        in_times_t backup;
 
         /* is this task under control of litmus?
          *
@@ -102,6 +110,9 @@ memset(&(t)->rt_param,0, sizeof(struct task_rt_param))
 #define get_last_release_time(t)   ((t)->rt_param.times.last_release)
 #define set_last_release_time(t,r) ((t)->rt_param.times.last_releasee=(r))
 
+#define get_release(t) ((t)->rt_param.times.release)
+#define set_release(t,r) ((t)->rt_param.times.release=(r))
+
 #define is_running(t)   ((t)->state == TASK_RUNNING)
 #define is_released(t)  (time_before_eq((t)->rt_param.times.release, jiffies))
 #define is_tardy(t)     (time_before_eq((t)->rt_param.times.deadline, jiffies))
@@ -118,4 +129,8 @@ memset(&(t)->rt_param,0, sizeof(struct task_rt_param))
         (a)->rt_param.times.release,\
         (b)->rt_param.times.release))
 
+#define backup_times(t) do { (t)->rt_patam.backup=(t)->rt_param.times; \
+                        } while(0);
+#define restore_times(t) do { (t)->rt_patam.times=(t)->rt_param.backup; \
+                        } while(0);
 #endif