source: rtems/cpukit/score/include/rtems/score/schedulersmpimpl.h @ 27783f6

4.11
Last change on this file since 27783f6 was 27783f6, checked in by Sebastian Huber <sebastian.huber@…>, on Jul 10, 2014 at 12:27:42 PM

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: 26.0 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 * The scheduler nodes can be in four states
39 * - @ref SCHEDULER_SMP_NODE_BLOCKED,
40 * - @ref SCHEDULER_SMP_NODE_SCHEDULED, and
41 * - @ref SCHEDULER_SMP_NODE_READY.
42 *
43 * State transitions are triggered via basic operations
44 * - _Scheduler_SMP_Enqueue_ordered(),
45 * - _Scheduler_SMP_Enqueue_scheduled_ordered(), and
46 * - _Scheduler_SMP_Block().
47 *
48 * @dot
49 * digraph {
50 *   node [style="filled"];
51 *
52 *   bs [label="BLOCKED"];
53 *   ss [label="SCHEDULED", fillcolor="green"];
54 *   rs [label="READY", fillcolor="red"];
55 *
56 *   edge [label="enqueue"];
57 *   edge [fontcolor="darkgreen", color="darkgreen"];
58 *
59 *   bs -> ss;
60 *
61 *   edge [fontcolor="red", color="red"];
62 *
63 *   bs -> rs;
64 *
65 *   edge [label="enqueue other"];
66 *
67 *   ss -> rs;
68 *
69 *   edge [label="block"];
70 *   edge [fontcolor="black", color="black"];
71 *
72 *   ss -> bs;
73 *   rs -> bs;
74 *
75 *   edge [label="block other"];
76 *   edge [fontcolor="darkgreen", color="darkgreen"];
77 *
78 *   rs -> ss;
79 * }
80 * @enddot
81 *
82 * During system initialization each processor of the scheduler instance starts
83 * with an idle thread assigned to it.  Lets have a look at an example with two
84 * idle threads I and J with priority 5.  We also have blocked threads A, B and
85 * C with priorities 1, 2 and 3 respectively.  The scheduler nodes are ordered
86 * with respect to the thread priority from left to right in the below
87 * diagrams.  The highest priority node (lowest priority number) is the
88 * leftmost node.  Since the processor assignment is independent of the thread
89 * priority the processor indices may move from one state to the other.
90 *
91 * @dot
92 * digraph {
93 *   node [style="filled"];
94 *   edge [dir="none"];
95 *   subgraph {
96 *     rank = same;
97 *
98 *     i [label="I (5)", fillcolor="green"];
99 *     j [label="J (5)", fillcolor="green"];
100 *     a [label="A (1)"];
101 *     b [label="B (2)"];
102 *     c [label="C (3)"];
103 *     i -> j;
104 *   }
105 *
106 *   subgraph {
107 *     rank = same;
108 *
109 *     p0 [label="PROCESSOR 0", shape="box"];
110 *     p1 [label="PROCESSOR 1", shape="box"];
111 *   }
112 *
113 *   i -> p0;
114 *   j -> p1;
115 * }
116 * @enddot
117 *
118 * Lets start A.  For this an enqueue operation is performed.
119 *
120 * @dot
121 * digraph {
122 *   node [style="filled"];
123 *   edge [dir="none"];
124 *
125 *   subgraph {
126 *     rank = same;
127 *
128 *     i [label="I (5)", fillcolor="green"];
129 *     j [label="J (5)", fillcolor="red"];
130 *     a [label="A (1)", fillcolor="green"];
131 *     b [label="B (2)"];
132 *     c [label="C (3)"];
133 *     a -> i;
134 *   }
135 *
136 *   subgraph {
137 *     rank = same;
138 *
139 *     p0 [label="PROCESSOR 0", shape="box"];
140 *     p1 [label="PROCESSOR 1", shape="box"];
141 *   }
142 *
143 *   i -> p0;
144 *   a -> p1;
145 * }
146 * @enddot
147 *
148 * Lets start C.
149 *
150 * @dot
151 * digraph {
152 *   node [style="filled"];
153 *   edge [dir="none"];
154 *
155 *   subgraph {
156 *     rank = same;
157 *
158 *     a [label="A (1)", fillcolor="green"];
159 *     c [label="C (3)", fillcolor="green"];
160 *     i [label="I (5)", fillcolor="red"];
161 *     j [label="J (5)", fillcolor="red"];
162 *     b [label="B (2)"];
163 *     a -> c;
164 *     i -> j;
165 *   }
166 *
167 *   subgraph {
168 *     rank = same;
169 *
170 *     p0 [label="PROCESSOR 0", shape="box"];
171 *     p1 [label="PROCESSOR 1", shape="box"];
172 *   }
173 *
174 *   c -> p0;
175 *   a -> p1;
176 * }
177 * @enddot
178 *
179 * Lets start B.
180 *
181 * @dot
182 * digraph {
183 *   node [style="filled"];
184 *   edge [dir="none"];
185 *
186 *   subgraph {
187 *     rank = same;
188 *
189 *     a [label="A (1)", fillcolor="green"];
190 *     b [label="B (2)", fillcolor="green"];
191 *     c [label="C (3)", fillcolor="red"];
192 *     i [label="I (5)", fillcolor="red"];
193 *     j [label="J (5)", fillcolor="red"];
194 *     a -> b;
195 *     c -> i -> j;
196 *   }
197 *
198 *   subgraph {
199 *     rank = same;
200 *
201 *     p0 [label="PROCESSOR 0", shape="box"];
202 *     p1 [label="PROCESSOR 1", shape="box"];
203 *   }
204 *
205 *   b -> p0;
206 *   a -> p1;
207 * }
208 * @enddot
209 *
210 * Lets change the priority of thread A to 4.
211 *
212 * @dot
213 * digraph {
214 *   node [style="filled"];
215 *   edge [dir="none"];
216 *
217 *   subgraph {
218 *     rank = same;
219 *
220 *     b [label="B (2)", fillcolor="green"];
221 *     c [label="C (3)", fillcolor="green"];
222 *     a [label="A (4)", fillcolor="red"];
223 *     i [label="I (5)", fillcolor="red"];
224 *     j [label="J (5)", fillcolor="red"];
225 *     b -> c;
226 *     a -> i -> j;
227 *   }
228 *
229 *   subgraph {
230 *     rank = same;
231 *
232 *     p0 [label="PROCESSOR 0", shape="box"];
233 *     p1 [label="PROCESSOR 1", shape="box"];
234 *   }
235 *
236 *   b -> p0;
237 *   c -> p1;
238 * }
239 * @enddot
240 *
241 * Now perform a blocking operation with thread B.  Please note that thread A
242 * migrated now from processor 0 to processor 1 and thread C still executes on
243 * processor 1.
244 *
245 * @dot
246 * digraph {
247 *   node [style="filled"];
248 *   edge [dir="none"];
249 *
250 *   subgraph {
251 *     rank = same;
252 *
253 *     c [label="C (3)", fillcolor="green"];
254 *     a [label="A (4)", fillcolor="green"];
255 *     i [label="I (5)", fillcolor="red"];
256 *     j [label="J (5)", fillcolor="red"];
257 *     b [label="B (2)"];
258 *     c -> a;
259 *     i -> j;
260 *   }
261 *
262 *   subgraph {
263 *     rank = same;
264 *
265 *     p0 [label="PROCESSOR 0", shape="box"];
266 *     p1 [label="PROCESSOR 1", shape="box"];
267 *   }
268 *
269 *   a -> p0;
270 *   c -> p1;
271 * }
272 * @enddot
273 *
274 * @{
275 */
276
277typedef Scheduler_Node *( *Scheduler_SMP_Get_highest_ready )(
278  Scheduler_Context *context,
279  Scheduler_Node    *node
280);
281
282typedef Scheduler_Node *( *Scheduler_SMP_Get_lowest_scheduled )(
283  Scheduler_Context *context,
284  Scheduler_Node    *filter,
285  Chain_Node_order   order
286);
287
288typedef void ( *Scheduler_SMP_Extract )(
289  Scheduler_Context *context,
290  Scheduler_Node    *node_to_extract
291);
292
293typedef void ( *Scheduler_SMP_Insert )(
294  Scheduler_Context *context,
295  Scheduler_Node    *node_to_insert
296);
297
298typedef void ( *Scheduler_SMP_Move )(
299  Scheduler_Context *context,
300  Scheduler_Node    *node_to_move
301);
302
303typedef void ( *Scheduler_SMP_Update )(
304  Scheduler_Context *context,
305  Scheduler_Node    *node_to_update,
306  Priority_Control   new_priority
307);
308
309typedef Thread_Control *( *Scheduler_SMP_Enqueue )(
310  Scheduler_Context *context,
311  Scheduler_Node    *node_to_enqueue,
312  Thread_Control    *needs_help
313);
314
315typedef Thread_Control *( *Scheduler_SMP_Enqueue_scheduled )(
316  Scheduler_Context *context,
317  Scheduler_Node    *node_to_enqueue
318);
319
320typedef void ( *Scheduler_SMP_Allocate_processor )(
321  Scheduler_Context *context,
322  Thread_Control    *scheduled,
323  Thread_Control    *victim
324);
325
326static inline bool _Scheduler_SMP_Insert_priority_lifo_order(
327  const Chain_Node *to_insert,
328  const Chain_Node *next
329)
330{
331  const Scheduler_SMP_Node *node_to_insert =
332    (const Scheduler_SMP_Node *) to_insert;
333  const Scheduler_SMP_Node *node_next =
334    (const Scheduler_SMP_Node *) next;
335
336  return node_to_insert->priority <= node_next->priority;
337}
338
339static inline bool _Scheduler_SMP_Insert_priority_fifo_order(
340  const Chain_Node *to_insert,
341  const Chain_Node *next
342)
343{
344  const Scheduler_SMP_Node *node_to_insert =
345    (const Scheduler_SMP_Node *) to_insert;
346  const Scheduler_SMP_Node *node_next =
347    (const Scheduler_SMP_Node *) next;
348
349  return node_to_insert->priority < node_next->priority;
350}
351
352static inline Scheduler_SMP_Context *_Scheduler_SMP_Get_self(
353  Scheduler_Context *context
354)
355{
356  return (Scheduler_SMP_Context *) context;
357}
358
359static inline void _Scheduler_SMP_Initialize(
360  Scheduler_SMP_Context *self
361)
362{
363  _Chain_Initialize_empty( &self->Scheduled );
364  _Chain_Initialize_empty( &self->Idle_threads );
365}
366
367static inline Scheduler_SMP_Node *_Scheduler_SMP_Thread_get_node(
368  Thread_Control *thread
369)
370{
371  return (Scheduler_SMP_Node *) _Scheduler_Thread_get_node( thread );
372}
373
374static inline Scheduler_SMP_Node *_Scheduler_SMP_Thread_get_own_node(
375  Thread_Control *thread
376)
377{
378  return (Scheduler_SMP_Node *) _Scheduler_Thread_get_own_node( thread );
379}
380
381static inline Scheduler_SMP_Node *_Scheduler_SMP_Node_downcast(
382  Scheduler_Node *node
383)
384{
385  return (Scheduler_SMP_Node *) node;
386}
387
388static inline void _Scheduler_SMP_Node_initialize(
389  Scheduler_SMP_Node *node,
390  Thread_Control     *thread
391)
392{
393  _Scheduler_Node_do_initialize( &node->Base, thread );
394  node->state = SCHEDULER_SMP_NODE_BLOCKED;
395}
396
397static inline void _Scheduler_SMP_Node_update_priority(
398  Scheduler_SMP_Node *node,
399  Priority_Control    new_priority
400)
401{
402  node->priority = new_priority;
403}
404
405extern const bool _Scheduler_SMP_Node_valid_state_changes[ 3 ][ 3 ];
406
407static inline void _Scheduler_SMP_Node_change_state(
408  Scheduler_SMP_Node      *node,
409  Scheduler_SMP_Node_state new_state
410)
411{
412  _Assert(
413    _Scheduler_SMP_Node_valid_state_changes[ node->state ][ new_state ]
414  );
415
416  node->state = new_state;
417}
418
419static inline bool _Scheduler_SMP_Is_processor_owned_by_us(
420  const Scheduler_Context *context,
421  const Per_CPU_Control   *cpu
422)
423{
424  return cpu->scheduler_context == context;
425}
426
427static inline Thread_Control *_Scheduler_SMP_Get_idle_thread(
428  Scheduler_Context *context
429)
430{
431  Scheduler_SMP_Context *self = _Scheduler_SMP_Get_self( context );
432  Thread_Control *idle = (Thread_Control *)
433    _Chain_Get_first_unprotected( &self->Idle_threads );
434
435  _Assert( &idle->Object.Node != _Chain_Tail( &self->Idle_threads ) );
436
437  return idle;
438}
439
440static inline void _Scheduler_SMP_Release_idle_thread(
441  Scheduler_Context *context,
442  Thread_Control    *idle
443)
444{
445  Scheduler_SMP_Context *self = _Scheduler_SMP_Get_self( context );
446
447  _Chain_Prepend_unprotected( &self->Idle_threads, &idle->Object.Node );
448}
449
450static inline void _Scheduler_SMP_Allocate_processor_lazy(
451  Scheduler_Context *context,
452  Thread_Control    *scheduled_thread,
453  Thread_Control    *victim_thread
454)
455{
456  Per_CPU_Control *scheduled_cpu = _Thread_Get_CPU( scheduled_thread );
457  Per_CPU_Control *victim_cpu = _Thread_Get_CPU( victim_thread );
458  Per_CPU_Control *cpu_self = _Per_CPU_Get();
459  Thread_Control *heir;
460
461  _Assert( _ISR_Get_level() != 0 );
462
463  if ( _Thread_Is_executing_on_a_processor( scheduled_thread ) ) {
464    if ( _Scheduler_SMP_Is_processor_owned_by_us( context, scheduled_cpu ) ) {
465      heir = scheduled_cpu->heir;
466      _Thread_Dispatch_update_heir(
467        cpu_self,
468        scheduled_cpu,
469        scheduled_thread
470      );
471    } else {
472      /* We have to force a migration to our processor set */
473      _Assert(
474        scheduled_thread->Scheduler.debug_real_cpu->heir != scheduled_thread
475      );
476      heir = scheduled_thread;
477    }
478  } else {
479    heir = scheduled_thread;
480  }
481
482  if ( heir != victim_thread ) {
483    _Thread_Set_CPU( heir, victim_cpu );
484    _Thread_Dispatch_update_heir( cpu_self, victim_cpu, heir );
485  }
486}
487
488static inline void _Scheduler_SMP_Allocate_processor(
489  Scheduler_Context                *context,
490  Scheduler_Node                   *scheduled,
491  Scheduler_Node                   *victim,
492  Scheduler_SMP_Allocate_processor  allocate_processor
493)
494{
495  Thread_Control *scheduled_thread = _Scheduler_Node_get_user( scheduled );
496  Thread_Control *victim_thread = _Scheduler_Node_get_user( victim );
497
498  _Scheduler_SMP_Node_change_state(
499    _Scheduler_SMP_Node_downcast( scheduled ),
500    SCHEDULER_SMP_NODE_SCHEDULED
501  );
502  _Scheduler_Thread_change_state( scheduled_thread, THREAD_SCHEDULER_SCHEDULED );
503
504  ( *allocate_processor )( context, scheduled_thread, victim_thread );
505}
506
507static inline Scheduler_Node *_Scheduler_SMP_Get_lowest_scheduled(
508  Scheduler_Context *context,
509  Scheduler_Node    *filter,
510  Chain_Node_order   order
511)
512{
513  Scheduler_SMP_Context *self = _Scheduler_SMP_Get_self( context );
514  Chain_Control *scheduled = &self->Scheduled;
515  Scheduler_Node *lowest_scheduled =
516    (Scheduler_Node *) _Chain_Last( scheduled );
517
518  (void) filter;
519  (void) order;
520
521  _Assert( &lowest_scheduled->Node != _Chain_Tail( scheduled ) );
522
523  return lowest_scheduled;
524}
525
526static inline Thread_Control *_Scheduler_SMP_Enqueue_to_scheduled(
527  Scheduler_Context                *context,
528  Scheduler_Node                   *node,
529  Scheduler_Node                   *lowest_scheduled,
530  Scheduler_SMP_Insert              insert_scheduled,
531  Scheduler_SMP_Move                move_from_scheduled_to_ready,
532  Scheduler_SMP_Allocate_processor  allocate_processor
533)
534{
535  Thread_Control *user = _Scheduler_Node_get_user( node );
536  Thread_Control *lowest_scheduled_user =
537    _Scheduler_Node_get_user( lowest_scheduled );
538  Thread_Control *needs_help;
539  Thread_Control *idle;
540
541  _Scheduler_SMP_Node_change_state(
542    _Scheduler_SMP_Node_downcast( lowest_scheduled ),
543    SCHEDULER_SMP_NODE_READY
544  );
545  _Scheduler_Thread_change_state(
546    lowest_scheduled_user,
547    THREAD_SCHEDULER_READY
548  );
549
550  _Scheduler_Thread_set_node( user, node );
551
552  _Scheduler_SMP_Allocate_processor(
553    context,
554    node,
555    lowest_scheduled,
556    allocate_processor
557  );
558
559  ( *insert_scheduled )( context, node );
560  ( *move_from_scheduled_to_ready )( context, lowest_scheduled );
561
562  idle = _Scheduler_Release_idle_thread(
563    context,
564    lowest_scheduled,
565    _Scheduler_SMP_Release_idle_thread
566  );
567  if ( idle == NULL ) {
568    needs_help = lowest_scheduled_user;
569  } else {
570    needs_help = NULL;
571  }
572
573  return needs_help;
574}
575
576/**
577 * @brief Enqueues a node according to the specified order function.
578 *
579 * The node must not be in the scheduled state.
580 *
581 * @param[in] context The scheduler instance context.
582 * @param[in] node The node to enqueue.
583 * @param[in] needs_help The thread needing help in case the node cannot be
584 *   scheduled.
585 * @param[in] order The order function.
586 * @param[in] insert_ready Function to insert a node into the set of ready
587 *   nodes.
588 * @param[in] insert_scheduled Function to insert a node into the set of
589 *   scheduled nodes.
590 * @param[in] move_from_scheduled_to_ready Function to move a node from the set
591 *   of scheduled nodes to the set of ready nodes.
592 * @param[in] get_lowest_scheduled Function to select the node from the
593 *   scheduled nodes to replace.  It may not be possible to find one, in this
594 *   case a pointer must be returned so that the order functions returns false
595 *   if this pointer is passed as the second argument to the order function.
596 * @param[in] allocate_processor Function to allocate a processor to a node
597 *   based on the rules of the scheduler.
598 */
599static inline Thread_Control *_Scheduler_SMP_Enqueue_ordered(
600  Scheduler_Context                  *context,
601  Scheduler_Node                     *node,
602  Thread_Control                     *needs_help,
603  Chain_Node_order                    order,
604  Scheduler_SMP_Insert                insert_ready,
605  Scheduler_SMP_Insert                insert_scheduled,
606  Scheduler_SMP_Move                  move_from_scheduled_to_ready,
607  Scheduler_SMP_Get_lowest_scheduled  get_lowest_scheduled,
608  Scheduler_SMP_Allocate_processor    allocate_processor
609)
610{
611  Scheduler_Node *lowest_scheduled =
612    ( *get_lowest_scheduled )( context, node, order );
613
614  if ( ( *order )( &node->Node, &lowest_scheduled->Node ) ) {
615    needs_help = _Scheduler_SMP_Enqueue_to_scheduled(
616      context,
617      node,
618      lowest_scheduled,
619      insert_scheduled,
620      move_from_scheduled_to_ready,
621      allocate_processor
622    );
623  } else {
624    ( *insert_ready )( context, node );
625  }
626
627  return needs_help;
628}
629
630/**
631 * @brief Enqueues a scheduled node according to the specified order
632 * function.
633 *
634 * @param[in] context The scheduler instance context.
635 * @param[in] node The node to enqueue.
636 * @param[in] order The order function.
637 * @param[in] extract_from_ready Function to extract a node from the set of
638 *   ready nodes.
639 * @param[in] get_highest_ready Function to get the highest ready node.
640 * @param[in] insert_ready Function to insert a node into the set of ready
641 *   nodes.
642 * @param[in] insert_scheduled Function to insert a node into the set of
643 *   scheduled nodes.
644 * @param[in] move_from_ready_to_scheduled Function to move a node from the set
645 *   of ready nodes to the set of scheduled nodes.
646 * @param[in] allocate_processor Function to allocate a processor to a node
647 *   based on the rules of the scheduler.
648 */
649static inline Thread_Control *_Scheduler_SMP_Enqueue_scheduled_ordered(
650  Scheduler_Context                *context,
651  Scheduler_Node                   *node,
652  Chain_Node_order                  order,
653  Scheduler_SMP_Extract             extract_from_ready,
654  Scheduler_SMP_Get_highest_ready   get_highest_ready,
655  Scheduler_SMP_Insert              insert_ready,
656  Scheduler_SMP_Insert              insert_scheduled,
657  Scheduler_SMP_Move                move_from_ready_to_scheduled,
658  Scheduler_SMP_Allocate_processor  allocate_processor
659)
660{
661  Thread_Control *needs_help;
662
663  while ( true ) {
664    Scheduler_Node *highest_ready = ( *get_highest_ready )( context, node );
665
666    /*
667     * The node has been extracted from the scheduled chain.  We have to place
668     * it now on the scheduled or ready set.
669     */
670    if ( ( *order )( &node->Node, &highest_ready->Node ) ) {
671      ( *insert_scheduled )( context, node );
672
673      needs_help = NULL;
674
675      break;
676    } else if (
677      _Scheduler_Try_to_schedule_node(
678        context,
679        highest_ready,
680        _Scheduler_SMP_Get_idle_thread
681      )
682    ) {
683      Thread_Control *user = _Scheduler_Node_get_user( node );
684      Thread_Control *idle;
685
686      _Scheduler_SMP_Node_change_state(
687        _Scheduler_SMP_Node_downcast( node ),
688        SCHEDULER_SMP_NODE_READY
689      );
690      _Scheduler_Thread_change_state( user, THREAD_SCHEDULER_READY );
691
692      _Scheduler_SMP_Allocate_processor(
693        context,
694        highest_ready,
695        node,
696        allocate_processor
697      );
698
699      ( *insert_ready )( context, node );
700      ( *move_from_ready_to_scheduled )( context, highest_ready );
701
702      idle = _Scheduler_Release_idle_thread(
703        context,
704        node,
705        _Scheduler_SMP_Release_idle_thread
706      );
707      if ( idle == NULL ) {
708        needs_help = user;
709      } else {
710        needs_help = NULL;
711      }
712
713      break;
714    } else {
715      _Scheduler_SMP_Node_change_state(
716        _Scheduler_SMP_Node_downcast( highest_ready ),
717        SCHEDULER_SMP_NODE_BLOCKED
718      );
719
720      ( *extract_from_ready )( context, highest_ready );
721    }
722  }
723
724  return needs_help;
725}
726
727static inline void _Scheduler_SMP_Extract_from_scheduled(
728  Scheduler_Node *node
729)
730{
731  _Chain_Extract_unprotected( &node->Node );
732}
733
734static inline void _Scheduler_SMP_Schedule_highest_ready(
735  Scheduler_Context                *context,
736  Scheduler_Node                   *victim,
737  Scheduler_SMP_Extract             extract_from_ready,
738  Scheduler_SMP_Get_highest_ready   get_highest_ready,
739  Scheduler_SMP_Move                move_from_ready_to_scheduled,
740  Scheduler_SMP_Allocate_processor  allocate_processor
741)
742{
743  while ( true ) {
744    Scheduler_Node *highest_ready = ( *get_highest_ready )( context, victim );
745
746    if (
747      _Scheduler_Try_to_schedule_node(
748        context,
749        highest_ready,
750        _Scheduler_SMP_Get_idle_thread
751      )
752    ) {
753      _Scheduler_SMP_Allocate_processor(
754        context,
755        highest_ready,
756        victim,
757        allocate_processor
758      );
759
760      ( *move_from_ready_to_scheduled )( context, highest_ready );
761
762      break;
763    } else {
764      _Scheduler_SMP_Node_change_state(
765        _Scheduler_SMP_Node_downcast( highest_ready ),
766        SCHEDULER_SMP_NODE_BLOCKED
767      );
768
769      ( *extract_from_ready )( context, highest_ready );
770    }
771  }
772}
773
774/**
775 * @brief Blocks a thread.
776 *
777 * @param[in] context The scheduler instance context.
778 * @param[in] thread The thread of the scheduling operation.
779 * @param[in] extract_from_ready Function to extract a node from the set of
780 *   ready nodes.
781 * @param[in] get_highest_ready Function to get the highest ready node.
782 * @param[in] move_from_ready_to_scheduled Function to move a node from the set
783 *   of ready nodes to the set of scheduled nodes.
784 */
785static inline void _Scheduler_SMP_Block(
786  Scheduler_Context                *context,
787  Thread_Control                   *thread,
788  Scheduler_SMP_Extract             extract_from_ready,
789  Scheduler_SMP_Get_highest_ready   get_highest_ready,
790  Scheduler_SMP_Move                move_from_ready_to_scheduled,
791  Scheduler_SMP_Allocate_processor  allocate_processor
792)
793{
794  Scheduler_SMP_Node *node = _Scheduler_SMP_Thread_get_node( thread );
795  bool is_scheduled = node->state == SCHEDULER_SMP_NODE_SCHEDULED;
796  bool block = _Scheduler_Block_node(
797    context,
798    &node->Base,
799    is_scheduled,
800    _Scheduler_SMP_Get_idle_thread
801  );
802
803  if ( block ) {
804    _Scheduler_SMP_Node_change_state( node, SCHEDULER_SMP_NODE_BLOCKED );
805
806    if ( is_scheduled ) {
807      _Scheduler_SMP_Extract_from_scheduled( &node->Base );
808
809      _Scheduler_SMP_Schedule_highest_ready(
810        context,
811        &node->Base,
812        extract_from_ready,
813        get_highest_ready,
814        move_from_ready_to_scheduled,
815        allocate_processor
816      );
817    } else {
818      ( *extract_from_ready )( context, &node->Base );
819    }
820  }
821}
822
823static inline Thread_Control *_Scheduler_SMP_Unblock(
824  Scheduler_Context             *context,
825  Thread_Control                *thread,
826  Scheduler_SMP_Enqueue          enqueue_fifo
827)
828{
829  Scheduler_SMP_Node *node = _Scheduler_SMP_Thread_get_node( thread );
830  bool is_scheduled = node->state == SCHEDULER_SMP_NODE_SCHEDULED;
831  bool unblock = _Scheduler_Unblock_node(
832    context,
833    thread,
834    &node->Base,
835    is_scheduled,
836    _Scheduler_SMP_Release_idle_thread
837  );
838  Thread_Control *needs_help;
839
840  if ( unblock ) {
841    _Scheduler_SMP_Node_change_state( node, SCHEDULER_SMP_NODE_READY );
842
843    needs_help = ( *enqueue_fifo )( context, &node->Base, thread );
844  } else {
845    needs_help = NULL;
846  }
847
848  return needs_help;
849}
850
851static inline Thread_Control *_Scheduler_SMP_Change_priority(
852  Scheduler_Context               *context,
853  Thread_Control                  *thread,
854  Priority_Control                 new_priority,
855  bool                             prepend_it,
856  Scheduler_SMP_Extract            extract_from_ready,
857  Scheduler_SMP_Update             update,
858  Scheduler_SMP_Enqueue            enqueue_fifo,
859  Scheduler_SMP_Enqueue            enqueue_lifo,
860  Scheduler_SMP_Enqueue_scheduled  enqueue_scheduled_fifo,
861  Scheduler_SMP_Enqueue_scheduled  enqueue_scheduled_lifo
862)
863{
864  Scheduler_SMP_Node *node = _Scheduler_SMP_Thread_get_own_node( thread );
865  Thread_Control *needs_help;
866
867  if ( node->state == SCHEDULER_SMP_NODE_SCHEDULED ) {
868    _Scheduler_SMP_Extract_from_scheduled( &node->Base );
869
870    ( *update )( context, &node->Base, new_priority );
871
872    if ( prepend_it ) {
873      needs_help = ( *enqueue_scheduled_lifo )( context, &node->Base );
874    } else {
875      needs_help = ( *enqueue_scheduled_fifo )( context, &node->Base );
876    }
877  } else if ( node->state == SCHEDULER_SMP_NODE_READY ) {
878    ( *extract_from_ready )( context, &node->Base );
879
880    ( *update )( context, &node->Base, new_priority );
881
882    if ( prepend_it ) {
883      needs_help = ( *enqueue_lifo )( context, &node->Base, NULL );
884    } else {
885      needs_help = ( *enqueue_fifo )( context, &node->Base, NULL );
886    }
887  } else {
888    ( *update )( context, &node->Base, new_priority );
889
890    needs_help = NULL;
891  }
892
893  return needs_help;
894}
895
896static inline Thread_Control *_Scheduler_SMP_Ask_for_help(
897  Scheduler_Context                  *context,
898  Thread_Control                     *offers_help,
899  Thread_Control                     *needs_help,
900  Scheduler_SMP_Enqueue               enqueue_fifo
901)
902{
903  Scheduler_SMP_Node *node = _Scheduler_SMP_Thread_get_own_node( offers_help );
904  Thread_Control *next_needs_help = NULL;
905  Thread_Control *previous_accepts_help;
906
907  previous_accepts_help = node->Base.accepts_help;
908  node->Base.accepts_help = needs_help;
909
910  switch ( node->state ) {
911    case SCHEDULER_SMP_NODE_READY:
912      next_needs_help =
913        _Scheduler_Ask_ready_node_for_help( &node->Base, needs_help );
914      break;
915    case SCHEDULER_SMP_NODE_SCHEDULED:
916      next_needs_help = _Scheduler_Ask_scheduled_node_for_help(
917        context,
918        &node->Base,
919        offers_help,
920        needs_help,
921        previous_accepts_help,
922        _Scheduler_SMP_Release_idle_thread
923      );
924      break;
925    case SCHEDULER_SMP_NODE_BLOCKED:
926      if (
927        _Scheduler_Ask_blocked_node_for_help(
928          context,
929          &node->Base,
930          offers_help,
931          needs_help
932        )
933      ) {
934        _Scheduler_SMP_Node_change_state( node, SCHEDULER_SMP_NODE_READY );
935
936        next_needs_help = ( *enqueue_fifo )(
937          context,
938          &node->Base,
939          needs_help
940        );
941      }
942      break;
943  }
944
945  return next_needs_help;
946}
947
948static inline Thread_Control *_Scheduler_SMP_Yield(
949  Scheduler_Context               *context,
950  Thread_Control                  *thread,
951  Scheduler_SMP_Extract            extract_from_ready,
952  Scheduler_SMP_Enqueue            enqueue_fifo,
953  Scheduler_SMP_Enqueue_scheduled  enqueue_scheduled_fifo
954)
955{
956  Scheduler_SMP_Node *node = _Scheduler_SMP_Thread_get_node( thread );
957  Thread_Control *needs_help;
958
959  if ( node->state == SCHEDULER_SMP_NODE_SCHEDULED ) {
960    _Scheduler_SMP_Extract_from_scheduled( &node->Base );
961
962    needs_help = ( *enqueue_scheduled_fifo )( context, &node->Base );
963  } else {
964    ( *extract_from_ready )( context, &node->Base );
965
966    needs_help = ( *enqueue_fifo )( context, &node->Base, NULL );
967  }
968
969  return needs_help;
970}
971
972static inline void _Scheduler_SMP_Insert_scheduled_lifo(
973  Scheduler_Context *context,
974  Scheduler_Node    *node_to_insert
975)
976{
977  Scheduler_SMP_Context *self = _Scheduler_SMP_Get_self( context );
978
979  _Chain_Insert_ordered_unprotected(
980    &self->Scheduled,
981    &node_to_insert->Node,
982    _Scheduler_SMP_Insert_priority_lifo_order
983  );
984}
985
986static inline void _Scheduler_SMP_Insert_scheduled_fifo(
987  Scheduler_Context *context,
988  Scheduler_Node    *node_to_insert
989)
990{
991  Scheduler_SMP_Context *self = _Scheduler_SMP_Get_self( context );
992
993  _Chain_Insert_ordered_unprotected(
994    &self->Scheduled,
995    &node_to_insert->Node,
996    _Scheduler_SMP_Insert_priority_fifo_order
997  );
998}
999
1000/** @} */
1001
1002#ifdef __cplusplus
1003}
1004#endif /* __cplusplus */
1005
1006#endif /* _RTEMS_SCORE_SCHEDULERSMPIMPL_H */
Note: See TracBrowser for help on using the repository browser.