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

How To Guides
Virtualization
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Windows
Problem Solutions

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

The ornamental garden

In this simulation, the garden committee would like to know how many people enter the garden each day through its multiple gates. Each gate has a turnstile or some other kind of counter, and after the turnstile count is incremented, a shared count is incremented that represents the total number of people in the garden.

//: C11:OrnamentalGarden.cpp {RunByHand}
#include <vector>
#include <cstdlib>
#include <ctime>
#include "Display.h"
using namespace std;

class Count : public Cancelable {
FastMutex lock;
int count;
bool paused, canceled;
public:
Count() : count(0), paused(false), canceled(false) {}
int increment() {
// Comment the following line to see counting fail:
Guard<FastMutex> g(lock);
int temp = count ;
if(rand() % 2 == 0) // Yield half the time
return (count = ++temp);
}
int value() {
Guard<FastMutex> g(lock);
return count;
}
void cancel() {
Guard<FastMutex> g(lock);
canceled = true;
}
bool isCanceled() {
Guard<FastMutex> g(lock);
return canceled;
}
void pause() {
Guard<FastMutex> g(lock);
paused = true;
}
bool isPaused() {
Guard<FastMutex> g(lock);
return paused;
}
};

class Entrance : public Runnable {
CountedPtr<Count> count;
CountedPtr<Display> display;
int number;
int id;
bool waitingForCancel;
public:
Entrance(CountedPtr<Count>& cnt,
CountedPtr<Display>& disp, int idn)
: count(cnt), display(disp), number(0), id(idn),
waitingForCancel(false) {}
void run() {
while(!count->isPaused()) {
++number;
{
ostringstream os;
os << *this << " Total: "
<< count->increment() << endl;
display->output(os);
}
}
waitingForCancel = true;
while(!count->isCanceled()) // Hold here...
ostringstream os;
os << "Terminating " << *this << endl;
display->output(os);
}
int getValue() {
while(count->isPaused() && !waitingForCancel)
return number;
}
friend ostream&
operator<<(ostream& os, const Entrance& e) {
return os << "Entrance " << e.id << ": " << e.number;
}
};

int main() {
srand(time(0)); // Seed the random number generator
cout << "Press <ENTER> to quit" << endl;
CountedPtr<Count> count(new Count);
vector<Entrance*> v;
CountedPtr<Display> display(new Display);
const int SZ = 5;
try {
for(int i = 0; i < SZ; i++) {
Entrance* task = new Entrance(count, display, i);
// Save the pointer to the task:
}
cin.get(); // Wait for user to press <Enter>
count->pause(); // Causes tasks to stop counting
int sum = 0;
vector<Entrance*>::iterator it = v.begin();
while(it != v.end()) {
sum += (*it)->getValue();
++it;
}
ostringstream os;
os << "Total: " << count->value() << endl
<< "Sum of Entrances: " << sum << endl;
display->output(os);
count->cancel(); // Causes threads to quit
} catch(Synchronization_Exception& e) {
cerr << e.what() << endl;
}
} ///:~

Count is the class that keeps the master count of garden visitors. The single Count object defined in main( ) as count is held as a CountedPtr in Entrance and thus is shared by all Entrance objects. A FastMutex called lock is used in this example instead of an ordinary Mutex because a FastMutex uses the native operating system mutex and will thus yield more interesting results.

A Guard is used with lock in increment( ) to synchronize access to count. This function uses rand( ) to cause a yield( ) roughly half the time, in between fetching count into temp and incrementing and storing temp back into count. Because of this, if you comment out the Guard object definition, you will rapidly see the program break because multiple threads will be accessing and modifying count simultaneously.

The Entrance class also keeps a local number with the number of visitors that have passed through this particular entrance. This provides a double-check against the count object to make sure that the proper number of visitors is being recorded. Entrance::run( ) simply increments number and the count object and sleeps for 100 milliseconds.

In main, a vector<Entrance*> is loaded with each Entrance that is created. After the user presses <Enter>, this vector is used to iterate over all the individual Entrance values and total them.

This program goes to quite a bit of extra trouble to shut everything down in a stable fashion. Part of the reason for this is to show just how careful you must be when terminating a multithreaded program, and part of the reason is to demonstrate the value of interrupt( ), which you will learn about shortly.

All the communication between the Entrance objects takes place through the single Count object. When the user presses <Enter>, main( ) sends the pause( ) message to count. Since each Entrance::run( ) is watching the count object to see whether it is paused, this causes each Entrance to move into the waitingForCancel state, where it is no longer counting, but it is still alive. This is essential because main( ) must still be able to safely iterate over the objects in the vector<Entrance*>. Note that because there is a slight possibility that the iteration might occur before an Entrance has finished counting and moved into the waitingForCancel state, the getValue( ) function cycles through calls to sleep( ) until the object moves into waitingForCancel. (This is one form of what is called a busy wait, which is undesirable. You ll see the preferred approach of using wait( ) later in the chapter.) Once main( ) completes its iteration through the vector<Entrance*>, the cancel( ) message is sent to the count object, and once again all the Entrance objects are watching for this state change. At this point, they print a termination message and exit from run( ), which causes each task to be destroyed by the threading mechanism.

As this program runs, you will see the total count and the count at each entrance displayed as people walk through a turnstile. If you comment out the Guard object in Count::increment( ), you ll notice that the total number of people is not what you expect it to be. The number of people counted by each turnstile will be different from the value in count. As long as the Mutex is there to synchronize access to the Counter, things work correctly. Keep in mind that Count::increment( ) exaggerates the potential for failure by using temp and yield( ). In real threading problems, the possibility for failure may be statistically small, so you can easily fall into the trap of believing that things are working correctly. Just as in the example above, there are likely to be hidden problems that haven t occurred to you, so be exceptionally diligent when reviewing concurrent code.

Atomic operations

Note that Count::value( ) returns the value of count using a Guard object for synchronization. This brings up an interesting point because this code will probably work fine with most compilers and systems without synchronization. The reason is that, in general, a simple operation such as returning an int will be an atomic operation, which means that it will probably happen in a single microprocessor instruction that will not get interrupted. (The multithreading mechanism is unable to stop a thread in the middle of a microprocessor instruction.) That is, atomic operations are not interruptible by the threading mechanism and thus do not need to be guarded.[152] In fact, if we removed the fetch of count into temp and removed the yield( ), and instead simply incremented count directly, we probably wouldn t need a lock because the increment operation is usually atomic, as well.[153]

The problem is that the C++ Standard doesn t guarantee atomicity for any of these operations. Although operations such as returning an int and incrementing an int are almost certainly atomic on most machines, there s no guarantee. And because there s no guarantee, you have to assume the worst. Sometimes you might investigate the atomicity behavior on a particular machine (usually by looking at assembly language) and write code based on those assumptions. That s always dangerous and ill-advised. It s too easy for that information to be lost or hidden, and the next person that comes along may assume that this code can be ported to another machine and then go mad tracking down the occasional glitch caused by thread collisions.

So, while removing the guard on Count::value( ) seems to work, it s not airtight, and thus on some machines you may see aberrant behavior.

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

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