The following scheduling disciplines are considered:
FCFS (First Come First Served): jobs are served in their order of arrival, this is the simplest discipline to implement because it does not manipulate any information concerning the jobs.
EDF (Earliest Deadline First): In this discipline, jobs are only processed based on a single piece of information: their deadline. The implementation of this discipline would therefore be quite simple, but it would lead to losses due to the multiple switching between jobs that could occur.
EDF-NP (Earliest Deadline First Non-preemptive): This discipline is the same as the previous one from an implementation point of view, however it will generate less loss due to switching between jobs because it is non-preemptive
SRT (Shortest Remaining Time): This discipline assigns the server to the job that has the least execution time remaining. It is preemptive and therefore generates switching costs. It also requires the system to know in advance the service time of each job. It cannot therefore be implemented if the service times of the jobs are not known in advance.
SRT2D (Shortest Remaining Time to Deadline): This discipline assigns the server to the job whose deadline would be closest to the end of its execution. It requires knowing two pieces of information about the jobs: service time and deadline, so it cannot be used in a situation where the service times of the jobs are not known in advance, but it allows reducing the number of “dropped jobs” it is also preemptive so it generates costs due to switching.
6 SERT2D (Shortest Expected Remaining Time to Deadline): This discipline is similar to the previous one, except that it is based on “Expected Remaining Time to Deadline” where its predecessor considered “Remaining Time to Deadline”, which makes it usable when we do not know the service times in advance.
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
set.seed(1); # Set seed for reproducibility
run_simulation <- function(Service, ES, Deadline, rho){
debug=0;
scheduling_disciplines = c("EDF",
"EDF-NP",
"SRT2D",
"SRPT",
"SERT2D",
"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 = 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
Completed = rep(N, x=0); # completed service times of each job, it will be use in only one discipline(SERT2D)
Queue = rep(N, x=NA); # queue of jobs in the server
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;
#
dtD = 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(CurrentTask)){ # if the CurrentTask expires
dtD = AbsDeadline[CurrentTask]-t; #time to the expiration if there is one
}
if(is.na(dtA) & is.na(dtC) & is.na(dtD)) { # break if there are no further events
break;
}
dt = min(dtA,dtC,dtD,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];
if(!is.na(CurrentTask)){
Remaining[CurrentTask] = Remaining[CurrentTask]-dt;
Completed[CurrentTask] = Completed[CurrentTask] + dt;
}
NextArrival = NextArrival + 1;
}
# Job expiration
if(!is.na(CurrentTask)){
if(AbsDeadline[CurrentTask]<=t ){
Completion[CurrentTask]= NA;
Completed[CurrentTask]=NA;
Remaining[CurrentTask]=NA;
CurrentTask=NA;
}
}
# Job departure
if(!is.na(CurrentTask)) {
Remaining[CurrentTask] = Remaining[CurrentTask] - dt;
Completed[CurrentTask] = Completed[CurrentTask] + dt;
if(Remaining[CurrentTask] <= 0) {
# CurrentTask completed
Completion[CurrentTask] = t;
Remaining[CurrentTask] = NA;
CurrentTask = NA;
}
}
#drop all the jobs who are already over their Deadlines
for (absDeadline in (1:NextArrival)[is.na(AbsDeadline)]) {
if(absDeadline<t){
Completion[wich(AbsDeadline==absDeadline)]= NA
Completed[wich(AbsDeadline==absDeadline)]= NA
Remaining[wich(AbsDeadline==absDeadline)]=NA;
AbsDeadline[wich(AbsDeadline==absDeadline)]=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"){
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"){
# in this discipline , we compute the expected remaining time to deadline, in this way:
# since AbsDedline = Arrival + Deadline and Deadline= Service*5 , the mean of AbsDeadline is 1/lamdba + 5*ES
# Remaining can be computed Service - Completed , so it mean is ES-Completed
# notice the comleted can not be NA,since its initial value is 0 and for expired job the remaining time is also # set to NA so they are not there in the waitinglist, then we don't need the "!is.na()" condition
CurrentTask = WaitingList[which.min(1/lambda +5*ES -(t+ES- Completed[WaitingList]))];
}
}
if (debug==1){
print(paste("Current Task = ", CurrentTask))
# readline(prompt="Press [enter] to proceed")
}
} # while
#Step 2
MDR=mean(is.na(Completion));# all the jobs who have a defined Completion dated had really completed and the others has expired
ResponseTime = mean(Completion - Arrival, na.rm = TRUE)
IDR=mean(Service>Deadline);
AvgJobs=AvgJobs/t; # Average number of job in the system is the weighted mean of each period
if (debug>=0){
cat(paste(" Little law verification: ", round(AvgJobs,digits = 4), "=N=lambda*R=",
round(lambda*ResponseTime,digits = 4),"\n")); # Little law verification, we verify that the average number of job in the system equals to response time times the arrival rate.
}
# 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
simuler_S <- function(n) { #this function simulates the service time of jobs, since we have this random variable , the ES(Expected Service time) equals 19.25
U <- runif(n) # Génère n nombres aléatoires entre 0 et 1
S <- ifelse(U <= 0.85,
runif(n, 0, 10), # Si U <= 0.85, S ~ U[0, 10]
runif(n, 90, 110)) # Sinon, S ~ U[90, 110]
return(S)
}In Step 3, 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. and deadlines are \(x=5\) times larger than service times.
knitr::opts_chunk$set(echo = FALSE)
#set.seed(9); # Set seed for reproducibility
N = 1e4; # number of jobs to simulate;
Service=simuler_S(N); # Service times
x=runif(N,3,7);
x=5;
Deadline=Service*x; # Relative deadlines
rho=0.9; # load
run_simulation(Service, 19.25, Deadline, rho);## Little law verification: 1.0444 =N=lambda*R= 1.0394
## EDF completed.
## Little law verification: 0.8663 =N=lambda*R= 0.8613
## EDF-NP completed.
## Little law verification: 1.1749 =N=lambda*R= 1.1692
## SRT2D completed.
## Little law verification: 1.005 =N=lambda*R= 0.976
## SRPT completed.
## Little law verification: 1.3353 =N=lambda*R= 1.2048
## SERT2D completed.
## Little law verification: 0.76 =N=lambda*R= 0.7207
## FCFS completed.
##
## Results:
## RT MDR
## EDF 22.23115 0.0000
## EDF-NP 18.42235 0.1310
## SRT2D 25.00800 0.0000
## SRPT 20.87497 0.0010
## SERT2D 25.76931 0.0193
## FCFS 15.41564 0.1508In view of the results obtained after simulation, we can conclude that in a situation where we know in advance the service times of the jobs the best discipline would be SRT2D. But if this is not the case, the best discipline would therefore be EDF if the priority is to lose as few jobs as possible and rather SERT2D if the priority is on the response time of the system