source: rtems/cpukit/score/include/rtems/score/schedulersmpimpl.h @ 38b59a6

4.115
Last change on this file since 38b59a6 was 38b59a6, checked in by Sebastian Huber <sebastian.huber@…>, on 05/02/14 at 08:31:09

score: Implement forced thread migration

The current implementation of task migration in RTEMS has some
implications with respect to the interrupt latency. It is crucial to
preserve the system invariant that a task can execute on at most one
processor in the system at a time. This is accomplished with a boolean
indicator in the task context. The processor architecture specific
low-level task context switch code will mark that a task context is no
longer executing and waits that the heir context stopped execution
before it restores the heir context and resumes execution of the heir
task. So there is one point in time in which a processor is without a
task. This is essential to avoid cyclic dependencies in case multiple
tasks migrate at once. Otherwise some supervising entity is necessary to
prevent life-locks. Such a global supervisor would lead to scalability
problems so this approach is not used. Currently the thread dispatch is
performed with interrupts disabled. So in case the heir task is
currently executing on another processor then this prolongs the time of
disabled interrupts since one processor has to wait for another
processor to make progress.

It is difficult to avoid this issue with the interrupt latency since
interrupts normally store the context of the interrupted task on its
stack. In case a task is marked as not executing we must not use its
task stack to store such an interrupt context. We cannot use the heir
stack before it stopped execution on another processor. So if we enable
interrupts during this transition we have to provide an alternative task
independent stack for this time frame. This issue needs further
investigation.

  • Property mode set to 100644
