StrictPolicyImpl.cc

Go to the documentation of this file.

/*
 * StrictPolicyImpl.cc
 *
 * Copyright (c) 2003 The University of Utah and the Flux Group.
 * All rights reserved.
 *
 * This file is licensed under the terms of the GNU Public License.  
 * See the file "license.terms" for restrictions on redistribution 
 * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
 */

/**
 * @file StrictPolicyImpl.cc
 *
 * Implementation of the StrictPolicyImpl class.
 */

#include "config.h"

#include <assert_pp.h>

#include "StubRealTimeTask.hh"
#include "StrictPolicyImpl.hh"

StrictPolicyImpl::StrictPolicyImpl(const char *name) :
    sp_Name(name)
{
    StubRealTimeTask *srtt;
    
    require(name != NULL);
    
    this->sp_MaxUsedCPU = DEFAULT_MAX_USED_CPU;
    this->sp_MinTaskCPU = DEFAULT_MIN_TASK_CPU;
    lnNewList((struct lnMinList *)&this->sp_List);
    memset(&this->sp_FauxTask, 0, sizeof(struct TaskPriority));
    this->sp_FauxTask.tp_Link.ln_Pri = 127;
    srtt = new StubRealTimeTask("_faux_");
    this->sp_FauxTask.tp_Task = srtt->_this();
}

StrictPolicyImpl::~StrictPolicyImpl()
{
}

char *StrictPolicyImpl::Name(void)
    throw (CORBA::SystemException)
{
    CORBA::String_var retval;

    retval = this->sp_Name;
    return( retval._retn() );
}

CORBA::Float StrictPolicyImpl::GetMaxCPUAllocation(void)
    throw (CORBA::SystemException)
{
    CORBA::Float retval;

    retval = this->sp_MaxUsedCPU;
    return( retval );
}

void StrictPolicyImpl::SetMaxCPUAllocation(CORBA::Float value)
    throw (CORBA::SystemException)
{
    if( (value < BrokerPolicies::StrictPolicy::CPU_ALLOCATION_MIN) ||
        (value > BrokerPolicies::StrictPolicy::CPU_ALLOCATION_MAX) )
    {
        throw CORBA::BAD_PARAM();
    }

    if( !lnEmptyList(&this->sp_List) )
    {
        if( value > this->sp_MaxUsedCPU )
        {
            CORBA::ULong amount;
            
            amount = (CORBA::ULong)
                ((value - this->sp_MaxUsedCPU) *
                 this->sp_FauxTask.tp_Schedule.rts_Deadline);
            this->GiveCPU(this->SubList(this->sp_FauxTask.tp_Schedule, NULL),
                          amount,
                          &this->sp_FauxTask);
        }
        else if( value < this->sp_MaxUsedCPU )
        {
            CORBA::ULong amount;
            
            amount = (CORBA::ULong)
                ((this->sp_MaxUsedCPU - value) *
                 this->sp_FauxTask.tp_Schedule.rts_Deadline);
            this->TakeCPU(this->SubList(this->sp_FauxTask.tp_Schedule, NULL),
                          amount,
                          &this->sp_FauxTask);
        }
    }
    this->sp_MaxUsedCPU = value;
}

