This is the mail archive of the ecos-discuss@sources.redhat.com 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]

Re: Max number of priorities using mlqueue scheduler


[Originally sent with the patch as an attachment, forgetting that this
list doesn't like them. Reposted in case anyone else is interested.]

Nick Garnett <nickg at ecoscentric dot com> writes:

> What's needed is to add a two-level bitmap. This is something I
> started working on some time ago, but other commitments meant that it
> was sidelined. Also, this is a fundamental change to the eCos
> scheduler. It's something I would only be happy checking in to an
> experimental branch for prolonged testing. Putting it straight into
> the CVS repository is a big risk.
> 

Daniel,

If you are interested in living on the edge, I have dusted off the
two-level bitmap stuff I mentioned. I have only tested it on a few of the
more thread-intensive kernel tests, and only with 32 and 1024 priority
levels. No guarantees.

The attached patch is against the current CVS sources and needs some
more work before it could be checked in.


Index: kernel/current/cdl/scheduler.cdl
===================================================================
RCS file: /cvs/ecos/ecos/packages/kernel/current/cdl/scheduler.cdl,v
retrieving revision 1.8
diff -u -5 -r1.8 scheduler.cdl
--- kernel/current/cdl/scheduler.cdl	24 Feb 2003 14:06:55 -0000	1.8
+++ kernel/current/cdl/scheduler.cdl	21 Mar 2003 18:39:28 -0000
@@ -130,11 +130,11 @@
 # NOTE: This option only makes sense if the current scheduler
 #       supports multiple priority levels.
 cdl_component CYGNUM_KERNEL_SCHED_PRIORITIES {
     display       "Number of priority levels"
     flavor        data
-    legal_values  1 to 32
+    legal_values  1 to 1024
     default_value 32
     #active_if     CYGINT_KERNEL_SCHED_PRIORITY_SCHEDULER
     description "
         This option controls the number of priority levels that are
         available. For some types of scheduler including the bitmap
Index: kernel/current/include/kapidata.h
===================================================================
RCS file: /cvs/ecos/ecos/packages/kernel/current/include/kapidata.h,v
retrieving revision 1.13
diff -u -5 -r1.13 kapidata.h
--- kernel/current/include/kapidata.h	27 Feb 2003 06:14:32 -0000	1.13
+++ kernel/current/include/kapidata.h	21 Mar 2003 18:39:29 -0000
@@ -106,15 +106,31 @@
 #elif CYGNUM_KERNEL_SCHED_BITMAP_SIZE <= 16
 typedef cyg_ucount16 cyg_sched_bitmap;
 #elif CYGNUM_KERNEL_SCHED_BITMAP_SIZE <= 32
 typedef cyg_ucount32 cyg_sched_bitmap;
 #elif CYGNUM_KERNEL_SCHED_BITMAP_SIZE <= 64
-typedef cyg_ucount64 cyg_sched_bitmap;
+typedef cyg_ucount8 cyg_sched_bitmap;
+#define CYGIMP_KERNEL_SCHED_TWO_LEVEL_BITMAP
+#define CYGNUM_KERNEL_SCHED_BITMAP2_SIZE 	8
+#define CYGNUM_KERNEL_SCHED_BITMAP2_SHIFT	3
+#define CYGNUM_KERNEL_SCHED_BITMAP2_MASK	0x07
+#elif CYGNUM_KERNEL_SCHED_BITMAP_SIZE <= 256
+typedef cyg_ucount16 cyg_sched_bitmap;
+#define CYGIMP_KERNEL_SCHED_TWO_LEVEL_BITMAP
+#define CYGNUM_KERNEL_SCHED_BITMAP2_SIZE 	16
+#define CYGNUM_KERNEL_SCHED_BITMAP2_SHIFT	4
+#define CYGNUM_KERNEL_SCHED_BITMAP2_MASK	0x0F
+#elif CYGNUM_KERNEL_SCHED_BITMAP_SIZE <= 1024
+typedef cyg_ucount32 cyg_sched_bitmap;
+#define CYGIMP_KERNEL_SCHED_TWO_LEVEL_BITMAP
+#define CYGNUM_KERNEL_SCHED_BITMAP2_SIZE 	32
+#define CYGNUM_KERNEL_SCHED_BITMAP2_SHIFT	5
+#define CYGNUM_KERNEL_SCHED_BITMAP2_MASK	0x1F
 #else
-#error Bitmaps greater than 64 bits not currently allowed
+#error Bitmaps greater than 1024 bits not currently allowed
 #endif
-
+    
 typedef struct 
 {
 #if defined(CYGSEM_KERNEL_SCHED_BITMAP)
 
     cyg_sched_bitmap map;
Index: kernel/current/include/mlqueue.hxx
===================================================================
RCS file: /cvs/ecos/ecos/packages/kernel/current/include/mlqueue.hxx,v
retrieving revision 1.12
diff -u -5 -r1.12 mlqueue.hxx
--- kernel/current/include/mlqueue.hxx	23 May 2002 23:06:48 -0000	1.12
+++ kernel/current/include/mlqueue.hxx	21 Mar 2003 18:39:29 -0000
@@ -83,12 +83,30 @@
 typedef cyg_ucount8 cyg_sched_bitmap;
 #elif CYGNUM_KERNEL_SCHED_BITMAP_SIZE <= 16
 typedef cyg_ucount16 cyg_sched_bitmap;
 #elif CYGNUM_KERNEL_SCHED_BITMAP_SIZE <= 32
 typedef cyg_ucount32 cyg_sched_bitmap;
+#elif CYGNUM_KERNEL_SCHED_BITMAP_SIZE <= 64
+typedef cyg_ucount8 cyg_sched_bitmap;
+#define CYGIMP_KERNEL_SCHED_TWO_LEVEL_BITMAP
+#define CYGNUM_KERNEL_SCHED_BITMAP2_SIZE 	8
+#define CYGNUM_KERNEL_SCHED_BITMAP2_SHIFT	3
+#define CYGNUM_KERNEL_SCHED_BITMAP2_MASK	0x07
+#elif CYGNUM_KERNEL_SCHED_BITMAP_SIZE <= 256
+typedef cyg_ucount16 cyg_sched_bitmap;
+#define CYGIMP_KERNEL_SCHED_TWO_LEVEL_BITMAP
+#define CYGNUM_KERNEL_SCHED_BITMAP2_SIZE 	16
+#define CYGNUM_KERNEL_SCHED_BITMAP2_SHIFT	4
+#define CYGNUM_KERNEL_SCHED_BITMAP2_MASK	0x0F
+#elif CYGNUM_KERNEL_SCHED_BITMAP_SIZE <= 1024
+typedef cyg_ucount32 cyg_sched_bitmap;
+#define CYGIMP_KERNEL_SCHED_TWO_LEVEL_BITMAP
+#define CYGNUM_KERNEL_SCHED_BITMAP2_SIZE 	32
+#define CYGNUM_KERNEL_SCHED_BITMAP2_SHIFT	5
+#define CYGNUM_KERNEL_SCHED_BITMAP2_MASK	0x1F
 #else
-#error Bitmaps greater than 32 bits not currently allowed
+#error Bitmaps greater than 1024 bits not currently allowed
 #endif
 
 // -------------------------------------------------------------------------
 // Customize the scheduler
 
@@ -104,10 +122,36 @@
 // scheduler Run queue object
 
 typedef Cyg_CList_T<Cyg_Thread> Cyg_RunQueue;
 
 // -------------------------------------------------------------------------
+// Priority map object
+
+class Cyg_Priority_Map
+{
+    cyg_sched_bitmap	map;
+
+#ifdef CYGIMP_KERNEL_SCHED_TWO_LEVEL_BITMAP
+    cyg_sched_bitmap    map_2[CYGNUM_KERNEL_SCHED_BITMAP2_SIZE];
+#endif
+
+public:
+
+    Cyg_Priority_Map();
+
+    cyg_bool empty();
+    
+    void set_map_bit( cyg_priority bit );
+    
+    void clear_map_bit( cyg_priority bit );
+    
+    cyg_priority get_map_bit( cyg_priority bit );
+    
+    cyg_priority get_map_lsb();
+};
+
+// -------------------------------------------------------------------------
 // Thread queue implementation.
 // This class provides the (scheduler specific) implementation of the
 // thread queue class.
 
 class Cyg_ThreadQueue_Implementation
@@ -150,11 +194,11 @@
     friend class Cyg_SchedThread_Implementation;
     friend class Cyg_HardwareThread;
     friend void cyg_scheduler_set_need_reschedule();
     
     // Mask of which run queues have ready threads
-    cyg_sched_bitmap    queue_map;
+    Cyg_Priority_Map   queue_map;
 
     // Each run queue is a double linked circular list of threads.
     // These pointers point to the head element of each list.
     Cyg_RunQueue run_queue[CYGNUM_KERNEL_SCHED_PRIORITIES];
 
@@ -163,11 +207,11 @@
     // In SMP systems we additionally keep a counter for each priority
     // of the number of pending but not running threads in each queue.
     
     cyg_uint32 pending[CYGNUM_KERNEL_SCHED_PRIORITIES];
 
-    cyg_sched_bitmap pending_map;
+    Cyg_Priority_Map 	pending_map;
 
 #endif    
 
 protected:
     
Index: kernel/current/src/sched/mlqueue.cxx
===================================================================
RCS file: /cvs/ecos/ecos/packages/kernel/current/src/sched/mlqueue.cxx,v
retrieving revision 1.18
diff -u -5 -r1.18 mlqueue.cxx
--- kernel/current/src/sched/mlqueue.cxx	23 May 2002 23:06:54 -0000	1.18
+++ kernel/current/src/sched/mlqueue.cxx	21 Mar 2003 18:39:32 -0000
@@ -80,18 +80,100 @@
 
 //==========================================================================
 // Cyg_Scheduler_Implementation class members
 
 // -------------------------------------------------------------------------
+// Queue map manipulation routines
+
+#define mlq_inline
+
+mlq_inline Cyg_Priority_Map::Cyg_Priority_Map()
+{
+    map   = 0;
+
+#ifdef CYGIMP_KERNEL_SCHED_TWO_LEVEL_BITMAP
+    for( int i = 0; i < CYGNUM_KERNEL_SCHED_BITMAP2_SIZE; i++ )
+	map_2[i] = 0;
+#endif
+}
+
+mlq_inline cyg_bool Cyg_Priority_Map::empty()
+{
+    return map == 0;
+}
+
+mlq_inline void Cyg_Priority_Map::set_map_bit( cyg_priority bit )
+{
+#ifndef CYGIMP_KERNEL_SCHED_TWO_LEVEL_BITMAP
+
+    map |= (1<<bit);
+    
+#else
+
+    register cyg_priority map2_index = bit >> CYGNUM_KERNEL_SCHED_BITMAP2_SHIFT;
+    map_2[map2_index] |= 1 << (bit & CYGNUM_KERNEL_SCHED_BITMAP2_MASK);
+    map |= (1 << map2_index);
+    
+#endif
+}
+
+mlq_inline void Cyg_Priority_Map::clear_map_bit( cyg_priority bit )
+{
+#ifndef CYGIMP_KERNEL_SCHED_TWO_LEVEL_BITMAP
+
+    map &= ~(1<<bit);
+    
+#else
+
+    register cyg_priority map2_index = bit >> CYGNUM_KERNEL_SCHED_BITMAP2_SHIFT;
+    map_2[map2_index] &= ~(1 << (bit & CYGNUM_KERNEL_SCHED_BITMAP2_MASK));
+    if( map_2[map2_index] == 0 )
+	map &= ~(1 << map2_index);
+    
+#endif
+}
+
+mlq_inline cyg_priority Cyg_Priority_Map::get_map_lsb()
+{
+    cyg_priority index;
+#ifndef CYGIMP_KERNEL_SCHED_TWO_LEVEL_BITMAP
+
+    HAL_LSBIT_INDEX( index, map );
+    return index;
+    
+#else
+
+    register cyg_priority map2_index;
+    HAL_LSBIT_INDEX( map2_index, map );
+    HAL_LSBIT_INDEX( index, map_2[map2_index] );
+    return map2_index<<CYGNUM_KERNEL_SCHED_BITMAP2_SHIFT | index;
+    
+#endif
+}
+
+mlq_inline cyg_priority Cyg_Priority_Map::get_map_bit( cyg_priority bit )
+{
+#ifndef CYGIMP_KERNEL_SCHED_TWO_LEVEL_BITMAP
+
+    return (map & (1<<bit)) != 0;
+    
+#else
+
+    register cyg_priority map2_index = bit >> CYGNUM_KERNEL_SCHED_BITMAP2_SHIFT;
+    return (map_2[map2_index] & (1 << (bit & CYGNUM_KERNEL_SCHED_BITMAP2_MASK))) != 0;
+    
+#endif
+    
+}
+
+// -------------------------------------------------------------------------
 // Constructor.
 
 Cyg_Scheduler_Implementation::Cyg_Scheduler_Implementation()
 {
     CYG_REPORT_FUNCTION();
         
-    queue_map   = 0;
-
 #ifdef CYGPKG_KERNEL_SMP_SUPPORT
 
     pending_map = 0;
     
     for( int i = 0; i < CYGNUM_KERNEL_SCHED_PRIORITIES; i++ )
@@ -119,12 +201,12 @@
     CYG_REPORT_FUNCTYPE("returning thread %08x");
 
     // The run queue may _never_ be empty, there is always
     // an idle thread at the lowest priority.
 
-    CYG_ASSERT( queue_map != 0, "Run queue empty");
-    CYG_ASSERT( queue_map & (1<<CYG_THREAD_MIN_PRIORITY), "Idle thread vanished!!!");
+    CYG_ASSERT( !queue_map.empty(), "Run queue empty");
+    CYG_ASSERT( queue_map.get_map_bit(CYG_THREAD_MIN_PRIORITY), "Idle thread vanished!!!");
     CYG_ASSERT( !run_queue[CYG_THREAD_MIN_PRIORITY].empty(), "Idle thread vanished!!!");
 
 #ifdef CYGPKG_KERNEL_SMP_SUPPORT
 
     Cyg_Thread *current = get_current_thread();
@@ -137,21 +219,23 @@
     // for execution.
     if( current->get_state() == Cyg_Thread::RUNNING )
     {
         current->cpu = CYG_KERNEL_CPU_NONE;
         pending[current->priority]++;
-        pending_map |= (1<<current->priority);
+	pending_map.set_map_bit(current->priority);
+//        pending_map |= (1<<current->priority);
     }
     else
     {
         // Otherwise, ensure that the thread is no longer marked as
         // running.
         current->cpu = CYG_KERNEL_CPU_NONE;        
     }
 
     
-    HAL_LSBIT_INDEX(index, pending_map);
+    index = pending_map.get_map_lsb();
+//    HAL_LSBIT_INDEX(index, pending_map);
 
     Cyg_RunQueue *queue = &run_queue[index];
     
     CYG_ASSERT( !queue->empty(), "Queue for index empty");
     CYG_ASSERT( pending[index] > 0, "Pending array and map disagree");
@@ -166,17 +250,19 @@
         thread = thread->get_next();
 
     // Take newly scheduled thread out of pending map
     thread->cpu = CYG_KERNEL_CPU_THIS();
     if( --pending[index] == 0 )
-        pending_map &= ~(1<<index);
+	pending_map.clear_map_bit(index);
+//        pending_map &= ~(1<<index);
     
 #else    
 
     register cyg_uint32 index;
 
-    HAL_LSBIT_INDEX(index, queue_map);
+    index = queue_map.get_map_lsb();
+//    HAL_LSBIT_INDEX(index, queue_map);
 
     Cyg_RunQueue *queue = &run_queue[index];
     
     CYG_ASSERT( !queue->empty(), "Queue for index empty");
 
@@ -209,12 +295,13 @@
     
     CYG_ASSERT((CYG_THREAD_MIN_PRIORITY >= pri) 
                && (CYG_THREAD_MAX_PRIORITY <= pri),
                "Priority out of range!");
 
-    CYG_ASSERT( ((queue_map & (1<<pri))!=0) == ((!run_queue[pri].empty())!=0), "Map and queue disagree");
-
+    CYG_ASSERT( queue_map.get_map_bit(pri) == ((!run_queue[pri].empty())!=0), "Map and queue disagree");    
+//    CYG_ASSERT( ((queue_map & (1<<pri))!=0) == ((!run_queue[pri].empty())!=0), "Map and queue disagree");
+    
     // If the thread is on some other queue, remove it
     // here.
     if( thread->queue != NULL )
     {
         thread->queue->remove(thread);
@@ -223,11 +310,12 @@
     if( queue->empty() )
     {
         // set the map bit and ask for a reschedule if this is a
         // new highest priority thread.
       
-        queue_map |= (1<<pri);
+	queue_map.set_map_bit(pri);
+//        queue_map |= (1<<pri);
 
     }
     // else the queue already has an occupant, queue behind him
 
     queue->add_tail(thread);
@@ -244,22 +332,23 @@
     // pending map.
 
     if( thread->cpu == CYG_KERNEL_CPU_NONE )
     {
         if( pending[pri]++ == 0 )
-            pending_map |= (1<<pri);
+	    pending_map.set_map_bit(pri);
+//            pending_map |= (1<<pri);
     }
     // Otherwise the pending count will be dealt with in schedule().
     
 #endif    
-    
+
     CYG_ASSERT( thread->queue == NULL , "Runnable thread on a queue!");
-    CYG_ASSERT( queue_map != 0, "Run queue empty");
-    CYG_ASSERT( queue_map & (1<<pri), "Queue map bit not set for pri");
+    CYG_ASSERT( !queue_map.empty(), "Run queue empty");
+    CYG_ASSERT( queue_map.get_map_bit(pri), "Queue map bit not set for pri");
     CYG_ASSERT( !run_queue[pri].empty(), "Queue for pri empty");
-    CYG_ASSERT( ((queue_map & (1<<pri))!=0) == ((!run_queue[pri].empty())!=0), "Map and queue disagree");    
-    CYG_ASSERT( queue_map & (1<<CYG_THREAD_MIN_PRIORITY), "Idle thread vanished!!!");
+    CYG_ASSERT( queue_map.get_map_bit(pri) == ((!run_queue[pri].empty())!=0), "Map and queue disagree");    
+    CYG_ASSERT( queue_map.get_map_bit(CYG_THREAD_MIN_PRIORITY), "Idle thread vanished!!!");
     CYG_ASSERT( !run_queue[CYG_THREAD_MIN_PRIORITY].empty(), "Idle thread vanished!!!");
     
     CYG_REPORT_RETURN();
 }
 
@@ -269,11 +358,11 @@
 Cyg_Scheduler_Implementation::rem_thread(Cyg_Thread *thread)
 {
     CYG_REPORT_FUNCTION();
     CYG_REPORT_FUNCARG1("thread=%08x", thread);
         
-    CYG_ASSERT( queue_map != 0, "Run queue empty");
+    CYG_ASSERT( !queue_map.empty(), "Run queue empty");
 
     cyg_priority pri    = thread->priority;
     Cyg_RunQueue *queue = &run_queue[pri];
 
     CYG_INSTRUMENT_MLQ( REM, thread, pri);
@@ -287,11 +376,12 @@
     {
         // If the thread is not running, then we need to adjust the
         // pending count array and map if necessary.
 
         if( --pending[pri] == 0 )
-            pending_map &= ~(1<<pri);
+	    pending_map.clear_map_bit(pri);
+//            pending_map &= ~(1<<pri);
     }
     else
     {
         // If the target thread is currently running on a different
         // CPU, send a reschedule interrupt there to deschedule it.        
@@ -301,28 +391,29 @@
     // If the thread is current running on this CPU, then the pending
     // count will be dealt with in schedule().
     
 #endif
         
-    CYG_ASSERT( queue_map & (1<<pri), "Queue map bit not set for pri");
+//    CYG_ASSERT( queue_map & (1<<pri), "Queue map bit not set for pri");
     CYG_ASSERT( !run_queue[pri].empty(), "Queue for pri empty");
     
     // remove thread from queue
     queue->remove(thread);
 
     if( queue->empty() )
     {
         // If this was only thread in
         // queue, clear map.
       
-        queue_map &= ~(1<<pri);
+	queue_map.clear_map_bit(pri);
+//        queue_map &= ~(1<<pri);
     }
 
-    CYG_ASSERT( queue_map != 0, "Run queue empty");
-    CYG_ASSERT( queue_map & (1<<CYG_THREAD_MIN_PRIORITY), "Idle thread vanished!!!");
+//    CYG_ASSERT( queue_map != 0, "Run queue empty");
+//    CYG_ASSERT( queue_map & (1<<CYG_THREAD_MIN_PRIORITY), "Idle thread vanished!!!");
     CYG_ASSERT( !run_queue[CYG_THREAD_MIN_PRIORITY].empty(), "Idle thread vanished!!!");
-    CYG_ASSERT( ((queue_map & (1<<pri))!=0) == ((!run_queue[pri].empty())!=0), "Map and queue disagree");
+//    CYG_ASSERT( ((queue_map & (1<<pri))!=0) == ((!run_queue[pri].empty())!=0), "Map and queue disagree");
     
     CYG_REPORT_RETURN();
 }
 
 // -------------------------------------------------------------------------
@@ -404,11 +495,12 @@
     // In SMP, we need to take this thread out of the pending array
     // and map.
     
     cyg_priority pri    = thread->priority;
     if( --pending[pri] == 0 )
-        pending_map &= ~(1<<pri);
+	pending_map.clear_map_bit(pri);
+//        pending_map &= ~(1<<pri);
 #endif    
     
 }
 
 // -------------------------------------------------------------------------
@@ -498,12 +590,12 @@
 #endif
 
     Cyg_Thread *thread = get_current_thread();
     HAL_SMP_CPU_TYPE cpu_this = CYG_KERNEL_CPU_THIS();
     
-    CYG_ASSERT( queue_map != 0, "Run queue empty");
-    CYG_ASSERT( queue_map & (1<<CYG_THREAD_MIN_PRIORITY), "Idle thread vanished!!!");
+//    CYG_ASSERT( queue_map != 0, "Run queue empty");
+//    CYG_ASSERT( queue_map & (1<<CYG_THREAD_MIN_PRIORITY), "Idle thread vanished!!!");
 
 #ifdef CYGSEM_KERNEL_SCHED_TIMESLICE_ENABLE
     if( thread->timeslice_enabled &&
         timeslice_count[cpu_this] == 0 )
 #else    
@@ -549,11 +641,11 @@
             timeslice_count[cpu_this] = CYGNUM_KERNEL_SCHED_TIMESLICE_TICKS;
         }
     }
 
     
-    CYG_ASSERT( queue_map & (1<<CYG_THREAD_MIN_PRIORITY), "Idle thread vanished!!!");
+//    CYG_ASSERT( queue_map & (1<<CYG_THREAD_MIN_PRIORITY), "Idle thread vanished!!!");
     CYG_ASSERT( !run_queue[CYG_THREAD_MIN_PRIORITY].empty(), "Idle thread vanished!!!");
 #ifdef CYGDBG_KERNEL_TRACE_TIMESLICE
     CYG_REPORT_RETURN();
 #endif
 }


-- 
Nick Garnett                    eCos Kernel Architect
http://www.ecoscentric.com/     The eCos and RedBoot experts


-- 
Before posting, please read the FAQ: http://sources.redhat.com/fom/ecos
and search the list archive: http://sources.redhat.com/ml/ecos-discuss


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