Archives

rp_filter 的一个例子

我们都知道 Linux 反向路由查询,它的原理很简单,检查流入本机的 IP 地址是否合法,是否可能路由进来,是否是最佳路由。但是像多数网络问题,理论很简单,代码你看了也能懂,可实际情况往往比较复杂。之前一直没有碰到过实际中的例子,最近总算碰到一个。

情况是这样的,我有两个 vlan 设备,eth0.7 和 eth0.9,都是经过 vconfig 创建的虚拟网卡,eth0 硬件本身不能处理 vlan tag。现在的问题是,我给这两个网卡配置了同一个 IP 地址,192.168.122.74。你也许会感觉奇怪,但这是可行的,毕竟 eth0.7 和 eth0.9 不在同一个 vlan!你可以想象成它们的网线接在不同的局域网中。好了,问题出来了,现在我们在另外一台机器,物理上连接着 eth0,上面分别发送 vlan tag 是 7 和 9 的两个 arp request,结果是只有先被 ifup 起来的那个网卡回应!为什么?

我一开始的想法这可能是内核的bug,毕竟 vlan 那一部分经常出现一些问题。但经过人肉跟踪 vlan tag 的处理流程,发现基本上不太可能是内核的问题,至少不是内核 vlan 处理代码的问题。其实,这部分内核代码经过重写之后还是很清晰的,推荐你有时间阅读一下。

所以问题一定是在 arp 处理的代码中,所以最后锁定到了 arp_process()。分析一下里面的代码你不难看到里面调用了 ip_route_input_noref(),所以路由有可能是其中一个因素。所以我们看一下路由表:

ip r s

default via 192.168.122.1 dev eth0
192.168.122.0/24 dev eth0.7 proto kernel scope link src 192.168.122.74
192.168.122.0/24 dev eth0.9 proto kernel scope link src 192.168.122.74

然后尝试换一个顺序对 eth0.7 和 eth0.9 进行 ifup,你会发现其实是路由的顺序决定了你能得到哪个 arp reply!这时你应该能明白了,是 rp_filter 在起作用。查看一下它们的 /proc/sys/net/ipv4/conf/X/rp_filter 设置,果然都是1,那么在这种情况下,eth0.9 因为不是最佳路由,因此发送给它的 arp request 就被丢弃了。我们也可以把 /proc/sys/net/ipv4/conf/eth0.9/log_martians 打开,很容易看到下面的log:

[87317.980514] IPv4: martian source 192.168.122.74 from 192.168.122.1, on dev eth0.9
[87317.998162] ll header: 00000000: ff ff ff ff ff ff 52 54 00 2e 23 92 08 06 00 01 ……RT..#…..
[87318.015159] ll header: 00000010: 08 00 ..

另外,分析过程中用到的两条相关的 tcpdump 命令:

tcpdump arp -xx -ni eth0

tcpdump -xx -ni eth0 vlan

为什么你不应该爱国

极权最有效的统治术是仇恨教育,塑造一个远在天边的外在敌人,人们就会忘记身边的痛苦。

——《1984》
在我们这个世界上,有些东西比爱国要重要一万倍,那就是生命与尊严、自由与民主、公平与正义。这些都是整个人类生存和发展的基础,是普世价值观,不会因为国家、种族的不同而有所改变。任何一个国家,尤其是你的国家,如果维护不了它们,那么这个国家就没有存在的必要和基础,就根本不值得你去爱。如果你的国家连为何要在一起组成这个国家都回答不了,那么这个国家就没有必要去爱。

自由就像空气,拥有它时,你甚至感觉不到它的存在。一旦没有自由时,它比什么都重要,值得你用生命去捍卫。而爱国,只是在此基础上可有可无的东西。没有自由,没有尊严就去谈爱国纯属扯淡,毫无意义。任何形式的爱国都不应该和这些普世价值观冲突,如果有,那你应该毫不犹豫地抛弃爱国,去捍卫自由和尊严,不管他们是不是你的同胞。

退一步讲,就算我们应该爱国,那爱国的前提至少也得是这个国家属于你才行吧?问题是,你觉得这个国家哪里属于你了?你买的房子,70年之后就不是你的了;代表你去开会的人,也不是你投票选出来的;你纳税养的人民公仆,也是先为领导服务;除了你必须纳税是真实的外,这个国家有哪个地方算是属于你的了?一个不属于你的国家你凭什么去爱?

