Various optimizations to the scheduler.

git-svn-id: svn://svn.code.sf.net/p/chibios/svn/trunk@378 35acf78f-673a-0410-8e92-d51de3d6d3f4

10 files changed, 120 insertions, 67 deletions

diff --git a/ports/ARMCM3/chcore.c b/ports/ARMCM3/chcore.c
index 1a631e36b..199c71fd9 100644
--- a/ports/ARMCM3/chcore.c
+++ b/ports/ARMCM3/chcore.c
@@ -167,8 +167,8 @@ void PendSVVector(void) {
   PUSH_CONTEXT(sp_thd);
 
   (otp = currp)->p_ctx.r13 = sp_thd;
-  chSchReadyI(otp);
   (currp = fifo_remove(&rlist.r_queue))->p_state = PRCURR;
+  chSchReadyI(otp);
 #ifdef CH_USE_ROUNDROBIN
   /* set the round-robin time quantum */
   rlist.r_preempt = CH_TIME_QUANTUM;
diff --git a/readme.txt b/readme.txt
index 87b4f3a5d..a272b62d2 100644
--- a/readme.txt
+++ b/readme.txt
@@ -80,9 +80,15 @@ Win32-MinGW            - ChibiOS/RT simulator and demo into a WIN32 process,
   faster if the feature is not required. Threads at the same priority level

   are still supported when the feature is disabled but the scheduling among

   them becomes cooperative.

+- OPT: Improved reschedulation time by reordering the sequence of operations,

+  now during enqueuing the ready list contains one less element. This change

+  also slightly improves the interrupt latency.

+- OPT: Optimization to the chSemReset(), reversed the order of dequeuing.

 - FIX: Fixed a bug in the chThdSetPriority() API.

 - FIX: Modified the structure names into nvic.h in order to not make them

   collide with external libraries.

+- Added a benchmark to the test suit that measures the mass reschedulation

+  performance.

 - Made the Cortex-M3 port preemption code more readable.

 

 *** 0.6.8 ***

diff --git a/src/chlists.c b/src/chlists.c
index 3b173c94d..dcb3b0412 100644
--- a/src/chlists.c
+++ b/src/chlists.c
@@ -47,19 +47,19 @@ void prio_insert(Thread *tp, ThreadsQueue *tqp) {
 }

 

 /*

- * Inserts a Thread into a FIFO queue.

+ * Inserts a Thread into a queue.

  *

  * @param tp the pointer to the thread to be inserted in the list

  * @param tqp the pointer to the threads list header

  */

-void fifo_insert(Thread *tp, ThreadsQueue *tqp) {

+void queue_insert(Thread *tp, ThreadsQueue *tqp) {

 

   tp->p_prev = (tp->p_next = (Thread *)tqp)->p_prev;

   tp->p_prev->p_next = tqp->p_prev = tp;

 }

 

 /*

- * Removes the first-out Thread from a FIFO queue and returns it.

+ * Removes the first-out Thread from a queue and returns it.

  *

  * @param tqp the pointer to the threads list header

  * @return the removed thread pointer

@@ -72,6 +72,19 @@ Thread *fifo_remove(ThreadsQueue *tqp) {
 }

 

 /*

+ * Removes the last-out Thread from a queue and returns it.

+ *

+ * @param tqp the pointer to the threads list header

+ * @return the removed thread pointer

+ */

+Thread *lifo_remove(ThreadsQueue *tqp) {

+  Thread *tp = tqp->p_next;

+

+  (tqp->p_next = tp->p_next)->p_prev = (Thread *)tqp;

+  return tp;

+}

+

+/*

  * Removes a Thread from a FIFO list and returns it.

  *

  * @param tp the pointer to the thread to be removed from the list

diff --git a/src/chmsg.c b/src/chmsg.c
index bcc7117e2..03b7edd01 100644
--- a/src/chmsg.c
+++ b/src/chmsg.c
@@ -40,9 +40,9 @@ msg_t chMsgSend(Thread *tp, msg_t msg) {
   if (tp->p_flags & P_MSGBYPRIO)

     prio_insert(currp, &tp->p_msgqueue);

   else

-    fifo_insert(currp, &tp->p_msgqueue);

+    queue_insert(currp, &tp->p_msgqueue);

 #else

-  fifo_insert(currp, &tp->p_msgqueue);

+  queue_insert(currp, &tp->p_msgqueue);

 #endif

   currp->p_msg = msg;

   currp->p_wtthdp = tp;

@@ -79,9 +79,9 @@ msg_t chMsgSendWithEvent(Thread *tp, msg_t msg, EventSource *esp) {
   if (tp->p_flags & P_MSGBYPRIO)

     prio_insert(currp, &tp->p_msgqueue);

   else

-    fifo_insert(currp, &tp->p_msgqueue);

+    queue_insert(currp, &tp->p_msgqueue);

 #else

-  fifo_insert(currp, &tp->p_msgqueue);

+  queue_insert(currp, &tp->p_msgqueue);

 #endif

   chEvtBroadcastI(esp);

   currp->p_wtthdp = tp;

diff --git a/src/chschd.c b/src/chschd.c
index c97eea1e8..8b606cd1b 100644
--- a/src/chschd.c
+++ b/src/chschd.c
@@ -174,18 +174,17 @@ void chSchWakeupS(Thread *ntp, msg_t msg) {
  * Intended to be called if \p chSchRescRequired() evaluates to \p TRUE.
  */
 void chSchDoRescheduleI(void) {
-  /* put the running thread on the ready queue */
+
   Thread *otp = currp;
-  chSchReadyI(otp);
-  /* pick the first thread from the ready queue */
+  /* pick the first thread from the ready queue and makes it current */
   (currp = fifo_remove(&rlist.r_queue))->p_state = PRCURR;
+  chSchReadyI(otp);
 #ifdef CH_USE_ROUNDROBIN
   rlist.r_preempt = CH_TIME_QUANTUM;
 #endif
 #ifdef CH_USE_TRACE
   chDbgTrace(otp, currp);
 #endif
-  /* switch thread context */
   chSysSwitchI(otp, currp);
 }
 
diff --git a/src/chsem.c b/src/chsem.c
index d1199f072..b5c197b6b 100644
--- a/src/chsem.c
+++ b/src/chsem.c
@@ -72,7 +72,7 @@ void chSemResetI(Semaphore *sp, cnt_t n) {
   cnt = sp->s_cnt;

   sp->s_cnt = n;

   while (cnt++ < 0)

-    chSchReadyI(fifo_remove(&sp->s_queue))->p_rdymsg = RDY_RESET;

+    chSchReadyI(lifo_remove(&sp->s_queue))->p_rdymsg = RDY_RESET;

 }

 

 /**

@@ -101,7 +101,7 @@ msg_t chSemWait(Semaphore *sp) {
 msg_t chSemWaitS(Semaphore *sp) {

 

   if (--sp->s_cnt < 0) {

-    fifo_insert(currp, &sp->s_queue);

+    queue_insert(currp, &sp->s_queue);

     currp->p_wtsemp = sp;

     chSchGoSleepS(PRWTSEM);

     return currp->p_rdymsg;

@@ -140,7 +140,7 @@ msg_t chSemWaitTimeout(Semaphore *sp, systime_t time) {
 msg_t chSemWaitTimeoutS(Semaphore *sp, systime_t time) {

 

   if (--sp->s_cnt < 0) {

-    fifo_insert(currp, &sp->s_queue);

+    queue_insert(currp, &sp->s_queue);

     currp->p_wtsemp = sp;

     return chSchGoSleepTimeoutS(PRWTSEM, time);

   }

@@ -201,7 +201,7 @@ msg_t chSemSignalWait(Semaphore *sps, Semaphore *spw) {
     chSchReadyI(fifo_remove(&sps->s_queue))->p_rdymsg = RDY_OK;

 

   if (--spw->s_cnt < 0) {

-    fifo_insert(currp, &spw->s_queue);

+    queue_insert(currp, &spw->s_queue);

     currp->p_wtsemp = spw;

     chSchGoSleepS(PRWTSEM);

     msg = currp->p_rdymsg;

diff --git a/src/include/inline.h b/src/include/inline.h
index 85de20f3f..9cc18974d 100644
--- a/src/include/inline.h
+++ b/src/include/inline.h
@@ -36,7 +36,7 @@ static INLINE void prio_insert(Thread *tp, ThreadsQueue *tqp) {
   tp->p_prev->p_next = cp->p_prev = tp;

 }

 

-static INLINE void fifo_insert(Thread *tp, ThreadsQueue *tqp) {

+static INLINE void queue_insert(Thread *tp, ThreadsQueue *tqp) {

 

   tp->p_prev = (tp->p_next = (Thread *)tqp)->p_prev;

   tp->p_prev->p_next = tqp->p_prev = tp;

@@ -49,6 +49,13 @@ static INLINE Thread *fifo_remove(ThreadsQueue *tqp) {
   return tp;

 }

 

+static INLINE Thread *lifo_remove(ThreadsQueue *tqp) {

+  Thread *tp = tqp->p_prev;

+

+  (tqp->p_prev = tp->p_prev)->p_next = (Thread *)tqp;

+  return tp;

+}

+

 static INLINE Thread *dequeue(Thread *tp) {

 

   tp->p_prev->p_next = tp->p_next;

diff --git a/src/include/lists.h b/src/include/lists.h
index d98892600..741648a03 100644
--- a/src/include/lists.h
+++ b/src/include/lists.h
@@ -61,8 +61,9 @@ typedef struct {
 extern "C" {

 #endif

   void prio_insert(Thread *tp, ThreadsQueue *tqp);

-  void fifo_insert(Thread *tp, ThreadsQueue *tqp);

+  void queue_insert(Thread *tp, ThreadsQueue *tqp);

   Thread *fifo_remove(ThreadsQueue *tqp);

+  Thread *lifo_remove(ThreadsQueue *tqp);

   Thread *dequeue(Thread *tp);

   void list_insert(Thread *tp, ThreadsList *tlp);

   Thread *list_remove(ThreadsList *tlp);

diff --git a/test/testbmk.c b/test/testbmk.c
index 392297782..f2fcb94dc 100644
--- a/test/testbmk.c
+++ b/test/testbmk.c
@@ -21,6 +21,10 @@
 

 #include "test.h"

 

+static Semaphore sem1;

+

+static void empty(void) {}

+

 static msg_t thread1(void *p) {

   msg_t msg;

 

@@ -52,12 +56,6 @@ static char *bmk1_gettest(void) {
   return "Benchmark, context switch #1, optimal";

 }

 

-static void bmk1_setup(void) {

-}

-

-static void bmk1_teardown(void) {

-}

-

 static void bmk1_execute(void) {

   uint32_t n;

 

@@ -74,8 +72,8 @@ static void bmk1_execute(void) {
 

 const struct testcase testbmk1 = {

   bmk1_gettest,

-  bmk1_setup,

-  bmk1_teardown,

+  empty,

+  empty,

   bmk1_execute

 };

 

@@ -84,12 +82,6 @@ static char *bmk2_gettest(void) {
   return "Benchmark, context switch #2, empty ready list";

 }

 

-static void bmk2_setup(void) {

-}

-

-static void bmk2_teardown(void) {

-}

-

 static void bmk2_execute(void) {

   uint32_t n;

 

@@ -106,8 +98,8 @@ static void bmk2_execute(void) {
 

 const struct testcase testbmk2 = {

   bmk2_gettest,

-  bmk2_setup,

-  bmk2_teardown,

+  empty,

+  empty,

   bmk2_execute

 };

 

@@ -121,12 +113,6 @@ static char *bmk3_gettest(void) {
   return "Benchmark, context switch #3, 4 threads in ready list";

 }

 

-static void bmk3_setup(void) {

-}

-

-static void bmk3_teardown(void) {

-}

-

 static void bmk3_execute(void) {

   uint32_t n;

 

@@ -147,8 +133,8 @@ static void bmk3_execute(void) {
 

 const struct testcase testbmk3 = {

   bmk3_gettest,

-  bmk3_setup,

-  bmk3_teardown,

+  empty,

+  empty,

   bmk3_execute

 };

 

@@ -157,12 +143,6 @@ static char *bmk4_gettest(void) {
   return "Benchmark, threads creation/termination, worst case";

 }

 

-static void bmk4_setup(void) {

-}

-

-static void bmk4_teardown(void) {

-}

-

 static void bmk4_execute(void) {

 

   uint32_t n = 0;

@@ -184,8 +164,8 @@ static void bmk4_execute(void) {
 

 const struct testcase testbmk4 = {

   bmk4_gettest,

-  bmk4_setup,

-  bmk4_teardown,

+  empty,

+  empty,

   bmk4_execute

 };

 

@@ -194,12 +174,6 @@ static char *bmk5_gettest(void) {
   return "Benchmark, threads creation/termination, optimal";

 }

 

-static void bmk5_setup(void) {

-}

-

-static void bmk5_teardown(void) {

-}

-

 static void bmk5_execute(void) {

 

   uint32_t n = 0;

@@ -221,23 +195,75 @@ static void bmk5_execute(void) {
 

 const struct testcase testbmk5 = {

   bmk5_gettest,

-  bmk5_setup,

-  bmk5_teardown,

+  empty,

+  empty,

   bmk5_execute

 };

 

+static msg_t thread3(void *p) {

+

+  while (!chThdShouldTerminate())

+    chSemWait(&sem1);

+  return 0;

+}

+

 static char *bmk6_gettest(void) {

 

-  return "Benchmark, I/O Queues throughput";

+  return "Benchmark, mass reschedulation, 5 threads";

 }

 

 static void bmk6_setup(void) {

-}

 

-static void bmk6_teardown(void) {

+  chSemInit(&sem1, 0);

 }

 

 static void bmk6_execute(void) {

+  uint32_t n;

+

+  threads[0] = chThdCreateFast(chThdGetPriority()+1, wa[0], STKSIZE, thread3);

+  threads[1] = chThdCreateFast(chThdGetPriority()+2, wa[1], STKSIZE, thread3);

+  threads[2] = chThdCreateFast(chThdGetPriority()+3, wa[2], STKSIZE, thread3);

+  threads[3] = chThdCreateFast(chThdGetPriority()+4, wa[3], STKSIZE, thread3);

+  threads[4] = chThdCreateFast(chThdGetPriority()+5, wa[4], STKSIZE, thread3);

+

+  n = 0;

+  test_wait_tick();

+  test_start_timer(1000);

+  do {

+    chSemReset(&sem1, 0);

+    n++;

+#if defined(WIN32)

+    ChkIntSources();

+#endif

+  } while (!test_timer_done);

+  chThdTerminate(threads[0]);

+  chThdTerminate(threads[1]);

+  chThdTerminate(threads[2]);

+  chThdTerminate(threads[3]);

+  chThdTerminate(threads[4]);

+  chSemReset(&sem1, 0);

+  test_wait_threads();

+

+  test_print("--- Score : ");

+  test_printn(n);

+  test_print(" reschedulations/S, ");

+  test_printn(n * 6);

+  test_println(" ctxswc/S");

+}

+

+const struct testcase testbmk6 = {

+  bmk6_gettest,

+  bmk6_setup,

+  empty,

+  bmk6_execute

+};

+

+static char *bmk7_gettest(void) {

+

+  return "Benchmark, I/O Queues throughput";

+}

+

+static void bmk7_execute(void) {

   static uint8_t ib[16];

   static Queue iq;

 

@@ -264,9 +290,9 @@ static void bmk6_execute(void) {
   test_println(" bytes/S");

 }

 

-const struct testcase testbmk6 = {

-  bmk6_gettest,

-  bmk6_setup,

-  bmk6_teardown,

-  bmk6_execute

+const struct testcase testbmk7 = {

+  bmk7_gettest,

+  empty,

+  empty,

+  bmk7_execute

 };

diff --git a/test/testbmk.h b/test/testbmk.h
index e52abee28..5e99dc3d5 100644
--- a/test/testbmk.h
+++ b/test/testbmk.h
@@ -21,6 +21,7 @@
 #define _TESTBMK_H_

 

 extern const struct testcase testbmk1, testbmk2, testbmk3,

-                             testbmk4, testbmk5, testbmk6;

+                             testbmk4, testbmk5, testbmk6,

+                             testbmk7;

 

 #endif /* _TESTBMK_H_ */