problem with CPU scheduling algorithm

[rose_2]

I make a program to simulate the Shortest Job First algorithm in CPU scheduling ..
this function will calculate the start , end, turn,and wait time for each proccess according to Non-preemptive way .. the 1st condition gonna check for the 1st arrival time or the smallest burst time .. I go some trouble here with handling the condition .. i just need some help to show me the right way to handle the condition .. thanks

vector<timeSlote> SJF_Np(vector<process> v)
 {
     vector<timeSlote> t;
     timeSlote ts;
    int temp,temp1;
    int turn,wait;
    int totalwait = 0;
    int totalturn = 0;
    int currentTime = 0;

    for (unsigned int i = 0; i<v.size(); i++)
    {
        for (unsigned int j = 1; j <= v.size(); j++)
        {
            if (v.at(i).arrival <= currentTime || v.at(j - 1).burst >v.at(j).burst)
            {
                   ts.start = currentTime;
                    temp = v.at(j - 1).burst;
                    temp1 = v.at(i).arrival;
                    v.at(j - 1).burst = v.at(j).burst;
                    v.at(i).arrival = currentTime;
                    v.at(j).burst = temp;
                    currentTime = temp1;

                    ts.start = currentTime;
                    ts.p = v.at(i);
                    ts.end = v.at(i).burst + ts.start;
                    currentTime = ts.end;
                    turn = ts.end - v.at(i).arrival;
                    wait = turn - v.at(i).burst;
                    totalturn += turn;
                    totalwait+= wait;
                    t.push_back(ts);
            }
            else
            {
                process p = { "idle" };
                ts.start = currentTime;
                ts.p = p;
                ts.end = v.at(i).arrival;
                t.push_back(ts);
                timeSlote ts2;
                ts2.start = ts.end;
                ts2.p = v.at(i);
                ts2.end = v.at(i).burst + ts2.start;
                currentTime = ts2.end;
                turn= ts2.end - v.at(i).arrival;
                wait = turn - v.at(i).burst;
                totalturn += turn;
                totalwait+= wait;
                t.push_back(ts2);
            }
        }
    }

[rproffitt]

Wow, one of my old favorite topics. This reminds of the queuing theory class days. But before I comment I think this is pretty well discussed:
https://www.google.com/search?q=simulate+the+Shortest+Job+First+algorithm+in+CPU+scheduling&ie=utf-8&oe=utf-8

Videos and more are out there.

Now if you want to discuss your code, you omitted what issue you have with it. Very few folk will deflea code today. If you have errors, share them since to find it, you are asking folk to guess what compiler, IDE and OS you are on and more.

With that out of the way, I may be outdated but my results for maximum throughput was longest job first. The example was 1 or more machines, then start the longest job and then prepare the rest of the jobs sorted by how long they take. In the real world this worked great plus one modifcation. We would start the work just like queuing theory said then go back and see if any job had priority.

[rose_2]

hmmm ..
i think the error in the condition which check for the smallest burst time .. it acts as fcfs but includes the smallest burst .. am i right ?
this code is assumed to work under linux & windows

[rproffitt]

This code does not compile with Visual Studio or gcc. So I would be guessing what's missing.

fcfs? In queuing I would guess that's First Come First Served. In such a system there would be no sorting, just a queue that we have a method to add new requests.

[rose_2]

no it's compiled in visual and gcc .. and yeah i tried to edit the fcfs code to implement SJF_Non preemptive ..i think i need those two function to handle the condition but in which way.. i cant get that .. the condition to get the 1st arrival then whenever arrival it gonna take the smallest burst .. but if there is a process doesnt arrive yet but has the smallest arrival ..which condition will gonna handle that case !!

//sorting vector<process> according to arrival time to get which process will be execute at 1st
void sortArrivals(vector<process>& v){

    bool swapp = true;
    while (swapp){
        swapp = false;
        for (unsigned int i = 0; i < v.size() - 1; i++) {
            if (v.at(i).arrival > v.at(i + 1).arrival){
                process p = v.at(i);
                v[i] = v.at(i + 1);
                v.at(i + 1) = p;
                swapp = true;
            }
        }
    }
}
//getting smallest burst time 
int  getSmallestBurst(vector<process> v)
{
    assert(v.size());
    int smallest = v.at(0).burst;
    for (unsigned int i = 0; i < v.size(); i++)
    {
        if (v.at(i).burst < smallest)
            smallest = v.at(i).burst;
    }
    return smallest;
}

[rproffitt]

Still looks incomplete code wise. I tossed the above into http://ideone.com/ and well, what's here looks incomplete so I can't guess what you are seeing.

Back to you. Narrow down your question to what lines you think are trouble. Here I can't guess what else is missing in your code or what lines to read. I won't read more than a page of code since you can narrow it down.

[rose_2]

okey .. thxx for ur help i fixed it .. and here is my code

#include <cassert>
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <vector>
#include <climits>
#include <cstdlib>

using namespace std;

struct process
{
    string name;
    int arrival;
    int burst;
    int per;
    int RemainingBurst;
};
struct timeSlot
{
    int start;
    int end;
    process p;
};
int toint(string s) //The conversion function
{
    return atoi(s.c_str());
}
void printProcess(process p)                            //print the process struct in a special formate
{
    cout << "======================" << endl;
    cout << "Process name: " << p.name << endl;
    cout << "Process arrival time: " << p.arrival << endl;
    cout << "Process burst time: " << p.burst << endl;
    //cout << "Process periourty" << p.per << endl;
    cout << "======================" << endl;
}
void printAllProcess(vector<process> p)
{
    for (unsigned int i = 0; i<p.size(); i++)
    {
        printProcess(p.at(i));
    }
}
void printSlot(timeSlot s)
{
    cout << s.start << "==";
    cout << "[" << s.p.name << "]==";
    cout << s.end << "==";
}
void printAllSlots(vector<timeSlot> t)
{
    cout << endl;
    for (unsigned int i = 0; i<t.size(); i++)
        printSlot(t.at(i));
    cout << endl;
}
//save the contents of the vector of timeSlots in a new file with name "fileName"
void writeTimeSlote(vector<timeSlot> v, char argv[])
{
    ofstream outfile;
    outfile.open("fileName.txt");
    timeSlot s;
    for (unsigned int i = 0; i < v.size(); i++)
    {
        s = v.at(i);
        outfile << "=================" << endl;
        outfile << "start at time: " << s.start << endl;
        outfile << s.p.name << endl;
        outfile << "End at time: " << s.end << endl;
        outfile << "=================" << endl;
    }
    outfile.close();
}
//to let stoi() be valid type in compilation line g++ -std=c++0x filename.cpp
process parseProcess(string s)              //parse the given string s to find the process information 
{
    process p;
    stringstream lineStream;
    lineStream.str(s);
    string item;
    getline(lineStream, item, '$');
    p.name = item;
    getline(lineStream, item, '$');
    p.arrival = toint(item);
    getline(lineStream, item, '$');
    p.burst = toint(item);
    //getline(lineStream, item, '$');
    //p.per = stoi(item);
    p.RemainingBurst = p.burst;
    return p;
}
//function to read information from file
vector<process> readProcess(char argv[])
{
    vector<process> v;
    ifstream infile;
    infile.open("info.txt");
    string line;
    while (getline(infile, line))
    {
        process p = parseProcess(line);
        v.push_back(p);
        cout << "==================" << endl;
    }
    infile.close();
    return v;
}
//sorting vector<process> according to arrival time to get which process will be execute at 1st
void sortArrivals(vector<process>& v){

    bool swapp = true;
    while (swapp){
        swapp = false;
        for (unsigned int i = 0; i < v.size() - 1; i++) {
            if (v.at(i).arrival > v.at(i + 1).arrival){
                process p = v.at(i);
                v[i] = v.at(i + 1);
                v.at(i + 1) = p;
                swapp = true;
            }
        }
    }
}
//getting smallest burst time 
process getSmallestBurst(vector<process> v)
{
    assert(v.size());
    process p = v.at(0);
    int smallest = v.at(0).burst;
    for (unsigned int i = 0; i < v.size(); i++)
    {
        if (v.at(i).burst < smallest){
            smallest = v.at(i).burst;
            p = v.at(0);

        }
    }
    return p;
}

int totalTurn = 0;
int totalWait = 0;

vector<timeSlot> SJF_Np(vector<process> v)
{
    vector<timeSlot> t;
    int currentTime = 0;
    int turn, wait;
    timeSlot slote;

    for (unsigned int x = 0; v.size() != 0; x++){
        process p = { "idle" };
        int index = -1;
        for (unsigned int i = 0; i < v.size(); i++){
            if (v.at(i).arrival <= currentTime){
                if (p.name == "idle"){
                    p = v.at(i);
                    index = i;
                }
                else{
                    if (p.burst > v.at(i).burst){
                        p = v.at(i);
                        index = i;
                    }
                }
            }
        }
        if (p.name == "idle"){
            p = v.at(0);
            for (unsigned int i = 0; i < v.size(); i++){
                if (v.at(i).arrival < p.arrival)
                    p = v.at(i);
            }
            timeSlot idleSlote;
            idleSlote.start = currentTime;
            currentTime += p.arrival - currentTime;
            idleSlote.end = currentTime;
            idleSlote.p = { "idle" };
            t.push_back(idleSlote);
            x--;
        }
        else{
            timeSlot slotNotidle;
            slotNotidle.p = p;
            slotNotidle.start = currentTime;
            currentTime += p.burst;
            slotNotidle.end = currentTime;
            wait = slotNotidle.end - p.burst - p.arrival;
            turn = wait + p.burst;
            totalTurn += turn;
            totalWait += wait;
            t.push_back(slotNotidle);
            v.erase(v.begin() + index);
        }
    }
    return t;
}
/*vector<timeSlot> SJF_P(vector<process> v)
{

}*/
int main(int argc, char *argv[])                        //it takes two arguments 1:inputFile name, 2:outputFile name
{

        int processNumber;

        vector<process> v = readProcess(argv[1]);
        processNumber = v.size();
        printAllProcess(v);

        vector<timeSlot> t = SJF_Np(v);

        printAllSlots(t);
        writeTimeSlote(t, argv[2]);
        cout << "Average Turn Time = " << (float)totalTurn / processNumber << endl;
        cout << "Average WaitingTime = " << (float)totalWait / processNumber << endl;

        //cin.get();
        return 0;

}