Processing math: 100%

Problem statement

The aim of this session is to be able to simulate and compare the dynamics of a G/G/1 queue adopting a number of scheduling disciplines and where jobs have soft deadlines. Specifically, when a job arrives, it should be completed before a deadline that is specific to the job. The deadline is “soft” in the sense it may not be respected, though this wold imply some penalty.

We consider the following scheduling disciplines:

  1. FCFS (First Come First Served): jobs are processed following the order of their arrival

  2. EDF (Earliest Deadline First): jobs are processed according to the earliest deadline with preemption, i.e., the current job is interrupted if a new job with an earlier deadline arrives.

  3. EDF-NP (Earliest Deadline First Non-preemptive): As EDF but jobs are not interrupted once their processing has started.

We are interested in comparing the performance of the previous scheduling disciplines with respect to:

  1. Response Time (RT): the mean time that a job spends in the system (in the queue and processing phases).

  2. Missed Deadline Ratio (MDR): the proportion of jobs that completed after their declared deadline.

  3. Impossible Deadline Ratio (IDR): the proportion of jobs that declared an impossible deadline, i.e., no discipline can fulfill the deadline requirement in any scenario. This is the case of a job whose service time is larger than its declared deadline.

Towards this purpose, the objective is to create a table of the form:

Discipline RT MDR IDR
FCFS
EDF
EDF-NP

We will rely on this table to comment on the results.

Parameter settings

We will consider two parameter settings, referred to as Scenarios 1 and 2. Specifically,

  1. in Scenario 1, assume that service times are exponentially distributed (with rate, say, μ) and deadlines are x=5 times larger than service times. In this case, note that IDR=0.

  2. in Scenario 2, assume that service times are exponentially distributed (with rate, say, μ) and deadlines are also exponentially distributed with rate γ=μ/5. Also, deadlines are independent random variables.

In both scenarios, assume a Poisson arrival process, i.e., job interarrival times are independent and exponentially distributed with rate, say, λ. The rate λ is such that the system load ρ=λ/μ is 0.9.

Hints

Adapt the code for the simulation of the G/G/1 queue.

The R function which.min(v) returns the index of the minimum element in vector v.

Main code

Here is the main R function that performs the simulation and print the results.

knitr::opts_chunk$set(echo = TRUE)

# This function performs the required simulation.
# As input, it takes the job service times (Service), their expected value (ES), the job deadlines (relative to the absolute job arrival time), and the system load
run_simulation <- function(Service, ES, Deadline, rho){
    debug=0;
    scheduling_disciplines = c("EDF",
                               "EDF-NP",
                               "SRT2D",
                               # "EDF-SRPT-D",
                               # "SRPT",
                               "FCFS");
    num_arrival_rates=1;
    lambda = rho/ES;
    
    # Matrix of average response times for all disciplines and arrival rates
    Results <- matrix(0, nrow = length(scheduling_disciplines), ncol = 3);
    rownames(Results) <- scheduling_disciplines;
    colnames(Results) <- c("RT", "MDR", "IDR"); # performance metrics
    
    # Let's assume a Poisson process coming in, otherwise change the next line
    Arrival= cumsum(rexp(n=N, rate = lambda)); # Arrival times
    AbsDeadline = Arrival+Deadline;
    
    for (scheduling_discipline in scheduling_disciplines)
    {
        t = 0; # simulation time
        Remaining = rep(N, x=NA);    # Remaining service times of each job
        Completion = rep(N, x=NA);   # Completion time of each job
        
        CurrentTask = NA;
        NextArrival = 1;
        AvgJobs = 0;
        while (TRUE) {

if (debug==1){
    print("*********************");
    cat("Arrival:     ",Arrival,'\n');
    cat("AbsDeadline: ",AbsDeadline,'\n');
    cat("Service:     ",Service,'\n');
    cat("Remaining:   ",Remaining,'\n');
}
            dtA = NA; dtC = NA;
            if(length(Arrival[Arrival>t])>0) { # if an arrival exists after t
                dtA = head(Arrival[Arrival>t],n=1)-t ; # time to next arrival
            }
            if(!is.na(CurrentTask)) { # if a task is running
                dtC = Remaining[CurrentTask]; # time to next completion
            }
            if(is.na(dtA) & is.na(dtC)) {
                break;
            } 
        
            dt = min(dtA,dtC,na.rm=T);
        
            # update system variables
            t = t + dt;
            AvgJobs=AvgJobs+dt*sum(!is.na(Remaining));
            
            # Job arrival
            if((NextArrival <=N) & (Arrival[NextArrival] == t)) {
                Remaining[NextArrival] = Service[NextArrival];
                NextArrival = NextArrival + 1;
            }
        
            # Job departure
            if(!is.na(CurrentTask)) {
                Remaining[CurrentTask] = Remaining[CurrentTask] - dt;
                if(Remaining[CurrentTask] <= 0) {
                    # CurrentTask completed
                    Completion[CurrentTask] = t;
                    Remaining[CurrentTask] = NA;
                    CurrentTask = NA;
                }
            }
            
            # Scheduling discipline: Let's find the new task to process
            
            WaitingList=(1:NextArrival)[!is.na(Remaining)];
            
if (debug==1){
    print(paste("Sim. time:", t));
    print(paste("# of jobs arrived: ", NextArrival));
    cat("WaitingList:", WaitingList, "\n");
}
            if(length(WaitingList)>0) {
        
              if (scheduling_discipline=="FCFS"){
                CurrentTask = head(WaitingList,n=1);
              }
              
              if (scheduling_discipline=="EDF"){
                 # Solution 1
                 # CurrentTask = which(AbsDeadline==min(AbsDeadline[WaitingList]));
                 # Solution 2
                  CurrentTask = WaitingList[which.min(AbsDeadline[WaitingList])];
                 # cat(CurrentTask, " while FCFS says ", head(WaitingList,n=1), '\n');
              }
        
              if (scheduling_discipline=="EDF-NP"){
                  if (is.na(CurrentTask)) {
                    CurrentTask = WaitingList[which.min(AbsDeadline[WaitingList])];
                  }
              }

              if (scheduling_discipline=="SRPT"){
                    CurrentTask = which.min(Remaining);
              }
                
              if (scheduling_discipline=="SRT2D"){
                    CurrentTask = WaitingList[which.min(AbsDeadline[WaitingList]-(t+Remaining[WaitingList]))];
              }
                
              if (scheduling_discipline=="EDF-SRPT-D"){
                  # Set a value for Delta
                  # Select the waiting jobs that have absolute deadline prior to t+Delta, say Waiting_Delta
                  # As CurrentTask, choose the job with the shortest remaining processing time in Waiting_Delta.
              }

            }
    
if (debug==1){
    print(paste("Current Task = ", CurrentTask))
    #    readline(prompt="Press [enter] to proceed")
}
        
    } # while
    
        IDR=mean(Service>Deadline);
        MDR=mean(Completion>AbsDeadline);
        ResponseTime = mean(Completion-Arrival); 
        AvgJobs=AvgJobs/(tail(Completion,n=1)-Arrival[1]);

if (debug>=0){
    cat(paste(" Little law verification: ", round(AvgJobs,digits = 4), "=N=lambda*R=", 
              round(lambda*ResponseTime,digits = 4),"\n"));
}        
        
        # Simulation completed.
        
        Results[scheduling_discipline,1]=ResponseTime;
        Results[scheduling_discipline,2]=MDR;
        Results[scheduling_discipline,3]=IDR;
        
        cat(scheduling_discipline," completed.\n");
    
    } # loop scheduling discipline
    
    cat("\nResults:\n")
    print(Results)
    
} # end function

