aboutsummaryrefslogtreecommitdiffstats
path: root/arch/frv/lib
diff options
context:
space:
mode:
authorGlenn Elliott <gelliott@cs.unc.edu>2012-08-20 17:28:55 -0400
committerGlenn Elliott <gelliott@cs.unc.edu>2012-08-27 15:07:17 -0400
commit077aaecac31331b65442275843932314049a2ceb (patch)
tree6b24a59521a0f5e3853b7667669b54211b03b272 /arch/frv/lib
parent9a19f35c9c287cb8abd5bcf276ae8d1a3e876907 (diff)
EDF priority tie-breaks.wip-robust-tie-break
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. Conflicts: litmus/edf_common.c
Diffstat (limited to 'arch/frv/lib')
0 files changed, 0 insertions, 0 deletions