Blog Archive

Happy New Year 2011

Thursday, 13 January 2011

It's nearly two weeks into 2011 already (though it only seems a couple of days — where did it all go?), but I'd like to wish you all a (slightly belated) Happy New Year!

2010 was a good year for me. Sales of Just::Thread, my implementation of the C++0x thread library have been growing steadily — there's a new version due out any day now, with support for the changes accepted at the November 2010 C++ Standards meeting, and Just::Thread Pro is in the works. I also presented at the ACCU conference for the third year running.

It's also been a big year for the C++ community:

  • the C++0x FCD was published, and we're now in the final phase of getting it ready for publication this year;
  • Microsoft Visual Studio 2010 was released, providing Windows developers access to several C++0x features such as rvalue references and lambda functions;
  • g++ 4.5 was released, providing further C++0x support (including lambdas, again) to C++ developers across the wide variety of platforms supported by gcc;
  • Plus, of course, new versions of other compilers and libraries too (including four(!) releases of the Boost C++ libraries).

Popular articles

As is my custom, here's a list of the 10 most popular articles and blog entries from the Just Software Solutions website in 2010. The key difference from last year's list is the rise of the C++0x thread library stuff.

  1. November 2010 C++ Standards Committee Mailing
    My summary of the November 2010 C++ committee mailing.
  2. Implementing a Thread-Safe Queue using Condition Variables
    A description of the issues around writing a thread-safe queue, with code.
  3. just::thread C++0x Thread Library V1.0 Released
    This is the release announcement for our just::thread C++0x thread library.
  4. Importing an Existing Windows XP Installation into VirtualBox
    This article describes how I recovered the hard disk of a dead laptop to run as a VM under VirtualBox.
  5. Deadlock Detection with just::thread
    This article describes how to use the special deadlock-detection mode of our just::thread C++0x thread library to locate the cause of deadlocks.
  6. Implementing drop-down menus in pure CSS (no JavaScript)
    How to implement drop-down menus in CSS in a cross-browser fashion (with a teensy bit of JavaScript for IE).
  7. Multithreading in C++0x part 1: Starting Threads
    This is the first part of my series on the new C++0x thread library. Links to the remaining parts are at the end of the article.
  8. Thread Interruption in the Boost Thread Library
    A description of the thread interruption feature of the Boost Thread library.
  9. Introduction to C++ Templates
    My basic introduction to C++ templates.
  10. October 2010 C++ Standards Committee Mailing
    My summary of the October 2010 C++ committee mailing, and the big issues for discussion at the November 2010 meeting — implicit move functions and noexcept for destructors.

What's coming in 2011?

Will 2011 be even better than 2010? I hope so. As I already mentioned, there's a new version of just::thread coming soon, along with Just::Thread Pro. Also, both the C++0x standard and my book should finally be published. I'll also be presenting at ACCU 2011 in April — hope to see you there.

What are you looking forward to in 2011?

Posted by Anthony Williams
[/ news /] permanent link
Tags: ,

| Stumble It! stumbleupon logo | Submit to Reddit reddit logo | Submit to DZone dzone logo

Comment on this post

If you liked this post, why not subscribe to the RSS feed RSS feed or Follow me on Twitter? You can also subscribe to this blog by email using the form on the right.

November 2010 C++ Standards Committee Mailing

Tuesday, 07 December 2010

The November 2010 mailing for the C++ Standards Committee was published last week. This is the post-meeting mailing for the November 2010 committee meeting.

As well as the usual core and library issues lists, this mailing also includes an updated summary of the status of the FCD comments, along with a whole host of papers attempting to address some the remaining FCD comments and a new C++0x working draft.

To move or not to move

