The goal of this homework assignment is to simulate and analyze the dynamics of a G/G/1 queue under various scheduling disciplines, where jobs have hard deadlines. Specifically, each arriving job must be completed before its individual deadline. The deadline is considered “hard” because if it is not met, the job becomes useless and is consequently removed from the system
We consider the following scheduling disciplines:
FCFS: jobs are processed following the order of their arrival. If a job’s deadline expires while it is being processed, the job is removed from the system. The server does not know the service times in advance. Easiest to implement in real life.
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. The server does not know the service times in advance. Simple to implement in real situation. Provides good performance in practice.
EDF-NP (Earliest Deadline First Non-preemptive): As EDF but jobs are not interrupted once their processing has started. The server does not know the service times in advance. Simple to implement in real situation. Provides good performance in practice. Simpler than EDF Avoids context switch
SRPT (Shortest Remaining Processing Time): the job with the shortest remaining processing time is served first. Here, the jobs whose remaining processing times overflow their corresponding deadlines are not considered, i.e., removed from the system. Hard to know the remaining processing time in real life but optimal in theory.
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” is always non-negative because jobs that cannot be completed by the deadline are removed from the system. Hard to know the remaining processing time in real life.
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. The server does not know the service times in advance (but it knows their distribution function).
We are interested in comparing the performance of the previous scheduling disciplines with respect to:
• The arrival process is Poisson with rate λ. • Service times are all independent and have the distribution of the random variable S. The random variable S is uniform over [0,10] with probability 0.85 and and uniform over [90,110] with probability 0.15. • The deadline of any job is x = 5 times larger than its service time. • In the G/G/1 queue, it is assumed that the server processes jobs with speed one. • The system load ρ is 0.9.
• When a job is preempted, it resumes exactly where it left off.
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
# 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
ERemaining = rep(N, x=NA); # Expected 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');
cat("ERemaining: ",ERemaining,'\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];
ERemaining[NextArrival] = ES;
NextArrival = NextArrival + 1;
}
# Job departure
if(!is.na(CurrentTask)) {
Remaining[CurrentTask] = Remaining[CurrentTask] - dt;
ERemaining[CurrentTask] = ERemaining[CurrentTask] - dt;
if(Remaining[CurrentTask] <= 0) {
# CurrentTask completed
Completion[CurrentTask] = t;
Remaining[CurrentTask] = NA;
ERemaining[CurrentTask] = NA;
CurrentTask = NA;
}
}
# Hard deadlines
# for (i in 1:NextArrival) {
# if (!is.na(Remaining[i]) && !is.na(AbsDeadline[i]) && AbsDeadline[i] < (t + Remaining[i])) {
# if (!is.na(CurrentTask) && i == CurrentTask) {
# CurrentTask = NA
# }
# Remaining[i] = NA
# }
# }
WaitingList = which(!is.na(Remaining[1:NextArrival]))
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 (AbsDeadline[CurrentTask] < t + Remaining[CurrentTask]){
}
}
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"){
# Solution 1
# CurrentTask = which(AbsDeadline==min(AbsDeadline[WaitingList]));
# Solution 2
if(is.na(CurrentTask)){
CurrentTask = WaitingList[which.min(AbsDeadline[WaitingList])];
# cat(CurrentTask, " while FCFS says ", head(WaitingList,n=1), '\n');
}
}
if(scheduling_discipline=="SRPT"){
CurrentTask = WaitingList[which.min(Remaining[WaitingList])];
}
if (scheduling_discipline=="SRT2D"){
CurrentTask = WaitingList[which.min(AbsDeadline[WaitingList] - t + Remaining[WaitingList])];
}
if (scheduling_discipline=="SERT2D"){
CurrentTask = WaitingList[which.min(AbsDeadline[WaitingList] - (t + ERemaining[WaitingList]))];
}
}
if (debug==1){
print(paste("Current Task = ", CurrentTask))
# readline(prompt="Press [enter] to proceed")
}
} # while
MDR=mean(Completion>AbsDeadline);
ResponseTime = mean(Completion-Arrival);
AvgJobs=AvgJobs/(tail(Completion,n=1)-Arrival[1]);
if (debug==1){
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 function10 jobs
knitr::opts_chunk$set(echo = FALSE)
set.seed(9); # Set seed for reproducibility
N = 10; # number of jobs to simulate;
Service = rep(N,x=NA);
for (i in 1:N) {
if (runif(1) < 0.85) {
Service[i] = runif(1, 0, 10)
} else {
Service[i] = runif(1, 90, 110)
}
}
ES=((0+10)/2)*0.85+((90+110)/2)*0.15;
x=5; Deadline=Service*x; # Relative deadlines
rho=0.9; # load
run_simulation(Service, ES, Deadline, rho);## FCFS completed.
## EDF completed.
## EDF-NP completed.
## SRPT completed.
## SRT2D completed.
## SERT2D completed.
##
## Results:
## RT MDR
## FCFS 29.71550 0.3
## EDF 15.84836 0.0
## EDF-NP 29.23008 0.3
## SRPT 15.84836 0.0
## SRT2D 15.84836 0.0
## SERT2D 15.84836 0.01e4 jobs
## FCFS completed.
## EDF completed.
## EDF-NP completed.
## SRPT completed.
## SRT2D completed.
## SERT2D completed.
##
## Results:
## RT MDR
## FCFS 318.45957 0.7747
## EDF 142.36501 0.3205
## EDF-NP 163.91695 0.6979
## SRPT 75.57376 0.0254
## SRT2D 125.73731 0.2809
## SERT2D 141.30069 0.3027