Follow Techotopia on Twitter

On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
System/Network Admin
Programming
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Databases
Mail Systems
openSolaris
Eclipse Documentation
Techotopia.com
Virtuatopia.com
Answertopia.com

How To Guides
Virtualization
General System Admin
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Windows
Problem Solutions
Privacy Policy

  




 

 

Thinking in C++ Vol 2 - Practical Programming
Prev Home Next

queue

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.[109]

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

 
 
   Reproduced courtesy of Bruce Eckel, MindView, Inc. Design by Interspire