Showing posts with label cpp14_concurrent. Show all posts
Showing posts with label cpp14_concurrent. Show all posts

Jun 5, 2019

[C++] C++ Concurrency In Action, Second edition, recap [Ch.5]

Anthony Williams' C++ Concurrency In Action book hits second edition, hereby jotting down reading notes starts from Chapter 5, which draws the C++'s memory model and concurrent program design.
The Art of Multiprocessor Programming , [multiprocessor programming] types of synchronization)

For the system languages I am currently using having the sequential-consistent memory model, which is quite straight forward to work with (Go, Java). While C++ gives us a bit more,
thus the understanding of MESI , store buffer,
memory/compiler barrier would be a plus for reading through the context.


Nov 25, 2017

[C++][Book read] C++ concurrency in Action, 2nd edition

std::thread::native_handle
std::thread::hardware_concurrency()

Aware of thread constructor:
It's passing argument to callable function as rvalue through std::decay_t<T>.
Thus, if callable function is taking an l-value reference, compile fails.

std::thread::id offer the complete set of comparison operators,
which provide a total ordering for all distinct values.

The Standard Library provides std::hash<std::thread::id> so that values of
type std::thread::id can be used as keys in the new unordered associative containers.

FP like functions:



Before calling thread.join(), things have to be considered all code path with:
  • Will the callable function throw?
  • If the caller thread throws, what happen if thread.join() not called.
  • Using RAII
For thread's callable function's arguments:
by default the arguments are copied into internal storage,
where they can be accessed by the newly created thread of execution,
and then passed to the callable object or function as rvalues as if they were temporaries.
Thus, use
std::ref

reference boost::bind:
http://vsdmars.blogspot.com/2013/06/cboost-lambda-note.html
mem_fn

Sharing data between threads:
If all shared data is read-only, there's no problem, because
the data read by one thread is unaffected by whether or not another thread is reading the
same data.
i.e
a const member function implies thread safe.


Sharing data between threads:
mutex:

std::mutex some_mutex;
std::lock_guard<std::mutex> guard(some_mutex);
std::lock(lhs.m,rhs.m);
# instance of std::adopt_lock_t http://en.cppreference.com/w/cpp/thread/lock_tag_t
std::lock_guard<std::mutex> lock_a(lhs.m,std::adopt_lock);
std::lock_guard<std::mutex> lock_b(rhs.m,std::adopt_lock);

std::lock
std::scoped_lock RAII style.

Race conditions:
Avoiding problematic race conditions:
  1. Wrap data structure with a protection mechanism, to ensure that only the thread actually performing a modification can see the intermediate states where the invariants are broken.
  2.  Modify the design of your data structure and its invariants so that modifications are done as a series of indivisible changes, each of which preserves the invariants. This is generally referred to as lock-free programming.
  3. Handle the updates to the data structure as a transaction, just as updates to a database are done within a transaction. The required series of data modifications and reads is stored in a transaction log and then committed in a single step. If the commit can’t proceed because the data structure has been modified by another thread, the transaction is restarted. This is termed software transactional memory (STM), and it’s an active research area at the time of writing.
Aware of constructo might throw, which makes the container's data loss.
Thus solution:
  • PASS IN A REFERENCE
  • REQUIRE A NO-THROW COPY CONSTRUCTOR OR MOVE CONSTRUCTOR
  • RETURN A POINTER TO THE POPPED ITEM
  • PROVIDE BOTH OPTION 1 AND EITHER OPTION 2 OR 3

The class unique_lock is a general-purpose mutex ownership wrapper allowing deferred locking,
time-constrained attempts at locking, recursive locking, transfer of lock ownership,
and use with condition variables.

RWLock:
The class shared_lock is a general-purpose shared mutex ownership wrapper allowing deferred locking, timed locking and transfer of lock ownership. Locking a shared_lock locks the associated shared mutex in shared mode (to lock it in exclusive mode, std::unique_lock can be used)

std::unique_lock<std::mutex> lock_a(lhs.m,std::defer_lock); // http://en.cppreference.com/w/cpp/thread/unique_lock
std::unique_lock<std::mutex> lock_b(rhs.m,std::defer_lock);
std::lock(lock_a,lock_b); // http://en.cppreference.com/w/cpp/thread/lock


mutex:

has two levels of access:
  • shared - several threads can share ownership of the same mutex.
  • exclusive - only one thread can own the mutex.
Shared mutexes are usually used in situations when multiple readers can access the same resource at the same time without causing data races, but only one writer can do so.


