From 4401d0e7b2874074e37c90e0178667a854d0da1f Mon Sep 17 00:00:00 2001 From: gdisirio Date: Mon, 6 Feb 2012 19:45:47 +0000 Subject: Round robin scheduling improvements. git-svn-id: svn://svn.code.sf.net/p/chibios/svn/trunk@3930 35acf78f-673a-0410-8e92-d51de3d6d3f4 --- os/kernel/include/chschd.h | 19 +++++---- os/kernel/include/chthreads.h | 6 +++ os/kernel/src/chschd.c | 95 ++++++++++++++++++++++++++++++++++++------- os/kernel/src/chsys.c | 4 +- os/kernel/src/chthreads.c | 3 ++ 5 files changed, 102 insertions(+), 25 deletions(-) (limited to 'os/kernel') 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 @@ -121,6 +121,12 @@ struct Thread { * @brief References to this 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__) /** 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; -- cgit v1.2.3