无锁数据结构设计 之 原子数据类型Atomic介绍

  • 这是mhy12345的无锁数据结构教程的第一篇,原子数据类型介绍。在阅读这篇文章之前,先安利一本这方面叙述非常详细的书《C++并发编程实战》(C++ Concurrency IN ACTION)
  • 想要详细了解无锁编程可移步无锁编程教程,里面从原理上介绍了atomic类型。

原子操作,即不可分割的操作,这样的操作在观察者看来,要不然就做完了,要不然就没有做完。原子操作本身是数据库中的一个概念,举一个例子,“在数据库中删除name为mhy12345的数据项,并且添加一个myh54321的数据项”对应了一个用户改名操作。这种操作如果从中间断开,只完成了一半,会产生灾难性后果。

为了使得我们数据结构能在多线程环境下安全运行,并且尽量不使用锁mutex(时间开销太大),原子数据类型就成了最佳选择方案。C++11提供了一系列原子数据类型,包含在头文件<atomic>里面,我们首先介绍原子数据类型的模板 std::atomic<T> a ,这是一个泛类型模板,支持极少数原子操作——

对于上述的原子操作函数,我们可以理解为函数的调用不会由于进程调度而被切断。例如其中的 compare_excahnge_strong(x,y) 函数,在单线程情况下,等同于一个if语句——

在多线程情况下,该if语句是可以被进程调度切断,这在某些情况下是我们不希望发生的,而这时,我们可以将这个语句用 compare_excahnge_strong 实现。

每一种操作还有一个内存顺序参数memory_order可以选择,这方面内容将在无锁数据结构设计 之 详解C++内存顺序(Memory Order)中介绍。不过,现在,我们可以直接忽略参数中所有memory_order相关项。

接下来,我们将详细介绍这几个函数——

前三个函数并不需要太详细的讲解,因为赋值、读取操作本身在我们的理解中就已经不可分割了,实际上,在当今大多数处理器上,即使一个普通的int的读写也都是原子的。

exchange(x)在我学习期间基本没有看到过使用,不过含义也非常简单:将desired储存,返回是原来的值。本质就是一个数据交换的方式。

定义很多,只用看第一条定义就好了,将变量的值与expected比较,如果相等就用desired更新,返回true,否则返回false,将变量的值放在expected里面。其等价的伪代码在前文已经写过了。

也许读者会问:这个函数看起来非常奇怪,真的在实际工程中会用吗?其实,这两个函数才是atomic的精粹所在!

无论是互斥锁实现,还是无锁栈,无锁队列的实现,都需要用到这些函数。具体细节可以移步 无锁数据结构设计 之 通过atomic实现自旋锁

看了这些文章,可能又有了新的疑惑,我怎么没看出来 compare_exchange_strong 和 compare_exchange_weak 有什么区别?

其实答案很简单, compare_exchange_weak 可以理解为 compare_exchange_strong 的一个有bug,但是更加高效的实现——

在一些特殊情况下,即使expected和变量的值是相同的,也有可能返回false,不过这样一个bug对于最常见的情况:将函数放在一个while循环中并不会产生影响,下面是一个典型的 compare_exchange_weak 放在while循环中的例子。在该例子中,如果少数情况条件判断将本应返回true的情况判断成了false,也并不会导致什么问题(只是多执行一遍while循环罢了)

所以说如果我们并没有意图通过函数返回值判断是否expected与变量的值确实不同,或者对于错误有容许度,我们完全可以用weak替换strong。

 

参考资料:

Cplusplus reference:http://en.cppreference.com/w/cpp/atomic/atomic

C++11原子操作atomic的内存顺序(memory_order)的理解

关于无锁数据类型的详细叙述,可以在无锁数据结构里面看,而内存顺序,则在无锁编程教程:简介 里面有讲。

在学习C++11的原子数据类型中,不免会遇到这样的语句——

其中第一个参数很容易理解,但第二个参数就比较奇怪了。实际上,内存乱序是由于编译器和处理器为了提升单线程程序运行效率所引入的,而第二个参数就是尝试去告诉编译器和处理器,哪些地方千万不要自以为是的乱序。