void StrictPolicyImpl::AddTask(Broker::Task_ptr task,
                               const Broker::ScheduleParameters &sp)
    throw (CORBA::SystemException)
{
    Broker::RealTimeTask_ptr rtt;
    
    /* Check inputs. */
    if( CORBA::is_nil(task) )
    {
        throw CORBA::BAD_PARAM();
    }

    this->RepairTaskList();
    
    /* XXX We can only handle RealTimeTasks at the moment. */
    rtt = Broker::RealTimeTask::_narrow(task);
    if( !CORBA::is_nil(rtt) )
    {
        if( (rtt->Period() == 0) || (rtt->Deadline() == 0) )
        {
            throw CORBA::BAD_PARAM();
        }

        struct TaskPriority *tp = new TaskPriority();
        struct TaskPriority *sub_list;
        CORBA::ULong ct;
        
        /* Initialize the node and */
        tp->tp_Link.ln_Pred = NULL;
        tp->tp_Link.ln_Succ = NULL;
        tp->tp_Link.ln_Pri = 0;
        tp->tp_Task = rtt;
        /* ... cache some values. */
        tp->tp_Schedule.rts_Period = rtt->Period();
        tp->tp_Schedule.rts_Deadline = rtt->Deadline();
        
        /* XXX fix this, use task->GetComputeTime() */
        ct = (CORBA::ULong)(this->sp_MinTaskCPU *
                            (float)tp->tp_Schedule.rts_Deadline);
        sub_list = this->SubList(tp->tp_Schedule, tp);
        ct = this->TakeCPU(sub_list, ct, tp);
        try
        {
            rtt->SetComputeTime(ct);
            tp->tp_ComputeTime = ct;
        }
        catch(const CORBA::Exception &e)
        {
            cerr << e << endl;
        }
        catch(...)
        {
            cerr << "Gah error in SetComputeTime!\n"; // XXX
        }
        
        /* Finally, add it to list, ordered by tp_Link.ln_Pri. */
        lnEnqueue(&this->sp_List, &tp->tp_Link);
    }
}

void StrictPolicyImpl::RemoveTask(Broker::Task_ptr task)
    throw (CORBA::SystemException)
{
    Broker::RealTimeTask_ptr rtt;
    struct TaskPriority *tp;

    /* Find the task and */
    rtt = Broker::RealTimeTask::_narrow(task);
    if( (tp = this->FindTaskPriority(rtt)) == NULL )
    {
        throw CORBA::BAD_PARAM();
    }

    /* ... give its compute time to the others. */
    this->GiveCPU(this->SubList(tp->tp_Schedule, tp),
                  tp->tp_ComputeTime,
                  tp);
    /* Finally, remove the node and */
    lnRemove((struct lnMinNode *)&tp->tp_Link);
    /* ... delete it. */
    delete tp;
}

void StrictPolicyImpl::Activate(const Broker::TaskList &tl)
    throw (CORBA::SystemException)
{
    /* XXX */
}

void StrictPolicyImpl::Deactivate(void)
    throw (CORBA::SystemException)
{
    /* XXX */
}

Broker::TaskList *StrictPolicyImpl::GetTaskList(void)
    throw (CORBA::SystemException)
{
    Broker::TaskList_var retval;
    struct TaskPriority *tp;
    unsigned int lpc = 0;
    
    retval = new Broker::TaskList();
    retval->length(lnCountNodes((struct lnMinList *)&this->sp_List));
    tp = (struct TaskPriority *)this->sp_List.lh_Head;
    while( tp->tp_Link.ln_Succ != NULL )
    {
        (*retval)[lpc] = Broker::Task::_duplicate(tp->tp_Task.in());
        lpc += 1;
        tp = (struct TaskPriority *)tp->tp_Link.ln_Succ;
    }
    return( retval._retn() );
}

void StrictPolicyImpl::SetTaskPriority(Broker::Task_ptr task,
                                       CORBA::Short priority)
    throw (CORBA::SystemException)
{
    Broker::RealTimeTask_var rtt;
    struct TaskPriority *tp;

    rtt = Broker::RealTimeTask::_narrow(task);
    if( CORBA::is_nil(rtt.in()) )
    {
        throw CORBA::BAD_PARAM();
    }
    if( (tp = this->FindTaskPriority(rtt.in())) == NULL )
    {
        throw CORBA::BAD_PARAM();
    }

    /* Remove from the list */
    lnRemove((struct lnMinNode *)&tp->tp_Link);
    /* ... set the new priority */
    tp->tp_Link.ln_Pri = (char)priority;
    /* ... and reinsert to get the new ordering. */
    lnEnqueue(&this->sp_List, &tp->tp_Link);
}

CORBA::Short StrictPolicyImpl::GetTaskPriority(Broker::Task_ptr task)
    throw (CORBA::SystemException)
{
    Broker::RealTimeTask_var rtt;
    struct TaskPriority *tp;
    CORBA::Short retval;

    rtt = Broker::RealTimeTask::_narrow(task);
    if( CORBA::is_nil(rtt.in()) )
    {
        throw CORBA::BAD_PARAM();
    }
    if( (tp = this->FindTaskPriority(rtt.in())) == NULL )
    {
        throw CORBA::BAD_PARAM();
    }

    retval = tp->tp_Link.ln_Pri;
    return( retval );
}

