diff options
author | Glenn Elliott <gelliott@cs.unc.edu> | 2012-08-05 20:22:39 -0400 |
---|---|---|
committer | Glenn Elliott <gelliott@cs.unc.edu> | 2012-08-05 20:22:39 -0400 |
commit | 7952ecbc73db87db30a4ae2b337d65ccbe696e83 (patch) | |
tree | 66e47fe49d8937ed958cebf51bd21be7c0f3a881 /litmus/edf_common.c | |
parent | b53c479a0f44b8990ce106622412a3bf54809944 (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.c | 45 |
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 | ||
20 | static 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 | ||
87 | int edf_ready_order(struct bheap_node* a, struct bheap_node* b) | 128 | int edf_ready_order(struct bheap_node* a, struct bheap_node* b) |