Chapter 11 Threads and Locks

---

“The Rules”

---

1.Concurrency

1.1 Threads vs Processes
Each process provides the resources needed to execute a program. Each process is started with a single thread, often called the primary thread, but can create additional threads from any of its threads. A thread is the entity within a process that can be scheduled for execution. All threads of a process share its virtual address space and system resources.

e.g. What’s the difference between a thread and a process? ( CtCI: 16.1)

1.2 Concurrency vs Parallelism
Concurrency is when two tasks can start, run, and complete in overlapping time periods. It doesn’t necessarily mean they’ll ever both be running at the same instant. e.g. multitasking on a single-core machine.
Parallelism is when tasks literally run at the same time, eg. on a multicore processor.

1.3 Peterson’s Algorithm
Guarantees mutual exclusion and protects against Deadlock and Livelock.

1.4 Deadlocks
A deadlock is a situation that each thread is waiting for the other thread to reliquish a lock.
Deadlock conditions: (1) Mutual Exclusion (2) Hold and Wait (3) No Preemption (4) Circular Wait.

“Circular Wait”是判定或避免Deadlock的关键：Build a directed graph, each edge (w,v) exist if a process declare that it will request lock v right after lock w.Any circle in this graph correspond to a deadlock.

e.g. Design a class which provides a lock only if there are no possible deadlocks.(CtCI: 16.4)

2.Concurrency in JAVA
When a standalone application is run, a user thread is automatically created to execute the main() method.

2.1 Create a thread
step1: public class RunnableThread implements Runnable + Thread thread = new Thread(instance); 或
public class ThreadExample extends Thread + ThreadExample thread = new ThreadExample(); 需要实现 public void run()
step2: 运行 thread.start();

2.2 Synchronization and Locks
给method或block加注synchronized关键词，即禁止不同thread访问同一object的任何synchronized对象；特别地，如果加注static关键词，则对该class的synchronized区域有效。
JAVA的实现类 ReentrantLock 提供更加精细的控制，lock()可以用于尝试获取控制权，若当前lock由其他thread控制，则当前thread禁用并等待，直到 owner thread 释放控制权；相对地，trylock()则立即返回false。unlock()则用于释放控制权。
http://ifeve.com/basic-thread-synchronization-5/

e.g. You are given a class with synchronized method A & B, and a normal method C.If you have two threads visiting the same instance of that class, they cannot execute A & B at the same time, but they can execute A & C simultaneously.

2.3 Semaphore
Semaphore与lock类似，区别在于其通过控制发放permit数量来允许多个thread访问。acquire()禁用当前thread并等待，直到获取一个permit,release则用于强行释放当前semaphore的一个permit，无论当前thread是否曾经acquire()。

3.Concurrency in C++11
http://www.baptiste-wicht.com/2012/03/cpp11-concurrency-part1-start-threads/
http://www.youtube.com/watch?v=LL8wkskDlbs&list=PL5jc9xFGsL8E12so1wlMS0r0hTQoJL74M

3.1 Start Threads
在C++11中，创建thread与创建其他对象无甚区别，构造函数以function pointer或functor object为第一参数，前者的函数参数为后续参数（通常可以借助std::ref来wrap传递引用）。创建thread后，可以通过join()来等待运行结束或detach()置入后台运行。

3.2 Protect Shared Resource
在C++11中，可以用std::mutex来解决thread-safe的问题。一般来说，优先使用wrapper class即std::unique_lock<mutex>（或其轻量版std::lock_guard<mutex>）来开启其在block内的自动控制和释放，如参数：defer_lock与adopt_lock，函数：lock(),try_lock()与unlock()。

3.3 Advanced features
注：thread, mutex或unique_lock,promise,future均不能复制，只能move()。
3.3.1 如果希望某段函数对于所有threads只执行一次，则可使用call_once：

std::once_flag flag;
void do_something(){
    std::call_once(flag, [](){ cout << "Call once" << endl;} );
    cout << "Call each time" << endl;
}

3.3.2 如果希望thread休眠一段时间（比如在尝试获取 mutex 一次失败之后），可以使用sleep_for:

std::timed_mutex mutex;
void work(){
    std::chrono::milliseconds timeout(100);
    while(true){
        if( mutex.try_lock_for(timeout) ){
            do_Something();
            mutex.unlock();
        }else{
            std::chrono::milliseconds sleepDuration(250);
            std::this_thread::sleep_for(sleepDuration);
        }
    }
}

3.3.3 异步问题
通常用future<T>来标示一个期望获得的变量，如： 从一个即将运行的thread的返回值获得, future<T> f = async( func , ref(param1) ); ; 或从promise获得，即producer承诺后传递future给customer，之后producer需满足承诺：future<t> f = p.get_future(); ...; p.set_value(val); 。对于更多的相互关系，可以使用shared_future（可多次获取share()）。

---

“模式识别”

---

1. Thread-Safe 问题
Thread-safe问题，即多个thread 访问同一对象(Object)或类(class)的问题，为了禁止多个thread调用对象同时进行某些行为，则可使用synchronized标记这些行为(method或block)；为了强调对象进入某种状态并且禁止其他thread更正这种状态，则可使用Lock或std::mutex，即任何使用该特定Lock锁定的行为（如读写操作），都不会同时有多个thread进行；为了强调对象进入某种状态但允许其他thread来释放这种状态，则可使用Semaphore。事实上，如果状态的开始和结束（临界区），都在同一个行为内，那么就可以用synchronized代替lock处理。

对于“Producer-Consumer Situation”，可以用condition_variable来高效解决资源”供需关系”的矛盾 ( 供应商到货时尽快通知客户，而无需客户反复查询）,unique_lock作为参数时，wait会在结束等待时重新获得控制权：

#define MAX_STOCK 10
std::mutex _mutex;
std::condition_variable _cond;
int count = 0;
void produce(){
    while( count < MAX_STOCK ){
        unique_lock<mutex> locker(_mutex);
        count++;
        locker.unlock();
        _cond.notify_one();  // Notify one waiting thread, if there is one.
        this_thread::sleep_for(chrono::seconds(1));
    }
}
void consume(){
    while( true ){ 
        unique_lock<mutex> locker(_mutex);
        _cond.wait( locker, [](){ return count != 0; }); // "Re-Lock" the mutex when waked up.
        count--;
        locker.unlock();
    }
 }

e.g.1 Implement a thread-safe blocking queue.(LinkedIn interview)

template <typename T>
class BlockingQueue{
    private:
        queue<T> _queue;
        mutex _mutex;
        condition_variable _cond;
    public:
        void push( const T& item){
            unique_lock<mutex> locker(_mutex);
            _queue.push(item);
            locker.unlock();
            _cond.notify_one(); 
        }
        T pop(){
            unique_lock<mutex> locker(_mutex);
            _cond.wait(locker, [=](){ return !_queue.empty() ;} );  //lambda function, capture by value
            T item = _queue.front();
            _queue.pop();
            return item; 
        }
};

e.g.2 Suppose we have:

public class Foo{
    public Foo(){ ... }
    public void first(){ ... }
    public void second(){ ... }
    public void thrid(){ ... }
}

The same instance of Foo will be passed to three different threads.Design a mechanism to ensure that first is called before sencond and second is called before third. (CtCI: 16.5)

2.解决Deadlock问题
除了让每次Locks之间依赖的顺序相同以外， 通常可以用try_lock()避免thread之间的互相等待，解决可能的Deadlock问题。

e.g. Design an algorithm solve Dining philosophers problem.(CtCI: 16.3)