/*You are required to simulate a multilevel queue CPU scheduling that
has the following four-priority queues.
Processes are assigned to one of the queues according to their
individual priority number. 

      System processes queue. Processes with highest priority (0). When
a process with this priority comes in, it
      preempts immediately any process of lower priority and gets the
CPU. It executes until it finishes. 
      Express processes queue. Processes with priority (1). A process is
assigned the CPU as soon as the current
      process leaves the CPU, provided that "system processes" queue is
empty. A process from this queue will
      have the CPU until it finishes execution or when a process with
higher priority comes in. 
      Interactive processes queue. Processes with priority (2).
Processes in this queue are executed in a Round
      Robin scheduling with Q=2 time units. 
      Batch processes queue. Processes with lowest priority (3). Batch
processes are executed First Come First
      Served scheduling. 

Scheduling between queues is done as follows: 

      When there are no processes with priority number less than 3
(priority higher than that of batch
      processes), the system devotes the CPU completely to batch
processes. 
      When there are interactive and batch processes, the CPU time is
divided between interactive and batch
      processes queues, giving 20 time units to the former and 5 time
units to the latter. 
      Otherwise, a process is preempted from the CPU when another
process with higher priority comes in. The
      remaining time slot is given to the preempted process when
processes with higher priorities have finished. 

Each process includes the following parameters: 

      Process number 
      Time of arrival 
      CPU burst time 
      Priority number 

            0: system

            1: express

            2: interactive

            3: batch

Your simulator should generate the Gantt chart and calculate the average
waiting and turnaround times for any
possible set of processes. For this assignment, your simulator will read
a stream of processes with their
parameters from a manually generated file.
*/
/* Anan Tongprasith */
/********************/
#include<stdio.h>
#include<stdlib.h>
/*** New structure type ***/
struct ml {	int procnum;		/* process number */
		int arrvtime;		/* arrival time */
		int cpub;		/* cpu burst time */
		int priority;		/* priority of the process */
	  };
struct q1 {	int procnum[5];		/* arriving process */
		int runproc;		/* running process */
		int finishproc;		/* exiting process */
	  };
struct q2 {	int procnum;		/* process number */
		int cpubleft;		/* more cpu burst needed */
	  };
struct q3 {	int procnum;		/* process number */
		int cpubleft;		/* more cpu burst needed */
		int tquantumleft; /*time quantum left from the original 2*/
	  };

/*** Global variables ***/
struct ml mainlist[100]; /*"mainlist[order]" contains each process' data read
			   from input file in consecutive order*/ 
struct q1 eventlist[500]; /*"eventlist[time]" contains events happen along the
			   timeline, eg. processes'arrival, running
			   process, exiting process*/
struct q2 systemq[25]; /*"systemq[queue-order]" contains ready-to-run system 
			processes*/
struct q2 expressq[25]; /*"expressq" contains ready-to-run express processes*/
struct q3 interacq[25]; /*"interacq" contains ready-to run interactive
			 processes*/