struct StrictPolicyImpl::TaskPriority *
StrictPolicyImpl::SubList(const RealTimeSchedule &rts,
                          struct TaskPriority *ignore)
{
    CORBA::ULong start, stop, max_deadline = 0;
    struct TaskPriority *curr, *retval = NULL;

    start = rts.rts_Start;
    stop = rts.rts_Start + rts.rts_Deadline;
    retval = NULL;

    if( ignore != NULL )
    {
        max_deadline = ignore->tp_Schedule.rts_Deadline;
    }
    
    /* Walk the list to */
    curr = (struct TaskPriority *)this->sp_List.lh_Head;
    while( curr->tp_Link.ln_Succ != NULL )
    {
        /* ... see if they intersect and by how much */
        if( (curr != ignore) &&
            (curr->tp_SubTime = curr->tp_Schedule.intersect(start, stop)) > 0 )
        {
            curr->tp_SubLink = retval;
            retval = curr;
        }
        if( curr->tp_Schedule.rts_Deadline > max_deadline )
        {
            max_deadline = curr->tp_Schedule.rts_Deadline;
        }
        curr = (struct TaskPriority *)curr->tp_Link.ln_Succ;
    }

    {
        CORBA::ULong ct;

        ct = (CORBA::ULong)(this->sp_MaxUsedCPU * max_deadline);
        this->sp_FauxTask.tp_Schedule.rts_Period = max_deadline;
        this->sp_FauxTask.tp_Schedule.rts_Deadline = max_deadline;
        this->sp_FauxTask.tp_SubTime = ct;
        this->sp_FauxTask.tp_Task->SetComputeTime(ct);
        this->sp_FauxTask.tp_ComputeTime = ct;
    }
    
    return( retval );
}

CORBA::ULong StrictPolicyImpl::TakeCPU(struct TaskPriority *sub_list,
                                       CORBA::ULong amount,
                                       struct TaskPriority *for_tp)
{
    float percent_cpu, percent_req_cpu, percent_total_cpu = 0.0;
    CORBA::ULong ct, new_ct, window_ct, new_window_ct;
    CORBA::ULong retval = 0;
    struct TaskPriority *tp;

    require(for_tp != NULL);

#if defined(DEBUG)
    cout << "TakeCPU amount="
         << amount
         << "; for="
         << for_tp->tp_Task->Name()
         << "; start="
         << for_tp->tp_Schedule.rts_Start
         << "; period="
         << for_tp->tp_Schedule.rts_Period
         << "; deadline="
         << for_tp->tp_Schedule.rts_Deadline
         << endl;
#endif

