Round robin scheduling improvements.

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

5 files changed, 102 insertions, 25 deletions

diff --git a/os/kernel/include/chschd.h b/os/kernel/include/chschd.h
index 54076ec56..215398659 100644
--- a/os/kernel/include/chschd.h
+++ b/os/kernel/include/chschd.h
@@ -95,9 +95,6 @@ typedef struct {
   Thread                *r_older;   /**< @brief Older registry element.     */

 #endif

   /* End of the fields shared with the Thread structure.*/

-#if (CH_TIME_QUANTUM > 0) || defined(__DOXYGEN__)

-  cnt_t                 r_preempt;  /**< @brief Round robin counter.        */

-#endif

   Thread                *r_current; /**< @brief The currently running

                                                 thread.                     */

 } ReadyList;

@@ -154,6 +151,12 @@ extern "C" {
 #if !defined(PORT_OPTIMIZED_ISPREEMPTIONREQUIRED)

   bool_t chSchIsPreemptionRequired(void);

 #endif

+#if !defined(PORT_OPTIMIZED_DORESCHEDULEBEHIND) || defined(__DOXYGEN__)

+  void chSchDoRescheduleBehind(void);

+#endif

+#if !defined(PORT_OPTIMIZED_DORESCHEDULEAHEAD) || defined(__DOXYGEN__)

+  void chSchDoRescheduleAhead(void);

+#endif

 #if !defined(PORT_OPTIMIZED_DORESCHEDULE)

   void chSchDoReschedule(void);

 #endif

@@ -197,7 +200,7 @@ extern "C" {
 #if !defined(PORT_OPTIMIZED_DOYIELDS) || defined(__DOXYGEN__)

 #define chSchDoYieldS() {                                                   \

   if (chSchCanYieldS())                                                     \

-    chSchDoReschedule();                                                    \

+    chSchDoRescheduleBehind();                                              \

 }

 #endif /* !defined(PORT_OPTIMIZED_DOYIELDS) */

 

@@ -212,19 +215,19 @@ extern "C" {
 #define chSchPreemption() {                                                 \

   tprio_t p1 = firstprio(&rlist.r_queue);                                   \

   tprio_t p2 = currp->p_prio;                                               \

-  if (rlist.r_preempt) {                                                    \

+  if (currp->p_preempt) {                                                   \

     if (p1 > p2)                                                            \

-      chSchDoReschedule();                                                  \

+      chSchDoRescheduleAhead();                                             \

   }                                                                         \

   else {                                                                    \

     if (p1 >= p2)                                                           \

-      chSchDoReschedule();                                                  \

+      chSchDoRescheduleBehind();                                            \

   }                                                                         \

 }

 #else /* CH_TIME_QUANTUM == 0 */

 #define chSchPreemption() {                                                 \

   if (p1 >= p2)                                                             \

-    chSchDoReschedule();                                                    \

+    chSchDoRescheduleAhead();                                               \

 }

 #endif /* CH_TIME_QUANTUM == 0 */

 /** @} */

diff --git a/os/kernel/include/chthreads.h b/os/kernel/include/chthreads.h
index 66b593818..421a3e23f 100644
--- a/os/kernel/include/chthreads.h
+++ b/os/kernel/include/chthreads.h
@@ -122,6 +122,12 @@ struct Thread {
    */

   trefs_t               p_refs;

 #endif

+  /**

+   * @brief Number of ticks remaining to this thread.

+   */

+#if (CH_TIME_QUANTUM > 0) || defined(__DOXYGEN__)

+  tslices_t             p_preempt;

+#endif

 #if CH_DBG_THREADS_PROFILING || defined(__DOXYGEN__)

   /**

    * @brief Thread consumed time in ticks.

diff --git a/os/kernel/src/chschd.c b/os/kernel/src/chschd.c
index 4acc500af..3dd226b1b 100644
--- a/os/kernel/src/chschd.c
+++ b/os/kernel/src/chschd.c
@@ -49,9 +49,6 @@ void _scheduler_init(void) {
 

   queue_init(&rlist.r_queue);

   rlist.r_prio = NOPRIO;

-#if CH_TIME_QUANTUM > 0

-  rlist.r_preempt = CH_TIME_QUANTUM;

-#endif

 #if CH_USE_REGISTRY

   rlist.r_newer = rlist.r_older = (Thread *)&rlist;

 #endif

@@ -59,6 +56,8 @@ void _scheduler_init(void) {
 

 /**

  * @brief   Inserts a thread in the Ready List.

+ * @details The thread is positioned behind all threads with higher or equal

+ *          priority.

  * @pre     The thread must not be already inserted in any list through its

  *          @p p_next and @p p_prev or list corruption would occur.

  * @post    This function does not reschedule so a call to a rescheduling

@@ -111,7 +110,9 @@ void chSchGoSleepS(tstate_t newstate) {
 

   (otp = currp)->p_state = newstate;

 #if CH_TIME_QUANTUM > 0

-  rlist.r_preempt = CH_TIME_QUANTUM;

+  /* The thread is renouncing its remaining time slices so it will have a new

+     time quantum when it will wakeup.*/

+  otp->p_preempt = CH_TIME_QUANTUM;

 #endif

   setcurrp(fifo_remove(&rlist.r_queue));

   currp->p_state = THD_STATE_CURRENT;

@@ -222,9 +223,6 @@ void chSchWakeupS(Thread *ntp, msg_t msg) {
     chSchReadyI(ntp);

   else {

     Thread *otp = chSchReadyI(currp);

-#if CH_TIME_QUANTUM > 0

-    rlist.r_preempt = CH_TIME_QUANTUM;

-#endif

     setcurrp(ntp);

     ntp->p_state = THD_STATE_CURRENT;

     chSysSwitch(ntp, otp);

@@ -237,7 +235,7 @@ void chSchWakeupS(Thread *ntp, msg_t msg) {
  * @details If a thread with a higher priority than the current thread is in

  *          the ready list then make the higher priority thread running.

  *

- * @iclass

+ * @sclass

  */

 #if !defined(PORT_OPTIMIZED_RESCHEDULES) || defined(__DOXYGEN__)

 void chSchRescheduleS(void) {

@@ -245,7 +243,7 @@ void chSchRescheduleS(void) {
   chDbgCheckClassS();

 

   if (chSchIsRescRequiredI())

-    chSchDoReschedule();

+    chSchDoRescheduleAhead();

 }

 #endif /* !defined(PORT_OPTIMIZED_RESCHEDULES) */

 

@@ -271,7 +269,7 @@ bool_t chSchIsPreemptionRequired(void) {
      if the first thread on the ready queue has a higher priority.

      Otherwise, if the running thread has used up its time quantum, reschedule

      if the first thread on the ready queue has equal or higher priority.*/

-  return rlist.r_preempt ? p1 > p2 : p1 >= p2;

+  return currp->r_preempt ? p1 > p2 : p1 >= p2;

 #else

   /* If the round robin preemption feature is not enabled then performs a

      simpler comparison.*/

@@ -282,25 +280,92 @@ bool_t chSchIsPreemptionRequired(void) {
 

 /**

  * @brief   Switches to the first thread on the runnable queue.

+ * @details The current thread is positioned in the ready list behind all

+ *          threads having the same priority. The thread regains its time

+ *          quantum.

  * @note    Not a user function, it is meant to be invoked by the scheduler

  *          itself or from within the port layer.

  *

  * @special

  */

-#if !defined(PORT_OPTIMIZED_DORESCHEDULE) || defined(__DOXYGEN__)

-void chSchDoReschedule(void) {

+#if !defined(PORT_OPTIMIZED_DORESCHEDULEBEHIND) || defined(__DOXYGEN__)

+void chSchDoRescheduleBehind(void) {

   Thread *otp;

 

-#if CH_TIME_QUANTUM > 0

-  rlist.r_preempt = CH_TIME_QUANTUM;

-#endif

   otp = currp;

   /* Picks the first thread from the ready queue and makes it current.*/

   setcurrp(fifo_remove(&rlist.r_queue));

   currp->p_state = THD_STATE_CURRENT;

+  otp->p_preempt = CH_TIME_QUANTUM;

   chSchReadyI(otp);

   chSysSwitch(currp, otp);

 }

+#endif /* !defined(PORT_OPTIMIZED_DORESCHEDULEBEHIND) */

+

+/**

+ * @brief   Switches to the first thread on the runnable queue.

+ * @details The current thread is positioned in the ready list ahead of all

+ *          threads having the same priority.

+ * @note    Not a user function, it is meant to be invoked by the scheduler

+ *          itself or from within the port layer.

+ *

+ * @special

+ */

+#if !defined(PORT_OPTIMIZED_DORESCHEDULEAHEAD) || defined(__DOXYGEN__)

+void chSchDoRescheduleAhead(void) {

+  Thread *otp, *cp;

+

+  otp = currp;

+  /* Picks the first thread from the ready queue and makes it current.*/

+  setcurrp(fifo_remove(&rlist.r_queue));

+  currp->p_state = THD_STATE_CURRENT;

+

+  otp->p_state = THD_STATE_READY;

+  cp = (Thread *)&rlist.r_queue;

+  do {

+    cp = cp->p_next;

+  } while (cp->p_prio > otp->p_prio);

+  /* Insertion on p_prev.*/

+  otp->p_next = cp;

+  otp->p_prev = cp->p_prev;

+  otp->p_prev->p_next = cp->p_prev = otp;

+

+  chSysSwitch(currp, otp);

+}

+#endif /* !defined(PORT_OPTIMIZED_DORESCHEDULEAHEAD) */

+

+/**

+ * @brief   Switches to the first thread on the runnable queue.

+ * @details The current thread is positioned in the ready list behind or

+ *          ahead of all threads having the same priority depending on

+ *          if it used its whole time slice.

+ * @note    Not a user function, it is meant to be invoked by the scheduler

+ *          itself or from within the port layer.

+ *

+ * @special

+ */

+#if !defined(PORT_OPTIMIZED_DORESCHEDULE) || defined(__DOXYGEN__)

+void chSchDoReschedule(void) {

+

+#if CH_TIME_QUANTUM > 0

+  /* If CH_TIME_QUANTUM is enabled then there are two different scenarios to

+     handle on preemption: time quantum elapsed or not.*/

+  if (currp->p_preempt == 0) {

+    /* The thread consumed its time quantum so it is enqueued behind threads

+       with same priority level, however, it acquires a new time quantum.*/

+    chSchDoRescheduleBehind();

+  }

+  else {

+    /* The thread didn't consume all its time quantum so it is put ahead of

+       threads with equal priority and does not acquire a new time quantum.*/

+    chSchDoRescheduleAhead();

+  }

+#else /* !(CH_TIME_QUANTUM > 0) */

+  /* If the round-robin mechanism is disabled then the thread goes always

+     ahead of its peers.*/

+  chSchDoRescheduleAhead();

+#endif /* !(CH_TIME_QUANTUM > 0) */

+}

 #endif /* !defined(PORT_OPTIMIZED_DORESCHEDULE) */

 

 /** @} */

diff --git a/os/kernel/src/chsys.c b/os/kernel/src/chsys.c
index 41946cdaf..e433a8e42 100644
--- a/os/kernel/src/chsys.c
+++ b/os/kernel/src/chsys.c
@@ -129,9 +129,9 @@ void chSysTimerHandlerI(void) {
 

 #if CH_TIME_QUANTUM > 0

   /* Running thread has not used up quantum yet? */

-  if (rlist.r_preempt > 0)

+  if (currp->p_preempt > 0)

     /* Decrement remaining quantum.*/

-    rlist.r_preempt--;

+    currp->p_preempt--;

 #endif

 #if CH_DBG_THREADS_PROFILING

   currp->p_time++;

diff --git a/os/kernel/src/chthreads.c b/os/kernel/src/chthreads.c
index a73697eb4..eccf466d0 100644
--- a/os/kernel/src/chthreads.c
+++ b/os/kernel/src/chthreads.c
@@ -71,6 +71,9 @@ Thread *_thread_init(Thread *tp, tprio_t prio) {
   tp->p_prio = prio;

   tp->p_state = THD_STATE_SUSPENDED;

   tp->p_flags = THD_MEM_MODE_STATIC;

+#if CH_TIME_QUANTUM > 0

+  tp->p_preempt = CH_TIME_QUANTUM;

+#endif

 #if CH_USE_MUTEXES

   tp->p_realprio = prio;

   tp->p_mtxlist = NULL;