离散数学之把妹要诀

离散数学课(CSCI 2110)上,讲到一个有趣的问题。

假设有五个男生,五个女生,每个人都在自己心中对五个异性有一定的preference排序,比如:

7cc829d3gw1el42973qnqj20fe07r74y

以上的排序表解读为:男生1最中意女生C,次中意女生B,次次中意女生E……

以此类推……

在五男五女全部成功脱光之后(假设都在圈子内部解决),定义一个unstable matching为:如果存在一对不是情侣的男女符合以下情况:

对于该男,该女在他的preference列表中处于现任女友的前面,对于该女,该男在他的preference列表中亦处于现任男友的前面,那么这对男女必然有私奔的倾向……

这样的情景即为unstable matching。反之,若不存在这样一对有私奔倾向的男女,即为stable matching。

问题是:是否在任何情况下,即不论各位的preference列表如何变化,只要男女数量相同,总是存在一个stable matching。 (当然,搅基之类的,是不可以的……)

在上面五男五女的例子里,一种stable matching如下:

7cc829d3gw1el4297sjusj20fe08fdgq

因为每个女生最中意的男生都不同,所以只要让女生们都选择跟自己最中意的男生在一起,她们就都不会有和其他男生私奔的想法。虽然男生们会表示略苦逼啊!仍然不失为一个stable matching……。

那么如果有n男n女,每个人心中都已经有了一个preference 列表,stable matching是不是一定存在呢?

1962年,Gale 和 Shapley 证明了stable matching是一定存在的。

首先他们给出了一个算法:

第一天早上:所有男生都向自己最中意的女生表白。

第一天中午:每个女生都被表白了n次(可能是0次)之后,拒绝了相对不太中意的那n-1位,hold住其中最中意的那位……即暂时不答应也不拒绝

第一天晚上,被拒绝的男生们在自己的preference列表中划掉了那个拒绝他的人……

第二天早上:所有没有被hold住的男生都向自己最中意的女生(无视已经被划掉的)表白。

第二天中午:女生们在那些向她表白的男生和已经hold住的那男生中选择最中意的一位,拒绝掉其他的。

第二天晚上:被拒绝的男生们在自己的preference列表中划掉拒绝了自己的人……

第三天,重复同样的过程……

第四天……

…………

这样的过程是有限的,不会一直循环下去。(Claim 1)

在这样的过程结束之后,每个女生都会hold住一个男生。(Claim 2)即在那一天之后没有男生可以继续表白了,这时女生们终于都向那个男生说了yes!

按照这样的过程,最后不会存在一对男女有私奔倾向(Claim3)

即完成了stable matching。

关于Claim1, Claim2, Claim3的证明,有兴趣的同学可以参考下面算法:

function stableMatching {
        Initialize all m ∈ M and w ∈ W to free
        while ∃ free man m who still has a woman w to propose to {
                w = m's highest ranked woman to whom he has not yet proposed
                if w is free
                        (m, w) become engaged
                else some pair (m', w) already exists
                        if w prefers m to m'
                                (m, w) become engaged
                                m' becomes free
                        else
                                (m', w) remain engaged
        }
}

下面是我们的关键问题:

在这样男生主动的算法中,占了优势的是男生还是女生呢?

表面上,男生略苦逼:要么被拒绝,要么被hold住还不知道是不是第二天就会被拒绝;女生则有着充分的选择权,享受着众星捧月的优越感,而且最差情况下到头来还是会有个伴儿也不至于孤家寡人……。。

但是实际上,占了优势的却是男生!

对于男生,

设最后他的女友是在他当初的preference列表的第i位,那么在i位之前的那些女生,他是怎么追也追不到的:

因为即使追到(即该女生一时糊涂答应了),

那么那个女生(记为Y)也必然会有比他心仪的对象另一男X(因为既然是一时糊涂,表明在当时的情况下有更心仪的男生已经向她表白),

而男X既然在当时向该女生表白,表明在Y之前的女生都拒绝了他,而如果Y也拒绝了他,他最后在一起的女生必定排在Y之后。

所以,X和Y是注定要私奔的!

所以嘛,男生没有追到的那些女生,都是命中不该有不可强求的……即他最后追到的女生是他最好的选择了……

对于女生:

设最后她的男友在她当初的preference列表的第i位,那么在i位之前的那些男生,都是还没机会向她表白就被其他女生hold住的,也就是说,她永远也等不到的最好的,多苦啊……

实际上,还可以证明,这个男友是在所有的stable matching中她能得到的最差的选择。

如果她选择了i+1,也就是拒绝了i,那么i最后只能跟不如她的女生(在i眼中)在一起。

而i+1也是不如i的,那么最后她还是要和i私奔。

即:若她选择了(在她眼中的)更差的男生,最后的配对就是unstable matching了,所以,没办法更差了!这已经是最差了有木有啊!

综上,我们惊奇地发现,男生追到的女生,是他最好的选择。

女生接受的男生,是她最差的选择。

如果情况相反,即女生主动追求男生,那么结论也会相反。

这个事实教导我们,主动表白是多么重要啊!

但是……

羞涩的女生如果不愿主动表白,还是有机会避免这种最差结果的。这时候,撒点小谎就显得非常重要……。

假设一个简单的情境,4 V 4 好了。

男1:BADC          A女:1234

男2:ABCD          B女:2143

男3:BCAD          C女:3241

男4:ADBC          D女:4231

按照Gale Shapley算法,

第一天,男1和男3向B女表白,男2和男4向A女表白。

A女喜欢2胜过喜欢4,但是她对2说谎了(“不,我不爱你……”)她拒绝了2

B女喜欢1胜过喜欢3,但是她对1说谎了,她拒绝了1

于是第二天早上,被拒的男1向A女表白,同时男2向B女表白……。。

最后的结果是:

1-A

2-B

3-C

4-D

女生们最终都得到了最佳选择。

以上的事实教导我们,当女生拒绝你的时候,可能她不是真的不喜欢你(至少在当时),所以…… 一切死缠烂打都是有理论依据滴,不可等同于耍流氓……

最后,如果是男生撒谎(即不按preference列表来表白,不能否认这样的2B青年的存在),他最终能不能交到更加心仪的女友呢?答案是不能。撒谎只会让男生交到在男生心目中排得更靠后的女生。原因不难分析,大家可以自行尝试。结论是:对于主动的一方,真诚和坦白是保证得到最优选所必需的……

Linux Kernel Memory Leak

一个Linux Kernel Memory Leak的定位过程。

最近客户那里报了个的OOM问题, 一开始以为是HTTP并发连接数太多,导致TCP在协议栈这一层分配的内存太多,
在这种情况下基本没有很好地解决方案,无非就是调整下TCP的一些参数如tcp_window_scaling, tcp_rmem, tcp_wmem等让单TCP连接占用的低端内存少一些, 这样服务器可以承受更多连接。

后来远程登录到客户的机器研究了下,发现OOM的时候连接数并不多,才300多TCP连接, 所以排除了并发连接数太多的问题,在分析OOM log的时候发现有时OOM发生kernel干掉的进程才释放了200多K的物理内存,
说明当时系统的内存已经极其紧缺,连200K物理内存都不放过,但是干掉进程后系统并没有释放多少内存,紧接着又发生了多次OOM, 于是怀疑耗尽内存的源头不在应用层,而在内核。

用slabtop发现了OOM的根源, 我们的服务器物理内存一共才9G, 内核的ip_dst_cache占去了7G多, 加上其他一些关键业务进程占用的内存, 导致系统内存耗尽。
而且ip_dst_cache的内存一直在增长。
查了下内核源码, ip_dst_cache的内存主要分配给了内核路由表rt_table, 这个问题应该跟内核协议栈相关。

后来公司的TS提供了一些关键的线索, 他们做了一些测试发现在干掉某个进程的时候, ip_dst_cache停止增长,这个进程主要业务就是每隔一秒钟向网络里的其他服务器发送4个多播UDP包用于同步系统状态信息。
现在范围已经很小了, 肯定跟内核的多播IP报文的处理有关系。

于是痛苦的读kernel代码开始了, 分析了从ip_rcv_finish内核收到IP报文开始, 在IP协议栈报文向上传递到ip_route_input_noref->ip_route_input_mc(就是在这里内核从ip_dst_cache分配了rt_table)->ip_local_deliver, 然后一直到UDP多播报文的处理udp_rcv->__udp4_lib_rcv->__udp4_lib_mcast_deliver, 一切流程貌似正常,所有IP/UDP报文分配的rt_table在应用层通过recv系统调用跑到udp_recvmsg的时候会正常释放。

到这里一切都卡住了没有进展,后来分析了一下从客户那里抓的pcap, 发现了一点线索, 就是在这4个多播报文当中,有一个多播报文因为太大(大于1500), 被分成了两个分片。
难道是因为IP分片导致了内存泄露?

读了下内核IP分片重组的那块代码,终于找到了问题所在:)
流程是这样的,ip_local_deliver收到新的IP报文的时候会检查是不是分片, 如果是分片,会调用ip_defrag–>ip_frag_queue->ip_frag_reasm重组分片,
问题就是出在重组分片的时候,上代码:

static int ip_frag_reasm(struct ipq *qp, struct sk_buff *prev,
                        struct net_device *dev)
{
        for (fp = head->next; fp;) {
                if (skb_try_coalesce(head, fp, &headstolen, &delta)) {
                        kfree_skb_partial(fp, headstolen);
                } else {
                        if (!skb_shinfo(head)->frag_list)
                                skb_shinfo(head)->frag_list = fp;
                        head->data_len += fp->len;
                        head->len += fp->len;
                        head->truesize += fp->truesize;
                }
                fp = next;
        }
}

在分片重组的时候, 内核合并所有分片到一个skb_buff, 这样之前分片的skb就没用了,内核会调用kfree_skb_partial释放分片,
内存泄露就发生在kfree_skb_partial。这是出问题的版本,内核只是放了skb本身, 并没有有释放skb引用的dst_entry/rt_table

void kfree_skb_partial(struct sk_buff *skb, bool head_stolen)
{
        if (head_stolen)
                kmem_cache_free(skbuff_head_cache, skb);
        else
                __kfree_skb(skb);
}

对比了下3.12.6的内核代码,这个问题已经修正了, 就是这行skb_release_head_state(skb):

void kfree_skb_partial(struct sk_buff *skb, bool head_stolen)
{
        if (head_stolen) {
                skb_release_head_state(skb);
                kmem_cache_free(skbuff_head_cache, skb);
        } else {
                __kfree_skb(skb);
        }
}

改完之后重新上线测试, 一切OK, ip_dst_cache一直维持在200K以内不怎么增长。
终于可以松一口气了

需要说明的是我们服务器的内核版本是3.6.3

生活是一種偶然

《和自己喜歡的一切在一起》是我讀完的第壹本韓寒的書。

去年的時候曾整理過自己生活中遇到的壹些事物,寫了《和自己喜歡的壹切在壹起》。文中只說了這句話是從朋友的書中無意看到的,如今算是拿起來,完整的讀了壹遍。

這不是因爲我不喜歡或者不曾接觸過這個作者,相反韓寒的名字如雷貫耳,壹直在心中是個高大的存在,可是有些時候人就是很奇怪,韓寒太特別了,反而不願意去了解了,似乎離我太遠。我不是很喜歡很犀利的文字。可是到現在我才發現,我的主觀意識的多麽可笑,爲什麽總是先入爲主,在沒有任何了解的情況下,自顧自的給別人貼上標簽呢。

我也不知道從幾何時,自己變得悲觀,對社會上的種種總是無可奈何,常常用類似“每個人都有他的命運,無論發生什麽我都會努力接受”來淡化社會上種種。已經很少憤青了,而這或多或少有那些悲劇不曾發生在自己身上的慶幸吧。我總是在想,每天都會有那麽多不公平的事,每天都有那麽多人在受苦。

世界有這麽多變幻莫測的因素,妳的人生卻沒有什麽變故,生活是壹種偶然。

我變得越來越理解這個社會,但並不代表我會越來越接受這個社會。

對于韓寒,我了解的不多,可是僅通過這本書,就能很深刻的感受到韓寒是多麽真的壹個人。太真的文字總是會引來爭議,因爲中國最卻的就是真實。我們似乎虛僞著爲別人活了太久。

世界很大,也很小,我看到的就是我全部的世界。我只想守護好我的世界,世界的悲歡離合離我太遠,我不是救世主。做個純真正直的人,不給這個社會添堵,真的就夠了。

我所理解的生活,在偶然中努力。

科学解释暗黑3极品装备掉落与人品的关系

人品值一直是diablo系列的一个谣言,据说,人品值是这样的。

1.建立人物时候随机生成一个隐藏数值。(这一条我有科学解释)

2.这个隐藏数值会随着带人,给新人装备,扶老奶奶过马路而轻微提升。(这一条应该是选择性记忆的心理学解释)

好了,我来解释diablo中的算法。现代计算机使用的随机数生成器多数是线性同余生成器,虽然有更好的随机数发生器,但是越好的随机数发生器意味着越高的时间开销,往往只有在对随机性要求很高的科学仿真中才会采用,至于网游,一般都会选择最简单,计算速度越快的算法。

有人反编译过diablo2的代码,给出过diablo2的随机代码生成器,是算法简单,计算速度很快的线性同余计算法。而diablo3的官方说法是,mf,随机等问题是继承diablo2的算法。

但是线性同余算法有一个问题,这种算法有一定的聚合性,就是说,生成的随机数不会均匀的弥散整个数值空间,在某些点上被强化而某些点永远都达不到,具体哪些点达不到和你选择的random seeds有关。在游戏中的表现就是,你会经常出某种东西,而某些东西你用这个号得话一辈子都打不出。本人在diablo2中曾经一个赛季打出近10个权冠 (别说不值钱,hc的),光靠卖权冠做了一把无限,但是死亡深度和破隐就是打不出。

所以,个人觉得,游戏中,在建人物的时候,为这个人物生成一段母seed,然后以后的seed和这个母seed先关是有可能的,这就是所谓的人品值,所以rp值的谣言也许确实是成立的,所以,当你想要什么装备,却很久都不出的话,请删号重练一个。

回到游戏中,diablo 3目前也有这种情况,有些人娜戒,骷髅重复出,有些人老是出垃圾暗金,比如我,不出装备,一直爆工匠书,注定一辈子打铁的命。

Golang 的 12345

这几天认真玩起了 Go。所谓认真玩,就是拿 Go 写点程序,前后大约两千行吧。

据说 Go 的最佳开发平台是 Mac OS & Linux ,在自己和公司电脑都试了试,确实很方便。Windows 版还是算了吧,应该也可以用了,但不抱什么希望。

就几天来的经历,我喜欢上这门新语言有如下原因:

mix-in 的接口风格。非常接近于我在用 C 时惯用的面向对象风格。有语法上的支持要舒服多了。以平坦的方式编写函数,没有层次。而后用 interface 把需要的功能聚合在一起。没有继承层次,只有组合功能。

两个问题,很纠结

1. 读写数据时,产生fatal: invalid metadata block,进而导致gfs2文件系统挂了,进而再导致dlm死锁,然后kernel挂了,机器宕机。

遥记得这个问题我曾经在修改gfs2源码的时候加入了检测文件系统出了问题自动发withdraw然后umount,发通知让dlm等安全退出,为毛会出现这种问题。

是继续改gfs2还是改kernel呢。。。

2. 无操作的情况下cib占用cpu始终在50%左右徘徊

这个现象显然是不科学。。。
我明明移除简化了操作流程,也去掉了一些不必要的锁。。。