struct q2 batchq[25]; /*"batchq" contains ready-to-run batch processes*/
int mytime=0,timer=0,dedicated=0;
/*** Main function ***/
int main(int *argc, char *argv[])
{	int i,j,k,runq,mytotal,turnaroundtime[100],waitingtime[100];
	FILE *fp;
	char newline[30];char buf1[5],buf2[20],buf3[25];
/* Initialize the mainlist */
  for(i=0;i<100;i++)
  	mainlist[i].procnum=-1;
/* Read the lines from input file and put into the main list*/
  i=0;
  fp=fopen(argv[1],"r");
  while(fgets(newline,100,fp) != NULL)
  {	sscanf(newline,"%s %25c",buf1,buf3);
	mainlist[i].procnum=atoi(buf1);
  	sscanf(buf3,"%s %20c",buf1,buf2);
	mainlist[i].arrvtime=atoi(buf1);
  	sscanf(buf2,"%s %20c",buf1,buf3);
	mainlist[i].cpub=atoi(buf1);
	mainlist[i].priority=atoi(buf3);
	i++;
  }
  mytotal=i;
  fclose(fp);
/* Initialize eventlist, timeline ends at 499 time units */
  for(i=0;i<500;i++)
  {	eventlist[i].finishproc=-1;	/*exiting process*/
	eventlist[i].runproc=-1;	/*running process*/
	for(j=0;j<5;j++)
		eventlist[i].procnum[j]=-1;	/*arriving processes*/
  }
/* Write eventlist out from mainlist */
  i=0;
  while(mainlist[i].procnum>0) 
  {
	j=0;
	while(eventlist[mainlist[i].arrvtime].procnum[j]>0)
		j++;
	eventlist[mainlist[i].arrvtime].procnum[j]=mainlist[i].procnum;
	i++;
  }
/* Initialize queues */
for(i=0;i<25;i++)
{	systemq[0].procnum=0;	/*The queues start from 1 to 24 */
	expressq[0].procnum=0;  /*Queue's element 0 is the total number*/
	interacq[0].procnum=0;  /*of entries in that queue*/
	batchq[0].procnum=0;
}
/* Now let's begin the simulation */
  fp=fopen("sim.out","w");
  fprintf(fp,"---------------\n");
  for(mytime=0;mytime<500;mytime++)
  {	
/* Read arriving processes from eventlist and put them into queues */
	stuffqueue(mytime);
/* Decide process from which queue should be run at this time unit */
	runq=4;
	runq=decidequeue(runq);
/* Decided, now run the first process from that queue */
	myrun(runq);
/* Now write the output */ 
	if(mytime>0)
	{ if(eventlist[mytime-1].runproc!=eventlist[mytime].runproc)
	   fprintf(fp,"---------------\n");
	  else
	  { if(eventlist[mytime-1].finishproc>0)
		fprintf(fp,"---------------\n");
	    else
		if(runq==2&&interacq[1].tquantumleft==1)
		   fprintf(fp,"---------------\n");
	  }
	}
	if(eventlist[mytime].runproc>0)
	  fprintf(fp,"%2d:   %2d\n",mytime,eventlist[mytime].runproc);
	else
	  fprintf(fp,"%2d:    X\n",mytime);
  }
printf("Total process=%d\n",mytotal);
  i=0;
  while(i<mytotal)
  {	j=mainlist[i].procnum;
	k=0;
	while(eventlist[k].finishproc!=j)	k++;
	turnaroundtime[i]=k-mainlist[i].arrvtime+1;
	waitingtime[i]=turnaroundtime[i]-mainlist[i].cpub;
	i++;
  }
  i=0;j=0;k=0;
  while(i<mytotal)
  {	j+=turnaroundtime[i];
	k+=waitingtime[i];
	i++;
  }
  fprintf(fp,"Total processes = %d \n",mytotal);
  fprintf(fp,"Average turnaround time = %.2f \n",(float)j/mytotal);
  printf("Average turnaround time = %.2f \n",(float)j/mytotal);
  fprintf(fp,"Average waiting time = %.2f\n", (float)k/mytotal);
  printf("Average waiting time = %.2f\n", (float)k/mytotal);
  printf("Gantt chart is in 	sim.out	   .\n");
  fclose(fp);
}
/*** "lookup" return the position in the mainlist which has the given
     process number ***/
int lookup(int i)
{  int j=0;
	for(j=0;j<100;j++)
	{	if(mainlist[j].procnum==i)
			return j;
	}
	return j;
}
/*** "stuffqueue" read arriving processes from eventlist and put into
     system queue, express queue, interactive queue, or batch queue ***/
int stuffqueue(int mytime)
{  int j,k,x;
	j=0;
/* Read the arriving process */
	while(eventlist[mytime].procnum[j]>0)
	{	k=lookup(eventlist[mytime].procnum[j]);
/* Put into the correct queue */
		switch(mainlist[k].priority)
		{  case 0:	x=systemq[0].procnum;
				systemq[x+1].procnum=mainlist[k].procnum;
				systemq[x+1].cpubleft=mainlist[k].cpub;
				systemq[0].procnum=x+1;
				break;
		   case 1:	x=expressq[0].procnum;
				expressq[x+1].procnum=mainlist[k].procnum;
				expressq[x+1].cpubleft=mainlist[k].cpub;
				expressq[0].procnum=x+1;
				break;
		   case 2:	x=interacq[0].procnum;
				interacq[x+1].procnum=mainlist[k].procnum;
				interacq[x+1].cpubleft=mainlist[k].cpub;
				interacq[x+1].tquantumleft=2;
				interacq[0].procnum=x+1;
/* Reset timer if interactive process arrives with none exists before */
				if(x==0&&dedicated==3)	
				{	timer=0;
					dedicated=0;
				}
				break;
		   case 3:	x=batchq[0].procnum;
				batchq[x+1].procnum=mainlist[k].procnum;
				batchq[x+1].cpubleft=mainlist[k].cpub;
				batchq[0].procnum=x+1;
/* Reset timer if batch process arrives with none exists before */
				if(x==0&&dedicated==2)	
				{	timer=0;
					dedicated=0;
				}	
				break;

		}
		
		j++;
	}
}
/*** "decidequeue" decides process from which queue should be run
     at this time ***/