更何况爱国本身就是不对的。如果爱国是正确的,那么纳粹统治期间的德国人民效忠纳粹就是正确的;如果爱国正确的,那么军国主义时期的日本人民崇尚战争就是正确的。既然你反对侵略战争,反对军国主义,那何必举着爱自己国家的旗号去反对别人爱国?既然你赞同普世价值观,那么当你自己同胞的自由受到侵害,社会正义得不到伸张时,你为什么不上街?而当一个遥远的假想的敌人购买了一个你这辈子都不会去的小岛时你反而上街了?就算这个小岛收回了又如何?你的自由会收回嘛?你国家的社会正义会多哪怕一点嘛?贪污腐败会减少一点嘛?不会!

相反,如果我们从今天起,不爱国,爱自由,爱公平,爱民主,努力争取自己的权利,那么我们的国家过不了多久就会变成一个自由、公平、民主的国家,就会变成一个真正值得你去爱的国家,到那时候爱国只是一个自然而然的感情罢了。

除非你能消除人类的爱国之心,否则世界就永远不会太平。

C binary literals

众所周知,C 语言中只有十进制、十六进制和八进制的常数表示(literal),没有二进制的常数表示。有时候我们很想用二进制的常数,因为它设置了哪些位一目了然。当然了,十六进制和八进制在某种程度上也行,对于熟练的人或许一眼就能看出,但是有二进制的常数表示不是更好嘛?

这里有人就给出了一个解决方法,构造一个宏接受二进制的“常量”,这样我们就可以通过它来直接使用二进制常量了。其实代码很容易理解,见下:

[c]
/ Binary constant generator macro
By Tom Torfs - donated to the public domain
/

/ All macro’s evaluate to compile-time constants /

/ ** helper macros */

/ turn a numeric literal into a hex constant
(avoids problems with leading zeroes)
8-bit constants max value 0x11111111, always fits in unsigned long
/

define HEX__(n) 0x##n##LU

/ 8-bit conversion function /

define B8__(x) ((x&0x0000000FLU)?1:0)

    +((x&0x000000F0LU)?2:0) 
    +((x&0x00000F00LU)?4:0) 
    +((x&0x0000F000LU)?8:0) 
    +((x&0x000F0000LU)?16:0) 
    +((x&0x00F00000LU)?32:0) 
    +((x&0x0F000000LU)?64:0) 
    +((x&0xF0000000LU)?128:0)

/ ** user macros */

/ for upto 8-bit binary constants /

define B8(d) ((unsigned char)B8(HEX(d)))

/ for upto 16-bit binary constants, MSB first /

define B16(dmsb,dlsb) (((unsigned short)B8(dmsb)<<8)

        + B8(dlsb))

/ for upto 32-bit binary constants, MSB first /

define B32(dmsb,db2,db3,dlsb) (((unsigned long)B8(dmsb)<<24)

            + ((unsigned long)B8(db2)&lt;&lt;16) 
            + ((unsigned long)B8(db3)&lt;&lt;8) 
            + B8(dlsb))

/ Sample usage:
B8(01010101) = 85
B16(10101010,01010101) = 43605
B32(10000000,11111111,10101010,01010101) = 2164238933
/

[/c]

把这段代码放到头文件中,使用的时候 #include 进去就行了。当然了,这最好还是编译器支持才行,幸运的是,gcc 从4.3 开始就已经支持二进制常数了!以0b或者0B为前缀即可,比如:0b01010101。

示例代码如下:

[c]

include

int main(void)
{
assert(B8(01010101) == 85);
assert(B8(01010101) == 0b01010101); //gcc extension!!
assert(B8(11111111) == 0xff);
assert(B8(00111111) == 077);
assert(B16(10101010,01010101) == 43605);
assert(B32(10000000,11111111,10101010,01010101) == 2164238933);
return 0;
}
[/c]

顺便说一句,在C++中你可以使用 std::bitset

bash 网络接口

