broker.java

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

            // initialise Report header.
            scheduleReport(experiment_, BRListOriginal, true);
            scheduleReport(experiment_, BRListOriginal, false);

            // SCHEDUDLING: Do until experiment finishes
            while (glFinishedList_.size() < experiment_.getGridletList().size())
            {
                // stop if there is no sufficient deadline or budget is
                // available.
                if ( (GridSim.clock() >= experiment_.getDeadlineTime()) ||
                     (expenses_ >= experiment_.getBudget()) )
                {
                    break;
                }

                // TODO: these 2 statements are unused
                // TODO: if commented this one, the gridlets are NOT assigned
                // to resources
                int scheduled = scheduleAdviser();

                // TODO: if commented this one, the gridlets are assigned to
                // resources but not executed.
                int just_dispatched = dispatcher();

                int just_received = gridletReceptor();
                scheduleReport(experiment_, BRListOriginal, false);

                // Broker entity should hold for sometime to advance simulation
                // time. Otherwise, no other entities can proceed nor any
                // events/messages are delivered to other entities.
                if (just_received == 0)
                {
                    double deadline_left = experiment_.getDeadlineTime() -
                                GridSim.clock();

                    // heurisitics for deciding hold condition
                    // hold period can be as high as the time required to
                    // process some Gridlets.
                    // HOLD PERIOD NEED TO BE AS HIGH AS SMALLEST PROCESSING
                    // TIME OF A GRIDLET
                    // Something like:
                    //      Math.min(deadline_left*0.01, GridLetProcessingTIME);
                    //---->WARNINING------------
                    // THE CAN LEAD  TO ERROR<PAST Events Detected>: if hold
                    // period is Larger than
                    // processing time of a Gridlet, because when Gridlet is
                    // dispatched and this is Still in Hold

                    double holdperiod = Math.max(deadline_left * 0.01, 1.0);

                    // holdperiod = 1.0;
                    // broker holds for some period for other activities to
                    // proceed.
                    // holdperiod = 1; OR less takes MORE simulation time,
                    // but makes Simulation more precise.
                    // REAL systems use higher HOLD-period because lower values
                    // introduces too much overhead on the broker.

                    //System.out.println("deadline_left = " + deadline_left + 
                    //        ", holdperiod = " + holdperiod);

                    super.gridSimHold(holdperiod);

                    // NOTE: GridSimHold may be changed to INTERRUPTABLE Hold,
                    // then event should be procesed. Otherwise, this can lead
                    // to Past events detected.
                }
            }

            // Capture all events related to Gridlets that have been scheduled
            // for execution, but not yet received.
            while (gridletDispatched_ > gridletReturned_)
            {
                gridletReceptor();
                scheduleReport(experiment_, BRListOriginal, false);
            }

            aggregatedScheduleReport(experiment_, BRListOriginal);
            super.send(UserEntityID, GridSimTags.SCHEDULE_NOW,
                    GridSimTags.EXPERIMENT, experiment_);
        }

        super.terminateIOEntities();
    }

    //////////////////////// PRIVATE METHODS /////////////////////////////

    /**
     * Finds the broker resource with a specified resource name
     * @param BRList    a linked-list containing BrokerResource objects
     * @param resourceName  a resource name entity
     * @return a <tt>BrokerResource</tt> object or <tt>null</tt> if not found
     * @pre BRList != null
     * @pre resourceName != null
     * @post $none
     */
    private BrokerResource findBrokerResourceWithName(LinkedList BRList,
                String resourceName)
    {
        for (int i = 0; i < BRList.size(); i++)
        {
            BrokerResource br = (BrokerResource) BRList.get(i);
            if (resourceName.compareTo( br.resource.getResourceName() ) == 0) {
                return br;
            }
        }
        return null;
    }

    /**
     * Receives a Gridlet one at a time
     * @return number of Gridlets received
     * @pre $none
     * @post $none
     */
    private int gridletReceptor()
    {
        int received = 0;

        if (gridletDispatched_ > gridletReturned_)
        {
            do
            {
                // Get Gridlet finished information via input entity
                Gridlet glFinished = super.gridletReceive();

                super.recordStatistics("BROKER.Gridlet.EndTime",
                        glFinished.getGridletID());

                // Updated Broker Resource:
                BrokerResource brServed = whoServed(glFinished);
                brServed.NoOfGridletsFinishedSoFar++;
                brServed.ProcessingExpensesSoFar +=
                        glFinished.getProcessingCost();

                // Update Available Resource Share
                brServed.updateAvailableMIPS(glFinished, maxGridletPerPE_);

                // move just finished Gridlet from Broker Resource to the
                // glFinishedList_
                brServed.glList.remove(glFinished);
                glFinishedList_.add(glFinished);

                // updated global parameters.
                gridletReturned_++;
                expenses_ += glFinished.getProcessingCost();
                received++;
            }
            while (super.sim_waiting(new Sim_from_port(super.input) ) > 0);
        }

        return received;
    }

    /**
     * Identified by a BrokerResource which processed the Gridlet
     * @param gl    a Gridlet object
     * @return <tt>BrokerResource</tt> that executed Gridlet
     * @pre gl != null
     * @post $result != null
     * @see gridsim.Gridlet
     * @see gridbroker.BrokerResource
     */
    private BrokerResource whoServed(Gridlet gl)
    {
        BrokerResource br = null;
        for (int i = 0; i < brokerResourceList_.size(); i++)
        {
            br = (BrokerResource) brokerResourceList_.get(i);
            if (br.glList.contains(gl)) {
                break;
            }
        }
        return br;
    }

    /**
     * Budget committed, but NOT yet spent.
     * Processing Cost of Gridlets in READY, INQUEUE, or INEXEC
     * @return Expected cost of processing Gridlets that are already
     *         committeed to resources
     * @pre $none
     * @post $result >= 0.0
     */
    private double budgetOnHold()
    {
        double amount = 0;
        int j = 0;
        int status = 0;

        for (int i = 0; i < brokerResourceList_.size(); i++)
        {
            BrokerResource br = (BrokerResource) brokerResourceList_.get(i);
            for (j = 0; j < br.glList.size(); j++)
            {
                Gridlet gl = (Gridlet) br.glList.get(j);
                status =  gl.getGridletStatus();
                if (status == Gridlet.READY || status == Gridlet.QUEUED ||
                        status == Gridlet.INEXEC)
                {
                    amount += br.getExpectedProcessingCost(gl);
                }
            }
        }
        return amount;
    }

    /**
     * Decide whether budget is available for processing Gridlet on a broker
     * resource
     * @param gl    a Gridlet object
     * @param obj   a BrokerResource object
     * @return <tt>true</tt> if budget available, <tt>false</tt>otherwise
     * @pre gl != null
     * @pre obj != null
     * @post $none
     */
    private boolean isBudgetAvailable(Gridlet gl, BrokerResource obj)
    {
        if ( (expenses_ + budgetOnHold() + obj.getExpectedProcessingCost(gl)) <=
                experiment_.getBudget() )
        {
            return true;
        }
        else {
            return false;
        }
    }

    /**
     * The budget available for allocation...after excluding "the budget spent
     * + committed
     * @return the remaining budget
     * @pre $none
     * @post $result >= 0.0
     */
    private double experimentRemainingBudget()
    {
        // budget spent + budget committed need to be taken into consideration
        return experiment_.getBudget() - ( expenses_ + budgetOnHold() );
    }

    /**
     * It takes the length of other Gridlets into consideration
     * @param gl    a Gridlet object
     * @return the proportional available budget for processing the Gridlet
     * @pre gl != null
     * @post $result >= 0.0
     */
    private double remainingBudgetForGridlet(Gridlet gl)
    {
        double remaining_budget = experimentRemainingBudget();

        // find out sum of all UnAssignedGridlet Length();
        double sum_gridlets_length = 0;
        for (int i = 0; i < glUnfinishedList_.size(); i++)
        {
            sum_gridlets_length +=
                    ( (Gridlet) glUnfinishedList_.get(i) ).getGridletLength();
        }

        double available_budget_per_MI = remaining_budget/sum_gridlets_length;
        return available_budget_per_MI * gl.getGridletLength();
    }

    /**
     * Depending on Optimisation Policy, it selects resources
     * @return the number of Gridlets scheduled
     * @pre $none
     * @post $result >= 0
     */
    private int scheduleAdviser()
    {
        if (experiment_.getOptimizationStrategy() == Experiment.OPTIMIZE_TIME)
        {
            // Removing all non-dispatched gridlets for making FRESH decision
            // on mapping Gridlets to resources
            // May be we can do Prediction to see how many to REMOVE from the
            // previous assignment
            int rating = 0;
            int gridletReady = 0;

            for (int i = 0; i < brokerResourceList_.size(); i++)
            {
                BrokerResource br = (BrokerResource) brokerResourceList_.get(i);
                rating = br.resource.getMIPSRating();
                double per1 = br.getAvailableMIPS_PreviousSchedule() / rating;
                double per2 = br.getAvailableMIPS() / rating;

                gridletReady = br.getNumGridletInReady();
                int ExpectedToFinish = (int) ( (per2/per1) * gridletReady );
                int ExcessGridlets = gridletReady - ExpectedToFinish;

                // Remove ExcessGridlets from the assigned list.
                // this is for scanning across whole list.
                GridletList glTempList = (GridletList) br.glList.clone();
                for (int j = 0; ExcessGridlets >0 && j< glTempList.size(); j++)
                {
                    Gridlet gl = (Gridlet) glTempList.get(j);
                    if (gl.getGridletStatus() == Gridlet.READY)
                    {
                        // change Gridlet Status back to Created, remove from
                        // the BR and add to glUnfinishedList_!
                        try {
                            gl.setGridletStatus(Gridlet.CREATED);
                        }
                        catch (Exception e) {
                            e.printStackTrace();
                        }

                        br.glList.remove(gl);
                        glUnfinishedList_.add(gl);
                        --ExcessGridlets;
                    } // end if
                } // end for

                br.setAvailableMIPS_PreviousSchedule();
            } // end for
        } // end if

        else
        {

            // Removing all non-dispatched gridlets for making FRESH decision
            // on mapping Gridlets to resources
            // May be we can do Prediction to see how many to REMOVE from the
            // previous assignment
            for (int i = 0; i < brokerResourceList_.size(); i++)
            {
                BrokerResource br = (BrokerResource) brokerResourceList_.get(i);

                // Create temporary GL list from the br.glList since using
                // br.glList.size() in LOOP + removing items
                // from br.glList leads to inconsistency.
                // this is for scanning across whole list.
                GridletList glTempList = (GridletList) br.glList.clone();
                for (int j = 0; j < glTempList.size(); j++)
                {
                    Gridlet gl = (Gridlet) glTempList.get(j);
                    if (gl.getGridletStatus() == Gridlet.READY)
                    {
                        // change Gridlet Status back to Created, remove from
                        // the BR and add to glUnfinishedList_!
                        try {
                            gl.setGridletStatus(Gridlet.CREATED);
                        }
                        catch (Exception e) {
                            e.printStackTrace();
                        }
                        br.glList.remove(gl);
                        glUnfinishedList_.add(gl);
                    } // end if
                } // end for
            } // end for
        } // end else

        int scheduled = experiment_.getNumGridlet() -
                            (glFinishedList_.size() + glUnfinishedList_.size());

        if (glUnfinishedList_.size() == 0) {
            return scheduled;
        }

        // sort by the ascending order of length to maximize packing AND it can
        // also be reverse to minimise the risk of exceeding too much beyond
        // deadline if resources do not perform as expected!
        glUnfinishedList_.sort();

        switch ( experiment_.getOptimizationStrategy() )
        {
            case Experiment.OPTIMIZE_COST:
                scheduled += scheduleWithDBC_CostOptimisation(new OrderCost());
                break;