[rtems commit] score: Implement priority boosting

Sebastian Huber sebh at rtems.org
Fri Sep 4 11:45:49 UTC 2015


Module:    rtems
Branch:    master
Commit:    dafa5d88435853809040761b79ab9d8f2217281b
Changeset: http://git.rtems.org/rtems/commit/?id=dafa5d88435853809040761b79ab9d8f2217281b

Author:    Sebastian Huber <sebastian.huber at embedded-brains.de>
Date:      Thu Sep  3 10:27:16 2015 +0200

score: Implement priority boosting

---

 cpukit/score/include/rtems/score/threadimpl.h  | 31 +++++++++++++
 cpukit/score/include/rtems/score/threadqimpl.h | 25 +++++++++++
 cpukit/score/src/coremutexseize.c              |  2 +-
 cpukit/score/src/coremutexsurrender.c          |  1 +
 cpukit/score/src/mutex.c                       | 15 ++++---
 cpukit/score/src/threadchangepriority.c        | 34 ++++++++++++++
 cpukit/score/src/threadqops.c                  | 22 ++++++++++
 doc/user/glossary.texi                         |  6 +++
 doc/user/sem.t                                 |  5 +++
 doc/user/smp.t                                 |  6 ++-
 testsuites/smptests/smpmutex01/init.c          | 61 +++++++++++++++++++++++---
 11 files changed, 195 insertions(+), 13 deletions(-)

