This is the mail archive of the ecos-patches@sourceware.org mailing list for the eCos project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Is timeslicing broken?


It seems that timeslicing of equal priority threads is broken
in the presence of any other higher priority threads that may
cause preemption.

I have modified the timeslice test to have an additional thread.
This thread is higher priority than the "worker" threads and
all it does is wake up at a modest frequency (every 2 ticks).
What this does is to preempt one of the worker threads before
it has a chance to run the timeslice timer down to zero.  When
the worker thread is resumed, the timeslice timer is reset and
the same worker thread continues running forever, never being
rescheduled and letting the other worker threads run.

Here's the output - first with the high priority thread stopped:

INFO:<Timeslice Test: Check timeslicing works>
 Thread        CPU  0        Total
      0           142          142
      1           142          142
 Total            284
Threads             2
INFO:<Timeslice Test: done>
INFO:<Timeslice Test: Check timeslicing works>
 Thread        CPU  0        Total
      0            96           96
      1            94           94
      2            94           94
 Total            284
Threads             3
INFO:<Timeslice Test: done>

Now, the output when the high priority thread runs:

INFO:<Timeslice Test: Check timeslicing works>
 Thread        CPU  0        Total
      0           285          285
      1             0            0
 Total            285
Threads             1
INFO:<Timeslice Test: done>
INFO:<Timeslice Test: Check timeslicing works>
 Thread        CPU  0        Total
      0           285          285
      1             0            0
      2             0            0
 Total            285
Threads             1
INFO:<Timeslice Test: done>

The modified test is attached, along with a patch that makes this
work the way I think it should.  n.b. the implementation may not
be the most elegant - I get lost in C++ :-(

--
------------------------------------------------------------
Gary Thomas                 |  Consulting for the
MLB Associates              |    Embedded world
------------------------------------------------------------
Index: kernel/current/ChangeLog
===================================================================
RCS file: /misc/cvsfiles/ecos/packages/kernel/current/ChangeLog,v
retrieving revision 1.139
diff -u -5 -p -r1.139 ChangeLog
--- kernel/current/ChangeLog	12 Oct 2006 15:41:49 -0000	1.139
+++ kernel/current/ChangeLog	7 Jan 2007 13:20:14 -0000
@@ -1,5 +1,17 @@
+2007-01-07  Gary Thomas  <gary@mlbassoc.com>
+
+	* include/thread.hxx: 	
+	* include/thread.inl: 
+	* include/mlqueue.hxx: 
+	* src/sched/mlqueue.cxx: 
+	* src/sched/sched.cxx: Change timeslice behaviour such that threads
+	have their own timeslice counter which is saved/restored when the
+	thread loses the CPU.  This keeps higher priority [preemption]
+	threads from causing starvation amongst a set of compute-bound
+	lower priority threads which depend on timeslicing to share the CPU.
+
 2006-10-12  Nick Garnett  <nickg@ecoscentric.com>
 
 	* cdl/synch.cdl: Added CYGIMP_MBOX_USE_MBOXT_PLAIN option. This is
 	tested in various places but was not actually defined. It now is
 	and defaults to 1 so that the plain version of mail boxes is
Index: kernel/current/include/mlqueue.hxx
===================================================================
RCS file: /misc/cvsfiles/ecos/packages/kernel/current/include/mlqueue.hxx,v
retrieving revision 1.12
diff -u -5 -p -r1.12 mlqueue.hxx
--- kernel/current/include/mlqueue.hxx	23 May 2002 23:06:48 -0000	1.12
+++ kernel/current/include/mlqueue.hxx	7 Jan 2007 13:16:03 -0000
@@ -211,10 +211,15 @@ protected:
     // Set need_reschedule if the supplied thread is of lower
     // priority than any that are currently running.
     static void set_need_reschedule( Cyg_Thread *thread );
     static void set_need_reschedule();
 
+#ifdef CYGSEM_KERNEL_SCHED_TIMESLICE
+    void save_timeslice_count(Cyg_Thread *thread);
+    void restore_timeslice_count(Cyg_Thread *thread);
+#endif
+
 public:
     void set_idle_thread( Cyg_Thread *thread, HAL_SMP_CPU_TYPE cpu );
     
 #ifdef CYGSEM_KERNEL_SCHED_TIMESLICE
 
Index: kernel/current/include/thread.hxx
===================================================================
RCS file: /misc/cvsfiles/ecos/packages/kernel/current/include/thread.hxx,v
retrieving revision 1.12
diff -u -5 -p -r1.12 thread.hxx
--- kernel/current/include/thread.hxx	28 Mar 2006 10:06:53 -0000	1.12
+++ kernel/current/include/thread.hxx	7 Jan 2007 13:16:03 -0000
@@ -248,10 +248,17 @@ private:
     CYG_ADDRWORD                wait_info;
     
     // Unique thread id assigned on creation
     cyg_uint16                  unique_id;
 
+#ifdef CYGSEM_KERNEL_SCHED_TIMESLICE
+    cyg_ucount32                timeslice_count;
+public:
+    static void set_timeslice_count(cyg_uint32 count);
+    static cyg_uint32 get_timeslice_count(void);
+#endif
+
 #ifdef CYGPKG_KERNEL_EXCEPTIONS
 
     // If exceptions are supported, define an exception control
     // object that will be used to manage and deliver them. If
     // exceptions are global there is a single static instance
Index: kernel/current/include/thread.inl
===================================================================
RCS file: /misc/cvsfiles/ecos/packages/kernel/current/include/thread.inl,v
retrieving revision 1.16
diff -u -5 -p -r1.16 thread.inl
--- kernel/current/include/thread.inl	15 Mar 2004 15:20:53 -0000	1.16
+++ kernel/current/include/thread.inl	7 Jan 2007 13:16:03 -0000
@@ -574,10 +574,22 @@ inline void Cyg_Thread::deregister_excep
         );
 }
 
 #endif
 
