Class CloudletSchedulerCompletelyFair

java.lang.Object
org.cloudsimplus.schedulers.cloudlet.CloudletSchedulerAbstract
org.cloudsimplus.schedulers.cloudlet.CloudletSchedulerTimeShared
org.cloudsimplus.schedulers.cloudlet.CloudletSchedulerCompletelyFair
All Implemented Interfaces:
Serializable, CloudletScheduler
public final class CloudletSchedulerCompletelyFair extends CloudletSchedulerTimeShared

A simplified implementation of the Completely Fair Scheduler (CFS) that is the default scheduler used for most tasks on recent Linux Kernel. It is a time-shared scheduler that shares CPU cores between running applications by preempting them after a time period (time-slice), allowing other apps to start executing during their time-slices.

This scheduler supposes that Cloudlets' priorities are in the range from [-20 to 19], as used in Linux Kernel. Despite setting priorities with values outside this interval will work as well, you have to realize that negative values indicate lower priorities.

Features

This is a basic implementation that covers the following features:

  • Defines a general run-queue (the waiting list which indicates which Cloudlets to run next) for all CPU cores (Pes) instead of one queue for each core. More details in the listing below.
  • Computes the process's (Cloudlet) niceness based on its priority: niceness = -priority. The nice value (niceness) defines how nice a process is to the other ones. Lower niceness (negative values) represents higher priority and consequently higher weight, while higher niceness (positive values) represents lower priority and lower weight.
  • Computes the process' time-slice based on its weight, that in turn is computed based on its niceness. The time-slice is the amount of time that a process is allowed to use the CPU, before being preempted to make room for other processes to run. The CFS scheduler uses a dynamic defined time-slice.

Limitations

This class currently DOES NOT implement the following features:

  • Additional overhead for CPU context switch: context switch is the process of removing an application that is using a CPU core to allow another one to start executing. This is the task preemption process that allows a core to be shared between several applications.
  • Since this scheduler does not consider context switch overhead, there is only one run-queue (waiting list) for all CPU cores, because each application is not in fact assigned to a specific CPU core. The scheduler just computes how much computing power (in MIPS) and number of cores each application can use. That MIPS capacity is multiplied by the number of cores the application requires. Such an approach enables the application to execute that number of instructions per second. Once the Pes do not in fact run the application, (application execution is simulated just computing the number of instructions that can be run), it doesn't matter which PEs are "running" the app.
  • It doesn't use a Red-Black tree (such as the TreeSet), as in real implementations of CFS, to sort waiting Cloudlets (run-queue list) increasingly, based on their virtual runtime (vruntime or VRT) (placing the Cloudlets that have run the least at the top of the tree). Furthermore, the use of such a data structure added some complexity to the implementation. Since different Cloudlets may have the same virtual runtime, this introduced some issues when adding or removing elements in a structure such as the TreeSet. That data structure requires each value (the virtual runtime in this case) used to sort the Set to be unique.

Notes

