Changeset 3995e6d in rtems


Ignore:
Timestamp:
Sep 2, 2015, 9:58:54 AM (4 years ago)
Author:
Sebastian Huber <sebastian.huber@…>
Branches:
master
Children:
dafa5d88
Parents:
c4db18a
git-author:
Sebastian Huber <sebastian.huber@…> (09/02/15 09:58:54)
git-committer:
Sebastian Huber <sebastian.huber@…> (09/04/15 11:25:03)
Message:

score: Implement SMP-specific priority queue

Files:
4 added
9 edited

Legend:

Unmodified
Added
Removed
  • cpukit/sapi/include/confdefs.h

    rc4db18a r3995e6d  
    10091009  };
    10101010
     1011  #define CONFIGURE_SCHEDULER_COUNT RTEMS_ARRAY_SIZE( _Scheduler_Table )
     1012
    10111013  #if defined(RTEMS_SMP)
    1012     const size_t _Scheduler_Count =
    1013       RTEMS_ARRAY_SIZE( _Scheduler_Table );
     1014    const size_t _Scheduler_Count = CONFIGURE_SCHEDULER_COUNT;
    10141015
    10151016    const Scheduler_Assignment _Scheduler_Assignments[] = {
     
    29712972    _Configure_Object_RAM(_tasks, sizeof(Configuration_Thread_control)) \
    29722973      + _Configure_From_workspace(_Configure_Max_Objects(_tasks) \
    2973         * sizeof(Thread_queue_Heads)) \
     2974        * THREAD_QUEUE_HEADS_SIZE(CONFIGURE_SCHEDULER_COUNT)) \
    29742975      + _Configure_Max_Objects(_number_FP_tasks) \
    29752976        * _Configure_From_workspace(CONTEXT_FP_SIZE) \
  • cpukit/score/include/rtems/score/threadq.h

    rc4db18a r3995e6d  
    4141
    4242typedef struct _Thread_Control Thread_Control;
     43
     44/**
     45 * @brief Thread priority queue.
     46 */
     47typedef struct {
     48#if defined(RTEMS_SMP)
     49  /**
     50   * @brief Node to enqueue this queue in the FIFO chain of the corresponding
     51   * heads structure.
     52   *
     53   * @see Thread_queue_Heads::Heads::Fifo.
     54   */
     55  Chain_Node Node;
     56#endif
     57
     58  /**
     59   * @brief The actual thread priority queue.
     60   */
     61  RBTree_Control Queue;
     62} Thread_queue_Priority_queue;
    4363
    4464/**
     
    6282    /**
    6383     * @brief This is the FIFO discipline list.
     84     *
     85     * On SMP configurations this FIFO is used to enqueue the per scheduler
     86     * instance priority queues of this structure.  This ensures FIFO fairness
     87     * among the highest priority thread of each scheduler instance.
    6488     */
    6589    Chain_Control Fifo;
    6690
     91#if !defined(RTEMS_SMP)
    6792    /**
    6893     * @brief This is the set of threads for priority discipline waiting.
    6994     */
    70     RBTree_Control Priority;
     95    Thread_queue_Priority_queue Priority;
     96#endif
    7197  } Heads;
    7298
     
    82108   */
    83109  Chain_Node Free_node;
     110
     111#if defined(RTEMS_SMP)
     112  /**
     113   * @brief One priority queue per scheduler instance.
     114   */
     115  Thread_queue_Priority_queue Priority[ RTEMS_ZERO_LENGTH_ARRAY ];
     116#endif
    84117} Thread_queue_Heads;
     118
     119#if defined(RTEMS_SMP)
     120  #define THREAD_QUEUE_HEADS_SIZE( scheduler_count ) \
     121    ( sizeof( Thread_queue_Heads ) \
     122      + ( scheduler_count ) * sizeof( Thread_queue_Priority_queue ) )
     123#else
     124  #define THREAD_QUEUE_HEADS_SIZE( scheduler_count ) \
     125    sizeof( Thread_queue_Heads )
     126#endif
    85127
    86128typedef struct {
  • cpukit/score/include/rtems/score/threadqimpl.h

    rc4db18a r3995e6d  
    2323#include <rtems/score/chainimpl.h>
    2424#include <rtems/score/rbtreeimpl.h>
     25#include <rtems/score/scheduler.h>
    2526#include <rtems/score/thread.h>
    2627
     
    5152#endif
    5253} Thread_queue_Syslock_queue;
     54
     55RTEMS_INLINE_ROUTINE void _Thread_queue_Heads_initialize(
     56  Thread_queue_Heads *heads
     57)
     58{
     59#if defined(RTEMS_SMP)
     60  size_t i;
     61
     62  for ( i = 0; i < _Scheduler_Count; ++i ) {
     63    _RBTree_Initialize_empty( &heads->Priority[ i ].Queue );
     64  }
     65#endif
     66
     67  _Chain_Initialize_empty( &heads->Free_chain );
     68}
    5369
    5470RTEMS_INLINE_ROUTINE void _Thread_queue_Queue_initialize(
  • cpukit/score/src/thread.c

    rc4db18a r3995e6d  
    2121#include <rtems/score/threadimpl.h>
    2222#include <rtems/score/interr.h>
     23#include <rtems/score/scheduler.h>
    2324#include <rtems/score/wkspace.h>
    2425
     
    7475    _Workspace_Allocate_or_fatal_error,
    7576    _Objects_Maximum_per_allocation( maximum ),
    76     sizeof( Thread_queue_Heads )
     77    THREAD_QUEUE_HEADS_SIZE( _Scheduler_Count )
    7778  );
    7879}
  • cpukit/score/src/threadinitialize.c

    rc4db18a r3995e6d  
    143143    _Workspace_Allocate,
    144144    _Objects_Extend_size( &information->Objects ),
    145     sizeof( *the_thread->Wait.spare_heads )
     145    THREAD_QUEUE_HEADS_SIZE( _Scheduler_Count )
    146146  );
    147147  if ( the_thread->Wait.spare_heads == NULL ) {
    148148    goto failed;
    149149  }
    150   _Chain_Initialize_empty( &the_thread->Wait.spare_heads->Free_chain );
     150  _Thread_queue_Heads_initialize( the_thread->Wait.spare_heads );
    151151
    152152  /*
  • cpukit/score/src/threadqops.c

    rc4db18a r3995e6d  
    2121#include <rtems/score/chainimpl.h>
    2222#include <rtems/score/rbtreeimpl.h>
     23#include <rtems/score/schedulerimpl.h>
    2324
    2425static void _Thread_queue_Do_nothing_priority_change(
     
    151152}
    152153
     154static Thread_queue_Priority_queue *_Thread_queue_Priority_queue(
     155  Thread_queue_Heads   *heads,
     156  const Thread_Control *the_thread
     157)
     158{
     159#if defined(RTEMS_SMP)
     160  return &heads->Priority[
     161    _Scheduler_Get_index( _Scheduler_Get_own( the_thread ) )
     162  ];
     163#else
     164  (void) the_thread;
     165
     166  return &heads->Heads.Priority;
     167#endif
     168}
     169
    153170static void _Thread_queue_Priority_priority_change(
    154171  Thread_Control     *the_thread,
     
    157174)
    158175{
    159   Thread_queue_Heads *heads = queue->heads;
     176  Thread_queue_Heads          *heads = queue->heads;
     177  Thread_queue_Priority_queue *priority_queue;
    160178
    161179  _Assert( heads != NULL );
    162180
     181  priority_queue = _Thread_queue_Priority_queue( heads, the_thread );
     182
    163183  _RBTree_Extract(
    164     &heads->Heads.Priority,
     184    &priority_queue->Queue,
    165185    &the_thread->Wait.Node.RBTree
    166186  );
    167187  _RBTree_Insert(
    168     &heads->Heads.Priority,
     188    &priority_queue->Queue,
    169189    &the_thread->Wait.Node.RBTree,
    170190    _Thread_queue_Compare_priority,
     
    177197)
    178198{
     199#if defined(RTEMS_SMP)
     200  _Chain_Initialize_empty( &heads->Heads.Fifo );
     201#else
    179202  _RBTree_Initialize_empty( &heads->Heads.Priority );
     203#endif
    180204}
    181205
     
    185209)
    186210{
     211  Thread_queue_Priority_queue *priority_queue =
     212    _Thread_queue_Priority_queue( heads, the_thread );
     213
     214#if defined(RTEMS_SMP)
     215  if ( _RBTree_Is_empty( &priority_queue->Queue ) ) {
     216    _Chain_Append_unprotected( &heads->Heads.Fifo, &priority_queue->Node );
     217  }
     218#endif
     219
    187220  _RBTree_Insert(
    188     &heads->Heads.Priority,
     221    &priority_queue->Queue,
    189222    &the_thread->Wait.Node.RBTree,
    190223    _Thread_queue_Compare_priority,
     
    198231)
    199232{
     233  Thread_queue_Priority_queue *priority_queue =
     234    _Thread_queue_Priority_queue( heads, the_thread );
     235
    200236  _RBTree_Extract(
    201     &heads->Heads.Priority,
     237    &priority_queue->Queue,
    202238    &the_thread->Wait.Node.RBTree
    203239  );
     240
     241#if defined(RTEMS_SMP)
     242  _Chain_Extract_unprotected( &priority_queue->Node );
     243
     244  if ( !_RBTree_Is_empty( &priority_queue->Queue ) ) {
     245    _Chain_Append_unprotected( &heads->Heads.Fifo, &priority_queue->Node );
     246  }
     247#endif
    204248}
    205249
     
    233277)
    234278{
    235   RBTree_Control *priority_queue = &heads->Heads.Priority;
    236   RBTree_Node    *first;
    237 
    238   _Assert( !_RBTree_Is_empty( priority_queue ) );
    239   first = _RBTree_Minimum( priority_queue );
     279  Thread_queue_Priority_queue *priority_queue;
     280  RBTree_Node                 *first;
     281
     282#if defined(RTEMS_SMP)
     283  _Assert( !_Chain_Is_empty( &heads->Heads.Fifo ) );
     284  priority_queue = (Thread_queue_Priority_queue *)
     285    _Chain_First( &heads->Heads.Fifo );
     286#else
     287  priority_queue = &heads->Heads.Priority;
     288#endif
     289
     290  _Assert( !_RBTree_Is_empty( &priority_queue->Queue ) );
     291  first = _RBTree_Minimum( &priority_queue->Queue );
    240292
    241293  return THREAD_RBTREE_NODE_TO_THREAD( first );
  • doc/user/smp.t

    rc4db18a r3995e6d  
    186186SCHEDULER_IDENT - Get ID of a scheduler} and @ref{Symmetric Multiprocessing
    187187Services TASK_SET_SCHEDULER - Set scheduler of a task}.
     188
     189@subsection Task Priority Queues
     190
     191Due to the support for clustered scheduling the task priority queues need
     192special attention.  It makes no sense to compare the priority values of two
     193different scheduler instances.  Thus, it is not possible to simply use one
     194plain priority queue for tasks of different scheduler instances.
     195
     196One solution to this problem is to use two levels of queues.  The top level
     197queue provides FIFO ordering and contains priority queues.  Each priority queue
     198is associated with a scheduler instance and contains only tasks of this
     199scheduler instance.  Tasks are enqueued in the priority queue corresponding to
     200their scheduler instance.  In case this priority queue was empty, then it is
     201appended to the FIFO.  To dequeue a task the highest priority task of the first
     202priority queue in the FIFO is selected.  Then the first priority queue is
     203removed from the FIFO.  In case the previously first priority queue is not
     204empty, then it is appended to the FIFO.  So there is FIFO fairness with respect
     205to the highest priority task of each scheduler instances. See also @cite{
     206Brandenburg, Björn B.: A fully preemptive multiprocessor semaphore protocol for
     207latency-sensitive real-time applications. In Proceedings of the 25th Euromicro
     208Conference on Real-Time Systems (ECRTS 2013), pages 292–302, 2013.
     209@uref{http://www.mpi-sws.org/~bbb/papers/pdf/ecrts13b.pdf}}.
     210
     211Such a two level queue may need a considerable amount of memory if fast enqueue
     212and dequeue operations are desired (depends on the scheduler instance count).
     213To mitigate this problem an approch of the FreeBSD kernel was implemented in
     214RTEMS.  We have the invariant that a task can be enqueued on at most one task
     215queue.  Thus, we need only as many queues as we have tasks.  Each task is
     216equipped with spare task queue which it can give to an object on demand.  The
     217task queue uses a dedicated memory space independent of the other memory used
     218for the task itself. In case a task needs to block, then there are two options
     219
     220@itemize @bullet
     221@item the object already has task queue, then the task enqueues itself to this
     222already present queue and the spare task queue of the task is added to a list
     223of free queues for this object, or
     224@item otherwise, then the queue of the task is given to the object and the task
     225enqueues itself to this queue.
     226@end itemize
     227
     228In case the task is dequeued, then there are two options
     229
     230@itemize @bullet
     231@item the task is the last task on the queue, then it removes this queue from
     232the object and reclaims it for its own purpose, or
     233@item otherwise, then the task removes one queue from the free list of the
     234object and reclaims it for its own purpose.
     235@end itemize
     236
     237Since there are usually more objects than tasks, this actually reduces the
     238memory demands. In addition the objects contain only a pointer to the task
     239queue structure. This helps to hide implementation details and makes it
     240possible to use self-contained synchronization objects in Newlib and GCC (C++
     241and OpenMP run-time support).
    188242
    189243@subsection Scheduler Helping Protocol
  • testsuites/smptests/Makefile.am

    rc4db18a r3995e6d  
    2727SUBDIRS += smpmigration02
    2828SUBDIRS += smpmrsp01
     29SUBDIRS += smpmutex01
    2930SUBDIRS += smpschedaffinity01
    3031SUBDIRS += smpschedaffinity02
  • testsuites/smptests/configure.ac

    rc4db18a r3995e6d  
    8282smpmigration02/Makefile
    8383smpmrsp01/Makefile
     84smpmutex01/Makefile
    8485smppsxaffinity01/Makefile
    8586smppsxaffinity02/Makefile
Note: See TracChangeset for help on using the changeset viewer.