北海道旅游——札幌附近地区攻略

札幌

白色恋人巧克力工坊

在宫の沢站,从大通坐东西线,340就可达。

工坊庭院非常漂亮,整点有音乐表演。一楼进去是商店,可以在那里买到全系列的产品。小火车在往里走,不过我们去的时候人挺多,很遗憾没坐上。

工坊在9:30, 11:30, 13:30, 15:30提供亲手制作巧克力饼干的课程,必须赶准时间否则就得等下一批。参观博物馆是600一人,我们报的课程是1250的,报名者参观打折到500。

课程并不复杂,戴好装备走进去,大约一刻钟到半小时的操作后,出来等烘陪结果。大约20分钟后再进去裱花,然后就可以带走了。很多小孩进去体验的,大人还可以在外面看着。

带小孩进去的需要注意安全,最好有大人陪同。

博物馆里有很多老式留音机,碰到半点(准确时间不确定)还会有表演。

建议一早冲过去,踩准点,否则容易碰到白白等着。做饼干的空余,出来在餐厅喝个茶,吃点糕点,看看风景。一般还能看到音乐表演。逛到楼下直接买点东西就走。

36片的巧克力饼干折扣价在2400日元上下,目前汇率折合人民币120上下。

蟹将军

在ささきの那里,离开狸小路非常近。从大通可以走到。

全蟹宴大概4300-4500,按现在汇率,200多点的样子。店的定位非常高档,所以绝对超值。

整个店都是要脱鞋,全地板铺塌塌米。上了一堆螃蟹,最后还有一道泡饭,是穿着和服的女服务员帮着处理的。手势超级优雅,感觉碉堡了。

狸小路

在大通南边一点,是一条非常热闹的步行街。

去的话可以先学学小钢珠(パチンコ)的玩法。其实没啥好学的,就是扔进去,完了按按钮。但是老婆楞是没看懂,没上去玩。主要是,我们完全没想到这种简单的规则还能当游戏玩。。。

狸小路5那里有个免税店,店员的中文相当不错,价格也基本是最低了(至少白色恋人巧克力是这样)。我在那里基本扫齐了所有货。

狸小路上有一家饺子の王將,两盘饺子加一个杏仁豆腐才733。换成人民币大约36,和上海基本持平。关键是,好吃到爆啊!!!顿时觉得上海的饺子店弱爆了。

居酒屋

我们总计吃了两次居酒屋。

首先,大部分居酒屋都有服务费。例如毛巾,前菜什么的。一般是一个人500上下。我们第一次不知道,进去点了1500的东西,被收了2500。老婆日语太差,还不敢问。后来就明白了,大部分这种店都是这样的。只要是居酒屋类的,都会收取一定的服务费。蟹将军不是很确定,可能也是收了服务费的。

但是,居酒屋的点菜超级困难。根据大熊酱的说法,日语二级进去也未必能全身而退。我老婆日语还不一定比我强,去了就要英文菜单了。

居酒屋基本就是吃个意思。论性价比还是饺子の王將,或者吉野家之类的比较好。可是真去日本的,基本不会选择这些。

小樽

小樽没啥好说的,总共才去了半天。

nikka的威士忌酒厂没啥好看的,倒是商店里面的商品还算不错。有很漂亮的小瓶威士忌,当纪念品很好。

情书拍摄地很坑。

商店街那里看个人喜欢。玻璃制品和八音盒都很漂亮,让人担心自己的钱包。有空的话可以多逛一下,买点海鲜吃。

滑雪

坑爹。第一天跑过去,大雪关门。第三天跑过去,还有半个小时关门。

所以,这次滑雪行程没有滑到雪。

不要玩一些太少人玩的东西啊,只有一个人玩的结果就是很可能投票失败。。。

洞爷湖

我们住的酒店叫做洞爷湖万世屋。我开始还不知道。出门一看,越后屋。我了个去。尼玛万事屋不是因为空知英秋根本住过这间吧。

不管了,扫货。整个店里面,大部分动漫都是银魂和天体的周边(偷偷说,酒店去餐厅路上还能看到天体的海报)。

登别

地狱谷有鬼灯的画报。好像还有周边,但是没空逛。

上下文切换技术

上下文切换技术

简述

在进一步之前,让我们先回顾一下各种上下文切换技术。

不过首先说明一点术语。当我们说“上下文”的时候,指的是程序在执行中的一个状态。通常我们会用调用栈来表示这个状态——栈记载了每个调用层级执行到哪里,还有执行时的环境情况等所有有关的信息。

当我们说“上下文切换”的时候,表达的是一种从一个上下文切换到另一个上下文执行的技术。而“调度”指的是决定哪个上下文可以获得接下去的CPU时间的方法。

进程

进程是一种古老而典型的上下文系统,每个进程有独立的地址空间,资源句柄,他们互相之间不发生干扰。

每个进程在内核中会有一个数据结构进行描述,我们称其为进程描述符。这些描述符包含了系统管理进程所需的信息,并且放在一个叫做任务队列的队列里面。

很显然,当新建进程时,我们需要分配新的进程描述符,并且分配新的地址空间(和父地址空间的映射保持一致,但是两者同时进入COW状态)。这些过程需要一定的开销。

进程状态

忽略去linux内核复杂的状态转移表,我们实际上可以把进程状态归结为三个最主要的状态:就绪态,运行态,睡眠态。这就是任何一本系统书上都有的三态转换图。

就绪和执行可以互相转换,基本这就是调度的过程。而当执行态程序需要等待某些条件(最典型就是IO)时,就会陷入睡眠态。而条件达成后,一般会自动进入就绪。

阻塞

当进程需要在某个文件句柄上做IO,这个fd又没有数据给他的时候,就会发生阻塞。具体来说,就是记录XX进程阻塞在了XX fd上,然后将进程标记为睡眠态,并调度出去。当fd上有数据时(例如对端发送的数据到达),就会唤醒阻塞在fd上的进程。进程会随后进入就绪队列,等待合适的时间被调度。

阻塞后的唤醒也是一个很有意思的话题。当多个上下文阻塞在一个fd上(虽然不多见,但是后面可以看到一个例子),而且fd就绪时,应该唤醒多少个上下文呢?传统上应当唤醒所有上下文,因为如果仅唤醒一个,而这个上下文又不能消费所有数据时,就会使得其他上下文处于无谓的死锁中。

