Shortest Job First with Preemption in C
Before proceeding forward , lets talk about data structures which i have used in this program.
1. I have created a structure Process.
2. I have implemented a Job Pool of process via array of structure type Process which also used for input.
3. Ready Queue implemented through linked list. enqueue and dequeue function for ready queue.
4. Load_ReadyQueue function which load Process from job pool to ready queue.
5. MinInQueue is function to find the process in ReadyQueue having minimum reaming cpu burst time. ** Note that this function store the the address of that minimum process in the min , which is pointer to the Process.
6. CPU is where process is actually allocated , Data structure used for CPU is struct Process.
Procedure is straight forward
Run the loop for total sum of CPUBURST of all the process
Load the ready queue for every value of loop
IF (CPU is empty) Then allocate process from the Ready Queue having minimum cpu burst
IF( current running process in CPU have greater remaining cpu burst than process residing in ready queue) Then swap the processes and allocate new process to CPU.
IF two process having same remaining cpu burst time then First come first serve is used for deciding the process.
IF( current process in CPU have completed its total cpu bound) then deallocate the CPU , and also free the pointer that pointing to address of that particular process.
** Note dynamic memory have to freed
Continue these steps util all process have completed their cpu bound.
For simulation of process scheduling , check my process scheduling simulator in Java.
Source Code:-
#include <stdio.h>
#include <stdlib.h>
struct Process{
int job_id;
int arrival_time;
int cpu_burst;
int reaming_time;
int waiting_time;
int turnaround_time;
int response_time;
int lastresponse_time;
};
struct Process job_queue[10];
struct Process CPU;
struct Process temp_process;
struct Node{
struct Process process;
struct Node *link;
}*head,*tail,*temp,*ptr,*min,*minLink;
// Global functions
void enqueue(struct Process p);
void MinInQueue();
void load_ReadyQueue(int var);
// Global variable
int n,t=0;
double sum=0,sum2=0;
double avg_time,avg_turnTime;
int main()
{
int i,j; // n->no. of process
int loop_time;
printf("\tSHORTEST REMAING TIME FIRST SCHEDULING\n");
printf("\t ENTER NO. OF PROCESS\t=\t");
scanf("%d",&n);
printf("\n\t JOB_ID|ARRIVAL TIME|CPU BURST \n");
printf("\t ------------------------------\n");
for(i=0;i<n;i++){
printf("\t %d\t\t",i+1);
scanf("\t%d\t\t\t \t",&job_queue[i].arrival_time);
scanf("\t %d",&job_queue[i].cpu_burst);
job_queue[i].job_id=i+1;
job_queue[i].reaming_time=job_queue[i].cpu_burst;
t=t+job_queue[i].cpu_burst;
}
for(j=0;j<t;j++){
load_ReadyQueue(j);
if(CPU.reaming_time==0){
MinInQueue();
if(min==NULL){
printf("|IDLE|");
}else{
CPU=min->process;
CPU.lastresponse_time=j;
if(CPU.cpu_burst==CPU.reaming_time){
CPU.response_time=j;
}
if(min==head && min==tail){
head=NULL;
tail=NULL;
free(min);
}else if(min==head && min!=tail){
head=min->link;
free(min);
}else if(min==tail && min!=head){
minLink=head;
ptr=head;
while(ptr->link!=NULL){
minLink=ptr;
ptr=ptr->link;
}
tail=minLink;
minLink->link=NULL;
free(min);
minLink=NULL;
}else if(min!=head && min!=tail){
minLink=head;
ptr=head;
while(ptr->link!=min){
minLink=ptr;
ptr=ptr->link;
}
minLink->link=min->link;
free(min);
minLink=NULL;
}
CPU.reaming_time--;
printf("|JOB_ID%d|",CPU.job_id);
//min=NULL;
}
}else if(CPU.reaming_time>0){
MinInQueue();
if(min!=NULL && min->process.reaming_time < CPU.reaming_time){
if(min==head && min==tail){
temp_process=CPU;
head=NULL;
tail=NULL;
CPU=min->process;
CPU.lastresponse_time=j;
if(CPU.cpu_burst==CPU.reaming_time){
CPU.response_time=j;
}
CPU.reaming_time--;
printf("|JOB_ID%d|",CPU.job_id);
free(min);
enqueue(temp_process);
}else if(min==head && min!=tail){
temp_process=CPU;
head=min->link;
CPU=min->process;
CPU.lastresponse_time=j;
if(CPU.response_time==0){
CPU.response_time=j;
}
CPU.reaming_time--;
printf("|JOB_ID%d|",CPU.job_id);
free(min);
enqueue(temp_process);
}else if(min!=head && min==tail){
minLink=head;
ptr=head;
while(ptr->link!=NULL){
minLink=ptr;
ptr=ptr->link;
}
temp_process=CPU;
CPU=min->process;
CPU.lastresponse_time=j;
if(CPU.cpu_burst==CPU.reaming_time){
CPU.response_time=j;
}
tail=minLink;
minLink->link=NULL;
CPU.reaming_time--;
printf("|JOB_ID%d|",CPU.job_id);
free(min);
enqueue(temp_process);
}else{
minLink=head;
ptr=head;
while(ptr->link!=min){
minLink=ptr;
ptr=ptr->link;
}
temp_process=CPU;
CPU=min->process;
CPU.lastresponse_time=j;
if(CPU.cpu_burst==CPU.reaming_time){
CPU.response_time=j;
}
minLink->link=min->link;
CPU.reaming_time--;
printf("|JOB_ID%d|",CPU.job_id);
free(min);
enqueue(temp_process);
}
}else{
CPU.reaming_time--;
printf("|JOB_ID%d|",CPU.job_id);
}
}
if(CPU.reaming_time==0){
job_queue[CPU.job_id-1].turnaround_time=j-job_queue[CPU.job_id-1].arrival_time+1;
job_queue[CPU.job_id-1].waiting_time=job_queue[CPU.job_id-1].turnaround_time-job_queue[CPU.job_id-1].cpu_burst;
job_queue[CPU.job_id-1].response_time=CPU.response_time;
job_queue[CPU.job_id-1].lastresponse_time=CPU.lastresponse_time;
}
}
printf("\n----------------------------------------------------------------------------------------------\n");
printf("\t JOB_ID | Waitting Time | TurnAround Time | First Response Time | Last Response Time\n");
for(i=0;i<n;i++){
printf("\t %d",job_queue[i].job_id);
printf("\t \t%d",job_queue[i].waiting_time);
printf("\t %d",job_queue[i].turnaround_time);
printf("\t\t %d",job_queue[i].response_time);
printf("\t\t\t %d",job_queue[i].lastresponse_time);
printf("\n");
sum=sum+job_queue[i].waiting_time;
sum2=sum2+job_queue[i].turnaround_time;
}
avg_time=sum/n;
avg_turnTime=sum2/n;
printf("\n\n AVG. WAITING TIME=%lf",avg_time);
printf("\n\n AVG. TURN AROUND TIME=%lf",avg_turnTime);
printf("\n");
return 0;
}
// Function definition
void enqueue(struct Process p){
// if no element is present
if(tail==NULL){
temp=(struct Node *)malloc(1*sizeof(struct Node));
temp->link=NULL;
temp->process=p;
head=temp;
tail=head;
}else{
temp = (struct Node *)malloc(1*sizeof(struct Node));
tail->link=temp;
temp->process=p;
temp->link=NULL;
tail=temp;
}
}
void MinInQueue()
{
ptr=head;
if(ptr==NULL){
min=NULL;
return;
}
min = head;
for (ptr=ptr->link;ptr!=NULL;ptr=ptr->link)
{
if(ptr->process.reaming_time < min->process.reaming_time){
min=ptr;
}else if(ptr->process.reaming_time==min->process.reaming_time){
if(ptr->process.job_id < min->process.job_id){
min=ptr;
}
}else {
}
}
}
load_ReadyQueue(int var){
int i; // i-> local loop variable
for(i=0;i<n;i++){
if(job_queue[i].arrival_time==var){
enqueue(job_queue[i]);
}
}
}
IF( current running process in CPU have greater remaining cpu burst than process residing in ready queue) Then swap the processes and allocate new process to CPU.
IF two process having same remaining cpu burst time then First come first serve is used for deciding the process.
IF( current process in CPU have completed its total cpu bound) then deallocate the CPU , and also free the pointer that pointing to address of that particular process.
** Note dynamic memory have to freed
Continue these steps util all process have completed their cpu bound.
For simulation of process scheduling , check my process scheduling simulator in Java.
Source Code:-
#include <stdio.h>
#include <stdlib.h>
struct Process{
int job_id;
int arrival_time;
int cpu_burst;
int reaming_time;
int waiting_time;
int turnaround_time;
int response_time;
int lastresponse_time;
};
struct Process job_queue[10];
struct Process CPU;
struct Process temp_process;
struct Node{
struct Process process;
struct Node *link;
}*head,*tail,*temp,*ptr,*min,*minLink;
// Global functions
void enqueue(struct Process p);
void MinInQueue();
void load_ReadyQueue(int var);
// Global variable
int n,t=0;
double sum=0,sum2=0;
double avg_time,avg_turnTime;
int main()
{
int i,j; // n->no. of process
int loop_time;
printf("\tSHORTEST REMAING TIME FIRST SCHEDULING\n");
printf("\t ENTER NO. OF PROCESS\t=\t");
scanf("%d",&n);
printf("\n\t JOB_ID|ARRIVAL TIME|CPU BURST \n");
printf("\t ------------------------------\n");
for(i=0;i<n;i++){
printf("\t %d\t\t",i+1);
scanf("\t%d\t\t\t \t",&job_queue[i].arrival_time);
scanf("\t %d",&job_queue[i].cpu_burst);
job_queue[i].job_id=i+1;
job_queue[i].reaming_time=job_queue[i].cpu_burst;
t=t+job_queue[i].cpu_burst;
}
for(j=0;j<t;j++){
load_ReadyQueue(j);
if(CPU.reaming_time==0){
MinInQueue();
if(min==NULL){
printf("|IDLE|");
}else{
CPU=min->process;
CPU.lastresponse_time=j;
if(CPU.cpu_burst==CPU.reaming_time){
CPU.response_time=j;
}
if(min==head && min==tail){
head=NULL;
tail=NULL;
free(min);
}else if(min==head && min!=tail){
head=min->link;
free(min);
}else if(min==tail && min!=head){
minLink=head;
ptr=head;
while(ptr->link!=NULL){
minLink=ptr;
ptr=ptr->link;
}
tail=minLink;
minLink->link=NULL;
free(min);
minLink=NULL;
}else if(min!=head && min!=tail){
minLink=head;
ptr=head;
while(ptr->link!=min){
minLink=ptr;
ptr=ptr->link;
}
minLink->link=min->link;
free(min);
minLink=NULL;
}
CPU.reaming_time--;
printf("|JOB_ID%d|",CPU.job_id);
//min=NULL;
}
}else if(CPU.reaming_time>0){
MinInQueue();
if(min!=NULL && min->process.reaming_time < CPU.reaming_time){
if(min==head && min==tail){
temp_process=CPU;
head=NULL;
tail=NULL;
CPU=min->process;
CPU.lastresponse_time=j;
if(CPU.cpu_burst==CPU.reaming_time){
CPU.response_time=j;
}
CPU.reaming_time--;
printf("|JOB_ID%d|",CPU.job_id);
free(min);
enqueue(temp_process);
}else if(min==head && min!=tail){
temp_process=CPU;
head=min->link;
CPU=min->process;
CPU.lastresponse_time=j;
if(CPU.response_time==0){
CPU.response_time=j;
}
CPU.reaming_time--;
printf("|JOB_ID%d|",CPU.job_id);
free(min);
enqueue(temp_process);
}else if(min!=head && min==tail){
minLink=head;
ptr=head;
while(ptr->link!=NULL){
minLink=ptr;
ptr=ptr->link;
}
temp_process=CPU;
CPU=min->process;
CPU.lastresponse_time=j;
if(CPU.cpu_burst==CPU.reaming_time){
CPU.response_time=j;
}
tail=minLink;
minLink->link=NULL;
CPU.reaming_time--;
printf("|JOB_ID%d|",CPU.job_id);
free(min);
enqueue(temp_process);
}else{
minLink=head;
ptr=head;
while(ptr->link!=min){
minLink=ptr;
ptr=ptr->link;
}
temp_process=CPU;
CPU=min->process;
CPU.lastresponse_time=j;
if(CPU.cpu_burst==CPU.reaming_time){
CPU.response_time=j;
}
minLink->link=min->link;
CPU.reaming_time--;
printf("|JOB_ID%d|",CPU.job_id);
free(min);
enqueue(temp_process);
}
}else{
CPU.reaming_time--;
printf("|JOB_ID%d|",CPU.job_id);
}
}
if(CPU.reaming_time==0){
job_queue[CPU.job_id-1].turnaround_time=j-job_queue[CPU.job_id-1].arrival_time+1;
job_queue[CPU.job_id-1].waiting_time=job_queue[CPU.job_id-1].turnaround_time-job_queue[CPU.job_id-1].cpu_burst;
job_queue[CPU.job_id-1].response_time=CPU.response_time;
job_queue[CPU.job_id-1].lastresponse_time=CPU.lastresponse_time;
}
}
printf("\n----------------------------------------------------------------------------------------------\n");
printf("\t JOB_ID | Waitting Time | TurnAround Time | First Response Time | Last Response Time\n");
for(i=0;i<n;i++){
printf("\t %d",job_queue[i].job_id);
printf("\t \t%d",job_queue[i].waiting_time);
printf("\t %d",job_queue[i].turnaround_time);
printf("\t\t %d",job_queue[i].response_time);
printf("\t\t\t %d",job_queue[i].lastresponse_time);
printf("\n");
sum=sum+job_queue[i].waiting_time;
sum2=sum2+job_queue[i].turnaround_time;
}
avg_time=sum/n;
avg_turnTime=sum2/n;
printf("\n\n AVG. WAITING TIME=%lf",avg_time);
printf("\n\n AVG. TURN AROUND TIME=%lf",avg_turnTime);
printf("\n");
return 0;
}
// Function definition
void enqueue(struct Process p){
// if no element is present
if(tail==NULL){
temp=(struct Node *)malloc(1*sizeof(struct Node));
temp->link=NULL;
temp->process=p;
head=temp;
tail=head;
}else{
temp = (struct Node *)malloc(1*sizeof(struct Node));
tail->link=temp;
temp->process=p;
temp->link=NULL;
tail=temp;
}
}
void MinInQueue()
{
ptr=head;
if(ptr==NULL){
min=NULL;
return;
}
min = head;
for (ptr=ptr->link;ptr!=NULL;ptr=ptr->link)
{
if(ptr->process.reaming_time < min->process.reaming_time){
min=ptr;
}else if(ptr->process.reaming_time==min->process.reaming_time){
if(ptr->process.job_id < min->process.job_id){
min=ptr;
}
}else {
}
}
}
load_ReadyQueue(int var){
int i; // i-> local loop variable
for(i=0;i<n;i++){
if(job_queue[i].arrival_time==var){
enqueue(job_queue[i]);
}
}
}