    /* Figure out the total percentage of CPU currently in use. */
#if defined(DEBUG)
    cout << "\tName\tPri\tCPU\n";
#endif
    for( tp = sub_list; tp != NULL; tp = tp->tp_SubLink )
    {
        CORBA::ULong sub_us;
        
        ct = tp->tp_ComputeTime;
        percent_cpu = (float)ct / (float)tp->tp_Schedule.rts_Deadline;
        sub_us = (CORBA::ULong)((float)tp->tp_SubTime * percent_cpu);
        percent_cpu = (float)sub_us / (float)for_tp->tp_Schedule.rts_Deadline;
        percent_total_cpu += percent_cpu;
#if defined(DEBUG)
        cout << "\t"
             << tp->tp_Task->Name()
             << "\t"
             << tp->tp_Link.ln_Pri
             << "\t"
             << (percent_cpu * 100.0)
             << "%"
             << endl;
#endif
    }
    percent_req_cpu = (float)amount / (float)for_tp->tp_Schedule.rts_Deadline;
#if defined(DEBUG)
    cout << "\tSubtotal\t" << (percent_total_cpu * 100.0) << "%" << endl;
    cout << "\t" << for_tp->tp_Task->Name()
         << "\t" << for_tp->tp_Link.ln_Pri
         << "\t" << (percent_req_cpu * 100.0) << "%"
         << endl
         << "\tTotal\t\t"
         << ((percent_total_cpu + percent_req_cpu) * 100.0)
         << "%"
         << endl;
#endif
    if( (percent_total_cpu + percent_req_cpu) <= this->sp_MaxUsedCPU )
    {
        /* There is still some free CPU, give it to the requester. */
        retval = amount;
    }
    else
    {
        float percent_free_cpu;
        CORBA::ULong free_ct;

        /* There is contention */
        percent_free_cpu = this->sp_MaxUsedCPU - percent_total_cpu -
            ((float)for_tp->tp_ComputeTime /
             (float)for_tp->tp_Schedule.rts_Deadline);
        if( percent_free_cpu < 0.0 )
        {
            /* Adjust for any rounding errors/etc... */
            percent_free_cpu = 0.0;
        }
        free_ct = (CORBA::ULong)(percent_free_cpu *
                                 (float)for_tp->tp_Schedule.rts_Deadline);
#if defined(DEBUG)
        cout << "cpu free " << (percent_free_cpu * 100.0) << "%\n";
        cout << "already have " << for_tp->tp_ComputeTime << "..." << endl;
#endif
        /*
         * The task already has some compute time, subtract that from what they
         * need.
         */
        amount -= for_tp->tp_ComputeTime;
        retval += for_tp->tp_ComputeTime;
        if( amount > free_ct )
        {
            /* The amount needed is greater than the available CPU */
            amount -= free_ct;
            retval += free_ct;
        }
        else
        {
            retval += amount;
            amount = 0;
        }
#if defined(DEBUG)
        cout << "revoking " << amount << "..." << endl;
#endif
        percent_total_cpu = 0.0;
        /*
         * Walk the list as long as more CPU is needed and the task has
         * priority over the others.
         */
        for( tp = sub_list;
             tp &&
                 (for_tp->tp_Link.ln_Pri > tp->tp_Link.ln_Pri) &&
                 (amount > 0);
             tp = tp->tp_SubLink )
        {
            float percent_orig_cpu;

            /* Convert their CPU usage to our time frame by */
            ct = tp->tp_ComputeTime;
            /* ... figuring out their total allocated percentage and */
            percent_orig_cpu = (float)ct / (float)tp->tp_Schedule.rts_Deadline;
            /*
             * ... multiplying that by the amount of time that both tasks
             * interesect
             */
            window_ct = (CORBA::ULong)(percent_orig_cpu *
                                       (float)tp->tp_SubTime);
            if( amount > window_ct )
            {
                /*
                 * They don't have enough to satisfy the request, so take
                 * some of it away and look for more.
                 */
                new_window_ct = 0;
            }
            else
            {
                /* They have more than enough to satisfy the request. */
                new_window_ct = window_ct - amount;
            }
            /* Convert the CPU percentage back to the tasks time frame. */
            percent_cpu = (float)new_window_ct / (float)tp->tp_SubTime;
            if( percent_cpu < this->sp_MinTaskCPU )
            {
                percent_cpu = this->sp_MinTaskCPU;
                new_window_ct = (CORBA::ULong)
                    (percent_cpu * (float)tp->tp_SubTime);
            }
            amount -= (window_ct - new_window_ct);
            retval += (window_ct - new_window_ct);
            percent_total_cpu += percent_cpu;
#if defined(DEBUG)
            cout << "\t"
                 << tp->tp_Task->Name()
                 << "\t"
                 << (percent_orig_cpu * 100.0)
                 << "% -> "
                 << (percent_cpu * 100.0)
                 << "%"
                 << endl;
#endif
            new_ct = (CORBA::ULong)((float)tp->tp_Schedule.rts_Deadline *
                                    percent_cpu);
            try
            {
                tp->tp_Task->SetComputeTime(new_ct);
                tp->tp_ComputeTime = new_ct;
            }
            catch(...)
            {
                // assert(0);
            }
        }
        percent_req_cpu = (float)retval /
            (float)for_tp->tp_Schedule.rts_Deadline;
#if defined(DEBUG)
        cout << "\tSubtotal\t" << (percent_total_cpu * 100.0) << "%" << endl;
        cout << "\tTotal\t"
             << ((percent_total_cpu + percent_req_cpu) * 100.0)
             << "%"
             << endl;
#endif
    }