但是有个著名的例子——accept,也是使用读就绪来表示收到的。如果试图用多个线程来accept会发生什么?当有新连接时,所有上下文都会就绪,但是只有第一个可以实际获得fd,其他的被调度后又立刻阻塞。这就是惊群问题thundering herd problem

现代linux内核已经解决了这个问题,方法惊人的简单——accept方法加锁。(inet_connection_sock.c:inet_csk_wait_for_connect)

线程

线程是一种轻量进程,实际上在linux内核中,两者几乎没有差别,除了一点——线程并不产生新的地址空间和资源描述符表,而是复用父进程的。

但是无论如何,线程的调度和进程一样,必须陷入内核态。

传统网络服务模型

进程模型

为每个客户分配一个进程。优点是业务隔离,在一个进程中出现的错误不至于影响整个系统,甚至其他进程。Oracle传统上就是进程模型。

缺点是进程的分配和释放有非常高的成本。因此Oracle需要连接池来保持连接减少新建和释放,同时尽量复用连接而不是随意的新建连接。

线程模型

为每客户分配一个线程。优点是更轻量,建立和释放速度更快,而且多个上下文间的通讯速度非常快。

缺点是一个线程出现问题容易将整个系统搞崩溃。

一个例子

py_http_fork_thread.py

在这个例子中,线程模式和进程模式可以轻易的互换。

如何工作的

  1. 父进程监听服务端口
  2. 在有新连接建立的时候,父进程执行fork,产生一个子进程副本
  3. 如果子进程需要的话,可以exec(例如CGI)
  4. 父进程执行(理论上应当先执行子进程,因为exec执行的快可以避免COW)到accept后,发生阻塞
  5. 上下文调度,内核调度器选择下一个上下文,如无意外,应当就是刚刚派生的子进程
  6. 子进程进程进入读取处理状态,阻塞在read调用上,所有上下文均进入睡眠态
  7. 随着SYN或者数据报文到来,CPU会唤醒对应fd上阻塞的上下文(wait_queue),切换到就绪态,并加入调度队列
  8. 上下文继续执行到下一个阻塞调用,或者因为时间片耗尽被挂起

关于更多细节,可以看这里。这篇文章里还介绍了epoll的工作细节。

评价

  • 同步模型,编写自然,每个上下文可以当作其他上下文不存在一样的操作,每次读取数据可以当作必然能读取到。
  • 进程模型自然的隔离了连接。即使程序复杂且易崩溃,也只影响一个连接而不是在整个系统。
  • 生成和释放开销很大(效率测试的进程fork和线程模式开销测试),需要考虑复用。
  • 进程模式的多客户通讯比较麻烦,尤其在共享大量数据的时候。

C10K问题

描述

当同时连接数在10K左右时,传统模型就不再适用。实际上在效率测试报告的线程切换开销一节可以看到,超过1K后性能就差的一塌糊涂了。

更细节描述,可以看这里

进程模型的问题

在C10K的时候,启动和关闭这么多进程是不可接受的开销。事实上单纯的进程fork模型在C1K时就应当抛弃了。

Apache的prefork模型,是使用预先分配(pre)的进程池。这些进程是被复用的。但即便是复用,本文所描述的很多问题仍不可避免。

线程模式的问题

从任何测试都可以表明,线程模式比进程模式更耐久一些,性能更好。但是在面对C10K还是力不从心的。问题是,线程模式的问题出在哪里呢?

内存?

有些人可能认为线程模型的失败首先在于内存。如果你这么认为,一定是因为你查阅了非常老的资料,并且没仔细思考过。

你可能看到资料说,一个线程栈会消耗8M内存(linux默认值,ulimit可以看到),512个线程栈就会消耗4G内存,而10K个线程就是80G。所以首先要考虑调整栈深度,并考虑爆栈问题。

听起来很有道理,问题是——linux的栈是通过缺页来分配内存的(How does stack allocation work in Linux?),不是所有栈地址空间都分配了内存。因此,8M是最大消耗,实际的内存消耗只会略大于实际需要的内存(内部损耗,每个在4k以内)。但是内存一旦被分配,就很难回收(除非线程结束),这是线程模式的缺陷。

这个问题提出的前提是,32位下地址空间有限。虽然10K个线程不一定会耗尽内存,但是512个线程一定会耗尽地址空间。然而这个问题对于目前已经成为主流的64位系统来说根本不存在。

内核陷入开销?

所谓内核陷入开销,就是指CPU从非特权转向特权,并且做输入检查的一些开销。这些开销在不同的系统上差异很大。

线程模型主要通过陷入切换上下文,因此陷入开销大听起来有点道理。

实际上,这也是不成立的。线程在什么时候发生陷入切换?正常情况下,应当是IO阻塞的时候。同样的IO量,难道其他模型就不需要陷入了么?只是非阻塞模型有很大可能直接返回,并不发生上下文切换而已。

效率测试报告的基础调用开销一节,证实了当代操作系统上内核陷入开销是非常惊人的小的(10个时钟周期这个量级)。

线程模型的问题在于切换成本高

熟悉linux内核的应该知道,近代linux调度器经过几个阶段的发展。

  1. linux2.4的调度器。
  2. O(1)调度器。
  3. CFS。

实际上直到O(1),调度器的调度复杂度才和队列长度无关。在此之前,过多的线程会使得开销随着线程数增长(不保证线性)。

O(1)调度器看起来似乎是完全不随着线程的影响。但是这个调度器有显著的缺点——难于理解和维护,并且在一些情况下会导致交互式程序响应缓慢。

CFS使用红黑树管理就绪队列。每次调度,上下文状态转换,都会查询或者变更红黑树。红黑树的开销大约是O(logm),其中m大约为活跃上下文数(准确的说是同优先级上下文数),大约和活跃的客户数相当。

因此,每当线程试图读写网络,并遇到阻塞时,都会发生O(logm)级别的开销。而且每次收到报文,唤醒阻塞在fd上的上下文时,同样要付出O(logm)级别的开销。

这里参考了这篇文章,在此表示感谢。这篇文章里面清楚的介绍了各种linux调度器技术(不包括bfs)。

分析