In my blog post on the October mailing, I mentioned that the implicit generation of move constructors was a big issue. I even contributed a paper with proposed wording for removing implicit move generation from the draft — with expert core wording guidance from Jason Merrill, this became N3216. My paper was just to give the committee something concrete to vote on — it doesn't matter how good your arguments are; if there isn't a concrete proposal for wording changes then the committee can't vote on it. In the end, the decision was that implicit move generation was a good thing, even though there was the potential for breaking existing code. However, the conditions under which move operations are implicitly generated have been tightened: the accepted proposal was N3203: Tightening the conditions for generating implicit moves by Jens Maurer, which provides wording for Bjarne's paper N3201: Moving Right Along. The proposal effectively treats copy, move and destruction as a group: if you specify any of them manually then the compiler won't generate any move operations, and if you specify a move operation then the compiler won't generate a copy. For consistency and safety, it would have been nice to prevent implicit generation of copy operations under the same circumstances, but for backwards compatibility this is still done when it would be done under C++03, though this is deprecated if the user specifies a destructor or only one of the copy operations.

Exceptions and Destructors

The second big issue from the October mailing was the issue of implicitly adding noexcept to destructors. In the end, the committee went for Jens Maurer's paper N3204: Deducing "noexcept" for destructors — destructors have the same exception specification they would have if they were implicitly generated, unless the user explicitly says otherwise. This will break code, but not much — the fraction of code that intentionally throws an exception from a destructor is small, and easily annotated with noexcept(false) to fix it.

Concurrency-related papers

There are 9 concurrency-related papers in this mailing, which I've summarised below. 8 of them were adopted at this meeting, and are now in the new C++0x working draft.

N3188 - Revision to N3113: Async Launch Policies (CH 36)

This paper is a revision of N3113 from the August mailing. It is a minor revision to the previous paper, which clarifies and simplifies the proposed wording.

It provides a clearer basis for implementors to supply additional launch policies for std::async, or for the committee to do so in a later revision of the C++ standard, by making the std::launch enum a bitmask type. It also drops the std::launch::any enumeration value, and renames std::launch::sync to std::launch::deferred, as this better describes what it means.

The use of a bitmask allows new values to be added which are either distinct values, or combinations of the others. The default policy for std::async is thus std::launch::async|std::launch::deferred.

N3191: C++ Timeout Specification

This paper is a revision of N3128: C++ Timeout Specification from the August mailing. It is a minor revision to the previous paper, which clarifies and simplifies the proposed wording.

There are several functions in the threading portion of the library that allow timeouts, such as the try_lock_for and try_lock_until member functions of the timed mutex types, and the wait_for and wait_until member functions of the future types. This paper clarifies what it means to wait for a specified duration (with the xxx_for functions), and what it means to wait until a specified time point (with the xxx_until functions). In particular, it clarifies what can be expected of the implementation if the clock is changed during a wait.

This paper also proposes replacing the old std::chrono::monotonic_clock with a new std::chrono::steady_clock. Whereas the only constraint on the monotonic clock was that it never went backwards, the steady clock cannot be adjusted, and always ticks at a uniform rate. This fulfils the original intent of the monotonic clock, but provides a clearer specification and name. It is also tied into the new wait specifications, since waiting for a duration requires a steady clock for use as a basis.

N3192: Managing C++ Associated Asynchronous State

This paper is a revision of N3129: Managing C++ Associated Asynchronous State from the August mailing. It is a minor revision to the previous paper, which clarifies and simplifies the proposed wording.

This paper tidies up the wording of the functions and classes related to the future types, and clarifies the management of the associated asynchronous state which is used to communicate e.g. between a std::promise and a std::future that will receive the result.

N3193: Adjusting C++ Atomics for C Compatibility

This paper is an update to N3164: Adjusting C++ Atomics for C Compatibility from the October mailing.

It drops the C compatibility header <stdatomic.h>, and the macro _Atomic, and loosens the requirements on the atomic_xxx types — they may be base classes of the associated atomic<T> specializations, or typedefs to them.

N3194: Clarifying C++ Futures

This paper is a revision ofN3170: Clarifying C++ Futures from the October mailing.

