1 | /** |
---|
2 | * @file |
---|
3 | * |
---|
4 | * Scheduler Simple SMP Handler / Schedule |
---|
5 | */ |
---|
6 | |
---|
7 | /* |
---|
8 | * COPYRIGHT (c) 2011- 2012. |
---|
9 | * On-Line Applications Research Corporation (OAR). |
---|
10 | * |
---|
11 | * The license and distribution terms for this file may be |
---|
12 | * found in found in the file LICENSE in this distribution or at |
---|
13 | * http://www.rtems.com/license/LICENSE. |
---|
14 | */ |
---|
15 | |
---|
16 | #if HAVE_CONFIG_H |
---|
17 | #include "config.h" |
---|
18 | #endif |
---|
19 | |
---|
20 | #include <rtems/system.h> |
---|
21 | #include <rtems/score/smp.h> |
---|
22 | #include <rtems/score/schedulersimplesmp.h> |
---|
23 | |
---|
24 | #include <stdio.h> |
---|
25 | |
---|
26 | /* |
---|
27 | * The following is very useful on the scheduler simulator when debugging |
---|
28 | * this algorithm. You are not likely to be able to print like this when |
---|
29 | * running on a real system. |
---|
30 | * |
---|
31 | * NOTE: This is NOT using RTEMS_DEBUG because this is not consistency |
---|
32 | * checking and is VERY VERY noisy. It is just for debugging |
---|
33 | * the algorithm. |
---|
34 | */ |
---|
35 | #if 0 |
---|
36 | #define D(format,...) printk( format, __VA_ARGS__) |
---|
37 | #else |
---|
38 | #define D(format,...) |
---|
39 | #endif |
---|
40 | |
---|
41 | /* Declaration to avoid warnings */ |
---|
42 | bool _Scheduler_simple_smp_Assign( |
---|
43 | Thread_Control *consider |
---|
44 | ); |
---|
45 | |
---|
46 | /** |
---|
47 | * @brief Assign Heir Thread to CPU |
---|
48 | * |
---|
49 | * This method attempts to find a core for the thread under consideration |
---|
50 | * (@a consider) to become heir of. The placement takes into account |
---|
51 | * priority, preemptibility, and length of time on core. |
---|
52 | * |
---|
53 | * Combined with the loop in _Scheduler_simple_smp_Schedule, it attempts |
---|
54 | * to faithfully implement the behaviour of the Deterministic Priority |
---|
55 | * Scheduler while spreading the threads across multiple cores. |
---|
56 | * |
---|
57 | * @param[in] consider is the thread under consideration. This means |
---|
58 | * that the method is looking for the best core to place it |
---|
59 | * as heir. |
---|
60 | * |
---|
61 | * @return This method returns true if it was able to make @a consider |
---|
62 | * the heir on a core and false otherwise. When this returns |
---|
63 | * false, there is no point in attempting to place an heir of |
---|
64 | * of lower priority. |
---|
65 | */ |
---|
66 | bool _Scheduler_simple_smp_Assign( |
---|
67 | Thread_Control *consider |
---|
68 | ) |
---|
69 | { |
---|
70 | bool found; /* have we found a cpu to place it on? */ |
---|
71 | uint32_t found_cpu; /* CPU to place this thread */ |
---|
72 | bool blocked; /* CPU has blocked thread? */ |
---|
73 | Thread_Control *pheir; /* heir on found cpu to potentially replace */ |
---|
74 | Thread_Control *h; |
---|
75 | Thread_Control *e; |
---|
76 | uint32_t cpu; |
---|
77 | |
---|
78 | /* |
---|
79 | * Initialize various variables to indicate we have not found |
---|
80 | * a potential core for the thread under consideration. |
---|
81 | */ |
---|
82 | found = false; |
---|
83 | blocked = false; |
---|
84 | found_cpu = 0; |
---|
85 | pheir = NULL; |
---|
86 | |
---|
87 | for ( cpu=0 ; cpu < _SMP_Processor_count ; cpu++ ) { |
---|
88 | D( "SCHED CPU=%d consider=0x%08x ASSIGN\n", cpu, consider->Object.id ); |
---|
89 | |
---|
90 | /* |
---|
91 | * If the thread under consideration is already executing or |
---|
92 | * heir, then we don't have a better option for it. |
---|
93 | */ |
---|
94 | e = _Per_CPU_Information[cpu].executing; |
---|
95 | if ( e == consider ) { |
---|
96 | D( "SCHED CPU=%d Executing=0x%08x considering=0x%08x ASSIGNED\n", |
---|
97 | cpu, e->Object.id, consider->Object.id ); |
---|
98 | return true; |
---|
99 | } |
---|
100 | |
---|
101 | if ( !_States_Is_ready( e->current_state ) ) { |
---|
102 | pheir = e; |
---|
103 | found_cpu = cpu; |
---|
104 | found = true; |
---|
105 | blocked = true; |
---|
106 | D( "SCHED CPU=%d PHeir=0x%08x considering=0x%08x BLOCKED\n", |
---|
107 | cpu, e->Object.id, consider->Object.id ); |
---|
108 | continue; |
---|
109 | } |
---|
110 | |
---|
111 | h = _Per_CPU_Information[cpu].heir; |
---|
112 | if ( h == consider ) { |
---|
113 | D( "SCHED CPU=%d Heir=0x%08x considering=0x%08x ASSIGNED\n", |
---|
114 | cpu, h->Object.id, consider->Object.id ); |
---|
115 | return true; |
---|
116 | } |
---|
117 | |
---|
118 | if ( blocked ) |
---|
119 | continue; |
---|
120 | |
---|
121 | /* |
---|
122 | * If we haven't found a potential CPU to locate the thread |
---|
123 | * under consideration on, we need to consider if this is a |
---|
124 | * more important threads first (e.g. priority <). |
---|
125 | * |
---|
126 | * But when a thread changes its priority and ends up at the end of |
---|
127 | * the priority group for the new heir, we also need to schedule |
---|
128 | * a new heir. This is the "=" part of the check. |
---|
129 | */ |
---|
130 | if ( !found ) { |
---|
131 | if ( consider->current_priority <= h->current_priority ) { |
---|
132 | pheir = h; |
---|
133 | found_cpu = cpu; |
---|
134 | found = true; |
---|
135 | D( "SCHED CPU=%d PHeir=0x%08x considering=0x%08x MAYBE #1\n", |
---|
136 | cpu, h->Object.id, consider->Object.id ); |
---|
137 | } |
---|
138 | |
---|
139 | continue; |
---|
140 | } |
---|
141 | |
---|
142 | /* |
---|
143 | * ASSERTION: (found == true) |
---|
144 | * |
---|
145 | * Past this point, we have found a potential heir and are considering |
---|
146 | * whether the thread is better placed on another core. It is desirable |
---|
147 | * to preempt the lowest priority thread using time on core and |
---|
148 | * preemptibility as additional factors. |
---|
149 | */ |
---|
150 | |
---|
151 | /* |
---|
152 | * If we have found a potential CPU on which to make the |
---|
153 | * thread under consideration the heir, then we need to |
---|
154 | * check if the current CPU is a more appropriate place |
---|
155 | * for this thread to be placed. |
---|
156 | * |
---|
157 | * Check 1: heir of potential CPU is more important |
---|
158 | * then heir of current CPU. We want to |
---|
159 | * replace the least important thread possible. |
---|
160 | */ |
---|
161 | if ( h->current_priority > pheir->current_priority ) { |
---|
162 | pheir = h; |
---|
163 | found_cpu = cpu; |
---|
164 | D( "SCHED CPU=%d PHeir=0x%08x considering=0x%08x MAYBE #2\n", |
---|
165 | cpu, h->Object.id, consider->Object.id ); |
---|
166 | continue; |
---|
167 | } |
---|
168 | |
---|
169 | /* |
---|
170 | * If the current heir is more important than the potential |
---|
171 | * heir, then we should not consider it further in scheduling. |
---|
172 | */ |
---|
173 | if ( h->current_priority < pheir->current_priority ) |
---|
174 | continue; |
---|
175 | |
---|
176 | /* |
---|
177 | * ASSERTION: (h->current_priority == pheir->current_priority). |
---|
178 | * |
---|
179 | * Past this point, this means we are considering the length of time |
---|
180 | * the thread has spent on the time on the CPU core and if it is |
---|
181 | * preemptible. |
---|
182 | */ |
---|
183 | |
---|
184 | /* |
---|
185 | * If heir of potential CPU and of the current CPU are of the SAME |
---|
186 | * priority, then which has been running longer? |
---|
187 | * |
---|
188 | * Which CPU has had its executing thread longer? |
---|
189 | */ |
---|
190 | if ( _Timestamp_Less_than( |
---|
191 | &_Per_CPU_Information[cpu].time_of_last_context_switch, |
---|
192 | &_Per_CPU_Information[found_cpu].time_of_last_context_switch |
---|
193 | ) ) { |
---|
194 | pheir = h; |
---|
195 | found_cpu = cpu; |
---|
196 | D( "SCHED CPU=%d PHeir=0x%08x considering=0x%08x LONGER\n", |
---|
197 | cpu, h->Object.id, consider->Object.id ); |
---|
198 | continue; |
---|
199 | } |
---|
200 | |
---|
201 | /* |
---|
202 | * If we are looking at a core with a non-preemptible thread |
---|
203 | * for potential placement, then favor a core with a preeemtible |
---|
204 | * thread of the same priority. This should help avoid priority |
---|
205 | * inversions and let threads run earlier. |
---|
206 | */ |
---|
207 | if ( !pheir->is_preemptible && h->is_preemptible ) { |
---|
208 | D( "SCHED CPU=%d PHeir==0x%08x is NOT PREEMPTIBLE\n", |
---|
209 | cpu, pheir->Object.id ); |
---|
210 | pheir = h; |
---|
211 | found_cpu = cpu; |
---|
212 | D( "SCHED CPU=%d PHeir=0x%08x considering=0x%08x PREEMPTIBLE\n", |
---|
213 | cpu, h->Object.id, consider->Object.id ); |
---|
214 | continue; |
---|
215 | |
---|
216 | } |
---|
217 | } |
---|
218 | |
---|
219 | /* |
---|
220 | * If we found a cpu to make this thread heir of, then we |
---|
221 | * need to consider whether we need a dispatch on that CPU. |
---|
222 | */ |
---|
223 | if ( found ) { |
---|
224 | e = _Per_CPU_Information[found_cpu].executing; |
---|
225 | D( "SCHED CPU=%d executing=0x%08x considering=0x%08x FOUND\n", |
---|
226 | found_cpu, e->Object.id, consider->Object.id ); |
---|
227 | _Per_CPU_Information[found_cpu].heir = consider; |
---|
228 | if ( !_States_Is_ready( e->current_state ) ) { |
---|
229 | D( "SCHED CPU=%d executing not ready dispatch needed\n", found_cpu); |
---|
230 | _Per_CPU_Information[found_cpu].dispatch_necessary = true; |
---|
231 | } else if ( consider->current_priority < e->current_priority ) { |
---|
232 | if ( e->is_preemptible || consider->current_priority == 0 ) { |
---|
233 | D( "SCHED CPU=%d preempting\n", found_cpu); |
---|
234 | _Per_CPU_Information[found_cpu].dispatch_necessary = true; |
---|
235 | } |
---|
236 | } |
---|
237 | } |
---|
238 | |
---|
239 | /* |
---|
240 | * Return true to indicate we changed an heir. This indicates |
---|
241 | * scheduling needs to examine more threads. |
---|
242 | */ |
---|
243 | return found; |
---|
244 | } |
---|
245 | |
---|
246 | /* |
---|
247 | * Reschedule threads -- select heirs for all cores |
---|
248 | */ |
---|
249 | void _Scheduler_simple_smp_Schedule(void) |
---|
250 | { |
---|
251 | Chain_Control *c; |
---|
252 | Chain_Node *n; |
---|
253 | Thread_Control *t; |
---|
254 | uint32_t cpu; |
---|
255 | |
---|
256 | c = (Chain_Control *)_Scheduler.information; |
---|
257 | cpu = 0; |
---|
258 | |
---|
259 | /* |
---|
260 | * Iterate over the first N (where N is the number of CPU cores) threads |
---|
261 | * on the ready chain. Attempt to assign each as heir on a core. When |
---|
262 | * unable to assign a thread as a new heir, then stop. |
---|
263 | */ |
---|
264 | for (n = _Chain_First(c); !_Chain_Is_tail(c, n); n = _Chain_Next(n)) { |
---|
265 | t = (Thread_Control *)n; |
---|
266 | if ( !_Scheduler_simple_smp_Assign( t ) ) |
---|
267 | break; |
---|
268 | if ( ++cpu >= _SMP_Processor_count ) |
---|
269 | break; |
---|
270 | } |
---|
271 | } |
---|