我很早以前就见过 /dev/tcp/<host>/<port> 这个接口,但一直以为是某个 BSD 内核实现了一个特殊的文件系统,因为 Linux 上面很明显没有 /dev/tcp 这个目录。直到今天我才发现,这个目录其实是 bash 自己实现的!!这么以来就可以不借助wget,nc 来实现网络连接了!设计这么一个接口是要逆天了嘛!

使用这个接口很简单,如下所示:

bash-4.2$ cat </dev/tcp/time.nist.gov/13

56188 12-09-18 15:34:26 50 0 0 733.5 UTC(NIST) *

bash-4.2$ exec 3<>/dev/tcp/www.w3.org/80
bash-4.2$ echo -e “GET / HTTP/1.0nn” >&3
bash-4.2$ cat <&3
HTTP/1.1 200 OK
Date: Tue, 18 Sep 2012 15:41:08 GMT
Server: Apache/2
Content-Location: Home.html
Vary: negotiate,accept
TCN: choice
Last-Modified: Tue, 18 Sep 2012 14:06:27 GMT
ETag: “8f75-4c9fa65657ec0;89-3f26bd17a2f00”
Accept-Ranges: bytes
Content-Length: 36725
Cache-Control: max-age=600
Expires: Tue, 18 Sep 2012 15:51:08 GMT
P3P: policyref=”http://www.w3.org/2001/05/P3P/p3p.xml
Connection: close
Content-Type: text/html; charset=utf-8

在 bash 的源代码树 redir.c 文件中,我们不难发现下面的代码:

[c]
/ A list of pattern/value pairs for filenames that the redirection
code handles specially.
/
static STRING_INT_ALIST _redir_special_filenames[] = {

if !defined (HAVE_DEV_FD)

{ “/dev/fd/[0-9]*”, RF_DEVFD },

endif

if !defined (HAVE_DEV_STDIN)

{ “/dev/stderr”, RF_DEVSTDERR },
{ “/dev/stdin”, RF_DEVSTDIN },
{ “/dev/stdout”, RF_DEVSTDOUT },

endif

if defined (NETWORK_REDIRECTIONS)

{ “/dev/tcp//“, RF_DEVTCP },
{ “/dev/udp//“, RF_DEVUDP },

endif

{ (char *)NULL, -1 }
};


static int
redir_open (filename, flags, mode, ri)
char *filename;
int flags, mode;
enum r_instruction ri;
{
int fd, r;

r = find_string_in_alist (filename, _redir_special_filenames, 1);
if (r >= 0)
return (redir_special_open (r, filename, flags, mode, ri));

/ If we are in noclobber mode, you are not allowed to overwrite
existing files. Check before opening.
/
if (noclobber && CLOBBERING_REDIRECT (ri))
{
fd = noclobber_open (filename, flags, mode, ri);
if (fd == NOCLOBBER_REDIRECT)
return (NOCLOBBER_REDIRECT);
}
else
{
fd = open (filename, flags, mode);

if defined (AFS)

  if ((fd &lt; 0) &amp;&amp; (errno == EACCES))
    {
      fd = open (filename, flags &amp; ~O_CREAT, mode);
      errno = EACCES;       /* restore errno */
    }

endif / AFS /

}

return fd;
}

[/c]

可见,当 bash 发现重定向时它会先查看重定向的文件是不是特殊文件,如果是截获它,自行解释之,否则就打开这个文件。当然了,真正解释 /dev/tcp/HOST/PORT 的代码是在 lib/sh/netopen.c 中。

bash 的手册中也提到了这些特殊接口:

/dev/fd/fd
If fd is a valid integer, file descriptor fd is duplicated.
/dev/stdin
File descriptor 0 is duplicated.
/dev/stdout
File descriptor 1 is duplicated.
/dev/stderr
File descriptor 2 is duplicated.
/dev/tcp/host/port
If host is a valid hostname or Internet address, and port is an integer port number or service name, bash attempts
to open a TCP connection to the corresponding socket.
/dev/udp/host/port
If host is a valid hostname or Internet address, and port is an integer port number or service name, bash attempts
to open a UDP connection to the corresponding socket.

Linux 内核中的 KMP 实现

Linux 内核中使用到了字符串搜索,所以它也有 KMP 算法的实现,代码在 lib/ts_kmp.c 中。

Linux 内核中用到 KMP 算法的地方有三处:iptables string match 模块、iptables conntrack amanda 模块(不知道这个是用来干什么的)、以及 ematch qdisc。iptables string match 是通过字符串搜索来匹配一个包,然后进行相应的处理,比如用下面的命令可以阻止对domain.com服务器的HTTP请求:

iptables -I INPUT 1 -p tcp —dport 80 -m string —string “domain.com” —algo kmp -j DROP

至于 ematch qdisc,和它类似,可以通过字符串匹配到对应的包进行 QoS,比如这个例子

tc filter add dev eth0 parent 10:12 prio 10 protocol ip basic match ‘text(kmp foobar from 0 to 200)’ flowid 10:1

总之,在内核中实现 KMP 算法是有必要的。下面来看具体实现。

我们知道,KMP 算法中最核心的地方就是 prefix 的计算,也称为 next 数组,它用来表示当字符 pattern[i] 匹配失败后应该从 pattern[next[i]] 字符继续进行匹配,而不总是从头开始,因此它的时间复杂度是O(n)。如果你对 KMP 不熟悉的话,网上有很多介绍,我觉得这篇文章还算不错,在继续看下面的代码之前可以读一下它。

内核中实现比网上的很多代码都更容易理解,因为在匹配开始之前,它就先把 prefix 计算好了。计算 prefix 的函数是:

[c]
static inline void compute_prefix_tbl(const u8 pattern, unsigned int len,
unsigned int
prefix_tbl, int flags)
{
unsigned int k, q;
const u8 icase = flags & TS_IGNORECASE;

    for (k = 0, q = 1; q  0 &amp;&amp; (icase ? toupper(pattern[k]) : pattern[k])
                != (icase ? toupper(pattern[q]) : pattern[q]))
                    k = prefix_tbl[k-1];
            if ((icase ? toupper(pattern[k]) : pattern[k])
                == (icase ? toupper(pattern[q]) : pattern[q]))
                    k++;
            prefix_tbl[q] = k;
    }

}
[/c]

结合 KMP 实现的主函数来理解更一目了然:

[c]
static unsigned int kmp_find(struct ts_config conf, struct ts_state state)
{
struct ts_kmp kmp = ts_config_priv(conf);
unsigned int i, q = 0, text_len, consumed = state->offset;
const u8
text;
const int icase = conf->flags & TS_IGNORECASE;

    for (;;) {
            text_len = conf-&gt;get_next_block(consumed, &amp;text, conf, state);

            if (unlikely(text_len == 0))
                    break;

            for (i = 0; i  0 &amp;&amp; kmp-&gt;pattern[q]
                        != (icase ? toupper(text[i]) : text[i]))
                            q = kmp-&gt;prefix_tbl[q - 1];
                    if (kmp-&gt;pattern[q]
                        == (icase ? toupper(text[i]) : text[i]))
                            q++;
                    if (unlikely(q == kmp-&gt;pattern_len)) {
                            state-&gt;offset = consumed + i + 1;
                            return state-&gt;offset - kmp-&gt;pattern_len;
                    }
            }

            consumed += text_len;
    }

    return UINT_MAX;

}
[/c]

内核中的 KMP 函数接口是封装过的,你不能直接调用它。如果你的内核模块中要使用它,可以参考 lib/textsearch.c 中给的例子:

[c]
int pos;
struct ts_config conf;
struct ts_state state;
const char
pattern = “chicken”;
const char *example = “We dance the funky chicken”;

conf = textsearch_prepare(“kmp”, pattern, strlen(pattern),
GFP_KERNEL, TS_AUTOLOAD);
if (IS_ERR(conf)) {
err = PTR_ERR(conf);
goto errout;
}

pos = textsearch_find_continuous(conf, &state, example, strlen(example));
if (pos != UINT_MAX)
panic(“Oh my god, dancing chickens at %dn”, pos);

textsearch_destroy(conf);
[/c]

撤销 git 操作

今天脑抽了一下,在做 git rebase -i 的时候无意识地把某一个 commit 给合并到前一个 commit 里去了,结果是该 commit 丢失,而且前一个 commit 也搞砸了。怎么能撤销这个操作呢?

