SharedApplication: Linux Shared Memory Wrapper in C++, Lockfree Queue

Introduction

SharedApplication is a class used for sharing data between processes, support malloc between multi-process and could be derived to create multi-process data structure.

SharedQueue is a lockfree queue with fixed capacity, derived from the SharedApplication. Easy to use.

Code

Github:https://github.com/mhy12345/SharedApplication

Usage

SharedApplication

Create a SharedApplication instance with a unique APPKEY. The APPKEY is used to tell the operating system which Shared Memory you are going to alloc.

shared_application :: SharedApplication<APPKEY> sApp;

Then, we can do some basic configuration to our application.

sApp.setSize(size_t size);

Set the size of the memory you are going to alloc, and this must called before start. If it wasn’t called, then the default size will be 1024 bytes.

Some other configurations are also available.

void setCPU(); //Atomatically bind a CPU
void setCPU(int id); //Bind a CPU[id]

After the configurations, you can start the sApp, simple write:

sApp.start();

Then, in you program, you can use malloc to alloc memory.

void* ptr = sApp.malloc(size_t size);

In other process, if you use the same APPKEY, and use same order of malloc, and same size, then the contents in the memory allocated should be synchronized.

Shared Queue

The SharedQueue is a private inherited form the SharedApplication, means you can just replace SharedApplication with SharedQueue.

shared_application :: SharedQueue<T,capacity,APPKEY> sQueue;
sQueue::init();//called first in the main function

In the main function, you can use sQueue like a normal queue.

sQueue::push(T &val);
sQueue::pop(T &val);
sQueue::full(T &val);
sQueue::empty(T &val);

Attentions

  • In the SharedApplication, make sure you alloc each memory block using the same order and size
  • The destructive function must be called, otherwise the shared memory cannot be deleted.

SharedApplication: 共享内存操作原理

共享内存是Linux里面一个进程通讯的实现机制,通过系统API将同一块内存块挂载在到两个进程的内存地址空间中,从而实现共享内存的操作。

对于一块共享内存,我们用Key和Id进行标识,Key为用户自定义的一个值,不同进程倘若使用了同一个Key,即视为他们需要同一块共享内存。通过Key,用户可以向系统申请开一个指定大小的共享内存,并返回这块内存的内部标识Id,之后的挂载操作都需要用Id进行制定。

有关共享内存的API都封装在了<sys/shm.h>文件中,具体有

通过自定义Token新建共享内存,并返回标识符:appId = shmget(TOKEN,size,0666)

通过标识符挂在已经建好的共享内存到本地内存空间:ptr = shmat(appId,NULL,0)

取消挂载:shmdt(ptr)

删除共享内存:shmctl(appId,IPC_RMID,NULL)

每一次需要共享内存,强行调用这些语句看起来比较的繁琐,因此我希望写一个共享内存的操控框架,使得每次只需要极少的代码,就可自动完成诸如共享内存挂载,新建等要求。这也是SharedApplication的编写背景。

 

无锁数据结构设计 之 内存顺序实际表现

这是mhy12345的无锁数据结构教程的第四篇,在详解了C++内存顺序之后,谈谈C++内存顺序在实际运行中的一些影响。

从原理上出发看看C++内存顺序的含义:是由于计算机缓存等内存结构性质导致的线程间单原子变量读写互相不可见的情形。

不过,稍微仔细想想,发现这其实只是一种理论概率上的情形。

首先在考虑内存顺序的误差时,我们先举一个锁的例子——

锁,是为了防止线程之间的资源竞争,

假设一个线程在1%的时间需要独占某一个资源,两个没有加锁的线程产生了竞争导致程序崩溃的概率1%

则,在某一时刻,两个线程同时占有某资源且发生崩溃的概率应为10^{-6}

别看这概率很小,但是我们的程序是若干时点的概念,我们若将时点设为10^6个(这个数应该是有一段程序运行间线程期望切换次数决定的),则发生崩溃的概率为

    \[(1-10^{-6})^{10^6}-1 = 63%\]

