Showing posts with label cpp11_concurrent. Show all posts
Showing posts with label cpp11_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.


Sep 16, 2018

[Concurrency] [C++][Go] Wrap up - 2018

Modified
  • Thie Core's cache line has the modified data.
  • Data in memory won't be in other Core's cache line.
Exclusive
  • Data aren't modified.
  • Data in memory is the latest.
  • If the Core has to evict the data inside the cache line,
    nothing need to be write back to memory.
Shared
  • Data are shared between Cores' cache line.
  • If this core has to modify the data, it needs to ask for data from other cores first.
Invalid
  • The data in the cache line is null.

Operations:

Read
  • read data from cache lines. Ask for other cores' for data.  
Read response
  • Data for read request. Either from Memory or from Cores' cache.
Invalidate
  • Invalidate the particular data inside Cores' cache lines.
Invalidate ack
  • Response to invalidate request that the request is in the queue.      
Read invalidate
  • Read + Invalidate.
  • Will get read's data response and invalidate ack.
Writeback
  • Write the data from cache line to memory.

Store buffer:

  • Read invalidate request to other Cores' cache line for the to be modified data  is not necessary since the data response isn't needed because this Core is going to modify the data anyway.
  • Thus, this core will write data to Store buffer first.
  • Thus, Core will read data inside the Store Buffer with highest priority if the data exist in Store buffer and Cache line.
  • However, there's an issue for Read invalidate request to other cores.
    Consider that data A in Core 1 cache, data B in Core 2 cache.
    And data A, data B has this happen before relationship.
    i.e
    In Core 1, update data A(Core 1), then update data B(Core 2).
    In Core 2, read data A(Core 1), verify data B(Core 2).
 
You see the problem. Between operation on A/B there's interleaves.
 
Core 1 updates data B, write into store buffer, send read invalidate to Core 2 on data B, at the same time, Core 2 reads data A, receives data A from Core 1, and verify data B as well, at the time, data B isn't invalidated yet.

Thus we need some wait mechanism.
i.e memory barrier.

In the above case, we need
  • WMB(write memory barrier) on Core 1,
  • RMB(read memory barrier) on Core 2. 
For Core 1, we do:
Update B, then WMB, then update data A.

For Core 2, we do:
Read data A, if A is old data, verify B won't happen, and if A is new data.
i.e
Core 1 updated data A, data B in Core 2 SHOULD use new one from Core 1, since it's invalidate queued.
But how to trigger Core 2 to verify invalidate queue? Before verify data B in Core 2, call RMB.
So the sequence for Core 2 will become:
Read Data A, RMB, verify data B.
     
 
WMB:
  • Send read invalidate to Core 2 and till Core 2 send back invalidate ack will Core 1 flush data A from store buffer to it's cache line.
RMW:
  • Verify invalidate queue, make data that is in the invalidate queue invalid the Core 2's cache line.
  • While Core 2 tries to read the data, it will send a 'read' request to Core 1 for data B.

Take away:
  • WMB should be issued AFTER a write to the shared data.
  • RMW should be issued BEFORE a read to the shared data.
     
Reference:
  1. Memory Barriers: a Hardware View for Software Hackers
  2. https://en.cppreference.com/w/cpp/atomic/memory_order
  3. https://en.cppreference.com/w/cpp/atomic/atomic_thread_fence

Code:

#include <atomic>
#include <iostream>
#include <thread>

using namespace std;
atomic<int> A{0};
atomic<int> B{0};

void t1()
{
    this_thread::sleep_for(1s);
    B.store(38, memory_order_relaxed);

    int a = 42;
    // WMB, prevents 'a' passing A.store.
    A.store(a, memory_order_release);
}

void t2()
{
    // RMB
    while (A.load(memory_order_acquire) != 42) {
        cout << "in while" << endl;
        // Prints 0 or 38 if B.store hasn't process yet.
        cout << B.load(memory_order_relaxed) << endl;
    }
    cout << "out while" << endl;
    // Always print 38.
    cout << B << endl;
}
int main()
{
    thread T1{t1};
    thread T2{t2};
    T1.join();
    T2.join();
}
Fence:
#include <atomic>
#include <iostream>
#include <thread>
using namespace std;
atomic<int> A{0};
atomic<int> B{0};

void t1()
{
    A.store(42, memory_order_relaxed);
    atomic_thread_fence(memory_order_release);
    // B.store can NEVER before A.store.
    B.store(38, memory_order_relaxed);
}

void t2()
{
    while (B.load(memory_order_relaxed) == 38) {
        cout << "in while loop\n";
        cout << A << endl; // Must be 42
        break;
    }
    cout << "out while loop\n";
}

int main()
{
    thread T1{t1};
    thread T2{t2};
    T1.join();
    T2.join();
}


Fence:

Release/Store
  • Prevents all preceding memory operations from being reordered past subsequent writes.
  • Prevents all following memory operations from being memory reordered before the write.
Acquire/Load
  • Prevents all following memory operations from being reordered before this fence.
  • Prevents all preceding memory operations from being reordered pass this fence.

Memory fences are NOT an acquire or release operation.


Operation:

Release operation:  store
  • Cannot be reordered by compiler.
  • Prevents preceding memory operations from being reordered past itself.
    i.e Any operations after a store can be reordered before the store operation.
  • Any read or write operation that precedes it in program order.
    i.e those in memory_order_relaxed mode can't be reordered.
     
Acquire operation:  load
  • https://en.cppreference.com/w/cpp/atomic/atomic_load
  • Cannot be reordered by compiler.
  • Any read or write operation that follows it in program order.
    i.e those in memory_order_relaxed mode can't be reordered.
  • Those before the load can be memory ordered pass the load. Not as strong as fence.