Most of the time, if you think you want a recursive mutex, you probably need to change
your design instead. A common use of recursive mutexes is where a class is designed to be
accessible from multiple threads concurrently, so it has a mutex protecting the member data.



Ch. 4

Synchronizing concurrent operations:

header
<condition_variable>

std::condition_variable is preferred then std::condition_variable_any.

Pattern:

Producer:

std::lock_guard

modify data.
unlock mutex.
std::condition_variable notify_one 

Waiter:

std::unique_lock
std::condition_variable wait 
modify data.
unlock mutex.

header
<future>

std::async
Just as with std::thread, if the arguments are rvalues,
the copies are created by moving the originals.
This allows the use of move-only types as both the function
object and the arguments.

#include <string>
#include <future>

struct X
{
void foo(int,std::string const&);
std::string bar(std::string const&);
};

X x;

auto f1=std::async(&X::foo,&x,42,"hello");  // Calls p->foo(42,"hello") where p is &x
auto f2=std::async(&X::bar,x,"goodbye");    // Calls tmpx.bar("goodbye") where tmpx is a copy of x

struct Y
{
double operator()(double);
};
Y y;

auto f3=std::async(Y(),3.141);  // Calls tmpy(3.141) where tmpy is move-constructed from Y()
auto f4=std::async(std::ref(y),2.718);  // Calls y(2.718)

X baz(X&);

std::async(baz,std::ref(x));    // Calls baz(x)

class move_only
{
public:
move_only();
move_only(move_only&&)
move_only(move_only const&) = delete;
move_only& operator=(move_only&&);
move_only& operator=(move_only const&) = delete;
void operator()();
};

auto f5=std::async(move_only());    // Calls tmp() where tmp is constructed from std::move(move_only())

std::packaged_task

The std::packaged_task object is thus a callable object, and it can be wrapped in a
std::function object, passed to a std::thread as the thread function, passed to another
function that requires a callable object, or even invoked directly.

std::promise

some_promise.set_exception(std::make_exception_ptr(std::logic_error("foo ")));

Another way to store an exception in a future is to destroy the std::promise or
std::packaged_task associated with the future without calling either of the set functions on
the promise or invoking the packaged task.
In either case, the destructor of the std::promise or std::packaged_task will store a
std::future_error exception with an error code of std::future_errc::broken_promise
 in the associated state if the future isn’t already ready;

std::future


// get shared_future
std::promise< std::map< SomeIndexType, SomeDataType, SomeComparator,
SomeAllocator>::iterator> p;
auto sf=p.get_future().share();

C++ time class:

namespapce
std::literals::chrono_literals 
contains literals and chrono_literals
std::ratio has predefined type.
using namespace std::literals::chrono_literals
using namespace std::literals
using namespace std::chrono_literals
Fixed width integer types

Duration literals
user defined literals from cppref and c++11 faq
 
There are four kinds of literals that can be suffixed to make a user-defined literal:
  • integer literal: accepted by a literal operator taking a single unsigned long long or const char* argument.
  • floating-point literal: accepted by a literal operator taking a single long double or const char* argument.
  • string literal: accepted by a literal operator taking a pair of (const char*, size_t) arguments.
  • character literal: accepted by a literal operator taking a single char argument.

using namespace std::chrono_literals;
auto one_day=24h;
auto half_an_hour=30min;
auto max_time_between_messages=30ms;

Explicit conversions can be done with std::chrono::duration_cast<>
std::chrono::milliseconds ms(54802);
std::chrono::seconds s;
std::chrono::duration_cast<std::chrono::seconds>(ms);

Time points

std::chrono::time_point<>


header:

<experimental/future> 

std::experimental::when_all
std::experimental::when_any

std::experimental::latch
std::experimental::barrier
more basic, and potentially therefore has lower overhead

std::experimental::flex_barrier
more flexible, but potentially has more overhead.

Jan 23, 2016

[multiprocessor programming] types of synchronization.

Coarse-grained synchronization: 
Lock the whole object while accessing each it's methods.

  • Not scalable
  • Ok for levels of concurrency are low.
  • interface:
    • add , lock whole list
    • remove, lock whole list

    
Fine-grained synchronization: 
Provide each data member it's own lock.

  • interface:
    • add: lock couple nodes. 
      • Use lock coupling. i.e during add between a, b. First we need to
        lock a, then b.
        All methods MUST acquire locks in the same order.
        Each lock must be 'hand-over-hand' style, must lock in couple.
      • Reasoning is simple. Multi-thread adding nodes between a, b could
        cause problem.
    • remove: lock couple nodes.


