饭中淹的避难所~~~~~

偶尔来避难的地方~

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  94 随笔 :: 0 文章 :: 257 评论 :: 0 Trackbacks

 首先,我们来看一个例子。

  1 //    交互通道“没有货”状态
  2 #define COMMUNICATIONCHANNEL_STATE_THINGSNOTEXISTS 0
  3 //    交互通道“有货”状态
  4 #define COMMUNICATIONCHANNEL_STATE_THINGSEXISTS 1
  5 //    交互通道结构
  6 struct CommunicationChannel
  7 {
  8     //    有货没货的状态
  9     volatile int iState;
 10     //    货物:值0
 11     int iValue0;
 12     //    货物:值1
 13     int iValue1;
 14 };
 15 //    线程参数
 16 struct ThreadParam
 17 {
 18     //    输出通道
 19     CommunicationChannel * pOutputChannel;
 20     //    输入通道
 21     CommunicationChannel * pInputChannel;
 22     //    减的值,用于制造奇数和偶数
 23     int iSubValue;
 24     //    值0的和
 25     int iSum0;
 26     //    值1的和
 27     int iSum1;
 28 };
 29 //    线程处理函数
 30 DWORD WINAPI ThreadProc( LPVOID lpParam )
 31 {
 32     //    取得参数
 33     ThreadParam * pParam = (ThreadParam*)lpParam;
 34     int iCounter = 0;
 35     bool bCountFinish = false;
 36     bool bCalcFinish = false;
 37 
 38     //    线程循环
 39     whiletrue )
 40     {
 41         //    向外输出数值给另一个线程
 42         if!bCountFinish )
 43         {
 44             //    输出通道是否是无货状态
 45             if( pParam->pOutputChannel->iState == COMMUNICATIONCHANNEL_STATE_THINGSNOTEXISTS )
 46             {
 47                 //    状态满足,输出数字
 48                 if( iCounter < 10 )
 49                 {
 50                     //    头10次,输出一个序列
 51                     ++iCounter;
 52                     pParam->pOutputChannel->iValue0 = iCounter;
 53                     pParam->pOutputChannel->iValue1 = iCounter * 2 - pParam->iSubValue;
 54                 }
 55                 else
 56                 {
 57                     //    第11次,输出0,不在进行向外输出数字
 58                     pParam->pOutputChannel->iValue0 = 0;
 59                     pParam->pOutputChannel->iValue1 = 0;
 60                     bCountFinish = true;
 61                 }
 62                 //    修改输出通道的状态为有货
 63                 pParam->pOutputChannel->iState = COMMUNICATIONCHANNEL_STATE_THINGSEXISTS;
 64             }
 65         }
 66         //    根据另一个线程输入的数值进行计算
 67         if!bCalcFinish )
 68         {
 69             //    检查输入通道是否有货
 70             if( pParam->pInputChannel->iState == COMMUNICATIONCHANNEL_STATE_THINGSEXISTS )
 71             {
 72                 //    状态满足
 73                 if( pParam->pInputChannel->iValue0 != 0 )
 74                 {
 75                     //    输入不是0,就累加到和上
 76                     pParam->iSum0 += pParam->pInputChannel->iValue0;
 77                     pParam->iSum1 += pParam->pInputChannel->iValue1;
 78                     //    修改输入通道为无货
 79                     pParam->pInputChannel->iState = COMMUNICATIONCHANNEL_STATE_THINGSNOTEXISTS;
 80                 }
 81                 else
 82                 {
 83                     //    否则,结束掉计算输入数值
 84                     //    因为另一个输出0就表示不再有新货到达
 85                     bCalcFinish = true;
 86                 }
 87             }
 88         }
 89         //    输出和计算过程都结束,就跳出线程循环
 90         if( bCountFinish &&
 91             bCalcFinish )
 92             break;
 93     }
 94 
 95     return 0;
 96 }
 97 
 98 int _tmain(int argc, _TCHAR* argv[])
 99 {
100     //    初始化两个交互通道,用于A到B的信息传送和B到A的信息传送。
101     struct CommunicationChannel A2BChannel = { COMMUNICATIONCHANNEL_STATE_THINGSNOTEXISTS, 00 };
102     struct CommunicationChannel B2AChannel = { COMMUNICATIONCHANNEL_STATE_THINGSNOTEXISTS, 00 };
103     //    初始化两个线程参数,用于线程A和线程B
104     struct ThreadParam ThreadAParam = { 
105         &A2BChannel,
106         &B2AChannel,
107         0,
108         0,
109         0
110     };
111     struct ThreadParam ThreadBParam = { 
112         &B2AChannel,
113         &A2BChannel,
114         1,
115         0,
116         0
117     };
118 
119     //    创建线程A,B,并等待他们结束。
120     DWORD dwId = 0;
121     HANDLE hThreadA = CreateThread( NULL, 0, (LPTHREAD_START_ROUTINE)ThreadProc, &ThreadAParam, 0&dwId );
122     HANDLE hThreadB = CreateThread( NULL, 0, (LPTHREAD_START_ROUTINE)ThreadProc, &ThreadBParam, 0&dwId );
123     WaitForSingleObject( hThreadA, INFINITE );
124     WaitForSingleObject( hThreadB, INFINITE );
125     //    输出线程A,B的计算结果。
126     printf( "Thread A sum0 = %d sum1 = %d\n", ThreadAParam.iSum0, ThreadAParam.iSum1 );
127     printf( "Thread B sum0 = %d sum1 = %d\n", ThreadBParam.iSum0, ThreadBParam.iSum1 );
128 
129     //    计算并输出正确的结果,用于比较这个方法的计算结果是否正确。
130     int iCorrectSum0 = 0;
131     int iCorrectSum1A = 0;
132     int iCorrectSum1B = 0;
133     forint i = 1;i <= 10++i )
134     {
135         iCorrectSum0 += i;
136         iCorrectSum1A += i * 2 - 1;
137         iCorrectSum1B += i * 2;
138     }
139     printf( "Correct sum0 = %d sum1A = %d sum1B = %d\n", iCorrectSum0, iCorrectSum1A, iCorrectSum1B );
140 
141     return 0;
142 }
143 
144 

