source: rtems/cpukit/score/include/rtems/score/scheduler.h @ 5c3d250

4.11
Last change on this file since 5c3d250 was 5c3d250, checked in by Sebastian Huber <sebastian.huber@…>, on Jul 4, 2014 at 12:34:23 PM

score: Implement scheduler helping protocol

The following scheduler operations return a thread in need for help

  • unblock,
  • change priority, and
  • yield.

A thread in need for help is a thread that encounters a scheduler state
change from scheduled to ready or a thread that cannot be scheduled in
an unblock operation. Such a thread can ask threads which depend on
resources owned by this thread for help.

Add a new ask for help scheduler operation. This operation is used by
_Scheduler_Ask_for_help() to help threads in need for help returned by
the operations mentioned above. This operation is also used by
_Scheduler_Thread_change_resource_root() in case the root of a resource
sub-tree changes. A use case is the ownership change of a resource.

In case it is not possible to schedule a thread in need for help, then
the corresponding scheduler node will be placed into the set of ready
scheduler nodes of the scheduler instance. Once a state change from
ready to scheduled happens for this scheduler node it may be used to
schedule the thread in need for help.

  • Property mode set to 100644
File size: 14.4 KB
Line 
1/**
2 *  @file  rtems/score/scheduler.h
3 *
4 *  @brief Constants and Structures Associated with the Scheduler
5 *
6 *  This include file contains all the constants and structures associated
7 *  with the scheduler.
8 */
9
10/*
11 *  Copyright (C) 2010 Gedare Bloom.
12 *  Copyright (C) 2011 On-Line Applications Research Corporation (OAR).
13 *
14 *  The license and distribution terms for this file may be
15 *  found in the file LICENSE in this distribution or at
16 *  http://www.rtems.org/license/LICENSE.
17 */
18
19#ifndef _RTEMS_SCORE_SCHEDULER_H
20#define _RTEMS_SCORE_SCHEDULER_H
21
22#include <rtems/score/percpu.h>
23#include <rtems/score/priority.h>
24#include <rtems/score/thread.h>
25#if defined(__RTEMS_HAVE_SYS_CPUSET_H__) && defined(RTEMS_SMP)
26  #include <sys/cpuset.h>
27#endif
28
29#ifdef __cplusplus
30extern "C" {
31#endif
32
33/**
34 *  @defgroup ScoreScheduler Scheduler Handler
35 *
36 *  @ingroup Score
37 *
38 *  This handler encapsulates functionality related to managing sets of threads
39 *  that are ready for execution.
40 */
41/**@{*/
42
43typedef struct Scheduler_Control Scheduler_Control;
44
45typedef struct Scheduler_Node Scheduler_Node;
46
47#if defined(RTEMS_SMP)
48  typedef Thread_Control * Scheduler_Void_or_thread;
49
50  #define SCHEDULER_RETURN_VOID_OR_NULL return NULL
51#else
52  typedef void Scheduler_Void_or_thread;
53
54  #define SCHEDULER_RETURN_VOID_OR_NULL return
55#endif
56
57/**
58 * @brief The scheduler operations.
59 */
60typedef struct {
61  /** @see _Scheduler_Handler_initialization() */
62  void ( *initialize )( const Scheduler_Control * );
63
64  /** @see _Scheduler_Schedule() */
65  void ( *schedule )( const Scheduler_Control *, Thread_Control *);
66
67  /** @see _Scheduler_Yield() */
68  Scheduler_Void_or_thread ( *yield )(
69    const Scheduler_Control *,
70    Thread_Control *
71  );
72
73  /** @see _Scheduler_Block() */
74  void ( *block )(
75    const Scheduler_Control *,
76    Thread_Control *
77  );
78
79  /** @see _Scheduler_Unblock() */
80  Scheduler_Void_or_thread ( *unblock )(
81    const Scheduler_Control *,
82    Thread_Control *
83  );
84
85  /** @see _Scheduler_Change_priority() */
86  Scheduler_Void_or_thread ( *change_priority )(
87    const Scheduler_Control *,
88    Thread_Control *,
89    Priority_Control,
90    bool
91  );
92
93#if defined(RTEMS_SMP)
94  /**
95   * Ask for help operation.
96   *
97   * @param[in] scheduler The scheduler of the thread offering help.
98   * @param[in] offers_help The thread offering help.
99   * @param[in] needs_help The thread needing help.
100   *
101   * @retval needs_help It was not possible to schedule the thread needing
102   *   help, so it is returned to continue the search for help.
103   * @retval next_needs_help It was possible to schedule the thread needing
104   *   help, but this displaced another thread eligible to ask for help.  So
105   *   this thread is returned to start a new search for help.
106   * @retval NULL It was possible to schedule the thread needing help, and no
107   *   other thread needs help as a result.
108   *
109   * @see _Scheduler_Ask_for_help().
110   */
111  Thread_Control *( *ask_for_help )(
112    const Scheduler_Control *scheduler,
113    Thread_Control          *offers_help,
114    Thread_Control          *needs_help
115  );
116#endif
117
118  /** @see _Scheduler_Node_initialize() */
119  void ( *node_initialize )( const Scheduler_Control *, Thread_Control * );
120
121  /** @see _Scheduler_Node_destroy() */
122  void ( *node_destroy )( const Scheduler_Control *, Thread_Control * );
123
124  /** @see _Scheduler_Update_priority() */
125  void ( *update_priority )(
126    const Scheduler_Control *,
127    Thread_Control *,
128    Priority_Control
129  );
130
131  /** @see _Scheduler_Priority_compare() */
132  int ( *priority_compare )(
133    Priority_Control,
134    Priority_Control
135  );
136
137  /** @see _Scheduler_Release_job() */
138  void ( *release_job ) (
139    const Scheduler_Control *,
140    Thread_Control *,
141    uint32_t
142  );
143
144  /** @see _Scheduler_Tick() */
145  void ( *tick )( const Scheduler_Control *, Thread_Control * );
146
147  /** @see _Scheduler_Start_idle() */
148  void ( *start_idle )(
149    const Scheduler_Control *,
150    Thread_Control *,
151    Per_CPU_Control *
152  );
153
154#if defined(__RTEMS_HAVE_SYS_CPUSET_H__) && defined(RTEMS_SMP)
155  /** @see _Scheduler_Get_affinity() */
156  bool ( *get_affinity )(
157    const Scheduler_Control *,
158    Thread_Control *,
159    size_t,
160    cpu_set_t *
161  );
162 
163  /** @see _Scheduler_Set_affinity() */
164  bool ( *set_affinity )(
165    const Scheduler_Control *,
166    Thread_Control *,
167    size_t,
168    const cpu_set_t *
169  );
170#endif
171} Scheduler_Operations;
172
173/**
174 * @brief Scheduler context.
175 *
176 * The scheduler context of a particular scheduler implementation must place
177 * this structure at the begin of its context structure.
178 */
179typedef struct Scheduler_Context {
180#if defined(RTEMS_SMP)
181  /**
182   * @brief Count of processors owned by this scheduler instance.
183   */
184  uint32_t processor_count;
185#endif
186} Scheduler_Context;
187
188/**
189 * @brief Scheduler control.
190 */
191struct Scheduler_Control {
192  /**
193   * @brief Reference to a statically allocated scheduler context.
194   */
195  Scheduler_Context *context;
196
197  /**
198   * @brief The scheduler operations.
199   */
200  Scheduler_Operations Operations;
201
202  /**
203   * @brief The scheduler name.
204   */
205  uint32_t name;
206};
207
208#if defined(RTEMS_SMP)
209/**
210 * @brief State to indicate potential help for other threads.
211 *
212 * @dot
213 * digraph state {
214 *   y [label="HELP YOURSELF"];
215 *   ao [label="HELP ACTIVE OWNER"];
216 *   ar [label="HELP ACTIVE RIVAL"];
217 *
218 *   y -> ao [label="obtain"];
219 *   y -> ar [label="wait for obtain"];
220 *   ao -> y [label="last release"];
221 *   ao -> r [label="wait for obtain"];
222 *   ar -> r [label="timeout"];
223 *   ar -> ao [label="timeout"];
224 * }
225 * @enddot
226 */
227typedef enum {
228  /**
229   * @brief This scheduler node is solely used by the owner thread.
230   *
231   * This thread owns no resources using a helping protocol and thus does not
232   * take part in the scheduler helping protocol.  No help will be provided for
233   * other thread.
234   */
235  SCHEDULER_HELP_YOURSELF,
236
237  /**
238   * @brief This scheduler node is owned by a thread actively owning a resource.
239   *
240   * This scheduler node can be used to help out threads.
241   *
242   * In case this scheduler node changes its state from ready to scheduled and
243   * the thread executes using another node, then an idle thread will be
244   * provided as a user of this node to temporarily execute on behalf of the
245   * owner thread.  Thus lower priority threads are denied access to the
246   * processors of this scheduler instance.
247   *
248   * In case a thread actively owning a resource performs a blocking operation,
249   * then an idle thread will be used also in case this node is in the
250   * scheduled state.
251   */
252  SCHEDULER_HELP_ACTIVE_OWNER,
253
254  /**
255   * @brief This scheduler node is owned by a thread actively obtaining a
256   * resource currently owned by another thread.
257   *
258   * This scheduler node can be used to help out threads.
259   *
260   * The thread owning this node is ready and will give away its processor in
261   * case the thread owning the resource asks for help.
262   */
263  SCHEDULER_HELP_ACTIVE_RIVAL,
264
265  /**
266   * @brief This scheduler node is owned by a thread obtaining a
267   * resource currently owned by another thread.
268   *
269   * This scheduler node can be used to help out threads.
270   *
271   * The thread owning this node is blocked.
272   */
273  SCHEDULER_HELP_PASSIVE
274} Scheduler_Help_state;
275#endif
276
277/**
278 * @brief Scheduler node for per-thread data.
279 */
280struct Scheduler_Node {
281#if defined(RTEMS_SMP)
282  /**
283   * @brief Chain node for usage in various scheduler data structures.
284   *
285   * Strictly this is the wrong place for this field since the data structures
286   * to manage scheduler nodes belong to the particular scheduler
287   * implementation.  Currently all SMP scheduler implementations use chains.
288   * The node is here to simplify things, just like the object node in the
289   * thread control block.  It may be replaced with a union to add a red-black
290   * tree node in the future.
291   */
292  Chain_Node Node;
293
294  /**
295   * @brief The thread using this node.
296   */
297  Thread_Control *user;
298
299  /**
300   * @brief The help state of this node.
301   */
302  Scheduler_Help_state help_state;
303
304  /**
305   * @brief The thread owning this node.
306   */
307  Thread_Control *owner;
308
309  /**
310   * @brief The idle thread claimed by this node in case the help state is
311   * SCHEDULER_HELP_ACTIVE_OWNER.
312   *
313   * Active owners will lend their own node to an idle thread in case they
314   * execute currently using another node or in case they perform a blocking
315   * operation.  This is necessary to ensure the priority ceiling protocols
316   * work across scheduler boundaries.
317   */
318  Thread_Control *idle;
319
320  /**
321   * @brief The thread accepting help by this node in case the help state is
322   * not SCHEDULER_HELP_YOURSELF.
323   */
324  Thread_Control *accepts_help;
325#endif
326};
327
328/**
329 * @brief Registered schedulers.
330 *
331 * Application provided via <rtems/confdefs.h>.
332 *
333 * @see _Scheduler_Count.
334 */
335extern const Scheduler_Control _Scheduler_Table[];
336
337/**
338 * @brief Count of registered schedulers.
339 *
340 * Application provided via <rtems/confdefs.h> on SMP configurations.
341 *
342 * It is very important that this is a compile-time constant on uni-processor
343 * configurations (in this case RTEMS_SMP is not defined) so that the compiler
344 * can optimize the some loops away
345 *
346 * @see _Scheduler_Table.
347 */
348#if defined(RTEMS_SMP)
349  extern const size_t _Scheduler_Count;
350#else
351  #define _Scheduler_Count ( (size_t) 1 )
352#endif
353
354#if defined(RTEMS_SMP)
355  /**
356   * @brief The scheduler assignment default attributes.
357   */
358  #define SCHEDULER_ASSIGN_DEFAULT UINT32_C(0x0)
359
360  /**
361   * @brief The presence of this processor is optional.
362   */
363  #define SCHEDULER_ASSIGN_PROCESSOR_OPTIONAL SCHEDULER_ASSIGN_DEFAULT
364
365  /**
366   * @brief The presence of this processor is mandatory.
367   */
368  #define SCHEDULER_ASSIGN_PROCESSOR_MANDATORY UINT32_C(0x1)
369
370  /**
371   * @brief Scheduler assignment.
372   */
373  typedef struct {
374    /**
375     * @brief The scheduler for this processor.
376     */
377    const Scheduler_Control *scheduler;
378
379    /**
380     * @brief The scheduler assignment attributes.
381     *
382     * Use @ref SCHEDULER_ASSIGN_DEFAULT to select default attributes.
383     *
384     * The presence of a processor can be
385     * - @ref SCHEDULER_ASSIGN_PROCESSOR_OPTIONAL, or
386     * - @ref SCHEDULER_ASSIGN_PROCESSOR_MANDATORY.
387     */
388    uint32_t attributes;
389  } Scheduler_Assignment;
390
391  /**
392   * @brief The scheduler assignments.
393   *
394   * The length of this array must be equal to the maximum processors.
395   *
396   * Application provided via <rtems/confdefs.h>.
397   *
398   * @see _Scheduler_Table and rtems_configuration_get_maximum_processors().
399   */
400  extern const Scheduler_Assignment _Scheduler_Assignments[];
401#endif
402
403#if defined(RTEMS_SMP)
404  /**
405   * @brief Does nothing.
406   *
407   * @param[in] scheduler Unused.
408   * @param[in] offers_help Unused.
409   * @param[in] needs_help Unused.
410   *
411   * @retval NULL Always.
412   */
413  Thread_Control *_Scheduler_default_Ask_for_help(
414    const Scheduler_Control *scheduler,
415    Thread_Control          *offers_help,
416    Thread_Control          *needs_help
417  );
418
419  #define SCHEDULER_OPERATION_DEFAULT_ASK_FOR_HELP \
420    _Scheduler_default_Ask_for_help,
421#else
422  #define SCHEDULER_OPERATION_DEFAULT_ASK_FOR_HELP
423#endif
424
425/**
426 * @brief Does nothing.
427 *
428 * @param[in] scheduler Unused.
429 * @param[in] the_thread Unused.
430 */
431void _Scheduler_default_Schedule(
432  const Scheduler_Control *scheduler,
433  Thread_Control          *the_thread
434);
435
436/**
437 * @brief Does nothing.
438 *
439 * @param[in] scheduler Unused.
440 * @param[in] the_thread Unused.
441 */
442void _Scheduler_default_Node_initialize(
443  const Scheduler_Control *scheduler,
444  Thread_Control          *the_thread
445);
446
447/**
448 * @brief Does nothing.
449 *
450 * @param[in] scheduler Unused.
451 * @param[in] the_thread Unused.
452 */
453void _Scheduler_default_Node_destroy(
454  const Scheduler_Control *scheduler,
455  Thread_Control          *the_thread
456);
457
458/**
459 * @brief Does nothing.
460 *
461 * @param[in] scheduler Unused.
462 * @param[in] the_thread Unused.
463 * @param[in] new_priority Unused.
464 */
465void _Scheduler_default_Update_priority(
466  const Scheduler_Control *scheduler,
467  Thread_Control          *the_thread,
468  Priority_Control         new_priority
469);
470
471/**
472 * @brief Does nothing.
473 *
474 * @param[in] scheduler Unused.
475 * @param[in] the_thread Unused.
476 * @param[in] deadline Unused.
477 */
478void _Scheduler_default_Release_job(
479  const Scheduler_Control *scheduler,
480  Thread_Control          *the_thread,
481  uint32_t                 deadline
482);
483
484/**
485 * @brief Performs tick operations depending on the CPU budget algorithm for
486 * each executing thread.
487 *
488 * This routine is invoked as part of processing each clock tick.
489 *
490 * @param[in] scheduler The scheduler.
491 * @param[in] execution An executing thread.
492 */
493void _Scheduler_default_Tick(
494  const Scheduler_Control *scheduler,
495  Thread_Control          *executing
496);
497
498/**
499 * @brief Starts an idle thread.
500 *
501 * @param[in] scheduler The scheduler.
502 * @param[in] the_thread An idle thread.
503 * @param[in] cpu This parameter is unused.
504 */
505void _Scheduler_default_Start_idle(
506  const Scheduler_Control *scheduler,
507  Thread_Control          *the_thread,
508  Per_CPU_Control         *cpu
509);
510
511#if defined(__RTEMS_HAVE_SYS_CPUSET_H__) && defined(RTEMS_SMP)
512  /**
513   * @brief Get affinity for the default scheduler.
514   *
515   * @param[in] thread The associated thread.
516   * @param[in] cpusetsize The size of the cpuset.
517   * @param[out] cpuset Affinity set containing all CPUs.
518   *
519   * @retval 0 Successfully got cpuset
520   * @retval -1 The cpusetsize is invalid for the system
521   */
522  bool _Scheduler_default_Get_affinity(
523    const Scheduler_Control *scheduler,
524    Thread_Control          *thread,
525    size_t                   cpusetsize,
526    cpu_set_t               *cpuset
527  );
528
529  /**
530   * @brief Set affinity for the default scheduler.
531   *
532   * @param[in] thread The associated thread.
533   * @param[in] cpusetsize The size of the cpuset.
534   * @param[in] cpuset Affinity new affinity set.
535   *
536   * @retval 0 Successful
537   *
538   *  This method always returns successful and does not save
539   *  the cpuset.
540   */
541  bool _Scheduler_default_Set_affinity(
542    const Scheduler_Control *scheduler,
543    Thread_Control          *thread,
544    size_t                   cpusetsize,
545    const cpu_set_t         *cpuset
546  );
547
548  #define SCHEDULER_OPERATION_DEFAULT_GET_SET_AFFINITY \
549    , _Scheduler_default_Get_affinity \
550    , _Scheduler_default_Set_affinity
551#else
552  #define SCHEDULER_OPERATION_DEFAULT_GET_SET_AFFINITY
553#endif
554
555/**
556 * @brief Indicates if thread priority queues are broken with the configured
557 * scheduler or not.
558 *
559 * See also PR2174: Memory corruption with EDF scheduler and thread priority
560 * queues.
561 */
562extern const bool _Scheduler_FIXME_thread_priority_queues_are_broken;
563
564/**@}*/
565
566#ifdef __cplusplus
567}
568#endif
569
570#endif
571/* end of include file */
Note: See TracBrowser for help on using the repository browser.