ecos: packages/kernel/current/src/sched/lottery.cxx comparison

comparison packages/kernel/current/src/sched/lottery.cxx @ 0:3111d98ba7b3 ecos-v1_1-release

Initial commit of eCos version 1.1

author	jlarmour
date	Tue, 11 May 1999 11:16:07 +0000
parents
children	443894e2e912

comparison

equal deleted inserted replaced

--1:000000000000
+:3111d98ba7b3
+//==========================================================================
+//
+//	sched/lottery.cxx
+//
+//	Lottery scheduler class implementation
+//
+//==========================================================================
+//####COPYRIGHTBEGIN####
+//
+// -------------------------------------------
+// The contents of this file are subject to the Cygnus eCos Public License
+// Version 1.0 (the "License"); you may not use this file except in
+// compliance with the License.  You may obtain a copy of the License at
+// http://sourceware.cygnus.com/ecos
+//
+// Software distributed under the License is distributed on an "AS IS"
+// basis, WITHOUT WARRANTY OF ANY KIND, either express or implied.  See the
+// License for the specific language governing rights and limitations under
+// the License.
+//
+// The Original Code is eCos - Embedded Cygnus Operating System, released
+// September 30, 1998.
+//
+// The Initial Developer of the Original Code is Cygnus.  Portions created
+// by Cygnus are Copyright (C) 1998 Cygnus Solutions.  All Rights Reserved.
+// -------------------------------------------
+//
+//####COPYRIGHTEND####
+//==========================================================================
+//#####DESCRIPTIONBEGIN####
+//
+// Author(s): 	nickg
+// Contributors:	nickg
+// Date:	1997-09-16
+// Purpose:	Lottery scheduler class implementation
+// Description:	This file contains the implementations of
+//              Cyg_Scheduler_Implementation and
+//              Cyg_SchedThread_Implementation.
+//
+//
+//####DESCRIPTIONEND####
+//
+//==========================================================================
+#include <pkgconf/kernel.h>
+#include <cyg/kernel/ktypes.h>         // base kernel types
+#include <cyg/infra/cyg_trac.h>        // tracing macros
+#include <cyg/infra/cyg_ass.h>         // assertion macros
+#include <cyg/kernel/sched.hxx>        // our header
+#include <cyg/kernel/intr.hxx>         // interrupt defines, for Cyg_HAL_Clock
+#include <cyg/hal/hal_arch.h>          // Architecture specific definitions
+#include <cyg/kernel/thread.inl>       // thread inlines
+#include <cyg/kernel/sched.inl>        // scheduler inlines
+#ifdef CYGSEM_KERNEL_SCHED_LOTTERY
+#define CYG_ENABLE_TRACE 1
+//==========================================================================
+// Cyg_Scheduler_Implementation class static members
+#ifdef CYGSEM_KERNEL_SCHED_TIMESLICE
+cyg_count32 Cyg_Scheduler_Implementation::timeslice_count =
+CYGNUM_KERNEL_SCHED_TIMESLICE_TICKS;
+#endif
+//==========================================================================
+// Cyg_Scheduler_Implementation class members
+// -------------------------------------------------------------------------
+// Constructor.
+Cyg_Scheduler_Implementation::Cyg_Scheduler_Implementation()
+{
+CYG_REPORT_FUNCTION();
+total_tickets = 0;
+rand_seed = 1;
+}
+// -------------------------------------------------------------------------
+// Choose the best thread to run next
+Cyg_Thread *Cyg_Scheduler_Implementation::schedule()
+{
+CYG_REPORT_FUNCTION();
+#ifdef CYG_HAL_POWERPC
+// PowerPc specific version of random number generator.
+register cyg_int32 r1 asm("r4");
+r1 = rand_seed;
+asm(
+"li     7,0;"
+"ori    7,7,33614;"
+"mulhwu 5,7,%0;"
+"mullw  6,7,%0;"
+"srawi  6,6,1;"
+"add    %0,5,6;"
+"cmpwi  %0,0;"
+"bge    1f;"
+"slwi   %0,%0,1;"
+"srwi   %0,%0,1;"
+"addi   %0,%0,1;"
+"1:;"
+: "=r"(r1)
+: "0"(r1)
+: "r5", "r6", "r7"
+);
+rand_seed = r1;
+#else
+#if 1
+rand_seed = (rand_seed * 1103515245) + 1234;
+cyg_int32 r1 = rand_seed & 0x7FFFFFFF;
+#else
+// Generic implementation of RNG.
+#if( CYG_BYTEORDER == CYG_MSBFIRST )
+#define _LO 1
+#define _HI 0
+#else
+#define _LO 0
+#define _HI 1
+#endif
+union { cyg_int64 r64; cyg_int32 r32[2]; } u;
+u.r64 = (cyg_int64)rand_seed * 33614LL;
+cyg_int32 r1 = u.r32[_HI] + (u.r32[_LO]>>1);
+if( r1 < 0 )
+r1 = (r1 & 0x7FFFFFFF) + 1;
+rand_seed = r1;
+#undef _LO
+#undef _HI
+#endif
+#endif
+cyg_int32 ticket = r1 % total_tickets;
+cyg_int32 tick = ticket;
+Cyg_Thread *thread = run_queue.highpri();
+// Search the run queue for the thread with the
+// given ticket.
+while( ticket > 0 )
+{
+ticket -= thread->priority;
+if( ticket <= 0 ) break;
+thread = thread->next;
+CYG_ASSERT( thread != run_queue.highpri(), "Looping in scheduler");
+}
+CYG_TRACE3( CYG_ENABLE_TRACE,
+	"seed %08x ticket %d thread %08x",
+rand_seed, tick, thread);
+// If the thread has any compensation tickets, take them away since
+// it has just won.
+if( thread->compensation_tickets > 0 )
+{
+thread->priority -= thread->compensation_tickets;
+total_tickets -= thread->compensation_tickets;
+thread->compensation_tickets = 0;
+}
+// Re-insert thread at head of list. This reduces runtime by
+// putting the large ticket holders at the front of the list.
+//    run_queue.remove(thread);
+//    run_queue.enqueue(thread);
+CYG_CHECK_DATA_PTR( thread, "Invalid next thread pointer");
+CYG_ASSERTCLASS( thread, "Bad next thread" );
+return thread;
+}
+// -------------------------------------------------------------------------
+void Cyg_Scheduler_Implementation::add_thread(Cyg_Thread *thread)
+{
+CYG_REPORT_FUNCTION();
+// If the thread is on some other queue, remove it
+// here.
+if( thread->queue != NULL )
+{
+thread->queue->remove(thread);
+thread->queue = NULL;
+}
+total_tickets += thread->priority;
+run_queue.enqueue(thread);
+}
+// -------------------------------------------------------------------------
+void Cyg_Scheduler_Implementation::rem_thread(Cyg_Thread *thread)
+{
+CYG_REPORT_FUNCTION();
+run_queue.remove(thread);
+total_tickets -= thread->priority;
+// Compensate the thread for the segment of the quantum that
+// it used. This makes it more likely to win the lottery next time
+// it is scheduled. We only do this for threads that have voluntarily
+// given up the CPU.
+//    if( thread->get_state() != Cyg_Thread::RUNNING )
+{
+#if 0
+cyg_uint32 hal_ticks;
+HAL_CLOCK_READ( &hal_ticks );
+thread->compensation_tickets = thread->priority *
+CYGNUM_KERNEL_COUNTERS_RTC_PERIOD / hal_ticks;
+#else
+thread->compensation_tickets = (thread->priority *
+CYGNUM_KERNEL_SCHED_TIMESLICE_TICKS) / timeslice_count;
+#endif
+thread->priority += thread->compensation_tickets;
+}
+}
+// -------------------------------------------------------------------------
+// register thread with scheduler
+void Cyg_Scheduler_Implementation::register_thread(Cyg_Thread *thread)
+{
+CYG_REPORT_FUNCTION();
+// No registration necessary in this scheduler
+}
+// -------------------------------------------------------------------------
+// deregister thread
+void Cyg_Scheduler_Implementation::deregister_thread(Cyg_Thread *thread)
+{
+CYG_REPORT_FUNCTION();
+// No registration necessary in this scheduler
+}
+// -------------------------------------------------------------------------
+// Test the given priority for uniqueness
+cyg_bool Cyg_Scheduler_Implementation::unique( cyg_priority priority)
+{
+CYG_REPORT_FUNCTION();
+// Priorities are not unique
+return true;
+}
+//==========================================================================
+// Support for timeslicing option
+#ifdef CYGSEM_KERNEL_SCHED_TIMESLICE
+void Cyg_Scheduler_Implementation::timeslice()
+{
+CYG_REPORT_FUNCTION();
+if( --timeslice_count <= 0 )
+{
+CYG_INSTRUMENT_SCHED(TIMESLICE,0,0);
+// Force a reschedule on each timeslice
+need_reschedule = true;
+timeslice_count = CYGNUM_KERNEL_SCHED_TIMESLICE_TICKS;
+}
+}
+#endif
+//==========================================================================
+// Cyg_Cyg_SchedThread_Implementation class members
+Cyg_SchedThread_Implementation::Cyg_SchedThread_Implementation
+(
+CYG_ADDRWORD sched_info
+)
+{
+CYG_REPORT_FUNCTION();
+priority = cyg_priority(sched_info);
+// point the next and prev field at this thread.
+next = prev = CYG_CLASSFROMBASE(Cyg_Thread,
+Cyg_SchedThread_Implementation,
+this);
+}
+// -------------------------------------------------------------------------
+// Insert thread in front of this
+void Cyg_SchedThread_Implementation::insert( Cyg_Thread *thread)
+{
+CYG_REPORT_FUNCTION();
+thread->next        = CYG_CLASSFROMBASE(Cyg_Thread,
+Cyg_SchedThread_Implementation,
+this);
+thread->prev        = prev;
+prev->next          = thread;
+prev                = thread;
+}
+// -------------------------------------------------------------------------
+// remove this from queue
+void Cyg_SchedThread_Implementation::remove()
+{
+CYG_REPORT_FUNCTION();
+next->prev          = prev;
+prev->next          = next;
+next = prev         = CYG_CLASSFROMBASE(Cyg_Thread,
+Cyg_SchedThread_Implementation,
+this);
+}
+// -------------------------------------------------------------------------
+// Yield the processor to another thread
+void Cyg_SchedThread_Implementation::yield()
+{
+CYG_REPORT_FUNCTION();
+}
+//==========================================================================
+// Cyg_ThreadQueue_Implementation class members
+void Cyg_ThreadQueue_Implementation::enqueue(Cyg_Thread *thread)
+{
+CYG_REPORT_FUNCTION();
+// Always put thread at head of queue
+if( queue == NULL ) queue = thread;
+else
+{
+queue->insert(thread);
+//        queue->next->insert(thread);
+//        queue = thread;
+}
+thread->queue = CYG_CLASSFROMBASE(Cyg_ThreadQueue,
+Cyg_ThreadQueue_Implementation,
+this);
+}
+// -------------------------------------------------------------------------
+Cyg_Thread *Cyg_ThreadQueue_Implementation::dequeue()
+{
+CYG_REPORT_FUNCTION();
+if( queue == NULL ) return NULL;
+Cyg_Thread *thread = queue;
+if( thread->next == thread )
+{
+// sole thread on list, NULL out ptr
+queue = NULL;
+}
+else
+{
+// advance to next and remove thread
+queue = thread->next;
+thread->remove();
+}
+thread->queue = NULL;
+return thread;
+}
+// -------------------------------------------------------------------------
+Cyg_Thread *Cyg_ThreadQueue_Implementation::highpri()
+{
+CYG_REPORT_FUNCTION();
+return queue;
+}
+// -------------------------------------------------------------------------
+void Cyg_ThreadQueue_Implementation::remove(Cyg_Thread *thread)
+{
+CYG_REPORT_FUNCTION();
+// If the thread we want is the at the head
+// of the list, and is on its own, clear the
+// list and return. Otherwise advance to the
+// next thread and remove ours. If the thread
+// is not at the head of the list, just dequeue
+// it.
+thread->queue = NULL;
+if( queue == thread )
+{
+if( thread->next == thread )
+{
+queue = NULL;
+return;
+}
+else queue = thread->next;
+}
+thread->Cyg_SchedThread_Implementation::remove();
+}
+// -------------------------------------------------------------------------
+// Rotate the front thread on the queue to the back.
+void Cyg_ThreadQueue_Implementation::rotate()
+{
+CYG_REPORT_FUNCTION();
+queue = queue->next;
+}
+// -------------------------------------------------------------------------
+#endif
+// -------------------------------------------------------------------------
+// EOF sched/lottery.cxx

Mercurial > ecos

comparison packages/kernel/current/src/sched/lottery.cxx @ 0:3111d98ba7b3 ecos-v1_1-release