O(logm)的开销看似并不大,但是却是一个无法接受的开销。因为IO阻塞是一个经常发生的事情。每次IO阻塞,都会发生开销。而且决定活跃线程数的是用户,这不是我们可控制的。更糟糕的是,当性能下降,响应速度下降时。同样的用户数下,活跃上下文会上升(因为响应变慢了)。这会进一步拉低性能。

问题的关键在于,http服务并不需要对每个用户完全公平,偶尔某个用户的响应时间大大的延长了是可以接受的。在这种情况下,使用红黑树去组织待处理fd列表(其实是上下文列表),并且反复计算和调度,是无谓的开销。

多路复用

简述

要突破C10K问题,必须减少系统内活跃上下文数(其实未必,例如换一个调度器,例如使用RT的SCHED_RR),因此就要求一个上下文同时处理多个链接。而要做到这点,就必须在每次系统调用读取或写入数据时立刻返回。否则上下文持续阻塞在调用上,如何能够复用?这要求fd处于非阻塞状态,或者数据就绪。

上文所说的所有IO操作,其实都特指了他的阻塞版本。所谓阻塞,就是上下文在IO调用上等待直到有合适的数据为止。这种模式给人一种“只要读取数据就必定能读到”的感觉。而非阻塞调用,就是上下文立刻返回。如果有数据,带回数据。如果没有数据,带回错误(EAGAIN)。因此,“虽然发生错误,但是不代表出错”。

但是即使有了非阻塞模式,依然绕不过就绪通知问题。如果没有合适的就绪通知技术,我们只能在多个fd中盲目的重试,直到碰巧读到一个就绪的fd为止。这个效率之差可想而知。

在就绪通知技术上,有两种大的模式——就绪事件通知和异步IO。其差别简要来说有两点。就绪通知维护一个状态,由用户读取。而异步IO由系统调用用户的回调函数。就绪通知在数据就绪时就生效,而异步IO直到数据IO完成才发生回调。

linux下的主流方案一直是就绪通知,其内核态异步IO方案甚至没有被封装到glibc里去。围绕就绪通知,linux总共提出过三种解决方案。我们绕过select和poll方案,看看epoll方案的特性。

另外提一点。有趣的是,当使用了epoll后(更准确说只有在LT模式下),fd是否为非阻塞其实已经不重要了。因为epoll保证每次去读取的时候都能读到数据,因此不会阻塞在调用上。

epoll

用户可以新建一个epoll文件句柄,并且将其他fd和这个”epoll fd”关联。此后可以通过epoll fd读取到所有就绪的文件句柄。

epoll有两大模式,ET和LT。LT模式下,每次读取就绪句柄都会读取出完整的就绪句柄。而ET模式下,只给出上次到这次调用间新就绪的句柄。换个说法,如果ET模式下某次读取出了一个句柄,这个句柄从未被读取完过——也就是从没有从就绪变为未就绪。那么这个句柄就永远不会被新的调用返回,哪怕上面其实充满了数据——因为句柄无法经历从非就绪变为就绪的过程。

类似CFS,epoll也使用了红黑树——不过是用于组织加入epoll的所有fd。epoll的就绪列表使用的是双向队列。这方便系统将某个fd加入队列中,或者从队列中解除。

要进一步了解epoll的具体实现,可以参考这篇linux下poll和epoll内核源码剖析

性能

如果使用非阻塞函数,就不存在阻塞IO导致上下文切换了,而是变为时间片耗尽被抢占(大部分情况下如此),因此读写的额外开销被消除。而epoll的常规操作,都是O(1)量级的。而epoll wait的复制动作,则和当前需要返回的fd数有关(在LT模式下几乎就等同于上面的m,而ET模式下则会大大减少)。

但是epoll存在一点细节问题。epoll fd的管理使用红黑树,因此在加入和删除时需要O(logn)复杂度(n为总连接数),而且关联操作还必须每个fd调用一次。因此在大连接量下频繁建立和关闭连接仍然有一定性能问题(超短连接)。不过关联操作调用毕竟比较少。如果确实是超短连接,tcp连接和释放开销就很难接受了,所以对总体性能影响不大。

固有缺陷

原理上说,epoll实现了一个wait_queue的回调函数,因此原理上可以监听任何能够激活wait_queue的对象。但是epoll的最大问题是无法用于普通文件,因为普通文件始终是就绪的——虽然在读取的时候不是这样。

这导致基于epoll的各种方案,一旦读到普通文件上下文仍然会阻塞。golang为了解决这个问题,在每次调用syscall的时候,会独立的启动一个线程,在独立的线程中进行调用。因此golang在IO普通文件的时候网络不会阻塞。

推测libaio解决了这个问题(TODO: test)。

事件通知机制下的几种程序设计模型

简述

使用通知机制的一大缺憾就是,用户进行IO操作后会陷入茫然——IO没有完成,所以当前上下文不能继续执行。但是由于复用线程的要求,当前线程还需要接着执行。所以,在如何进行异步编程上,又分化出数种方案。

用户态调度

首先需要知道的一点就是,异步编程大多数情况下都伴随着用户态调度问题——即使不使用上下文技术。

因为系统不会自动根据fd的阻塞状况来唤醒合适的上下文了,所以这个工作必须由其他人——一般就是某种框架——来完成。

你可以想像一个fd映射到对象的大map表,当我们从epoll中得知某个fd就绪后,需要唤醒某种对象,让他处理fd对应的数据。

当然,实际情况会更加复杂一些。原则上所有不占用CPU时间的等待都需要中断执行,陷入睡眠,并且交由某种机构管理,等待合适的机会被唤醒。例如sleep,或是文件IO,还有lock。更精确的说,所有在内核里面涉及到wait_queue的,在框架里面都需要做这种机制——也就是把内核的调度和等待搬到用户态来。

当然,其实也有反过来的方案——就是把程序扔到内核里面去。其中最著名的实例大概是微软的http服务器了。

这个所谓的“可唤醒可中断对象”,用的最多的就是协程。

协程

协程是一种编程组件,可以在不陷入内核的情况进行上下文切换。如此一来,我们就可以把协程上下文对象关联到fd,让fd就绪后协程恢复执行。

当然,由于当前地址空间和资源描述符的切换无论如何需要内核完成,因此协程所能调度的,只有在同一进程中的不同上下文而已。

