source: rtems/cpukit/score/src/schedulersimplesmpschedule.c @ 4fc370e

4.115
Last change on this file since 4fc370e was 32815a2, checked in by Joel Sherrill <joel.sherrill@…>, on 04/24/12 at 21:08:16

Simple SMP Scheduler - Fix typo which likely broke scheduling

  • Property mode set to 100644
File size: 8.4 KB
Line 
1/**
2 *  @file
3 *
4 *  Scheduler Simple SMP Handler / Schedule
5 */
6
7/*
8 *  COPYRIGHT (c) 2011- 2012.
9 *  On-Line Applications Research Corporation (OAR).
10 *
11 *  The license and distribution terms for this file may be
12 *  found in found in the file LICENSE in this distribution or at
13 *  http://www.rtems.com/license/LICENSE.
14 */
15
16#if HAVE_CONFIG_H
17#include "config.h"
18#endif
19
20#include <rtems/system.h>
21#include <rtems/score/smp.h>
22#include <rtems/score/schedulersimplesmp.h>
23
24#include <stdio.h>
25
26/*
27 *  The following is very useful on the scheduler simulator when debugging
28 *  this algorithm.  You are not likely to be able to print like this when
29 *  running on a real system.
30 *
31 *  NOTE: This is NOT using RTEMS_DEBUG because this is not consistency
32 *        checking and is VERY VERY noisy.  It is just for debugging
33 *        the algorithm.
34 */
35#if 0
36#define D(format,...) printk( format, __VA_ARGS__)
37#else
38#define D(format,...)
39#endif
40
41/* Declaration to avoid warnings */
42bool _Scheduler_simple_smp_Assign(
43  Thread_Control *consider
44);
45
46/**
47 *  @brief Assign Heir Thread to CPU
48 *
49 *  This method attempts to find a core for the thread under consideration
50 *  (@a consider) to become heir of.  The placement takes into account
51 *  priority, preemptibility, and length of time on core.
52 *
53 *  Combined with the loop in _Scheduler_simple_smp_Schedule, it attempts
54 *  to faithfully implement the behaviour of the Deterministic Priority
55 *  Scheduler while spreading the threads across multiple cores.
56 *
57 *  @param[in] consider is the thread under consideration.  This means
58 *             that the method is looking for the best core to place it
59 *             as heir.
60 *
61 *  @return This method returns true if it was able to make @a consider
62 *          the heir on a core and false otherwise.  When this returns
63 *          false, there is no point in attempting to place an heir of
64 *          of lower priority.
65 */
66bool _Scheduler_simple_smp_Assign(
67  Thread_Control *consider
68)
69{
70  bool            found;       /* have we found a cpu to place it on? */
71  uint32_t        found_cpu;   /* CPU to place this thread */
72  bool            blocked;     /* CPU has blocked thread? */
73  Thread_Control *pheir;       /* heir on found cpu to potentially replace */
74  Thread_Control *h;
75  Thread_Control *e;
76  uint32_t        cpu;
77
78  /*
79   *  Initialize various variables to indicate we have not found
80   *  a potential core for the thread under consideration.
81   */
82  found     = false;
83  blocked   = false;
84  found_cpu = 0;
85  pheir     = NULL;
86
87  for ( cpu=0 ; cpu < _SMP_Processor_count ; cpu++ ) {
88    D( "SCHED CPU=%d consider=0x%08x ASSIGN\n", cpu, consider->Object.id );
89
90    /*
91     *  If the thread under consideration is already executing or
92     *  heir, then we don't have a better option for it.
93     */
94    e = _Per_CPU_Information[cpu].executing;
95    if ( e == consider ) {
96      D( "SCHED CPU=%d Executing=0x%08x considering=0x%08x ASSIGNED\n",
97        cpu, e->Object.id, consider->Object.id );
98      return true;
99    }
100
101    if ( !_States_Is_ready( e->current_state ) ) {
102      pheir     = e;
103      found_cpu = cpu;
104      found     = true;
105      blocked   = true;
106      D( "SCHED CPU=%d PHeir=0x%08x considering=0x%08x BLOCKED\n",
107        cpu, e->Object.id, consider->Object.id );
108      continue;
109    }
110
111    h = _Per_CPU_Information[cpu].heir;
112    if ( h == consider ) {
113      D( "SCHED CPU=%d Heir=0x%08x considering=0x%08x ASSIGNED\n",
114        cpu, h->Object.id, consider->Object.id );
115      return true;
116    }
117
118    if ( blocked )
119      continue;
120
121    /*
122     *  If we haven't found a potential CPU to locate the thread
123     *  under consideration on, we need to consider if this is a
124     *  more important threads first (e.g. priority <).
125     *
126     *  But when a thread changes its priority and ends up at the end of
127     *  the priority group for the new heir, we also need to schedule
128     *  a new heir.  This is the "=" part of the check.
129     */
130    if ( !found ) {
131      if ( consider->current_priority <= h->current_priority ) {
132        pheir     = h;
133        found_cpu = cpu;
134        found     = true;
135        D( "SCHED CPU=%d PHeir=0x%08x considering=0x%08x MAYBE #1\n",
136          cpu, h->Object.id, consider->Object.id );
137      }
138
139      continue;
140    }
141
142    /*
143     *  ASSERTION: (found == true)
144     *
145     *  Past this point, we have found a potential heir and are considering
146     *  whether the thread is better placed on another core. It is desirable
147     *  to preempt the lowest priority thread using time on core and
148     *  preemptibility as additional factors.
149     */
150
151    /*
152     *  If we have found a potential CPU on which to make the
153     *  thread under consideration the heir, then we need to
154     *  check if the current CPU is a more appropriate place
155     *  for this thread to be placed.
156     *
157     *  Check 1: heir of potential CPU is more important
158     *           then heir of current CPU.  We want to
159     *           replace the least important thread possible.
160     */
161    if ( h->current_priority > pheir->current_priority ) {
162      pheir = h;
163      found_cpu = cpu;
164      D( "SCHED CPU=%d PHeir=0x%08x considering=0x%08x MAYBE #2\n",
165        cpu, h->Object.id, consider->Object.id );
166      continue;
167    }
168
169    /*
170     *  If the current heir is more important than the potential
171     *  heir, then we should not consider it further in scheduling.
172     */
173    if ( h->current_priority < pheir->current_priority )
174      continue;
175
176    /*
177     *  ASSERTION: (h->current_priority == pheir->current_priority).
178     *
179     *  Past this point, this means we are considering the length of time
180     *  the thread has spent on the time on the CPU core and if it is
181     *  preemptible.
182     */
183
184    /*
185     *  If heir of potential CPU and of the current CPU are of the SAME
186     *  priority, then which has been running longer?
187     *
188     *           Which CPU has had its executing thread longer?
189     */
190    if ( _Timestamp_Less_than(
191           &_Per_CPU_Information[cpu].time_of_last_context_switch,
192           &_Per_CPU_Information[found_cpu].time_of_last_context_switch
193         ) ) {
194      pheir = h;
195      found_cpu = cpu;
196      D( "SCHED CPU=%d PHeir=0x%08x considering=0x%08x LONGER\n",
197        cpu, h->Object.id, consider->Object.id );
198      continue;
199    }
200
201    /*
202     *  If we are looking at a core with a non-preemptible thread
203     *  for potential placement, then favor a core with a preeemtible
204     *  thread of the same priority.  This should help avoid priority
205     *  inversions and let threads run earlier.
206     */
207    if ( !pheir->is_preemptible && h->is_preemptible ) {
208      D( "SCHED CPU=%d PHeir==0x%08x is NOT PREEMPTIBLE\n",
209        cpu, pheir->Object.id );
210      pheir = h;
211      found_cpu = cpu;
212      D( "SCHED CPU=%d PHeir=0x%08x considering=0x%08x PREEMPTIBLE\n",
213        cpu, h->Object.id, consider->Object.id );
214      continue;
215
216    }
217  }
218
219  /*
220   *  If we found a cpu to make this thread heir of, then we
221   *  need to consider whether we need a dispatch on that CPU.
222   */
223  if ( found ) {
224    e = _Per_CPU_Information[found_cpu].executing;
225    D( "SCHED CPU=%d executing=0x%08x considering=0x%08x FOUND\n",
226      found_cpu, e->Object.id, consider->Object.id );
227    _Per_CPU_Information[found_cpu].heir = consider;
228    if ( !_States_Is_ready( e->current_state ) ) {
229       D( "SCHED CPU=%d executing not ready dispatch needed\n", found_cpu);
230      _Per_CPU_Information[found_cpu].dispatch_necessary = true;
231    } else if ( consider->current_priority < e->current_priority ) {
232      if ( e->is_preemptible || consider->current_priority == 0 ) {
233         D( "SCHED CPU=%d preempting\n", found_cpu);
234        _Per_CPU_Information[found_cpu].dispatch_necessary = true;
235      }
236    }
237  }
238
239  /*
240   *  Return true to indicate we changed an heir.  This indicates
241   *  scheduling needs to examine more threads.
242   */
243  return found;
244}
245
246/*
247 *  Reschedule threads -- select heirs for all cores
248 */
249void _Scheduler_simple_smp_Schedule(void)
250{
251  Chain_Control  *c;
252  Chain_Node     *n;
253  Thread_Control *t;
254  uint32_t        cpu;
255
256  c   = (Chain_Control *)_Scheduler.information;
257  cpu = 0;
258
259  /*
260   *  Iterate over the first N (where N is the number of CPU cores) threads
261   *  on the ready chain.  Attempt to assign each as heir on a core.  When
262   *  unable to assign a thread as a new heir, then stop.
263   */
264  for (n = _Chain_First(c); !_Chain_Is_tail(c, n); n = _Chain_Next(n)) {
265    t = (Thread_Control *)n;
266    if ( !_Scheduler_simple_smp_Assign( t ) )
267      break;
268    if ( ++cpu >= _SMP_Processor_count )
269      break;
270  }
271}
Note: See TracBrowser for help on using the repository browser.