path: root/ecos/packages/kernel/current/src/sched/lottery.cxx

//==========================================================================
//
//      sched/lottery.cxx
//
//      Lottery scheduler class implementation
//
//==========================================================================
// ####ECOSGPLCOPYRIGHTBEGIN####                                            
// -------------------------------------------                              
// This file is part of eCos, the Embedded Configurable Operating System.   
// Copyright (C) 1998, 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
//
// 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.,    
// 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, 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 v2.                                               
//
// This exception does not invalidate any other reasons why a work based    
// on this file might be covered by the GNU General Public License.         
// -------------------------------------------                              
// ####ECOSGPLCOPYRIGHTEND####                                              
//==========================================================================
//#####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 CYGPKG_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