Google 搜索了一下,发现了还有 git reflog 这个命令,可以查看 git 命令的历史记录,比如我刚才的操作:

324c85e HEAD@{0}: rebase -i (finish): returning to refs/heads/ipv6
324c85e HEAD@{1}: checkout: moving from ipv6 to 324c85e
324c85e HEAD@{2}: rebase -i (finish): returning to refs/heads/ipv6
324c85e HEAD@{3}: rebase -i (pick): ipv6: use xxxx
9fc8e64 HEAD@{4}: rebase -i (fixup): ipv6: unify xxxx
2ea2149 HEAD@{5}: rebase -i (fixup): updating HEAD
8d1f07b HEAD@{6}: checkout: moving from ipv6 to 8d1f07b
0e118d2 HEAD@{7}: commit: ipv6: separate xxxx

可以看出 HEAD@{7} 这个点就是我应该重置回去的,然后执行 git reset HEAD@{7} 就行了!

通过 git reflog 也可以撤销 git reset 的操作,非常实用。

另外,我很惊讶似乎还有不少人不知道 git rebase -i 这个命令。这个命令真的十分强大,我几乎天天都在用,它既可以用来合并补丁,也可以用来切割补丁,还能修改 commit 的记录(具体可自行参考 git-rebase 的手册),可以说是 git 命令中的一把瑞士军刀啊!不过如果你的 git tree 是 public 的,最好不用或者少用 git rebase,我用 git rebase 大多都是在自己的非 public 的树上。

关于 schedule() 函数

今天在 LKML 上看到一个补丁:http://permalink.gmane.org/gmane.linux.kernel/1337629,它对 schedule() 函数做了很好的注释,分享一下:

+ *
+ * The main means of driving the scheduler and thus entering this function are:
+ *
+ *   1\. Explicit blocking: mutex, semaphore, waitqueue, etc.
+ *
+ *   2\. TIF_NEED_RESCHED flag is checked on interrupt and userspace return
+ *      paths. For example, see arch/x86/entry_64.S.
+ *
+ *      To drive preemption between tasks, the scheduler sets the flag in timer
+ *      interrupt handler scheduler_tick().
+ *
+ *   3\. Wakeups don't really cause entry into schedule(). They add a
+ *      task to the run-queue and that's it.
+ *
+ *      Now, if the new task added to the run-queue preempts the current
+ *      task, then the wakeup sets TIF_NEED_RESCHED and schedule() gets
+ *      called on the nearest possible occasion:
+ *
+ *       - If the kernel is preemptible (CONFIG_PREEMPT=y):
+ *
+ *         - in syscall or exception context, at the next outmost
+ *           preempt_enable(). (this might be as soon as the wake_up()'s
+ *           spin_unlock()!)
+ *
+ *         - in IRQ context, return from interrupt-handler to
+ *           preemptible context
+ *
+ *       - If the kernel is not preemptible (CONFIG_PREEMPT is not set)
+ *         then at the next:
+ *
+ *          - cond_resched() call
+ *          - explicit schedule() call
+ *          - return from syscall or exception to user-space
+ *          - return from interrupt-handler to user-space

KVM 中搭建 VLAN 和 IPv6 环境

普通的 IPv4 环境很简单,如果你使用 virt-manager 的话它自动都给你搭好了。每个 kvm guest 都在同一个子网内,通过 bridge 连接到一起,然后通过 host 上的 NAT 访问外网,如下所示:

# brctl show
bridge name bridge id STP enabled interfaces
virbr0 8000.5254002e2392 yes virbr0-nic
vnet0
vnet1

iptables -L -t nat

Chain PREROUTING (policy ACCEPT)
target prot opt source destination

Chain INPUT (policy ACCEPT)
target prot opt source destination

Chain OUTPUT (policy ACCEPT)
target prot opt source destination

Chain POSTROUTING (policy ACCEPT)
target prot opt source destination
MASQUERADE tcp — 192.168.122.0/24 !192.168.122.0/24 masq ports: 1024-65535
MASQUERADE udp — 192.168.122.0/24 !192.168.122.0/24 masq ports: 1024-65535
MASQUERADE all — 192.168.122.0/24 !192.168.122.0/24
稍微有点儿困难的是在此基础上搭建 VLAN 和 IPv6 环境。