从cplusplus.com上面可以看到更加详细的定义:

可以发现,基本所有涉及到加“锁”,放“锁”的地方,都会存在这样一个memory_order参数!

要理解到这个参数的意思,还得从C++编译器的优化说起。对于一个顺序执行的语句

看起来确实是按顺序执行,先修改a的值,再修改b的值。

但是我们可以发现第3行和第4行在cpu中的顺序可以完全交换,因为a,b内存地址是独立的,交换执行顺序并不会导致任何的错误。甚至,在大部分情况下,这两个语句的执行顺序交换或重叠可以使得程序跑的更快!

在摩尔定律几近失效的今天,当然不能放过任何的优化空间,处理器在执行代码时会按照自己的理解将这类独立的语句按照另一种顺序执行。对于单线程程序,完全没有问题。但是到了多线程里面,这样的交换顺序就不对了。

这是一个通过bool实现自旋锁的代码——

不过这个程序第3行和第4行不是一个原子操作,也就是说其他线程可能在这个时候切入,导致数据访问错误。

而倘若将读取、判断、赋值合并为了一个操作。这样自旋锁就work了!这里用到了C++11的atomic<bool>类型

一个小小的问题,之前谈到了编译器会按照自己的想法交换一些代码的位置,也就是说其他线程的TODO2的代码和TODO0的代码块都有可能在编译器的优化下越过我们的加锁位置跳到TODO1里面(只要没有严格先后次序的语句都是可以随便交换顺序的)。在多线程里面,这是一个致命的问题,这个优化导致了之前的努力全部泡汤了!

怎么办呢,别忘了我们还有memory_order参数——

  • memory_order_acquire:执行该操作时,加入一个内存屏障,需要等待其他线程完成所有内存读
  • memory_order_release:执行该操作时,加入一个内存屏障,需要等待本线程完成所有内存写

有了这两个操作,TODO1中的读写语句就严格和外部的语句隔离开了,潜在的风险也就没有了。

当然,memory_order不只这些,还包括

  • memory_order_relaxed:完全不添加任何屏障
  • memory_order_consume:同acquire,但是该屏障并不阻塞无关的读操作,只阻塞有依赖关系的读写(不知道如何做到的,比较神奇)
  • memory_order_acq_rel:清空自己所在cpu的读写依赖
  • memory_order_seq_cst:最严格的屏障,要求所有cpu的读写严格依赖

这些都是我自己从网上的博客中总结的,如果有什么不对的地方还请留言告诉我。

不过看起来挺靠谱的~v~

参考链接1:https://blog.poxiao.me/p/spinlock-implementation-in-cpp11/

参考链接2:http://blog.csdn.net/yockie/article/details/8838661

参考链接3:http://www.cplusplus.com/reference/atomic/memory_order/

Tushare数据自动缓存

tushare是一个财经数据获取库,内置若干财经数据的获取爬虫,将各种数据的爬取封装在了一起。但是tushare有一个很大的缺点,就是其抓取的数据无法缓存在本地。故考虑实现一组自己的api用以缓存tushare数据。

这是python中获取tushare数据的典型例子,我们考虑实现一个简单的装饰函数,将函数调用以及调用的参数进行记忆化!

这里面data_cacher函数包装后的ts.api增加了将返回值保存为以“函数名”、“参数”命名的文件中,供下次调用直接使用。

最后,如何实现data_cacher函数呢?直接上代码:

 

 

人智大作业-四子棋实验报告

题目大意

带重力的四子棋(连成4个(横竖斜)胜利)

大致算法

预测:朴素搜索

通过判定一个必胜态的后继状态存在对手必败态,一个必败态后继状态必须全是对手必胜态。实现搜索算法,搜索深度可以达到6层左右。

朴素搜索只能对于短期一定必胜、必败的状态进行判断,故可用于

  1. 蒙特卡罗树新增一个节点时,如果该节点胜负短期可判,则不使用随机游走,而直接将固定胜率\败率100%返回
  2. 决策时跑预测防止出现一些蒙特卡洛故意走向一个必败态的情况