Optimistic synchronization: 

  • Search without requiring any lock.
  • While find the data member, lock it, and check if the data member not being modified
    since previous search. If every time during the lock data member has changed, it's
    not good for this method. This method is good for less change during the lock of
    data member.
  • interface:
    • add: search the list without lock.
      find the place valid for add, then lock pred, curr nodes.
      Check the locked nodes are still the same value during the previous search.
      Actually, just make sure the curr is larger than the input node is enough if don't care
      about sorting.
      Or do the sorting later.
    • remove: same as add.
    • contains: search the key without lock. While locating the key, lock pred, curr nodes, make sure the nodes contain the value with previous search. If not, re-searching again.

     
Lazy synchronization:

  •  Postponing the efforts. Make into 2 phase commit.
    First, logically remove the data member by setting a tag bit.
    Secondly, physically remove it from the data structure, this time, we give a
    lock.
  • interface:
    • contain: a wait-free traversal. Only check if the node exists and not marked.
      In order to have contain wait-free, add/remove MUST to have the 'mark' variable assign as atomic.
      Node.next assign as atomic.
    • add: introducing a 'mark' variable into the Node struct. During the first search,
      either can not find the node or finding the node is 'marked', consider the node
      does not exist in the list.
      While found  the node, lock pred, curr nodes, validates it, if pass the validation, insert the node.
    • remove: 4 steps: 
      • search for the node to remove, no lock needed.
        (all belowing steps are under pred, curr lock)
      • while found, validate the finding.
      • mark the removing node. This logically removes the node.
      • redirect pred's next field. This physically removes the node.
    • validation:  Does not traverse the whole list as previous methods.
      Just test if the node is marked or not and the value remains the same as previous (before lock) search.

     
Nonblocking synchronization:

  • Most hard to implement. Not necessarily better than locking, since
    a RMW still forming a loop. Beware of ABA issue.
    Reference:
    Load-link/store-conditional
  • interface:
    • Base on Lazy synchronization, we tend to make add/remove lock-free by using RMW.
      BUT it won't work!
      Why? Because while applying RMW on pred's next field for removing curr,
      another thread  could apply RMW on curr's next field, it turns out that the second thread's adding won't work.
      We should group next and mark fields together as a atomic change.
      Introduce "find" member function.
      This function will use RMW to physically remove the node.
      Then continue finding the key. Return a position object which includes pred, curr, and
      the insertion key is in between.
    • add: will call 'find' in the while loop. Continuously testing the finding to insert the key.
      That is to say, although there's no lock, however, if RMW fails, it will loop again and again
      till the condition satisfies.
    • remove: same as add. Calling 'find' in the while loop. Mark the to be removed key.
      Let the 'find' to physically removes it.
    • contain: same as Lazy synchronization.
     
Concurrent Reasoning:

  • Finding the invariant. Properties that always hold.
  1. Property holds when the object is created.
  2. Once the property holds, then no thread can take a
    step that makes the property false.


  • there are
  1. insert
  2. remove
  3. contain
  4. validation
 member functions that could modify the object's data member state.


Look out steps:   

  • define data members.     e.g Sentinels nodes.
  • Beware of dead-lock and starvation.


Definition:
A method is wait-free if it guarantees  that every call finishes in a finite number
    of steps. (Strong)
A method is lock-free if it guarantees that some call always finishes in a finite number
    of steps. (Weak)

Oct 31, 2015

[C++ concurrent note][note] Ch.5 study note.



Reference:
LLVM Atomic Instructions and Concurrency Guide
There are only 2 places need barrier:
  • processing invalid queue (RMB) 
  • write store buffer to cache. (WMB) 
That's it, period!

Other places, like read pull request, response to read request, mark as share, do NOT participate with barrier!

If using bit fields, this is an important point to note
Though adjacent bit fields are distinct objects, they’re still counted as the same memory location.

The bit fields bf1 and bf2 share a memory location, and the std::string object s
consists of several memory locations internally,
but otherwise each member has its own memory location.

Note how the zero-length bit field marked /*bf3*/
(the name is commented out because zero-length bitfields must be unnamed)
separates bf4 into its own memory location, but doesn't have a memory location itself.


Four important things to take away from this
  • Every variable is an object, including those that are members of other objects.
  • Every object occupies at least one memory location.
  • Variables of fundamental type such as int or char are exactly one memory location, whatever their size, even if they’re adjacent or part of an array.
  • Adjacent bit fields are part of the same memory location.
Everything hinges on those memory locations. If two threads access separate memory locations, there’s no problem: everything works fine. On the other hand, if two threads access the same memory location, then have to be careful.