source: rtems/cpukit/score/src/schedulerpriorityaffinitysmp.c @ 63e2ca1b

5
Last change on this file since 63e2ca1b was 63e2ca1b, checked in by Sebastian Huber <sebastian.huber@…>, on Oct 31, 2016 at 8:13:35 AM

score: Simplify yield and unblock scheduler ops

Update #2556.

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