BUT with different variable(object):
A release operation followed by a acquire operation CAN be reordered.
A acquire operation followed by a release operation CAN be reordered.
i.e
    A.store(1, std::memory_order_release);
    int b = B.load(std::memory_order_acquire);
=>
    int b = B.load(std::memory_order_acquire);
    A.store(1, std::memory_order_release);

However, keep in mind that (different variable/object) even reorder is OK for release/acquire operation, standard also depicts:
http://eel.is/c++draft/intro.multithread#intro.progress-18
An implementation should ensure that the last value (in modification order) assigned by an atomic or synchronization operation will become visible to all other threads in a finite period of time.
Reference:
https://stackoverflow.com/questions/8819095/concurrency-atomic-and-volatile-in-c11-memory-model/8833218#8833218

i.e
If an store operation follows a for/while loop and a load operation,
the compiler shouldn't reorder load before store due to it can't
reasoning that the for/while loop is finite thus other thread can see thread store result in a finite time.
   
Reference:
  1. [Preshing] Can Reordering of Release/Acquire Operations Introduce Deadlock?
  2. [Bruce Dawson] In Praise of Idleness
  3. [Golang bug list] cmd/compile: go1.8 regression: sync/atomic loop elided #19182

Hardware Memory Model:

Weak memory model
  • ARM/Power PC
Strong memory model
  • x86/64
  • Sequential Consistence (software)

Reordering:

Sequentially Consistent types:
  • Java: volatile variables
  • C++11: atomic (default)
Explicit Compiler Barriers:
gcc:
    asm volatile("" ::: "memory");
Macro:
    #define COMPILER_BARRIER() asm volatile("" ::: "memory")

source:
https://elixir.bootlin.com/linux/latest/source/arch/x86/include/asm/barrier.h#L22





Don't consider Sequential Consistency is SLOW; correctness is the highest priority.








Implied Compiler Barriers:
C++11:
  • Every non­-relaxed atomic operation acts as a compiler barrier.
    這裡是compiler reordering, 不是memory reordering.
  • Every function containing a compiler barrier must act as a compiler barrier itself, even the function is inlined.
  • The majority of function calls act as compiler barriers, whether they contain their own compiler barrier or not due to it's coming from different TU. 
  • But does not include inline functions, functions declared with the pure attribute, and cases where link ­time code generation is used.          
Reference:
  1. [Implications of pure and constant functions] https://lwn.net/Articles/285332/

What about Golang?

goroutine act as 'user space thread', 
i.e it's runtime memory location is allocated on the heap.

Inside a single goroutine, the compiler is allowed to re-arrange
expressions as long as the reordering does not change the behavior within that goroutine as defined by the language specification. 

Within a single goroutine, the happens-before order is the order expressed by the program.
i.e
a := 42
if a == 42 {
    // always true.
}

// b will always be 42
b := a
// within other goroutines, the observe of a == 42 and c == 38 sequence is not guaranteed.
c := 38  

Reads and writes of values larger than a single machine word behave as multiple machine-word-sized operations in an unspecified order.


Initialization:
  • If a package p imports package q, the completion of q's init functions happens before the start of any of p's.
  • The start of the function main.main happens after all init functions have finished.
Goroutine creation:
  • The go statement that starts a new goroutine happens before the goroutine's execution begins.
  • i.e go statement act as a barrier function call in C/C++ which won't be reordered.
Goroutine destruction:
  • Can happen any time.
  • Be ware that if a goroutine that updates a global value and do nothing (i.e using channel etc.), an aggressive compiler could delete the goroutine entirely for optimization.
    i.e just modify the global variable without creating a goroutine.
    https://github.com/golang/go/issues/19182

Channel communication:
  • A send on a channel happens before the corresponding receive from that channel completes.
  • The closing of a channel happens before a receive that returns a zero value because the channel is closed.
  • A receive from an un-buffered channel happens before the send on that channel completes.
  • The kth receive on a channel with capacity C happens before the k+Cth send from that channel completes.
i.e the famous:
Do not communicate by sharing memory; instead, share memory by communicating.
No more memory store/load operation from programmer's point of view.
The Channel acted as the sequential consistence/memory fence contract.


Reference:
[Preventing stack guard-page hopping] https://lwn.net/Articles/725832/

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.

Jun 15, 2017

[C++][note] Can Reordering of Release/Acquire Operations Introduce Deadlock?

preshing's article:
Can Reordering of Release/Acquire Operations Introduce Deadlock?

C++17 working draft:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4659.pdf

excerpt:
N4659, section 4.7.2:18 states:
An implementation should ensure that the last value (in modification order) assigned by an atomic or synchronization operation will become visible to all other threads in a finite period of time.


Refer to this note:
http://vsdmars.blogspot.in/2015/10/c-concurrent-notenote-ch5-study-note.html
RELAXED ORDERING:
Operations on atomic types performed with relaxed ordering don’t participate in synchronizes-with relationships.

Operations on the same variable within a single
thread still obey happens-before relationships, but there’s almost no requirement on ordering relative to other threads.

The only requirement is that accesses to a single
atomic variable from the same thread can’t be reordered; once a given thread has seen a particular value of an atomic variable, a subsequent read by that thread can’t retrieve an earlier value of the variable.

1. 同一個thread仍有同一個 variable 的 happen before relationship
2. 同一個thread同一個variable不能被either compiler reordered or memory reordering.
3. 同一個thread但不同variable,compiler仍能做reordering!!

----
RMW operations had to see the latest value in the object's modification order;
even 32.4:11 in the standard says so, quote:
Atomic read-modify-write operations shall always read the last value (in the modification order) written before the write associated with the read-modify-write operation.

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.