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",
"SRT2D",
# "EDF-SRPT-D",
"SRPT",
"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
# 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
ExpectedTimeToDeadline = rep(N, x=NA); #used for SERT2D
CurrentTask = NA;
NextArrival = 1;
AvgJobs = 0;
MDR =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];
ExpectedTimeToDeadline[NextArrival] = ES;
NextArrival = NextArrival + 1;
}
# Job departure
if(!is.na(CurrentTask)) {
Remaining[CurrentTask] = Remaining[CurrentTask] - dt;
ExpectedTimeToDeadline[CurrentTask] = ExpectedTimeToDeadline[CurrentTask] - dt;
if(!is.na(Remaining[CurrentTask]) && 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)];
# remove job if they have exceed their deadline
for (i in WaitingList) {
if (t > AbsDeadline[i]) {
if (!is.na(CurrentTask) && i == CurrentTask){
CurrentTask = NA;
}
Remaining[i] = NA;
MDR = MDR+ 1;
}
}
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 = WaitingList[which.min(Remaining[WaitingList])];
}
if (scheduling_discipline=="SRT2D"){
RemainingTimeToDeadline = AbsDeadline[WaitingList]- (t + Remaining[WaitingList]); # calcul le temps restant de tous les jobs
if (any(RemainingTimeToDeadline > 0)){ # on vérifie qu'il y en ai au moins 1 qui n'a pas vu sa deadline dépassé
CurrentTask = WaitingList[which.min(RemainingTimeToDeadline)]; # on choisit le plus petit
}else{
CurrentTask = NA;
}
}
if (scheduling_discipline=="SERT2D"){
CurrentTask = WaitingList[which.min(AbsDeadline[WaitingList]-(t+ExpectedTimeToDeadline[WaitingList]))];
}
}
if (debug==1){
print(paste("Current Task = ", CurrentTask))
# readline(prompt="Press [enter] to proceed")
}
} # while
########### STEP 2: Performance measures implementations
MDR = MDR/length(Arrival);
ResponseTime = mean((Completion-Arrival)[!is.na(Completion)]);
AvgJobs=AvgJobs/(tail(Completion[!is.na(Completion)],n=1)-Arrival[1]);
if (debug>=0){
########### STEP 3: Code correctness
# To check if our code is correct, we have the verification with the Little's law that should be verified
# The average number of jobs in the system should be equal to lambda * R (R is the ResponseTime),
cat(paste(" Little law verification: ", round(AvgJobs,digits = 4), "=N=lambda*R=",
round(lambda*ResponseTime,digits = 4),"\n"));
}
########### STEP 4: Performance evaluation (creation of the table)
# 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