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