Implement hash-based EDF tie-breaking.wip-better-break

Added kernel config option to perform deadline tie-breaking
by comparing the hashes of (pid, job#) pairs. Hashing ensures
that the same task is not repeatedly victimized in overload
conditions in systems where deadline ties are common (say,
several synchronous media players).

2 files changed, 82 insertions, 2 deletions

diff --git a/litmus/Kconfig b/litmus/Kconfig
index 68459d4dca41..7de5b81d5d0b 100644
--- a/litmus/Kconfig
+++ b/litmus/Kconfig
@@ -79,6 +79,45 @@ config SCHED_CPU_AFFINITY
 
           Say Yes if unsure.
 
+choice
+        prompt "EDF Tie-Break Behavior"
+        default EDF_HASH_TIE_BREAK
+        help
+          Allows the configuration of tie-breaking behavior when the deadlines
+          of two EDF-scheduled tasks are equal.
+
+config EDF_HASH_TIE_BREAK
+        bool "Hash-based Tie Breaks"
+        help
+          Break ties between two jobs, A and B, with equal deadlines by using a
+          uniform hash; i.e.: hash(A.pid, A.job_num) < hash(B.pid, B.job_num).
+
+          This is particularly useful in overloaded systems that process
+          synchronous task sets of tasks with equal relative deadlines (ex.
+          media players). Hashing reduces the likelihood that the same task
+          loses repeated tie-break rounds, always suffering worst-case
+          response time.
+
+          Warning: It may be harder to reproduce bugs since PIDs change each
+            time a task is run.
+
+          NOTES:
+                * This feature can increase response-time jitter, but should improve
+                  average case response time.
+                * Tie-break falls back to PIDs in unlikely event two hashes collide.
+
+config EDF_PID_TIE_BREAK
+        bool "PID-based Tie Breaks"
+        help
+          Break ties based upon OS-assigned process IDs. Use this option if
+          required by algorithm's real-time analysis or per-task response-time
+          jitter must be minimized in overload conditions.
+
+          NOTES:
+                * This tie-breaking method was default in Litmus 2012.2 and before.
+
+endchoice
+
 endmenu
 
 menu "Tracing"
diff --git a/litmus/edf_common.c b/litmus/edf_common.c
index 9b44dc2d8d1e..a603d06afe15 100644
--- a/litmus/edf_common.c
+++ b/litmus/edf_common.c
@@ -14,6 +14,35 @@
 
 #include <litmus/edf_common.h>
 
+#include <linux/hash.h>
+
+#ifdef CONFIG_EDF_HASH_TIE_BREAK
+static inline long edf_hash(struct task_struct *t)
+{
+        long key;
+        /* pid is 32 bits, so normally we would shove that into the
+         * upper 32-bits and and put the job number in the bottom
+         * and hash the 64-bit number with hash_64(). Sadly,
+         * in testing, hash_64() doesn't distribute keys were the
+         * upper bits are close together (as would be the case with
+         * pids) and job numbers are equal (as would be the case with
+         * synchronous task sets with all relative deadlines equal).
+         *
+         * A 2006 Linux patch proposed the following solution
+         * (but for some reason it wasn't accepted...).
+         *
+         * At least this workaround works for 32-bit systems as well.
+         */
+
+        /* This would be nice, but hash_64() has problems.
+        key = ((long)t->pid << 32) | ((long)tsk_rt(t)->job_params.job_no & 0xFFFFFFFF);
+        return hash_64(key, 0);
+        */
+
+        return hash_32(hash_32((u32)tsk_rt(t)->job_params.job_no, 32) ^ t->pid, 32);
+}
+#endif
+
 /* edf_higher_prio -  returns true if first has a higher EDF priority
  *                    than second. Deadline ties are broken by PID.
  *
@@ -25,6 +54,10 @@ int edf_higher_prio(struct task_struct* first,
         struct task_struct *first_task = first;
         struct task_struct *second_task = second;
 
+#ifdef CONFIG_EDF_HASH_TIE_BREAK
+        long fhash, shash;
+#endif
+
         /* There is no point in comparing a task to itself. */
         if (first && first == second) {
                 TRACE_TASK(first,
@@ -63,7 +96,6 @@ int edf_higher_prio(struct task_struct* first,
 
 #endif
 
-
         return !is_realtime(second_task)  ||
 
                 /* is the deadline of the first task earlier?
@@ -75,13 +107,22 @@ int edf_higher_prio(struct task_struct* first,
                  * Then break by PID.
                  */
                 (get_deadline(first_task) == get_deadline(second_task) &&
+#ifdef CONFIG_EDF_HASH_TIE_BREAK
+                        /* assignment within less-than compare is intentional */
+                        ((fhash = edf_hash(first_task)) < (shash = edf_hash(second_task)) ||
+                                (fhash == shash &&
+#endif          
                 (first_task->pid < second_task->pid ||
 
                 /* If the PIDs are the same then the task with the inherited
                  * priority wins.
                  */
                 (first_task->pid == second_task->pid &&
-                 !second->rt_param.inh_task)));
+                 !second->rt_param.inh_task))
+#ifdef CONFIG_EDF_HASH_TIE_BREAK
+                ))
+#endif
+                        );
 }
 
 int edf_ready_order(struct bheap_node* a, struct bheap_node* b)