Queue Application – Round Robin Job Execution

Many tasks in an operating system require Queue application. Queues can be used for scheduling OS tasks by maintaining their job details and its sequence of execution in all the submitted jobs.  

Assumptions

Consider a situation where a number of jobs are submitted to a system. All the jobs have known and variable execution time. The system executes jobs in such a way that all jobs are given fixed time of execution in a round robin fashion. This will ensure that no job is starved and each one is executed giving an impression of multi tasking.

The system takes up first job and executes it for a predefined fixed time slot. The slot duration is subtracted from the remaining duration of the executed job and the remaining time of completion of a job is updated.

When time slot of current job finishes, the system proceeds to pick up next job in queue and execute it for the same predefined and fixed time slot.

When the execution time of any job exhausts, it is removed from the queue.

When the system executes last job in queue for the fixed time slot, it starts back from the first job again and repeats these rounds of execution till all the jobs in the queue are finished.

Queue Application-Code

Using the above assumption, the Queue Application program (in C) for Round Robin Job Execution is created. The data about the jobs is stored by linked list implementation. The node has a JobID part and Duration part in addition to the pointer to the next node. The program begins by asking the user to enter the number of jobs to be executed. Next the user has to enter the total duration of execution of each job.

The rounds of execution of this queue application depend upon the value of the front pointer. The rounds end when FRONT pointer becomes null indicating that no unfinished jobs are left in the queue. In each round the duration part of each job is reduced by 1 if it is non zero. When duration part of a job becomes zero, the queue node of this job is removed from the queue by updating the pointer of the previous node with address of next node.

Code

#include<stdio.h>
#include<stdlib.h>
// decelaration of a node 
struct node
{
	int jobid;
	int duration;
	struct node *link;
}*front=NULL, *rear=NULL;
// inserting a new job in the queue at end
void QLinsert(int jid, int item)
{
	struct node *ptr;
	ptr=(struct node *)malloc(sizeof(struct node));
	//check for underflow
	if(ptr==NULL)
	{
		printf("\n Overflow");
		return;
	}
	//prepare the node
	ptr->duration=item;
	ptr->jobid=jid;
	ptr->link=NULL;
	//add at end
	if(front==NULL)
	{
		front=ptr;
		rear=ptr;
	}
	else
	{
		rear->link=ptr;
		rear=ptr;
	}
}

void display()
{
	struct node*ptr;
	if(front==NULL)
	{
		return;
	}
	printf("Current Jobs in Queue are:");
	ptr=front;
	printf("\n---------------------------------------\n");
	printf("Job ID\t\t\t Duration left\n ");
	printf("\n---------------------------------------\n");

	while(ptr!=NULL)
	{
		printf("%d\t\t\t\t%d  \n",ptr->jobid, ptr->duration);
		ptr=ptr->link;
	}
	printf("\n---------------------------------------\n");
}
void main()
{
	int item, n,i=0, rounds=0,time=0;
	struct node *ptr,*prev;
		//read duartions of jobs
	printf("\nEnter number of Jobs to be executed:");
	scanf("%d", &n);
	while(i<n)
	{
			printf("Enter Job %d. duration ",i+1);
			scanf("%d", &item);
			QLinsert(i+1, item);
			i=i+1;
	}
	printf("\nInitially ");
	display();
	i=0;
	while(front!=NULL)
	{
			prev=NULL;
			ptr=front;
			while(ptr!=NULL)
			{
				if(ptr->duration-1==0)
				{
					if (prev==NULL)
						front=ptr->link;
					else
					{
						prev->link=ptr->link;
					}
				}
				else
				{
					ptr->duration--;
					prev=ptr;
				}
				ptr=ptr->link;
			}
			rounds++;
			printf("\nAfter Round %d ",rounds);		
			display();
	}
	printf("execution is completed ");
	
}

Output

You can enhance this code using a circular queue.

admin