The speedup is potential because, in the real world, there are always trade-offs. In order to have computational parallelism you need synchronization, which adds overhead. In order to overlap I/O with computation you again need synchronization in the form of I/O completion events.

Multi threading helps by hiding (but not eliminating) the complexity and the overhead associated with both types of parallelism. In the many cases where parallelism does help, programming with threads is a convenient way to use it.

High-level languages generally let you ignore the underlying machine, but parallel programming drags you back into worrying about what is really happening. On the other hand, you do have enough information in the declarations to help spot the potential problems. Variables that are declared at file scope and static data within functions clearly need to be protected from uncoordinated updates by multiple threads.

Less obviously, control data structures used by library packages need careful attention as well. Examples of these are the FILE structures used in the Standard C library and the dirent structures used in UNIX and POSIX. These data structures hold state information between calls. Problems may arise if they are used in more than one thread at the same time, or even alternately.

The same issues arise with member data in C++ classes. In the C library, something has to be done for errno, stdin, stdout, and stderr (at least), to make them thread-safe. In C++, the analogous structures are cin, cout, cerr, and clog.

• provide locking in order to synchronize updates
• eliminate the problem by making the variable thread private

Locks should be associated with the data, not the code. Locking code that happens to access shared variables may overly limit parallelism. For example, in an operating system one has to lock the global run queue or task data during updates, but one should avoid having a scheduler lock. The latter approach results in a system that may be thread-safe, but it will be slower than the original, single-threaded version. The trade-off one makes is to implement enough fine-grained locking to maximize parallelism without adding too much overhead.

Besides adding to the overhead of even a single-threaded program, locking introduces the problem of deadlock. Deadlock can be avoided by recognizing the hierarchical structure of the data, and obtaining locks in a strict order. However, this requires global knowledge of all data, which may be impossible in a modular system, such as a third-party library.

Thread-private data may be supported explicitly by the compiler, if you're lucky. But there are routines in each thread package that provide for thread-private data, because it is indispensable. In POSIX threads, the routines are pthread_keycreate, pthread_getspecific, and pthread_setspecific. These routines implement an associative memory, in which a shared key is associated with a thread-specific pointer.

The easiest form of thread-private storage to use is the stack. Each thread has its own stack, therefore all automatic variables are thread-safe. You can also place a data structure in thread-private storage by using malloc (in C) or new (in C++) to allocate the storage, then storing the pointer in thread-specific data. When a new thread is created, its specific data pointers are set to null. Knowing this, the program can tell at runtime when to allocate and initialize another instance of the data structure. Therefore, not every thread needs a copy of every data structure. pthread_keycreate registers a destructor function to be called for each key when the thread exits. This function may free the storage and otherwise clean things up.

It's best to make variables thread-private whenever possible. The access cost of thread-specific data is much less compared to lock/unlock overhead, and the associated code can be written using the simpler, uni processor model.

Sometimes global shared variables can be used in a multi-threaded program without additional protection. For example, a Boolean variable used as a flag can be set or cleared without synchronization. The code sequence:

lock;
flag = 1;
unlock

Statistics counters employ another kind of update which may go unprotected. An expression like ++count is a multi-step update of a global variable, and is a candidate for locking. But if all you ever care about are zero/non-zero values of the count, no harm will result even if multiple processors collide on an update. (The value will be at least 1.) This is worth mentioning because test coverage tools often insert such counters. It is seldom worth the trouble to make these tools thread-safe.

If the threads are to be cooperating, meaning they produce or consume the same stream of data, then the data must have internal locking and external synchronization. In this model, the POSIX opendir/readdir facility, for example, would operate with a shared data structure. An application would want to have threads alternately read or write directory entries.

Each independent thread, on the other hand, would produce or consume its own stream of data. In this case, the buffering would be thread-private, and there would be no need for internal locking. Either approach is viable, it just depends upon the application. But what is the library writer supposed to do? The answer may be to supply both.

Second, C++ uses an internal list to keep track of sizes of arrays of objects. This is due to the fact that C++ lets you say

delete [] array-ref

