Main code
Here is the main R function that performs the simulation and print the results. (this code is heavily based on the code from TD #2 and #3)
knitr::opts_chunk$set(echo = TRUE)
set.seed(9999); # Set seed for reproducibility
# 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
# 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
ExpectedRemaining = rep(N,x=NA); # Expected remaining service time (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];
ExpectedRemaining[NextArrival] = ES;
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;
}
}
# Scheduling discipline: Let's find the new task to process
WaitingList=(1:NextArrival)[!is.na(Remaining)];
# Remove jobs from the system if they can't reach their deadline
for(Task in WaitingList) {
if(AbsDeadline[Task] <= t + Remaining[Task]) {
if(!is.na(CurrentTask) && Task == CurrentTask) {
CurrentTask = NA;
}
Remaining[Task] = 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) {
# STEP 1: Scheduling disciplines implementation
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=="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 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
# If our code is correct, Little's law should be verified:
# The average number of jobs in the system should be equal to lambda * R,
# Where R is the ResponseTime of the system.
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