+#ifdef CYGSEM_KERNEL_SCHED_TIMESLICE
+inline void Cyg_Thread::set_timeslice_count(cyg_uint32 count)
+{
+    self()->timeslice_count = count;
+}
+
+inline cyg_uint32 Cyg_Thread::get_timeslice_count(void)
+{
+    return self()->timeslice_count;
+}
+#endif
+
 //==========================================================================
 // Inlines for Cyg_ThreadTimer class
 
 // -------------------------------------------------------------------------
 #if defined(CYGFUN_KERNEL_THREADS_TIMER) && defined(CYGVAR_KERNEL_COUNTERS_CLOCK)
Index: kernel/current/src/sched/mlqueue.cxx
===================================================================
RCS file: /misc/cvsfiles/ecos/packages/kernel/current/src/sched/mlqueue.cxx,v
retrieving revision 1.19
diff -u -5 -p -r1.19 mlqueue.cxx
--- kernel/current/src/sched/mlqueue.cxx	24 Sep 2004 16:57:12 -0000	1.19
+++ kernel/current/src/sched/mlqueue.cxx	7 Jan 2007 13:21:11 -0000
@@ -563,10 +563,19 @@ Cyg_Scheduler_Implementation::timeslice_
 __externC void cyg_scheduler_timeslice_cpu(void)
 {
     Cyg_Scheduler::scheduler.timeslice_cpu();
 }
 
+void Cyg_Scheduler_Implementation::save_timeslice_count(Cyg_Thread *thread)
+{
+    thread->set_timeslice_count(timeslice_count[CYG_KERNEL_CPU_THIS()]);
+}
+
+void Cyg_Scheduler_Implementation::restore_timeslice_count(Cyg_Thread *thread)
+{
+    timeslice_count[CYG_KERNEL_CPU_THIS()] = thread->get_timeslice_count();
+}
 #endif
 
 //==========================================================================
 // Cyg_SchedThread_Implementation class members
 