    if( retval < amount )
    {
        for_tp->tp_Flags |= TPF_STARVED;
    }
    else
    {
        for_tp->tp_Flags &= ~TPF_STARVED;
    }

#if defined(DEBUG)
    cout << "end TakeCPU retval="
         << retval
         << endl;
#endif
    
    return( retval );
}

CORBA::ULong StrictPolicyImpl::GiveCPU(struct TaskPriority *sub_list,
                                       CORBA::ULong amount,
                                       struct TaskPriority *for_tp)
{
    float percent_cpu, percent_ret_cpu, percent_total_cpu = 0.0;
    CORBA::ULong ct, new_ct, window_ct, new_window_ct;
    CORBA::ULong retval = 0;
    struct TaskPriority *tp;

    require(for_tp != NULL);

    /* Very similar to TakeCPU */

#if defined(DEBUG)
    try
    {
        cout << "GiveCPU amount="
             << amount
             << "; for="
             << for_tp->tp_Task->Name()
             << "; start="
             << for_tp->tp_Schedule.rts_Start
             << "; period="
             << for_tp->tp_Schedule.rts_Period
             << "; deadline="
             << for_tp->tp_Schedule.rts_Deadline
             << endl;
    }
    catch(const CORBA::SystemException &e)
    {
        cerr << e << endl;
    }
#endif

#if defined(DEBUG)
    cout << "\tName\tPri\tCPU\n";
#endif
    for( tp = sub_list; tp != NULL; tp = tp->tp_SubLink )
    {
        CORBA::ULong sub_us;
        
        ct = tp->tp_ComputeTime;
        percent_cpu = (float)ct / (float)tp->tp_Schedule.rts_Deadline;
        sub_us = (CORBA::ULong)((float)tp->tp_SubTime * percent_cpu);
        percent_cpu = (float)sub_us / (float)for_tp->tp_Schedule.rts_Deadline;
#if defined(DEBUG)
        try
        {
            cout << "\t"
                 << tp->tp_Task->Name()
                 << "\t"
                 << tp->tp_Link.ln_Pri
                 << "\t"
                 << (percent_cpu * 100.0)
                 << "%"
                 << endl;
        }
        catch(const CORBA::SystemException &e)
        {
            cerr << e << endl;
        }
#endif
        percent_total_cpu += percent_cpu;
    }
    percent_ret_cpu = (float)amount / (float)for_tp->tp_Schedule.rts_Deadline;
#if defined(DEBUG)
    cout << "\tSubtotal\t" << (percent_total_cpu * 100.0) << "%" << endl;
    try
    {
        cout << "\t" << for_tp->tp_Task->Name()
             << "\t" << for_tp->tp_Link.ln_Pri
             << "\t" << (percent_ret_cpu * 100.0) << "%"
             << endl
             << "\tTotal\t\t"
             << ((percent_total_cpu + percent_ret_cpu) * 100.0)
             << "%"
             << endl;
    }
    catch(const CORBA::SystemException &e)
    {
        cerr << e << endl;
    }
#endif
    {
#if defined(DEBUG)
        cout << "returning " << amount << "..." << endl;
#endif
        for( tp = sub_list; tp && (amount > 0); tp = tp->tp_SubLink )
        {
            float percent_orig_cpu;

            /*
             * Only give CPU to those tasks that are actually starved and need
             * it.
             */
            if( !(tp->tp_Flags & TPF_STARVED) )
            {
                continue;
            }
            ct = tp->tp_ComputeTime;
            percent_orig_cpu = (float)ct / (float)tp->tp_Schedule.rts_Deadline;
            window_ct = (CORBA::ULong)(percent_orig_cpu *
                                       (float)tp->tp_SubTime);
            if( (window_ct + amount) < tp->tp_Schedule.rts_Deadline )
            {
                new_window_ct = window_ct + amount;
                amount = 0;
            }
            else
            {
                CORBA::ULong diff;

                diff = tp->tp_Schedule.rts_Deadline - window_ct;
                new_window_ct = window_ct + (diff / 2);
                amount -= diff / 2;
            }
            percent_cpu = (float)new_window_ct / (float)tp->tp_SubTime;
#if defined(DEBUG)
            try
            {
                cout << "\t"
                     << tp->tp_Task->Name()
                     << "\t"
                     << (percent_orig_cpu * 100.0)
                     << "% -> "
                     << (percent_cpu * 100.0)
                     << "%"
                     << endl;
            }
            catch(const CORBA::SystemException &e)
            {
                cerr << e << endl;
            }
#endif
            new_ct = (CORBA::ULong)((float)tp->tp_Schedule.rts_Deadline *
                                    percent_cpu);
            try
            {
                tp->tp_Task->SetComputeTime(new_ct);
                tp->tp_ComputeTime = new_ct;
            }
            catch(const CORBA::Exception &e)
            {
                cerr << "SetComputeTime failed: " << e << endl;
            }
            catch(...)
            {
                cerr << "** Give failed: " << new_ct << endl;
            }
        }
    }

#if defined(DEBUG)
    cout << "end GiveCPU retval="
         << retval
         << endl;
#endif

