Thinking In C++. Volume 2: Practical Programming

In multithreading, multiple threads of control run simultaneously, sharing the same address space. Quite often you have fewer CPUs than you do threads (and often only one CPU). To give the illusion that each thread has its own CPU, a time-slicing mechanism says "OK, current thread, you’ve had enough time. I’m going to stop you and give time to some other thread." This automatic stopping and starting of threads is called preemptive, and it means you (the programmer) don’t need to manage the threading process at all.

An alternative approach has each thread voluntarily yield the CPU to the scheduler, which then finds another thread that needs running. Instead, we’ll build the "time-slicing" into the classes in the system. In this case, it will be the tellers that represent the "threads," (the customers will be passive). Each teller will have an infinite-looping run( ) member function that will execute for a certain number of "time units" and then simply return. By using the ordinary return mechanism, we eliminate the need for any swapping. The resulting program, although small, provides a remarkably reasonable simulation:

//: C07:BankTeller.cpp

// Using a queue and simulated multithreading

// To model a bank teller system

#include

#include

#include

#include

#include

#include

using namespace std;

class Customer {

  int serviceTime;

public:

  Customer() : serviceTime(0) {}

  Customer(int tm) : serviceTime(tm) {}

  int getTime() { return serviceTime; }

  void setTime(int newtime) {

    serviceTime = newtime;

  }

  friend ostream&

  operator<<(ostream& os, const Customer& c) {

    return os << '[' << c.serviceTime << ']';

  }

};

class Teller {

  queue& customers;

  Customer current;

  enum { slice = 5 };

  int ttime; // Time left in slice

  bool busy; // Is teller serving a customer?

public:

  Teller(queue& cq)

    : customers(cq), ttime(0), busy(false) {}

  Teller& operator=(const Teller& rv) {

    customers = rv.customers;

    current = rv.current;

    ttime = rv.ttime;

    busy = rv.busy;

    return *this;

  }

  bool isBusy() { return busy; }

  void run(bool recursion = false) {

    if(!recursion)

      ttime = slice;

    int servtime = current.getTime();

    if(servtime > ttime) {

      servtime -= ttime;

      current.setTime(servtime);

      busy = true; // Still working on current

      return;

    }

    if(servtime < ttime) {

      ttime -= servtime;

      if(!customers.empty()) {

        current = customers.front();

        customers.pop(); // Remove it

        busy = true;

        run(true); // Recurse

      }

      return;

    }

    if(servtime == ttime) {

      // Done with current, set to empty:

      current = Customer(0);

      busy = false;

      return; // No more time in this slice

    }

  }

};

// Inherit to access protected implementation:

class CustomerQ : public queue {

public:

  friend ostream&

  operator<<(ostream& os, const CustomerQ& cd) {

    copy(cd.c.begin(), cd.c.end(),

      ostream_iterator(os, ""));

    return os;

  }

};

int main() {

  CustomerQ customers;

  list tellers;

  typedef list::iterator TellIt;

  tellers.push_back(Teller(customers));

  srand(time(0)); // Seed random number generator

  clock_t ticks = clock();

  // Run simulation for at least 5 seconds:

  while(clock() < ticks + 5 * CLOCKS_PER_SEC) {

    // Add a random number of customers to the

    // queue, with random service times:

    for(int i = 0; i < rand() % 5; i++)

      customers.push(Customer(rand() % 15 + 1));

    cout << '{' << tellers.size() << '}'

      << customers << endl;

    // Have the tellers service the queue:

    for(TellIt i = tellers.begin();

      i != tellers.end(); i++)

      (*i).run();

    cout << '{' << tellers.size() << '}'

      << customers << endl;

    // If line is too long, add another teller:

    if(customers.size() / tellers.size() > 2)

      tellers.push_back(Teller(customers));

    // If line is short enough, remove a teller:

    if(tellers.size() > 1 &&

      customers.size() / tellers.size() < 2)

      for(TellIt i = tellers.begin();

        i != tellers.end(); i++)

        if(!(*i).isBusy()) {

          tellers.erase(i);

          break; // Out of for loop

        }

  }

} ///:~

Each customer requires a certain amount of service time, which is the number of time units that a teller must spend on the customer to serve that customer’s needs. Of course, the amount of service time will be different for each customer and will be determined randomly. In addition, you won’t know how many customers will be arriving in each interval, so this will also be determined randomly^.

The Customer objects are kept in a queue, and each Teller object keeps a reference to that queue. When a Teller object is finished with its current Customer object, that Teller will get another Customer from the queue and begin working on the new Customer, reducing the Customer’s service time during each time slice that the Teller is allotted. All this logic is in the run( ) member function, which is basically a three-way if statement based on whether the amount of time necessary to serve the customer is less than, greater than, or equal to the amount of time left in the teller’s current time slice. Notice that if the Teller has more time after finishing with a Customer, it gets a new customer and recurses into itself^.