[PATCH 10/12] smp: Optimize Simple SMP scheduler

Sebastian Huber sebastian.huber at embedded-brains.de
Tue Aug 13 13:42:55 UTC 2013


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          |   10 ++
 cpukit/score/src/schedulersimplesmp.c              |  135 +++++++++++++++-----
 cpukit/score/src/threadinitialize.c                |    1 +
 .../smptests/smpmigration01/smpmigration01.scn     |   24 ++--
 6 files changed, 143 insertions(+), 45 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..984bc0e 100644
--- a/cpukit/score/include/rtems/score/thread.h
+++ b/cpukit/score/include/rtems/score/thread.h
@@ -378,6 +378,16 @@ 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 is in a transient state.  The extract
+   * operation on a scheduled thread will produce threads in the air.  Such
+   * threads are no longer on the scheduled chain, but are still allocated to a
+   * processor.  The next enqueue or schedule operation will decide what to do.
+   */
+  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..f9fc2cc 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.
+     *
+     * XXX: 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 );
 
-  if ( ( *order )( &thread->Object.Node, &lowest_scheduled->Object.Node ) ) {
-    _Scheduler_SMP_Allocate_processor( thread, lowest_scheduled );
+      _Scheduler_simple_smp_Insert( &self->ready[ 0 ], thread, order );
 
-    _Scheduler_simple_smp_Insert( &self->scheduled, thread, order );
+      _Scheduler_simple_smp_Move_from_ready_to_scheduled(
+        self,
+        highest_ready
+      );
+    } else {
+      thread->is_scheduled = true;
 
-    _Scheduler_simple_smp_Move_from_scheduled_to_ready(
-      &self->ready[ 0 ],
-      lowest_scheduled
-    );
+      _Scheduler_simple_smp_Insert( &self->scheduled, thread, order );
+    }
   } else {
-    _Scheduler_simple_smp_Insert( &self->ready[ 0 ], thread, order );
+    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 );
+    }
+  }
+}
+
+void _Scheduler_simple_smp_Block( Thread_Control *thread )
+{
+  _Chain_Extract_unprotected( &thread->Object.Node );
+
+  if ( thread->is_scheduled ) {
+    Scheduler_SMP_Control *self = _Scheduler_SMP_Instance();
+
+    _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 ***
-- 
1.7.7




More information about the devel mailing list