这个例子,使用第一篇里面的方法,实现了两个线程双向通信。

线程处理函数里面进行的事情很简单,就是:输出通道没货,就放货进去,输入通道有货,就取货计算。

在这个过程里,我们将线程A的输出和线程B的计算结合起来看,称为一个任务

这个任务,它是如下图所示的过程进行处理的。





红色部分,是任务的主要处理部分。绿色的部分,则是隔离两个线程中处理部分的重要因素。

从图上看,如果填充数据和使用数据的红色部分在垂直方向有交错,那么,就会导致线程同步问题。

但是要那样,需要状态满足要求在设置状态的前面才行。上帝说,那是不可能的,不设置状态,怎么可能达成状态满足要求。除非线程B穿越了。

所以,使用这种方法,红色部分永远不会重合,也就实现了无锁的线程通信!当然,只是在两个线程间实现了。

从单个通道来看,这种方法可以形象的看作一个线程在不断的喂数据,另一个线程则在不断的吃数据。这里就简单的称为“喂食”。

喂食”是一种可用的方法,不过它也有缺点,比如得等另一个线程吃完才能喂新的食物;或者另一个线程得等第一个线程去喂才有东西吃。

接下来,得挑战点高难度的:突破喂食,以及两个线程的限制。






posted on 2010-05-06 14:49 饭中淹 阅读(1626) 评论(3)  编辑 收藏 引用 所属分类: 数据算法分析

评论

# re: 无锁线程通信(2):例程与分析 2010-05-06 16:09 fcc
在网上查了好久的资料,终于明白楼主的做法是不恰当的,在某些编译环境下、某些编译参数设置下可能是可行的,但并非严谨的。参见一篇著名的论文Threads Cannot Be Implemented As a Library。在此文中,举出了两个例子,1 Compilers may reorder memory operations 2 The hardware may reorder memory operations 。综上,除非保证程序必定按源代码一致的顺序执行指令,否则楼主提供的这种多线程编程模式是不能严格保证安全的。以上抛砖引玉,仅供探讨。  回复  更多评论
  

# re: 无锁线程通信(2):例程与分析 2010-05-06 16:34 shbooom
就算不考虑编译器优化,这个方法也是无效的。。。检查和置位完全是两个原子操作  回复  更多评论
  

# re: 无锁线程通信(2):例程与分析 2010-05-06 16:42 饭中淹
@fcc
确实是存在这种情况。
@shbooom
如果不考虑优化,还是可以用的,这个方法。

  回复  更多评论
  


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理