因此我们发现,对于线程而言,加锁确实是必不可少的。

不过确实给我们一个提示:为什么我们一定要研究理论上那一丁点的小概率事件呢?假设我告诉你崩溃的概率只有10^-20,那我们还需不需要加锁呢?

我们在开始

 

如何写一个简单的对拍

最近很多同学问我

  • “数据结构的某PA交上去WA了怎么办,我明明过了样例的呀!”
  • “我如何才知道我的程序在大数据下跑的多块?小数据什么算法都看不出差别?”
  • “求救,我已经盯着我的程序看了两个小时了”

其实这种东西都可以通过一种叫做对拍的方式解决。对拍的核心思路是:写一个程序造数据,写一个程序暴力跑数据,然后和你的正解程序的输出进行比较。

这里面涉及到了三个程序:

  • 数据生成程序gen.py/.cpp
  • 暴力程序std.cpp
  • 对拍程序check.py/.sh/.bat

gen.py

全称generator.py,他的作用是你调用一次这个程序,自动给你生成一个随机输入数据,我们以PA4为例,我们可以写一个这样的程序。

from random import * #randint随机生成整数


if __name__ == '__main__':
    with open('input.txt','w') as f:
        n = 100000 #数据规模
        f.write("%d\n"%n)
        totIn = 0 #当前没有删去的股票个数
        totOut = n #当前所有没有加入的股票个数
        for i in range(n*2):
            if totIn==0 or (totOut>0 and randint(0,1)==1): #加一个股票
                f.write('%d %d\n'%(randint(1,100),randint(1,10000)))
                totOut -= 1
                totIn += 1
            else: #删一个股票
                f.write("%d\n"%randint(1,100))
                totIn -= 1

将这个程序写入gen.py 中,则每次调用python3 gen.py 都可以在input.txt 文件中生成一组规模100000的数据!

到这里,我们已经可以解决不清楚程序运行速度的问题了:你最大规模数据都有了,为啥还不能看出来呢?

std.cpp

对于大部分题目,我们都能找到一种不那么好的解法,比如PA4,我们实际上可以讲每天的区间即权值,放到一个struct数组里面,对于每一个时刻,查询包含该时刻的区间权值最大值。

放代码恐怕我就要被邓公请去喝茶了,所以大家自己写咯。

目标是写一个程序,交到网站上不会WA,只会TLE的那种。

check.py

现在一个比较直接的方式是:每次运行一边generator,在运行一边std,比较输出文件。但是这样非常慢。为什么我们不能将这个过程自动化呢?

这里需要科普几个终端命令:

diff A.txt B.txt 比较A.txt B.txt文件差别,这个diff函数在文件不同的时候返回非零值
./std 执行该目录下std这个程序
./std <input.txt >output.txt 将input.txt作为std的标准输入,output.txt反之

首先,我们可以通过bash/bat等批处理文件实现,不过看在读者基本都不会愿意再学一门新语言,我们直接用我们会的python实现,python的os.system() 可以调用一个系统命令,并且返回结果。

import os

if __name__ == '__main__':
    while True:
        os.system('python3 gen.py')
        os.system('./std <input.txt >out1.txt')
        os.system('./prog <input.txt >out2.txt')#自己的程序
        if os.system('diff out1.txt out2.txt'):
            print("GG")
            break
        print("Good!")

大概程序长成这样,调用python3 check.py 就自动无线循环造数据测试啦。

这里我们需要修改gen.py 里的数据范围,使得刚好到你的暴力程序能两三秒跑出来的规模。这样一分钟你就可以测试三四十组数据了。

 

这就是一个最简单的对拍程序。对拍对于数据结构的题简直是神器,因为这类问题总是会存在一个非常暴力,但是不容易写错的解法。而且熟练之后,三个程序加起来也就是二十分钟的事。

