source: rtems/cpukit/score/src/schedulerpriorityaffinitysmp.c @ c597fb1

5
Last change on this file since c597fb1 was c597fb1, checked in by Sebastian Huber <sebastian.huber@…>, on 11/09/17 at 15:21:37

score: Optimize scheduler priority updates

Thread priority changes may append or prepend the thread to its priority
group on the scheduler ready queue. Previously, a separate priority
value and a prepend-it flag in the scheduler node were used to propagate
a priority change to the scheduler.

Now, use an append-it bit in the priority control and reduce the plain
priority value to 63 bits.

This change leads to a significant code size reduction (about 25%) of
the SMP schedulers. The negligible increase of the standard priority
scheduler is due to some additional shift operations
(SCHEDULER_PRIORITY_MAP() and SCHEDULER_PRIORITY_UNMAP()).

Before:

text filename

136 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulersimpleblock.o
464 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulersimplechangepriority.o

24 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulersimple.o

108 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulersimpleschedule.o
292 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulersimpleunblock.o
264 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulersimpleyield.o

text filename

280 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulerpriorityblock.o
488 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulerprioritychangepriority.o
200 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulerpriority.o
164 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulerpriorityschedule.o
328 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulerpriorityunblock.o
200 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulerpriorityyield.o

text filename

24112 arm-rtems5/c/imx7/cpukit/score/src/libscore_a-scheduleredfsmp.o

text filename

37204 sparc-rtems5/c/gr740/cpukit/score/src/libscore_a-scheduleredfsmp.o

text filename

42236 powerpc-rtems5/c/qoriq_e6500_32/cpukit/score/src/libscore_a-scheduleredfsmp.o

After:

text filename

136 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulersimpleblock.o
272 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulersimplechangepriority.o

24 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulersimple.o

108 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulersimpleschedule.o
292 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulersimpleunblock.o
264 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulersimpleyield.o

text filename

280 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulerpriorityblock.o
488 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulerprioritychangepriority.o
208 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulerpriority.o
164 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulerpriorityschedule.o
332 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulerpriorityunblock.o
200 sparc-rtems5/c/erc32/cpukit/score/src/libscore_a-schedulerpriorityyield.o

text filename

18860 arm-rtems5/c/imx7/cpukit/score/src/libscore_a-scheduleredfsmp.o

text filename

28520 sparc-rtems5/c/gr740/cpukit/score/src/libscore_a-scheduleredfsmp.o

text filename

32664 powerpc-rtems5/c/qoriq_e6500_32/cpukit/score/src/libscore_a-scheduleredfsmp.o

  • Property mode set to 100644
