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.
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. CurrentTask = which(AbsDeadline==min(AbsDeadline[WaitingList]));
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. CurrentTask = WaitingList[which.min(AbsDeadline[WaitingList])];
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. if(is.na(CurrentTask)) CurrentTask = WaitingList[which.min(AbsDeadline[WaitingList])];
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. CurrentTask = WaitingList[which.min(AbsDeadline[WaitingList]-(t+Remaining[WaitingList]))];
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:
Response Time (RT): the mean time that completed job spends in the system (in the queue and processing phases). Note that the average is only taken over the jobs that have been actually completed.
Missed Deadline Ratio (MDR): the proportion of dropped jobs, i.e., jobs that did not complete.
We implement these performance measures in our code.
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(NA, N); # Remaining service times of each job
Completion = rep(NA, N); # Completion time of each job
ExpectedTimetoCompletion = rep(NA, N);
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));
Remaining[AbsDeadline < t] = NA;
# Job arrival
if((NextArrival <=N) & (Arrival[NextArrival] == t)) {
Remaining[NextArrival] = Service[NextArrival];
ExpectedTimetoCompletion[NextArrival] = ES;
NextArrival = NextArrival + 1;
}
# Job departure
if(!is.na(CurrentTask)) {
Remaining[CurrentTask] = Remaining[CurrentTask] - dt;
ExpectedTimetoCompletion[CurrentTask] = ExpectedTimetoCompletion[CurrentTask] - dt;
if (!is.na(Remaining[CurrentTask]) && Remaining[CurrentTask] <= 0) {
Completion[CurrentTask] = t;
Remaining[CurrentTask] = NA;
CurrentTask = NA;
}
}
# Scheduling discipline: Let's find the new task to process
#HARD DEADLINES
WaitingList=(1:NextArrival)[!is.na(Remaining)];
# if the current job exceeds its deadline, we abandon it immediately
for (i in WaitingList){
if (t >= AbsDeadline[i]) {
if(!is.na(CurrentTask)){
if(i == CurrentTask){
CurrentTask = NA
}
}
Remaining[i] = NA
}
}
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 = WaitingList[which.min(Remaining[WaitingList])];
}
if (scheduling_discipline=="SRT2D"){
timetodeadline = AbsDeadline[WaitingList] - t - Remaining[WaitingList] # we don't verify that the job can be compute before the deadline (it's already done in the hard deadline verification)
CurrentTask = WaitingList[which.min(timetodeadline)];
}
if (scheduling_discipline=="SERT2D"){
CurrentTask = WaitingList[which.min(AbsDeadline[WaitingList] - t - ExpectedTimetoCompletion[WaitingList])]
}
}
if (debug==1){
print(paste("Current Task = ", CurrentTask))
# readline(prompt="Press [enter] to proceed")
}
} # while
#MDR=mean(Completion>AbsDeadline); # for soft deadlines
#STEP 2 Performance measures implementation
MDR = sum(is.na(Completion)) / length(Completion); # for hard deadlines: proportion of jobs that are NA
ResponseTime = mean(Completion[!is.na(Completion)] - Arrival[!is.na(Completion)]); # verify only the not NA jobs
AvgJobs=AvgJobs/(tail(Completion[!is.na(Completion)],n=1)-Arrival[1]); # verify only the not NA jobs
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;
cat(scheduling_discipline," completed.\n");
} # loop scheduling discipline
cat("\nResults of this simulation :\n")
print(Results)
} # end function
We take a scheduling discipline of our choice, here the random variable is uniform over [0,10] with probability 0.85 and and uniform over [90,110] with probability 0.15. Then, we simulate the dynamics induced by 10 arrivals.
knitr::opts_chunk$set(echo = FALSE)
set.seed(11);
N = 10
rho = 0.9
# 85% of the jobs have service times uniformly distributed between [0, 10],
# 15% of the jobs have service times uniformly distributed between [90, 110]
Service = c(
runif(round(0.85 * N), min = 0, max = 10), # 85% of jobs
runif(round(0.15 * N), min = 90, max = 110) # 15% of jobs
)
x = 5
Deadline = Service * x
ES = mean(Service) #expected service time (mean of service times)
lambda = lambda = rho * ES
mu = 1
results <- run_simulation(Service, ES, Deadline, rho)## Little law verification: 0.7215 =N=lambda*R= 1.3299
## FCFS completed.
## Little law verification: 0.9311 =N=lambda*R= 1.2753
## EDF completed.
## Little law verification: 0.7215 =N=lambda*R= 1.3299
## EDF-NP completed.
## Little law verification: 0.7186 =N=lambda*R= 1.198
## SRPT completed.
## Little law verification: 0.9311 =N=lambda*R= 1.2753
## SRT2D completed.
## Little law verification: 0.9311 =N=lambda*R= 1.2753
## SERT2D completed.
##
## Results of this simulation :
## RT MDR
## FCFS 32.81276 0.1
## EDF 31.46675 0.0
## EDF-NP 32.81276 0.1
## SRPT 29.55958 0.0
## SRT2D 31.46675 0.0
## SERT2D 31.46675 0.0cat("Job deadlines: ", Deadline, "\n")## Job deadlines: 13.86249 0.02591565 25.53042 0.7023954 3.234489 47.74246 4.324795 14.49875 538.0699 462.3216
Results with N=1e4
| Discipline | RT | MDR |
|---|---|---|
| FCFS | 6.780986 | 0.1699 |
| EDF | 6.187860 | 0.1492 |
| EDF-NP | 5.738338 | 0.9651 |
| SRPT | 12.856610 | 0.1176 |
| SRT2D | 5.956728 | 0.1500 |
| SERT2D | 6.000767 | 0.1499 |
The results show that SRPT minimizes the Missed Deadline Ratio (MDR)
(0.1176) but has the highest Response Time (RT) (12.86), making it
inefficient for timely processing. EDF and SRT2D offer a better balance,
with MDRs around 0.15 and lower RTs (6.19 and 5.96, respectively),
making them strong candidates for deadline-sensitive systems. FCFS has
moderate performance (RT = 6.78, MDR = 0.1699), while EDF-NP performs
worst with an extremely high MDR (0.9651) due to its non-preemptive
nature. SERT2D performs similarly to SRT2D, but has the advantage of
working without needing to know the remaining time, making it more
practical in situations where service times are uncertain. Overall, EDF
and SRT2D are the best choices for balancing deadline adherence and
response time.