*注,上面的代码都是手打的,没有测试过哦……错了评论一下就好了,思路是对的

问:写这个耗费时间啊!

答:你盯着代码不动更费时间。

问:不会写暴力,或者暴力我也可能写错怎么办

答:找A了的同学的代码当std

电影爬虫日记 之 豆瓣网爬虫记录

2017年9月29日

最近接到了一个小任务,要求爬取豆瓣、时光网等网站的电影信息并进行少量的数据处理。爬电影确实不是一个难的东西,不就是选择一个相对简单的目标url,写一个脚本进行访问。但是,要想要为何不借此机会,好好研究一下python中的异步以及多线程机制呢?说不定还就写出一个像scrapy一样的爬虫框架了呢!

爬取豆瓣电影列表这件事,也不算什么复杂的工作,因为豆瓣电影本身没有反爬虫机制。

电影列表抓取

方案A

网址:https://movie.douban.com/tag/2017

里面有2017年的所有电影,但是其中有混杂很多的电视剧啥的,总数也仅仅只有4000个。


2017年9月30日

方案B

网址:https://movie.douban.com/typerank?type_name=剧情&type=11&interval_id=100:90&action=

倘若枚举每一个分类的每一个得分档次的每一页,就可以得到大约20000个电影。这可以说非常全面了。


2017年10月7日

电影信息抓取

豆瓣对于每一个电影都有一个自己的id,这个在之前爬取爬虫列表的部分就已经预处理出来了。

页面链接就是普通的电影页面:https://movie.douban.com/subject/26425068/

然而,当我尝试开始使用诸如多线程爬虫时……

豆瓣把我给封掉了……

现在可以确认的消息是

  1. 通过urllib.request.urlopen进行访问,单线程会在几千次左右被封
  2. 通过多线程访问可以在一分钟内被封
  3. 通过IP代理暂时没有看出效果

首先我尝试的是直接将爬取的数据写入数据库,但是感觉比较迷……因为容易被封IP,需要在八小时后自动重新启动。判重等问题非常难处理。

另一种尝试则是通过在ID对应文件中写入数据。网上的爬虫用的是第二种,但是感觉第一种可能会方便一些……吧……

 

无锁数据结构设计 之 详解C++内存顺序(Memory Order)


内存顺序概述

内存顺序,这是一个很大很大很大的坑,在介绍atomic原子类型的时候,就已经提及过,但是由于本身概念理解起来非常困难,所以没有细讲。现在就让我们仔细看看这是什么一个神奇的东西吧。

先通过一系列简单的代码片段,看一看内存顺序是如何定义的:

std::atomic<bool> x;
x.store(true,std::memory_order_seq_cst);
std::atomic<bool> flag = ATOMIC_VAR_INIT(false);

bool expected = false;
while(!flag.compare_exchange_strong(expected, true, std::memory_order_acquire))
    expected = false;
flag.store(false, std::memory_order_release);

可见,memory_order一般情况下是加在有内存操作的函数(如store、load等)后面,比如上面程序中的std::memory_order_release ,特别的由于函数compare_exchange_weak在失败、成功之后存在两种不同的内存操作策略,因此它可以传入两个memory_order分别指示成功(success)和失败(failure)后不同的操作策略:

bool compare_exchange_weak (T& expected, T val,
           memory_order success, memory_order failure) noexcept;

 

内存顺序原理

好了,废话不多说,为了让读者理解内存顺序,我们将分别解释内存顺序、操作可见性等概念

内存顺序,顾名思义,是由于内存操作重排带来的不确定性。

CPU中的缓存机制曾经大幅提高了内存访问速度,这个机制将内存中经常访问的区域拷贝到了缓存中以加快速度。这种策略使得内存的读写的目标不一定是内存中的值,而是有可能仅仅是该值在缓存中的一个副本。