There were a few FCD comments from the US about the use of futures; this paper outlines all the issues and potential solutions. The proposed changes are actually fairly minor though:

  • future gains a share() member function for easy conversion to the corresponding shared_future type;
  • Accessing a shared_future for which valid() is false is now encouraged to throw an exception though it remains undefined behaviour;
  • atomic_future is to be removed;
  • packaged_task now has a valid() member function instead of operator bool for consistency with the future types.

A few minor changes have also been made to the wording to make things clearer.

N3196: Omnibus Memory Model and Atomics Paper

This paper is an update to N3125: Omnibus Memory Model and Atomics Paper from the August mailing.

This paper clarifies the wording surrounding the memory model and atomic operations.

N3197: Lockable Requirements for C++0x

This paper is an update to N3130: Lockable Requirements for C++0x from the October mailing. This is a minor revision reflecting discussions at Batavia.

This paper splits out the requirements for general lockable types away from the specific requirements on the standard mutex types. This allows the lockable concepts to be used to specify the requirements on a type to be used the the std::lock_guard and std::unique_lock class templates, as well as for the various overloads of the wait functions on std::condition_variable_any, without imposing the precise behaviour of std::mutex on user-defined mutex types.

N3209: Progress guarantees for C++0x (US 3 and US 186)(revised)

This paper is a revision ofN3152: Progress guarantees for C++0x (US 3 and US 186) from the October mailing. It is a minor revision to the previous paper, which extends the proposed wording to cover compare_exchange_weak as well as try_lock.

The FCD does not make any progress guarantees when multiple threads are used. In particular, writes made by one thread do not ever have to become visible to other threads, and threads aren't guaranteed ever to actually run at all. This paper looks at the issues and provides wording for minimal guarantees.

N3230: Constexpr Library Additions: future

This paper has not yet been accepted by the committee. It adds constexpr to the default constructors of future and shared_future, so that they can be statically initialized.

Other adopted papers

Of course, the committee did more than just address implicit move, exceptions in destructors and concurrency. The full minutes are available as N3212 in the mailing. Here is a quick summary of some of the other changes made:

  • Library functions that don't throw exceptions have been changed to use noexcept
  • The ratio arithmetic facilities have been changed to allow libraries to try and give the correct result if the result is representable, but the intermediate calculations may overflow (e.g. ratio_add<ratio<1,INTMAX_MAX>,ratio<1,INTMAX_MAX>>) (N3210)
  • New functions have been added to retrieve the current new handler, terminate handler or unexpected handler (N3189)
  • Alignment control is now done with the alignas keyword, rather than an attribute (N3190)
  • Virtual function override control is now done with keywords (including the first context sensitive keywords: override amd final) rather than attributes (N3206)

For the remaining changes, see the full minutes.

FCD comment status

The count of unresolved FCD comments is dropping rapidly, and now stands at 75 (out of 564 total), of which only 56 have any technical content. See N3224: C++ FCD Comment Status from the mailing for the full list.

Your comments

If you have any opinions on any of the papers listed here, or the resolution of any NB comments, please add them to the comments for this post.

Posted by Anthony Williams
[/ cplusplus /] permanent link
Tags: , , ,

| Stumble It! stumbleupon logo | Submit to Reddit reddit logo | Submit to DZone dzone logo

Comment on this post

If you liked this post, why not subscribe to the RSS feed RSS feed or Follow me on Twitter? You can also subscribe to this blog by email using the form on the right.

Coming Soon: Just::Thread Pro

Friday, 29 October 2010

Sign up to find out more about Just::Thread Pro

Multithreaded code doesn't have to be complicated.

That's the idea behind the Just::Thread Pro library. By providing a set of high level facilities in the library, your application code can be simplified — rather than spending your time on the complexities of multithreading and concurrency you can instead focus on what it is your application is trying to achieve.