Index: kernel/current/src/sched/sched.cxx
===================================================================
RCS file: /misc/cvsfiles/ecos/packages/kernel/current/src/sched/sched.cxx,v
retrieving revision 1.18
diff -u -5 -p -r1.18 sched.cxx
--- kernel/current/src/sched/sched.cxx	19 Jan 2006 17:53:58 -0000	1.18
+++ kernel/current/src/sched/sched.cxx	7 Jan 2007 13:20:39 -0000
@@ -197,10 +197,17 @@ void Cyg_Scheduler::unlock_inner( cyg_uc
 
 #ifdef CYGFUN_KERNEL_THREADS_STACK_CHECKING
                 next->check_stack(); // before running it
 #endif
 
+#ifdef CYGSEM_KERNEL_SCHED_TIMESLICE
+                // Reset the timeslice counter so that this thread gets a full
+                // quantum. 
+                Cyg_Scheduler::scheduler.save_timeslice_count(current);
+                Cyg_Scheduler::scheduler.restore_timeslice_count(next);
+#endif
+
                 // Switch contexts
                 HAL_THREAD_SWITCH_CONTEXT( &current->stack_ptr,
                                            &next->stack_ptr );
 
                 // Worry here about possible compiler
@@ -221,16 +228,10 @@ void Cyg_Scheduler::unlock_inner( cyg_uc
                 CYG_ASSERTCLASS( current, "Bad current thread" );
 
                 current_thread[CYG_KERNEL_CPU_THIS()] = current;   // restore current thread pointer
             }
 
-#ifdef CYGSEM_KERNEL_SCHED_TIMESLICE
-            // Reset the timeslice counter so that this thread gets a full
-            // quantum. 
-            reset_timeslice_count();
-#endif
-
             clear_need_reschedule();    // finished rescheduling
         }
 
         if( new_lock == 0 )
         {
//==========================================================================
//
//        timeslice2.c
//
//        Timeslice test
//
//==========================================================================
//####ECOSGPLCOPYRIGHTBEGIN####
// -------------------------------------------
// This file is part of eCos, the Embedded Configurable Operating System.
// Copyright (C) 1998, 1999, 2000, 2001, 2002 Red Hat, Inc.
// Copyright (C) 2007, Gary Thomas
//
// eCos is free software; you can redistribute it and/or modify it under
// the terms of the GNU General Public License as published by the Free
// Software Foundation; either version 2 or (at your option) any later version.
//
// eCos is distributed in the hope that it will be useful, but WITHOUT ANY
// WARRANTY; without even the implied warranty of MERCHANTABILITY or
// FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
// for more details.
//
// You should have received a copy of the GNU General Public License along
// with eCos; if not, write to the Free Software Foundation, Inc.,
// 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA.
//
// As a special exception, if other files instantiate templates or use macros
// or inline functions from this file, or you compile this file and link it
// with other works to produce a work based on this file, this file does not
// by itself cause the resulting work to be covered by the GNU General Public
// License. However the source code for this file must still be made available
// in accordance with section (3) of the GNU General Public License.
//
// This exception does not invalidate any other reasons why a work based on
// this file might be covered by the GNU General Public License.
//
// Alternative licenses for eCos may be arranged by contacting Red Hat, Inc.
// at http://sources.redhat.com/ecos/ecos-license/
// -------------------------------------------
//####ECOSGPLCOPYRIGHTEND####
//==========================================================================
//#####DESCRIPTIONBEGIN####
//
// Author(s):     nickg, gthomas
// Contributors:  nickg
// Date:          2001-06-18
// Description:   A basic timeslicing test.
//
//####DESCRIPTIONEND####
//==========================================================================

#include <pkgconf/kernel.h>
#include <pkgconf/hal.h>

#include <cyg/hal/hal_arch.h>

#include <cyg/kernel/smp.hxx>

#include <cyg/kernel/kapi.h>

#include <cyg/infra/testcase.h>
#include <cyg/infra/diag.h>

//==========================================================================

#if defined(CYGSEM_KERNEL_SCHED_TIMESLICE) &&   \
    defined(CYGFUN_KERNEL_API_C) &&             \
    defined(CYGSEM_KERNEL_SCHED_MLQUEUE) &&     \
    defined(CYGVAR_KERNEL_COUNTERS_CLOCK) &&    \
    !defined(CYGDBG_INFRA_DIAG_USE_DEVICE) &&   \
    (CYGNUM_KERNEL_SCHED_PRIORITIES > 12)

//==========================================================================

#define STACK_SIZE CYGNUM_HAL_STACK_SIZE_TYPICAL

#define NTHREADS_MAX (CYGNUM_KERNEL_CPU_MAX*6)

static int ncpus = CYGNUM_KERNEL_CPU_MAX;

static char test_stack[STACK_SIZE];
static cyg_thread test_thread;
static cyg_handle_t main_thread;

static char timer_stack[STACK_SIZE];
static cyg_thread timer_thread;
static cyg_handle_t timer;

static char stacks[NTHREADS_MAX][STACK_SIZE];
static cyg_thread test_threads[NTHREADS_MAX];
static cyg_handle_t threads[NTHREADS_MAX];

static volatile int failed = false;

static volatile cyg_uint32 slicerun[NTHREADS_MAX][CYGNUM_KERNEL_CPU_MAX];

//==========================================================================

#define LONG_TIME 1000000
void 
test_thread_timeslice(CYG_ADDRESS id)
{
    volatile int i;

    for(;;) {
        // Simulate a very long computation
        for (i = 0;  i < LONG_TIME;  i++) ;
        slicerun[id][CYG_KERNEL_CPU_THIS()]++;
    }
}

// This thread runs at a priority higher than the worker threads
// We want to test that time slicing still works for those threads
// even if there are other prioritized threads causing some preemption

void
test_high_prio_thread(CYG_ADDRESS param)
{
    for (;;) {
        cyg_thread_delay(2);
    }
}

//==========================================================================

void run_test_timeslice(int nthread)
{
    int i,j;
    cyg_uint32 cpu_total[CYGNUM_KERNEL_CPU_MAX];
    cyg_uint32 cpu_threads[CYGNUM_KERNEL_CPU_MAX];
    cyg_uint32 thread_total[NTHREADS_MAX];

    CYG_TEST_INFO( "Timeslice Test: Check timeslicing works");
    
    // Init flags.
    for (i = 0;  i < nthread;  i++)
        for( j = 0; j < ncpus; j++ )
            slicerun[i][j] = 0;
    
    // Set my priority higher than any I plan to create
    cyg_thread_set_priority(cyg_thread_self(), 2);

    for (i = 0;  i < nthread;  i++) {
        cyg_thread_create(10,              // Priority - just a number
                          test_thread_timeslice, // entry
                          i,               // index
                          "test_thread",     // Name
                          &stacks[i][0],   // Stack
                          STACK_SIZE,      // Size
                          &threads[i],     // Handle
                          &test_threads[i] // Thread data structure
            );
        cyg_thread_resume( threads[i]);
    }

    // Just wait a while, until the threads have all run for a bit.
    cyg_thread_delay( CYGNUM_KERNEL_SCHED_TIMESLICE_TICKS*100 );

    // Suspend all the threads
    for (i = 0;  i < nthread;  i++) {
        cyg_thread_suspend(threads[i]);
    }

    
    // And check that a thread ran on each CPU, and that each thread
    // ran.
    
    
    diag_printf(" Thread ");
    for( j = 0; j < ncpus; j++ )
    {
        cpu_total[j] = 0;
        cpu_threads[j] = 0;
        // "  %11d"  __123456789ab"
        diag_printf("       CPU %2d",j);
    }
    // "  %11d"  __123456789ab"
    diag_printf("        Total\n");
    for (i = 0;  i < nthread;  i++)
    {
        thread_total[i] = 0;
        diag_printf("     %2d ",i);
        for( j = 0; j < ncpus; j++ )
        {
            thread_total[i] += slicerun[i][j];
            cpu_total[j] += slicerun[i][j];
            if( slicerun[i][j] > 0 )
                cpu_threads[j]++;
            diag_printf("  %11d",slicerun[i][j]);
        }
        diag_printf("  %11d\n",thread_total[i]);
        if( thread_total[i] == 0 )
            failed++;
    }
    
    diag_printf(" Total  ");
    for( j = 0; j < ncpus; j++ )
        diag_printf("  %11d",cpu_total[j]);
    diag_printf("\n");
    diag_printf("Threads ");
    for( j = 0; j < ncpus; j++ )
    {
        diag_printf("  %11d",cpu_threads[j]);
        if( cpu_threads[j] < 2 )
            failed++;
    }
    diag_printf("\n");

    // Delete all the threads
    for (i = 0;  i < nthread;  i++) {
        cyg_thread_delete(threads[i]);
    }

    CYG_TEST_INFO( "Timeslice Test: done");
}


//==========================================================================

void 
run_tests(CYG_ADDRESS id)
{
    int step;
    int nthread;
    
    // Try to run about 10 times in total, with varying numbers of threads
    // from only one extra up to the full set:

    step = (NTHREADS_MAX - (1 + CYG_KERNEL_CPU_COUNT()))/10;
    if( step == 0 ) step = 1;
    
    for( nthread = 1 + CYG_KERNEL_CPU_COUNT() ;
         nthread <= NTHREADS_MAX ;
         nthread += step )
            run_test_timeslice(nthread);

    if( failed )
        CYG_TEST_FAIL_FINISH("Timeslice test failed\n");
    
    CYG_TEST_PASS_FINISH("Timeslice test OK");    
}

//==========================================================================

void timeslice_main( void )
{
    CYG_TEST_INIT();

    // Work out how many CPUs we actually have.
    ncpus = CYG_KERNEL_CPU_COUNT();

    cyg_thread_create(0,              // Priority - just a number
                      run_tests,      // entry
                      0,              // index
                      "run_tests",    // Name
                      test_stack,     // Stack
                      STACK_SIZE,     // Size
                      &main_thread,   // Handle
                      &test_thread    // Thread data structure
        );
    cyg_thread_resume( main_thread);

    cyg_thread_create(1,              // Priority - just a number
                      test_high_prio_thread,      // entry
                      0,              // index
                      "timer",        // Name
                      timer_stack,    // Stack
                      STACK_SIZE,     // Size
                      &timer,         // Handle
                      &timer_thread   // Thread data structure
        );
    cyg_thread_resume(timer);
    
    cyg_scheduler_start();
}

//==========================================================================

#ifdef CYGSEM_HAL_STOP_CONSTRUCTORS_ON_FLAG
externC void
cyg_hal_invoke_constructors();
#endif

externC void
cyg_start( void )
{
#ifdef CYGSEM_HAL_STOP_CONSTRUCTORS_ON_FLAG
    cyg_hal_invoke_constructors();
#endif
    timeslice_main();
}   

//==========================================================================

#else // CYGSEM_KERNEL_SCHED_TIMESLICE etc

externC void
cyg_start( void )
{
    CYG_TEST_INIT();
    CYG_TEST_INFO("SMP test requires:\n"
                "CYGSEM_KERNEL_SCHED_TIMESLICE &&\n"
                "CYGPKG_KERNEL_SMP_SUPPORT &&\n"
                "CYGFUN_KERNEL_API_C && \n"
                "CYGSEM_KERNEL_SCHED_MLQUEUE &&\n"
                "CYGVAR_KERNEL_COUNTERS_CLOCK &&\n"
                "!CYGPKG_HAL_I386_LINUX &&\n"
                "!CYGDBG_INFRA_DIAG_USE_DEVICE &&\n"
                "(CYGNUM_KERNEL_SCHED_PRIORITIES > 12)\n");
    CYG_TEST_NA("SMP test requirements");
}

#endif // CYGSEM_KERNEL_SCHED_TIMESLICE etc.

//==========================================================================
// EOF timeslice.c

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]