在单核处理器下,并不会出现任何问题,毕竟所有线程的缓存是共用的,也就是说不存在缓存同步的问题。在多核的情况下,问题就会比较复杂了,每一个核都有自己独立的L1缓存,若两个核共享内存,就需要解决缓存同步的问题。内存重排就是处理器(编译器)设计者为了平衡缓存同步的时间开销,和程序不稳定性之后得到的一个较好的解决方式。

不仅仅缓存会导致内存操作的重排,编译器也可能为了优化速度重排操作,当然,这些重排也是建立在不影响单线程程序正确性的情况下。不过,编译器的优化非常好处理,在解决好处理器优化后,编译器优化自然而然可以解决,因此我们这里就不深入讨论。

【注:在 之前的文章 中,我曾介绍过内存顺序可以用多人写作的版本控制来理解,单独线程的本地修改对于自身来说是一定有序的,但是这些修改要传递到远程的代码库中,则是一个可能发生顺序交换的不确定事件。  】

#include <atomic>
#include <thread>
#include <assert.h>
std::atomic<bool> x,y;
std::atomic<int> z;
void write_x_then_y()
{
    x.store(true,std::memory_order_relaxed);
    y.store(true,std::memory_order_relaxed);
}

void read_y_then_x()
{
    while(!y.load(std::memory_order_relaxed));
    if(x.load(std::memory_order_relaxed))
        ++z;
}
int main() {
    x=false;
    y=false;
    z=0;
    std::thread a(write_x_then_y);
    std::thread b(read_y_then_x);
    a.join();
    b.join();
    assert(z.load()!=0);
}

以上面的程序为例子:函数write_x_then_y 依次写了变量x和y,而函数read_y_then_x 在确认变量y已经被写之后读入x。从常理上来说,此时z++ 是一定会被执行的。但是从运行结果上来看,assert可能被触发!

假设编译器没有优化汇编层面x和y的写入次序。实际上,是由于缓存机制,导致不同变量在其他线程看来更新的顺序是不同的。这就是内存顺序所刻画的问题。其中,本程序中,x的赋值操作可能不会被其他线程所看到,这就是所谓的不可见

从可见性方面重新叙述内存顺序的问题——一个线程的内存操作对于其他线程来说是不可见的。一种可能的情况是:

  • 线程A:写x,写y
  • 线程B:发现x先于y被赋值
  • 线程C:发现y先于x被赋值

联想之前说的缓存机制,确实会是这样的。

所以内存顺序memory_order是什么呢,memory_order是编译器指定常规的非原子内存访问如何围绕原子操作排序。

初步理解内存顺序

下面是我对于内存顺序的理解,由于在x8-64的机器上,内存顺序的问题本身不容易触发,所以下面的所有解释都没有经过验证,但是是我通过阅读网络上各种“不靠谱”的文献之后,经过自己筛选总结出的一套可信的解释。

memory_order_acquire & memory_order_release

在各种资料中,这两个内存顺序标记都是组合使用的,一个比较直观的理解是:线程A的release标记写操作W_A和线程B的acquire标记读操作R_B组合,可以达到:

  1. 线程A中的所有W_A之前的写操作,相对于W_A对齐,也就是说W_A操作完成后,线程A所有写操作完成
  2. 线程B中的所有R_B之后的读操作,相对于R_B对齐,也就是说R_A操作开始时,线程B的所有读操作尚未开始
  3. 线程A的W_A在线程B的R_B之前读入

综合上面三条性质,我们发现,acquire-release操作成功将线程A和线程B分割开来。

memory_order_relaxed

不进行内存顺序限制,即对于某一条语句,倘若运用了memory_order_relaxed标记,则其储存顺序对于其他线程不可见。那么什么时候使用这个标记呢?

既然acquire-release通过标记线程A的最后一个写操作,和线程B的第一个读操作,实现了线程的顺序要求,那么除了这两个操作之外的其他操作,实际上是可以直接用memory_order_relaxed的

