From dafa5d88435853809040761b79ab9d8f2217281b Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Thu, 3 Sep 2015 10:27:16 +0200 Subject: 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 46568813a4..1092b65f9b 100644 --- a/cpukit/score/include/rtems/score/threadimpl.h +++ b/cpukit/score/include/rtems/score/threadimpl.h @@ -436,6 +436,37 @@ void _Thread_Raise_priority( Priority_Control new_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. * diff --git a/cpukit/score/include/rtems/score/threadqimpl.h b/cpukit/score/include/rtems/score/threadqimpl.h index bf01eb7404..510f886844 100644 --- a/cpukit/score/include/rtems/score/threadqimpl.h +++ b/cpukit/score/include/rtems/score/threadqimpl.h @@ -521,6 +521,31 @@ RTEMS_INLINE_ROUTINE void _Thread_queue_Destroy( #endif } +/** + * @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. * diff --git a/cpukit/score/src/coremutexseize.c b/cpukit/score/src/coremutexseize.c index ddc5d6b982..8059659a42 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 d3f965d55d..7d9c57f98b 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 ae637dda84..f03bab76ee 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 8f5d14f412..35e5e5bfbc 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 07473f50bd..7b017793ed 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 f0beeab4d7..bf22cf6133 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. +@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 6bd22dd3d7..210f1d0d92 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 db4114c564..de07f3c2d9 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, -@item message queues, and +@item message queues, +@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 1b2a1895ef..80b16fec90 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) -- cgit v1.2.3