技术经验分享，欢迎关注并指点

并发编程过程中的同步操作往往是通过锁来实现，实际上在业界可以通过Dekker这种无锁同步算法来实现高性能程序的通信问题。

Dekker是并发编程中仅通过共享内存通信的互斥操作来解决通信的重要算法，它有效的避免了互斥，死锁，饿死三种情况。

原理

中文有个词语能够很精妙的解释这个算法

• 孔融让梨

什么意思呢，当两个进程/线程尝试访问临界区域的时候，它们在已经获取到资源的时候，尝试先让给对立的资源，如果对立的资源此时想要运行，那就让对立的资源运行，如果对立的资源没有想要运行，那么自己再运行。

可以看看，这种思想是不是完全的孔融让梨。当获取到梨的时候，并不想着里面吃掉，而是让给大哥吃。

说回dekker，其工作流程如下

测试程序

实现dekker算法的原型非常简单，我们只需要为每个线程提供一个flag，flag置位就代表自己获取了资源，再为两个线程提供一个全局的让梨标志位turn，这样在获取资源的时候先让给别人

staticvoiddekker0(void){    flag0 = 1;    turn = 1;while ((flag1 == 1) && (turn == 1));    counter++;    flag0 = 0;}staticvoiddekker1(void){    flag1 = 1;    turn = 0;while ((flag0 == 1) && (turn == 0));    counter++;    flag1 = 0;}

上面代码可以看到，当dekker0得到运行的时候，它在开始和结束将flag0置位和清除，然后将梨(turn) 设置为别人的1，自己等待，如果别人不吃（while循环），自己在做counter++的操作。

同样的，对于dekker1也是如此

解释

可以看到，这种设计原则上，没有使用任何的锁同步机制，其原理上可以保证互斥，死锁，饿死。下面逐一解释

避免互斥

因为每次线程得以运行的时候，都是先尝试让给对方，而不是自己里面运行，所以天然就避免了互斥

死锁

这种设计里面没有锁，每次进入临界区的时候（counter++）即使turn被错误的置位给自己，下次无论轮到自己还是别人运行，都会尝试把turn让给别人，所以也不会发生死锁

饿死

假设dekker0在某种情况下被卡在 while ((flag1 == 1) && (turn == 1));上，那么等dekker1得到资源运行的时候，dekker1会将turn设置为0 ，为dekker0解围，所以dekker0永远不会饿死。

运行

运行这个代码很简单，创建两个任务，直接运行即可

    (void) pthread_create(&thread1, NULL, task0, NULL);    (void) pthread_create(&thread2, NULL, task1, NULL);

总结

Dekker算法就是计算机领域的孔融让梨，它是一种wait-free的设计哲学，它的优势在于不需要任何特殊的原子读/修改/写的操作，所以基于此算法的代码行为非常高效。

注意，你可能看到当资源来到的时候让给对立资源的短暂收益是低效的(梨让给别人吃)，但是其代码全局确实高效的(无需原子操作)。但是当CAS指令诞生之后，高性能程序可以转向CAS指令型设计。

参考

https://en.wikipedia.org/wiki/Dekker%27s_algorithm