原子性
.NET(C#)：再议值类型 - 原子性
两年前我曾经写过一篇讲 理解值类型，引用类型的文章 ，主要是讲常见的值类型，引用类型的区别。但是这两种类型的渊源不止那些，今天就说说值类型在线程方面的原子性问题。
目录
0. 概念阐述 1. 使用Interlocked类型 2. 使用引用类型来声明 3. 通过装箱和拆箱 4. 使用lock 返回目录 0. 概念阐述首先我想专门强调一下，“ 原子性 ”和“ 线程安全 ”属于容易混淆的概念，解决了“原子性”不等于解决了“线程安全”，但是如果连“原子性”都没有保证，那么肯定不是“线程安全”的。“原子性”属于“线程安全”考虑的一个范畴，本文也仅仅是讨论“原子性”问题。
根据 C#语言标准 的描述，只有如下类型的读写是保证具有原子性的：
bool, char, byte, sbyte, short, ushort, uint, int, float，引用类型，和以上述值类型做为底层类型的枚举类型。
但同时注意这些类型的运算（包含递增++和递减--）不是原子性的。
但是根据 CLI标准 。
I.12.6.6（Atomic reads and writes）：CLI应该保证如下类型的读写是原子性的：
在内存中正确对其的位置，且大小不大于CPU一次性处理的字大小（也就是所谓的WORD大小，等于本地int大小）。
那么可以推理出在64位CPU的环境下，64位的内置类型（如long, ulong, double）的读写也是具有原子性的。这一点在 Eric Lippert的博客 中叙述过。不过注意，Eric Lippert也在其文章中提到由于这是CLI的规定，而不是C#语言的规定，因此某些非标准CLI执行环境可能会打破这个推断。因此对于这些特殊类型，我个人觉得最好还是用Interlocked类型提供的操作，或者使用lock。下文会详细讲这些内容。
下面开始阐述尝试解决值类型原子性的各种方法，越是上面的方法越推荐使用。
返回目录 1. 使用Interlocked类型对于解决值类型的原子性问题，首先考虑的类型就是System.Threading. Interlocked 类型。如下图，Interlocked类型的方法成员：
可以看到，Interlocked类型提供多种形式的原子性操作：读取，写入，递增，递减等。同时还支持多种类型。
使用Interlocked类型提供的方法可以减少lock的使用从而增加性能，比如实现一个计数器的添加原子性操作，其实是没有必要像这样使用lock的：
readonly object locker = new object ();
int myVar;
//执行原子性增值操作的方法
public void AtomicIncrement( int increment)
{
lock (locker)
{
myVar += increment;
}
}
完全可以使用Interlocked类型来执行这个原子性操作，使用如下更推荐的代码：
int myVar;
//执行原子性增值操作的方法
public void AtomicIncrement( int increment)
{
Interlocked . Add( ref myVar, increment);
}
这不仅会增加性能，还减少了代码，不需要声明用于lock的对象。
因此，如果能用到Interlocked的话，尽量就用Interlocked类型去解决问题，当然也肯定会有Interlocked类型不支持的方法，比如Read方法只支持long参数，没有double。（这个问题之后会被解决的）
返回目录 2. 使用引用类型来声明比如这样一个值类型：
struct MyStruct
{
public long Data1;
public double Data2;
}
显然，该类型的对象占用空间肯定是大于等于128位的，无论在32位还是64位CPU环境下，该类型的读写操作都不具备原子性的。而且Interlocked类型不支持用户定义的结构体，那么怎样使其具备原子性呢？
其实如果可以的话，这里最好的方法就是把它改成class，是的，引用类型的读写始终是具备原子性的。这样的话我们仍然可以不用lock。
//把MyStruct改成MyClass，该类型的读写具备了原子性 :-)
class MyClass
{
public long Data1;
public double Data2;
}
返回目录 3. 通过装箱和拆箱假设我们无法把上面的MyStruct结构体定义成引用类型，怎样解决原子性读写的问题？还有一个小诡计的，先来描述一下问题，我们先声明一个MyStruct结构体的属性：
public MyStruct MyStructObject { get ; set ; }
显然，MyStruct结构体的读写是不具备原子性的，如果一个线程在写入MyStructObject属性，而另一个线程在读取MyStructObject变量，那么可能会输出意想不到的值，因为有可能在一个线程写入了一半的时候，另一个线程开始了读取操作。于是另一个线程通过MyStructObject属性读取的值可能既不是写入前，也不是写入后的值，而是部分写入部分原始的不完整状态 。
//一个线程在写入
MyStructObject = new MyStruct () { Data1 = 2 , Data2 = 3 };
//另一个线程在读取
//输出既不是写入前，也不是写入后的值，而是部分写入部分原始的不完整状态！
Console . WriteLine( "{0} {1}" , MyStructObject . Data1, MyStructObject . Data2);
诡计就是可以使用装箱和拆箱，把属性声明成object，如下：
//声明类型为object
//对于MyStruct对象的读写需要装箱和拆箱
public static object MyStructObject { get ; set ; }
这样如果再次遇到上面的多线程读写代码，不会有问题发生（注意读取MyStructObject属性时需要一次强制转换，也就是装箱操作），因为此时读写操作会进行装箱拆箱操作，最终操作的是object引用对象，它的读写操作是具备原子性的。
返回目录 4. 使用lock上面提到过的方法都有自己的优势，但是全部不是万能的，而如果使用lock的话，虽然有额外的性能损耗，但它确是万能的。所以如果有任何非原子性操作，可以把他嵌套到一个lock中，这样其他线程就不会打断这些操作，整个过程具备原子性了！
比如在32位CPU环境下，进行原子的double加法操作，可以这样：
readonly object locker = new object ();
double myDouble;
//执行原子性增值操作的方法
public void AtomicIncrement( double increment)
{
//Interlocked.Add方法不支持double类型！！！
lock (locker)
{
myDouble += increment;
}
}
作者： Mgen
出处： www.cnblogs.com/mgen
其他参考页面： 我的软件和工程 ， 博客导读 。
标签: BCL , Threading
程序员们都是不被世人所理解的真正天才吗?-请大家看这个数独的解法
相关事件来自这个新闻: 江苏69岁农民3天破解“世界最难数独”_新华时政_新华网
事情大体上是这样的:
“芬兰数学家因卡拉，花费3个月时间设计出了世界上迄今难度最大的数独游戏，而且它只有一个答案。因卡拉说只有思考能力最快、头脑最聪明的人才能破解这个游戏。”这是英国《每日邮报》2012年6月30日的一篇报道。这个号称“世界最难数独”的“超级游戏”，却被扬州一位69岁的农民花三天时间解了出来。而这个具有初中文化的老汉，数独游戏启蒙正是源于扬子晚报。
上面就是题目,简单说下,所谓数独,就是如上图,横向竖向都用1到9填充.然后就是九宫,就是你注意到黑线分成的九个矩阵,也是1到9,下面是这位天才老头用了三天给出的结果.
从答案可以看出,天才老头把原题目给改了,然后花了3天算出一个答案,然后自然被封神了,也就是你看的新闻,可见,这就是广大人民眼中的天才.
作为孤独的程序员们,因为计算机与经和大脑密不可分,所以无论是做事还是其它,最终的结果都是人机合体的.所以他们往往能给出世人无法理解的答案和东西.比如:
通过自已的聪明,借助程序去完成.这当然也是本文的大体意思,如果用最粗造的算法,相信很一个会写程序的人都可以写出来,计算结果的时间看CPU能力,以现在的CPU,应该都可以很快给出结果.
有兴趣的可以尝试下, 人加机器,多久能给出答案!
这里把结果贴一下:
当然,如果以为程序员们仅仅只能做到这一步,那就大错特错了.
下面还有更多的解:
1.Google搜答案,程序员很善于这个,有问题,找Google.
2.使用Google Goggles,这是个图形搜索,只要把图片拍下来一搜,结果都出来了.
3.使用数独计算器软件,当然也可以自已写一个,那么不仅仅是上面这个数堵,理论上所有数独的答案都有了.当然也可以轻松去做一个题.
当然,如果以为程序员们仅仅只能做到这一步,那就大错特错了.
终盘数量
数独中的数字排列千变万化，那么究竟有多少种终盘的数字组合呢？
6,670,903,752,021,072,936,960（约有6.67×10的21次方）种组合，2005年由Bertram Felgenhauer和Frazer Jarvis计算出该数字，并将计算方法发布在他们网站上，如果将等价终盘（如旋转、翻转、行行对换，数字对换等变形）不计算，则有5,472,730,538个组合。数独终盘的组合数量都如此惊人，那么数独题目数量就更加不计其数了，因为每个数独终盘又可以制作出无数道合格的数独题目。
当然,如果以为程序员们仅仅只能做到这一步,那就大错特错了.
标准数独
目前（截止2011年）发现的最少提示数9×9 标准数独 为17个提示,关于是否有16提示数的合格题目，网络上也争论很久，有发现16提示数双解的，但是仍未发现唯一解。
在2006年Gary McGuire撰写了程式，试图通过暴力法来证明16提示数的数独是否存在，方法很简单，既然Bertram Felgenhauer和Frazer Jarvis已经计算出不等价的终盘总数为5,472,730,538个，那么将每个终盘是16提示的情况都跑一遍，如果没有找到16提示的数独，那么就可以证明最少提示数为17个。
但因为是暴力方法，对于一台单核的电脑来说需要跑30万年才能跑出结果。
经过很多人及团队努力,最后 Gary McGuire的团队在2009年设计了新的算法，利用Deadly Pattern的思路，花费710万小时CPU时间后，于2012年1月1日提出了9×9标准数独不存在16提示唯一解的证明，继而说明最少需要17个提示数。并将他们的论文以及源代码更新在2006年的页面上。
由此可见,程序员们借助聪明的脑袋,加上计算机的强大计算机能力,可以完成的事情,已经远远超越普通老白姓,尤其是对电脑理解不是很深的群体的理解范围,所以程序员们不容易被世人所理解也很正常.
你只要稍微借助计算机,就可以完成一般人无法想象的事情.给出他们难于置信的答案,而这种能力已经无法用普通的,不借助计算机所无法理解和承受的范围.
再回顾一下:
芬兰数学家因卡拉，花费3个月时间设计出了世界上迄今难度最大的数独游戏(难度大的依据是什么?)
江苏69岁农民3天破解“世界最难数独”(改了题目)那么作为一个程序员的你,你可以在这方面,你怎么去出题和去破解呢?你要花多少时间呢?
分类: 技术思考
作者： Leo_wl
出处： http://www.cnblogs.com/Leo_wl/
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。
版权信息声明：本文来自网络，不代表【好得很程序员自学网】立场，转载请注明出处：http://haodehen.cn/did45577