Building on the Just::Thread C++0x thread library, Just::Thread Pro will provide facilities to:

  • Encapsulate communication between threads to avoid deadlocks and race conditions
  • Easily scale your application to make use of multi-core processors
  • Parallelize existing single-threaded code without a major rewrite

Just::Thread Pro will be available for all platforms supported by Just::Thread.

Head over to the Just::Thread Pro website and sign up to receive further news about the library and notification when it is released.

Posted by Anthony Williams
[/ news /] permanent link
Tags: , ,

| Stumble It! stumbleupon logo | Submit to Reddit reddit logo | Submit to DZone dzone logo

Comment on this post

If you liked this post, why not subscribe to the RSS feed RSS feed or Follow me on Twitter? You can also subscribe to this blog by email using the form on the right.

October 2010 C++ Standards Committee Mailing

Thursday, 21 October 2010

The October 2010 mailing for the C++ Standards Committee was published earlier this week. This is the pre-meeting mailing for the November 2010 committee meeting.

As well as the usual core and library issues lists, this mailing also includes a Summary of the status of the FCD comments, along with a whole host of papers attempting to address some the remaining FCD comments.

To move or not to move

The big issue of the upcoming meeting is looking to be whether or not the compiler should implicitly generate move constructors and move assignment operators akin to the copy constructors and copy assignment operators that are currently auto generated. The wording in the FCD requires this, but people are concerned that this will break existing code when people start using their code with a C++0x compiler and library. There are two papers on the subject in the mailing: N3153: Implicit Move Must Go by Dave Abrahams, and N3174: To move or not to move by Bjarne Stroustrup.

There seems to be consensus among committee members that the FCD requires compilers to generate the move constructor and move assignment operator in cases that will break existing code. The key question is whether the breakage can be limited by restricting the cases in which the move members are implicitly generated, or whether implicit generation should be abandoned altogether. The various options are explained very clearly in the papers.

Exceptions and Destructors

N3166: Destructors default to noexcept is another potentially controversial issue. It is generally acknowledged that throwing exceptions from destructors is a bad idea, not least because this leads to termination if the destructor is invoked whilst the stack is being unwound due to another exception. Herb Sutter wrote about this way back in 1998 when the original C++ standard was hot off the presses, in GotW #47: Uncaught Exceptions.

The proposal in the paper comes from a Finnish comment on the FCD, and is quite simple: by default all destructors are assumed to be marked noexcept(true) (which is the new way of saying they cannot throw an exception, similar to an exception specification of throw()), unless they explicitly have a non-empty exception specification or are marked noexcept(false).

Since it is generally good practice not to throw from a destructor, you'd think this would be uncontroversial. Unfortunately it is not the case — there are currently situations where throwing from a destructor has defined behaviour, and even does exactly what people want. The example most frequently cited is the SOCI project for accessing databases from C++. This library provides an easy syntax for constructing SQL queries using the << operator. The operator builds a temporary object which executes the SQL in the destructor. If the SQL is invalid, or executing it causes an exception for any other reason then the destructor throws. Changing destructors to be noexcept(true) by default will make such code terminate on a database error unless the destructor is updated to declare that it can throw exceptions. Working code with defined behaviour is thus broken when recompiled with a C++0x compiler.

Concurrency-related papers

There are 3 concurrency-related papers in this mailing, which I've summarised below.

N3152: Progress guarantees for C++0x (US 3 and US 186)

The FCD does not make any progress guarantees when multiple threads are used. In particular, writes made by one thread do not ever have to become visible to other threads, and threads aren't guaranteed ever to actually run at all. This paper looks at the issues and provides wording for minimal guarantees.

N3164: Adjusting C++ Atomics for C Compatibility

This is an update to N3137 from the last mailing, which provides detailed wording updates for the required changes to regain compatibility with C1X atomics.

N3170: Clarifying C++ Futures