diff --git a/cpukit/score/include/rtems/score/threadimpl.h b/cpukit/score/include/rtems/score/threadimpl.h
index 4656881..1092b65 100644
--- a/cpukit/score/include/rtems/score/threadimpl.h
+++ b/cpukit/score/include/rtems/score/threadimpl.h
@@ -437,6 +437,37 @@ void _Thread_Raise_priority(
 );
 
 /**
+ * @brief Inherit the priority of a thread.
+ *
+ * It changes the current priority of the inheritor thread to the current priority
+ * of the ancestor thread if it is higher than the current priority of the inheritor
+ * thread.  In this case the inheritor thread is appended to its new priority group
+ * in its scheduler instance.
+ *
+ * On SMP configurations, the priority is changed to PRIORITY_PSEUDO_ISR in
+ * case the own schedulers of the inheritor and ancestor thread differ (priority
+ * boosting).
+ *
+ * @param[in] inheritor The thread to inherit the priority.
+ * @param[in] ancestor The thread to bequeath its priority to the inheritor
+ *   thread.
+ */
+#if defined(RTEMS_SMP)
+void _Thread_Inherit_priority(
+  Thread_Control *inheritor,
+  Thread_Control *ancestor
+);
+#else
+RTEMS_INLINE_ROUTINE void _Thread_Inherit_priority(
+  Thread_Control *inheritor,
+  Thread_Control *ancestor
+)
+{
+  _Thread_Raise_priority( inheritor, ancestor->current_priority );
+}
+#endif
+
+/**
  * @brief Sets the current to the real priority of a thread.
  *
  * Sets the priority restore hint to false.
diff --git a/cpukit/score/include/rtems/score/threadqimpl.h b/cpukit/score/include/rtems/score/threadqimpl.h
index bf01eb7..510f886 100644
--- a/cpukit/score/include/rtems/score/threadqimpl.h
+++ b/cpukit/score/include/rtems/score/threadqimpl.h
@@ -522,6 +522,31 @@ RTEMS_INLINE_ROUTINE void _Thread_queue_Destroy(
 }
 
 /**
+ * @brief Boosts the priority of the thread if threads of another scheduler
+ * instance are enqueued on the thread queue.
+ *
+ * The thread queue must use the priority waiting discipline.
+ *
+ * @param[in] queue The actual thread queue.
+ * @param[in] the_thread The thread to boost the priority if necessary.
+ */
+#if defined(RTEMS_SMP)
+void _Thread_queue_Boost_priority(
+  Thread_queue_Queue *queue,
+  Thread_Control     *the_thread
+);
+#else
+RTEMS_INLINE_ROUTINE void _Thread_queue_Boost_priority(
+  Thread_queue_Queue *queue,
+  Thread_Control     *the_thread
+)
+{
+  (void) queue;
+  (void) the_thread;
+}
+#endif
+
+/**
  * @brief Compare two thread's priority for RBTree Insertion.
  *
  * @param[in] left points to the left thread's RBnode
diff --git a/cpukit/score/src/coremutexseize.c b/cpukit/score/src/coremutexseize.c
index ddc5d6b..8059659 100644
--- a/cpukit/score/src/coremutexseize.c
+++ b/cpukit/score/src/coremutexseize.c
@@ -75,7 +75,7 @@ void _CORE_mutex_Seize_interrupt_blocking(
     _Thread_queue_Release( &the_mutex->Wait_queue, lock_context );
 #endif
 
-    _Thread_Raise_priority( holder, executing->current_priority );
+    _Thread_Inherit_priority( holder, executing );
 
 #if !defined(RTEMS_SMP)
     _Thread_queue_Acquire( &the_mutex->Wait_queue, lock_context );
diff --git a/cpukit/score/src/coremutexsurrender.c b/cpukit/score/src/coremutexsurrender.c
index d3f965d..7d9c57f 100644
--- a/cpukit/score/src/coremutexsurrender.c
+++ b/cpukit/score/src/coremutexsurrender.c
@@ -209,6 +209,7 @@ CORE_mutex_Status _CORE_mutex_Surrender(
         case CORE_MUTEX_DISCIPLINES_PRIORITY_INHERIT:
           _CORE_mutex_Push_priority( the_mutex, the_thread );
           the_thread->resource_count++;
+          _Thread_queue_Boost_priority( &the_mutex->Wait_queue.Queue, the_thread );
           break;
         case CORE_MUTEX_DISCIPLINES_PRIORITY_CEILING:
           _CORE_mutex_Push_priority( the_mutex, the_thread );
diff --git a/cpukit/score/src/mutex.c b/cpukit/score/src/mutex.c
index ae637dd..f03bab7 100644
--- a/cpukit/score/src/mutex.c
+++ b/cpukit/score/src/mutex.c
@@ -112,9 +112,7 @@ static void _Mutex_Acquire_slow(
   ISR_lock_Context  *lock_context
 )
 {
-  /* Priority inheritance */
-  _Thread_Raise_priority( owner, executing->current_priority );
-
+  _Thread_Inherit_priority( owner, executing );
   _Thread_queue_Enqueue_critical(
     &mutex->Queue.Queue,
     MUTEX_TQ_OPERATIONS,
@@ -136,15 +134,22 @@ static void _Mutex_Release_slow(
 {
   if (heads != NULL) {
     const Thread_queue_Operations *operations;
-    Thread_Control *first;
+    Thread_Control                *first;
+    bool                           unblock;
 
     operations = MUTEX_TQ_OPERATIONS;
     first = ( *operations->first )( heads );
 
     mutex->owner = first;
-    _Thread_queue_Extract_critical(
+    unblock = _Thread_queue_Extract_locked(
       &mutex->Queue.Queue,
       operations,
+      first
+    );
+    _Thread_queue_Boost_priority( &mutex->Queue.Queue, first );
+    _Thread_queue_Unblock_critical(
+      unblock,
+      &mutex->Queue.Queue,
       first,
       lock_context
     );
diff --git a/cpukit/score/src/threadchangepriority.c b/cpukit/score/src/threadchangepriority.c
index 8f5d14f..35e5e5b 100644
--- a/cpukit/score/src/threadchangepriority.c
+++ b/cpukit/score/src/threadchangepriority.c
@@ -110,6 +110,40 @@ void _Thread_Raise_priority(
   );
 }
 
+#if defined(RTEMS_SMP)
+static bool _Thread_Inherit_priority_filter(
+  Thread_Control   *inheritor,
+  Priority_Control *new_priority,
+  void             *arg
+)
+{
+  Thread_Control *ancestor = arg;
+
+  if ( _Scheduler_Get_own( inheritor ) == _Scheduler_Get_own( ancestor ) ) {
+    *new_priority = ancestor->current_priority;
+  }
+
+  return _Thread_Priority_less_than(
+    inheritor->current_priority,
+    *new_priority
+  );
+}
+
+void _Thread_Inherit_priority(
+  Thread_Control *inheritor,
+  Thread_Control *ancestor
+)
+{
+  _Thread_Change_priority(
+    inheritor,
+    PRIORITY_PSEUDO_ISR,
+    ancestor,
+    _Thread_Inherit_priority_filter,
+    false
+  );
+}
+#endif
+
 static bool _Thread_Restore_priority_filter(
   Thread_Control   *the_thread,
   Priority_Control *new_priority,
diff --git a/cpukit/score/src/threadqops.c b/cpukit/score/src/threadqops.c
index 07473f5..7b01779 100644
--- a/cpukit/score/src/threadqops.c
+++ b/cpukit/score/src/threadqops.c
@@ -293,6 +293,28 @@ static Thread_Control *_Thread_queue_Priority_first(
   return THREAD_RBTREE_NODE_TO_THREAD( first );
 }
 
+#if defined(RTEMS_SMP)
+void _Thread_queue_Boost_priority(
+  Thread_queue_Queue *queue,
+  Thread_Control     *the_thread
+)
+{
+  Thread_queue_Heads *heads = queue->heads;
+
+  if (
+    heads != NULL
+      && (
+        !_Chain_Has_only_one_node( &heads->Heads.Fifo )
+          || _RBTree_Is_empty(
+            &_Thread_queue_Priority_queue( heads, the_thread )->Queue
+          )
+      )
+  ) {
+    _Thread_Raise_priority( the_thread, PRIORITY_PSEUDO_ISR );
+  }
+}
+#endif
+
 const Thread_queue_Operations _Thread_queue_Operations_default = {
   .priority_change = _Thread_queue_Do_nothing_priority_change,
   .extract = _Thread_queue_Do_nothing_extract
diff --git a/doc/user/glossary.texi b/doc/user/glossary.texi
index f0beeab..bf22cf6 100644
--- a/doc/user/glossary.texi
+++ b/doc/user/glossary.texi
@@ -505,6 +505,12 @@ A mechanism used to represent the relative
 importance of an element in a set of items.  RTEMS uses priority
 to determine which task should execute.
 
+ at item priority boosting
+A simple approach to extend the priority inheritance protocol for clustered
+scheduling is @dfn{priority boosting}.  In case a mutex is owned by a task of
+another cluster, then the priority of the owner task is raised to an
+artificially high priority, the pseudo-interrupt priority.
+
 @item priority inheritance
 An algorithm that calls for
 the lower priority task holding a resource to have its priority
diff --git a/doc/user/sem.t b/doc/user/sem.t
index 6bd22dd..210f1d0 100644
--- a/doc/user/sem.t
+++ b/doc/user/sem.t
@@ -115,6 +115,11 @@ for that resource.  Each time a task blocks attempting to obtain
 the resource, the task holding the resource may have its
 priority increased.
 
+On SMP configurations, in case the task holding the resource and the task that
+blocks attempting to obtain the resource are in different scheduler instances,
+the priority of the holder is raised to the pseudo-interrupt priority (priority
+boosting).  The pseudo-interrupt priority is the highest priority.
+
 RTEMS supports priority inheritance for local, binary
 semaphores that use the priority task wait queue blocking
 discipline.   When a task of higher priority than the task
diff --git a/doc/user/smp.t b/doc/user/smp.t
index db4114c..de07f3c 100644
--- a/doc/user/smp.t
+++ b/doc/user/smp.t
@@ -164,12 +164,14 @@ and instruction caches.  With clustered scheduling it is possible to honour the
 cache topology of a system and thus avoid expensive cache synchronization
 traffic.  It is easy to implement.  The problem is to provide synchronization
 primitives for inter-cluster synchronization (more than one cluster is involved
-in the synchronization process). In RTEMS there are currently three means
+in the synchronization process). In RTEMS there are currently four means
 available
 
 @itemize @bullet
 @item events,
- at item message queues, and
+ at item message queues,
+ at item semaphores using the @ref{Semaphore Manager Priority Inheritance}
+protocol (priority boosting), and
 @item semaphores using the @ref{Semaphore Manager Multiprocessor Resource
 Sharing Protocol} (MrsP).
 @end itemize
diff --git a/testsuites/smptests/smpmutex01/init.c b/testsuites/smptests/smpmutex01/init.c
index 1b2a189..80b16fe 100644
--- a/testsuites/smptests/smpmutex01/init.c
+++ b/testsuites/smptests/smpmutex01/init.c
@@ -26,7 +26,7 @@ const char rtems_test_name[] = "SMPMUTEX 1";
 
 #define PART_COUNT 2
 
-#define TASK_COUNT 8
+#define TASK_COUNT 9
 
 typedef enum {
   REQ_WAKE_UP_MASTER = RTEMS_EVENT_0,
@@ -43,7 +43,8 @@ typedef enum {
   B_4,
   B_5_0,
   B_5_1,
-  H,
+  H_A,
+  H_B,
   NONE
 } task_id;
 
@@ -111,15 +112,21 @@ static rtems_event_set wait_for_events(void)
   return events;
 }
 
-static void sync_with_helper(test_context *ctx)
+static void sync_with_helper_by_id(test_context *ctx, task_id id)
 {
   rtems_event_set events;
 
-  send_event(ctx, H, REQ_WAKE_UP_HELPER);
+  send_event(ctx, id, REQ_WAKE_UP_HELPER);
   events = wait_for_events();
   rtems_test_assert(events == REQ_WAKE_UP_MASTER);
 }
 
+static void sync_with_helper(test_context *ctx)
+{
+  sync_with_helper_by_id(ctx, H_A);
+  sync_with_helper_by_id(ctx, H_B);
+}
+
 static void request(test_context *ctx, task_id id, request_id req)
 {
   send_event(ctx, id, req);
@@ -159,6 +166,24 @@ static void check_generations(test_context *ctx, task_id a, task_id b)
   }
 }
 
+static void assert_prio(
+  test_context *ctx,
+  task_id id,
+  rtems_task_priority expected
+)
+{
+  rtems_task_priority actual;
+  rtems_status_code sc;
+
+  sc = rtems_task_set_priority(
+    ctx->tasks[id],
+    RTEMS_CURRENT_PRIORITY,
+    &actual
+  );
+  rtems_test_assert(sc == RTEMS_SUCCESSFUL);
+  rtems_test_assert(expected == actual);
+}
+
 static void helper(rtems_task_argument arg)
 {
   test_context *ctx = &test_instance;
@@ -202,7 +227,8 @@ static void test(void)
   start_task(ctx, B_4, worker, 4, SCHED_B);
   start_task(ctx, B_5_0, worker, 5, SCHED_B);
   start_task(ctx, B_5_1, worker, 5, SCHED_B);
-  start_task(ctx, H, helper, 6, SCHED_B);
+  start_task(ctx, H_A, helper, 3, SCHED_A);
+  start_task(ctx, H_B, helper, 6, SCHED_B);
 
   sc = rtems_semaphore_create(
     rtems_build_name(' ', 'M', 'T', 'X'),
@@ -216,8 +242,10 @@ static void test(void)
   obtain(ctx);
   request(ctx, A_1, REQ_MTX_OBTAIN);
   check_generations(ctx, NONE, NONE);
+  assert_prio(ctx, M, 1);
   release(ctx);
   check_generations(ctx, A_1, NONE);
+  assert_prio(ctx, M, 3);
   request(ctx, A_1, REQ_MTX_RELEASE);
   check_generations(ctx, A_1, NONE);
 
@@ -226,8 +254,11 @@ static void test(void)
   request(ctx, A_1, REQ_MTX_OBTAIN);
   request(ctx, A_2_1, REQ_MTX_OBTAIN);
   check_generations(ctx, NONE, NONE);
+  assert_prio(ctx, M, 1);
   release(ctx);
   check_generations(ctx, A_1, NONE);
+  assert_prio(ctx, M, 3);
+  assert_prio(ctx, A_1, 1);
   request(ctx, A_1, REQ_MTX_RELEASE);
   check_generations(ctx, A_1, A_2_0);
   request(ctx, A_2_0, REQ_MTX_RELEASE);
@@ -240,8 +271,10 @@ static void test(void)
   request(ctx, B_4, REQ_MTX_OBTAIN);
   request(ctx, B_5_1, REQ_MTX_OBTAIN);
   check_generations(ctx, NONE, NONE);
+  assert_prio(ctx, M, 0);
   release(ctx);
   sync_with_helper(ctx);
+  assert_prio(ctx, M, 3);
   check_generations(ctx, B_4, NONE);
   request(ctx, B_4, REQ_MTX_RELEASE);
   check_generations(ctx, B_4, B_5_0);
@@ -252,26 +285,44 @@ static void test(void)
 
   obtain(ctx);
   request(ctx, A_2_0, REQ_MTX_OBTAIN);
+  check_generations(ctx, NONE, NONE);
+  assert_prio(ctx, M, 2);
   request(ctx, B_5_0, REQ_MTX_OBTAIN);
+  check_generations(ctx, NONE, NONE);
+  assert_prio(ctx, M, 0);
   request(ctx, B_5_1, REQ_MTX_OBTAIN);
   request(ctx, B_4, REQ_MTX_OBTAIN);
   request(ctx, A_2_1, REQ_MTX_OBTAIN);
   request(ctx, A_1, REQ_MTX_OBTAIN);
   check_generations(ctx, NONE, NONE);
   release(ctx);
+  sync_with_helper(ctx);
   check_generations(ctx, A_1, NONE);
+  assert_prio(ctx, M, 3);
+  assert_prio(ctx, A_1, 0);
   request(ctx, A_1, REQ_MTX_RELEASE);
   check_generations(ctx, A_1, B_4);
+  assert_prio(ctx, A_1, 1);
+  assert_prio(ctx, B_4, 0);
   request(ctx, B_4, REQ_MTX_RELEASE);
   check_generations(ctx, B_4, A_2_0);
+  assert_prio(ctx, B_4, 4);
+  assert_prio(ctx, A_2_0, 0);
   request(ctx, A_2_0, REQ_MTX_RELEASE);
   check_generations(ctx, A_2_0, B_5_0);
+  assert_prio(ctx, A_2_0, 2);
+  assert_prio(ctx, B_5_0, 0);
   request(ctx, B_5_0, REQ_MTX_RELEASE);
   check_generations(ctx, B_5_0, A_2_1);
+  assert_prio(ctx, B_5_0, 5);
+  assert_prio(ctx, A_2_1, 0);
   request(ctx, A_2_1, REQ_MTX_RELEASE);
   check_generations(ctx, A_2_1, B_5_1);
+  assert_prio(ctx, A_2_1, 2);
+  assert_prio(ctx, B_5_1, 5);
   request(ctx, B_5_1, REQ_MTX_RELEASE);
   check_generations(ctx, B_5_1, NONE);
+  assert_prio(ctx, B_5_1, 5);
 }
 
 static void Init(rtems_task_argument arg)




More information about the vc mailing list