[Sms231]

New to the forums. I've been racking my brain on implementing a Shortest Job First algorithm for my Operating Systems class. The jist of the program is, I have to read in from a file a list of system "processes" each with different execution time into an array. I decided to have an array of structs, because an array of linked lists wouldn't be fesable. I'm performing more than one type of scheduling algorithm simulation in this program, but I've got the first one done already (FCFS). The problem that I'm running into is traversing the array to find the next shortest job based on the boundaries that I set (the boundary being the total execution time that has passed up to 30) and performing analysis on that (wait times, end times, turnaround times, etc.)

I hope I explained the problem well enough. Any help that anyone can provide would be greatly appreciated. Here's the relevant code:

const int SIZE = 30;

struct ProcessData
{
	int processNumber;
	int burstTime;
	int waitTime;
	int turnAroundTime;
	int endTime;
	int completionFlag;
	int leftToProcess; //For Round Robin Algorithm
};

void SJFSim(ProcessData newData[], int& count);
...
void SJFSim(ProcessData newData[], int& count)
{
				//These variables are for my analysis
	float totalRunTime = 0;
	float totalWaitTime = 0;
	float totalTurnAroundTime = 0;
	float totalBurstTime = 0;
	
	float avgRunTime = 0;
	float avgWaitTime = 0;
	float avgTurnAroundTime = 0;
	float avgNormalizedTurnAroundTime = 0;

	//Variables Relavant to Traversal

				int i = 0;
	int j = 0;
	int k = 0;
	int nextProcessMarker = 0;
	int previousProcessMarker = 0;
	int temp = 0;

				//Analysis on Initial Read
	newData[i].waitTime = 0;
	newData[i].endTime = newData[i].burstTime + newData[i].waitTime;
	newData[i].turnAroundTime = newData[i].burstTime;
	newData[i].completionFlag = 1;

	totalRunTime = newData[i].turnAroundTime;
	totalBurstTime = newData[i].burstTime;
	previousProcessMarker = i; //Set this as the last job processed
	
	for (i = 1; i < count; ++i)
	{
		//Set Boundary To Only Those Processes That Have Come In During Previous Execution

		temp = totalBurstTime;
		if (temp > 30)
			temp = 30;
		
		if (newData[i].completionFlag != 1)
		{
			for (j = 0; j < temp; j++)
			{
	 //If this is the smallest data in within the boundaries
				if ((newData[i].burstTime < newData[j].burstTime) && ((newData[i].completionFlag != 1 || newData[j].completionFlag != 1)))
				{
//Set this job to process				nextProcessMarker = i;
				}
			}
		}
								
//Code to generate analysis on End times, etc.
		newData[nextProcessMarker].turnAroundTime = newData[nextProcessMarker].burstTime + newData[previousProcessMarker].burstTime;
		newData[nextProcessMarker].waitTime = newData[previousProcessMarker].burstTime + newData[previousProcessMarker].waitTime;
		newData[nextProcessMarker].endTime = newData[nextProcessMarker].burstTime + newData[nextProcessMarker].waitTime;
		
		totalTurnAroundTime = totalTurnAroundTime + newData[nextProcessMarker].turnAroundTime;	
		totalRunTime = totalRunTime + newData[nextProcessMarker].turnAroundTime;
		totalWaitTime = totalRunTime + newData[nextProcessMarker].waitTime;
		totalBurstTime = totalBurstTime + newData[nextProcessMarker].burstTime;

		//Set This Data As Completed
								newData[nextProcessMarker].completionFlag = 1;
		previousProcessMarker = nextProcessMarker;
	}
				
				//Calculate Averages
	avgRunTime = totalRunTime / count;
	avgWaitTime = totalWaitTime / count;
	avgTurnAroundTime = totalTurnAroundTime / count;
	avgNormalizedTurnAroundTime = totalTurnAroundTime / totalBurstTime;
	
				//Output Averages
	cout << "# \tTime \tEnd \tTurn \tWait" << endl << endl;
	
	for (int j = 0; j < count; j++)
	{	
		cout << newData[j].processNumber << "\t" << newData[j].burstTime << "\t " << 
			newData[j].endTime << "\t" << newData[j].turnAroundTime << "\t" << newData[j].waitTime << endl;
	}

	cout << endl << "Global Averages" << endl << "----------------" << endl;
	cout << "Turnaround Time:\t\t" << avgTurnAroundTime << "ms" << endl;
	cout << "Normalized Turnaround Time:\t" << avgNormalizedTurnAroundTime << "ms" << endl;
	cout << "Wait Time:\t\t\t" << avgWaitTime << "ms" << endl;
}