There were a few FCD comments from the US about the use of futures; this paper outlines all the issues and potential solutions. The proposed changes are actually fairly minor though:

  • future gains a share() member function for easy conversion to the corresponding shared_future type;
  • Accessing a shared_future for which valid() is false is now required to throw an exception rather than be undefined behaviour;
  • atomic_future is to be removed;

A few minor changes have also been made to the wording to make things clearer.

If you have any opinions on any of the papers listed here, or the resolution of any NB comments, please add them to the comments for this post.

Posted by Anthony Williams
[/ cplusplus /] permanent link
Tags: , , ,

| Stumble It! stumbleupon logo | Submit to Reddit reddit logo | Submit to DZone dzone logo

Comment on this post

If you liked this post, why not subscribe to the RSS feed RSS feed or Follow me on Twitter? You can also subscribe to this blog by email using the form on the right.

just::thread C++0x Thread Library V1.4.2 Released

Friday, 15 October 2010

I am pleased to announce that version 1.4.2 of just::thread, our C++0x Thread Library has just been released.

The big change with this release is the new support for gcc 4.5 on Ubuntu Linux. If you're running Ubuntu Lucid then you can get the .DEB files for gcc 4.5 from yesterday's blog post. For Ubuntu Maverick, gcc 4.5 is in the repositories.

Other changes:

  • Overflow in ratio arithmetic will now cause a compilation failure
  • Ratio arithmetic operations derive from the resulting std::ratio instantiation as well as providing the ::type member to better emulate the C++0x working draft
  • On Windows, just::thread can now be used in MFC DLLs
Purchase your copy and get started with the C++0x thread library now.

As usual, existing customers are entitled to a free upgrade to V1.4.2 from all earlier versions.

Posted by Anthony Williams
[/ news /] permanent link
Tags: , ,

| Stumble It! stumbleupon logo | Submit to Reddit reddit logo | Submit to DZone dzone logo

Comment on this post

If you liked this post, why not subscribe to the RSS feed RSS feed or Follow me on Twitter? You can also subscribe to this blog by email using the form on the right.

gcc 4.5 Packages for Ubuntu Lucid

Thursday, 14 October 2010

Ubuntu Maverick was released earlier this week. Amongst other things, gcc 4.5 is available in the repositories, whereas for previous versions you had to build it yourself from source.

In order to save you the pain of compiling gcc 4.5 for yourself (which can take a while, and overheated my laptop when I tried), I've built it for Ubuntu Lucid, and uploaded the .deb files to my website. The .debs are built from the Maverick source packages for gcc 4.5.1, binutils 2.20.51, cloog-ppl and mpclib, and I've built them for both i386 and amd64 architectures.

Enjoy!

Posted by Anthony Williams
[/ news /] permanent link
Tags: , ,

| Stumble It! stumbleupon logo | Submit to Reddit reddit logo | Submit to DZone dzone logo

Comment on this post

If you liked this post, why not subscribe to the RSS feed RSS feed or Follow me on Twitter? You can also subscribe to this blog by email using the form on the right.

Concept Checking Without C++0x Concepts

Wednesday, 06 October 2010

My latest article, Concept Checking Without Concepts in C++ was published on the Dr Dobb's website a couple of weeks ago.

One of the important features of the now-defunct C++0x Concepts proposal was the ability to overload functions based on whether or not their arguments met certain concepts. This article describes a way to allow that for concepts based on the presence of particular member functions.

The basic idea is that you can write traits classes that detect particular sets of member functions. Function overloads that require these concepts can then be enabled or disabled by using std::enable_if with these traits.

The example I use is checking for a Lockable type which has lock(), unlock() and try_lock() member functions, but the same technique could easily be used for other concepts that required other member functions.

Read the article for the full details.

Posted by Anthony Williams
[/ news /] permanent link
Tags: ,

| Stumble It! stumbleupon logo | Submit to Reddit reddit logo | Submit to DZone dzone logo

Comment on this post

