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("FCFS",
"EDF",
"EDF-NP",
"SRPT",
"SRT2D",
"SERT2D");
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 = 2);
rownames(Results) <- scheduling_disciplines;
colnames(Results) <- c("RT", "MDR"); # performance metrics
# Poisson process coming in
Interarrival = rexp(N, rate = lambda); # Exponentially distributed interarrival times
Arrival= cumsum(Interarrival); # 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; Stores remaining service times for jobs in the queue.
ExpectedRemaining = rep(N, x=ES); # Expected Remaining service times of each job; Stores remaining service times for jobs in the queue.
Completion = rep(N, x=NA); # Completion time of each job, Stores completion times.
CurrentTask = NA; # Tracks the currently running job.
NextArrival = 1; # Index for the next arriving job.
AvgJobs = 0; # Tracks the average number of jobs in the system.
while (TRUE) {
if (debug==1){
print("*********************");
cat("InterArrival: ", Interarrival, '\n');
cat("Arrival: ",Arrival,'\n');
cat("AbsDeadline: ",AbsDeadline,'\n');
cat("Service: ",Service,'\n');
cat("Remaining: ",Remaining,'\n');
}
# Determine next event : continue running the same job or choose another
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=TRUE);
# 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;
ExpectedRemaining[CurrentTask] = ExpectedRemaining[CurrentTask] - dt;
if(Remaining[CurrentTask] == 0) {
# CurrentTask completed
Completion[CurrentTask] = t;
Remaining[CurrentTask] = NA;
CurrentTask = NA;
} else {
# CurrentTask rejected
if(Remaining[CurrentTask] + t > AbsDeadline[CurrentTask]) {
Completion[CurrentTask] = NA;
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("Simulation time: ", t));
print(paste("Different 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"){
CurrentTask = WaitingList[which.min(AbsDeadline[WaitingList])];
}
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=="SERT2D"){
CurrentTask = WaitingList[which.min(AbsDeadline[WaitingList]-(t+ExpectedRemaining[WaitingList]))];
}
}
if (debug==1){
print(paste("Current Task = ", CurrentTask))
# readline(prompt="Press [enter] to proceed")
}
} # while
## Step 2: Performance measures implementation
#MDR = sum(is.na(Completion))/length(Arrival);
MDR = mean(is.na(Completion))
ResponseTime = mean(Completion - Arrival, na.rm = TRUE)
#Average nulber of job in the system
AvgJobs = AvgJobs / (tail(Completion[!is.na(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;
cat(scheduling_discipline," completed.\n");
} # loop scheduling discipline
cat("\nResults:\n")
print(Results)
} # end function
Comments
If the goal is minimizing missed deadlines, EDF is the best scheduling discipline. If the goal is minimizing response time, SRPT is the best choice.