First-come first-serve job scheduling algorithm

Question

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;
}

Answer 1

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 ;
}

Answer 2

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.