If you liked this post, why not subscribe to the RSS feed RSS feed or Follow me on Twitter? You can also subscribe to this blog by email using the form on the right.

August 2010 C++ Standards Committee Mailing

Wednesday, 08 September 2010

The August 2010 mailing for the C++ Standards Committee was published recently. This is the post-meeting mailing for the August 2010 committee meeting, and contains a new C++0x Working Draft. At the meeting in August, the committee discussed many of the National Body comments on the FCD, and this draft incorporates those changes that the committee approved of. As you can see from the FCD Comment Status document in this mailing, there were 301 technical comments and a further 215 editorial comments. Of these, 98 technical comments have been accepted as-is, 8 have been accepted with changes, and 63 have been rejected, leaving 132 technical comments that have still not been addressed one way or the other.

No significant changes have been accepted to the concurrency-related parts of the working draft, though there are quite a few editorial comments. However, there are several papers in this mailing that address the National Body comments in this area. These papers have by and large been drafted to represent the consensus of those members of the concurreny group in the LWG who were present at the meeting. I have summarised these papers below.

Concurrency-related papers

N3113: Async Launch Policies (CH 36)

This paper provides a clearer basis for implementors to supply additional launch policies for std::async, or for the committee to do so in a later revision of the C++ standard, by making the std::launch enum a bitmask type. It also drops the std::launch::any enumeration value, and renames std::launch::sync to std::launch::deferred, as this better describes what it means.

The use of a bitmask allows new values to be added which are either distinct values, or combinations of the others. The default policy for std::async is thus std::launch::async|std::launch::deferred.

N3125: Omnibus Memory Model and Atomics Paper

This paper addresses several National Body comments by updating the wording in the draft standard to better reflect the intent of the committee.

N3128: C++ Timeout Specification

There are several functions in the threading portion of the library that allow timeouts, such as the try_lock_for and try_lock_until member functions of the timed mutex types, and the wait_for and wait_until member functions of the future types. This paper clarifies what it means to wait for a specified duration (with the xxx_for functions), and what it means to wait until a specified time point (with the xxx_until functions). In particular, it clarifies what can be expected of the implementation if the clock is changed during a wait.

This paper also proposes replacing the old std::chrono::monotonic_clock with a new std::chrono::steady_clock. Whereas the only constraint on the monotonic clock was that it never went backwards, the steady clock cannot be adjusted, and always ticks at a uniform rate. This fulfils the original intent of the monotonic clock, but provides a clearer specification and name. It is also tied into the new wait specifications, since waiting for a duration requires a steady clock for use as a basis.

N3129: Managing C++ Associated Asynchronous State

This paper tidies up the wording of the functions and classes related to the future types, and clarifies the management of the associated asynchronous state which is used to communicate e.g. between a std::promise and a std::future that will receive the result.

N3130: Lockable requirements for C++0x

This paper splits out the requirements for general lockable types away from the specific requirements on the standard mutex types. This allows the lockable concepts to be used to specify the requirements on a type to be used the the std::lock_guard and std::unique_lock class templates, as well as for the various overloads of the wait functions on std::condition_variable_any, without imposing the precise behaviour of std::mutex on user-defined mutex types.

N3132: Mathematizing C++ Concurrency: The Post-Rapperswil Model

This paper provides a mathematical description for the C++0x memory model. A similar description was used to highlight some of the areas that are clarified by the omnibus memory model paper (N3125) described above.

N3136: Coherence Requirements Detailed

This paper introduces some simple coherence requirements to the memory model wording to make it clear that the sequence of values read for a given variable must be consistent across threads. The existence of a single modification order for each variable is a key component of the memory model, and the wording introduced in this paper makes it clear that this is a core requirement.

N3137: C and C++ Liaison: Compatibility for Atomics

The structure of the atomic types and operations in the FCD was carefully worked out in conjunction with the C standards committee to ensure that the C++0x atomic types were compatible with those being introduced in the upcoming C1x standard. Unfortunately, the C committee introduced a new incompatible syntax for atomic types into the C1x draft earlier this year because they believed it was a better match for the C language.