File size: 16.5 KB
Line 
1/**
2 * @file
3 *
4 * @brief Deterministic Priority Affinity SMP Scheduler Implementation
5 *
6 * @ingroup ScoreSchedulerPriorityAffinitySMP
7 */
8
9/*
10 *  COPYRIGHT (c) 2014.
11 *  On-Line Applications Research Corporation (OAR).
12 *
13 *  The license and distribution terms for this file may be
14 *  found in the file LICENSE in this distribution or at
15 *  http://www.rtems.org/license/LICENSE.
16 */
17
18#if HAVE_CONFIG_H
19  #include "config.h"
20#endif
21
22#include <rtems/score/schedulerpriorityaffinitysmp.h>
23#include <rtems/score/schedulerpriorityimpl.h>
24#include <rtems/score/schedulersmpimpl.h>
25#include <rtems/score/schedulerprioritysmpimpl.h>
26#include <rtems/score/priority.h>
27
28/*
29 * The following methods which initially were static in schedulerprioritysmp.c
30 * are shared with this scheduler. They are now public so they can be shared.
31 *
32 *  + _Scheduler_priority_SMP_Get_self
33 *  + _Scheduler_priority_SMP_Insert_ready_fifo
34 *  + _Scheduler_priority_SMP_Insert_ready_lifo
35 *  + _Scheduler_priority_SMP_Thread_get_node
36 *  + _Scheduler_priority_SMP_Move_from_scheduled_to_ready
37 *  + _Scheduler_priority_SMP_Move_from_ready_to_scheduled
38 *  + _Scheduler_priority_SMP_Extract_from_ready
39 *  + _Scheduler_priority_SMP_Do_update
40 */
41
42static bool _Scheduler_priority_affinity_SMP_Priority_less_equal(
43  const void       *to_insert,
44  const Chain_Node *next
45)
46{
47  return next != NULL
48    && _Scheduler_SMP_Priority_less_equal( to_insert, next );
49}
50
51static Scheduler_priority_affinity_SMP_Node *
52_Scheduler_priority_affinity_SMP_Node_downcast(
53  Scheduler_Node *node
54)
55{
56  return (Scheduler_priority_affinity_SMP_Node *) node;
57}
58
59/*
60 * This method initializes the scheduler control information for
61 * this scheduler instance.
62 */
63void _Scheduler_priority_affinity_SMP_Node_initialize(
64  const Scheduler_Control *scheduler,
65  Scheduler_Node          *node,
66  Thread_Control          *the_thread,
67  Priority_Control         priority
68)
69{
70  Scheduler_priority_affinity_SMP_Node *the_node;
71
72  _Scheduler_priority_SMP_Node_initialize( scheduler, node, the_thread, priority );
73
74  /*
75   *  All we add is affinity information to the basic SMP node.
76   */
77  the_node = _Scheduler_priority_affinity_SMP_Node_downcast( node );
78  _Processor_mask_Assign( &the_node->Affinity, _SMP_Get_online_processors() );
79}
80
81/*
82 * This method is unique to this scheduler because it takes into
83 * account affinity as it determines the highest ready thread.
84 * Since this is used to pick a new thread to replace the victim,
85 * the highest ready thread must have affinity such that it can
86 * be executed on the victim's processor.
87 */
88static Scheduler_Node *_Scheduler_priority_affinity_SMP_Get_highest_ready(
89  Scheduler_Context *context,
90  Scheduler_Node    *victim
91)
92{
93  Scheduler_priority_SMP_Context       *self =
94    _Scheduler_priority_SMP_Get_self( context );
95  Priority_Control                      index;
96  Scheduler_Node                       *highest = NULL;
97  Thread_Control                       *victim_thread;
98  uint32_t                              victim_cpu_index;
99  Scheduler_priority_affinity_SMP_Node *node;
100
101  /*
102   * This is done when we need to check if reevaluations are needed.
103   */
104  if ( victim == NULL ) {
105    node = (Scheduler_priority_affinity_SMP_Node *)
106      _Scheduler_priority_Ready_queue_first(
107        &self->Bit_map,
108        &self->Ready[ 0 ]
109      );
110
111    return &node->Base.Base.Base;
112  }
113
114  victim_thread = _Scheduler_Node_get_owner( victim );
115  victim_cpu_index = _Per_CPU_Get_index( _Thread_Get_CPU( victim_thread ) );
116
117  /**
118   * @todo The deterministic priority scheduler structure is optimized
119   * for insertion, extraction, and finding the highest priority
120   * thread. Scanning the list of ready threads is not a purpose
121   * for which it was optimized. There are optimizations to be
122   * made in this loop.
123   *
124   * + by checking the major bit, we could potentially skip entire
125   *   groups of 16.
126   *
127   * When using this scheduler as implemented, the application's
128   * choice of numeric priorities and their distribution can have
129   * an impact on performance.
130   */
131  for ( index = _Priority_bit_map_Get_highest( &self->Bit_map ) ;
132        index <= PRIORITY_MAXIMUM;
133        index++ )
134  {
135    Chain_Control   *chain =  &self->Ready[index];
136    Chain_Node      *chain_node;
137    for ( chain_node = _Chain_First( chain );
138          chain_node != _Chain_Immutable_tail( chain ) ;
139          chain_node = _Chain_Next( chain_node ) )
140    {
141      node = (Scheduler_priority_affinity_SMP_Node *) chain_node;
142
143      /*
144       * Can this thread run on this CPU?
145       */
146      if ( _Processor_mask_Is_set( &node->Affinity, victim_cpu_index ) ) {
147        highest = &node->Base.Base.Base;
148        break;
149      }
150    }
151    if ( highest )
152      break;
153  }
154
155  _Assert( highest != NULL );
156
157  return highest;
158}
159
160/*
161 * This method is very similar to _Scheduler_priority_affinity_SMP_Block
162 * but has the difference that is invokes this scheduler's
163 * get_highest_ready() support method.
164 */
165void _Scheduler_priority_affinity_SMP_Block(
166  const Scheduler_Control *scheduler,
167  Thread_Control          *thread,
168  Scheduler_Node          *node
169)
170{
171  Scheduler_Context *context = _Scheduler_Get_context( scheduler );
172
173  _Scheduler_SMP_Block(
174    context,
175    thread,
176    node,
177    _Scheduler_priority_SMP_Extract_from_ready,
178    _Scheduler_priority_affinity_SMP_Get_highest_ready,
179    _Scheduler_priority_SMP_Move_from_ready_to_scheduled,
180    _Scheduler_SMP_Allocate_processor_exact
181  );
182
183  /*
184   * Since this removed a single thread from the scheduled set
185   * and selected the most appropriate thread from the ready
186   * set to replace it, there should be no need for thread
187   * migrations.
188   */
189}
190
191/*
192 * This method is unique to this scheduler because it must take into
193 * account affinity as it searches for the lowest priority scheduled
194 * thread. It ignores those which cannot be replaced by the filter
195 * thread because the potential victim thread does not have affinity
196 * for that processor.
197 */
198static Scheduler_Node * _Scheduler_priority_affinity_SMP_Get_lowest_scheduled(
199  Scheduler_Context *context,
200  Scheduler_Node    *filter_base
201)
202{
203  Scheduler_SMP_Context *self = _Scheduler_SMP_Get_self( context );
204  Scheduler_Node *lowest_scheduled = NULL;
205  Chain_Control   *scheduled = &self->Scheduled;
206  Chain_Node      *chain_node;
207  Scheduler_priority_affinity_SMP_Node *filter =
208    _Scheduler_priority_affinity_SMP_Node_downcast( filter_base );
209
210  for ( chain_node = _Chain_Last( scheduled );
211        chain_node != _Chain_Immutable_head( scheduled ) ;
212        chain_node = _Chain_Previous( chain_node ) ) {
213    Scheduler_priority_affinity_SMP_Node *node;
214    Thread_Control                       *thread;
215    uint32_t                              cpu_index;
216
217    node = (Scheduler_priority_affinity_SMP_Node *) chain_node;
218
219    /* cpu_index is the processor number thread is executing on */
220    thread = _Scheduler_Node_get_owner( &node->Base.Base.Base );
221    cpu_index = _Per_CPU_Get_index( _Thread_Get_CPU( thread ) );
222
223    if ( _Processor_mask_Is_set( &filter->Affinity, cpu_index ) ) {
224      lowest_scheduled = &node->Base.Base.Base;
225      break;
226    }
227
228  }
229
230  return lowest_scheduled;
231}
232
233/*
234 * This method is unique to this scheduler because it must pass
235 * _Scheduler_priority_affinity_SMP_Get_lowest_scheduled into
236 * _Scheduler_SMP_Enqueue.
237 */
238static bool _Scheduler_priority_affinity_SMP_Enqueue_fifo(
239  Scheduler_Context *context,
240  Scheduler_Node    *node,
241  Priority_Control   insert_priority
242)
243{
244  return _Scheduler_SMP_Enqueue(
245    context,
246    node,
247    insert_priority,
248    _Scheduler_priority_affinity_SMP_Priority_less_equal,
249    _Scheduler_priority_SMP_Insert_ready,
250    _Scheduler_SMP_Insert_scheduled,
251    _Scheduler_priority_SMP_Move_from_scheduled_to_ready,
252    _Scheduler_priority_affinity_SMP_Get_lowest_scheduled,
253    _Scheduler_SMP_Allocate_processor_exact
254  );
255}
256
257/*
258 * This method is invoked at the end of certain scheduling operations
259 * to ensure that the highest priority ready thread cannot be scheduled
260 * to execute. When we schedule with affinity, there is the possibility
261 * that we need to migrate a thread to another core to ensure that the
262 * highest priority ready threads are in fact scheduled.
263 */
264static void _Scheduler_priority_affinity_SMP_Check_for_migrations(
265  Scheduler_Context *context
266)
267{
268  Scheduler_priority_SMP_Context *self;
269  Scheduler_Node                 *lowest_scheduled;
270  Scheduler_Node                 *highest_ready;
271
272  self = _Scheduler_priority_SMP_Get_self( context );
273
274  while (1) {
275    Priority_Control lowest_scheduled_priority;
276    Priority_Control insert_priority;
277
278    if ( _Priority_bit_map_Is_empty( &self->Bit_map ) ) {
279      /* Nothing to do */
280      break;
281    }
282
283    highest_ready =
284      _Scheduler_priority_affinity_SMP_Get_highest_ready( context, NULL );
285
286    lowest_scheduled =
287      _Scheduler_priority_affinity_SMP_Get_lowest_scheduled(
288        context,
289        highest_ready
290      );
291
292    /*
293     * If we can't find a thread to displace from the scheduled set,
294     * then we have placed all the highest priority threads possible
295     * in the scheduled set.
296     *
297     * We found the absolute highest priority thread without
298     * considering affinity. But now we have to consider that thread's
299     * affinity as we look to place it.
300     */
301
302    if ( lowest_scheduled == NULL )
303      break;
304
305    lowest_scheduled_priority =
306      _Scheduler_SMP_Node_priority( lowest_scheduled );
307
308    if (
309      _Scheduler_SMP_Priority_less_equal(
310        &lowest_scheduled_priority,
311        &highest_ready->Node.Chain
312      )
313    ) {
314      break;
315    }
316
317    /*
318     * But if we found a thread which is lower priority than one
319     * in the ready set, then we need to swap them out.
320     */
321
322    _Scheduler_priority_SMP_Extract_from_ready( context, highest_ready );
323    insert_priority = _Scheduler_SMP_Node_priority( highest_ready );
324    insert_priority = SCHEDULER_PRIORITY_APPEND( insert_priority );
325    _Scheduler_SMP_Enqueue_to_scheduled(
326      context,
327      highest_ready,
328      insert_priority,
329      lowest_scheduled,
330      _Scheduler_SMP_Insert_scheduled,
331      _Scheduler_priority_SMP_Move_from_scheduled_to_ready,
332      _Scheduler_SMP_Allocate_processor_exact
333    );
334  }
335}
336
337/*
338 * This is the public scheduler specific Unblock operation.
339 */
340void _Scheduler_priority_affinity_SMP_Unblock(
341  const Scheduler_Control *scheduler,
342  Thread_Control          *thread,
343  Scheduler_Node          *node
344)
345{
346  Scheduler_Context *context = _Scheduler_Get_context( scheduler );
347
348  _Scheduler_SMP_Unblock(
349    context,
350    thread,
351    node,
352    _Scheduler_priority_SMP_Do_update,
353    _Scheduler_priority_affinity_SMP_Enqueue_fifo
354  );
355
356  /*
357   * Perform any thread migrations that are needed due to these changes.
358   */
359  _Scheduler_priority_affinity_SMP_Check_for_migrations( context );
360}
361
362/*
363 *  This is unique to this scheduler because it passes scheduler specific
364 *  get_lowest_scheduled helper to _Scheduler_SMP_Enqueue.
365 */
366static bool _Scheduler_priority_affinity_SMP_Enqueue(
367  Scheduler_Context *context,
368  Scheduler_Node    *node,
369  Priority_Control   insert_priority
370)
371{
372  return _Scheduler_SMP_Enqueue(
373    context,
374    node,
375    insert_priority,
376    _Scheduler_priority_affinity_SMP_Priority_less_equal,
377    _Scheduler_priority_SMP_Insert_ready,
378    _Scheduler_SMP_Insert_scheduled,
379    _Scheduler_priority_SMP_Move_from_scheduled_to_ready,
380    _Scheduler_priority_affinity_SMP_Get_lowest_scheduled,
381    _Scheduler_SMP_Allocate_processor_exact
382  );
383}
384
385/*
386 * This method is unique to this scheduler because it must
387 * invoke _Scheduler_SMP_Enqueue_scheduled() with
388 * this scheduler's get_highest_ready() helper.
389 */
390static bool _Scheduler_priority_affinity_SMP_Enqueue_scheduled(
391  Scheduler_Context *context,
392  Scheduler_Node    *node,
393  Priority_Control   insert_priority
394)
395{
396  return _Scheduler_SMP_Enqueue_scheduled(
397    context,
398    node,
399    insert_priority,
400    _Scheduler_SMP_Priority_less_equal,
401    _Scheduler_priority_SMP_Extract_from_ready,
402    _Scheduler_priority_affinity_SMP_Get_highest_ready,
403    _Scheduler_priority_SMP_Insert_ready,
404    _Scheduler_SMP_Insert_scheduled,
405    _Scheduler_priority_SMP_Move_from_ready_to_scheduled,
406    _Scheduler_SMP_Allocate_processor_exact
407  );
408}
409
410static bool _Scheduler_priority_affinity_SMP_Do_ask_for_help(
411  Scheduler_Context *context,
412  Thread_Control    *the_thread,
413  Scheduler_Node    *node
414)
415{
416  return _Scheduler_SMP_Ask_for_help(
417    context,
418    the_thread,
419    node,
420    _Scheduler_SMP_Priority_less_equal,
421    _Scheduler_priority_SMP_Insert_ready,
422    _Scheduler_SMP_Insert_scheduled,
423    _Scheduler_priority_SMP_Move_from_scheduled_to_ready,
424    _Scheduler_SMP_Get_lowest_scheduled,
425    _Scheduler_SMP_Allocate_processor_lazy
426  );
427}
428
429void _Scheduler_priority_affinity_SMP_Update_priority(
430  const Scheduler_Control *scheduler,
431  Thread_Control          *thread,
432  Scheduler_Node          *node
433)
434{
435  Scheduler_Context *context = _Scheduler_Get_context( scheduler );
436
437  _Scheduler_SMP_Update_priority(
438    context,
439    thread,
440    node,
441    _Scheduler_priority_SMP_Extract_from_ready,
442    _Scheduler_priority_SMP_Do_update,
443    _Scheduler_priority_affinity_SMP_Enqueue,
444    _Scheduler_priority_affinity_SMP_Enqueue_scheduled,
445    _Scheduler_priority_affinity_SMP_Do_ask_for_help
446  );
447
448  /*
449   * Perform any thread migrations that are needed due to these changes.
450   */
451  _Scheduler_priority_affinity_SMP_Check_for_migrations( context );
452}
453
454bool _Scheduler_priority_affinity_SMP_Ask_for_help(
455  const Scheduler_Control *scheduler,
456  Thread_Control          *the_thread,
457  Scheduler_Node          *node
458)
459{
460  Scheduler_Context *context = _Scheduler_Get_context( scheduler );
461
462  return _Scheduler_priority_affinity_SMP_Do_ask_for_help( context, the_thread, node );
463}
464
465void _Scheduler_priority_affinity_SMP_Reconsider_help_request(
466  const Scheduler_Control *scheduler,
467  Thread_Control          *the_thread,
468  Scheduler_Node          *node
469)
470{
471  Scheduler_Context *context = _Scheduler_Get_context( scheduler );
472
473  _Scheduler_SMP_Reconsider_help_request(
474    context,
475    the_thread,
476    node,
477    _Scheduler_priority_SMP_Extract_from_ready
478  );
479}
480
481void _Scheduler_priority_affinity_SMP_Withdraw_node(
482  const Scheduler_Control *scheduler,
483  Thread_Control          *the_thread,
484  Scheduler_Node          *node,
485  Thread_Scheduler_state   next_state
486)
487{
488  Scheduler_Context *context = _Scheduler_Get_context( scheduler );
489
490  _Scheduler_SMP_Withdraw_node(
491    context,
492    the_thread,
493    node,
494    next_state,
495    _Scheduler_priority_SMP_Extract_from_ready,
496    _Scheduler_priority_affinity_SMP_Get_highest_ready,
497    _Scheduler_priority_SMP_Move_from_ready_to_scheduled,
498    _Scheduler_SMP_Allocate_processor_lazy
499  );
500}
501
502void _Scheduler_priority_affinity_SMP_Add_processor(
503  const Scheduler_Control *scheduler,
504  Thread_Control          *idle
505)
506{
507  Scheduler_Context *context = _Scheduler_Get_context( scheduler );
508
509  _Scheduler_SMP_Add_processor(
510    context,
511    idle,
512    _Scheduler_priority_SMP_Has_ready,
513    _Scheduler_priority_affinity_SMP_Enqueue_scheduled,
514    _Scheduler_SMP_Do_nothing_register_idle
515  );
516}
517
518Thread_Control *_Scheduler_priority_affinity_SMP_Remove_processor(
519  const Scheduler_Control *scheduler,
520  Per_CPU_Control         *cpu
521)
522{
523  Scheduler_Context *context = _Scheduler_Get_context( scheduler );
524
525  return _Scheduler_SMP_Remove_processor(
526    context,
527    cpu,
528    _Scheduler_priority_SMP_Extract_from_ready,
529    _Scheduler_priority_affinity_SMP_Enqueue
530  );
531}
532
533bool _Scheduler_priority_affinity_SMP_Set_affinity(
534  const Scheduler_Control *scheduler,
535  Thread_Control          *thread,
536  Scheduler_Node          *node_base,
537  const Processor_mask    *affinity
538)
539{
540  Scheduler_Context                    *context;
541  Scheduler_priority_affinity_SMP_Node *node;
542  States_Control                        current_state;
543  Processor_mask                        my_affinity;
544
545  context = _Scheduler_Get_context( scheduler );
546  _Processor_mask_And( &my_affinity, &context->Processors, affinity );
547
548  if ( _Processor_mask_Count( &my_affinity ) == 0 ) {
549    return false;
550  }
551
552  node = _Scheduler_priority_affinity_SMP_Node_downcast( node_base );
553
554  /*
555   * The old and new set are the same, there is no point in
556   * doing anything.
557   */
558  if ( _Processor_mask_Is_equal( &node->Affinity, affinity ) )
559    return true;
560
561  current_state = thread->current_state;
562
563  if ( _States_Is_ready( current_state ) ) {
564    _Scheduler_priority_affinity_SMP_Block( scheduler, thread, &node->Base.Base.Base );
565  }
566
567  _Processor_mask_Assign( &node->Affinity, affinity );
568
569  if ( _States_Is_ready( current_state ) ) {
570    /*
571     * FIXME: Do not ignore threads in need for help.
572     */
573    (void) _Scheduler_priority_affinity_SMP_Unblock( scheduler, thread, &node->Base.Base.Base );
574  }
575
576  return true;
577}
Note: See TracBrowser for help on using the repository browser.