scheduler.h

A small program to simulate priority scheduling in Unix.

#define _XOPEN_SOURCE
#include <stdio.h>
#include <sys/types.h>
#include <unistd.h>
#include <stdlib.h>
#include <sys/wait.h>
#include <sys/timeb.h>
#ifdef linux
#include <getopt.h>
#endif
#include <string.h>
#include "shared.h"
#include <time.h>
/* to implement priority scheduling, you may want to change the following */
    typedef PCB_entry *readyQueues;
    readyQueues  ready_q[10]; 	          /* global since it is shared among the  various scheduler functions.*/
//    ready_q = (PCB_entry *) malloc (10*sizeof (PCB_entry));

/*
 * Function Schedule_next: Non-preemptive round-robin
 *
 * Called by the central simulation system Returns a pointer to the PCB entry
 * for the "process" that should be put on the CPU next
 *
 */


PCB_entry *schedule_next (void)
{
	PCB_entry *temp;

/* if all ten ready_q are null, there are no processes in the system */

	int j;			/*simulates the priority levels of the ready queues*/
	for(j=9; j>=0; j--)
	{
		if(ready_q[j] == NULL)
			continue;
		else
			break;
	}

	temp = ready_q[j];		/*return the first process in the 1st non-null queue of the highest priority*/
	ready_q[j] = ready_q[j]->f_link;
	if (ready_q[j] != NULL)		            /* don't try to de-reference a NULL pointer */
		ready_q[j]->b_link = NULL;	           /* first process in the queue always has a NULL back link */
	temp->f_link = NULL;			/* just to be tidy -- set both links in the PCB */
							/* entry that will be returned to NULL */
	temp->b_link = NULL;
	return temp;
}


/*
 * Function insert_new: Non-preemptive 10 level priority
 *
 * Insert a new "process" into the scheduling queue
 *
 * Accepts a pointer to a PCB entry that will be inserted into the queue returns
 * either OK or NotOK to indicate success or failure
 *
 * Since this is simple round-robin, the new process is simply slotted in at the
 * end of the queue
 *
 * Note that optionally, this code could have been written with an additional
 * global pointer to the tail of the list. This would have provided some
 * performance advantages at the expense of slightly more complex insert and
 * remove functions.
 */


int insert_new (PCB_entry *proc)
{

	PCB_entry *next, *prev;
	int z = proc->initial_priority - 1;				/*set the index of the queue based on the priority*/
	//proc->current_priority = proc->initial_priority;	/*for a new process make both equal*/

	if (ready_q[z] == NULL)
	{						/* no entries in table */
		ready_q[z] = proc;			/* insert at the head of the list */
		proc->b_link = NULL;
		proc->f_link = NULL;
		return OK;
	}
	else
	{
		next = ready_q[z];
		while (next != NULL)
		{					/* traverse to the end of the list */
			prev = next;
			next = prev->f_link;
		}
		proc->b_link = prev;			/* link the new PCB in at the end */
		proc->f_link = NULL;
		prev->f_link = proc;
		return OK;
	}
	return NotOK;
}



/*
 * Function list_q
 *
 * essentially a debugging function to list the current contents of the ready
 * queue. We have modified this function to also do the boosting check for our
 * 10 level priority implimentation.
 */

void list_q (void)
{
    int i;
    time_t current_time;
  for(i=0; i<10; i++)
  {
	PCB_entry *next;

	next = ready_q[i];

	fprintf (stderr, "\n current state of the ready queue\n");

	while (next != NULL)
	{				/* traverse to the end of the list */
		fprintf (stderr, "%d\t", next->proc_no);
		    if (difftime(current_time, next->end_clock) >= 2000)     //checking if the process has waited more than 2000 time units.
        re_insert(next, 1);                      //submit the process for boosting if waited too long. We use 1 to show boosting
		next = next->f_link;
	}
	fprintf (stderr, "\n");

	next = ready_q[i];
	while (next != NULL)
	{				/* traverse to the end of the list */
		fprintf (stderr, "%d\t", next->pid);
		next = next->f_link;
	}
	fprintf (stderr, "\n\n");
  }
}


/*
 * Function re_insert: Non-preemptive round-robin
 *
 * a function to insert a process back into the queue following a run on the CPU
 * Depending on the scheduling algorithm chosen this would need to do a lot
 * more. In a priority algorithm with boost and reduction, it would need to
 * look at the percentage of the quantum that the process used and determine
 * if a change to the priority was required. Also, in implementing a
 * mulitlevel priority scheme, a variation of the ready_q pointer would be
 * required. The simplest method would be an array of pointers with one
 * element for each priority level.
 */


int re_insert (PCB_entry * proc, int run_time)
{
	PCB_entry *next, *prev;

	int j = proc->current_priority - 1;				/*set the index of the queue based on the priority*/

	if ( (proc->BurstHead)->quantum == QUANTUM )
        if (j!=0)
            j--;						/*reduce the priority if it used all the quantum*/

    if (run_time == 1)
        if (j<10)
            j++;

	if (ready_q[j] == NULL)
	{							/* no entries in table */
		ready_q[j] = proc;
		proc->b_link = NULL;
		proc->f_link = NULL;
		return OK;
	}
	else
	{
		next = ready_q[j];
		while (next != NULL)
		{						/* traverse to the end of the list */
			prev = next;
			next = prev->f_link;
		}
		proc->b_link = prev;				/* insert PCB struct at the end */
		proc->f_link = NULL;
		prev->f_link = proc;
		return OK;
	}

	return NotOK;
}



/*
 * Function init_q: Non-preemptive round-robin
 *
 * Initialises the ready queue.
 * Written as a function so that, if the ready_q becomes an array of pointers,
 * the initialisation can be changed without re-building the main part of the
 * simulator
 */

int init_q (void)
{
	int i;
	for(i=0; i<10; i++)
		ready_q[i] = NULL;
	return OK;
}