Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |
The queue container is a restricted form of a deque you
can only enter elements at one end and pull them off the other end.
Functionally, you could use a deque anywhere you need a queue,
and you would then also have the additional functionality of the deque.
The only reason you need to use a queue rather than a deque,
then, is when you want to emphasize that you will only be performing queue-like
behavior.
The queue class is an adaptor like stack, in
that it is built on top of another sequence container. As you might guess, the
ideal implementation for a queue is a deque, and that is the
default template argument for the queue; you ll rarely need a different
implementation.
Queues are often used if you want to model a system where
some elements are waiting to be served by other elements in the system. A
classic example of this is the bank-teller problem. Customers arrive at
random intervals, get into a line, and then are served by a set of tellers.
Since the customers arrive randomly and each takes a random amount of time to
be served, there s no way to deterministically know how long the line will be
at any time. However, it s possible to simulate the situation and see what
happens.
In a realistic simulation each customer and teller should be
run by a separate thread. What we d like is a multithreaded environment so that
each customer or teller would have his own thread. However, Standard C++ has no
support for multithreading. On the other hand, with a little adjustment to the
code, it s possible to simulate enough multithreading to provide a satisfactory
solution.
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.
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. Here,
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 {RunByHand}
// Using a queue and simulated multithreading
// to model a bank teller system.
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <iterator>
#include <list>
#include <queue>
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<Customer>& customers;
Customer current;
enum { SLICE = 5 };
int ttime; // Time left in slice
bool busy; // Is teller serving a customer?
public:
Teller(queue<Customer>& 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<Customer> {
public:
friend ostream&
operator<<(ostream& os, const
CustomerQ& cd) {
copy(cd.c.begin(), cd.c.end(),
ostream_iterator<Customer>(os,
""));
return os;
}
};
int main() {
CustomerQ customers;
list<Teller> tellers;
typedef list<Teller>::iterator TellIt;
tellers.push_back(Teller(customers));
srand(time(0)); // Seed the 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. 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<Customer>,
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.
Just as with a stack, when you use a queue,
it s only a queue and doesn t have any of the other functionality of the
basic sequence containers. This includes the ability to get an iterator in
order to step through the stack. However, the underlying sequence
container (that the queue is built upon) is held as a protected
member inside the queue, and the identifier for this member is specified
in the C++ Standard as c , which means that you can derive from queue
to access the underlying implementation. The CustomerQ class does
exactly that, for the sole purpose of defining an ostream operator<<
that can iterate through the queue and display its members.
The driver for the simulation is the while loop in main( ),
which uses processor ticks (defined in <ctime>) to determine if
the simulation has run for at least 5 seconds. At the beginning of each pass
through the loop, a random number of customers is added, with random service
times. Both the number of tellers and the queue contents are displayed so you
can see the state of the system. After running each teller, the display is
repeated. At this point, the system adapts by comparing the number of customers
and the number of tellers. If the line is too long, another teller is added,
and if it is short enough, a teller can be removed. In this adaptation section
of the program you can experiment with policies regarding the optimal addition
and removal of tellers. If this is the only section that you re modifying, you
might want to encapsulate policies inside different objects.
We ll revisit this example in a multithreaded exercise in
Chapter 11.
Thinking in C++ Vol 2 - Practical Programming |
Prev |
Home |
Next |