source: rtems/cpukit/score/src/schedulerpriorityaffinitysmp.c @ 6771359f

5
Last change on this file since 6771359f was 6771359f, checked in by Sebastian Huber <sebastian.huber@…>, on Oct 27, 2016 at 4:42:06 AM

score: Second part of new MrsP implementation

Update #2556.

  • Property mode set to 100644
File size: 18.7 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    _Scheduler_Thread_get_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 Thread_Control *_Scheduler_priority_affinity_SMP_Enqueue_fifo(
274  Scheduler_Context *context,
275  Scheduler_Node    *node,
276  Thread_Control    *needs_help
277)
278{
279  return _Scheduler_SMP_Enqueue_ordered(
280    context,
281    node,
282    needs_help,
283    _Scheduler_priority_affinity_SMP_Insert_priority_fifo_order,
284    _Scheduler_priority_SMP_Insert_ready_fifo,
285    _Scheduler_SMP_Insert_scheduled_fifo,
286    _Scheduler_priority_SMP_Move_from_scheduled_to_ready,
287    _Scheduler_priority_affinity_SMP_Get_lowest_scheduled,
288    _Scheduler_SMP_Allocate_processor_exact
289  );
290}
291
292/*
293 * This method is invoked at the end of certain scheduling operations
294 * to ensure that the highest priority ready thread cannot be scheduled
295 * to execute. When we schedule with affinity, there is the possibility
296 * that we need to migrate a thread to another core to ensure that the
297 * highest priority ready threads are in fact scheduled.
298 */
299static void _Scheduler_priority_affinity_SMP_Check_for_migrations(
300  Scheduler_Context *context
301)
302{
303  Scheduler_priority_SMP_Context *self;
304  Scheduler_Node                 *lowest_scheduled;
305  Scheduler_Node                 *highest_ready;
306
307  self = _Scheduler_priority_SMP_Get_self( context );
308
309  while (1) {
310    if ( _Priority_bit_map_Is_empty( &self->Bit_map ) ) {
311      /* Nothing to do */
312      break;
313    }
314
315    highest_ready =
316      _Scheduler_priority_affinity_SMP_Get_highest_ready( context, NULL );
317
318    lowest_scheduled =
319      _Scheduler_priority_affinity_SMP_Get_lowest_scheduled(
320        context,
321        highest_ready,
322        _Scheduler_SMP_Insert_priority_lifo_order
323      );
324
325    /*
326     * If we can't find a thread to displace from the scheduled set,
327     * then we have placed all the highest priority threads possible
328     * in the scheduled set.
329     *
330     * We found the absolute highest priority thread without
331     * considering affinity. But now we have to consider that thread's
332     * affinity as we look to place it.
333     */
334    if ( lowest_scheduled == NULL )
335      break;
336
337    /*
338     * But if we found a thread which is lower priority than one
339     * in the ready set, then we need to swap them out.
340     */
341
342    _Scheduler_priority_SMP_Extract_from_ready( context, highest_ready );
343    _Scheduler_SMP_Enqueue_to_scheduled(
344      context,
345      highest_ready,
346      lowest_scheduled,
347      _Scheduler_SMP_Insert_scheduled_fifo,
348      _Scheduler_priority_SMP_Move_from_scheduled_to_ready,
349      _Scheduler_SMP_Allocate_processor_exact
350    );
351  }
352}
353
354/*
355 * This is the public scheduler specific Unblock operation.
356 */
357Thread_Control *_Scheduler_priority_affinity_SMP_Unblock(
358  const Scheduler_Control *scheduler,
359  Thread_Control          *thread,
360  Scheduler_Node          *node
361)
362{
363  Scheduler_Context *context = _Scheduler_Get_context( scheduler );
364  Thread_Control    *needs_help;
365
366  needs_help = _Scheduler_SMP_Unblock(
367    context,
368    thread,
369    node,
370    _Scheduler_priority_SMP_Do_update,
371    _Scheduler_priority_affinity_SMP_Enqueue_fifo
372  );
373
374  /*
375   * Perform any thread migrations that are needed due to these changes.
376   */
377  _Scheduler_priority_affinity_SMP_Check_for_migrations( context );
378
379  return needs_help;
380}
381
382/*
383 *  This is unique to this scheduler because it passes scheduler specific
384 *  get_lowest_scheduled helper to _Scheduler_SMP_Enqueue_ordered.
385 */
386static Thread_Control *_Scheduler_priority_affinity_SMP_Enqueue_ordered(
387  Scheduler_Context     *context,
388  Scheduler_Node        *node,
389  Thread_Control        *needs_help,
390  Chain_Node_order       order,
391  Scheduler_SMP_Insert   insert_ready,
392  Scheduler_SMP_Insert   insert_scheduled
393)
394{
395  return _Scheduler_SMP_Enqueue_ordered(
396    context,
397    node,
398    needs_help,
399    order,
400    insert_ready,
401    insert_scheduled,
402    _Scheduler_priority_SMP_Move_from_scheduled_to_ready,
403    _Scheduler_priority_affinity_SMP_Get_lowest_scheduled,
404    _Scheduler_SMP_Allocate_processor_exact
405  );
406}
407
408/*
409 *  This is unique to this scheduler because it is on the path
410 *  to _Scheduler_priority_affinity_SMP_Enqueue_ordered() which
411 *  invokes a scheduler unique get_lowest_scheduled helper.
412 */
413static Thread_Control *_Scheduler_priority_affinity_SMP_Enqueue_lifo(
414  Scheduler_Context *context,
415  Scheduler_Node    *node,
416  Thread_Control    *needs_help
417)
418{
419  return _Scheduler_priority_affinity_SMP_Enqueue_ordered(
420    context,
421    node,
422    needs_help,
423    _Scheduler_priority_affinity_SMP_Insert_priority_lifo_order,
424    _Scheduler_priority_SMP_Insert_ready_lifo,
425    _Scheduler_SMP_Insert_scheduled_lifo
426  );
427}
428
429/*
430 * This method is unique to this scheduler because it must
431 * invoke _Scheduler_SMP_Enqueue_scheduled_ordered() with
432 * this scheduler's get_highest_ready() helper.
433 */
434static Thread_Control *
435_Scheduler_priority_affinity_SMP_Enqueue_scheduled_ordered(
436  Scheduler_Context    *context,
437  Scheduler_Node       *node,
438  Chain_Node_order      order,
439  Scheduler_SMP_Insert  insert_ready,
440  Scheduler_SMP_Insert  insert_scheduled
441)
442{
443  return _Scheduler_SMP_Enqueue_scheduled_ordered(
444    context,
445    node,
446    order,
447    _Scheduler_priority_SMP_Extract_from_ready,
448    _Scheduler_priority_affinity_SMP_Get_highest_ready,
449    insert_ready,
450    insert_scheduled,
451    _Scheduler_priority_SMP_Move_from_ready_to_scheduled,
452    _Scheduler_SMP_Allocate_processor_exact
453  );
454}
455
456/*
457 *  This is unique to this scheduler because it is on the path
458 *  to _Scheduler_priority_affinity_SMP_Enqueue_scheduled__ordered() which
459 *  invokes a scheduler unique get_lowest_scheduled helper.
460 */
461static Thread_Control *_Scheduler_priority_affinity_SMP_Enqueue_scheduled_lifo(
462  Scheduler_Context *context,
463  Scheduler_Node    *node
464)
465{
466  return _Scheduler_priority_affinity_SMP_Enqueue_scheduled_ordered(
467    context,
468    node,
469    _Scheduler_SMP_Insert_priority_lifo_order,
470    _Scheduler_priority_SMP_Insert_ready_lifo,
471    _Scheduler_SMP_Insert_scheduled_lifo
472  );
473}
474
475/*
476 *  This is unique to this scheduler because it is on the path
477 *  to _Scheduler_priority_affinity_SMP_Enqueue_scheduled__ordered() which
478 *  invokes a scheduler unique get_lowest_scheduled helper.
479 */
480static Thread_Control *_Scheduler_priority_affinity_SMP_Enqueue_scheduled_fifo(
481  Scheduler_Context *context,
482  Scheduler_Node    *node
483)
484{
485  return _Scheduler_priority_affinity_SMP_Enqueue_scheduled_ordered(
486    context,
487    node,
488    _Scheduler_SMP_Insert_priority_fifo_order,
489    _Scheduler_priority_SMP_Insert_ready_fifo,
490    _Scheduler_SMP_Insert_scheduled_fifo
491  );
492}
493
494static bool _Scheduler_priority_affinity_SMP_Do_ask_for_help(
495  Scheduler_Context *context,
496  Thread_Control    *the_thread,
497  Scheduler_Node    *node
498)
499{
500  return _Scheduler_SMP_Ask_for_help(
501    context,
502    the_thread,
503    node,
504    _Scheduler_SMP_Insert_priority_lifo_order,
505    _Scheduler_priority_SMP_Insert_ready_lifo,
506    _Scheduler_SMP_Insert_scheduled_lifo,
507    _Scheduler_priority_SMP_Move_from_scheduled_to_ready,
508    _Scheduler_SMP_Get_lowest_scheduled,
509    _Scheduler_SMP_Allocate_processor_lazy
510  );
511}
512
513void _Scheduler_priority_affinity_SMP_Update_priority(
514  const Scheduler_Control *scheduler,
515  Thread_Control          *thread,
516  Scheduler_Node          *node
517)
518{
519  Scheduler_Context *context = _Scheduler_Get_context( scheduler );
520
521  _Scheduler_SMP_Update_priority(
522    context,
523    thread,
524    node,
525    _Scheduler_priority_SMP_Extract_from_ready,
526    _Scheduler_priority_SMP_Do_update,
527    _Scheduler_priority_affinity_SMP_Enqueue_fifo,
528    _Scheduler_priority_affinity_SMP_Enqueue_lifo,
529    _Scheduler_priority_affinity_SMP_Enqueue_scheduled_fifo,
530    _Scheduler_priority_affinity_SMP_Enqueue_scheduled_lifo,
531    _Scheduler_priority_affinity_SMP_Do_ask_for_help
532  );
533
534  /*
535   * Perform any thread migrations that are needed due to these changes.
536   */
537  _Scheduler_priority_affinity_SMP_Check_for_migrations( context );
538}
539
540bool _Scheduler_priority_affinity_SMP_Ask_for_help(
541  const Scheduler_Control *scheduler,
542  Thread_Control          *the_thread,
543  Scheduler_Node          *node
544)
545{
546  Scheduler_Context *context = _Scheduler_Get_context( scheduler );
547
548  return _Scheduler_priority_affinity_SMP_Do_ask_for_help( context, the_thread, node );
549}
550
551void _Scheduler_priority_affinity_SMP_Reconsider_help_request(
552  const Scheduler_Control *scheduler,
553  Thread_Control          *the_thread,
554  Scheduler_Node          *node
555)
556{
557  Scheduler_Context *context = _Scheduler_Get_context( scheduler );
558
559  _Scheduler_SMP_Reconsider_help_request(
560    context,
561    the_thread,
562    node,
563    _Scheduler_priority_SMP_Extract_from_ready
564  );
565}
566
567void _Scheduler_priority_affinity_SMP_Withdraw_node(
568  const Scheduler_Control *scheduler,
569  Thread_Control          *the_thread,
570  Scheduler_Node          *node,
571  Thread_Scheduler_state   next_state
572)
573{
574  Scheduler_Context *context = _Scheduler_Get_context( scheduler );
575
576  _Scheduler_SMP_Withdraw_node(
577    context,
578    the_thread,
579    node,
580    next_state,
581    _Scheduler_priority_SMP_Extract_from_ready,
582    _Scheduler_priority_affinity_SMP_Get_highest_ready,
583    _Scheduler_priority_SMP_Move_from_ready_to_scheduled,
584    _Scheduler_SMP_Allocate_processor_lazy
585  );
586}
587
588/*
589 * This is the public scheduler specific Change Priority operation.
590 */
591bool _Scheduler_priority_affinity_SMP_Get_affinity(
592  const Scheduler_Control *scheduler,
593  Thread_Control          *thread,
594  size_t                   cpusetsize,
595  cpu_set_t               *cpuset
596)
597{
598  Scheduler_priority_affinity_SMP_Node *node =
599    _Scheduler_priority_affinity_SMP_Thread_get_node(thread);
600
601  (void) scheduler;
602
603  if ( node->Affinity.setsize != cpusetsize ) {
604    return false;
605  }
606
607  CPU_COPY( cpuset, node->Affinity.set );
608  return true;
609}
610
611bool _Scheduler_priority_affinity_SMP_Set_affinity(
612  const Scheduler_Control *scheduler,
613  Thread_Control          *thread,
614  size_t                   cpusetsize,
615  const cpu_set_t         *cpuset
616)
617{
618  Scheduler_priority_affinity_SMP_Node *node;
619  States_Control                        current_state;
620
621  /*
622   * Validate that the cpset meets basic requirements.
623   */
624  if ( !_CPU_set_Is_valid( cpuset, cpusetsize ) ) {
625    return false;
626  }
627
628  node = _Scheduler_priority_affinity_SMP_Thread_get_node( thread );
629
630  /*
631   * The old and new set are the same, there is no point in
632   * doing anything.
633   */
634  if ( CPU_EQUAL_S( cpusetsize, cpuset, node->Affinity.set ) )
635    return true;
636
637  current_state = thread->current_state;
638
639  if ( _States_Is_ready( current_state ) ) {
640    _Scheduler_priority_affinity_SMP_Block( scheduler, thread, &node->Base.Base.Base );
641  }
642
643  CPU_COPY( node->Affinity.set, cpuset );
644
645  if ( _States_Is_ready( current_state ) ) {
646    /*
647     * FIXME: Do not ignore threads in need for help.
648     */
649    (void) _Scheduler_priority_affinity_SMP_Unblock( scheduler, thread, &node->Base.Base.Base );
650  }
651
652  return true;
653}
Note: See TracBrowser for help on using the repository browser.