Scenario 1

In Scenario 1, service times are exponentially distributed with rate μ and deadlines are x=5 times larger than service times.

knitr::opts_chunk$set(echo = FALSE)

set.seed(9); # Set seed for reproducibility

N = 1e4; # number of jobs to simulate;

mu=1; Service=rexp(N,rate=mu); # Service times
x=runif(N,3,7);  
x=5;
Deadline=Service*x; # Relative deadlines

rho=0.9; # load
run_simulation(Service, 1/mu, Deadline, rho);
##  Little law verification:  6.0314 =N=lambda*R= 6.0576 
## EDF  completed.
##  Little law verification:  6.3218 =N=lambda*R= 6.3498 
## EDF-NP  completed.
##  Little law verification:  6.4466 =N=lambda*R= 6.4746 
## SRT2D  completed.
##  Little law verification:  8.6699 =N=lambda*R= 8.7084 
## FCFS  completed.
## 
## Results:
##              RT    MDR IDR
## EDF    6.730648 0.3074   0
## EDF-NP 7.055352 0.4526   0
## SRT2D  7.193988 0.3387   0
## FCFS   9.675979 0.6111   0

In view of the results obtained after several runs (with different seeds), EDF seems to provide the best performance in terms of all three performance indicators. This is confirmed also with respect to “perturbed” version of the scenario, where the factor x is replaced by a random variable uniformly distributed over [3,7] and/or the system load ρ changes.

Scenario 2

In Scenario 2, service times are exponentially distributed with rate μ, and deadlines are independent and exponentially distributed with rate γ=μ/5.

##  Little law verification:  9.1837 =N=lambda*R= 9.3221 
## EDF  completed.
##  Little law verification:  9.196 =N=lambda*R= 9.3346 
## EDF-NP  completed.
##  Little law verification:  9.7769 =N=lambda*R= 9.9238 
## SRT2D  completed.
##  Little law verification:  9.2138 =N=lambda*R= 9.3538 
## FCFS  completed.
## 
## Results:
##              RT    MDR    IDR
## EDF    10.35786 0.6822 0.1648
## EDF-NP 10.37177 0.6994 0.1648
## SRT2D  11.02641 0.7131 0.1648
## FCFS   10.39316 0.6728 0.1648

In this scenario, we find that all three scheduling disciplines perform equivalently well. Therefore, we may opt for FCFS as this scheduling discipline is fairer and does not incur preemption costs.

New scheduling disciplines

Let’s think about new scheduling disciplines that may improve over EDF. After discussion in class, the following disciplines have been proposed:

  1. SRPT (Shortest Remaining Processing Time): the job with the shortest remaining processing time is served first.

  2. SRT2D (Shortest Remaining Time to Deadline): the job with the shortest remaining time to deadline is served first. Note that “the remaining time to deadline” may assume a negative value. This occurs at time t if a job with absolute deadline prior to t exists.

  3. SERT2D (Shortest Expected Remaining Time to Deadline): as SRT2D but instead of the remaining time to deadline, we consider the expected remaining time to deadline.

  4. EDF-SRPT-Δ: with Δ>0, this scheduling discipline chooses at time t the job with the shortest remaining processing time among the jobs that have absolute deadlines belonging to the interval [t,t+Δ].

  5. EDF-SERPT-Δ: with Δ>0, this scheduling discipline chooses at time t the job with the shortest expected remaining processing time among the jobs that have absolute deadlines belonging to the interval [t,t+Δ].

Now, code these disciplines and then run simulations to evaluate their performance.