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