无锁数据结构设计 之 通过atomic实现自旋锁

这是mhy12345的无锁数据结构教程的第二篇,通过atomic<bool>实现自旋锁。对,你没有听错,用无锁数据结构实现一个锁 >_<

自旋锁,顾名思义,通过自旋来实现线程加锁的工具。一个最简单的demo如下

bool flag = false;
 
void func()
{
    while (!flag);
    flag = true;
    //TODO1
    flag = false;
    //TODO2
}

看起来这是一个很机智的做法。程序进入时将一个共享bool变量赋值为true,而在另一个程序准备进入时,检查到该bool变量已经为true了,就放弃进入,开始用while语句自旋。

自旋锁流程
自旋锁流程

不过对于一个多线程程序,其他线程可以在任意位置接入,比如这个程序的第4行和第5行不是一个原子操作,倘若这个时候恰好另一个线程获得了控制权,读取到flag值为false,继续执行,但是在释放flag之前控制权有转会了第一个线程,由于第一个线程已经执行了取值操作,也默认flag为false,继续执行,导致受保护数据被重复访问。产生问题。

这时候,一个非常自然的想法就是:我们能不能把对flag的操作换成原子数据类型操作呢?答案是肯定的!

std::atomic<bool> flag = ATOMIC_VAR_INIT(false);

void func()
{
    bool expected = false;
    while(!flag.compare_exchange_weak(expected, true, std::memory_order_acquire))
        expected = false;
    //TODO1
    flag.store(false, std::memory_order_release);
}

当程序执行到第六行时,准备进入临界区//TODO ,首先判断flag是否为false,如果不是,说明已经有一个程序在临界区中间了。否则将flag赋值为true,自己进入临界区。

一点细节是,如果进入临界区失败,则true值会被赋予expected,这是我们需要在while语句中恢复expected的值。

memory_order是什么呢?请看:无锁数据结构设计 之 详解C++内存顺序(Memory Order)

 

参考资料:

https://blog.poxiao.me/p/spinlock-implementation-in-cpp11/

http://blog.csdn.net/yockie/article/details/8838661

 

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

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

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

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

a.load();//获得a的值
a.store(x);//将新值存在a里面
a.exchange(x);//将x的值存入a,并返回原来的值
a.compare_exchange_weak(x,y);//将a的值与x比较,如果相等则将y存在a里面,否则将x的值变为a内部储存的值,返回是否储存成功
a.compare_excahnge_strong(x,y);//基本同上
a = <non-atomic-instance-of-T>; //等同于store

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

//将a的值与x比较,如果相等则将y存在a里面,否则将x的值变为a内部储存的值,返回是否储存成功
if (a == x) {
    a = y;
    return true;
}else {
    x = a;
    return false;
}

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

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

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

void store( T desired, std::memory_order order = std::memory_order_seq_cst ) noexcept;
void store( T desired, std::memory_order order = std::memory_order_seq_cst ) volatile noexcept;

T load( std::memory_order order = std::memory_order_seq_cst ) const noexcept;
T load( std::memory_order order = std::memory_order_seq_cst ) const volatile noexcept;

T operator=( T desired ) noexcept;
T operator=( T desired ) volatile noexcept;

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

T exchange( T desired, std::memory_order order = std::memory_order_seq_cst ) noexcept;
T exchange( T desired, std::memory_order order = std::memory_order_seq_cst ) volatile noexcept;
/*Atomically replaces the underlying value with desired. The operation is    read-modify-write operation. Memory is affected according to the value of order.*/

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

bool compare_exchange_weak( T& expected, T desired,
                            std::memory_order success, 
                            std::memory_order failure ) noexcept;
bool compare_exchange_weak( T& expected, T desired,
                            std::memory_order success, 
                            std::memory_order failure ) volatile noexcept;
bool compare_exchange_weak( T& expected, T desired,
                            std::memory_order order =
                                std::memory_order_seq_cst ) noexcept;