估值:随机下子

估计一个局面的情况可以通过随机下子的方式,双方随机在可能的位置等概率下子,判断最后谁胜,将随机下子次数增加可以非常“不准确”的估计出当前局面对谁有优势

决策:蒙特卡洛搜索树

对于上述算法,在短期无法判断局面的时候很难决策如何下子,因此使用信心上限树算法(UCT).

     $$I_j = X_j + \sqrt{\frac{2ln(n)}{T_j(n)}}$$

通过上面的式子得出决策树上每一个位置的信心上限[latex]I_j[\latex],其中n表示总的尝试次数,

    \[$T_j$\]

表示第j个状态(及其子状态)尝试次数。

显然,每次尝试I值最大的状态可以平衡所有状态的最小尝试次数以及对较优状态的多次尝试。

程序表现

与样例程序进行对抗,分数大约在30/200分左右。

一些细节

  1. 蒙特卡洛树的决策最好选择访问次数最多的而非期望权值最大的那一个,因为蒙特卡洛每次都会拓展期望权值L最大的那一个,并有一定概率使其变小。换句话说,蒙特卡洛的决策在某种意义下就是平衡L值得过程,所以L值并不能代表一个状态的优劣
  2. 比较神奇的是有些时候迭代次数较多的程序表现没有迭代次数较少的程序,可能是因为常数没有调好……
  3. 曾经尝试在随机游走的时候加入深度较小的特判,使得双方“稍微”有一点智能,但是发现这样会导致结果基本是平局
  4. 最开始程序使用new分配内存,然而Compete程序多次调用会出现segmentation fault,单独调用无误,改为预先分配就没有问题了。不知道是否和电脑的垃圾回收机制有关系。

makefile学习笔记&C++编译

静态链接库创建

  1. ar -rv maze.a BaseRouter.o ,将BaseRouter.o加入maze.a这个静态链接库中
  2. ranlib maze.a ,更新静态链接库符号表
  3. 库文件一般将.cpp改成.cxx

makefile笔记

  1. .PHONY: clean 表示clean为伪目标,否则如果文件夹下有clean文件会出错
  2. 而命令中的 $< 和 $@ 则是自动化变量, $< 表示所有的依赖目标集(也就是 BaseRouter.cxx ), $@ 表示目标集(就是 BaseRouter.o ),参见样例1
  3. makefile在target为.o的时候,dependence可以自动省略.cc,可以使用类似于 main.o : defs.h 的语法
  4. makefile只会完成第一个规则的第一个目标
  5. $(objects) 只是单纯的变量展开,一般表现为多条命令都是由于多目标的生成

样例

OOPWeek9_Makefile

 

Tmux学习笔记

相关链接

tmux入门教程:http://blog.jobbole.com/87278/,http://blog.jobbole.com/87584/

一些感悟

网上教程之所以看起来比较痛苦,主要是没有讲清楚session的含义,让我误认为一个窗口就是一个session,浪费了许多时间,实际上session可以理解为一个场景,在这个场景中一般你就是要写一个工程,故同一个session中可以开多个窗口,而一般不存在session切换的问题。

常用命令

一些问题

  1. 错误sessions should be nested with care, unset $TMUX to force:
    个人理解是说必须先detach当前的session再attach新的session,否则就成了嵌套关系,是tmux里面不推荐的。实际上这个问题就是对session理解不够导致的,参见前文
  2. tmux导致vim的分栏不能通过鼠标拖动了,需要使用命令调整宽度

 

Flask学习笔记

各种链接

官方文档:http://docs.jinkan.org/docs/flask/,*有一点点枯燥……

教程:http://www.pythondoc.com/flask-mega-tutorial/index.html,*一个写的不错的民间教程,一步步介绍了怎么建立一个工程,对于代码结构有讲解

flask-WTF:http://docs.jinkan.org/docs/flask-wtf/,*flask表单库

jinjia2文档:http://docs.jinkan.org/docs/jinja2/

jinjia教程:https://zhuanlan.zhihu.com/p/23669244