I have also attached the full program for reference.

Attached File(s)

•  main.txt (6.33K)
  Number of downloads: 2781

This post has been edited by Sms231: 16 March 2007 - 04:04 PM

[NickDMax]

I assume that you are talking abou the code:

for (i = 1; i < count; ++i)
	{
		//Set Boundary To Only Those Processes That Have Come In During Previous Execution

		temp = totalBurstTime;
		if (temp > 30)
			temp = 30;
		
		if (newData[i].completionFlag != 1)
		{
			for (j = 0; j < temp; j++)
			{
	 //If this is the smallest data in within the boundaries
				if ((newData[i].burstTime < newData[j].burstTime) && ((newData[i].completionFlag != 1 || newData[j].completionFlag != 1)))
				{
//Set this job to process				nextProcessMarker = i;
				}
			}
		}

spacificly.

I not that the if-statement makes the && ((newData[i ].completionFlag != 1 || newData[j].completionFlag != 1)) a little redundant since we already know that newData[i ].completionFlag != 1 from the outer if-statment.

I guess I don't really see how the inner loop works... I think you are trying to loop though and find the smallest burstTime such that the completionFlag is not set.

I think that something like:

int smallest = 0;
for (i=1; i < count; ++i)
{
	if (newData[i].completionFlag != 1 && smallest == 0) 
   { 
		smallest = i; 
	} else if (newData[i].completionFlag != 1 && (newData[i].burstTime <newData[smallest].burstTime)) { smallest = i; }
   }
}
nextProcessMarker = smallest;

Of course, since I don't really understand what you are doing I may be way off base here.

This post has been edited by NickDMax: 17 March 2007 - 09:32 PM

[ajwsurfer]

To start with, I think that the length of the Job is "leftToProcess".
The problem I see is that using an array as a queue might seem simple at first, but the problem will blow up as you try to mantain the array, while adding and removing nodes. I would think a queue or tree structure would be much better suited for this application. Two canidates are "priority queue" and "binary search tree". I think by definition the "priority queue" is the better one.

So here is the method
1. "Push" all the nodes (structs or jobs) into the priority queue, using the "leftToProcess" integer to determine the priority.
2. For each burst, take the node from the top, decrement the "leftToProcess" by the "burstTime" and then "Push" it back in (if it isn't finnished).
3 Continuing this cycle will insure that the what ever job is shortest is done first.

Of course this is a very simplified version of what is going on, but it covers the main schedualing process.
Note: there will be a lot more bookeeping and changing of fields in the structs to do.

[ajwsurfer]

So here is what I have so far.

 
#include <iostream>

using namespace std;

const int Q_SIZE = 30;
int turnAroundTime;


struct AnalyisVars
{				//These variables are for my analysis
	int totalRunTime;
	int totalWaitTime;
	int totalTurnAroundTime;
	int totalBurstTime;
	
	float avgRunTime;
	float avgWaitTime;
	float avgTurnAroundTime;
	float avgNormalizedTurnAroundTime;
};

struct Job
{
	int processNumber;
	int burstTime;
	int waitTime;
	int turnAroundTime;
	int endTime;
	bool completionFlag;
	int leftToProcess; //For Round Robin Algorithm
};

void printJobStats(Job &pj);
void ProcessData(Job &pj);
void initVars(AnalyisVars &av);

void ProcessData(Job &pj) {
   pj.waitTime = turnAroundTime;	   // INV: waitTime is set 
   if (pj.leftToProcess <= pj.burstTime) {
	 pj.burstTime = pj.leftToProcess;
	 pj.leftToProcess = 0;
	 pj.completionFlag = true;
	 pj.turnAroundTime = turnAroundTime + pj.burstTime;  // INV:  burstTime, leftToProcess, completionFlag & turnAroundTime are set.
   } else {
	 pj.leftToProcess -= pj.burstTime;
   }									// INV: leftToProcess and burstTime are set
   turnAroundTime += pj.burstTime;
   pj.turnAroundTime = turnAroundTime;  // INV: turnArroundTime is set
   printJobStats(pj);
}

void printJobStats(Job &pj) {   
   cout << "Job # " << pj.processNumber << endl;
   cout << "Wait time:\t\t" << pj.waitTime << "ms" << endl;
   cout << "Burst time:\t\t" << pj.burstTime << "ms" << endl;
   cout << "Left to proccess:\t\t" << pj.leftToProcess << "ms" << endl; 
   cout << "End time:\t\t" << pj.endTime << endl; 
   if (pj.completionFlag == true) {
	 cout << "Turn around time:\t\t" << pj.turnAroundTime << endl;  
   }
}

void initVars(AnalyisVars &av) {
  turnAroundTime = 0;
  av.totalRunTime = 0;
  av.totalWaitTime = 0;
  av.totalTurnAroundTime = 0;
  av.totalBurstTime = 0;

  av.avgRunTime = 0.0;
  av.avgWaitTime = 0.0;
  av.avgTurnAroundTime = 0.0;
  av.avgNormalizedTurnAroundTime = 0.0;
};


int main() {
  AnalyisVars av;
  initVars(av);
  cout << "It compiled";
  return 0;
}

The example in the link below shows how to use the STL Priority Queue.

http://www.java2s.co...iorityqueue.htm

I always say keep the functions small. If there are two things I am trying to acomplish, they can probably be done in two functions. And I realy like to keep the main function as small as possible.

[ajwsurfer]

Now lets add a few things...

#include <iostream>
#include <queue>
#include <string>

using namespace std;

...


// Determine priority.
bool operator<(const Job &a, const Job &b)
{
  return a.waitTime + a.leftToProcess > b.waitTime + b.leftToProcess;
}

int main() {
  AnalyisVars av;
  initVars(av);
  priority_queue<Job> jobs;
  
  // initialize and push jobs
  
  // process jobs

  // print statisitcs  
  cout << "It compiled";
  return 0;
}

There is still a lot to do but I think this should get you off int the right direction;)

