11
\$\begingroup\$

I tried to make the code for implementation of first-come first-serve job scheduling algorithm as used by operating systems.

How can I make it better?

I am using turbo C++ compiler

#include<conio.h>
#include<iostream.h>
#include<dos.h>
struct process//contains information about processes in waiting queue
{
    int waitt;
    int etime;
    char name[32];
    struct process * next;
};

void inc( struct process * q)//increases wait time of all processes in wait queue
{
     while(q!=0)
     {
         q->waitt++;
         q=q->next;
     }
}

int pop(struct process** q)//remove process from wait queue to run state returns wait time of process
{
    int wait=(*q)->waitt;
    struct process* t=*q;
    *q=(*q)->next;
    delete t;
    return wait;
}

void addnode(struct process** q)//add new process to wait queue
{
   struct process *temp=new (struct process);
   cout<<"\nEnter process name ";
   cin>>temp->name;
   do
   {
        cout<<"\nEnter process execution time ";
        cin>>temp->etime;
   }while(temp->etime<=0);//to check valid input for process burst time
   temp->next=0;
   temp->waitt=0;
   if(*q==0)
   *q=temp;
   else
   {
        struct process* t=*q;
        while(t->next!=0)
        t=t->next;
        t->next=temp;
    }
}

int main(void)
{
    clrscr();
    int e=1,wait=0,p=0,tt=1;
    struct process* q=0,*t;
    //add first process
    addnode(&q);
    e=q->etime;//Burst time of runing process
    cout<<"\nProcess "<<q->name<<" startedafter a wait time of "<<q->waitt;
    cout<<" time units \n";
    p++;
    wait=pop(&q);
    do
    {
        //to check addition of new process
        if(kbhit())
        addnode(&q);
        //increase wait time of waiting processes
        inc(q);
        //decrement time left for finishing of process
        e--;
        if(e==0)//if process ended
        {
            if(q!=0)/*if process is left in wait queue remove next process from wait queue and add  its wait time to total time*/
            {
                e=q->etime;
                cout<<"\n"<<q->name<<" started after a wait time of "<<q->waitt<<"time units\n";
                p++;
                wait+=pop(&q);
             }
        }
        delay(100);
        cout<<tt++<<"  ";//to show total time units since start of first process
    }while(q!=0||e!=0);//if process ended also no process in wait queue end loop
    cout<<"\n\nTotal no. of prcesses executed ="<<p;
    cout<<"\nTotal wait time for all prcesses executed ="<<wait;
    cout<<"\nAverage wait time for prcesses executed ="<<wait/(float)p;
    getch();
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Did you mean to tag this as [c]? This hardly looks like [c++] (except for cin and cout). \$\endgroup\$ – Jamal Feb 6 '14 at 20:06
  • \$\begingroup\$ I highly doubt this compiles. <iostream.h>? Calling cout and cin with no std:: or using namespace std;? Is this working code? \$\endgroup\$ – jliv902 Feb 6 '14 at 20:10
  • \$\begingroup\$ I was using the old turbo compiler \$\endgroup\$ – vidit jain Feb 6 '14 at 20:11
  • 2
    \$\begingroup\$ Several questions: Is this program your end-goal, or is this a starting point that you intend to expand off of later? If you want to study queueing behavior, why tie it to actual clock time by using delay? You'd do better to track simulated time and update it by the desired delay amount, e.g., simulated_time += 100; whenever there's something that involves delay in your model. I'd suggest using variable names that are more descriptive than e, p, q, t, or tt. Lose the inc function by storing the entry/arrival time in the queue rather than the wait: wait = time at pop - entry time. \$\endgroup\$ – pjs Feb 6 '14 at 20:47
  • 1
    \$\begingroup\$ Not really a C++ program. C with std::cout. Note: int main(void) is not a legal declaration for main. Use int main() \$\endgroup\$ – Martin York Feb 7 '14 at 17:21
11
\$\begingroup\$

I think this question would actually benefit from both a C review (just change the cout's to printf, etc) and a C++ review since you seem to be using a very C-orientated programming style.

This post will be a C++ review.
Please note that the Turbo C++ compiler is not available to me, so my suggestions will revolve around the C++98/03 standard.

My first bit of advice would be to switch to an object-oriented approach.
Turn process into a class and create a second class, process_queue.

In process, replace char name [32] with std::string name. This way, you don't have to worry about buffer overflows.

Refactor inc(), pop(), and addnode() into member functions for the new class process_queue.

Make pop() return a process instead of an int. This is because you have a queue of processs, not a queue of ints.

Rename inc() to something more readable like increment_all_wait_times(). That's a long name, but your code will be self-documenting.

Take out the user-input logic from inc(), pop(), and addnode().
This will improve their flexibility. A function should only do one thing, and do it well.

For function parameters, prefer the use of references over the use of pointers.
This will save you from having to check for NULL.

Here is an idea of what a process class might look like:

class process
{
public:
    process (const std::string &name, const int burst_time = 0, const int wait_time = 0) ;

    // getters
    std::string name () const ;
    int burst_time () const ;
    int wait_time () const ;
    const process* next () const ;
    process* next () ;

    void decrement_burst_time (const int time) ;

private:
    int burst_time_;
    int wait_time_;
    std::string name_;
    process *next_;

    friend  std::ostream& operator<< (std::ostream &os, const process &proc) ; 
    friend class process_queue ;
};

This would encapsulate your variables and (for the most part) make them read-only.
Because the process_queue class is tightly coupled with this class, I would make it a friend class. There are two versions of the next() method for the sake of const-correctness.

Here is an idea of what a process_queue class might look like:

class process_queue
{
public:
    process_queue () ;
    ~process_queue () ;

    bool empty () const ;
    void add_node (const process &proc) ;
    void increment_all_wait_times (const int wait) ;
    process pop () ;
    size_t size () const ;

    friend std::ostream & operator<< (std::ostream &os, const process_queue &pq) ;

private:
    size_t size_ ;
    process *head_;
    process *tail_; // for O(1) insertions
}; 

This, once again, encapsulates your variables while still providing useful functionality.

Here's what a constructor implementation might look like:

process::process (const std::string &name, const int burst_time, const int wait_time) 
    : name_ (name), burst_time_ (burst_time), wait_time_ (wait_time), next_ (NULL)
{
}

What you see here is a constructor initialization list. It is important to initialize your variables or else you may suffer from subtle bugs.

Here is a destructor for the process_queue class:

process_queue::~process_queue ()
{
    while (size_ > 0) {
        this->pop () ;
    }
}

This makes sure all of our resources (memory in this case) are cleaned up when an instance of this class goes out of scope. This strategy is called RAII. RAII is important for writing exception-safe code.

Here is an example implementation of all of the above combined (somewhat sloppily):

#include <iostream>
#include <string>
#include <stdexcept>

class process_queue ;

class process
{
public:
    process (const std::string &name, const int burst_time = 0, const int wait_time = 0) ;

    std::string name () const ;
    int burst_time () const ;
    int wait_time () const ;
    const process* next () const ;
    process* next () ;

    void decrement_burst_time (const int time) ;

private:
    int burst_time_;
    int wait_time_;
    std::string name_;
    process *next_;

    friend  std::ostream& operator<< (std::ostream &os, const process &proc) ; 
    friend class process_queue ;
};

process::process (const std::string &name, const int burst_time, const int wait_time) 
    : name_ (name), burst_time_ (burst_time), wait_time_ (wait_time), next_ (NULL)
{
}

std::string process::name () const
{
    return name_ ;
}

int process::burst_time () const
{
    return burst_time_ ;
}

int process::wait_time () const
{
    return wait_time_ ;
}

const process* process::next () const
{
    return next_ ;
}

process* process::next ()
{
    return next_ ;
}

void process::decrement_burst_time (const int time)
{
    burst_time_ -= time ;
}

std::ostream & operator<< (std::ostream &os, const process &proc)
{
    os  << "{Name = " << proc.name ()
        << ", Wait time = " << proc.wait_time ()
        << ", Burst time = " << proc.burst_time ()
        << ", Next = " ;

    if (proc.next () != NULL) {
        os << proc.next ()->name () ;
    }

    else {
        os << "None" ;
    }

    os << "}" ;

    return os ;
}

class process_queue
{
public:
    process_queue () ;
    ~process_queue () ;

    bool empty () const ;
    void add_node (const process &proc) ;
    void increment_all_wait_times (const int wait) ;
    process pop () ;
    size_t size () const ;

    friend std::ostream & operator<< (std::ostream &os, const process_queue &pq) ;

private:
    size_t size_ ;
    process *head_;
    process *tail_; // for O(1) insertions
};

process_queue::process_queue () : head_ (NULL), tail_ (NULL), size_ (0)
{
}

void process_queue::add_node (const process &proc)
{
    process *temp = new process (proc) ;

    if (tail_ != NULL) {
        tail_->next_ = temp ;

        if (head_ == tail_) {
            head_->next_ = temp ;
        }

        tail_ = tail_->next_ ;  
    }

    else {
        tail_ = temp ;
        head_ = tail_ ;
    }

    ++size_ ;
}

void process_queue::increment_all_wait_times (const int wait)
{
    process *temp = head_ ;

    while (temp != NULL) {
        temp->wait_time_ += wait ;
        temp = temp->next_ ;
    }
}

// Pops the head off.
process process_queue::pop ()
{
    if (head_ == NULL) {
        throw std::range_error ("process_queue::pop() called while the process_queue was empty.") ;
    }

    process ret = *head_ ;
    process *temp = head_ ;
    head_ = head_->next_ ;
    delete temp ;
    --size_ ;

    return ret ;
}

bool process_queue::empty () const
{
    return (size_ == 0) ;
}

size_t process_queue::size () const
{
    return size_ ;
}

std::ostream & operator<< (std::ostream &os, const process_queue &pq)
{
    process *temp = pq.head_ ;

    while (temp != NULL) {
        os << *temp << "\n" ;
        temp = temp->next () ;
    }

    return os ;
}

process_queue::~process_queue ()
{
    while (size_ > 0) {
        this->pop () ;
    }
}

namespace scheduler
{
    void run_first_come_first_serve (process_queue &pq)
    {
        std::cout << "Running first-come-first-serve scheduler with no preemption." "\n" ;

        while (pq.empty () == false) {
            process proc = pq.pop () ;

            std::cout << "Running " << proc.name () << "\n" ;

            std::cout << proc.name () << " finished running after " << (proc.burst_time () + proc.wait_time ()) << " ns." "\n" ; 
            pq.increment_all_wait_times (proc.burst_time ()) ;

            std::cout << "Queue:\n" << pq << "\n" ;
        }
    }
}

int main(void)
{
    process notepad ("notepad.exe", 500) ;
    process firefox ("firefox.exe", 1500) ;
    process excel ("excel.exe", 100) ;
    process visual_studio ("visual studio.exe", 200) ;
    process super_virus ("super virus.exe", 1000) ;

    process_queue pq ;
    pq.add_node (notepad) ;
    pq.add_node (firefox) ;
    pq.add_node (excel) ;
    pq.add_node (visual_studio) ;
    pq.add_node (super_virus) ;

    scheduler::run_first_come_first_serve (pq) ;

    return 0 ;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ That pretty good. The only difference I personally would make is removing all the getter functions. There is no need to expose the internal details of the class like this. You only use it for printing so create custom printing functions that have accesses to the internals (usually operator>> is a friend and can accesses the details anyway). By doing this you improve encapsulation. \$\endgroup\$ – Martin York Feb 7 '14 at 17:25
  • \$\begingroup\$ @LokiAstari How would the function declarations look like? Are you suggesting something like this: std::string print_burst_time() const or std::ostream& print_...? \$\endgroup\$ – jliv902 Feb 14 '14 at 15:37
  • \$\begingroup\$ The standard way to do it is: friend std::ostream& operator<<(std::ostream&, process const&) and friend std::istream& operator>>(std::istream&, process&) \$\endgroup\$ – Martin York Feb 14 '14 at 17:52
  • \$\begingroup\$ @LokiAstari I already overloaded those operators in this answer though. The only way to get rid of the getters that I can see would be to turn namespace scheduler into a class scheduler and have process be a friend class. I'm open to ideas though if you have a better way. \$\endgroup\$ – jliv902 Feb 14 '14 at 18:50
3
\$\begingroup\$

I'm going to assume that you just want to model the behavior of a first-come-first-served single-server queue and don't plan on extending it. If so, there's an almost trivial solution:

int number_entities = 100;
float arrival_time = 0.0, end_svc_time = 0.0, begin_svc_time;
for(int i = 0; i < number_entities; ++i) {
  arrival_time += interarrival_time();
  begin_svc_time = fmaxf(arrival_time, end_svc_time);
  end_svc_time = begin_svc_time + svc_time();
  /* delay in queue is begin_svc_time - arrival_time */
  /* delay in system is end_svc_time - arrival_time */
}

Basically, each customer arrives at a time determined by the prior arrival and your model of inter-arrival times. They can either begin service immediately if the prior customer is done, or have to wait until the prior customer's service gets completed. They finish and depart the system service-time time units after they begin. Lather, rinse, repeat.

The functions for interarrival_time() and svc_time() can be backed by any mechanism you like - constant or tabled values, values read in from one or more files, or random number generation.

If you don't want to run for a specified number of customers, replace the for with a time-based while.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.