bool compare_exchange_weak( T& expected, T desired,
                            std::memory_order order =
                                std::memory_order_seq_cst ) volatile noexcept;
bool compare_exchange_strong( T& expected, T desired,
                              std::memory_order success, 
                              std::memory_order failure ) noexcept;
bool compare_exchange_strong( T& expected, T desired,
                              std::memory_order success, 
                              std::memory_order failure ) volatile noexcept;
bool compare_exchange_strong( T& expected, T desired,
                              std::memory_order order = 
                                  std::memory_order_seq_cst ) noexcept;
bool compare_exchange_strong( T& expected, T desired,
                              std::memory_order order = 
                                  std::memory_order_seq_cst ) volatile noexcept;
/*Atomically compares the object representation of this with the object representation of expected, as if by std::memcmp, and if those are bitwise-equal, replaces the former with desired (performs read-modify-write operation). Otherwise, loads the actual value stored in this into expected (performs load operation). */

定义很多,只用看第一条定义就好了,将变量的值与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 = count.load();
desired = expected+1
while(!count.compare_exchange_weak(expected,desired)) {
    desired = expected + 1;
}

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

 

参考资料:

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

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

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

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

std::atomic<bool> x;
x.store(true,std::memory_order_seq_cst);

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

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

void store (T val, memory_order sync = memory_order_seq_cst) volatile noexcept;
void store (T val, memory_order sync = memory_order_seq_cst) noexcept;

T load (memory_order sync = memory_order_seq_cst) const volatile noexcept;
T load (memory_order sync = memory_order_seq_cst) const noexcept;

bool compare_exchange_weak (T& expected, T val,
           memory_order sync = memory_order_seq_cst) volatile noexcept;
bool compare_exchange_weak (T& expected, T val,
           memory_order sync = memory_order_seq_cst) noexcept;
bool compare_exchange_weak (T& expected, T val,
           memory_order success, memory_order failure) volatile noexcept;
bool compare_exchange_weak (T& expected, T val,
           memory_order success, memory_order failure) noexcept;

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

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

int a = 1;
int b = 2;
a *= 2;
b += 3;

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

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

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

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

bool flag = false;

while (!flag);
flag = true;
//TODO1
flag = false;
//TODO2

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

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

std::atomic<bool> flag = ATOMIC_VAR_INIT(false);
//TODO 0 
bool expected = false;
while(!flag.compare_exchange_strong(expected, true, std::memory_order_acquire))
    expected = false;
//TODO1
flag.store(false, std::memory_order_release);
//TODO2

一个小小的问题,之前谈到了编译器会按照自己的想法交换一些代码的位置,也就是说其他线程的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数据。

import tushare as ts
industry_info = ts.get_industry_classified()
profit_info = ts.get_profit_data(2017,1)

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

ts.get_industry_classified = data_cacher(ts.get_industry_classified)
ts.get_profit_data = data_cacher(ts.get_profit_data)

industry_info = ts.get_industry_classified()
profit_info = ts.get_profit_data(2017,1)

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

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

import attr
import pandas as pd

def data_cacher(func):
    def inner_function(*args,**kwargs):
        path = 'data/'+func.__name__
        for w in args:
            path += '&'+str(w)
        for w in kwargs:
            path += '&'+w+'='+str(kwargs[w])
        try:
            data = pd.DataFrame().from_csv(path)
            print("Use cache :",path)
        except FileNotFoundError:
            if 'fast_mode' in kwargs.keys() and kwargs['fast_mode'] == True:
                return pd.DataFrame()
            elif 'fast_mode' in kwargs.keys():
                del kwargs['fast_mode']
            print("Online => ",path)
            data = func(*args,**kwargs)
            #print(data,type(data),len(data))
            if len(data) == 0:
                print("Empty...")
                return data
            data.to_csv(path)
            data = pd.DataFrame().from_csv(path)
        return data
    return inner_function