技术背景
Concurrency and Parallelism
Concurrency:并发是指任务之间可以并发执行,但是这并不能确保任务都在执行,它们之间很可能是交替执行的。 可并发说明两个任务之间不需要共享状态,或者没有因果依赖关系
Parallelism:并行产生于多核计算机中,指两个任务在两(或以上)个CPU中同时执行。
并发是同一时间应对多件事情的能力;并行是同一时间动手做多件事情的能力。
举例:六大门派围攻光明顶,张无忌献身解围,当场放下豪言:六大门派,有和怨气可找我张无忌发泄。
所有在场的六大门派之人本来是可以一块向张无忌讨教的。但是,顾忌自己是名门正派,决定和张无忌一一单挑。打了半晌,明教白眉鹰王内气恢复,过来帮忙。六大门派见张无忌多了帮手,立马再派一人挑战。张无忌好比是CPU,六大门派好比是待处理的任务,谁先去和张无忌讨教都行,这时并发的。但是张无忌一次只能和一个人过招。当白眉鹰王上去帮忙之后,他们可以同时应对两人了。同时迎战的两人是并行的。
Asynchronous and Synchronous
Asynchronous:如果一个函数或者API是异步的,那么当我们调用这个函数或者请求这个API时,不用等到函数或者API返回,发送请求完成即可完成。
对于函数我们可以通过注册回调函数,当方法执行完毕时执行回调函数。
Synchronous:同步是指必须等到函数或者API执行完毕得到返回结果。
Blocking and Non-blocking
Blocking:当多个线程共享同一资源的时候,如果某个线程占有资源迟迟不释放则其他线程都会被阻塞。例如,一辆地铁进站后迟迟不出站则其它地铁都
被阻塞。在一段代码逻辑中如果某一段需要访问文件系统,或者请求外部API,这些一般都是耗时的请求,在它们执行完毕之前,后续逻辑都被阻塞。
Non-blocking:上边说到的阻塞的情况都会导致线程挂起,但是无阻塞不会产生线程的忙等。当线程试图请求资源时,应立即返回是否获取的状态。在代
码逻辑中呢,我们就可以通过异步的方式处理耗时的操作,注册回调函数,或者发送消息。
同步异步指的是一种协作方式;而阻塞和非阻塞指的是协作过程中出现的状态。
举一个"小王到书店买书"的例子:
一天,小王想要买一本编程书自学编程,于是来到了老王的书店。"老王,你这里有最新出版的《21天精通XXX》吗?"。于是发生了如下场景:
- 老王答道,"有,有,有,你稍微等一下,我给你找找"。两个小时之后老王终于找到了这本书,小王掏钱带书回家了。
- 老王答道,"有,有,有,你稍微等一下,我给你找找"。小王说,"行吧,你先找着,我去外边撸会串儿"。期间小王不时的去店里看看老王找到书没有。两个小时之后老王终于找到了这本书,小王掏钱带书回家了。
- 老王答道,"有是有,不过你得给你找找,要不你先到外边撸会串儿,等找到了叫你"。小王说,"没事,我等着你吧老王"。两个小时之后老王终于找到了这本书,小王掏钱带书回家了。
- 老王答道,"有是有,不过你得给你找找,要不你先到外边撸会串儿,等找到了叫你"。小王说,"好啊,等你找到了叫我"。两个小时之后老王终于找到了这本书,小王掏钱带书回家了。
场景1, 2, 3, 4分别对应:同步阻塞,同步非阻塞,异步阻塞,异步非阻塞。
在这个场景中,老王提供的卖书行为是一种同步或异步的协作方式;而小王等书的过程具有阻塞或非阻塞的状态。我们再为上述例子添加两个场景:这是小张过来买书了:"老王,你这里有最新出版的《7天精通XXX》吗?"
- 老王答道,"有,有,有,你先在小王后边排队等一会我给小张找完之后再给你找"。四个小时之后老王终于找到了这本书,小张掏钱带书回家了。
- 老王答道,"有,有,有,不过你得给你找找,要不你先到外边撸会串儿,等找到了叫你"。小张说,"好啊,等你找到了叫我"。两个小时之后老王终于找到了这本书,小张掏钱带书回家了。
同于同步的方式,当小王处于阻塞状态时,小张也必须阻塞,直到小王把老王"释放"出来。对于异步的方式,小张则不需要等待(意味着没有阻塞),等老王找到了直接去取就OK了。
Deadlock:是指两个或两个以上的进程(或线程)在执行过程中,因争夺资源而造成的一种互相等待的现象,若无外力作用,它们都将无法推进下去。
Starvation:饥饿是指在多线程环境下,调度算法总是使某些线程总是无法得到资源,使其长时间处于等待状态。
Live-lock:活锁是指两个线程在得到资源时都想让对方使用资源,导致双方都无法使用资源。
Race Condition:在多线程环境中,多个线程需要同时修改某一状态,由于没有对该共享状态加锁,不能保证每个线程进入顺序,因而产生Race Condition。
无锁算法:
Wait-free:是最有效的保证。每一次请求都在有限步骤内执行完成。
Lock-free:绝大多数都在有限步骤内完成,可以确保没有死锁,但是不能确保饥饿。
Obstruction-free(无干扰):一个方法在某一个时间点是隔离其他线程独立执行的
http://www.zhihu.com/question/19732473
http://www.cnblogs.com/ktgu/p/3529143.html
http://en.wikipedia.org/wiki/Non-blocking_algorithm