如何做到

这是如何做到的呢?

我们在内核里实行上下文切换的时候,其实是将当前所有寄存器保存到内存中,然后从另一块内存中载入另一组已经被保存的寄存器。对于图灵机来说,当前状态寄存器意味着机器状态——也就是整个上下文。其余内容,包括栈上内存,堆上对象,都是直接或者间接的通过寄存器来访问的。

但是请仔细想想,寄存器更换这种事情,似乎不需要进入内核态么。事实上我们在用户态切换的时候,就是用了类似方案。

C coroutine的实现,基本大多是保存现场和恢复之类的过程。python则是保存当前thread的top frame(greenlet)。

但是非常悲剧的,纯用户态方案(setjmp/longjmp)在多数系统上执行的效率很高,但是并不是为了协程而设计的。setjmp并没有拷贝整个栈(大多数的coroutine方案也不应该这么做),而是只保存了寄存器状态。这导致新的寄存器状态和老寄存器状态共享了同一个栈,从而在执行时互相破坏。而完整的coroutine方案应当在特定时刻新建一个栈。

而比较好的方案(makecontext/swapcontext)则需要进入内核(sigprocmask),这导致整个调用的性能非常低。

关于setjmp/longjmp,你可以参考CS360 Lecture notes — Setjmp,和setjmp 的正确使用 | 云风的 BLOG

协程与线程的关系

首先我们可以明确,协程不能调度其他进程中的上下文。而后,每个协程要获得CPU,都必须在线程中执行。因此,协程所能利用的CPU数量,和用于处理协程的线程数量直接相关。

作为推论,在单个线程中执行的协程,可以视为单线程应用。这些协程,在未执行到特定位置(基本就是阻塞操作)前,是不会被抢占,也不会和其他CPU上的上下文发生同步问题的。因此,一段协程代码,中间没有可能导致阻塞的调用,执行在单个线程中。那么这段内容可以被视为同步的。

我们经常可以看到某些协程应用,一启动就是数个进程。这并不是跨进程调度协程。一般来说,这是将一大群fd分给多个进程,每个进程自己再做fd-协程对应调度。

基于就绪通知的协程框架

  1. 首先需要包装read/write,在发生read的时候检查返回。如果是EAGAIN,那么将当前协程标记为阻塞在对应fd上,然后执行调度函数。
  2. 调度函数需要执行epoll(或者从上次的返回结果缓存中取数据,减少内核陷入次数),从中读取一个就绪的fd。如果没有,上下文应当被阻塞到至少有一个fd就绪。
  3. 查找这个fd对应的协程上下文对象,并调度过去。
  4. 当某个协程被调度到时,他多半应当在调度器返回的路上——也就是read/write读不到数据的时候。因此应当再重试读取,失败的话返回1。
  5. 如果读取到数据了,直接返回。

这样,异步的数据读写动作,在我们的想像中就可以变为同步的。而我们知道同步模型会极大降低我们的编程负担。

CPS模型

其实这个模型有个更流行的名字——回调模型。之所以扯上CPS这么高大上的玩意,主要是里面涉及不少有趣的话题。

首先是回调模型的大致过程。在IO调用的时候,同时传入一个函数,作为返回函数。当IO结束时,调用传入的函数来处理下面的流程。这个模型听起来挺简单的。

然后是CPS。用一句话来描述这个模型——他把一切操作都当作了IO,无论干什么,结果要通过回调函数来返回。从这个角度来说,IO回调模型只能被视作CPS的一个特例。

例如,我们需要计算1+2*3,在cps里面就需要这么写:

mul(lambda x: add(pprint.pprint, x, 1), 2, 3)

其中mul和add在python里面如下定义:

add = lambda f, *nums: f(sum(nums))
mul = lambda f, *nums: f(reduce(lambda x,y: x*y, nums))

而且由于python没有TCO,所以这样的写法会产生非常多的frame。

但是要正确理解这个模型,你需要仔细思考一下以下几个问题:

  • 函数的调用过程为什么必须是一个栈?
  • IO过程在什么时间发生?调用发生时,还是回调时?
  • 回调函数从哪里调用?如果当时利用工具去看上下文的话,调用栈是什么样子的?

函数组件和返回值

不知道你是否思考过为什么函数调用层级(上下文栈)会被表述为一个栈——是否有什么必要性,必须将函数调用的过程定义为一个栈呢?

原因就是返回值和同步顺序。对于大部分函数,我们需要得到函数计算的返回值。而要得到返回值,调用者就必须阻塞直到被调用者返回为止。因此调用者的执行状态就必须被保存,等到被调用者返回后继续——从这点来说,调用其实是最朴素的上下文切换手段。而对于少部分无需返回的函数,我们又往往需要他的顺序外部效应——例如干掉了某个进程,开了一个灯,或者仅仅是在环境变量里面添加了一项内容。而顺序外部效应同样需要等待被调用者返回以表明这个外部效应已经发生。

那么,如果我们不需要返回值也不需要顺序的外部效应呢?例如启动一个背景程序将数据发送到对端,无需保证发送成功的情况下。或者是开始一个数据抓取行为,无需保证抓取的成功。

通常这种需求我们就凑合着用一个同步调用混过去了——反正问题也不严重。但是对于阻塞相当严重的情况而言,很多人还是会考虑到将这个行为做成异步过程。目前最流行的异步调用分解工具就是mq——不仅异步,而且分布。当然,还有一个更简单的非分布方案——开一个coroutine。

而CPS则是另一个方向——函数的返回值可以不返回调用者,而是返回给第三者。

IO过程在什么时间发生

其实这个问题的核心在于——整个回调模型是基于多路复用的还是基于异步IO的?

原则上两者都可以。你可以监听fd就绪,也可以监听IO完成。当然,即使监听IO完成,也不代表使用了内核态异步接口。很可能只是用epoll封装的而已。

回调函数的上下文环境

这个问题则需要和上面提到的“用户态调度框架”结合起来说。IO回调注册的实质是将回调函数绑定到某个fd上——就如同将coroutine绑定上去那样。只是coroutine允许你顺序的执行,而callback则会切碎函数。当然,大部分实现中,使用callback也有好处——coroutine的最小切换开销也在50ns,而call本身则只有2ns。

