分类目录归档:技术

无锁队列

去年在做一个项目时,遇到一个问题:需要处理一些数据,其输入速度是一定的,但输入的数据中只有一部分是实际需要处理,具体比例不一定,但希望能够保证实际处理数据的速度是一定的。所以,在这里用到了队列。首先对数据进行预处理,判断是否需要进行实际处理,如果需要则放入队列。同时还以一定的速率从队列取数据进行处理。这些操作都是在一个进程中,所以用 C 写了一个很简单的队列实现:基于共享内存,保证进程重启队列数据不会丢失;支持当队列满时自动 dump 到文件,使用文件作为存储。

最近又有一个这样的需求:一个进程产生数据放入队列,另一个进程判断队列长度,如果大于某一个值则进行处理,典型的“生产者 – 消费者”模型。这里就要求队列支持多进程,直接把之前写的队列拿来用会有问题,因为读和写队列可能同时进行,当两个进程同时修改某一个计数器时就可能会导致数据不一致。这里简单对队列进行加锁,即读和写是互斥的,就很容易的解决了这个问题。但在高并发时,读写互斥会带来性能上降低。之前公司内部看到有人分享过无锁队列的实现,研究了一下代码发现这个实现并不是真正的无锁队列,读写仍然是互斥的。

在参考了酷壳的文章:无锁队列的实现 之后,根据文章提供的思路,实现了一个无锁队列,它的要求是:

1、支持多进程(线程)同时对队列进行读写。

2、使用共享内存作为存储。

3、能够获取到当前队列的长度。

4 、兼容32位和64位系统

另外前题是:数据单元长度是固定的。

代码在此:https://github.com/haipome/lock_free_queue

大致的思路是:

在初始化时获取一大块内存自己分配,永不释放。将内存划分为控制区和数据区,数据区分成平均的数据块,每个数据块又有一个数据块头。通过数据块头,将队列中的数据组织成为链表。控制区里有两个“指针”分别指向链表的头和尾,这里并不能使用真正的指针,而是数据块的编号,使用 -1 标识链表的结束,为了解决队列在最开始时的初始化问题,所以这里多使用了一个编号为 -1 的数据块。另外,为了解决头尾指针指向同一数据块的问题,当 pop 时,读取的是头指针指向的数据块的下一个数据块,所以这里又多使用了一个数据块。

后记:多进程到处是坑,花了将近两天时间来 DEBUG

参考:

Legacy __sync Built-in Functions for Atomic Memory Access

使用 stdarg 的一些注意事项

stdarg 给C语言提供一种可变参数的功能,最常见的例子为 stdio 中的 printf 函数。

1、stdarg 仅支持整数、浮点数和指针(数组),其他如结构体是未定义行为。

2、stdarg 在入参时会对参数会进行默认的提升,比如所有低于整数会提升到 int, 低于 double 的会提升到 double.

3、在使用 type va_arg ( va_list ap, type ) 取参数时,为了保留整数的符号位,可统一按照有符号整数进行数据类型转换。

4、c99 中 stdarg 加入了对 64 位整数的支持

5、综合2、3、4,va_arg 中的 type 只应该出现 int, int64_t, double, void *

6、在 gcc 中,stdarg 是由编译器在编译时实现的,而非写好的宏或函数等。这样编译器可以做一些优化。

7、永远不要将混用数据类型,如入参时放入的是浮点数,取参却用 int 或 int64_t 这是一个未定义的操作。详细分析请看这边文章:x86-64体系下一个奇怪问题的定位

8、c99 中新增了va_copy,以进行安全的 va_list 对象的复制操作。

两种匈牙利命名法

在编写程序时,为变量命名是一件非常重要的事情,因为它对于代码读着的意义重大。而对于作者而言,在写程序时往往会忽略这点。但程序被阅读、维护的时间远大于其写作时间。并且有研究表明,在程序被写完六个月后,其作者本人也会忘了自己当初写这些代码时的想法。所以,给程序变量取好名字是一件非常重要的事情。关于变量命名,《代码大全》里有一整个章节讨论它,推荐阅读。

匈牙利命名法就是为变量命名的一种规则。一般认为,它是以变量的数据类型为基础的命名法,以代表数据类型的小写字母开头,然后使用驼峰法进行命名,比如 int iNum; char *pFoo; 等。然而,大部分时候,变量的含义比它的数据类型重要多了。知道了变量的含义,就知道了它的数据类型,而反过来并不能如此。并且,机械的在变量名字前面加上数据类型是一种很丑陋的做法。

在我供职的公司,有一件比较有意思的事,QQ 号有一个近似于标准的命名:uin, 据我推测,这是按照匈牙利命名法得来的,其初始定义为 unsigned int n; 首字母连起来变为 uin. 而 n 几乎是毫无含义的名字(典型的谭浩强式命名法)。我觉得,命名为 uid 会更有意义:user’s id. 更好笑的是,随着命名规则的变迁,有时候它被命名为 dwUin, 即 double world uin, 表明其为4个字节的整数,有时候又被命名为 ulUin, 即 unsigned long uin。

事实上,最初的匈牙利命名法并不是现在广为人知的那样,其前缀它更强调变量的目的而非变量的数据类型。这种用前缀强调变量目的的命名法被称为匈牙利应用命名法,而上面所述的为系统匈牙利命名法。应用命名法的前缀应该是有自然语义的,比如:rwPosition:变量代表一个行(”rw”)。

匈牙利命名法现在并不那么受欢迎,事实上,连其发源地微软在最新版的 .NET Framework 就不建议程序员使用匈牙利命名法。

