timeshared.java

一个非常著名的网格模拟器,能够运行网格调度算法!

                    + " Gridlet #" + gridletId + " for User #" + userId
                    + " since it has FINISHED.");

            if (ack == true)
            {
                super.sendAck(GridSimTags.GRIDLET_SUBMIT_ACK, false, gridletId,
                              userId);
            }

            super.sendFinishGridlet(gl);   // sends the Gridlet back to sender
        }
        // moves this Gridlet to another GridResource entity
        else {
            super.gridletMigrate(gl, destId, ack);
        }
    }

    /**
     * Resumes a Gridlet only in the paused list.
     * The User ID is important as many Users might have the same Gridlet ID
     * in the lists.
     * @param gridletId    a Gridlet ID
     * @param userId       the user or owner's ID of this Gridlet
     * @param   ack   an acknowledgement, i.e. <tt>true</tt> if wanted to know
     *        whether this operation is success or not, <tt>false</tt>
     *        otherwise (don't care)
     * @pre gridletId > 0
     * @pre userId > 0
     * @post $none
     */
    public void gridletResume(int gridletId, int userId, boolean ack)
    {
        boolean success = false;

        // finds in the execution list first
        int found = super.findGridlet(gridletPausedList_, gridletId, userId);
        if (found >= 0)
        {
            // need to update Gridlets in execution up to this point in time
            updateGridletProcessing();

            // remove a Gridlet from paused list and change the status
            ResGridlet rgl = (ResGridlet) gridletPausedList_.remove(found);
            rgl.setGridletStatus(Gridlet.RESUMED);

            // add the Gridlet back to in execution list
            gridletInExecList_.add(rgl);

            // then forecast Gridlets in execution list
            forecastGridlet();

            success = true;
            System.out.println(super.resName_ +
                    ".TimeShared.gridletResume(): Gridlet #" + gridletId +
                    " with User #" + userId + " has been sucessfully RESUMED.");
        }
        else  // if no found then prints an error msg
        {
            System.out.println(super.resName_ +
                    ".TimeShared.gridletResume(): Cannot find Gridlet #" +
                    gridletId + " for User #" + userId);
        }

        // sends back an ack to sender
        if (ack == true)
        {
            super.sendAck(GridSimTags.GRIDLET_RESUME_ACK, success,
                          gridletId, userId);
        }
    }


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

    /**
     * Updates the execution of all Gridlets for a period of time.
     * The time period is determined from the last update time up to the
     * current time. Once this operation is successfull, then the last update
     * time refers to the current time.
     * @pre $none
     * @post $none
     */
    private void updateGridletProcessing()
    {
        // Identify MI share for the duration (from last event time)
        double time = GridSim.clock();
        double timeSpan = time - lastUpdateTime_;

        // if current time is the same or less than the last update time,
        // then ignore
        if (timeSpan <= 0.0) {
            return;
        }

        // Update Current Time as the Last Update
        lastUpdateTime_ = time;

        // update the GridResource load
        int size = gridletInExecList_.size();
        double load = super.calculateTotalLoad(size);
        super.addTotalLoad(load);       // add the current resource load

        // if no Gridlets in execution then ignore the rest
        if (size == 0) {
            return;
        }

        // gets MI Share for all Gridlets
        MIShares shares = getMIShare(timeSpan, size);
        ResGridlet obj = null;

        // a loop that allocates MI share for each Gridlet accordingly
        // In this algorithm, Gridlets at the front of the list
        // (range = 0 until MIShares.maxCount-1) will be given max MI value
        // For example, 2 PEs and 3 Gridlets. PE #0 processes Gridlet #0
        // PE #1 processes Gridlet #1 and Gridlet #2
        int i = 0;  // a counter
        Iterator iter = gridletInExecList_.iterator();
        while ( iter.hasNext() )
        {
            obj = (ResGridlet) iter.next();

            // Updates the Gridlet length that is currently being executed
            if (i < shares.maxCount) {
                obj.updateGridletFinishedSoFar(shares.max);
            }
            else {
                obj.updateGridletFinishedSoFar(shares.min);
            }

            i++;   // increments i
        }
    }

    /**
     * Identifies MI share (max and min) for all Gridlets in
     * a given time duration
     * @param timeSpan duration
     * @param size    total number of Gridlets in the execution list
     * @return  the total MI share that a Gridlet gets for a given
     *          <tt>timeSpan</tt>
     */
    private MIShares getMIShare(double timeSpan, int size)
    {
        // 1 - localLoad_ = available MI share percentage
        double localLoad = super.resCalendar_.getCurrentLoad();
        double TotalMIperPE = super.resource_.getMIPSRatingOfOnePE() * timeSpan
                              * (1 - localLoad);

        // This TimeShared is not Round Robin where each PE for 1 Gridlet only.
        // a PE can have more than one Gridlet executing.
        // minimum number of Gridlets that each PE runs.
        int glDIVpe = size / super.totalPE_;

        // number of PEs that run one extra Gridlet
        int glMODpe = size % super.totalPE_;

        // If num Gridlets in execution > total PEs in a GridResource,
        // then divide MIShare by the following constraint:
        // - obj.max = MIShare of a PE executing n Gridlets
        // - obj.min = MIShare of a PE executing n+1 Gridlets
        // - obj.maxCount = a threshold number of Gridlets will be assigned to
        //                  max MI value.
        //
        // In this algorithm, Gridlets at the front of the list
        // (range = 0 until maxCount-1) will be given max MI value
        if (glDIVpe > 0)
        {
            // this is for PEs that run one extra Gridlet
            share_.min = TotalMIperPE / (glDIVpe + 1);
            share_.max = TotalMIperPE / glDIVpe;
            share_.maxCount = (super.totalPE_ - glMODpe) * glDIVpe;
        }

        // num Gridlet in Exec < total PEs, meaning it is a
        // full PE share: i.e a PE is dedicated to execute a single Gridlet
        else
        {
            share_.max = TotalMIperPE;
            share_.min = TotalMIperPE;
            share_.maxCount = size;   // number of Gridlet
        }

        return share_;
    }

    /**
     * Determines the smallest completion time of all Gridlets in the execution
     * list. The smallest time is used as an internal event to
     * update Gridlets processing in the future.
     * <p>
     * The algorithm for this method:
     * <ul>
     *     <li> identify the finish time for each Gridlet in the execution list
     *          given the share MIPS rating for all and the remaining Gridlet's
     *          length
     *     <li> find the smallest finish time in the list
     *     <li> send the last Gridlet in the list with
     *          <tt>delay =  smallest finish time - current time</tt>
     * </ul>
     * @pre $none
     * @post $none
     */
    private void forecastGridlet()
    {
        // if no Gridlets available in exec list, then exit this method
        if (gridletInExecList_.size() == 0) {
            return;
        }

        // checks whether Gridlets have finished or not. If yes, then remove
        // them since they will effect the MIShare calculation.
        checkGridletCompletion();

        // Identify MIPS share for all Gridlets for 1 second, considering
        // current Gridlets + No of PEs.
        MIShares share = getMIShare( 1.0, gridletInExecList_.size() );

        ResGridlet rgl = null;
        int i = 0;
        double time = 0.0;
        double rating = 0.0;
        double smallestTime = 0.0;

        // For each Gridlet, determines their finish time
        Iterator iter = gridletInExecList_.iterator();
        while ( iter.hasNext() )
        {
            rgl = (ResGridlet) iter.next();

            // If a Gridlet locates before the max count then it will be given
            // the max. MIPS rating
            if (i < share.maxCount) {
                rating = share.max;
            }
            else {   // otherwise, it will be given the min. MIPS Rating
                rating = share.min;
            }

            time = forecastFinishTime(rating, rgl.getRemainingGridletLength() );

            int roundUpTime = (int) (time+1);   // rounding up
            rgl.setFinishTime(roundUpTime);

            // get the smallest time of all Gridlets
            if (i == 0 || smallestTime > time) {
                smallestTime = time;
            }

            i++;
        }

        // sends to itself as an internal event
        super.sendInternalEvent(smallestTime);
    }

    /**
     * Checks all Gridlets in the execution list whether they are finished or
     * not.
     * @pre $none
     * @post $none
     */
    private void checkGridletCompletion()
    {
        ResGridlet rgl = null;

        // a loop that determine the smallest finish time of a Gridlet
        // Don't use an iterator since it causes an exception because if
        // a Gridlet is finished, gridletFinish() will remove it from the list.
        int i = 0;
        while ( i < gridletInExecList_.size() )
        {
            rgl = (ResGridlet) gridletInExecList_.get(i);

            // if a Gridlet has finished, then remove it from the list
            if (rgl.getRemainingGridletLength() <= 0.0)
            {
                gridletFinish(rgl, Gridlet.SUCCESS);
                continue;  // not increment i coz the list size also decreases
            }

            i++;
        }
    }

    /**
     * Forecast finish time of a Gridlet.
     * <tt>Finish time = length / available rating</tt>
     * @param availableRating   the shared MIPS rating for all Gridlets
     * @param length   remaining Gridlet length
     * @return Gridlet's finish time.
     */
    private double forecastFinishTime(double availableRating, double length)
    {
        double finishTime = length / availableRating;

        // This is as a safeguard since the finish time can be extremely
        // small close to 0.0, such as 4.5474735088646414E-14. Hence causing
        // some Gridlets never to be finished and consequently hang the program
        if (finishTime < 1.0) {
            finishTime = 1.0;
        }

        return finishTime;
    }

    /**
     * Updates the Gridlet's properties, such as status once a
     * Gridlet is considered finished.
     * @param rgl     a ResGridlet object
     * @param status  the status of this ResGridlet object
     * @pre rgl != null
     * @post $none
     */
    private void gridletFinish(ResGridlet rgl, int status)
    {
        // NOTE: the order is important! Set the status first then finalize
        // due to timing issues in ResGridlet class.
        rgl.setGridletStatus(status);
        rgl.finalizeGridlet();

        // sends back the Gridlet with no delay
        Gridlet gl = rgl.getGridlet();
        super.sendFinishGridlet(gl);

        // remove this Gridlet in the execution
        gridletInExecList_.remove(rgl);
    }

    /**
     * Handles internal event
     * @pre $none
     * @post $none
     */
    private void internalEvent()
    {
        // this is a constraint that prevents an infinite loop
        // Compare between 2 floating point numbers. This might be incorrect
        // for some hardware platform.
        if ( lastUpdateTime_ == GridSim.clock() ) {
            return;
        }

        // update Gridlets in execution up to this point in time
        updateGridletProcessing();

        // schedule next event
        forecastGridlet();
    }

    /**
     * Handles an operation of canceling a Gridlet in either execution list
     * or paused list.
     * @param gridletId    a Gridlet ID
     * @param userId       the user or owner's ID of this Gridlet
     * @param an object of ResGridlet or <tt>null</tt> if this Gridlet is not
     *        found
     * @pre gridletId > 0
     * @pre userId > 0
     * @post $none
     */
    private ResGridlet cancel(int gridletId, int userId)
    {
        ResGridlet rgl = null;

        // Check whether the Gridlet is in execution list or not
        int found = super.findGridlet(gridletInExecList_, gridletId, userId);

        // if a Gridlet is in execution list
        if (found >= 0)
        {
            // update the gridlets in execution list up to this point in time
            updateGridletProcessing();

            // Get the Gridlet from the execution list
            rgl = (ResGridlet) gridletInExecList_.remove(found);

            // if a Gridlet is finished upon cancelling, then set it to success
            if (rgl.getRemainingGridletLength() == 0.0) {
                rgl.setGridletStatus(Gridlet.SUCCESS);
            }
            else {
                rgl.setGridletStatus(Gridlet.CANCELED);
            }

            // then forecast the next Gridlet to complete
            forecastGridlet();
        }

        // if a Gridlet is not in exec list, then find it in the paused list
        else
        {
            found = super.findGridlet(gridletPausedList_, gridletId, userId);

            // if a Gridlet is found in the paused list then remove it
            if (found >= 0)
            {
                rgl = (ResGridlet) gridletPausedList_.remove(found);
                rgl.setGridletStatus(Gridlet.CANCELED);
            }
        }

        return rgl;
    }

} // end class