File size: 7.5 KB
Line 
1/**
2 * @file
3 *
4 * @brief SMP Scheduler Implementation
5 *
6 * @ingroup ScoreSchedulerSMP
7 */
8
9/*
10 * Copyright (c) 2013-2014 embedded brains GmbH.  All rights reserved.
11 *
12 *  embedded brains GmbH
13 *  Dornierstr. 4
14 *  82178 Puchheim
15 *  Germany
16 *  <rtems@embedded-brains.de>
17 *
18 * The license and distribution terms for this file may be
19 * found in the file LICENSE in this distribution or at
20 * http://www.rtems.org/license/LICENSE.
21 */
22
23#ifndef _RTEMS_SCORE_SCHEDULERSMPIMPL_H
24#define _RTEMS_SCORE_SCHEDULERSMPIMPL_H
25
26#include <rtems/score/schedulersmp.h>
27#include <rtems/score/assert.h>
28#include <rtems/score/chainimpl.h>
29#include <rtems/score/schedulersimpleimpl.h>
30
31#ifdef __cplusplus
32extern "C" {
33#endif /* __cplusplus */
34
35/**
36 * @addtogroup ScoreSchedulerSMP
37 *
38 * @{
39 */
40
41typedef Thread_Control *( *Scheduler_SMP_Get_highest_ready )(
42  Scheduler_SMP_Context *self
43);
44
45typedef void ( *Scheduler_SMP_Extract )(
46  Scheduler_SMP_Context *self,
47  Thread_Control *thread
48);
49
50typedef void ( *Scheduler_SMP_Insert )(
51  Scheduler_SMP_Context *self,
52  Thread_Control *thread_to_insert
53);
54
55typedef void ( *Scheduler_SMP_Move )(
56  Scheduler_SMP_Context *self,
57  Thread_Control *thread_to_move
58);
59
60static inline void _Scheduler_SMP_Initialize(
61  Scheduler_SMP_Context *self
62)
63{
64  _Chain_Initialize_empty( &self->Scheduled );
65}
66
67static inline bool _Scheduler_SMP_Is_processor_owned_by_us(
68  const Scheduler_SMP_Context *self,
69  const Per_CPU_Control *cpu
70)
71{
72  return cpu->scheduler_context == &self->Base;
73}
74
75static inline void _Scheduler_SMP_Update_heir(
76  Per_CPU_Control *cpu_self,
77  Per_CPU_Control *cpu_for_heir,
78  Thread_Control *heir
79)
80{
81  cpu_for_heir->heir = heir;
82
83  /*
84   * It is critical that we first update the heir and then the dispatch
85   * necessary so that _Thread_Get_heir_and_make_it_executing() cannot miss an
86   * update.
87   */
88  _Atomic_Fence( ATOMIC_ORDER_SEQ_CST );
89
90  /*
91   * Only update the dispatch necessary indicator if not already set to
92   * avoid superfluous inter-processor interrupts.
93   */
94  if ( !cpu_for_heir->dispatch_necessary ) {
95    cpu_for_heir->dispatch_necessary = true;
96
97    if ( cpu_for_heir != cpu_self ) {
98      _Per_CPU_Send_interrupt( cpu_for_heir );
99    }
100  }
101}
102
103static inline void _Scheduler_SMP_Allocate_processor(
104  Scheduler_SMP_Context *self,
105  Thread_Control *scheduled,
106  Thread_Control *victim
107)
108{
109  Per_CPU_Control *cpu_of_scheduled = _Thread_Get_CPU( scheduled );
110  Per_CPU_Control *cpu_of_victim = _Thread_Get_CPU( victim );
111  Per_CPU_Control *cpu_self = _Per_CPU_Get();
112  Thread_Control *heir;
113
114  scheduled->is_scheduled = true;
115  victim->is_scheduled = false;
116
117  _Assert( _ISR_Get_level() != 0 );
118
119  if ( _Thread_Is_executing_on_a_processor( scheduled ) ) {
120    if ( _Scheduler_SMP_Is_processor_owned_by_us( self, cpu_of_scheduled ) ) {
121      heir = cpu_of_scheduled->heir;
122      _Scheduler_SMP_Update_heir( cpu_self, cpu_of_scheduled, scheduled );
123    } else {
124      /* We have to force a migration to our processor set */
125      _Assert( scheduled->debug_real_cpu->heir != scheduled );
126      heir = scheduled;
127    }
128  } else {
129    heir = scheduled;
130  }
131
132  if ( heir != victim ) {
133    _Thread_Set_CPU( heir, cpu_of_victim );
134    _Scheduler_SMP_Update_heir( cpu_self, cpu_of_victim, heir );
135  }
136}
137
138static inline Thread_Control *_Scheduler_SMP_Get_lowest_scheduled(
139  Scheduler_SMP_Context *self
140)
141{
142  Thread_Control *lowest_ready = NULL;
143  Chain_Control *scheduled = &self->Scheduled;
144
145  if ( !_Chain_Is_empty( scheduled ) ) {
146    lowest_ready = (Thread_Control *) _Chain_Last( scheduled );
147  }
148
149  return lowest_ready;
150}
151
152static inline void _Scheduler_SMP_Enqueue_ordered(
153  Scheduler_SMP_Context *self,
154  Thread_Control *thread,
155  Chain_Node_order order,
156  Scheduler_SMP_Get_highest_ready get_highest_ready,
157  Scheduler_SMP_Insert insert_ready,
158  Scheduler_SMP_Insert insert_scheduled,
159  Scheduler_SMP_Move move_from_ready_to_scheduled,
160  Scheduler_SMP_Move move_from_scheduled_to_ready
161)
162{
163  if ( thread->is_in_the_air ) {
164    Thread_Control *highest_ready = ( *get_highest_ready )( self );
165
166    thread->is_in_the_air = false;
167
168    /*
169     * The thread has been extracted from the scheduled chain.  We have to
170     * place it now on the scheduled or ready chain.
171     *
172     * NOTE: Do not exchange parameters to do the negation of the order check.
173     */
174    if (
175      highest_ready != NULL
176        && !( *order )( &thread->Object.Node, &highest_ready->Object.Node )
177    ) {
178      _Scheduler_SMP_Allocate_processor( self, highest_ready, thread );
179
180      ( *insert_ready )( self, thread );
181      ( *move_from_ready_to_scheduled )( self, highest_ready );
182    } else {
183      thread->is_scheduled = true;
184
185      ( *insert_scheduled )( self, thread );
186    }
187  } else {
188    Thread_Control *lowest_scheduled = _Scheduler_SMP_Get_lowest_scheduled( self );
189
190    /*
191     * The scheduled chain is empty if nested interrupts change the priority of
192     * all scheduled threads.  These threads are in the air.
193     */
194    if (
195      lowest_scheduled != NULL
196        && ( *order )( &thread->Object.Node, &lowest_scheduled->Object.Node )
197    ) {
198      _Scheduler_SMP_Allocate_processor( self, thread, lowest_scheduled );
199
200      ( *insert_scheduled )( self, thread );
201      ( *move_from_scheduled_to_ready )( self, lowest_scheduled );
202    } else {
203      ( *insert_ready )( self, thread );
204    }
205  }
206}
207
208static inline void _Scheduler_SMP_Schedule_highest_ready(
209  Scheduler_SMP_Context *self,
210  Thread_Control *victim,
211  Scheduler_SMP_Get_highest_ready get_highest_ready,
212  Scheduler_SMP_Move move_from_ready_to_scheduled
213)
214{
215  Thread_Control *highest_ready = ( *get_highest_ready )( self );
216
217  _Scheduler_SMP_Allocate_processor( self, highest_ready, victim );
218
219  ( *move_from_ready_to_scheduled )( self, highest_ready );
220}
221
222static inline void _Scheduler_SMP_Schedule(
223  Scheduler_SMP_Context *self,
224  Thread_Control *thread,
225  Scheduler_SMP_Get_highest_ready get_highest_ready,
226  Scheduler_SMP_Move move_from_ready_to_scheduled
227)
228{
229  if ( thread->is_in_the_air ) {
230    thread->is_in_the_air = false;
231
232    _Scheduler_SMP_Schedule_highest_ready(
233      self,
234      thread,
235      get_highest_ready,
236      move_from_ready_to_scheduled
237    );
238  }
239}
240
241static inline void _Scheduler_SMP_Block(
242  Scheduler_SMP_Context *self,
243  Thread_Control *thread,
244  Scheduler_SMP_Extract extract,
245  Scheduler_SMP_Get_highest_ready get_highest_ready,
246  Scheduler_SMP_Move move_from_ready_to_scheduled
247)
248{
249  ( *extract )( self, thread );
250
251  _Scheduler_SMP_Schedule(
252    self,
253    thread,
254    get_highest_ready,
255    move_from_ready_to_scheduled
256  );
257}
258
259static inline void _Scheduler_SMP_Extract(
260  Scheduler_SMP_Context *self,
261  Thread_Control *thread,
262  Scheduler_SMP_Extract extract
263)
264{
265  ( *extract )( self, thread );
266}
267
268static inline void _Scheduler_SMP_Insert_scheduled_lifo(
269  Scheduler_SMP_Context *self,
270  Thread_Control *thread
271)
272{
273  _Chain_Insert_ordered_unprotected(
274    &self->Scheduled,
275    &thread->Object.Node,
276    _Scheduler_simple_Insert_priority_lifo_order
277  );
278}
279
280static inline void _Scheduler_SMP_Insert_scheduled_fifo(
281  Scheduler_SMP_Context *self,
282  Thread_Control *thread
283)
284{
285  _Chain_Insert_ordered_unprotected(
286    &self->Scheduled,
287    &thread->Object.Node,
288    _Scheduler_simple_Insert_priority_fifo_order
289  );
290}
291
292static inline void _Scheduler_SMP_Start_idle(
293  Scheduler_SMP_Context *self,
294  Thread_Control *thread,
295  Per_CPU_Control *cpu
296)
297{
298  thread->is_scheduled = true;
299  _Thread_Set_CPU( thread, cpu );
300  _Chain_Append_unprotected( &self->Scheduled, &thread->Object.Node );
301}
302
303/** @} */
304
305#ifdef __cplusplus
306}
307#endif /* __cplusplus */
308
309#endif /* _RTEMS_SCORE_SCHEDULERSMPIMPL_H */
Note: See TracBrowser for help on using the repository browser.