flask-bootstrap:http://pythonhosted.org/Flask-Bootstrap/,*一个把flask和bootstrap结合的库

bootstrap官网:http://v3.bootcss.com/getting-started/,*里面有很多模板

Step1. virtualenv

道理我都懂,然而这tm到底有啥用啊……安装了那么多年的包,还没见过冲突的,而且我电脑里面python的包不就是venv里面的包么?外面如果要冲突里面就不了?最重要的是界面还那么丑……

其中一点比较有趣的是 . bin/activate 命令激活venv虚拟环境,其中点和source命令相似,将bin目录下activate这个bash文件导入,bash文件中将bin目录路径加在了PATH命令之前,已完成重定向python相关路径.

Step2. Hello World

照着链接2一步一步写,比较有趣的一点是工程的架构。

这是官方文档的HelloWorld

这是工程化的Helloworld目录架构

__init__.py

views.py

run.py

by the way,里面的循环引用关系实在是没有弄懂

Step3.服务器编写

 

jinjia2

jinjia2是flask的渲染引擎,自动在app/templates里面搜寻模板文件。

Bootstrap

flask里面的bootstrap貌似比一般nodejs啥的要简单一些,不需要自己配置static文件,直接 pip install flask-bootstrap 即可。

将__init__.py改写为

注意,之前将 Bootstrap(app) 放在run.py中出现了问题,可能是import views的问题

发现现在debug模式没法及时刷新了……不知道啥原因

Docker通过Nginx容器实现域名转发

有些时候一台服务器上面需要架设多个网站,而同一个服务器又只有一个80端口,所以这是一个非常麻烦的事……

我在docker里面架设了两个wordpress,希望分别通过a.com和b.com转发到不同的容器中。

首先大致介绍一下nginx的转发配置

监听blog.mhy12345.xyz:80,对于任意的路径,转发到地址:http://wordpress_wordpress,后面那几行都在转发过程中修改header,具体是不是有用我也不知道。这个内容复制两遍,放入Nginx对应位置(/etc/nginx/conf.d/default.conf),就可以实现对于两个容器的转发了。

顺便给一下docker-compose.yml的写法

这里解释了为什么之前的URL是http://wordpress_wordpress,这是由于docker内部容器链接的dns设置了wordpress_wordpress的ip地址。

参考:http://www.cnblogs.com/Jarvin/p/5796193.html

当然,这一部分相当糟糕,原因是:

缓存!

是的,就是这东西,缓存!

docker的image创建有缓存,这个可以直接通过添加–no-cache参数

解决。

还有更可怕的是“浏览器缓存”

谁tm想得到浏览器会把跳转页面缓存下来啊……

每次输入 http://blog.mhy12345.xyz ,自动重定向到 https://blog.mhy12345.xyz:8022 ,根本找不出哪里有问题……

最后吐槽腾讯云学生机真是坑,一个G内存,5个docker容器就撑爆了……之后扩成两个G,然后月租上百了……

Ipython Notebook 使用方法

ipython notebook是个人认为使用python处理课题研究的非常方便的工具。

使用浏览器巧妙解决了远程服务器编程的难题,真不知道设计者是怎么脑洞出来的。

而notebook的核心思想是维护一系列cell,每一个cell里面一句python语句,你可以非常方便的跳转到不同的cell执行下一句话。

下面简单总结一下常用的快捷键

编辑/运行块

复制粘贴块

分裂合并块

 

Tensorflow学习笔记1-源码学习

TensorFlow 编译

tensorflow可以通过pip安装,也可以通过源码安装,其中pip安装直接

[ccei]pip3 install tensorflow[/ccei]

即可

基于源码的安装教程在https://www.tensorflow.org/install/install_sources 可找到,核心难点在于处理包的依赖问题

[ccei]sudo pip install six numpy wheel
brew install coreutils[/ccei]

运行./configure检查是否完全安装依赖库

TensorFlow 使用

使用tensorflow解决MNIST问题

具体每一个函数都是干嘛的太麻烦,就不写了,反正代码也不是我写的,网上一查一大堆……