状态机模型

状态机模型是一个更难于理解和编程的模型,其本质是每次重入。

想像你是一个周期失忆的病人(就像“一周的朋友”那样)。那么你如何才能完成一项需要跨越周期的工作呢?例如刺绣,种植作物,或者——交一个男朋友。

当然,类比到失忆病人的例子上必须有一点限制。正常的生活技能,还有一些常识性的东西必须不能在周期失忆范围内。例如重新学习认字什么的可没人受的了。

答案就是——做笔记。每次重复失忆后,你需要阅读自己的笔记,观察上次做到哪个步骤,下一个步骤是什么。这需要将一个工作分解为很多步骤,在每个步骤内“重入”直到步骤完成,转移到下一个状态。

同理,在状态机模型解法里,每次执行都需要推演合适的状态,直到工作完成。这个模型已经很少用到了,因为相比回调函数来说,状态机模型更难理解和使用,性能差异也不大。

最后顺带一提,交一个男友的方案和其他几个略有不同,主要靠颜好高冷反差萌,一般人就不要尝试挑战了。。。当然一般人也不会一周失忆一次,毕竟生活不是韩剧也不是日本动漫。。。

上下文切换测试总结报告

效率测试

测试环境

  • Intel(R) Pentium(R) CPU G2030 @ 3.00GHz
  • 8G内存
  • debian jessie
  • Linux 3.16-2-amd64
  • 2014年10月27日

附注一下,该CPU有2核心,无HT,1ns3个时钟周期。

测试方法

测试代码如下:

time -f "%e,%S,%c,%r,%s,%K,%P" ./perf_fork

数据的意义分别为: 总时间,内核CPU时间,context switch次数,读/写次数,内存耗用,CPU使用百分比。

数据处理方法如下:

import numpy as np
p = lambda s: [float(line.strip().split(',')[0]) for line in s.splitlines()]
q = lambda s: [float(line.strip().split(',')[1]) for line in s.splitlines()]
np.array(p(s)).mean()
np.array(p(s)).var()
np.array(q(s)).mean()
np.array(q(s)).var()

基础开销测试

函数调用开销

使用s_call来测试性能,循环1G次。

2.35,0.00,17,0,0,0,99%
2.34,0.00,13,0,0,0,99%
2.34,0.00,10,0,0,0,100%
2.35,0.00,10,0,0,0,99%
2.34,0.00,14,0,0,0,99%
2.34,0.00,6,0,0,0,99%

统计结果如下:

  • time mean = 2.34
  • time var = 0.000022

每次call的开销为2.34ns,约7个指令周期。当然,这些并没有考虑调用压栈和数据返回。

内核调用开销

使用s_syscall来测试性能,循环1G次。这里特意选用了一个不可能失败的内核函数,getpid,来衡量每次进入getpid的开销。

4.37,0.00,76,0,0,0,99%
4.34,0.00,43,0,0,0,99%
4.37,0.00,124,0,0,0,99%
4.37,0.00,63,0,0,0,99%
4.36,0.00,48,0,0,0,99%
4.36,0.00,47,0,0,0,99%

统计结果如下:

  • time mean = 4.36
  • time var = 0.00011

这里可以看到,纯粹的内核进入开销小到非常惊人,只有4.36ns,约合13个指令周期,而且这里还要进行数据的查询和返回。所以内核调用开销在下面的测试中全部忽略不计。

系统上下文测试

进程fork开销

使用s_fork程序(注释语句关闭模式),循环1M次,重复6次,原始数据如下:

49.04,26.83,29784,0,0,0,55%
51.53,26.38,32057,0,0,0,52%
49.88,26.02,30892,0,0,0,53%
51.39,27.13,37573,0,0,0,54%
52.89,28.12,37924,0,0,0,54%
51.19,27.02,35880,0,0,0,54%

统计结果如下:

  • time mean = 50.98
  • time var = 1.52
  • kernel mean = 26.92
  • kernel var = 0.43

从数据上,我们可以简单得到结论。在测试设备上,每次fork的开销为51us,内核开销为27us,精确级别在1-2us左右。粗略换算一下,一次fork大约消耗了150k个时钟周期。

注意,这个数据并不代表fork本身的速度。因为除去fork之外,我们还有子进程退出的开销,父进程wait的开销。甚至严格来说,还包括了至少一次的context switch(有趣的是,这个取决于fork后是优先执行子进程还是父进程)。

但是作为进程模式的服务程序,这些开销都是预料中必须付出的。不过我们并没有模拟signal对性能的影响(简单测试表明,性能也会显著的变差)。

另外cs次数比产生的进程数远小,可能被第二颗核心执行掉了部分。看来要做精确的测试需要使用单核处理器。

fork模式强制优先执行子进程

s_fork中,注意那句注释。当优先执行子进程时,会发生什么现象?

预期来说,应当不发生变化,或者轻微的变慢。因为我们预期系统优先执行子进程(以减少exec前的page cow)。如果发生变化,那么说明这个假定是不正确的。真实情况是优先执行父进程或者无保证。

如果发生变化,首先是一次context switch会变为两次。因为如果在产生了大量子进程后再依次cs,那么需要N+1次cs来结束所有子进程并返回父进程,平均每个子进程一次cs(N足够大的情况下基本近似,例如在标准配置下30000以上)。而如果每次产生子进程就切换,那么会变为每个子进程两次cs。

其次,先执行父进程导致在每次调度时的活跃进程数更高,因此调度器的每次执行开销更高。按照算法量级估计,大约是4倍以上。但是实际复杂度的估量比平均值更加麻烦——因为活跃数总是在不停的变化中。大约是Sum(logn)/n=log(n!)/n。因此,虽然在cs次数上减少,但是每次cs的开销会增加。

最后,先执行子进程会导致上下文描述符表项被频繁的重用,从而提高命中率。当然,在我们的测试程序中做不到这点,因为每次都是开满才开始回收的。因为直接回收会导致父进程等待子进程结束,从而导致缓慢。所以至少应当需要执行相当的数量才进行回收。

而我们摒弃了使用信号响应的方式进行回收,因为信号的速度比fork更慢,这会导致测试不准。

下面是实际原始数据:

45.19,22.42,399890,0,0,0,51%
47.66,22.46,414808,0,0,0,48%
45.51,23.12,376053,0,0,0,52%
46.35,22.10,401536,0,0,0,49%
48.28,22.82,415162,0,0,0,48%
47.44,22.34,413285,0,0,0,48%

统计结果如下:

  • time mean = 46.73
  • time var = 1.29
  • kernel mean = 22.54
  • kernel var = 0.11

解读上可以发现,每10次fork产生四次cs(这可能是因为第二颗核心执行了部分的子进程),但是每次fork的开销降低为47us,内核CPU降为23us(用户态时间几乎不发生变化),精确级别在1us左右。

这说明真实情况确实是先执行父进程或无保证。

线程建立销毁开销

使用t_thread程序,循环1M次,重复6次,原始数据如下:

9.57,8.22,21098,0,0,0,104%
9.77,8.40,29704,0,0,0,104%
9.36,8.17,10390,0,0,0,106%
9.56,8.50,14514,0,0,0,107%
9.35,8.34,7244,0,0,0,108%
9.57,8.43,26351,0,0,0,106%

统计结果如下:

  • time mean = 9.53
  • time var = 0.02
  • kernel mean = 8.34
  • kernel var = 0.013

解读数据可以看到,thread模式的开销为9530ns(已经降到纳秒级了),CPU将为8340ns,精确级别在20ns级别。粗略换算一下每次create的开销大约是30k个时钟周期。简单对比可以看出,thread模式比fork模式大约快了5倍。

纯线程切换开销

使用t_yield.c程序研究线程切换开销。具体过程单独整理了一个文件,下面只贴出结论:

t_yield.png

基本可以看到,随着上下文数的增加,每次调度开销是随之增加的。而且两者近似的呈一条直线(虽然看起来比较扭曲)。这证明调度复杂度为O(logm)的推论基本是正确的。

另外,在1-2线程时性能特别优秀。这可能是线程数小于核数,导致大部分情况下根本未执行调度。对此作出的一点推论是。很多时候,我们为了充分利用CPU会作出worker = N+1的设定。如果IO并不是特别密集,可能性能反而比worker = N更差。

sleep切换开销

使用t_sleep.c程序来测试usleep(0)的性能。100线程,1M次循环。下面是结论:

66.55,90.62,4160,0,0,0,149%
65.60,87.08,3238,0,0,0,145%
65.28,83.95,2570,0,0,0,139%
65.59,85.98,2366,0,0,0,143%
65.67,86.79,1715,0,0,0,143%
65.84,87.70,1896,0,0,0,145%

统计结果如下:

  • time mean = 65.75
  • time var = 0.1539

计算结果来说,1315ns。比同样的单纯调度,开销增加了916.8ns。但是在此期间请特别留意CPU利用率曲线。该曲线呈现出明显的先达峰后下降趋势。说明某些线程的sleep比另一些线程的优先得到调度,导致最后CPU利用率不足。从循环次数和下降趋势来说,很难说调度是“近似公平”的。

另外特别注意,我们针对1线程1M次循环得到的结论。

53.81,2.52,20,0,0,0,4%
53.88,2.47,22,0,0,0,4%
53.79,2.48,16,0,0,0,4%
55.09,2.35,49,0,0,0,4%
56.19,2.27,50,0,0,0,4%
55.71,2.43,62,0,0,0,4%

统计结果如下:

  • time mean = 54.74
  • time var = 0.945

这个结果表明,usleep后会导致很长(50us以上)的延迟,在这个时间段内不会有CPU消耗,哪怕usleep(0)。这是由于任务被标记为TASK_INTERRUPTIBLE,然后挂到timer队列上。timer队列调度是有频率限制的,低于这个时间片的sleep不会得到及时响应。这导致usleep测试CPU和调度性能实际上是个很没意义的行为。

lock切换开销

使用t_lock.c来研究pthread mutex的性能。

t_lock.png

可以看到,mutex几乎不随着并发数的上升而上升。难道是我们的推论有误?

我详细的看了下源码。在glibc中,使用的是futex而非mutex实现的锁。前者会把系统置于TASK_UNINTERRUPTIBLE而后者会置于TASK_INTERRUPTIBLE。在ps中一望便知。而TASK_INTERRUPTIBLE是未就绪状态,并不在调度范围内。因此,仅仅在某个上下文执行了unlock后,未进入lock时的短暂时间内,系统有两个可调度上下文。在进入lock后,系统又变为一个可调度上下文。因此,系统在大多数时候都在1-2个可调度上下文间浮动。

而且请注意,这里还是换出-换入两次(所有锁类代码都是这样)。

而read/write中,活跃上下文数是受客户影响的。当某个fd收到用户数据的时候,对应上下文就会从TASK_INTERRUPTIBLE转变为就绪,而且在下一个阻塞(或处理完成)前始终占据调度队列。

python性能测试

yield模式性能测试

python下的测试就不用time了,我们改用python的timeit,循环100M次。具体可以看py_yield.py。数据结果如下:

7.64262938499 9.2919304393e-06
5.41777145863 4.94284924931e-06

从结果来看,100M次循环的平均时间是5.4s,平均每次大约54ns。使用yield后变为76ns,增加了22ns。

greenlet模式性能测试

这次代码在py_greenlet.py,循环10M次。数据结果如下:

5.35270996888 7.44085846125e-05
5.31448976199 5.82336765673e-05

单次循环时间消耗为535ns。比最初的54ns,增加了481ns。基本来说,时间增长了10倍率。

这是预料中的,因为greenlet早就声明自己通过堆栈拷贝来实现上下文切换。这会消耗大量CPU时间。从原理上说,栈越深,消耗越大。但是测试结果表明两者几乎没有差异,栈深反而性能更加优异。

yield from性能测试

这次代码在py_yield_from.py,循环100M次。数据结果如下:

11.3753386545 2.05564687993e-05
8.83233247434 7.92599097725e-05
6.31597025133 0.00346735863271

单次循环时间消耗为113.7ns。比最初的63.2ns,增加了50.5ns。单纯的yield为88.3ns,增加了25.1ns。

yield from需要在python3下执行,从数据上看,python3下执行循环加的过程比python2下更缓慢,而且yield也同样比python2下的缓慢(这也是python3经常被诟病的一个问题,经常比python2慢)。