This paper attempts to address this new incompatibility by removing the atomic_xxx types that were originally added for C compatibility, leaving just the std::atomic<T> class template. Also, a new _Atomic(T) macro is introduced for compatibility with the new C1x _Atomic keyword.

Other papers

As already mentioned, this mailing contains a new C++0x Working Draft, along with the usual post-meeting stuff — editors notes for the changes in the new draft, new issues lists, minutes of the meeting, etc. It also contains a complete list of the National Body Comments on the FCD, and a few other papers addressing National Body comments.

If you have any opinions on the resolution of any NB comments not yet formally accepted or rejected, please add them to the comments for this post.

Posted by Anthony Williams
[/ cplusplus /] permanent link
Tags: , , ,

| Stumble It! stumbleupon logo | Submit to Reddit reddit logo | Submit to DZone dzone logo

Comment on this post

If you liked this post, why not subscribe to the RSS feed RSS feed or Follow me on Twitter? You can also subscribe to this blog by email using the form on the right.

Definitions of Non-blocking, Lock-free and Wait-free

Tuesday, 07 September 2010

There have repeatedly been posts on comp.programming.threads asking for a definition of these terms. To write good multithreaded code you really need to understand what these mean, and how they affect the behaviour and performance of algorithms with these properties. I thought it would be therefore be useful to provide some definitions.

Definition of Blocking

A function is said to be blocking if it calls an operating system function that waits for an event to occur or a time period to elapse. Whilst a blocking call is waiting the operating system can often remove that thread from the scheduler, so it takes no CPU time until the event has occurred or the time has elapsed. Once the event has occurred then the thread is placed back in the scheduler and can run when allocated a time slice. A thread that is running a blocking call is said to be blocked.

Mutex lock functions such as std::mutex::lock(), and EnterCriticalSection() are blocking, as are wait functions such as std::future::wait() and std::condition_variable::wait(). However, blocking functions are not limited to synchronization facilities: the most common blocking functions are I/O facilities such as fread() or WriteFile(). Timing facilities such as Sleep(), or std::this_thread::sleep_until() are also often blocking if the delay period is long enough.

Definition of Non-blocking

Non-blocking functions are just those that aren't blocking. Non-blocking data structures are those on which all operations are non-blocking. All lock-free data structures are inherently non-blocking.

Spin-locks are an example of non-blocking synchronization: if one thread has a lock then waiting threads are not suspended, but must instead loop until the thread that holds the lock has released it. Spin locks and other algorithms with busy-wait loops are not lock-free, because if one thread (the one holding the lock) is suspended then no thread can make progress.

Defintion of lock-free

A lock-free data structure is one that doesn't use any mutex locks. The implication is that multiple threads can access the data structure concurrently without race conditions or data corruption, even though there are no locks — people would give you funny looks if you suggested that std::list was a lock-free data structure, even though it is unlikely that there are any locks used in the implementation.

Just because more than one thread can safely access a lock-free data structure concurrently doesn't mean that there are no restrictions on such accesses. For example, a lock-free queue might allow one thread to add values to the back whilst another removes them from the front, whereas multiple threads adding new values concurrently would potentially corrupt the data structure. The data structure description will identify which combinations of operations can safely be called concurrently.

For a data structure to qualify as lock-free, if any thread performing an operation on the data structure is suspended at any point during that operation then the other threads accessing the data structure must still be able to complete their tasks. This is the fundamental restriction which distinguishes it from non-blocking data structures that use spin-locks or other busy-wait mechanisms.

Just because a data structure is lock-free it doesn't mean that threads don't have to wait for each other. If an operation takes more than one step then a thread may be pre-empted by the OS part-way through an operation. When it resumes the state may have changed, and the thread may have to restart the operation.

