source: rtems/cpukit/score/src/schedulerpriorityaffinitysmp.c @ 27783f6

4.115
Last change on this file since 27783f6 was 27783f6, checked in by Sebastian Huber <sebastian.huber@…>, on 07/10/14 at 12:27:42

score: Fix scheduler helping implementation

Do not extract the idle threads from the ready set so that there is
always a thread available for comparison.

  • Property mode set to 100644
File size: 17.8 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/wkspace.h>
27#include <rtems/score/cpusetimpl.h>
28
29#include <rtems/score/priority.h>
30
31/*
32 * The following methods which initially were static in schedulerprioritysmp.c
33 * are shared with this scheduler. They are now public so they can be shared.
34 *
35 *  + _Scheduler_priority_SMP_Get_self
36 *  + _Scheduler_priority_SMP_Insert_ready_fifo
37 *  + _Scheduler_priority_SMP_Insert_ready_lifo
38 *  + _Scheduler_priority_SMP_Thread_get_node
39 *  + _Scheduler_priority_SMP_Move_from_scheduled_to_ready
40 *  + _Scheduler_priority_SMP_Move_from_ready_to_scheduled
41 *  + _Scheduler_priority_SMP_Extract_from_ready
42 *  + _Scheduler_priority_SMP_Do_update
43 */
44
45static bool _Scheduler_priority_affinity_SMP_Insert_priority_lifo_order(
46  const Chain_Node *to_insert,
47  const Chain_Node *next
48)
49{
50  return next != NULL
51    && _Scheduler_SMP_Insert_priority_lifo_order( to_insert, next );
52}
53
54static bool _Scheduler_priority_affinity_SMP_Insert_priority_fifo_order(
55  const Chain_Node *to_insert,
56  const Chain_Node *next
57)
58{
59  return next != NULL
60    && _Scheduler_SMP_Insert_priority_fifo_order( to_insert, next );
61}
62
63static Scheduler_priority_affinity_SMP_Node *
64_Scheduler_priority_affinity_SMP_Thread_get_own_node(
65  Thread_Control *thread
66)
67{
68  return (Scheduler_priority_affinity_SMP_Node *)
69    _Scheduler_Thread_get_own_node( thread );
70}
71
72/*
73 * This method returns the scheduler node for the specified thread
74 * as a scheduler specific type.
75 */
76static Scheduler_priority_affinity_SMP_Node *
77_Scheduler_priority_affinity_SMP_Thread_get_node(
78  Thread_Control *thread
79)
80{
81  return (Scheduler_priority_affinity_SMP_Node *)
82    _Scheduler_Thread_get_node( thread );
83}
84
85static Scheduler_priority_affinity_SMP_Node *
86_Scheduler_priority_affinity_SMP_Node_downcast(
87  Scheduler_Node *node
88)
89{
90  return (Scheduler_priority_affinity_SMP_Node *) node;
91}
92
93/*
94 * This method initializes the scheduler control information for
95 * this scheduler instance.
96 */
97void _Scheduler_priority_affinity_SMP_Node_initialize(
98  const Scheduler_Control *scheduler,
99  Thread_Control          *thread
100)
101{
102  Scheduler_priority_affinity_SMP_Node *node =
103    _Scheduler_priority_affinity_SMP_Thread_get_own_node( thread );
104
105  (void) scheduler;
106
107  _Scheduler_SMP_Node_initialize( &node->Base.Base, thread );
108
109  /*
110   *  All we add is affinity information to the basic SMP node.
111   */
112  node->Affinity     = *_CPU_set_Default();
113  node->Affinity.set = &node->Affinity.preallocated;
114}
115
116/*
117 * This method is slightly different from
118 * _Scheduler_SMP_Allocate_processor_lazy() in that it does what it is asked to
119 * do. _Scheduler_SMP_Allocate_processor_lazy() attempts to prevent migrations
120 * but does not take into account affinity.
121 */
122static inline void _Scheduler_SMP_Allocate_processor_exact(
123  Scheduler_Context *context,
124  Thread_Control    *scheduled_thread,
125  Thread_Control    *victim_thread
126)
127{
128  Per_CPU_Control *victim_cpu = _Thread_Get_CPU( victim_thread );
129  Per_CPU_Control *cpu_self = _Per_CPU_Get();
130
131  (void) context;
132
133  _Thread_Set_CPU( scheduled_thread, victim_cpu );
134  _Thread_Dispatch_update_heir( cpu_self, victim_cpu, scheduled_thread );
135}
136
137/*
138 * This method is unique to this scheduler because it takes into
139 * account affinity as it determines the highest ready thread.
140 * Since this is used to pick a new thread to replace the victim,
141 * the highest ready thread must have affinity such that it can
142 * be executed on the victim's processor.
143 */
144static Scheduler_Node *_Scheduler_priority_affinity_SMP_Get_highest_ready(
145  Scheduler_Context *context,
146  Scheduler_Node    *victim
147)
148{
149  Scheduler_priority_SMP_Context       *self =
150    _Scheduler_priority_SMP_Get_self( context );
151  Priority_Control                      index;
152  Scheduler_Node                       *highest = NULL;
153  Thread_Control                       *victim_thread;
154  uint32_t                              victim_cpu_index;
155  Scheduler_priority_affinity_SMP_Node *node;
156
157  /*
158   * This is done when we need to check if reevaluations are needed.
159   */
160  if ( victim == NULL ) {
161    node = (Scheduler_priority_affinity_SMP_Node *)
162      _Scheduler_priority_Ready_queue_first(
163        &self->Bit_map,
164        &self->Ready[ 0 ]
165      );
166
167    return &node->Base.Base.Base;
168  }
169
170  victim_thread = _Scheduler_Node_get_owner( victim );
171  victim_cpu_index = _Per_CPU_Get_index( _Thread_Get_CPU( victim_thread ) );
172
173  /**
174   * @todo The deterministic priority scheduler structure is optimized
175   * for insertion, extraction, and finding the highest priority
176   * thread. Scanning the list of ready threads is not a purpose
177   * for which it was optimized. There are optimizations to be
178   * made in this loop.
179   *
180   * + by checking the major bit, we could potentially skip entire
181   *   groups of 16.
182   *
183   * When using this scheduler as implemented, the application's
184   * choice of numeric priorities and their distribution can have
185   * an impact on performance.
186   */
187  for ( index = _Priority_bit_map_Get_highest( &self->Bit_map ) ;
188        index <= PRIORITY_MAXIMUM;
189        index++ )
190  {
191    Chain_Control   *chain =  &self->Ready[index];
192    Chain_Node      *chain_node;
193    for ( chain_node = _Chain_First( chain );
194          chain_node != _Chain_Immutable_tail( chain ) ;
195          chain_node = _Chain_Next( chain_node ) )
196    {
197      node = (Scheduler_priority_affinity_SMP_Node *) chain_node;
198
199      /*
200       * Can this thread run on this CPU?
201       */
202      if ( CPU_ISSET( (int) victim_cpu_index, node->Affinity.set ) ) {
203        highest = &node->Base.Base.Base;
204        break;
205      }
206    }
207    if ( highest )
208      break;
209  }
210
211  _Assert( highest != NULL );
212
213  return highest;
214}
215
216/*
217 * This method is very similar to _Scheduler_priority_affinity_SMP_Block
218 * but has the difference that is invokes this scheduler's
219 * get_highest_ready() support method.
220 */
221void _Scheduler_priority_affinity_SMP_Block(
222  const Scheduler_Control *scheduler,
223  Thread_Control *thread
224)
225{
226  Scheduler_Context *context = _Scheduler_Get_context( scheduler );
227
228  _Scheduler_SMP_Block(
229    context,
230    thread,
231    _Scheduler_priority_SMP_Extract_from_ready,
232    _Scheduler_priority_affinity_SMP_Get_highest_ready,
233    _Scheduler_priority_SMP_Move_from_ready_to_scheduled,
234    _Scheduler_SMP_Allocate_processor_exact
235  );
236
237  /*
238   * Since this removed a single thread from the scheduled set
239   * and selected the most appropriate thread from the ready
240   * set to replace it, there should be no need for thread
241   * migrations.
242   */
243}
244
245/*
246 * This method is unique to this scheduler because it must take into
247 * account affinity as it searches for the lowest priority scheduled
248 * thread. It ignores those which cannot be replaced by the filter
249 * thread because the potential victim thread does not have affinity
250 * for that processor.
251 */
252static Scheduler_Node * _Scheduler_priority_affinity_SMP_Get_lowest_scheduled(
253  Scheduler_Context *context,
254  Scheduler_Node    *filter_base,
255  Chain_Node_order   order
256)
257{
258  Scheduler_SMP_Context *self = _Scheduler_SMP_Get_self( context );
259  Scheduler_Node *lowest_scheduled = NULL;
260  Chain_Control   *scheduled = &self->Scheduled;
261  Chain_Node      *chain_node;
262  Scheduler_priority_affinity_SMP_Node *filter =
263    _Scheduler_priority_affinity_SMP_Node_downcast( filter_base );
264
265  for ( chain_node = _Chain_Last( scheduled );
266        chain_node != _Chain_Immutable_head( scheduled ) ;
267        chain_node = _Chain_Previous( chain_node ) ) {
268    Scheduler_priority_affinity_SMP_Node *node;
269    Thread_Control                       *thread;
270    uint32_t                              cpu_index;
271
272    node = (Scheduler_priority_affinity_SMP_Node *) chain_node;
273
274    /*
275     * If we didn't find a thread which is of equal or lower importance
276     * than filter thread is, then we can't schedule the filter thread
277     * to execute.
278     */
279    if ( (*order)( &node->Base.Base.Base.Node, &filter->Base.Base.Base.Node ) )
280      break;
281
282    /* cpu_index is the processor number thread is executing on */
283    thread = _Scheduler_Node_get_owner( &node->Base.Base.Base );
284    cpu_index = _Per_CPU_Get_index( _Thread_Get_CPU( thread ) );
285
286    if ( CPU_ISSET( (int) cpu_index, filter->Affinity.set ) ) {
287      lowest_scheduled = &node->Base.Base.Base;
288      break;
289    }
290
291  }
292
293  return lowest_scheduled;
294}
295
296/*
297 * This method is unique to this scheduler because it must pass
298 * _Scheduler_priority_affinity_SMP_Get_lowest_scheduled into
299 * _Scheduler_SMP_Enqueue_ordered.
300 */
301static Thread_Control *_Scheduler_priority_affinity_SMP_Enqueue_fifo(
302  Scheduler_Context *context,
303  Scheduler_Node    *node,
304  Thread_Control    *needs_help
305)
306{
307  return _Scheduler_SMP_Enqueue_ordered(
308    context,
309    node,
310    needs_help,
311    _Scheduler_priority_affinity_SMP_Insert_priority_fifo_order,
312    _Scheduler_priority_SMP_Insert_ready_fifo,
313    _Scheduler_SMP_Insert_scheduled_fifo,
314    _Scheduler_priority_SMP_Move_from_scheduled_to_ready,
315    _Scheduler_priority_affinity_SMP_Get_lowest_scheduled,
316    _Scheduler_SMP_Allocate_processor_exact
317  );
318}
319
320/*
321 * This method is invoked at the end of certain scheduling operations
322 * to ensure that the highest priority ready thread cannot be scheduled
323 * to execute. When we schedule with affinity, there is the possibility
324 * that we need to migrate a thread to another core to ensure that the
325 * highest priority ready threads are in fact scheduled.
326 */
327static void _Scheduler_priority_affinity_SMP_Check_for_migrations(
328  Scheduler_Context *context
329)
330{
331  Scheduler_Node        *lowest_scheduled;
332  Scheduler_Node        *highest_ready;
333
334  while (1) {
335    highest_ready =
336      _Scheduler_priority_affinity_SMP_Get_highest_ready( context, NULL );
337
338    lowest_scheduled =
339      _Scheduler_priority_affinity_SMP_Get_lowest_scheduled(
340        context,
341        highest_ready,
342        _Scheduler_SMP_Insert_priority_lifo_order
343      );
344
345    /*
346     * If we can't find a thread to displace from the scheduled set,
347     * then we have placed all the highest priority threads possible
348     * in the scheduled set.
349     *
350     * We found the absolute highest priority thread without
351     * considering affinity. But now we have to consider that thread's
352     * affinity as we look to place it.
353     */
354    if ( lowest_scheduled == NULL )
355      break;
356
357    /*
358     * But if we found a thread which is lower priority than one
359     * in the ready set, then we need to swap them out.
360     */
361
362    _Scheduler_SMP_Node_change_state(
363      _Scheduler_SMP_Node_downcast( lowest_scheduled ),
364      SCHEDULER_SMP_NODE_READY
365    );
366
367    _Scheduler_SMP_Allocate_processor(
368      context,
369      highest_ready,
370      lowest_scheduled,
371      _Scheduler_SMP_Allocate_processor_exact
372    );
373
374    _Scheduler_priority_SMP_Move_from_ready_to_scheduled(
375      context,
376      highest_ready
377    );
378
379    _Scheduler_priority_SMP_Move_from_scheduled_to_ready(
380      context,
381      lowest_scheduled
382    );
383  }
384}
385
386/*
387 * This is the public scheduler specific Unblock operation.
388 */
389Thread_Control *_Scheduler_priority_affinity_SMP_Unblock(
390  const Scheduler_Control *scheduler,
391  Thread_Control *thread
392)
393{
394  Scheduler_Context *context = _Scheduler_Get_context( scheduler );
395  Thread_Control    *needs_help;
396
397  needs_help = _Scheduler_SMP_Unblock(
398    context,
399    thread,
400    _Scheduler_priority_affinity_SMP_Enqueue_fifo
401  );
402
403  /*
404   * Perform any thread migrations that are needed due to these changes.
405   */
406  _Scheduler_priority_affinity_SMP_Check_for_migrations( context );
407
408  return needs_help;
409}
410
411/*
412 *  This is unique to this scheduler because it passes scheduler specific
413 *  get_lowest_scheduled helper to _Scheduler_SMP_Enqueue_ordered.
414 */
415static Thread_Control *_Scheduler_priority_affinity_SMP_Enqueue_ordered(
416  Scheduler_Context     *context,
417  Scheduler_Node        *node,
418  Thread_Control        *needs_help,
419  Chain_Node_order       order,
420  Scheduler_SMP_Insert   insert_ready,
421  Scheduler_SMP_Insert   insert_scheduled
422)
423{
424  return _Scheduler_SMP_Enqueue_ordered(
425    context,
426    node,
427    needs_help,
428    order,
429    insert_ready,
430    insert_scheduled,
431    _Scheduler_priority_SMP_Move_from_scheduled_to_ready,
432    _Scheduler_priority_affinity_SMP_Get_lowest_scheduled,
433    _Scheduler_SMP_Allocate_processor_exact
434  );
435}
436
437/*
438 *  This is unique to this scheduler because it is on the path
439 *  to _Scheduler_priority_affinity_SMP_Enqueue_ordered() which
440 *  invokes a scheduler unique get_lowest_scheduled helper.
441 */
442static Thread_Control *_Scheduler_priority_affinity_SMP_Enqueue_lifo(
443  Scheduler_Context *context,
444  Scheduler_Node    *node,
445  Thread_Control    *needs_help
446)
447{
448  return _Scheduler_priority_affinity_SMP_Enqueue_ordered(
449    context,
450    node,
451    needs_help,
452    _Scheduler_priority_affinity_SMP_Insert_priority_lifo_order,
453    _Scheduler_priority_SMP_Insert_ready_lifo,
454    _Scheduler_SMP_Insert_scheduled_lifo
455  );
456}
457
458/*
459 * This method is unique to this scheduler because it must
460 * invoke _Scheduler_SMP_Enqueue_scheduled_ordered() with
461 * this scheduler's get_highest_ready() helper.
462 */
463static Thread_Control *
464_Scheduler_priority_affinity_SMP_Enqueue_scheduled_ordered(
465  Scheduler_Context    *context,
466  Scheduler_Node       *node,
467  Chain_Node_order      order,
468  Scheduler_SMP_Insert  insert_ready,
469  Scheduler_SMP_Insert  insert_scheduled
470)
471{
472  return _Scheduler_SMP_Enqueue_scheduled_ordered(
473    context,
474    node,
475    order,
476    _Scheduler_priority_SMP_Extract_from_ready,
477    _Scheduler_priority_affinity_SMP_Get_highest_ready,
478    insert_ready,
479    insert_scheduled,
480    _Scheduler_priority_SMP_Move_from_ready_to_scheduled,
481    _Scheduler_SMP_Allocate_processor_exact
482  );
483}
484
485/*
486 *  This is unique to this scheduler because it is on the path
487 *  to _Scheduler_priority_affinity_SMP_Enqueue_scheduled__ordered() which
488 *  invokes a scheduler unique get_lowest_scheduled helper.
489 */
490static Thread_Control *_Scheduler_priority_affinity_SMP_Enqueue_scheduled_lifo(
491  Scheduler_Context *context,
492  Scheduler_Node    *node
493)
494{
495  return _Scheduler_priority_affinity_SMP_Enqueue_scheduled_ordered(
496    context,
497    node,
498    _Scheduler_SMP_Insert_priority_lifo_order,
499    _Scheduler_priority_SMP_Insert_ready_lifo,
500    _Scheduler_SMP_Insert_scheduled_lifo
501  );
502}
503
504/*
505 *  This is unique to this scheduler because it is on the path
506 *  to _Scheduler_priority_affinity_SMP_Enqueue_scheduled__ordered() which
507 *  invokes a scheduler unique get_lowest_scheduled helper.
508 */
509static Thread_Control *_Scheduler_priority_affinity_SMP_Enqueue_scheduled_fifo(
510  Scheduler_Context *context,
511  Scheduler_Node    *node
512)
513{
514  return _Scheduler_priority_affinity_SMP_Enqueue_scheduled_ordered(
515    context,
516    node,
517    _Scheduler_SMP_Insert_priority_fifo_order,
518    _Scheduler_priority_SMP_Insert_ready_fifo,
519    _Scheduler_SMP_Insert_scheduled_fifo
520  );
521}
522
523/*
524 * This is the public scheduler specific Change Priority operation.
525 */
526Thread_Control *_Scheduler_priority_affinity_SMP_Change_priority(
527  const Scheduler_Control *scheduler,
528  Thread_Control          *thread,
529  Priority_Control         new_priority,
530  bool                     prepend_it
531)
532{
533  Scheduler_Context *context = _Scheduler_Get_context( scheduler );
534  Thread_Control    *displaced;
535
536  displaced = _Scheduler_SMP_Change_priority(
537    context,
538    thread,
539    new_priority,
540    prepend_it,
541    _Scheduler_priority_SMP_Extract_from_ready,
542    _Scheduler_priority_SMP_Do_update,
543    _Scheduler_priority_affinity_SMP_Enqueue_fifo,
544    _Scheduler_priority_affinity_SMP_Enqueue_lifo,
545    _Scheduler_priority_affinity_SMP_Enqueue_scheduled_fifo,
546    _Scheduler_priority_affinity_SMP_Enqueue_scheduled_lifo
547  );
548
549  /*
550   * Perform any thread migrations that are needed due to these changes.
551   */
552  _Scheduler_priority_affinity_SMP_Check_for_migrations( context );
553
554  return displaced;
555}
556
557Thread_Control *_Scheduler_priority_affinity_SMP_Ask_for_help(
558  const Scheduler_Control *scheduler,
559  Thread_Control          *offers_help,
560  Thread_Control          *needs_help
561)
562{
563  Scheduler_Context *context = _Scheduler_Get_context( scheduler );
564
565  needs_help = _Scheduler_SMP_Ask_for_help(
566    context,
567    offers_help,
568    needs_help,
569    _Scheduler_priority_affinity_SMP_Enqueue_fifo
570  );
571
572  _Scheduler_priority_affinity_SMP_Check_for_migrations( context );
573
574  return needs_help;
575}
576
577/*
578 * This is the public scheduler specific Change Priority operation.
579 */
580bool _Scheduler_priority_affinity_SMP_Get_affinity(
581  const Scheduler_Control *scheduler,
582  Thread_Control          *thread,
583  size_t                   cpusetsize,
584  cpu_set_t               *cpuset
585)
586{
587  Scheduler_priority_affinity_SMP_Node *node =
588    _Scheduler_priority_affinity_SMP_Thread_get_node(thread);
589
590  (void) scheduler;
591
592  if ( node->Affinity.setsize != cpusetsize ) {
593    return false;
594  }
595
596  CPU_COPY( cpuset, node->Affinity.set );
597  return true;
598}
599
600bool _Scheduler_priority_affinity_SMP_Set_affinity(
601  const Scheduler_Control *scheduler,
602  Thread_Control          *thread,
603  size_t                   cpusetsize,
604  const cpu_set_t         *cpuset
605)
606{
607  Scheduler_priority_affinity_SMP_Node *node =
608    _Scheduler_priority_affinity_SMP_Thread_get_node(thread);
609
610  (void) scheduler;
611
612  /*
613   * Validate that the cpset meets basic requirements.
614   */
615  if ( !_CPU_set_Is_valid( cpuset, cpusetsize ) ) {
616    return false;
617  }
618
619  /*
620   * The old and new set are the same, there is no point in
621   * doing anything.
622   */
623  if ( CPU_EQUAL_S( cpusetsize, cpuset, node->Affinity.set ) )
624    return true;
625
626  _Thread_Set_state( thread, STATES_MIGRATING );
627    CPU_COPY( node->Affinity.set, cpuset );
628  _Thread_Clear_state( thread, STATES_MIGRATING );
629
630  return true;
631}
Note: See TracBrowser for help on using the repository browser.