An important issue is whether I/O streams be thread-private or shared. Given the nature of the interface, which is to perform I/O by the character, word, or line, it doesn't do much good to provide locking within the interface functions. For example, one thread may print hello and another print world, but the screen output will be jumbled anyway unless the threads coordinate their outputs in some way outside of the I/O library. Adding locking within each I/O primitive call (inside the interface) will make the I/O library thread-safe. Indeed, this was the approach taken for POSIX threads. The problem is that it introduces a lot of overhead in the interest of safety.

Alternatively, you could establish the rule that I/O streams are thread-private. Cooperating threads will need to synchronize outside of the interface. (Maybe they would have to anyway.) Independent threads would read or write streams as efficiently as in the single-threaded case.

Given this rule, the library only has to concern itself with the streams it provides initially, namely: cin, cout, cerr, and clog. In C++, it's fairly easy to provide a "wrapper class" that can operate on a thread-private version of the original class.

extern ostream_withassign cout;// stream declaration
extern t_ostream_withassign __tcout;// stream wrapper
#define cout (__tcout.ref())

The wrapper is a very small class that defines a static object (such as __tcout) which is shared by all threads. The static initializer does three things:

• It allocates a key to access thread-private storage.
• It stores the stream-initialization parameters it will need later.
• It points the wrapper at the corresponding global stream.

A pointer to the wrapper class is stored in thread-private storage. This pointer is later presented as an argument to the destructor function called by thread-exit processing. Therefore, the thread-private wrapper object and its stream object are deleted when the thread exits.

The ref member function simply uses the key stored in the static object and tries to look up the thread-private pointer to the wrapper. The very first time a new thread calls any I/O function, ref will find that its thread-private pointer is null. When the pointer is null, ref allocates a new wrapper object and a new stream, then stores the pointer to its wrapper object in thread-private storage. Subsequently, ref returns a reference to the stream object assocated with the wrapper object, both of which are private to the thread.

With this implementation, only threads that use stream I/O get copies of stream objects. Threads can be created at any time, since I/O stream allocation occurs on demand. The main cost added to implement thread-private streams is one lookup in thread-private storage for every I/O call. This is much cheaper than adding lock/unlock to every I/O call.

extern t_ostream_withassign cout

operator ostream_withassign&() {return ref();}

I tried this and it mostly works, but the following limitations were found:

Invocations of member functions didn't work. For example, cout.flush() had to be transformed to ((ostream_withassign&)(cout)).flush(). Here is a case where it would be nice to be able to overload the dot operator. Then you could say:

ostream_withassign& operator.()
   {return ref();}

The compiler complains when the expression in a return statement does not match the function's declaration. For example:

ostream_withassign& f()
   {return cout;}

There is a similar warning when the type of an initializer does not match the type of the variable being initialized. For example,

ostream_withassign &os = cout

The list is protected with simple, mutual exclusion, using pthread_mutex_lock and pthread_mutex_unlock in the underlying implementation. The list-handling file has a definition at file scope like

static_thread_lock_def list_lock;

The body of the code where mutual exclusion is needed has the syntax:

{ thread_lock L(list_lock);
   // do something to the list
} //end of critical region

This could be considered just another stupid C++ trick except that, should there be a return or an exception within the region, the destructor for L will be called, which will release the lock. Thus, locking is integrated with returns and exceptions because of this method.

There is a quiet gotcha in this implementation. Should you forget to supply a variable name (in this case it's L), and write thread_lock(list_lock), C++ will lock then immediately unlock list_lock, leaving the critical region unprotected.

The reason there is no warning has something to do with the great debate over the lifetime of temporaries. For example, in a simple expression like X + Y the compiler may have to make temporary copies of intermediate results, which one would expect to get deleted at the end of the expression, not at the end of the current scope. See your local language lawyer for details.

• C++ is very close to being thread-safe, except for some potential uses of I/O streams and arrays of objects.
• Making global data thread-private is more efficient than adding locking.
• I/O streams should be thread-private, because the shared use of a stream requires external coordination anyway.
• Uniform application of user-defined type conversion coupled with the ability to overload the dot operator would be useful extensions. This would aid in the creation of wrapper classes for indirect access to any object.
• Locking based upon C++ scoping rules integrates locking with exceptions.