int decidequeue(int runq)
{  int k;
	if(systemq[0].procnum>0)
		runq=0;
	else
	{	if(batchq[0].procnum>0)
		{
			if(timer>19)
				runq=3;
			else
			{	if(interacq[0].procnum==0)
				{	timer=20;
					dedicated=3;
					runq=3;
				}
			}
		}
		if(interacq[0].procnum>0)
		{ 
			if(timer<20)
				runq=2;
			else
			{	if(batchq[0].procnum==0)
				{	timer=0;
					dedicated=2;
					runq=2;
				}
			}
		}
		if(expressq[0].procnum>0)
		{	if(mytime==0)	
				runq=1;
			else
			{	k=lookup(eventlist[mytime-1].runproc);
				if(runq==4)
					runq=1;
				if(runq==3)
				  if(mainlist[k].procnum!=batchq[1].procnum)
					runq=1;
				if(runq==2&&interacq[1].tquantumleft==2)
					runq=1;
			}
		}
	}
	return runq;
}
/*** "myrun" assume a process run, given the queue authorized to run*/
int myrun(int runq)
{ int tleft,mycount;
	switch(runq)
	{ case 0:	 
		timer=0;
		eventlist[mytime].runproc=systemq[1].procnum;
		systemq[1].cpubleft-=1;
/* The process is exiting */
		if(systemq[1].cpubleft==0)
		{	systemq[0].procnum-=1;
			eventlist[mytime].finishproc=systemq[1].procnum;
			mycount=1;
			while(mycount<systemq[0].procnum)
			{ systemq[mycount].procnum=systemq[mycount+1].procnum;
			  systemq[mycount].cpubleft=systemq[mycount+1].cpubleft;
			  mycount++;
			}
		}	
		break;
	  case 1:
		timer=0;
		eventlist[mytime].runproc=expressq[1].procnum;
		expressq[1].cpubleft-=1;
/* The process is exiting */
		if(expressq[1].cpubleft==0)
		{	expressq[0].procnum-=1;
			eventlist[mytime].finishproc=expressq[1].procnum;
			mycount=1;
/* Shifting the queue */
			while(mycount<expressq[0].procnum)
			{ expressq[mycount].procnum=expressq[mycount+1].procnum;
			  expressq[mycount].cpubleft=expressq[mycount+1].cpubleft;
			  mycount++;
			}
		}
		break;
	  case 2:
		timer++;
		eventlist[mytime].runproc=interacq[1].procnum;
		interacq[1].cpubleft-=1;
		interacq[1].tquantumleft-=1;
/* The process is exiting */
		if(interacq[1].cpubleft==0)
		{	interacq[0].procnum-=1;
			eventlist[mytime].finishproc=interacq[1].procnum;
			mycount=1;
/* Shifting the queue */
			while(mycount<=interacq[0].procnum)
			{ interacq[mycount].procnum=interacq[mycount+1].procnum;
			  interacq[mycount].cpubleft=interacq[mycount+1].cpubleft;
			  interacq[mycount].tquantumleft=2;
			  mycount++;
			}
		}
		else
/* time quantum (2) ran out? */
		{	if(interacq[1].tquantumleft==0)
			{ mycount=interacq[0].procnum;
			  interacq[mycount+1].procnum=interacq[1].procnum; 
			  interacq[mycount+1].cpubleft=interacq[1].cpubleft;
			  interacq[mycount+1].tquantumleft=2;
			  mycount=1;
/* Round robin the queue */
			  while(mycount<interacq[0].procnum+1)
			  { interacq[mycount].procnum=interacq[mycount+1].procnum; 
			    interacq[mycount].cpubleft=interacq[mycount+1].cpubleft;
			    interacq[mycount].tquantumleft=2;
			    mycount++;
			  }
			}
		}
		break;	
	  case 3:
		timer++;if(timer>24)	timer=0;
		eventlist[mytime].runproc=batchq[1].procnum;
		batchq[1].cpubleft-=1;
/* The process is exiting */
		if(batchq[1].cpubleft==0)
		{	batchq[0].procnum-=1;
			eventlist[mytime].finishproc=batchq[1].procnum;
			mycount=1;
/* Shifting the queue */
			while(mycount<=batchq[0].procnum)
			{ batchq[mycount].procnum=batchq[mycount+1].procnum;
			  batchq[mycount].cpubleft=batchq[mycount+1].cpubleft;
			  mycount++;
			}
		}
		break;
	}
}