Welcome to Dream.In.Code
Become a C++ Expert!

Join 137,230 C++ Programmers for FREE! Get instant access to thousands of C++ experts, tutorials, code snippets, and more! There are 1,868 people online right now. Registration is fast and FREE... Join Now!




Shortest Job First

 
Reply to this topicStart new topic

Shortest Job First

Sms231
16 Mar, 2007 - 03:02 PM
Post #1

New D.I.C Head
*

Joined: 16 Mar, 2007
Posts: 4


My Contributions
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:

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.

This post has been edited by Sms231: 16 Mar, 2007 - 03:04 PM


Attached File(s)
Attached File  main.txt ( 6.33k ) Number of downloads: 337
User is offlineProfile CardPM
+Quote Post

NickDMax
RE: Shortest Job First
17 Mar, 2007 - 08:30 PM
Post #2

2B||!2B
Group Icon

Joined: 18 Feb, 2007
Posts: 2,859



Thanked: 50 times
Dream Kudos: 550
My Contributions
I assume that you are talking abou the code:

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:
CODE

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 Mar, 2007 - 08:32 PM
User is offlineProfile CardPM
+Quote Post

ajwsurfer
RE: Shortest Job First
19 Mar, 2007 - 12:07 PM
Post #3

D.I.C Regular
Group Icon

Joined: 24 Oct, 2006
Posts: 292



Thanked: 2 times
Dream Kudos: 50
My Contributions
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.
User is offlineProfile CardPM
+Quote Post

ajwsurfer
RE: Shortest Job First
20 Mar, 2007 - 06:56 AM
Post #4

D.I.C Regular
Group Icon

Joined: 24 Oct, 2006
Posts: 292



Thanked: 2 times
Dream Kudos: 50
My Contributions
So here is what I have so far.

CODE

#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.com/Code/Cpp/Data-Struct...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.

User is offlineProfile CardPM
+Quote Post

ajwsurfer
RE: Shortest Job First
20 Mar, 2007 - 07:45 AM
Post #5

D.I.C Regular
Group Icon

Joined: 24 Oct, 2006
Posts: 292



Thanked: 2 times
Dream Kudos: 50
My Contributions
Now lets add a few things...
CODE


#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;)
User is offlineProfile CardPM
+Quote Post

Reply to this topicStart new topic
Time is now: 12/4/08 03:17PM

Live C++ Help!

C++ Tutorials

Reference Sheets

C++ Snippets

DIC Chatroom

Bye Bye Ads

Monthly Drawing

Thumb Drive

Top Contributors

Top 10 Kudos This Month