EDF priority tie-breaks.

Instead of tie-breaking by PID (which is a static
priority tie-break), we can tie-break by other
job-level-unique parameters. This is desirable
because tasks are equaly affected by tardiness
since static priority tie-breaks cause tasks
with greater PID values to experience the most
tardiness.

There are four tie-break methods:

1) Lateness.  If two jobs, J_{1,i} and J_{2,j} of
tasks T_1 and T_2, respectively, have equal
deadlines, we favor the job of the task that
had the worst lateness for jobs J_{1,i-1} and
J_{2,j-1}.

Note: Unlike tardiness, lateness may be less than
zero. This occurs when a job finishes before its
deadline.

2) Normalized Lateness.  The same as #1, except
lateness is first normalized by each task's
relative deadline.  This prevents tasks with short
relative deadlines and small execution requirements
from always losing tie-breaks.

3) Hash. The job tuple (PID, Job#) is used to
generate a hash. Hash values are then compared.
A job has ~50% chance of winning a tie-break
with respect to another job.

Note: Emperical testing shows that some jobs
can have +/- ~1.5% advantage in tie-breaks.
Linux's built-in hash function is not totally
a uniform hash.

4) PIDs. PID-based tie-break used in prior
versions of Litmus.

1 files changed, 46 insertions, 0 deletions

diff --git a/litmus/Kconfig b/litmus/Kconfig
index 68459d4dca41..f2dbfb396883 100644
--- a/litmus/Kconfig
+++ b/litmus/Kconfig
@@ -79,6 +79,52 @@ config SCHED_CPU_AFFINITY
 
           Say Yes if unsure.
 
+choice
+        prompt "EDF Tie-Break Behavior"
+        default EDF_TIE_BREAK_LATENESS_NORM
+        help
+          Allows the configuration of tie-breaking behavior when the deadlines
+          of two EDF-scheduled tasks are equal.
+        
+        config EDF_TIE_BREAK_LATENESS
+        bool "Lateness-based Tie Break"
+        help
+          Break ties between two jobs, A and B, based upon the lateness of their
+          prior jobs. The job with the greatest lateness has priority. Note that
+          lateness has a negative value if the prior job finished before its
+          deadline.
+        
+        config EDF_TIE_BREAK_LATENESS_NORM
+        bool "Normalized Lateness-based Tie Break"
+        help
+          Break ties between two jobs, A and B, based upon the lateness, normalized
+          by relative deadline, of their prior jobs. The job with the greatest
+          normalized lateness has priority. Note that lateness has a negative value
+          if the prior job finished before its deadline.
+          
+          Normalized lateness tie-breaks are likely desireable over non-normalized
+          tie-breaks if the execution times and/or relative deadlines of tasks in a
+          task set vary greatly.
+        
+        config EDF_TIE_BREAK_HASH
+        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). Job
+          A has ~50% of winning a given tie-break.
+        
+        config EDF_PID_TIE_BREAK
+        bool "PID-based Tie Breaks"
+        help
+          Break ties based upon OS-assigned thread IDs. Use this option if
+          required by algorithm's real-time analysis or per-task response-time
+          jitter must be minimized.
+        
+          NOTES:
+            * This tie-breaking method was default in Litmus 2012.2 and before.
+                
+endchoice
+
 endmenu
 
 menu "Tracing"