但是针对2/3速度对比问题,我特别声明一下。这个测试没有针对2/3速度对比做定制,也没有经过精细分析。所以不能保证其他人在其他环境下执行出相反的结果。总之,目前我可以做出的简单结论是。python3和python2速度相仿,python2略快。

而yield from比yield更慢,这完全可以理解。在python2中,yield from需要用for来表达,这样的结果一个是难看,一个也未必快过yield from。

下面我们想要知道一下,随着yield的深度增加,速度是否减慢。用同一个程序里的test_all代码进行了简单的测试后,结果如下:

py_yield_from.png

结论是,随着递归深度的增加,yield from的上下文切换速度是会减慢的。两者呈明显的线性关系。

golang性能测试

goroutine创建开销

下面是一组golang有关的测试,首先使用g_goroutine.go来测试goroutine创建和销毁开销,执行10M次:

5.70,0.11,598,0,0,0,99%
5.70,0.12,77,0,0,0,99%
5.66,0.14,334,0,0,0,99%
5.66,0.10,271,0,0,0,99%
5.57,0.16,47,0,0,0,99%
5.77,0.10,521,0,0,0,99%

统计结果如下:

  • time mean = 5.68
  • time var = 0.0036

大致结果为创建开销568ns,大约是线程创建开销的1/20。注意代码没有保证goroutine执行完毕,所以可能会有一定误差。

调度开销

我们使用g_sched.go来研究golang的调度。

g_sched.png

可以看到,在很大范围内,延迟虽然随着并发升高而升高,但是升高的幅度并不大。即使是16K这个级别的并发,也只有250ns左右的延迟而已。

chan开销

我们使用g_chan.go来研究chan上的调度。

g_chan.png

可以看到,chan的性能更加优秀,而且不随着并发的增长而增长,在所有的范围内基本都是60-70ns。这主要是因为chan并不需要“调度”,而只需要上下文切换。所以这个切换是非公平的。chan唤醒上下文的顺序并不一定按照在chan上阻塞的顺序。

lock开销

我们使用g_lock.go来研究chan上的调度。

g_lock.png

让我颇为困惑的是,lock的性能居然比chan更优秀。在初始阶段都是30ns多点,在256并发上下遇到了剧烈的波动,以上就减少到了20ns。原理上说,lock同样也是不做出顺序假定,无调度的。但是这并不能说明为什么chan比lock性能更差。也许是chan内部做了一些额外工作。而且这些工作应当和并发无关,也就是局部(local)工作。

C语言上下文调度

setjmp/longjmp测试

使用s_jmp程序来测试setjmp的性能。1G次循环。下面是结论:

5.77,0.00,29,0,0,0,99%
5.70,0.00,30,0,0,0,99%
5.71,0.00,22,0,0,0,99%
5.71,0.00,23,0,0,0,99%
5.70,0.00,30,0,0,0,100%
5.70,0.00,23,0,0,0,99%

统计结果如下:

  • time mean = 5.715
  • time var = 0.000625

单次调度开销只有5.7ns,在所有测试中性能最优。(glibc-2.19/sysdeps/x86_64/setjmp.S)

makecontext/swapcontext测试

使用s_context程序来测试ucontext的性能。100M次循环。下面是结论:

33.42,13.08,163,0,0,0,99%
33.43,13.40,147,0,0,0,99%
33.39,13.24,143,0,0,0,99%
33.41,13.25,156,0,0,0,99%
33.70,13.41,328,0,0,0,99%
33.42,13.18,290,0,0,0,99%

统计结果如下:

  • time mean = 33.46
  • time var = 0.0115

单次调度开销高达167.3ns,仅比系统的sched在高线程下略快。这事很奇怪,因为根据我看到的源码(glibc-2.19/sysdeps/unix/sysv/linux/x86_64/setcontext.S),getcontext/setcontext在glibc中是用汇编实现的。其中陷入内核只是为了设定signal mask。

手机上app的权限对比和分析

简述

今天看到这篇文章,勾起了我的好奇。我的手机里有多少app有安全隐患呢?当然,我知道很多有安全问题的app我不能删——例如企鹅家。但是如果某个app没有必然需要,或者有替代品。我不介意换一个用。所以我写了这篇blog,对比了各种同类或近似app的权限要求。

先说明一点,这篇文章所列出的app权限,是根据当前(2014-11-07)google play上的应用权限数据,截取我感兴趣的部分权限汇总的。既不是完全的敏感权限列表,也不可能不变化。如果有什么补充,欢迎你联系我。

同时你需要知道,app需要某个权限,并不一定表示要用来做坏事。很多时候是因为功能确实需要。因此我也在下面点评了部分我知道的功能需要对应权限。即便我们在app里面找不到权限对应功能,也不能绝对断言app正在作恶——只是相比起来我更信任不需要提供这个权限的app而已。这也是为什么我做的是分类对比——方便你来比较和替换。

IM类

telegram

  • read SMS
  • 照相
  • 录音
  • location
  • read/modify contacts
  • run at startup

talkback

  • change audio setting

我太感动了。

QQ

  • read SMS
  • read/modify contacts
  • 照相
  • 录音
  • location
  • read/write call log
  • read/write calendar
  • disable screen lock
  • NFC
  • bluetooth
  • run at startup
  • change audio setting

流氓权限大集合啊。你说要contacts我还能理解,要call log干嘛?还要write?而且功能里也找不到为什么需要NFC和蓝牙。

微信

  • read SMS
  • 照相
  • 录音
  • location
  • read/modify contacts
  • bluetooth
  • run at startup
  • change audio setting

基本同QQ,不过权限少了很多。

评论

虽然我们都知道talkback比企鹅家的对隐私更友好,可是有本事你别用企鹅家。。。

SNS

facebook

  • read sms
  • 照相
  • 录音
  • location
  • read/modify contacts
  • read/write calendar
  • run at startup
  • set wallpaper
  • change audio setting

不知道为啥需要change audio setting,而且write calendar也奇怪了些。其他权限基本还能找到对应功能。

twitter

  • receive sms
  • 照相
  • location
  • read contacts

评论

twitter权限明显比facebook少,不过fb功能也比tw多。

购物

Amazon

  • 照相
  • 录音
  • location

