aboutsummaryrefslogtreecommitdiffstats
path: root/litmus/edf_common.c
diff options
context:
space:
mode:
authorGlenn Elliott <gelliott@cs.unc.edu>2012-08-05 20:22:39 -0400
committerGlenn Elliott <gelliott@cs.unc.edu>2012-08-05 20:22:39 -0400
commit7952ecbc73db87db30a4ae2b337d65ccbe696e83 (patch)
tree66e47fe49d8937ed958cebf51bd21be7c0f3a881 /litmus/edf_common.c
parentb53c479a0f44b8990ce106622412a3bf54809944 (diff)
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).
Diffstat (limited to 'litmus/edf_common.c')
-rw-r--r--litmus/edf_common.c45
1 files changed, 43 insertions, 2 deletions
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 @@
14 14
15#include <litmus/edf_common.h> 15#include <litmus/edf_common.h>
16 16
17#include <linux/hash.h>
18
19#ifdef CONFIG_EDF_HASH_TIE_BREAK
20static inline long edf_hash(struct task_struct *t)
21{
22 long key;
23 /* pid is 32 bits, so normally we would shove that into the
24 * upper 32-bits and and put the job number in the bottom
25 * and hash the 64-bit number with hash_64(). Sadly,
26 * in testing, hash_64() doesn't distribute keys were the
27 * upper bits are close together (as would be the case with
28 * pids) and job numbers are equal (as would be the case with
29 * synchronous task sets with all relative deadlines equal).
30 *
31 * A 2006 Linux patch proposed the following solution
32 * (but for some reason it wasn't accepted...).
33 *
34 * At least this workaround works for 32-bit systems as well.
35 */
36
37 /* This would be nice, but hash_64() has problems.
38 key = ((long)t->pid << 32) | ((long)tsk_rt(t)->job_params.job_no & 0xFFFFFFFF);
39 return hash_64(key, 0);
40 */
41
42 return hash_32(hash_32((u32)tsk_rt(t)->job_params.job_no, 32) ^ t->pid, 32);
43}
44#endif
45
17/* edf_higher_prio - returns true if first has a higher EDF priority 46/* edf_higher_prio - returns true if first has a higher EDF priority
18 * than second. Deadline ties are broken by PID. 47 * than second. Deadline ties are broken by PID.
19 * 48 *
@@ -25,6 +54,10 @@ int edf_higher_prio(struct task_struct* first,
25 struct task_struct *first_task = first; 54 struct task_struct *first_task = first;
26 struct task_struct *second_task = second; 55 struct task_struct *second_task = second;
27 56
57#ifdef CONFIG_EDF_HASH_TIE_BREAK
58 long fhash, shash;
59#endif
60
28 /* There is no point in comparing a task to itself. */ 61 /* There is no point in comparing a task to itself. */
29 if (first && first == second) { 62 if (first && first == second) {
30 TRACE_TASK(first, 63 TRACE_TASK(first,
@@ -63,7 +96,6 @@ int edf_higher_prio(struct task_struct* first,
63 96
64#endif 97#endif
65 98
66
67 return !is_realtime(second_task) || 99 return !is_realtime(second_task) ||
68 100
69 /* is the deadline of the first task earlier? 101 /* is the deadline of the first task earlier?
@@ -75,13 +107,22 @@ int edf_higher_prio(struct task_struct* first,
75 * Then break by PID. 107 * Then break by PID.
76 */ 108 */
77 (get_deadline(first_task) == get_deadline(second_task) && 109 (get_deadline(first_task) == get_deadline(second_task) &&
110#ifdef CONFIG_EDF_HASH_TIE_BREAK
111 /* assignment within less-than compare is intentional */
112 ((fhash = edf_hash(first_task)) < (shash = edf_hash(second_task)) ||
113 (fhash == shash &&
114#endif
78 (first_task->pid < second_task->pid || 115 (first_task->pid < second_task->pid ||
79 116
80 /* If the PIDs are the same then the task with the inherited 117 /* If the PIDs are the same then the task with the inherited
81 * priority wins. 118 * priority wins.
82 */ 119 */
83 (first_task->pid == second_task->pid && 120 (first_task->pid == second_task->pid &&
84 !second->rt_param.inh_task))); 121 !second->rt_param.inh_task))
122#ifdef CONFIG_EDF_HASH_TIE_BREAK
123 ))
124#endif
125 );
85} 126}
86 127
87int edf_ready_order(struct bheap_node* a, struct bheap_node* b) 128int edf_ready_order(struct bheap_node* a, struct bheap_node* b)