Scheduling Program Assignment
Task 1: Non-preemptive scheduling
Write a scheduling program that implements one of these non-preemptive scheduling algorithms:
• FCFS (First Come, First Served)
• SPN (Shortest Process Next)
Task 2: Preemptive scheduling
Now, implement a second scheduling program according to the following preemptive algorithm:
• SRTN (Shortest Remaining Time Next) scheduling algorithm, with a time quantum of 3.
Task 3: Deadline-based scheduling
Now, implement a third scheduling program, which has the primary objective of maximizing the number of processes that meet their specified deadlines.
For this particular task, you should come up with your own algorithm, or implement any existing deadline-based scheduling algorithm you can find. Your algorithm can be either preemptive or non-preemptive.
Solution:
Task 1:
#include < stdio.h>
#include < unistd.h>
#include < stdlib.h>
#include < string.h>
#include < errno.h>
#include < libgen.h>
/* process state */
typedef enum {
READY, RUNNING, EXIT
} process_state_t;
/* process control block. */
typedef struct {
char process_name[11];
/* Times in seconds...*/
int entryTime;
int serviceTime;
int remainingTime;
int deadline;
int turnaroundTime;
int waitTime;
process_state_t state;
} pcb_t;
typedef enum {
True, False
} boolean;
/* Funtion declaration */
void First_Come_First_Served(pcb_t p[], int num_process);
int main(int argc, char *argv[])
{
FILE *file;
// open file
file = fopen("process-data.txt", "r");
if (argc > 1)
{
char *res = strdup(argv[1]);
if (strcmp(dirname(res),".") != 0)
{
if(access(argv[1], F_OK) == 0)
{
// exists
file = fopen(argv[1], "r");
}
else
{
// not exists [error]
write(2, strerror(errno), strlen(strerror(errno)));
exit(1);
}
}
// if it's valid filename instead of absolute path
else if(access(argv[1], F_OK) == 0)
{
file = fopen(argv[1], "r");
}
// if the argument res is not absolute path, show error
else
{
// not exists [error]
write(2, strerror(errno), strlen(strerror(errno)));
exit(1);
}
}
char processName[10];
int data;
int arrivalTime;
int serviceTime;
int deadline;
int num_process = 0;
pcb_t proc[10];
/* read each line from file */
data = fscanf(file,"%s %d %d %d", processName, &arrivalTime, &serviceTime, &deadline);
// loop
while (data != EOF)
{
pcb_t proc_data;
proc_data.entryTime = arrivalTime;
proc_data.serviceTime = serviceTime;
proc_data.remainingTime = serviceTime;
proc_data.deadline = deadline;
strcpy(proc_data.process_name,processName);
// append process control block into new array
proc[num_process] = proc_data;
num_process ++;
data = fscanf(file,"%s %d %d %d", processName, &arrivalTime, &serviceTime, &deadline);
}
fclose(file);
First_Come_First_Served(proc, num_process);
FILE *outputfile = fopen("scheduler-result.txt", "w");
if(outputfile == NULL)
{
printf("Invalid file");
return 1;
}
// loop the process to write it into outputfile
for (int i = 0; i < num_process; i++)
{
pcb_t processes = proc[i];
// check the deadlineMet
int deadlineMet;
if (processes.turnaroundTime <= processes.deadline)
{
deadlineMet = 1;
}
else
{
deadlineMet = 0;
}
fprintf(outputfile, "%s %d %d %d\n", processes.process_name, processes.waitTime, processes.turnaroundTime, deadlineMet);
}
fclose(outputfile);
return(0);
}
void First_Come_First_Served(pcb_t proc[], int num_process)
{
// capture the timer
int duration = 0;
boolean bool1;
bool1 = False;
int process_done = 0;
pcb_t *running;
pcb_t *tem_proc[10];
int head = 0;
// exit when all processes are done
while(process_done < num_process)
{
int i = 0;
while (i < num_process)
{
// retrieve each data of processes from proc_data by using pointer
pcb_t* processes = &proc[i];
// each processes will be in Ready state depend on their enterTime
if(processes->entryTime == duration)
{
fprintf(stdout, "Time %d: %s has entered the system.\n", duration, processes->process_name);
tem_proc[head] = processes;
head++;
processes->state = READY;
}
i++;
}
if(bool1 == True && running->remainingTime == 0)
{
running->turnaroundTime = duration - running->entryTime;
// WaitTime = turnaround - serviceTime
running->waitTime = running->turnaroundTime - running->serviceTime;
running->state = EXIT;
fprintf(stdout, "Time %d: %s has finished execution.\n", duration, running->process_name);
bool1 = False;
process_done++;
}
// no process is running, the next process will start running
if(bool1 == False && (running = tem_proc[process_done]))
{
if(process_done < num_process)
{
running->state = RUNNING;
fprintf(stdout, "Time %d: %s is in the running state.\n", duration, running->process_name);
bool1 = True;
}
}
duration++;
// decrement the remainingTime
if(running)
{
running->remainingTime--;
}
sleep(1);
}
}
Task 2:
#include < stdio.h>
#include < unistd.h>
#include < stdlib.h>
#include < string.h>
#include < errno.h>
#include < libgen.h>
typedef enum {
READY, RUNNING, EXIT
} process_state_t;
typedef struct {
char process_name[11];
int entryTime;
int serviceTime;
int remainingTime;
int deadline;
int turnaroundTime;
int waitTime;
process_state_t state;
} pcb_t;
typedef enum {
True, False
} boolean;
/* Funtion declaration */
void Round_Robin(pcb_t p[], int num_process);
int main(int argc, char *argv[])
{
FILE *file;
file = fopen("process-data.txt", "r");
if (argc > 1)
{
char *res = strdup(argv[1]);
if (strcmp(dirname(res),".") != 0)
{
if(access(argv[1], F_OK) == 0)
{
// exists
file = fopen(argv[1], "r");
}
else
{
// not exists [error]
write(2, strerror(errno), strlen(strerror(errno)));
exit(1);
}
}
// if it's filename instead of absolute path
else if(access(argv[1], F_OK) == 0)
{
file = fopen(argv[1], "r");
}
// if the argument res is not absolute path, show error
else
{
// not exists [error]
write(2, strerror(errno), strlen(strerror(errno)));
exit(1);
}
}
char processName[10];
int data;
int arrivalTime;
int serviceTime;
int deadline;
int num_process = 0;
pcb_t proc[10];
/* read each line from file */
data = fscanf(file,"%s %d %d %d", processName, &arrivalTime, &serviceTime, &deadline);
while (data != EOF)
{
pcb_t proc_data;
proc_data.entryTime = arrivalTime;
proc_data.serviceTime = serviceTime;
proc_data.remainingTime = serviceTime;
proc_data.deadline = deadline;
strcpy(proc_data.process_name,processName);
proc[num_process] = proc_data;
num_process ++;
data = fscanf(file,"%s %d %d %d", processName, &arrivalTime, &serviceTime, &deadline);
}
fclose(file);
// passing the process control block array and total number of processes into Round_Robin
Round_Robin(proc, num_process);
FILE *outputfile = fopen("scheduler-result2.txt", "w");
if(outputfile == NULL)
{
printf("Invalid file");
return 1;
}
// loop the process to write it into outputfile
for (int i = 0; i < num_process; i++)
{
pcb_t processes = proc[i];
// check the deadlineMet
int deadlineMet;
if (processes.turnaroundTime <= processes.deadline)
{
deadlineMet = 1;
}
else
{
deadlineMet = 0;
}
fprintf(outputfile, "%s %d %d %d\n", processes.process_name, processes.waitTime, processes.turnaroundTime, deadlineMet);
}
fclose(outputfile);
return(0);
}
void Round_Robin(pcb_t proc[], int num_process)
{
int duration = 0;
boolean bool1;
bool1 = False;
int process_done = 0;
pcb_t *running;
pcb_t *tem_proc[10];
int head = 0;
int quantum = 2;
int quantum_counter = 0;
int used_time = 0;
int tem_proc_counter=0;
// exit when all processes are done
while(process_done < num_process)
{
int i = 0;
while (i < num_process)
{
// retrieve each data of processes from proc_data by using pointer
pcb_t* processes = &proc[i];
if(processes->entryTime == duration)
{
fprintf(stdout, "Time %d: %s has entered the system.\n", duration, processes->process_name);
tem_proc[head] = processes;
head++;
tem_proc_counter ++;
processes->state = READY;
}
// increment loop
i++;
}
// process is running and its remaining time is 0, then exit the process
if(bool1 == True && running->remainingTime == 0)
{
// turnaround = completion - entryTime
running->turnaroundTime = duration - running->entryTime;
// WaitTime = turnaround - serviceTime
running->waitTime = running->turnaroundTime - running->serviceTime;
running->state = EXIT;
fprintf(stdout, "Time %d: %s has finished execution.\n", duration, running->process_name);
bool1 = False;
process_done++;
tem_proc_counter--;
quantum_counter ++;
used_time = 0;
}
else if(bool1 == True && used_time >= quantum && tem_proc_counter > 0)
{
tem_proc_counter++;
running->state = READY;
used_time = 0;
tem_proc[head] = running;
head++;
quantum_counter ++;
bool1 = False;
}
if(bool1 == False && (running = tem_proc[quantum_counter]))
{
tem_proc_counter--;
running->state = RUNNING;
fprintf(stdout, "Time %d: %s is in the running state.\n", duration, running->process_name);
bool1 = True;
}
if(running)
{
used_time++;
running->remainingTime--;
}
duration++;
sleep(1);
}
}
Task 3:
#include < stdio.h>
#include < unistd.h>
#include < stdlib.h>
#include < string.h>
#include < errno.h>
#include < libgen.h>
#include < limits.h>
/* process state */
typedef enum {
READY, RUNNING, EXIT
} process_state_t;
/* process control block*/
typedef struct {
char process_name[11];
int entryTime;
int serviceTime;
int remainingTime;
int deadline;
int turnaroundTime;
int waitTime;
process_state_t state;
} pcb_t;
void Earliest_Deadline_First(pcb_t p[], int num_process);
int main(int argc, char *argv[])
{
FILE *file;
file = fopen("process-data.txt", "r");
if (argc > 1)
{
char *res = strdup(argv[1]);
if (strcmp(dirname(res),".") != 0)
{
if(access(argv[1], F_OK) == 0)
{
// exists
file = fopen(argv[1], "r");
}
else
{
// not exists [error]
write(2, strerror(errno), strlen(strerror(errno)));
exit(1);
}
}
// if it's valid filename instead of absolute path
else if(access(argv[1], F_OK) == 0)
{
file = fopen(argv[1], "r");
}
// if the argument res is not absolute path, show error
else
{
// not exists [error]
write(2, strerror(errno), strlen(strerror(errno)));
exit(1);
}
}
char processName[10];
int data;
int arrivalTime;
int serviceTime;
int deadline;
int num_process = 0;
pcb_t proc[10];
/* read each line from file */
data = fscanf(file,"%s %d %d %d", processName, &arrivalTime, &serviceTime, &deadline);
while (data != EOF)
{
pcb_t proc_data;
proc_data.entryTime = arrivalTime;
proc_data.serviceTime = serviceTime;
proc_data.remainingTime = serviceTime;
proc_data.deadline = deadline;
strcpy(proc_data.process_name,processName);
proc[num_process] = proc_data;
num_process ++;
data = fscanf(file,"%s %d %d %d", processName, &arrivalTime, &serviceTime, &deadline);
}
fclose(file);
Earliest_Deadline_First(proc, num_process);
FILE *outputfile = fopen("scheduler-result3.txt", "w");
if(outputfile == NULL)
{
printf("Invalid file");
return 1;
}
// loop the process to write it into outputfile
for (int i = 0; i < num_process; i++)
{
pcb_t processes = proc[i];
// check the deadlineMet
int deadlineMet;
if (processes.turnaroundTime <= processes.deadline)
{
deadlineMet = 1;
}
else
{
deadlineMet = 0;
}
fprintf(outputfile, "%s %d %d %d\n", processes.process_name, processes.waitTime, processes.turnaroundTime, deadlineMet);
}
fclose(outputfile);
return(0);
}
void Earliest_Deadline_First(pcb_t proc[], int num_process)
{
int duration = 0;
int process_done = 0;
pcb_t *running;
pcb_t *tem_proc[10];
int min_deadline = INT_MAX;
int tem_proc_counter = 0;
int head = 0;
int process_enter = 0;
// exit when all processes are done
while(process_done < num_process)
{
int i = 0;
while (i < num_process)
{
// retrieve each data of processes from proc_data by using pointer
pcb_t* processes = &proc[i];
if(processes->entryTime == duration)
{
process_enter ++;
fprintf(stdout, "Time %d: %s has entered the system.\n", duration, processes->process_name);
processes->state = READY;
if (process_enter > 1 && processes->deadline < min_deadline)
{
tem_proc[head] = running;
head++;
tem_proc_counter ++;
running = processes;
min_deadline = processes->deadline;
running->state = RUNNING;
fprintf(stdout, "Time %d: %s is in the running state.\n", duration, running->process_name);
}
else if (process_enter > 1 && processes->deadline > min_deadline)
{
tem_proc[head] = processes;
head++;
tem_proc_counter ++;
processes->state = READY;
}
else if (processes->deadline < min_deadline)
{
running = processes;
min_deadline = processes->deadline;
running->state = RUNNING;
fprintf(stdout, "Time %d: %s is in the running state.\n", duration, running->process_name);
}
}
// increment loop
i++;
}
// running process remaining time is 0, then exit the process
if(running->remainingTime == 0)
{
// turnaround = completion - entryTime
running->turnaroundTime = duration - running->entryTime;
// WaitTime = turnaround - serviceTime
running->waitTime = running->turnaroundTime - running->serviceTime;
running->state = EXIT;
fprintf(stdout, "Time %d: %s has finished execution.\n", duration, running->process_name);
process_done++;
min_deadline = INT_MAX;
// check the tem_proc process array
for (int i = 0; i < tem_proc_counter; i++)
{
if(tem_proc[i]->remainingTime != 0 && tem_proc[i]->deadline < min_deadline)
{
running = tem_proc[i];
min_deadline = tem_proc[i]->deadline;
running->state = RUNNING;
}
}
if (running->remainingTime != 0){
fprintf(stdout, "Time %d: %s is in the running state.\n", duration, running->process_name);
}
}
duration++;
// decrement the remainingTime
if(running)
{
running->remainingTime--;
}
sleep(1);
}
}