先看VLAN,虽然我们现在还没有 openvswitch,我们可以通过 bridge 设置一个简单的 vlan 局域网。因为 virt-manager 默认使用的是 192.168.122.0/24,我为VLAN单独开了一个 192.168.1.0/24,有两台机器 A 和 B,A 上运行此VLAN的 DHCP 服务,B 就可以直接动态获取地址了。

机器 A 上运行:

vconfig add eth0 2
ifconfig eth0.2 192.168.1.1
dnsmasq —listen-address=192.168.1.1 -i eth0.2 —dhcp-range=192.168.1.2,192.168.1.240

机器 B 上运行:

vconfig add eth0 2
dhclient eth0.2

注:vconfig 已经过时了,现在都使用 ip,我之所以还使用它是因为整个命令比较短。;-)

再来看 IPv6,因为我对 IPv6 不熟悉,所以折腾了好长时间最后还是不得不使用 sit tunnel,而且 IP 地址也是静态手工设置的。还是假设 A 和 B 两台机器,先让 IPv4 在上面跑起来,然后在两台机器上分别运行下面的命令:

echo 1 > /proc/sys/net/ipv4/conf/all/forwarding
echo 1 > /proc/sys/net/ipv6/conf/all/forwarding
ip tunnel add sit1 mode sit local ${SELF} remote ${REMOTE} dev eth0
ip -6 addr add fd00:1:2:3::2/64 dev sit1
ip -6 route add fd00:1:2:3::1/64 dev sit1
ifconfig sit1 up

${SELF} 为自己的IPv4地址;${REMOTE}为对方的IPv4地址,即在A上面为B的地址,B上面为A的地址。他们的IPv6地址分别是fd00:1:2:3::1 和 fd00:1:2:3::2。

Update:如果使用 libvirt 的话,可以用 virsh net-edit <NET> 编辑网络配置,添加下面两行:

<ip family=’ipv6’ address=’fd00:1:2:3::1’ prefix=’64’>
</ip>

可参考这里

去尼玛的现实好么!

时间过得真快,离开大理已经四个多月了。早就开始各种怀念在大理的日子了,尤其是在这么炎热的夏天,一想到大理现在那只有20多度的气温就恨不得买张机票马上飞过去。可是很无奈,现实中有各种各样的事儿让我无法回到大理。

仿佛离开大理之后再也回不到那种无忧无虑的日子了。在大理的时候每天都那么悠闲,喝喝茶、晒晒太阳、摆摆地摊,从来不用为现在为将来发愁,因为来大理的人们大多数也都是这个状态。似乎也只有在大理这种地方,你才能活在当下,不为前途顾虑,不为现实烦恼,无所事事地活在当下……

仔细想想人这一生:小时候不太懂事,可以毫无顾虑地去玩,这应该是人生最快乐的时光;长大了上了学就开始顾虑各种考试;好不容易挨到高中毕业,上了大学又开始顾虑找工作,找对象;大学毕业了又开始顾虑工作薪水,买车买房子,结婚生孩子;有了孩子顾虑就更多了,一直到孩子长大成人,可那时候我们也已经老了,然后又不得不顾虑自己的身体健康……

你看看,我们这一辈子能够完完全全只为自己活着的时间能有多少?这其中,能够完完全全活在当下,不去考虑将来的时间更是少之又少!更何况,有些时候为了自己活着和为了别人活着会有很大的冲突,我们不得不在两者之间放弃一个。人这样活着能不累么!

有时候真想竖起中指对现实说:去尼玛的现实好么!去尼玛的前途好么!老子只想活在当下!

Parallelism != Concurrency

Parallelism,中文一般翻译成“并行”;Concurrency,中文一般翻译成“并发”。这两个词往往被混淆使用,即使在英文资料中,中文翻译使得这种情况变得更糟糕。其实这两个词的含义是完全不同的,这里并不是在咬文嚼字,而是想说明它们本质上确实有不同。为了表达方便,下文一律使用英文中的原词。

Wikipedia 上对 Concurrency 的定义如下:

