[rtems commit] smp: Optimize Simple SMP scheduler
Sebastian Huber
sebh at rtems.org
Tue Aug 20 08:14:19 UTC 2013
Module: rtems
Branch: master
Commit: aea4a919933d721931f65d81391bf2b13b0f79aa
Changeset: http://git.rtems.org/rtems/commit/?id=aea4a919933d721931f65d81391bf2b13b0f79aa
Author: Sebastian Huber <sebastian.huber at embedded-brains.de>
Date: Thu Aug 8 11:49:15 2013 +0200
smp: Optimize Simple SMP scheduler
Add Thread_Control::is_in_the_air field if configured for SMP. This
helps to simplify the extract operation and avoids superfluous
inter-processor interrupts. Move the processor allocation step into the
enqueue operation.
Add and use _Scheduler_simple_smp_Get_highest_ready(). Add and use
_Scheduler_SMP_Get_lowest_scheduled().
---
.../score/include/rtems/score/schedulersimplesmp.h | 4 +-
.../score/include/rtems/score/schedulersmpimpl.h | 14 ++
cpukit/score/include/rtems/score/thread.h | 15 ++
cpukit/score/src/schedulersimplesmp.c | 137 +++++++++++++++-----
cpukit/score/src/threadinitialize.c | 1 +
.../smptests/smpmigration01/smpmigration01.scn | 24 ++--
6 files changed, 149 insertions(+), 46 deletions(-)
diff --git a/cpukit/score/include/rtems/score/schedulersimplesmp.h b/cpukit/score/include/rtems/score/schedulersimplesmp.h
index f62068a..7d29dda 100644
--- a/cpukit/score/include/rtems/score/schedulersimplesmp.h
+++ b/cpukit/score/include/rtems/score/schedulersimplesmp.h
@@ -57,7 +57,7 @@ extern "C" {
_Scheduler_simple_smp_Initialize, \
_Scheduler_simple_smp_Schedule, \
_Scheduler_simple_smp_Yield, \
- _Scheduler_simple_smp_Extract, \
+ _Scheduler_simple_smp_Block, \
_Scheduler_simple_smp_Enqueue_priority_fifo, \
_Scheduler_default_Allocate, \
_Scheduler_default_Free, \
@@ -73,6 +73,8 @@ extern "C" {
void _Scheduler_simple_smp_Initialize( void );
+void _Scheduler_simple_smp_Block( Thread_Control *thread );
+
void _Scheduler_simple_smp_Enqueue_priority_fifo( Thread_Control *thread );
void _Scheduler_simple_smp_Enqueue_priority_lifo( Thread_Control *thread );
diff --git a/cpukit/score/include/rtems/score/schedulersmpimpl.h b/cpukit/score/include/rtems/score/schedulersmpimpl.h
index d23b0c0..40e94cb 100644
--- a/cpukit/score/include/rtems/score/schedulersmpimpl.h
+++ b/cpukit/score/include/rtems/score/schedulersmpimpl.h
@@ -83,6 +83,20 @@ static inline void _Scheduler_SMP_Allocate_processor(
}
}
+static inline Thread_Control *_Scheduler_SMP_Get_lowest_scheduled(
+ Scheduler_SMP_Control *self
+)
+{
+ Thread_Control *lowest_ready = NULL;
+ Chain_Control *scheduled = &self->scheduled;
+
+ if ( !_Chain_Is_empty( scheduled ) ) {
+ lowest_ready = (Thread_Control *) _Chain_Last( scheduled );
+ }
+
+ return lowest_ready;
+}
+
/** @} */
#ifdef __cplusplus
diff --git a/cpukit/score/include/rtems/score/thread.h b/cpukit/score/include/rtems/score/thread.h
index d346ead..77f1d7a 100644
--- a/cpukit/score/include/rtems/score/thread.h
+++ b/cpukit/score/include/rtems/score/thread.h
@@ -378,6 +378,21 @@ struct Thread_Control_struct {
bool is_scheduled;
/**
+ * @brief This field is true if the thread is in the air.
+ *
+ * A thread is in the air if it has an allocated processor (it is an
+ * executing or heir thread on exactly one processor) and it is not a member
+ * of the scheduled chain. The extract operation on a scheduled thread will
+ * produce threads in the air (see also _Thread_Set_transient()). The next
+ * enqueue or schedule operation will decide what to do based on this state
+ * indication. It can either place the thread back on the scheduled chain
+ * and the thread can keep its allocated processor, or it can take the
+ * processor away from the thread and give the processor to another thread of
+ * higher priority.
+ */
+ bool is_in_the_air;
+
+ /**
* @brief This field is true if the thread is executing.
*
* A thread is executing if it executes on a processor. An executing thread
diff --git a/cpukit/score/src/schedulersimplesmp.c b/cpukit/score/src/schedulersimplesmp.c
index fa128f8..a46f58e 100644
--- a/cpukit/score/src/schedulersimplesmp.c
+++ b/cpukit/score/src/schedulersimplesmp.c
@@ -34,22 +34,42 @@ void _Scheduler_simple_smp_Initialize( void )
_Scheduler.information = self;
}
+static Thread_Control *_Scheduler_simple_smp_Get_highest_ready(
+ Scheduler_SMP_Control *self
+)
+{
+ Thread_Control *highest_ready = NULL;
+ Chain_Control *ready = &self->ready[ 0 ];
+
+ if ( !_Chain_Is_empty( ready ) ) {
+ highest_ready = (Thread_Control *) _Chain_First( ready );
+ }
+
+ return highest_ready;
+}
+
static void _Scheduler_simple_smp_Move_from_scheduled_to_ready(
- Chain_Control *ready_chain,
+ Scheduler_SMP_Control *self,
Thread_Control *scheduled_to_ready
)
{
_Chain_Extract_unprotected( &scheduled_to_ready->Object.Node );
- _Scheduler_simple_Insert_priority_lifo( ready_chain, scheduled_to_ready );
+ _Scheduler_simple_Insert_priority_lifo(
+ &self->ready[ 0 ],
+ scheduled_to_ready
+ );
}
static void _Scheduler_simple_smp_Move_from_ready_to_scheduled(
- Chain_Control *scheduled_chain,
+ Scheduler_SMP_Control *self,
Thread_Control *ready_to_scheduled
)
{
_Chain_Extract_unprotected( &ready_to_scheduled->Object.Node );
- _Scheduler_simple_Insert_priority_fifo( scheduled_chain, ready_to_scheduled );
+ _Scheduler_simple_Insert_priority_fifo(
+ &self->scheduled,
+ ready_to_scheduled
+ );
}
static void _Scheduler_simple_smp_Insert(
@@ -61,6 +81,19 @@ static void _Scheduler_simple_smp_Insert(
_Chain_Insert_ordered_unprotected( chain, &thread->Object.Node, order );
}
+static void _Scheduler_simple_smp_Schedule_highest_ready(
+ Scheduler_SMP_Control *self,
+ Thread_Control *victim
+)
+{
+ Thread_Control *highest_ready =
+ (Thread_Control *) _Chain_First( &self->ready[ 0 ] );
+
+ _Scheduler_SMP_Allocate_processor( highest_ready, victim );
+
+ _Scheduler_simple_smp_Move_from_ready_to_scheduled( self, highest_ready );
+}
+
static void _Scheduler_simple_smp_Enqueue_ordered(
Thread_Control *thread,
Chain_Node_order order
@@ -68,24 +101,68 @@ static void _Scheduler_simple_smp_Enqueue_ordered(
{
Scheduler_SMP_Control *self = _Scheduler_SMP_Instance();
- /*
- * The scheduled chain has exactly processor count nodes after
- * initialization, thus the lowest priority scheduled thread exists.
- */
- Thread_Control *lowest_scheduled =
- (Thread_Control *) _Chain_Last( &self->scheduled );
+ if ( thread->is_in_the_air ) {
+ Thread_Control *highest_ready =
+ _Scheduler_simple_smp_Get_highest_ready( self );
+
+ thread->is_in_the_air = false;
+
+ /*
+ * The thread has been extracted from the scheduled chain. We have to
+ * place it now on the scheduled or ready chain.
+ *
+ * NOTE: Do not exchange parameters to do the negation of the order check.
+ */
+ if (
+ highest_ready != NULL
+ && !( *order )( &thread->Object.Node, &highest_ready->Object.Node )
+ ) {
+ _Scheduler_SMP_Allocate_processor( highest_ready, thread );
+
+ _Scheduler_simple_smp_Insert( &self->ready[ 0 ], thread, order );
+
+ _Scheduler_simple_smp_Move_from_ready_to_scheduled(
+ self,
+ highest_ready
+ );
+ } else {
+ thread->is_scheduled = true;
+
+ _Scheduler_simple_smp_Insert( &self->scheduled, thread, order );
+ }
+ } else {
+ Thread_Control *lowest_scheduled = _Scheduler_SMP_Get_lowest_scheduled( self );
+
+ /*
+ * The scheduled chain is empty if nested interrupts change the priority of
+ * all scheduled threads. These threads are in the air.
+ */
+ if (
+ lowest_scheduled != NULL
+ && ( *order )( &thread->Object.Node, &lowest_scheduled->Object.Node )
+ ) {
+ _Scheduler_SMP_Allocate_processor( thread, lowest_scheduled );
+
+ _Scheduler_simple_smp_Insert( &self->scheduled, thread, order );
+
+ _Scheduler_simple_smp_Move_from_scheduled_to_ready(
+ self,
+ lowest_scheduled
+ );
+ } else {
+ _Scheduler_simple_smp_Insert( &self->ready[ 0 ], thread, order );
+ }
+ }
+}
- if ( ( *order )( &thread->Object.Node, &lowest_scheduled->Object.Node ) ) {
- _Scheduler_SMP_Allocate_processor( thread, lowest_scheduled );
+void _Scheduler_simple_smp_Block( Thread_Control *thread )
+{
+ _Chain_Extract_unprotected( &thread->Object.Node );
- _Scheduler_simple_smp_Insert( &self->scheduled, thread, order );
+ if ( thread->is_scheduled ) {
+ Scheduler_SMP_Control *self = _Scheduler_SMP_Instance();
- _Scheduler_simple_smp_Move_from_scheduled_to_ready(
- &self->ready[ 0 ],
- lowest_scheduled
- );
- } else {
- _Scheduler_simple_smp_Insert( &self->ready[ 0 ], thread, order );
+ _Scheduler_simple_smp_Schedule_highest_ready( self, thread );
}
}
@@ -107,21 +184,9 @@ void _Scheduler_simple_smp_Enqueue_priority_fifo( Thread_Control *thread )
void _Scheduler_simple_smp_Extract( Thread_Control *thread )
{
- Scheduler_SMP_Control *self = _Scheduler_SMP_Instance();
+ thread->is_in_the_air = true;
_Chain_Extract_unprotected( &thread->Object.Node );
-
- if ( thread->is_scheduled ) {
- Thread_Control *highest_ready =
- (Thread_Control *) _Chain_First( &self->ready[ 0 ] );
-
- _Scheduler_SMP_Allocate_processor( highest_ready, thread );
-
- _Scheduler_simple_smp_Move_from_ready_to_scheduled(
- &self->scheduled,
- highest_ready
- );
- }
}
void _Scheduler_simple_smp_Yield( Thread_Control *thread )
@@ -138,5 +203,11 @@ void _Scheduler_simple_smp_Yield( Thread_Control *thread )
void _Scheduler_simple_smp_Schedule( Thread_Control *thread )
{
- ( void ) thread;
+ if ( thread->is_in_the_air ) {
+ Scheduler_SMP_Control *self = _Scheduler_SMP_Instance();
+
+ thread->is_in_the_air = false;
+
+ _Scheduler_simple_smp_Schedule_highest_ready( self, thread );
+ }
}
diff --git a/cpukit/score/src/threadinitialize.c b/cpukit/score/src/threadinitialize.c
index a876147..34198ca 100644
--- a/cpukit/score/src/threadinitialize.c
+++ b/cpukit/score/src/threadinitialize.c
@@ -180,6 +180,7 @@ bool _Thread_Initialize(
#if defined(RTEMS_SMP)
the_thread->is_scheduled = false;
+ the_thread->is_in_the_air = false;
the_thread->is_executing = false;
/* Initialize the cpu field for the non-SMP schedulers */
diff --git a/testsuites/smptests/smpmigration01/smpmigration01.scn b/testsuites/smptests/smpmigration01/smpmigration01.scn
index dc3bae2..c5a2106 100644
--- a/testsuites/smptests/smpmigration01/smpmigration01.scn
+++ b/testsuites/smptests/smpmigration01/smpmigration01.scn
@@ -1,17 +1,17 @@
*** TEST SMPMIGRATION 1 ***
runner 0
- cpu 0 tokens 411501
- cpu 0 cycles 9464534
- cpu 1 tokens 411501
- cpu 1 cycles 9464802
+ cpu 0 tokens 530399
+ cpu 0 cycles 10077490
+ cpu 1 tokens 530399
+ cpu 1 cycles 10071429
runner 1
- cpu 0 tokens 411500
- cpu 0 cycles 41936630
- cpu 1 tokens 411501
- cpu 1 cycles 42009945
+ cpu 0 tokens 530399
+ cpu 0 cycles 5978212
+ cpu 1 tokens 530399
+ cpu 1 cycles 7951897
runner 2
- cpu 0 tokens 411501
- cpu 0 cycles 6583983
- cpu 1 tokens 411500
- cpu 1 cycles 6583701
+ cpu 0 tokens 530399
+ cpu 0 cycles 10070929
+ cpu 1 tokens 530398
+ cpu 1 cycles 10106437
*** END OF TEST SMPMIGRATION 1 ***
More information about the vc
mailing list