In some cases, a the partially-completed operation would prevent other threads performing their desired operations on the data structure until the operation is complete. In order for the algorithm to be lock-free, these threads must then either abort or complete the partially-completed operation of the suspended thread. When the suspended thread is woken by the scheduler it can then either retry or accept the completion of its operation as appropriate. In lock-free algorithms, a thread may find that it has to retry its operation an unbounded number of times when there is high contention.

If you use a lock-free data structure where multiple threads modify the same pieces of data and thus cause each other to retry then high rates of access from multiple threads can seriously cripple the performance, as the threads hinder each other's progress. This is why wait-free data structures are so important: they don't suffer from the same set-backs.

Definition of wait-free

A wait-free data structure is a lock-free data structure with the additional property that every thread accessing the data structure can make complete its operation within a bounded number of steps, regardless of the behaviour of other threads. Algorithms that can involve an unbounded number of retries due to clashes with other threads are thus not wait-free.

This property means that high-priority threads accessing the data structure never have to wait for low-priority threads to complete their operations on the data structure, and every thread will always be able to make progress when it is scheduled to run by the OS. For real-time or semi-real-time systems this can be an essential property, as the indefinite wait-periods of blocking or non-wait-free lock-free data structures do not allow their use within time-limited operations.

The downside of wait-free data structures is that they are more complex than their non-wait-free counterparts. This imposes an overhead on each operation, potentially making the average time taken to perform an operation considerably longer than the same operation on an equivalent non-wait-free data structure.

Choices

When choosing a data structure for a given task you need to think about the costs and benefits of each of the options.

A lock-based data structure is probably the easiest to use, reason about and write, but has the potential for limited concurrency. They may also be the fastest in low-load scenarios.

A lock-free (but not wait-free) data structure has the potential to allow more concurrent accesses, but with the possibility of busy-waits under high loads. Lock-free data structures are considerably harder to write, and the additional concurrency can make reasoning about the program behaviour harder. They may be faster than lock-based data structures, but not necessarily.

Finally, a wait-free data structure has the maximum potential for true concurrent access, without the possibility of busy waits. However, these are very much harder to write than other lock-free data structures, and typically impose an additional performance cost on every access.

Posted by Anthony Williams
[/ threading /] permanent link
Tags: , , , ,

| Stumble It! stumbleupon logo | Submit to Reddit reddit logo | Submit to DZone dzone logo

Comment on this post

If you liked this post, why not subscribe to the RSS feed RSS feed or Follow me on Twitter? You can also subscribe to this blog by email using the form on the right.

just::thread C++0x Thread Library V1.4.1 Released

Monday, 09 August 2010

I am pleased to announce that version 1.4.1 of just::thread, our C++0x Thread Library has just been released.

Thisis an improvement over V1.4.0 in a number of areas:

  • Both /Zc:wchar_t and /Zc:wchar_t- are supported with MSVC
  • std::chrono::high_resolution_clock typedef added
  • Added support for shared libraries on Linux
  • Faster mutex locking and unlocking on contended mutexes on Linux
  • Faster blocking/unblocking for condition variables on Linux
  • Support for tracking clock changes when waiting on a std::chrono::system_clock time with std::condition_variable on Linux with kernels >= 2.6.31
  • Support for floating-point durations
  • Faster time retrieval with std::chrono::monotonic_clock::now() on Windows
  • Added support for Microsoft Visual Studio 2005
Purchase your copy and get started with the C++0x thread library now.

As usual, existing customers are entitled to a free upgrade to V1.4.1 from all earlier versions.

Posted by Anthony Williams
[/ news /] permanent link
Tags: , ,

| Stumble It! stumbleupon logo | Submit to Reddit reddit logo | Submit to DZone dzone logo

Comment on this post

If you liked this post, why not subscribe to the RSS feed RSS feed or Follow me on Twitter? You can also subscribe to this blog by email using the form on the right.

More recent entries Older entries