至于用不用匈牙利命名法,则要看具体情况。如果团队有标准,就根据标准规则来,因为有效的标准是所能掌握的最有效的工具之一。

在数据类型非常有意义的情况下,比如在底层网络编程中,使用系统匈牙利命名法还是非常有好处的。比如用 c 前缀标识一个字节长度,w 表示两个字节长度,dw 代表四个字节等。其他情况,如果非要用匈牙利命名法,那就用匈牙利命应用名法。

MySQL 存储二进制数据

MySQL 支持在数据库中存储二进制数据,具体数据类型参考 MySQL 手册。然而,SQL 语句是文本化的,如果要向数据库中存储二进制数据,需要经过特殊的转化。通常的做法是将二进制数据或文件转换为对应的16进制字符串。

使用 insert 的例子:

**mysql**
create table test_table (test_blob tinyblob);

insert into test_table values(unhex(414243444500));

select * from test_table;
+-----------+
| test_blob |
+-----------+
| ABCDE     |
+-----------+
1 row in set (0.00 sec)

使用 load 的例子:

**shell**
echo '48494a4b4c00' > /tmp/test_load.txt

**mysql**
load data infile '/tmp/test_load.txt' into table test_table (test_blob) set test_blob=unhex(test_blob);

select * from test_table;
+-----------+
| test_blob |
+-----------+
| ABCDE     |
| HIPQR     |
+-----------+
2 rows in set (0.00 sec)

通常对于大的二进制文件,比如图片、word 文件等文件,放在数据库中不是一个好的做法,虽然数据库支持这样做。否则会导致数据库容量急剧增大,影响性能。

计算机系统中的时间

本文不完全的总结了 UNIX 环境编程中关于时间的操作。

计算机中有两种不同的时间参考系:一种为人们所熟悉的挂在墙上的时钟,即日历时间;另一种则为处理器时间,由于现代计算机系统一般为多任务系统,所以进程并不一直占用处理器。

计算机系统工作在数个不同的时间维度中,典型的 CPU 一个周期时间大约为 10^-9s, CPU 固定间隔时间的中断一般为 0.01s, 而人能够分辨的最小时间间隔在 0.1 s 左右。计算机能够提供的最小时间精度取决于其具体实现,一般计算机最少能提供其 CPU 时间片长度的时钟分辨率,一般为 10ms, 一些系统可以利用 CPU 周期数获取最高分辨率为 1ns 的时钟精度。

获取当前日期和时间

简单的,在 shell 中输入 date 命令即可打印出当前的日期和时间。

UNIX 系统提供的基本时间服务为国际标准时间公元1970年1月1日零点以来所经过的秒数,这个秒数是以数据类型 time_t 表示的,称为日历时间,可以使用 C 库函数 time 获得。另外 C 标准库 time.h 头文件中提供了一系列转换时间的函数,把 time 函数获得的秒数转换为可读的、本地的日期和时间。

#include <time.h>
time_t time(time_t *calptr); 

值得注意的是,time_t 被定义为 long int 类型,在32位系统中,最大只能表示到 2038 年左右。所幸随着64位系统的普及,这一问题将不复存在。

使用 gettimeofday 函数,能够获得比 time 函数具有更高分辨率的日历时间,最高能够达到微妙(10^-6s)级,但这取决与系统的具体实现。在有些平台上,操作系统能够使用 CPU 周期数来获取当前时间,能够达到微妙级的精度,但有些系统实现则使用系统时钟,一般只有 10ms (毫秒,10^-3s)的精度。

#include <sys/time.h>

struct timeval {
    long tv_sec; /* Seconds */
    long tv_usec; /* Microseconds */
}

int gettimeofday(struct timeval *tv, NULL);

在 linux 系统中,gettimeofday 的第二个参数应该简单的设置为 NULL, 因为它指向一个未被实现的校正时区的特性。

使用 clock_gettime 函数指定 clk_id 为 CLOCK_REALTIME 时可以获取系统纳秒级的日历时间。

#include <time.h>

struct timespec {
    time_t tv_sec; /* seconds */
    long tv_nsec; /* nanoseconds */
};

int clock_gettime(clockid_t clk_id, struct timespec *tp);

编译程序时需要链接 -lrt 库,否则会报错。

测量程序执行的时间

继续阅读

malloc 从哪里得到的内存空间

引子

在计算机高级编程语言中,C 语言相对来说是一种低级语言,从某种意义上讲,C 语言就是现代的“汇编语言”。说 C 语言低级很大程度上是因为 C 程序员需要手动管理存储,具体反应在公认最难最容易出错的指针上。比如编写 C 程序时,经常会出现莫名奇妙的段错误,并且内存泄漏会在不知不觉的情况下发生,直到耗尽你的计算机内存资源为止。更危险的则是缓冲区溢出,使程序非常容易受到攻击。

发明 C++ 的一个目的是为了提升 C 语言的抽象能力,还有一个目的就是为了消除指针,但 C++ 显然没有做到这一点。Java 则继承了 C++ 的遗愿,彻底的消灭了指针。Java 等高级语言采用严格的内存管理,动态的垃圾回收等机制使得程序员不用去手动管理内存,不用和底层打交道。但 C 语言的地位仍是无法取代的。在必须和底层打交道的时候,就得使用 C 语言(有时候甚至要用汇编语言),比如现代操作系统都是用 C 语言编写的。另外,高级语言在引入高级特征的同时,效率上就会有所损失,在非常强调执行效率的地方,C 语言通常是首选。

继续阅读