[palak1]

Can someone please tell me whether the code displayed in te above posts are for pre-emptive or for non-preemptive SJFS algorithm?

[kambagiri]

now just let us see a simple code for FCFS

    #include<stdio.h>
    #include<conio.h>
int main()
    {
      float avg;
       int cputm[20],arrvt[20],tmvar[20],sum=0,i,j=0,min,min1,temp1,temp,n;
   
       printf("Enter number of processors:");
       scanf("%d",&n);
       for(i=0;i<n;i++)
        {
           printf("Enter values for %d processors:",i+1);
            scanf("%d %d",&cputm[i],&arrvt[i]);
        }
       while(j<n)
        {
          min=arrvt[j];
          for(i=j+1;i<n;i++)
           {
               if(arrvt[i]<min)
                {
                  temp=arrvt[i];
                  temp1=cputm[i];
                   arrvt[i]=min;
                   cputm[i]=cputm[i-1];
                   arrvt[i-1]=temp;
                   cputm[i-1]=temp1;
                }
            }
          j++;
       }
     printf("The minimal order is :");
  for(i=0;i<n;i++)
        printf("\n %d \t %d",cputm[i],arrvt[i]);
   for(i=1;i<n;i++)
     cputm[i]+=cputm[i-1];
 tmvar[0]=0;
     for(i=1;i<n;i++)
                tmvar[i]=cputm[i-1]-arrvt[i];
      for(i=0;i<n;i++)
             sum+=tmvar[i];
    avg=(float)sum/n;
printf("\n The average waiting time is :%f",avg);
getch();
return 0;
}

[kambagiri]

The codes which are mentioned may be somewhat typical to understand. I written a simple which can also be understood by newbies

#include<stdio.h>
#include<conio.h>
int main()
{
     int cput[20],art[20],w[20],n,i,j=0,min,min1,temp,temp1;
     float avg,sum=0;
     printf("Enter number of processors:");
     scanf("%d",&n);
     for(i=0;i<n;i++)
     {
        printf("\n Enter values for %d processor:",i+1);
        scanf("%d ",&cput[i]);
        scanf("%d", &art[i]);
     }
    
    for(i=0;i<n;i++)
    {
      for(j=i+1;j<n;j++)
      {
        if(cput[i]>cput[j])
        {
          temp=cput[i];
          temp1=art[i];
          cput[i]=cput[j];
          art[i]=art[j];
          cput[j]=temp;
          art[j]=temp1;
        }
      }
    }
     printf("The order of processors:");
     for(i=0;i<n;i++)
     {
        printf("\n %d \t %d",cput[i],art[i]);
     }
     w[0]=0;
     for(i=1;i<n;i++)
     {
       w[i]=cput[i-1]+w[i-1];
       sum+=w[i];
     }
     avg=sum/n;
     printf("\n The average waiting time is :%f",avg);
    getch();
    return 0;
}