- The time interval for updating Cloudlets' execution in this scheduler is not primarily defined by the
[Datacenter#getSchedulingInterval()], but by the [timeslice][#computeCloudletTimeSlice(CloudletExecution)]
computed based on the defined [#getLatency()]. Each time the computed time-slice is greater than
the Datacenter scheduling interval, the next update of Cloudlets processing will follow
the [Datacenter#getSchedulingInterval()].
- The implementation was based on the book of Robert Love: Linux Kernel Development, 3rd ed. Addison-Wesley, 2010
and some other references listed below.
Since:
CloudSim Plus 1.0
Author:
Manoel Campos da Silva Filho
See Also:

  • Constructor Details

    • CloudletSchedulerCompletelyFair

      public CloudletSchedulerCompletelyFair()

  • Method Details

    • setLatency

      public void setLatency(int latency)
      Sets the latency time (in seconds).
      Parameters:
      latency - the latency to set
      Throws:
      IllegalArgumentException - when latency is lower than minimum granularity
      See Also:
      • invalid reference 
        #getLatency()

    • getCloudletWaitingList

      public List<CloudletExecution> getCloudletWaitingList()
      Returns a read-only list of Cloudlets which are waiting to run. This list is called run queue.

      NOTE: Different from real implementations, this scheduler uses just one run queue for all processor cores (PEs). Since CPU context switch is not concerned, there is no point in using different run queues.

      Specified by:
      getCloudletWaitingList in interface CloudletScheduler
      Overrides:
      getCloudletWaitingList in class CloudletSchedulerTimeShared
      Returns:
      a read-only list of Cloudlets which are waiting to run

    • findSuitableWaitingCloudlet

      protected Optional<CloudletExecution> findSuitableWaitingCloudlet()
      Try to find the first Cloudlet in the waiting list that the number of required PEs is not higher than the number of free PEs. The cloudlet waiting list (run queue) is sorted according to the virtual runtime (vruntime or VRT), which indicates the amount of time the Cloudlet has run. This runtime increases as the Cloudlet executes.
      Overrides:
      findSuitableWaitingCloudlet in class CloudletSchedulerAbstract
      Returns:
      an Optional containing the found Cloudlet or an empty Optional otherwise

    • setMinimumGranularity

      public void setMinimumGranularity(int minimumGranularity)
      Sets the minimum granularity that is the minimum amount of time (in seconds) that is assigned to each Cloudlet to execute.
      Parameters:
      minimumGranularity - the minimum granularity to set
      Throws:
      IllegalArgumentException - when minimum granularity is greater than latency

    • cloudletSubmitInternal

      protected double cloudletSubmitInternal(CloudletExecution cle, double fileTransferTime)
      Receives the execution information of a Cloudlet to be executed in the VM managed by this scheduler.

      It also sets the initial virtual runtime for the given Cloudlet to define how long the Cloudlet has executed already.
      See computeCloudletInitialVirtualRuntime(CloudletExecution) for more details.

      Overrides:
      cloudletSubmitInternal in class CloudletSchedulerAbstract
      Parameters:
      cle - the submitted cloudlet
      fileTransferTime - time required to move the required files from the SAN to the VM (in seconds)
      Returns:
      expected finish time of this cloudlet (considering the time to transfer required files from the Datacenter to the Vm), or 0 if it is in a waiting queue
      See Also:

    • updateProcessing

      public double updateProcessing(double currentTime, MipsShare mipsShare)
      Updates the processing of cloudlets inside the Vm running under management of this scheduler.
      Specified by:
      updateProcessing in interface CloudletScheduler
      Overrides:
      updateProcessing in class CloudletSchedulerAbstract
      Parameters:
      currentTime - current simulation time
      mipsShare - MIPS share of each Pe available to the scheduler
      Returns:
      the shorter time-slice assigned to the running cloudlets (which defines the time of the next expiring Cloudlet, enabling the preemption process), or Double.MAX_VALUE if there aren't next events

    • updateCloudletProcessing

      protected double updateCloudletProcessing(CloudletExecution cle, double currentTime)
      Description copied from class: CloudletSchedulerAbstract
      Updates the processing of a specific cloudlet from the Vm using this scheduler.
      Overrides:
      updateCloudletProcessing in class CloudletSchedulerAbstract
      Parameters:
      cle - the cloudlet to be its processing updated
      currentTime - current simulation time
      Returns:
      the next time to update the cloudlet processing (which is a relative delay from the current simulation time) This will be the delay incurred in cloudlet processing caused by (i) vMem usage or (ii) BW reduction due to oversubscription. If no delay is incurred, it returns the expected cloudlet completion time.

    • canExecuteCloudletInternal

      protected boolean canExecuteCloudletInternal(CloudletExecution cloudlet)
      Checks if a Cloudlet can be submitted to the execution list.

      This scheduler, different from its time-shared parent, only adds submitted Cloudlets to the execution list if there aren't enough free PEs. Otherwise, such Cloudlets are added to the waiting list, really enabling time-sharing between running Cloudlets. By this way, some Cloudlets have to be preempted to allow other ones to be executed.

      Overrides:
      canExecuteCloudletInternal in class CloudletSchedulerTimeShared
      Parameters:
      cloudlet - the Cloudlet that will be added to the execution list.
      Returns:
      always true to indicate that any submitted Cloudlet can be immediately added to the execution list
      See Also:
      • CloudletSchedulerAbstract.canExecuteCloudlet(CloudletExecution)

    • getCloudletExecList

      public List<CloudletExecution> getCloudletExecList()

      Prior to start executing, a Cloudlet is added to this list. When the Cloudlet vruntime reaches its time-slice (the amount of time it can use the CPU), it is removed from this list and added back to the getCloudletWaitingList().

      The sum of the PEs of Cloudlets into this list cannot exceed the number of PEs available for the scheduler. If the sum of PEs of such Cloudlets is less than the number of existing PEs, there are idle PEs. Since the CPU context switch overhead is not regarded in this implementation and as a result, it doesn't matter which PEs are running every Cloudlet, there is no such information anywhere. As an example, if the first Cloudlet requires 2 PEs, then one can say that it is using the first 2 PEs. But if at the next simulation time, the same Cloudlet is at the 3º position in this Collection, that indicates it's now using the 3º and 4º Pe, which doesn't change anything. In real schedulers, usually a process is pinned to a specific set of cores until it finishes executing, to avoid the overhead of changing processes from a run queue to another unnecessarily.

      Specified by:
      getCloudletExecList in interface CloudletScheduler
      Overrides:
      getCloudletExecList in class CloudletSchedulerAbstract
      Returns:

    • moveNextCloudletsFromWaitingToExecList

      protected double moveNextCloudletsFromWaitingToExecList(double currentTime)
      Checks which Cloudlets in the execution list have the virtual runtime equals to their allocated time slice and preempt them, getting the most priority Cloudlets in the waiting list (i.e., those at the beginning of the list).
      Overrides:
      moveNextCloudletsFromWaitingToExecList in class CloudletSchedulerAbstract
      Parameters:
      currentTime - current simulation time
      Returns:
      the next time to update the cloudlet processing (which is a relative delay from the current simulation time) This will be the delay incurred in cloudlet processing caused by (i) vMem usage or (ii) BW reduction due to oversubscription. If no delay is incurred, it returns the expected cloudlet completion time.
      See Also:
      • preemptExecCloudletsWithExpiredVRuntimeAndMoveToWaitingList()