Concurrent computing is a form of computing in which programs are designed as collections of interacting computational processes that may be executed in parallel. Concurrent programs (processes or threads) can be executed on a single processor by interleaving the execution steps of each in a time-slicing way, or can be executed in parallel by assigning each computational process to one of a set of processors that may be close or distributed across a network.
可见,concurrency 并不意味着一定是 parallelism,它是把多个互相作用的计算过程(注:上文第一句中的 processes 不是进程的意思!)组合起来的一种计算形式。为了完成一个大的任务,我们可以把它切割成几个独立的几个步骤,然后把每个步骤交给单独的线程去完成,那么在 UP 上 concurrency 看起来就像是这样:

Parallelism 的定义如下:

Parallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently (“in parallel”).
也就是多个计算同时执行,在 SMP 上如下图所示:

这里需要注意的是:广义上 parallelism 并不总是指 SMP,广义的 parallelism 也可以发生在指令上,比如支持 SIMD 的 CPU,像 Intel 的 SSE 指令;也可以发生在 CPU 内部的指令 pipeline 上。请结合上下文去理解。

考虑到现在流行的操作系统都是多任务的,那么 UP 也可以达到 SMP 的效果,对于用户空间的程序来说,多任务操作系统即使运行在 UP 上也是和 SMP 上一样的。因此下文中我们将不再区分 UP 和 SMP,并且假设操作系统就是多任务的,即所有多线程的程序都是并行运行的。

这时候,另一个问题随之而来:有 parallelism 的程序一定是 concurrent 的么?未必!根据上面 concurrency 的定义,不同的处理步骤之间需要是互相作用的(interacting),我们完全可以写一个多线程程序,线程之间没有任何互相的作用:比如我们要处理 [1 ~ 40000] 这个数组,我们可以启动4个线程,让它们分别处理 [1 ~ 10000]、[10000 ~ 20000]、[20000 ~ 30000]、[30000 ~ 40000],最后主线程把 4 个结果汇总成一个。这个多线程程序显然可以做到 parallelism,但它没有 concurrency!

有人这么认为,说 concurrency 是程序的属性;而 parallelism 程序执行时机器的属性。现在我们可以知道,这是不严格的。只有当 parallel 的程序的线程之间有了互相作用之后才会有 concurrency!concurrency 比 parallelism 要难得多。

Rob Pike 大牛是这么概括它们的区别的:

Concurrency is a way to structure a program by breaking it into pieces that can be executed independently. Communication is the means to coordinate the independent executions.
所以,concurrency 和 parallelism 的本质区别是,多个线程/进程(或程序的多个部分)之间有没有互相作用和交流。这种交流分两种:一种是共享内存,一种是消息传递。前者我们很熟悉,我们最常用的锁(Lock))或者信号量(Semaphore)就属于共享内存的一种。

另外,需要说明的是,并不是所有的 paraellel 的程序都使用多线程/进程,它们也可以使用 coroutine,使用 events。一言以蔽之,parallelism 是建立在同步(synchronous )代码的基础上,同步代码同时运行;而把一个程序分成几个同步的部分,它们之间允许进行 communication 就有 concurrency 了!

借用 Rob Pike 使用的图来说明一下就是:

Original Program

Parallel Program

Concurrent Program

从图中我们可以一目了然地看出两者之间并没有直接的关系。最后,在《Parallelism is not concurrency》一文中对此有更精辟的概括:

Concurrency is concerned with nondeterministic composition of programs (or their components). Parallelism is concerned with asymptotic efficiency of programs with deterministic behavior. Concurrency is all about managing the unmanageable[… ] Parallelism, on the other hand, is all about dependencies among the subcomputations of a deterministic computation.
参考资料:

1. http://stackoverflow.com/questions/1050222/concurrency-vs-parallelism-what-is-the-difference
2. http://existentialtype.wordpress.com/2011/03/17/parallelism-is-not-concurrency/
3. http://ghcmutterings.wordpress.com/2009/10/06/parallelism-concurrency/
4. http://stackoverflow.com/questions/1897993/difference-between-concurrent-programming-and-parallel-programming
5. http://concur.rspace.googlecode.com/hg/talk/concur.html#title-slide