    return( retval );
}

void StrictPolicyImpl::RepairTaskList(void)
{
    struct TaskPriority *curr, *succ;

    curr = (struct TaskPriority *)this->sp_List.lh_Head;
    while( curr->tp_Link.ln_Succ != NULL )
    {
        succ = (struct TaskPriority *)curr->tp_Link.ln_Succ;
        try
        {
            curr->tp_Task->GetComputeTime();
        }
        catch(const CORBA::TRANSIENT &e)
        {
            this->GiveCPU(this->SubList(curr->tp_Schedule, curr),
                          curr->tp_ComputeTime,
                          curr);
            lnRemove((struct lnMinNode *)&curr->tp_Link);
            delete curr;
        }
        curr = succ;
    }

}

struct StrictPolicyImpl::TaskPriority *
StrictPolicyImpl::FindTaskPriority(Broker::RealTimeTask_ptr task)
{
    struct TaskPriority *curr, *retval = NULL;

    require(task != NULL);
    
    curr = (struct TaskPriority *)this->sp_List.lh_Head;
    while( (retval == NULL) && (curr->tp_Link.ln_Succ != NULL) )
    {
        if( task->_is_equivalent(curr->tp_Task.in()) )
        {
            retval = curr;
        }
        curr = (struct TaskPriority *)curr->tp_Link.ln_Succ;
    }

    if( retval == NULL )
    {
        cerr << "Unknown task" << endl;
        throw Broker::Internal("FindTaskPriority failed to find task");
    }
    
    return( retval );
}

void StrictPolicyImpl::ChangeTaskCPU(Broker::RealTimeTask_ptr task,
                                     CORBA::ULong ct,
                                     CORBA::ULong status,
                                     CORBA::ULong advice)
    throw (CORBA::SystemException, Broker::InvalidState)
{
    struct TaskPriority *tp;

    require(task != NULL);

#if defined(DEBUG)
    cout << "policy: ct="
         << ct
         << "; status="
         << status
         << "; advice="
         << advice
         << endl;
#endif
    if( (tp = this->FindTaskPriority(task)) != NULL )
    {
        struct TaskPriority *sub_list;
        CORBA::ULong compute_us;

        /* Find the list of tasks that this one competes with and */
        sub_list = this->SubList(tp->tp_Schedule, tp);
        compute_us = tp->tp_ComputeTime;
        if( advice >= compute_us )
        {
            /* ... try to take CPU away from them for the task. */
            advice = this->TakeCPU(sub_list, advice, tp);
        }
        /* Finally, set their new compute time. */
        try
        {
            task->SetComputeTime(advice);
            tp->tp_ComputeTime = advice;
        }
        catch(const CORBA::Exception &e)
        {
            cerr << "SetComputeTime failed: " << e << endl;
        }
        catch(...)
        {
            cerr << "** Change failed: " << advice << endl;
        }
        if( advice < compute_us )
        {
            /* ... give back CPU that was taken away from them. */
            this->GiveCPU(sub_list, compute_us - advice, tp);
        }
    }
    else
    {
        throw Broker::InvalidState("AddTask must be called first");
    }
}

---