broker.java

实现网格环境下资源调度和分配的仿真

            case Experiment.OPTIMIZE_COST_PLUS:
                scheduled += scheduleWithDBC_CostOptimisation(
                                    new OrderCostTime() );
                break;

            case Experiment.OPTIMIZE_COST_TIME:
                scheduled += scheduleWithDBC_CostTimeOptimisation();
                break;

            case Experiment.OPTIMIZE_TIME:
                scheduled += scheduleWithDBC_TimeOptimisation();
                break;

            case Experiment.OPTIMIZE_NONE:
                // do nothing
                break;

            default:
                break;
        }

        return scheduled;
    }

    /**
     * It performs Deadline and Budget Constratined (DBC) Cost Minimisation
     * scheduling
     * @param sortComparator    a Comparator object
     * @return the number of Gridlets scheduled
     * @pre sortComparator != null
     * @post $result >= 0
     */
    private int scheduleWithDBC_CostOptimisation(Comparator sortComparator)
    {
        int scheduled = 0;  // No of Gridlets scheduled during this iteration
        Collections.sort(brokerResourceList_, sortComparator);

        for (int i = 0; i < brokerResourceList_.size() && 
                    glUnfinishedList_.size() > 0; i++)
        {
            BrokerResource br = (BrokerResource) brokerResourceList_.get(i);
            double AvailableMI = br.getAvailableMI(
                                        experiment_.getDeadlineTime() );

            // this is for scanning across whole list.
            GridletList glTempList = (GridletList) glUnfinishedList_.clone();

            // schedule as long as there Gridlets and MIs are available!
            for (int j = 0; j < glTempList.size() && AvailableMI > 0; j++)
            {
                Gridlet gl = (Gridlet) glTempList.get(j);

                // assign only when budget is available for processing on a
                // resource and it can complete by deadline.
                if ( isBudgetAvailable(gl, br) )
                {
                    if ( br.isSufficientMIAvailableOnSinglePE(gl,
                                experiment_.getDeadlineTime()) )
                    {
                        try {
                            gl.setGridletStatus(Gridlet.READY);
                        }
                        catch (Exception e) {
                            e.printStackTrace();
                        }
                        gl.setResourceParameter(br.resource.getResourceID(),
                                br.resource.getCostPerSec());

                        glUnfinishedList_.remove(gl);
                        br.glList.add(gl);
                        AvailableMI -= gl.getGridletLength();
                        scheduled++;
                    } // end if
                } // end if
            } // end for
        } // end for

        return scheduled;
    }

    /**
     * It performs Deadline and Budget Constratined (DBC) Cost+Time
     * Minimisation scheduling
     * @return the number of Gridlets scheduled
     * @pre $none
     * @post $result >= 0
     */
    private int scheduleWithDBC_CostTimeOptimisation()
    {
        int scheduled = 0;  // No of Gridlets scheduled during this iteration
        Collections.sort(brokerResourceList_, new OrderCostTime());

        // Initialise BrokerResourcesWithSameCostPerMI parameters
        BrokerResource br;
        LinkedList BrokerResourcesWithSameCostPerMI = new LinkedList();

        for (int currentBRindex = 0; glUnfinishedList_.size() > 0 && 
                 currentBRindex < brokerResourceList_.size();
                 currentBRindex++)
        {
            // Create a List of BrokerResourcesWithSameCostPerMI
            BrokerResourcesWithSameCostPerMI.clear();   // clear old listing.

            // add current resource to the list
            br = (BrokerResource) brokerResourceList_.get(currentBRindex);
            BrokerResourcesWithSameCostPerMI.add((BrokerResource) br);

            // group all those resources with the same cost PerMI as the
            // current resource into the list BrokerResourcesWithSameCostPerMI
            while (currentBRindex < brokerResourceList_.size()-1 &&
                   br.resource.getCostPerMI() == ( (BrokerResource)
                            brokerResourceList_.get(currentBRindex+1)
                       ).resource.getCostPerMI() )
            {
                currentBRindex++;
                br = (BrokerResource) brokerResourceList_.get(currentBRindex);
                BrokerResourcesWithSameCostPerMI.add((BrokerResource) br);
            }

            // Allocate Tasks to BrokerResourcesWithSameCostPerMI with Time
            // Minimisation Style
            // schedule as long as there are Gridlets and MIs are available!
            LinkedList BRGridletTimeList = new LinkedList();

            // this is for scanning all Gridlets
            GridletList glTempList = (GridletList) glUnfinishedList_.clone();
            for (int j = 0; j < glTempList.size(); j++)
            {
                Gridlet gl = (Gridlet) glTempList.get(j);
                BRGridletTimeList.clear();

                // TimeMinimisation Algorithm:
                // 1. For each resource, calculate the next completion time
                // for an assigned job, taking
                // into account previously assigned jobs.
                for (int k = 0;k < BrokerResourcesWithSameCostPerMI.size();k++)
                {
                    BRGridletTimeList.add( new BRGridletProcessingTime(
                         (BrokerResource) BrokerResourcesWithSameCostPerMI.get(
                              k), gl) );
                }

                // 2. Sort resources by next completion time.
                Collections.sort(BRGridletTimeList,
                        new OrderBRGridletProcessingTime());

                // 3. Assign Gridlet to a resource whose cost per Gridlet is
                // less than or equal to the
                // remaining budget per Gridlet. AND gridlet can be finished
                // within the Deadline.
                boolean gridlet_assigned_flag = false;
                for (int k = 0; k < BRGridletTimeList.size() &&
                        !gridlet_assigned_flag; k++)
                {
                    BrokerResource myBR = ( (BRGridletProcessingTime)
                            BRGridletTimeList.get(k) ).br;

                    // RemainingBudgetForGridlet(gl) may be replaced by just
                    // BudgetAvailable ?
                    double Gl_completion_time = GridSim.clock() +
                        ( (BRGridletProcessingTime)BRGridletTimeList.get(k)
                         ).gridlet_processing_time;

                    if ( Gl_completion_time <= experiment_.getDeadlineTime() )
                    {
                        if ( isBudgetAvailable(gl, myBR) )
                        {
                            try {
                                gl.setGridletStatus(Gridlet.READY);
                            }
                            catch (Exception e) {
                                e.printStackTrace();
                            }
                            gl.setResourceParameter(
                                    myBR.resource.getResourceID(),
                                    myBR.resource.getCostPerSec() );

                            glUnfinishedList_.remove(gl);
                            myBR.glList.add(gl);
                            scheduled++;
                            gridlet_assigned_flag = true;
                        } // end if
                    } // end if
                } // end for
            } // end for
        } // end for

        return scheduled;
    }

    /**
     * It performs Deadline and Budget Constratined (DBC) Cost+Time
     * Minimisation scheduling
     * @return the number of Gridlets scheduled
     * @pre $none
     * @post $result >= 0
     */
    private int scheduleWithDBC_TimeOptimisation()
    {
        int scheduled = 0;  // No of Gridlets scheduled during this iteration
        Collections.sort(brokerResourceList_, new OrderCostTime());

        // Initialise BrokerResourcesWithSameCostPerMI parameters
        BrokerResource br;
        LinkedList BrokerResourcesToUse = new LinkedList();

        // Allocate Tasks to BrokerResourcesWithSameCostPerMI with Time
        // Minimisation Style
        // schedule as long as there are Gridlets and MIs are available!
        LinkedList BRGridletTimeList = new LinkedList();
        GridletList glTempList = (GridletList) glUnfinishedList_.clone();

        // Time Minimisation Algorithm:
        for (int j = 0; j < glTempList.size(); j++)
        {
            Gridlet gl = (Gridlet) glTempList.get(j);
            BRGridletTimeList.clear();

            // 0. Create AFFORDABLE Broker Resources List
            BrokerResourcesToUse.clear();   // clear old listing

            for (int k = 0; k < brokerResourceList_.size(); k++)
            {
                br = (BrokerResource) brokerResourceList_.get(k);
                if (br.getExpectedProcessingCost(gl) <=
                        remainingBudgetForGridlet(gl))
                {
                    BrokerResourcesToUse.add( (BrokerResource) br );
                }
            }

            // If there are Afforable resources for processing Gridlets,
            // do scheduling.
            if (BrokerResourcesToUse.size() > 0)
            {
                // 1. For each resource, calculate the next completion time for
                // an assigned job, taking
                // into account previously assigned jobs.

                for (int k = 0; k <  BrokerResourcesToUse.size(); k++)
                {
                    BRGridletTimeList.add( new BRGridletProcessingTime(
                        (BrokerResource) BrokerResourcesToUse.get(k), gl) );
                }

                // 2. Sort resources by next completion time.
                Collections.sort(BRGridletTimeList,
                    new OrderBRGridletProcessingTime());

                // 3. Assign Gridlet to a resource whose cost per Gridlet is
                // less than or equal to the
                // remaining budget per Gridlet. AND gridlet can be finished
                // within the Deadline.
                boolean gridlet_assigned_flag = false;
                for (int k = 0; k < BRGridletTimeList.size() &&
                        !gridlet_assigned_flag; k++)
                {
                    BrokerResource myBR = ( (BRGridletProcessingTime)
                            BRGridletTimeList.get(k) ).br;

                    // remainingBudgetForGridlet(gl) may be replaced by just
                    // BudgetAvailable ?
                    double Gl_completion_time = GridSim.clock() +
                        ( (BRGridletProcessingTime)BRGridletTimeList.get(k)
                        ).gridlet_processing_time;

                    if ( Gl_completion_time <= experiment_.getDeadlineTime() )
                    {
                        try {
                            gl.setGridletStatus(Gridlet.READY);
                        }
                        catch (Exception e) {
                            e.printStackTrace();
                        }
                        gl.setResourceParameter(myBR.resource.getResourceID(),
                                myBR.resource.getCostPerSec());

                        glUnfinishedList_.remove(gl);
                        myBR.glList.add(gl);
                        scheduled++;
                        gridlet_assigned_flag = true;
                    } // end if
                } // end for
            } // end if
        } // end for
        return scheduled;
    }

    /**
     * Responsibles for assigning Gridlets from
     * Gridlets list in Broker Resource to Grid Resource in such a way
     * that GridResource is not overload.
     * <p>
     * This decision is made based
     * current load on Grid resource and size along in case of Time shared
     * resources.
     * If resource is Space shared, then it is based on number of nodes that
     * are free.
     * @pre $none
     * @post $result >= 0
     */
    private int dispatcher()
    {
        // TODO: this method is unused
        int dispatched = 0;
        for (int i = 0; i < brokerResourceList_.size(); i++)
        {
            BrokerResource br = (BrokerResource) brokerResourceList_.get(i);
            int NoOfPEs = br.resource.getNumPE();
            int NoOfGridletsToBeDispatched = br.getNumGridletInReady();
            int NoOfGridletsOnResource = br.getNumGridletInExec() +
                        br.getNumGridletInQueue();

            int OptimalDisptachSize = 0;
            int NoOfGridletsCanBeDispatched = 0;

            // Determine How many Gridlets to be dispatched depending on Type
            // of Resource
            switch ( br.resource.getResourceAllocationPolicy() )
            {
                case ResourceCharacteristics.TIME_SHARED:
                    // How many to be sent to a resource can be based on the
                    // following:
                    // 1. Load on PEs or resource
                    // 2. How many of your Gridlets are running
                    // A simple heuristic can be be about 2 Gridlets on each PE
                    // GET IDEA from Nimrod-G or some Heuristic in Laterature
                    NoOfGridletsCanBeDispatched = NoOfPEs * maxGridletPerPE_ -
                            NoOfGridletsOnResource;

                    OptimalDisptachSize = Math.min(NoOfGridletsToBeDispatched,
                            NoOfGridletsCanBeDispatched);
                    break;

                case ResourceCharacteristics.SPACE_SHARED:
                    NoOfGridletsCanBeDispatched = NoOfPEs * maxGridletPerPE_ -
                            br.getNumGridletInQueue();

                    OptimalDisptachSize = Math.min(NoOfGridletsToBeDispatched,
                            NoOfGridletsCanBeDispatched);
                    break;

                case ResourceCharacteristics.ADVANCE_RESERVATION:
                    // TODO: not yet done....
                    break;

                default:
                    break;
            }

            for (int j = 0;j < br.glList.size() && OptimalDisptachSize > 0;j++)
            {
                Gridlet gl = (Gridlet) br.glList.get(j);
                if (gl.getGridletStatus() == Gridlet.READY)
                {
                    // queues gridlet for execution on a resource
                    super.gridletSubmit(gl, br.resource.getResourceID());
                    br.NoOfGridletsDispatchedSoFar++;
                    gridletDispatched_++;
                    OptimalDisptachSize--;
                    dispatched++;
                } // end if
            } // end for
        } // end for

        return dispatched;
    }

} // end class