一号店

  • location
  • read/send SMS
  • read/write calendar
  • 设定闹钟
  • run at startup

不知道为啥需要设定闹钟,可能因为每日惠,所以要提醒?至于读取/发送sms也是很奇怪。location倒是很好理解——定位收货地址。可是在应用里又找不到这个功能。而且你说一款购物软件,启动时运行干嘛?24小时不间断购物?

大众点评

  • read sms
  • 照相
  • 录音
  • location

大众点评就是做location的,照相录音权限也很好理解。只有read sms有点奇怪。

去哪儿

  • read contacts
  • read/write calendar
  • location
  • 录音
  • 照相

权限让人直挠头,果然有高大上的读取通讯录。设定calendar是要做行程提醒么?虽然我在应用里面没找到对应功能。location很好理解,起飞/降落城市挺好用。但是照相和录音就不知道干嘛用的了。

华住酒店

  • location
  • send SMS
  • 照相
  • read contacts
  • disable screen lock
  • run at startup

location挺好理解,找酒店时很方便。但是send SMS干嘛用的?

还有照相和读取contacts。我觉得一款酒店软件要求这俩权限的唯一目的就是晒炮。

更不可理喻的是disable screen lock和run at startup。你没事关掉锁屏干嘛?盯着放广告么?24小时放广告?

评论

Amazon和大众点评的权限要求比较简单。一号店/去哪儿/华住的权限就比较流氓了。反正后面三个可以通过web使用,不如不装。

打车

快的

  • read sms
  • 录音
  • location
  • read contacts
  • change audio setting
  • run at startup

location很好理解,但是为什么又是read contacts?还有run at startup。我不能24小时都要打车吧。

uber

  • 照相
  • location
  • read contacts

read contacts无法理解

评论

打车软件普遍要求contacts,这点无法理解。但是又不能不用——快的和uber的服务目标不交叉,而且都要求了contacts。

另外,滴滴打车在google play里面找不到,所以不评论。

金融

wallet

  • 照相
  • location
  • read contacts
  • NFC
  • run at startup

支付宝

  • location
  • read contacts
  • bluetooth
  • run at startup

浦发银行

  • read/recieve sms
  • 照相
  • 录音
  • read call log
  • read contacts
  • NFC
  • change audio setting

为啥要NFC?我在里面看到了拍拍付,也许是为这个准备的。但是read sms和change audio setting也是个奇怪的东西。

而且又是read call log/read contacts。你们这帮应用啊。

CMB

  • read/recieve sms
  • 照相
  • 录音
  • location
  • read/modify contacts
  • read/write call log

除了NFC和audio setting外,和浦发差不多。还多了location——你没事想知道我的location干嘛?最近网点导航?

工行手机银行

  • read contacts
  • location
  • 照相
  • 录音
  • NFC
  • bluetooth
  • change audio setting

contacts就不说了。又是一个要求location的,到底准备干嘛呢?

没装过(没工行帐号),所以不知道功能上用不用NFC和bluetooth。

评论

金融类软件几乎无一例外都要求contacts,连google家都不例外,让我真是不知道说什么好。不过互联网应用要求contacts的理由更强一些——可以通过contacts关联的email或者mobile来找到收款人/汇款人。但是如果银行能这么做就是安全漏洞了。

总体来说,wallet和支付宝的权限要求还比较低。而银行类无一例外都要求照相和录音权限——你们要这个干嘛?

媒体类

bilibili

  • 照相

这个权限太让我感动了。

网易音乐

  • 录音
  • location
  • read call log
  • read contacts

要求contacts似乎是因为好友功能会直接用,call log也是同样原因。location是找附近听的音乐功能要求的。

天气类

weather channel

  • 读取location
  • 启动时运行

墨迹天气

  • read SMS
  • 照相
  • location
  • disable screen lock
  • 设定闹钟
  • run at startup

照相还可以理解,墨迹有现场照片分享功能。location和run at startup也很正常。

但是你说read sms和设定闹钟是干嘛用的?而且disable screen lock。我没事开个天气软件锁屏还被关了?

词典类

网易有道词典

  • location
  • read sms
  • 照相

作为一款词典,我可以理解为什么要照相。但是我是在无法理解读取短信(想帮我翻译短信?)和获得location(看看我在哪里好多国翻译)的用途?

欧路词典

  • 照相

我太感动了。

金山词霸

  • 照相
  • 录音
  • run at startup

除了开机执行,其他都还好。

translate

  • read sms
  • 照相
  • 录音

为什么要read sms?

评论

如果你的要求不是特别高,非要用网易有道不可,我建议换成欧路。词霸其实也很不错。

其他

dropbox

  • read contacts
  • run at startup

read contacts干嘛?

evernote

  • 照相
  • 录音
  • location
  • read contacts
  • read calendar
  • run at startup

评论

无可奉告,反正也没的换。

context切换测试——C语言协程有关部分请求review

setjmp/longjmp测试

使用s_jmp程序来测试setjmp的性能。1G次循环。下面是结论:

5.77,0.00,29,0,0,0,99%
5.70,0.00,30,0,0,0,99%
5.71,0.00,22,0,0,0,99%
5.71,0.00,23,0,0,0,99%
5.70,0.00,30,0,0,0,100%
5.70,0.00,23,0,0,0,99%

统计结果如下:

  • time mean = 5.715
  • time var = 0.000625

单次调度开销只有5.7ns,在所有测试中性能最优。(glibc-2.19/sysdeps/x86_64/setjmp.S)

getcontext/setcontext测试

使用s_context程序来测试setcontext的性能。100M次循环。下面是结论:

12.96,5.88,79,0,0,0,99%
13.13,5.94,105,0,0,0,99%
12.95,6.18,57,0,0,0,99%
13.13,5.90,64,0,0,0,99%
12.95,5.88,82,0,0,0,99%
12.96,5.80,51,0,0,0,99%

统计结果如下:

  • time mean = 13.01
  • time var = 0.0068

单次调度开销高达130ns,仅比系统的sched在高线程下略快。这事很奇怪,因为根据我看到的源码(glibc-2.19/sysdeps/unix/sysv/linux/x86_64/setcontext.S),getcontext/setcontext在glibc中是用汇编实现的。其中陷入内核只是为了设定signal mask。