分类： C/C++
2005-10-30 18:33:16
本文讲述了一种实现异步存取共享数据的方法，他没有用到操作系统提供的同步互斥借口，也没有用CPU提供的特殊指令，但能供保证读到的共享数据的完整性。
分两部分：
1. 对这种方法的证明
2. C++模板类的实现
1. 证明
template
class CViewdata{
private:
T d0; // 只能由写对象更新
T d1; // 只能由写对象更新
volatile int can_use; // 只能由写对象写
volatile int read_using; // 只能由读对象写
volatile int read_using2; // 只能有读对象写
public:
bool get( T &d ); // 返回true，取到了数据，只能由读对象调用
bool put( const T &d ); // 返回true，放入了数据，只能由写对象调用
...
};
读对象通过get取数据，写对象通过put写数据。初始时，d0、d1内都是完整数据。
讲述了两种证明方法，第二较简单：
// 处理情况：
// 存在两个对象，读对象和写对象及数据。写对象写数据是需要时间的，在某个时刻，也就是写操作
// 开始了但还没有完成前的任何时刻，被写数据是不完整的。而要求读对象每次读到的数据是完整。
// 显然这可以通过操作系统的互斥、同步接口完成，我在这里提出的是另一种方法。
//
// 设置can_use,read_using,read_using2的目的是为了保证读对象每次读到的viewdata_t数据是完整的。
//
// can_use = 0时，d0为有效，否则为d1有效
// 初始化该数据时，应该确保d0和d1都是完整的viewdata_t数据,并置can_use=0，read_using=-1,read_using2=-1
//
// 写对象：
// 当需要更改viewdata_t数据时，更改d{!can_use},然后设置can_use=!can_use,那么其他对象通过
// can_use读到的viewdata_t数据始终是完整的，更改前提read_using==-1&&read_using2==-1。
// 分两步，
// 1：读入read_using和read_using2到R1和R2；当R1和R2的值更改后，该步骤才算完
// 2：if( R1 != -1 || R2 != -1 ) goto 1 or 4
// d{!can_use}=data;
// can_use=!can_use；当内存can_use改变时，该步骤才算完成
// 3：
// 读对象：
// 分七步，
// 1：读入can_use到R；当R的值更改后，该步骤才算完成
// 2：read_using2=R；当内存read_using2为R时，该步骤才算完成
// 3：读入can_use到R；当R的值更改后，该步骤才算完成
// 4：if( read_using2 != R ) goto 1 or 8;
// read_using=read_using2；当内存read_using为read_using2的值时，该步骤才算完成
// 5：读入d{can_use}到局存data；当data的每个子元素都得到更改后，该步骤才算完成
// 6: read_using2=-1；当内存read_using2变为-1时，该步骤才算完成
// 7：read_using=-1；当内存read_using变为-1时，该步骤才算完成
// 8:
//
证法一：
// -----|------------------|-----------|-----|------|---------|--|--|-----> 时间轴
// t1 t2 t3 t4 t5========t6 t7 t8
//
// -----|------------------|-----------|------------|---------|--|--|-----> 写对象
// can_use=USE
//
//
// ------------------------|-----------|-----|------|---------|--|--|-----> 读对象
// (1) (2) (3) (4) (5)(6)(7) 每个步骤完成的时刻
// R=USE
//
// 只要can_use的值不在[t5,t6]时间段内翻转，就行了。而读写对象的以上步骤能保证这一点。以下为论证步骤：
//
// 前提同一时间内存值唯一，当前情况：can_use=USE后第一次读操作的第一步已完成，显然每种情形都从这种情况开始。
//
// 写对象：
// 第一步完成在t3之后时，那么这次写操作不会在[t5,t6]段对d{USE}更改(写操作的第二步保证了它)
// 第一步完成在[t1,t2]段时，
// 如果第二步完成在t4之后，那么显然在[t5,t6]时间段肯定不会对d{USE}更改
// 如果第二步完成在[t3,t4]段，那么从第二步完成的时刻->t8时间段的后续写操作是不会对d{USE}更改的(第二步阻止了它)
// 如果第二步完成在[t2,t3]段，以下讨论第二次写操作的第一步完成在[t2,t3]段(因为当第二次写操作的第一步t3以后，那么第二次写操作不可能继续，写操作的第二步保证了它)
// 如果第二次写操作的第二步完成发生在[t3,t4]段，那么从第二次操作的第二步完成时刻->t8时间段的后续写操作是不会对d{USE}更改的(因为这次读操作在第三次写操作开始前将被取消，读操作的第四步保证了它)
// 如果第二次写操作的第二步完成发生在[t2,t3]段，以下讨论第三次写操作，
// 第三次写操作的第一步完成发生在[t2,t3]段，那么这次写操作的讨论情形如同第一次写操作的第一步完成在[t2,t3]段的情形。
// 第三次写操作的第一步完成发生在t3以后，那么第三次写操作在[t5,t6]段是不可能更改d{USE}的(写操作的第二步保证了它)
// 如果第二步完成在[t1,t2]段，那么第二次写操作讨论的情形如同第一次写操作
// 第一步完成在[t2,t3]段时，
// 如果第二步完成在t4之后，同第一步完成在[t1,t2]段时
// 如果第二步完成在[t3,t4]段，同第一步完成在[t1,t2]段时
// 如果第二步完成在[t2,t3]段，同第一步完成在[t1,t2]段时
// 以上讨论了所有情况，都满足要求
//
//
//
证法二：
// 以上证明是以读对象为基础讨论写对象，以写对象为基础讨论读对象的证明将更加简单，如下：
// ---|----------|------|-----------------|-----------|-------------------> 时间轴
// t0 t1 t2 t1' t2'
//
// ---|----------|------|-----------------|-----------|-------------------> 写对象
// can_use=USE (1) (2) (1) (2)
// can_use=!USE can_use=USE
//
// ---------------------------------------|-----------|-------------------> 读对象
//
// 上图显示了读对象的连续两次成功的写操作，要保证读到数据的完整性就必须使得读对象的(4)(5)步骤与
// 时间段[t1,t2]重合。以下用反证法证明。
// 假设该算法不能保证读到数据的完整性，并且有一个读步骤(以下讨论的都是针对改写步骤)的(4)、(5)步
// 骤与时间段[t1',t2']有重合，即它会在写对象写d{USE}时去读d{USE}。那么读对象的第(1)、(3)步必须完成在
// 时间t2之前，那么第(2)步完成在t2之前，那么第二个写步骤的第(1)步必然不能通过，因为它读到的using2此
// 时必然不为-1，然而写步骤的这两个步骤的存在是前提，产生矛盾，所以假设不存在。即证。
2. C++模板的实现
// created by zleil
//
// 2005.9.19
//
// change:
// 2005.10.7 by zleil
// 把原来的CViewdata2内改成了模板实现，并更改了其get方法中第二步的一个bug
// 即：if( can_use ) ==> if( ! can_use )
//
#ifndef VIEWDATA_H
#define VIEWDATA_H
#include "viewdata_t.h"
// 两种使用方法
// 第一：get/put成对使用
// 1st CViewdata()或CViewdata( const T &init )，确保这个步骤完成后才能开启下一步
// 2nd 读写对象分别调用get，put方法
// 注意：参数类型T必须设置好其=运算符，详情请看test目录下的测试程序，
// 如果类型T的默认构造函数不能构造完整的数据，那么必须用初始化函数CViewdata( const T &init )
//
// 第二：{enter_get/leave_get} / {enter_put/leave_put}成对使用，T类型一般为指针类型
// d0和d1分别指向两块存储区
// 1st CViewdata( const T &d_0, const T &d_1 )或者
// CViewdata()，再连续两次put调用填入d_0和d_1。
// 保这个步骤完成后才能开启下一步
// 2nd 读对象操作：enter_get返回true时，表示可以对d指向的数据进行读，并且读操作从此开始，然后用户
// 利用该返回指针进行读操作，最后调用leave_get方法结束读操作
// 写对象操作：enter_put返回true时，表示可以对d指向的数据进行写，并且写操作从此开始，然后用户
// 利用该返回指针进行写操作，最后调用leave_put方法结束写操作
template
class CViewdata{
private:
T d0; // 只能由写对象更新
T d1; // 只能由写对象更新
volatile int can_use; // 只能由写对象写
volatile int read_using; // 只能由读对象写
volatile int read_using2; // 只能有读对象写
public:
CViewdata( const T &d_0, const T &d_1 );
CViewdata( const T &init ); // 初始化后，必须是完整的数据
CViewdata();
bool get( T &d ); // 返回true，取到了数据，只能由读对象调用
bool put( const T &d ); // 返回true，放入了数据，只能由写对象调用
bool enter_get( T &d ); // 返回true，可以取数据，但取数过程持续到leave_get调用结束
void leave_get();
bool enter_put( T &d ); // 返回true，可以放数据，但放置数据的过程持续到leave_put调用结束
void leave_put();
// 帮助调试
int get_can_use(){ return can_use; }
int get_read_using() { return read_using; }
int get_read_using2() { return read_using2; }
};
template< typename T >
CViewdata
{
// for enter/leave 用法
d0 = d_0;
d1 = d_1;
can_use = 0;
read_using = read_using2 = -1;
}
template< typename T >
CViewdata
{
d0 = init;
d1 = init;
can_use = 0;
read_using = read_using2 = -1;
}
template< typename T>
CViewdata
{
// default
#if 0
d0.create();
d0.vRIGHT=3.0f;
d0.vLEFT=-3.0f;
d0.vTOP=3.0f;
d0.vBOTTOM=-3.0f;
d0.vNEAR=0.1f;
d0.vFAR=100.0f;
d0.rotate_Y=0.0f;
d0.rotate_X=-45*(3.14/180);
d0.rotate_Z=0.0f;
d0.tranX=0;
d0.tranY=0;
d0.tranZ=-10.0;
d1 = d0;
#endif
can_use = 0;
read_using = read_using2 = -1;
}
template< typename T >
bool CViewdata
{
bool ret = false;
int R;
do{
// 1st
R = can_use;
// 2nd
read_using2 = R;
// 3rd
R = can_use;
// 4th
if( read_using2 != R ){
break;
}
read_using = read_using2;
// 5th copy
d = (read_using) ? d1 : d0;
// ... 返回true，由调用者完成后续步骤
ret = true;
}while(0);
return ret;
}
template< typename T >
void CViewdata
{
// 6th
read_using2 = -1;
// 7th
read_using = -1;
}
template< typename T >
bool CViewdata
{
bool ret = false;
int R;
do{
// 1st
R = can_use;
// 2nd
read_using2 = R;
// 3rd
R = can_use;
// 4th
if( read_using2 != R )
break;
read_using = read_using2;
// 5th copy
d = (read_using) ? d1 : d0;
#if 0
if( ! d.iscomplete() )
printf( "can_use=%d,using2=%d,using=%d
", can_use, read_using2, read_using );
#endif
// 6th
read_using2 = -1;
// 7th
read_using = -1;
ret = true;
}while(0);
return ret;
}
template< typename T >
bool CViewdata
{
int R1,R2;
bool ret = false;
do{
// 1st
R1 = read_using2;
R2 = read_using;
// 2nd
if( R1 != -1 || R2 != -1 )
break;
if( ! can_use )
d = d1;
else
d = d0;
// can_use = can_use ? 0 : 1; 这一步由leave_put完成
ret = true;
}while(0);
return ret;
}
template< typename T >
void CViewdata
{
can_use = can_use ? 0 : 1;
}
template< typename T>
bool CViewdata
{
int R1,R2;
bool ret = false;
do{
// 1st
R1 = read_using2;
R2 = read_using;
// 2nd
if( R1 != -1 || R2 != -1 )
break;
if( ! can_use )
d1 = d;
else
d0 = d;
can_use = can_use ? 0 : 1;
ret = true;
}while(0);
return ret;
}
typedef CViewdata
#endif
