Category Archives: 计算理论

解谜计算机科学

要掌握一个学科的精髓,不能从细枝末节开始。人脑的能力很大程度上受限于信念。一个人不相信自己的时候,他就做不到本来可能的事。信心是很重要的,信心却容易被挫败。如果只见树木不见森林,人会失去信心,以为要到猴年马月才能掌握一个学科。

所以我们不从“树木”开始,而是引导读者一起来探索这背后的“森林”,把计算机科学最根本的概念用浅显的例子解释,让读者领会到它们的本质。把这些概念稍作发展,你就得到逐渐完整的把握。你一开头就掌握着整个学科,而且一直掌握着它,只不过增添更多细节而已。这就像画画,先勾勒出轮廓,一遍遍的增加细节,日臻完善,却不失去对大局的把握。

一般计算机专业的学生学了很多课程,可是直到毕业都没能回答一个基础问题:什么是计算?这一章会引导你去发现这个问题的答案。不要小看这基础的问题,它经常是解决现实问题的重要线索。世界上有太多不理解它的人,他们走了很多的弯路,掉进很多的坑,制造出过度复杂或者有漏洞的理论和技术。

接下来,我们就来理解几个关键的概念,由此接触到计算的本质。

手指算术

每个人都做过计算,只是大部分人都没有理解自己在做什么。回想一下幼儿园(大概四岁)的时候,妈妈问你:“帮我算一下,4+3 等于几?” 你掰了一会手指,回答:7。当你掰手指的时候,你自己就是一台简单的计算机。

不要小看了这手指算术,它蕴含着深刻的原理。计算机科学植根于这类非常简单的过程,而不是复杂的高等数学。

现在我们来回忆一下这个过程。这里应该有一段动画,但现阶段还没有。请你对每一步发挥一下想象力,增加点“画面感”。

  1. 当妈妈问你“4+3 等于几”的时候,她是一个程序员,你是一台计算机。计算机得到程序员的输入:4,+,3。
  2. 听到妈妈的问题之后,你拿出两只手,左手伸出四个指头,右手伸出三个指头。
  3. 接着你开始自己的计算过程。一根根地数那些竖起来的手指,每数一根你就把它弯下去,表示它已经被数过了。你念道:“1,2,3,4,5,6,7。”
  4. 现在已经没有手指伸着,所以你把最后数到的那个数作为答案:7!整个计算过程就结束了。

符号和模型

(这个概念太过深入,好像不适合出现在第一章,考虑去掉)

这里的幼儿园手指算术包含着深刻的哲学问题,现在我们来初步体会一下这个问题。

当妈妈说“帮我算 4+3”的时候,4,+,3,三个字符传到你耳朵里,它们都是符号(symbol)。符号是“表面”的东西:光是盯着“4”和“3”这两个阿拉伯数字的曲线,一个像旗子,一个像耳朵,你是不能做什么的。你需要先用脑子把它们转换成对应的“模型”(model)。这就是为什么你伸出两只手,一只手表示 4,另一只表示 3。

这两只手的手势是“可操作”的。比如,你把左手再多弯曲一个手指,它就变成“3”。你再伸开一根手指,它就变成“5”。所以手指是一个相当好的机械模型,它是可以动,可操作的。把符号“4”和“3”转换成手指模型之后,你就可以开始计算了。

你怎么知道“4”和“3”对应什么样的手指模型呢?因为妈妈以前教过你。十根手指,对应着 1 到 10 十个数。这就是为什么人都用十进制数做算术。

我们现在没必要深究这个问题。我只是提示你,分清“符号”和“模型”是重要的。

计算图

在计算机领域,我们经常用一些抽象的图示来表达计算的过程,这样就能直观地看到信息的流动和转换。这种图示看起来是一些形状用箭头连接起来。我在这里把它叫做“计算图”。

对于以上的手指算术 4 + 3,我们可以用下图来表示它:

图中的箭头表示信息的流动方向。说到“流动”,你可以想象一下水的流动。首先我们看到数字 4 和 3 流进了一个圆圈,圆圈里有一个“+”号。这个圆圈就是你,一个会做手指加法的小孩。妈妈给你两个数 4 和 3,你现在把它们加起来,得到 7 作为结果。

注意圆圈的输入和输出方向是由箭头决定的,我们可以根据需要调整那些箭头的位置,只要箭头的连接关系和方向不变就行。它们不一定都是从左到右,也可能从右到左或者从上到下,但“出入关系”都一样:4 和 3 进去,结果 7 出来。比如它还可以是这样:

我们用带加号的圆圈表示一个“加法器”。顾名思义,加法器可以帮我们完成加法。在上个例子里,你就是一个加法器。我们也可以用其他装置作为加法器,比如一堆石头,一个算盘,某种电子线路…… 只要它能做加法就行。

具体要怎么做加法,就像你具体如何掰手指,很多时候我们是不关心的,我们只需要知道这个东西能做加法就行。圆圈把具体的加法操作给“抽象化”了,这个蓝色的圆圈可以代表很多种东西。抽象(abstraction)是计算机科学至关重要的思维方法,它帮助我们进行高层面的思考,而不为细节所累。

表达式

计算机科学当然不止 4 + 3 这么简单,但它的基本元素确实是如此简单。我们可以创造出很复杂的系统,然而归根结底,它们只是在按某种顺序计算像 4 + 3 这样的东西。

4 + 3 是一个很简单的表达式(expression)。你也许没听说过“表达式”这个词,但我们先不去定义它。我们先来看一个稍微复杂一些的表达式:

2 * (4 + 3)

这个表达式比 4 + 3 多了一个运算,我们把它叫做“复合表达式”。这个表达式也可以用计算图来表示:

你知道它为什么是这个样子吗?它表示的意思是,先计算 4 + 3,然后把结果(7)传送到一个“乘法器”,跟 2 相乘,得到最后的结果。那正好就是 2 * (4 + 3) 这个表达式的含义,它的结果应该是 14。

为什么要先计算 4 + 3 呢?因为当我们看到乘法器 2 * ... 的时候,其中一个输入(2)是已知的,而另外一个输入必须通过加法器的输出得到。加法器的结果是由 4 和 3 相加得到的,所以我们必须先计算 4 + 3,然后才能与 2 相乘。

小学的时候,你也许学过:“括号内的内容要先计算”。其实括号只是“符号层”的东西,它并不存在于计算图里面。我这里讲的“计算图”,其实才是本质的东西。数学的括号一类的东西,都只是表象,它们是符号或者叫“语法”。从某种意义上讲,计算图才是表达式的本质或者“模型”,而“2 * (4 + 3)”这串符号,只是对计算图的一种表示或者“编码”(coding)。

这里我们再次体会到了“符号”和“模型”的差别。符号是对模型的“表示”或者“编码”。我们必须从符号得到模型,才能进行操作。这种从符号到模型的转换过程,在计算机科学里叫做“语法分析”(parsing)。我们会在后面的章节理解这个过程。

我们现在来给表达式做一个初步的定义。这并不是完整的定义,但你应该试着理解这种定义的方式。稍后我们会逐渐补充这个定义,逐渐完善。

定义(表达式):表达式可以是如下几种东西。

  1. 数字是一个表达式。比如 1,2,4,15,……
  2. 表达式 + 表达式。两个表达式相加,也是表达式。
  3. 表达式 – 表达式。两个表达式相减,也是表达式。
  4. 表达式 * 表达式。两个表达式相乘,也是表达式。
  5. 表达式 / 表达式。两个表达式相除,也是表达式。

注意,由于我们之前讲过的符号和模型的差别,为了完全忠于我们的本质认识,这里的“表达式 + 表达式”虽然看起来是一串符号,它必须被想象成它所对应的模型。当你看到“表达式”的时候,你的脑子里应该浮现出它对应的计算图,而不是一串符号。这个计算图的画面大概是这个样子,其中左边的大方框里可以是任意两个表达式。

是不是感觉这个定义有点奇怪?因为在“表达式”的定义里,我们用到了“表达式”自己。这种定义叫做“递归定义”。所谓递归(recursion),就是在一个东西的定义里引用这个东西自己。看上去很奇怪,好像绕回去了一样。递归是一个重要的概念,我们会在将来深入理解它。

现在我们可以来验证一下,根据我们的定义,2 * (4 + 3) 确实是一个表达式:

  • 首先根据第一种形式,我们知道 4 是表达式,因为它是一个数字。3 也是表达式,因为它是一个数字。
  • 所以 4 + 3 是表达式,因为 + 的左右都是表达式,它满足表达式定义的第二种形式。
  • 所以 2 * (4 + 3) 是表达式,因为 * 的左右都是表达式,它满足表达式定义的第四种形式。

并行计算

考虑这样一个表达式:

(4 + 3) * (1 + 2)

它对应一个什么样的计算图呢?大概是这样:

如果妈妈只有你一个小孩,你应该如何用手指算出它的结果呢?你大概有两种办法。

第一种办法:先算出 4+3,结果是 7。然后算出 1+2,结果是 3。然后算 7*3,结果是 21。

第二种办法:先算出 1+2,结果是 3。然后算出 4+3,结果是 7。然后算 7*3,结果是 21。

注意到没有,你要么先算 4+3,要么先算 1+2,你不能同时算 4+3 和 1+2。为什么呢?因为你只有两只手,所以算 4+3 的时候你就没法算 1+2,反之也是这样。总之,你妈妈只有你一个加法器,所以一次只能做一个加法。

现在假设你还有一个妹妹,她跟你差不多年纪,她也会手指算术。妈妈现在就多了一些办法来计算这个表达式。她可以这样做:让你算 4+3,不等你算完,马上让妹妹算 1+2。等到你们的结果(7 和 3)都出来之后,让你或者妹妹算 7*3。

发现没有,在某一段时间之内,你和妹妹同时在做加法计算。这种时间上重叠的计算,叫做并行计算(parallel computing)。

你和妹妹同时计算,得到结果的速度可能会比你一个人算更快。如果你妈妈还有其它几个孩子,计算复杂的式子就可能快很多,这就是并行计算潜在的好处。所谓“潜在”的意思是,这种好处不一定会实现。比如,如果你的妹妹做手指算数的速度比你慢很多,你做完了 4+3,只好等着她慢慢的算 1+2。这也许比你自己依次算 4+3 和 1+2 还要慢。

即使妹妹做算术跟你一样快,这里还有个问题。你和妹妹算出结果 7 和 3 之后,得把结果传递给下一个计算 7*3 的那个人(也许是你,也许是你妹妹)。这种“通信”会带来时间的延迟,叫做“通信开销”。如果你们其中一个说话慢,这比起一个人来做计算可能还要慢。

如何根据计算单元能力的不同和通信开销的差异,来最大化计算的效率,降低需要的时间,就成为了并行计算领域研究的内容。并行计算虽然看起来是一个“博大精深”的领域,可是你如果理解了我这里说的那点东西,就很容易理解其余的内容。

变量和赋值

如果你有一个复杂的表达式,比如

(5 - 3) * (4 + (2 * 3 - 5) * 6)

由于它有比较多的嵌套,人的眼睛是难以看清楚的,它要表达的意义也会难懂。这时候,你希望可以用一些“名字”来代表中间结果,这样表达式就更容易理解。

打个比方,这就像你有一个亲戚,他是你妈妈的表姐的女儿的丈夫。你不想每次都称他“我妈妈的表姐的女儿的丈夫”,所以你就用他的名字“叮当”来指代他,一下子就简单了。

我们来看一个例子。之前的复合表达式

2 * (4 + 3)

其实可以被转换为等价的,含有变量的代码:

{
    a = 4 + 3       // 变量 a 得到 4+3 的值
    2 * a           // 代码块的值
}

其中 a 是一个名字。a = 4 + 3 是一个“赋值语句”,它的意思是:用 a 来代表 4 + 3 的值。这种名字,计算机术语叫做变量(variable)。

这段代码的意思可以简单地描述为:计算 4 + 3,把它的结果表示为 a,然后计算 2 * a 作为最后的结果。

有些东西可能扰乱了你的视线。两根斜杠 // 后面一直到行末的文字叫做“注释”,是给人看的说明文字。它们对代码的逻辑不产生作用,执行的时候可以忽略。许多语言都有类似这种注释,它们可以帮助阅读的人,但是会被机器忽略。

这段代码执行过程会是这样:先计算 4 + 3 得到 7,用 a 记住这个中间结果 7。接着计算 2 * a ,也就是计算 2 * 7,所以最后结果是 14。很显然,这跟 2 * (4 + 3) 的结果是一样的。

a 叫做一个变量,它是一个符号,可以用来代表任意的值。除了 a,你还有许多的选择,比如 b, c, d, x, y, foo, bar, u21… 只要它不会被误解成其它东西就行。

如果你觉得这里面的“神奇”成分太多,那我们现在来做更深一层的理解……

再看一遍上面的代码。这整片代码叫做一个“代码块”(block),或者叫一个“序列”(sequence)。这个代码块包括两条语句,分别是 a = 4 + 3 和 2 * a。代码块里的语句会从上到下依次执行。所以我们先执行 a = 4 + 3,然后执行 2 * a

最后一条语句 2 * a 比较特别,它是这个代码块的“值”,也就是最后结果。之前的语句都是在为生成这个最后的值做准备。换句话说,这整个代码块的值就是 2 * a 的值。不光这个例子是这样,这是一个通用的原理:代码块的最后一条语句,总是这个代码块的值。

我们在代码块的前后加上花括号 {...} 进行标注,这样里面的语句就不会跟外面的代码混在一起。这两个花括号叫做“边界符”。我们今后会经常遇到代码块,它存在于几乎所有的程序语言里,只是语法稍有不同。比如有些语言可能用括号 (...) 或者 BEGIN...END来表示边界,而不是用花括号。

这片代码已经有点像常用的编程语言了,但我们暂时不把它具体化到某一种语言。我不想固化你的思维方式。在稍后的章节,我们会把这种抽象的表达法对应到几种常见的语言,这样一来你就能理解几乎所有的程序语言。

另外还有一点需要注意,同一个变量可以被多次赋值。它的值会随着赋值语句而改变。举个例子:

{
    a = 4 + 3
    b = a
    a = 2 * 5
    c = a
}

这段代码执行之后,b 的值是 7,而 c 的值是 10。你知道为什么吗?因为 a = 4 + 3 之后,a 的值是 7。b = a 使得 b 得到值 7。然后 a = 2 * 5 把 a 的值改变了,它现在是 10。所以 c = a 使得 c 得到 10。

对同一个变量多次赋值虽然是可以的,但通常来说这不是一种好的写法,它可能引起程序的混淆,应该尽量避免。只有当变量表示的“意义”相同的时候,你才应该对它重复赋值。

编译

一旦引入了变量,我们就可以不用复合表达式。因为你可以把任意复杂的复合表达式拆开成“单操作算术表达式”(像 4 + 3 这样的),使用一些变量记住中间结果,一步一步算下去,得到最后的结果。

举一个复杂点的例子,也就是这一节最开头的那个表达式:

(5 - 3) * (4 + (2 * 3 - 5) * 6)

它可以被转化为一串语句:

{
    a = 2 * 3
    b = a - 5
    c = b * 6
    d = 4 + c
    e = 5 - 3
    e * d
}

最后的表达式 e * d,算出来就是原来的表达式的值。你观察一下,是不是每个操作都非常简单,不包含嵌套的复合表达式?你可以自己验算一下,它确实算出跟原表达式一样的结果。

在这里,我们自己动手做了“编译器”(compiler)的工作。通常来说,编译器是一种程序,它的任务是把一片代码“翻译”成另外一种等价形式。这里我们没有写编译器,可是我们自己做了编译器的工作。我们手动地把一个嵌套的复合表达式,编译成了一系列的简单算术语句。

这些语句的结果与原来的表达式完全一致。这种保留原来语义的翻译过程,叫做编译(compile)。

我们为什么需要编译呢?原因有好几种。我不想在这里做完整的解释,但从这个例子我们可以看到,编译之后我们就不再需要复杂的嵌套表达式了。我们只需要设计很简单的,只会做单操作算术的机器,就可以算出复杂的嵌套的表达式。实际上最后这段代码已经非常接近现代处理器(CPU)的汇编代码(assembly)。我们只需要多加一些转换,它就可以变成机器指令。

我们暂时不写编译器,因为你还缺少一些必要的知识。这当然也不是编译技术的所有内容,它还包含另外一些东西。但从这一开头,你就已经初步理解了编译器是什么,你只需要在将来加深这种理解。

函数

到目前为止,我们做的计算都是在已知的数字之上,而在现实的计算中我们往往有一些未知数。比如我们想要表达一个“风扇控制器”,有了它之后,风扇的转速总是当前气温的两倍。这个“当前气温”就是一个未知数。

我们的“风扇控制器”必须要有一个“输入”(input),用于得到当前的温度 t,它是一个温度传感器的读数。它还要有一个输出,就是温度的两倍。

那么我们可以用这样的方式来表达我们的风扇控制器:

t -> t*2

不要把这想成任何一种程序语言,这只是我们自己的表达法。箭头 -> 的左边表示输入,右边表示输出,够简单吧。

你可以把 t 想象成从温度传感器出来的一根电线,它连接到风扇控制器上,风扇控制器会把它的输入(t)乘以 2。这个画面像这个样子:

我们谈论风扇控制器的时候,其实不关心它的输入是哪里来的,输出到哪里去。如果我们把温度传感器和风扇从画面里拿掉,就变成这个样子:

这幅图才是你需要认真理解的函数的计算图。你发现了吗,这幅图画正好对应了之前的风扇控制器的符号表示:t -> t*2。看到符号就想象出画面,你就得到了符号背后的模型。

像 t -> t*2 这样具有未知数作为输入的构造,我们把它叫做函数(function)。其中 t 这个符号,叫做这个函数的参数。

参数,变量和电线

你可能发现了,函数的参数和我们之前了解的“变量”是很类似的,它们都是一个符号。之前我们用了 a, b, c, d, e 现在我们有一个 t,这些名字我们都是随便起的,只要它们不要重复就好。如果名字重复的话,可能会带来混淆和干扰。

其实参数和变量这两种概念不只是相似,它们的本质就是一样的。如果你深刻理解它们的相同本质,你的脑子就可以少记忆很多东西,而且它可能帮助你对代码做出一些有趣而有益的转化。在上一节你已经看到,我用“电线”作为比方来帮助你理解参数。你也可以用同样的方法来理解变量。

比如我们之前的变量 a

{
    a = 4 + 3
    2 * a
}

它可以被想象成什么样的画面呢?

我故意把箭头方向画成从右往左,这样它就更像上面的代码。从这个图画里,你也许可以看到变量 a 和风扇控制器图里的参数 t,其实没有任何本质差别。它们都表示一根电线,那根电线进入乘法器,将会被乘以 2,然后输出。如果你把这些都看成是电路,那么变量 a 和参数 t 都代表一根电线而已。

然后你还发现一个现象,那就是你可以把 a 这个名字换成任何其它名字(比如 b),而这幅图不会产生实质的改变。

这说明什么问题呢?这说明以下的代码(把 a 换成了 b)跟之前的是等价的:

{
    b = 4 + 3
    2 * b
}

根据几乎一样的电线命名变化,你也可以对之前的函数得到一样的结论:t -> t*2 和 u -> u*2,和 x -> x*2 都是一回事。

名字是很重要的东西,但它们具体叫什么,对于机器并没有实质的意义,只要它们不要相互混淆就可以。但名字对于人是很重要的,因为人脑没有机器那么精确。不好的变量和参数名会导致代码难以理解,引起程序员的混乱和错误。所以通常说来,你需要给变量和参数起好的名字。

什么样的名字好呢?我会在后面集中讲解。

有名字的函数

既然变量可以代表“值”,那么一个自然的想法,就是让变量代表函数。所以就像我们可以写

a = 4 + 3

我们似乎也应该可以写

f = t -> t*2

对的,你可以这么做。f = t->t*2 还有一个更加传统的写法,就像数学里的函数写法:

f(t) = t*2

请仔细观察 t 的位置变化。我们在函数名字的右边写一对括号,在里面放上参数的名字。

注意,你不可以只写

f = t*2

你必须明确的指出函数的参数是什么,否则你就不会明白函数定义里的 t 是什么东西。明确指出 t 是一个“输入”,你才会知道它是函数的输入,是一个未知数,而不是在函数外面定义的其它变量

这个看似简单的道理,很多数学家都不明白,所以他们经常这样写书:

有一个函数 y = x*2

这是错误的,因为他没有明确指出“x 是函数 y 的参数”。如果这句话之前他们又定义过 x,你就会疑惑这是不是之前那个 x。很多人就是因为这些糊里糊涂的写法而看不懂数学书。这不怪他们,只怪数学家自己对于语言不严谨。

函数调用

有了函数,我们可以给它起名字,可是我们怎么使用它的值呢?

由于函数里面有未知数(参数),所以你必须告诉它这些未知数,它里面的代码才会执行,给你结果。比如之前的风扇控制器函数

f(t) = t*2

它需要一个温度作为输入,才会给你一个输出。于是你就这样给它一个输入:

f(2)

你把输入写在函数名字后面的括号里。那么你就会得到输出:4。也就是说 f(2) 的值是 4。

如果你没有调用一个函数,函数体是不会被执行的。因为它不知道未知数是什么,所以什么事也做不了。那么我们定义函数的时候,比如

f(t) = t*2

当看到这个定义的时候,机器应该做什么呢?它只是记录下:有这么一个函数,它的参数是 t,它需要计算 t*2,它的名字叫 f。但是机器不会立即计算 t*2,因为它不知道 t 是多少。

分支

直到现在,我们的代码都是从头到尾,闷头闷脑地执行,不问任何问题。我们缺少一种“问问题”的方法。比如,如果我想表达这样一个“食物选择器”:如果气温低于 22 度,就返回 “hotpot” 表示今天吃火锅,否则返回 “ice cream” 表示今天吃冰激凌。

我们可以把它图示如下:

中间这种判断结构叫做“分支”(branching),它一般用菱形表示。为什么叫分支呢?你想象一下,代码就像一条小溪,平时它沿着一条路线流淌。当它遇到一个棱角分明的大石头,就分成两个支流,分开流淌。

我们的判断条件 t < 22 就像一块大石头,我们的“代码流”碰到它就会分开成两支,分别做不同的事情。跟溪流不同的是,这种分支不是随机的,而是根据条件来决定,而且分支之后只有一支继续执行,而另外一边不会被执行。

我们现在看到的都是图形化表示的模型,为了书写方便,现在我们要从符号的层面来表示这个模型。我们需要一种符号表示法来表达分支,我们把它叫做 if(如果)。我们的饮料选择器代码可以这样写:

t -> if (t < 22) 
     {
       "hotpot"
     }
     else 
     {
       "ice cream"
     }

它是一个函数,输入是一个温度。if 后面的括号里放我们的判断条件。后面接着条件成立时执行的代码块,然后是一个 else,然后是条件不成立时执行的代码。它说:如果温度低于 22 度,我们就吃火锅,否则就吃冰激凌。

其中的 else 是一个特殊的符号,它表示“否则”。看起来不知道为什么 else 要在那里?对的,它只是一个装饰品。我们已经有足够的表达力来分辨两个分支,不过有了 else 似乎更加好看一些。很多语言里面都有 else 这个标记词在那里,所以我也把它放在那里。

这只是一个最简单的例子,其实那两个代码块里面不止可以写一条语句。你可以有任意多的语句,就像这样:

t ->
if (t < 22)
{
    a = 4 + 3
    b = a * 2
    "hotpot"
}
else
{
    x = "ice cream"
    x
}

这段代码和之前是等价的,你知道为什么吗?

字符串

上面一节出现了一种我们之前没见过的东西,我为了简洁而没有介绍它。这两个分支的结果,也就是加上引号的 “hotpot” 和 “ice cream”,它们并不是数字,也不是其它语言构造,而是一种跟数字处于几乎同等地位的“数据类型”,叫做字符串(string)。字符串是我们在计算机里面表示人类语言的基本数据类型。

关于字符串,在这里我不想讲述更加细节的内容,我把对它的各种操作留到以后再讲,因为虽然字符串对于应用程序很重要,它却并不是计算机科学最关键最本质的内容。

很多计算机书籍一开头就讲很多对字符串的操作,导致初学者费很大功夫去做很多打印字符串的练习,结果几个星期之后还没学到“函数”之类最根本的概念。这是非常可惜的。

布尔值

我们之前的 if 语句的条件 t < 22 其实也是一个表达式,它叫做“布尔表达式”。你可以把小于号 < 看成是跟加法一类的“操作符”。它的输入是两个数值,输出是一个“布尔值”。什么是布尔值呢?布尔值只有两个:true 和 false,也就是“真”和“假”。

举个例子,如果 t 的值是 15,那么 t < 22 是成立的,那么它的值就是 true。如果 t 的值是 23,那么 t < 22 就不成立,那么它的值就是 false。是不是很好理解呢?

我们为什么需要“布尔值”这种东西呢?因为它的存在可以简化我们的思维。对于布尔值也有一些操作,这个我也不在这一章赘述,放到以后细讲。

计算的要素

好了,现在你已经掌握了计算机科学的几乎所有基本要素。每一个编程语言都包括这些构造:

  1. 基础的数值。比如整数,字符串,布尔值等。
  2. 表达式。包括基本的算术表达式,嵌套的表达式。
  3. 变量和赋值语句。
  4. 分支语句。
  5. 函数和函数调用。

你也许可以感觉到,我是把这些构造按照“从小到大”的顺序排列的。这也许可以帮助你的理解。

现在你可以回想一下你对它们的印象。每当学习一种新的语言或者系统,你只需要在里面找到对应的构造,而不需要从头学习。这就是掌握所有程序语言的秘诀。这就像学开车一样,一旦你掌握了油门,刹车,换挡器,方向盘,速度表的功能和用法,你就学会了开所有的汽车,不管它是什么型号的汽车。

我们在这一章不仅理解了这些要素,而且为它们定义了一种我们自己的“语言”。显然这个语言只能在我们的头脑里运行,因为我们没有实现这个语言的系统。在后面的章节,我会逐渐的把我们这种语言映射到现有的多种语言里面,然后你就能掌握这些语言了。

但是请不要以为掌握了语言就学会了编程或者学会了计算机科学。掌握语言就像学会了各种汽车部件的工作原理。几分钟之内,初学者就能让车子移动,转弯,停止。可是完了之后你还需要学习交通规则,你需要许许多多的实战练习和经验,掌握各种复杂情况下的策略,才能成为一个合格的驾驶员。如果你想成为赛车手,那就还需要很多倍的努力。

但是请不要被我这些话吓到了,你没有那么多的竞争者。现在的情况是,世界上就没有很多合格的计算机科学驾驶员,更不要说把车开得流畅的赛车手。绝大部分的“程序员”连最基本的引擎,油门,刹车,方向盘的工作原理都不明白,思维方式就不对,所以根本没法独自上路,一上路就出车祸。很多人把过错归结在自己的车身上,以为换一辆车马上就能成为好的驾驶员。这是一种世界范围的计算机教育的失败。

在后面的章节,我会引导你成为一个合格的驾驶员,随便拿一辆车就能开好。

什么是计算

现在你掌握了计算所需要的基本元素,可是什么是计算呢?我好像仍然没有告诉你。这是一个很哲学的问题,不同的人可能会告诉你不同的结果。我试图从最广义的角度来告诉你这个问题的答案。

当你小时候用手指算 4+3,那是计算。如果后来你学会了打算盘,你用算盘算 4+3,那也是计算。后来你从我这里学到了表达式,变量,函数,调用,分支语句…… 在每一新的构造加入的过程中,你都在了解不同的计算。

所以从最广义来讲,计算就是“机械化的信息处理”。所谓机械化,你可以用手指算,可以用算盘,可以用计算器,或者计算机。这些机器里面可以有代码,也可以没有代码,全是电子线路,甚至可以是生物活动或者化学反应。不同的机器也可以有不同的计算功能,不同的速度和性能……

有这么多种计算的事实不免让人困惑,总害怕少了点什么,其实你可以安心。如果你掌握了上一节的“计算要素”,那么你就掌握了几乎所有类型的计算系统所需要的东西。你在后面所需要做的只是加深这种理解,并且把它“对应”到现实世界遇到的各种计算机器里面。

为什么你可以相信计算机科学的精华就只有这些呢?因为计算就是处理信息,信息有它诞生的位置(输入设备,固定数值),它传输的方式(赋值,函数调用,返回值),它被查看的地方(分支)。你想不出对于信息还有什么其它的操作,所以你就很安心的相信了,这就是计算机科学这种“棋类游戏”的全部规则。

from:http://www.yinwang.org/blog-cn/2018/04/13/computer-science

每个程序员都应该了解的内存知识-0

这个系列文章源于 What Every Programmer Should Know About Memory ,粗读下来觉得很不错,最好能留存下来。同时发现这个系列的文章已经有一部分被人翻译了。故在此转发留存一份,毕竟存在自己收留的才是最可靠的,经常发现很多不错的文章链接失效的情况。

本文转载自,翻译自。本人进行了轻微的修改,感觉更符合原义。

1 简介

早期计算机比现在更为简单。系统的各种组件例如CPU,内存,大容量存储器和网口,由于被共同开发因而有非常均衡的表现。例如,内存和网口并不比CPU在提供数据的时候更(特别的)快。

曾今计算机稳定的基本结构悄然改变,硬件开发人员开始致力于优化单个子系统。于是电脑一些组件的性能大大的落后因而成为了瓶颈。由于开销的原因,大容量存储器和内存子系统相对于其他组件来说改善得更为缓慢。

大容量存储的性能问题往往靠软件来改善: 操作系统将常用(且最有可能被用)的数据放在主存中,因为后者的速度要快上几个数量级。或者将缓存加入存储设备中,这样就可以在不修改操作系统的前提下提升性能。(然而,为了在使用缓存时保证数据的完整性,仍然要作出一些修改)。这些内容不在本文的谈论范围之内,就不作赘述了。

而解决内存的瓶颈更为困难,它与大容量存储不同,几乎每种方案都需要对硬件作出修改。目前,这些变更主要有以下这些方式:

  • RAM的硬件设计(速度与并发度)
  • 内存控制器的设计
  • CPU缓存
  • 设备的直接内存访问(DMA)

本文主要关心的是CPU缓存和内存控制器的设计。在讨论这些主题的过程中,我们还会研究DMA。不过,我们首先会从当今商用硬件的设计谈起。这有助于我们理解目前在使用内存子系统时可能遇到的问题和限制。我们还会详细介绍RAM的分类,说明为什么会存在这么多不同类型的内存。

本文不会包括所有内容,也不会包括最终性质的内容。我们的讨论范围仅止于商用硬件,而且只限于其中的一小部分。另外,本文中的许多论题,我们只会点到为止,以达到本文目标为标准。对于这些论题,大家可以阅读其它文档,获得更详细的说明。

当本文提到操作系统特定的细节和解决方案时,针对的都是Linux。无论何时都不会包含别的操作系统的任何信息,作者无意讨论其他操作系统的情况。如果读者认为他/她不得不使用别的操作系统,那么必须去要求供应商提供其操作系统类似于本文的文档。

在开始之前最后的一点说明,本文包含大量出现的术语“通常”和别的类似的限定词。这里讨论的技术在现实中存在于很多不同的实现,所以本文只阐述使用得最广泛最主流的版本。在阐述中很少有地方能用到绝对的限定词。

1.1 文档结构

这个文档主要视为软件开发者而写的。本文不会涉及太多硬件细节,所以喜欢硬件的读者也许不会觉得有用。但是在我们讨论一些有用的细节之前,我们先要描述足够多的背景。

在这个基础上,本文的第二部分将描述RAM(随机寄存器)。懂得这个部分的内容很好,但是此部分的内容并不是懂得其后内容必须部分。我们会在之后引用不少之前的部分,所以心急的读者可以跳过任何章节来读他们认为有用的部分。

第三部分会谈到不少关于CPU缓存行为模式的内容。我们会列出一些图标,这样你们不至于觉得太枯燥。第三部分对于理解整个文章非常重要。第四部分将简短的描述虚拟内存是怎么被实现的。这也是你们需要理解全文其他部分的背景知识之一。

第五部分会提到许多关于Non Uniform Memory Access (NUMA)系统。

第六部分是本文的中心部分。在这个部分里面,我们将回顾其他许多部分中的信息,并且我们将给阅读本文的程序员许多在各种情况下的编程建议。如果你真的很心急,那么你可以直接阅读第六部分,并且我们建议你在必要的时候回到之前的章节回顾一下必要的背景知识。

本文的第七部分将介绍一些能够帮助程序员更好的完成任务的工具。即便在彻底理解了某一项技术的情况下,距离彻底理解在非测试环境下的程序还是很遥远的。我们需要借助一些工具。

第八部分,我们将展望一些在未来我们可能认为好用的科技。

1.2 反馈问题

作者会不定期更新本文档。这些更新既包括伴随技术进步而来的更新也包含更改错误。非常欢迎有志于反馈问题的读者发送电子邮件。

1.3 致谢

我首先需要感谢Johnray Fuller尤其是Jonathan Corbet,感谢他们将作者的英语转化成为更为规范的形式。Markus Armbruster提供大量本文中对于问题和缩写有价值的建议。

1.4 关于本文

本文题目对David Goldberg的经典文献《What Every Computer Scientist Should Know About Floating-Point Arithmetic》[goldberg]表示致敬。Goldberg的论文虽然不普及,但是对于任何有志于严格编程的人都会是一个先决条件

2 商用硬件现状

鉴于目前专业硬件正在逐渐淡出,理解商用硬件的现状变得十分重要。现如今,人们更多的采用水平扩展,也就是说,用大量小型、互联的商用计算机代替巨大、超快(但超贵)的系统。原因在于,快速而廉价的网络硬件已经崛起。那些大型的专用系统仍然有一席之地,但已被商用硬件后来居上。2007年,Red Hat认为,未来构成数据中心的“积木”将会是拥有最多4个插槽的计算机,每个插槽插入一个四核CPU,这些CPU都是超线程的。(超线程使单个处理器核心能同时处理两个以上的任务,只需加入一点点额外硬件)。也就是说,这些数据中心中的标准系统拥有最多64个虚拟处理器(至今来看2018那年,96核/128核的服务已经是很常见的服务器配置了)。当然可以支持更大的系统,但人们认为4插槽、4核CPU是最佳配置,绝大多数的优化都针对这样的配置。

在不同商用计算机之间,也存在着巨大的差异。不过,我们关注在主要的差异上,可以涵盖到超过90%以上的硬件。需要注意的是,这些技术上的细节往往日新月异,变化极快,因此大家在阅读的时候也需要注意本文的写作时间。

这么多年来,个人计算机和小型服务器被标准化到了一个芯片组上,它由两部分组成: 北桥和南桥,见图2.1。

图2.1 北桥和南桥组成的结构

CPU通过一条通用总线(前端总线,FSB)连接到北桥。北桥主要包括内存控制器和其它一些组件,内存控制器决定了RAM芯片的类型。不同的类型,包括DRAM、Rambus和SDRAM等等,要求不同的内存控制器。

为了连通其它系统设备,北桥需要与南桥通信。南桥又叫I/O桥,通过多条不同总线与设备们通信。目前,比较重要的总线有PCI、PCI Express、SATA和USB总线,除此以外,南桥还支持PATA、IEEE 1394、串行口和并行口等。比较老的系统上有连接北桥的AGP槽。那是由于南北桥间缺乏高速连接而采取的措施。现在的PCI-E都是直接连到南桥的。

这种结构有一些需要注意的地方:

  • 从某个CPU到另一个CPU的数据需要走它与北桥通信的同一条总线。
  • 与RAM的通信需要经过北桥
  • RAM只有一个端口。(本文不会介绍多端口RAM,因为商用硬件不采用这种内存,至少程序员无法访问到。这种内存一般在路由器等专用硬件中采用。)
  • CPU与南桥设备间的通信需要经过北桥

在上面这种设计中,瓶颈马上出现了。第一个瓶颈与设备对RAM的访问有关。早期,所有设备之间的通信都需要经过CPU,结果严重影响了整个系统的性能。为了解决这个问题,有些设备加入了直接内存访问(DMA)的能力。DMA允许设备在北桥的帮助下,无需CPU的干涉,直接读写RAM。到了今天,所有高性能的设备都可以使用DMA。虽然DMA大大降低了CPU的负担,却占用了北桥的带宽,与CPU形成了争用。

第二个瓶颈来自北桥与RAM间的总线。总线的具体情况与内存的类型有关。在早期的系统上,只有一条总线,因此不能实现并行访问。近期的RAM需要两条独立总线(或者说通道,DDR2就是这么叫的,见图2.8),可以实现带宽加倍。北桥将内存访问交错地分配到两个通道上。更新的内存技术(如FB-DRAM)甚至加入了更多的通道。

由于带宽有限,我们需要以一种使延迟最小化的方式来对内存访问进行调度。我们将会看到,处理器的速度比内存要快得多,需要等待内存。如果有多个超线程核心或CPU同时访问内存,等待时间则会更长。对于DMA也是同样。

除了并发以外,访问模式也会极大地影响内存子系统、特别是多通道内存子系统的性能。关于访问模式,可参见2.2节。

在一些比较昂贵的系统上,北桥自己不含内存控制器,而是连接到外部的多个内存控制器上(在下例中,共有4个)。

图2.2 拥有外部控制器的北桥

这种架构的好处在于,多条内存总线的存在,使得总带宽也随之增加了。而且也可以支持更多的内存。通过同时访问不同内存区,还可以降低延时。对于像图2.2中这种多处理器直连北桥的设计来说,尤其有效。而这种架构的局限在于北桥的内部带宽,非常巨大(来自Intel)。(出于完整性的考虑,还需要补充一下,这样的内存控制器布局还可以用于其它用途,比如说「内存RAID」,它可以与热插拔技术一起使用。)

使用外部内存控制器并不是唯一的办法,另一个最近比较流行的方法是将控制器集成到CPU内部,将内存直连到每个CPU。这种架构的走红归功于基于AMD Opteron处理器的SMP系统。图2.3展示了这种架构。Intel则会从Nehalem处理器开始支持通用系统接口(CSI),基本上也是类似的思路——集成内存控制器,为每个处理器提供本地内存。

图2.3 集成的内存控制器

通过采用这样的架构,系统里有几个处理器,就可以有几个内存库(memory bank)。比如,在4 CPU的计算机上,不需要一个拥有巨大带宽的复杂北桥,就可以实现4倍的内存带宽。另外,将内存控制器集成到CPU内部还有其它一些优点,这里就不赘述了。

同样也有缺点。首先,系统仍然要让所有内存能被所有处理器所访问,导致内存不再是统一的资源(NUMA即得名于此)。处理器能以正常的速度访问本地内存(连接到该处理器的内存)。但它访问其它处理器的内存时,却需要使用处理器之间的互联通道。比如说,CPU 1 如果要访问CPU 2 的内存,则需要使用它们之间的互联通道。如果它需要访问CPU 4 的内存,那么需要跨越两条互联通道。

使用互联通道是有代价的。在讨论访问远端内存的代价时,我们用「NUMA因子」这个词。在图2.3中,每个CPU有两个层级: 相邻的CPU,以及两个互联通道外的CPU。在更加复杂的系统中,层级也更多。甚至有些机器有不止一种连接,比如说IBM的x445和SGI的Altix系列。CPU被归入节点,节点内的内存访问时间是一致的,或者只有很小的NUMA因子。而在节点之间的连接代价很大,而且有巨大的NUMA因子。

目前,已经有商用的NUMA计算机,而且它们在未来应该会扮演更加重要的角色。人们预计,从2008年底开始,每台SMP机器都会使用NUMA。每个在NUMA上运行的程序都应该认识到NUMA的代价。在第5节中,我们将讨论更多的架构,以及Linux内核为这些程序提供的一些技术。

除了本节中所介绍的技术之外,还有其它一些影响RAM性能的因素。它们无法被软件所左右,所以没有放在这里。如果大家有兴趣,可以在第2.1节中看一下。介绍这些技术,仅仅是因为它们能让我们绘制的RAM技术全图更为完整,或者是可能在大家购买计算机时能够提供一些帮助。

以下的两节主要介绍一些入门级的硬件知识,同时讨论内存控制器与DRAM芯片间的访问协议。这些知识解释了内存访问的原理,程序员可能会得到一些启发。不过,这部分并不是必读的,心急的读者可以直接跳到第2.2.5节。

2.1 RAM类型

这些年来,出现了许多不同类型的RAM,各有差异,有些甚至有非常巨大的不同。那些很古老的类型已经乏人问津,我们就不仔细研究了。我们主要专注于几类现代RAM,剖开它们的表面,研究一下内核和应用开发人员们可以看到的一些细节。

第一个有趣的细节是,为什么在同一台机器中有不同的RAM?或者说得更详细一点,为什么既有静态RAM(SRAM {SRAM还可以表示「同步内存」。}),又有动态RAM(DRAM)。功能相同,前者更快。那么,为什么不全部使用SRAM?答案是,代价。无论在生产还是在使用上,SRAM都比DRAM要贵得多。生产和使用,这两个代价因子都很重要,后者则是越来越重要。为了理解这一点,我们分别看一下SRAM和DRAM一个位的存储的实现过程。

在本节的余下部分,我们将讨论RAM实现的底层细节。我们将尽量控制细节的层面,比如,在「逻辑的层面」讨论信号,而不是硬件设计师那种层面,因为那毫无必要。

2.1.1 静态RAM

图2.4 6-T静态RAM

图2.4展示了6晶体管SRAM的一个单元。核心是4个晶体管M 1 – M 4 ,它们组成两个交叉耦合的反相器。它们有两个稳定的状态,分别代表0和1。只要保持V dd 有电,状态就是稳定的。

当访问单元的状态时,需要拉升WL的电平。使得

和 上可以读取状态。如果需要覆盖单元状态,先将 和 设置为期望的值,然后升起WL电平。由于外部的驱动强于内部的4个晶体管(M 1 – M 4

),所以旧状态会被覆盖。

更多详情,可以参考[sramwiki]。为了下文的讨论,需要注意以下问题:

  • 一个单元需要6个晶体管。也有采用4个晶体管的SRAM,但有缺陷。
  • 维持状态需要恒定的电源。
  • 升起WL后立即可以读取状态。信号与其它晶体管控制的信号一样,是直角的(快速在两个状态间变化)。
  • 状态稳定,不需要刷新循环。

SRAM也有其它形式,不那么费电,但比较慢。由于我们需要的是快速RAM,因此不在关注范围内。这些较慢的SRAM的主要优点在于接口简单,比动态RAM更容易使用。

2.1.2 动态RAM

动态RAM比静态RAM要简单得多。图2.5展示了一种普通DRAM的结构。它只含有一个晶体管和一个电容器。显然,这种复杂性上的巨大差异意味着功能上的迥异。

图2.5 1-T动态RAM

动态RAM的状态是保持在电容器C中。晶体管M用来控制访问。如果要读取状态,拉升访问线AL,这时,可能会有电流流到数据线DL上,也可能没有,取决于电容器是否有电。如果要写入状态,先设置DL,然后升起AL一段时间,直到电容器充电或放电完毕。

动态RAM的设计有几个复杂的地方。由于读取状态时需要对电容器放电,所以这一过程不能无限重复,不得不在某个点上对它重新充电。

更糟糕的是,为了容纳大量单元(现在一般在单个芯片上容纳10的9次方以上的RAM单元),电容器的容量必须很小(0.000000000000001法拉以下)。这样,完整充电后大约持有几万个电子。即使电容器的电阻很大(若干兆欧姆),仍然只需很短的时间就会耗光电荷,称为「泄漏」。

这种泄露就是现在的大部分DRAM芯片每隔64ms就必须进行一次刷新的原因。在刷新期间,对于该芯片的访问是不可能的,这甚至会造成半数任务的延宕。(相关内容请察看【highperfdram】一章)

这个问题的另一个后果就是无法直接读取芯片单元中的信息,而必须通过信号放大器将0和1两种信号间的电势差增大。

最后一个问题在于电容器的冲放电是需要时间的,这就导致了信号放大器读取的信号并不是典型的矩形信号。所以当放大器输出信号的时候就需要一个小小的延宕,相关公式如下

这就意味着需要一些时间(时间长短取决于电容C和电阻R)来对电容进行冲放电。另一个负面作用是,信号放大器的输出电流不能立即就作为信号载体使用。图2.6显示了冲放电的曲线,x轴表示的是单位时间下的R*C。

与静态RAM可以即刻读取数据不同的是,当要读取动态RAM的时候,必须花一点时间来等待电容的冲放电完全。这一点点的时间最终限制了DRAM的速度。

当然了,这种读取方式也是有好处的。最大的好处在于缩小了规模。一个动态RAM的尺寸是小于静态RAM的。这种规模的减小不单单建立在动态RAM的简单结构之上,也是由于减少了静态RAM的各个单元独立的供电部分。以上也同时导致了动态RAM模具的简单化。

综上所述,由于不可思议的成本差异,除了一些特殊的硬件(包括路由器什么的)之外,我们的硬件大多是使用DRAM的。这一点深深的影响了咱们这些程序员,后文将会对此进行讨论。在此之前,我们还是先了解下DRAM的更多细节。

2.1.3 DRAM 访问

一个程序选择了一个内存位置使用到了一个虚拟地址。处理器转换这个到物理地址最后将内存控制选择RAM芯片匹配了那个地址。在RAM芯片去选择单个内存单元,部分的物理地址以许多地址行的形式被传递。

它单独地去处理来自于内存控制器的内存位置将完全不切实际:4G的RAM将需要 $ 2^32 $ 地址行。地址传递DRAM芯片的这种方式首先必须被路由器解析。一个路由器的N多地址行将有$ 2^N $输出行。这些输出行能被使用到选择内存单元。使用这个直接方法对于小容量芯片不再是个大问题。

from:https://www.tuicool.com/articles/IfueY3A

视频编码与封装综述

随着多媒体技术和网络通信技术的快速发展,视频多媒体应用已经覆盖了大众生活的方方面面。尤其是近年来高清和超高清视频应用越来越广泛,相比于标清视频,高清视频分辨率更高、画面更清晰,其数据量也更大。如果未经压缩,这些视频将很难应用于实际的存储和传输。这里我们就要提到视频应用中的一项关键技术——视频压缩编码技术

 

视频压缩编码技术可以有效地去除视频数据中冗余信息,实现视频数据在互联网中快速传输和离线存储

视频技术起源于第二次工业革命,随着视频技术的发展,一系列的视频编码标准被研发被使用。

压缩标准的变迁
目前已有的视频压缩标准有很多种,包括国际标准化组织(International Organization for Standardization, ISO)/国际电工技术委员会(International Electrotechnical Commission, IEC)制定的MPEG-1、MPEG-2、MPEG-4标准,国际电信联盟电信标准化部门(International Telecommunication Union-Telecom, ITU-T)制定的H.261、H.263。 

2003年3月,ITU-T和ISO/IEC 正式公布了H.264/MPEG-4 AVC视频压缩标准。H.264作为目前应用最为广泛的视频编码标准,在提高编码效率和灵活性方面取得了巨大成功,使得数字视频有效地应用在各种各样的网络类型和工程领域。为了在关键技术上不受国外牵制,同时也不用交大量的专利费用,中国也制定了AVS系列标准,可以提供与H.264/AVC相当的编码效率。

 

随着用户体验的升级,更高码率的视频也在被提供,比如超高清(3840 x 2160)。相对于标清视频,其分辨率更高,数据量也更多。在存储空间和网络带宽有限的情况下,现有的视频压缩技术已经不能满足现实的应用需求。为了解决高清及超高清视频急剧增长的数据率给网络传输和数据存储带来的冲击ITU-T和ISO/IEC联合制定了具有更高的压缩效率的新一代视频压缩标准HEVC(High Efficiency Video Coding)

HEVC简单介绍
HEVC:新一代视频压缩标准,以传统的混合视频编码为框架,并采用了更多的技术创新,包括灵活的块划分方式、更精细的帧内预测、新加入的Merge模式、Tile划分、自适应样点补偿等。 

这些技术一方面使得HEVC编码性能比H.264/AVC提高了一倍,另一方面也将编码复杂度大大增加,不利于HEVC的应用和推广

 

在这里着重说一下块划分方式——对编码性能提升最大。块划分包括编码单元(CU)、预测单元(PU)和变换单元(TU)。但是,递归的对每个编码单元进行率失真优化过程(RDO)来选择最优的模块划分的复杂度很高,其需要巨大的计算复杂度。因此降低HEVC编码复杂度的是视频行业人员所希望看到的。

640
图1 视频编码框图
新一代编码器对比
641
常见的封装格式有以下几种:· AVI(Audio Video Interleave):只能封装一条视频轨和音频轨,不能封装文字,没有任何控制功能,因而也就无法实现流媒体,其文件扩展名是.avi。

· WMV(Windows Media Video):具有数字版权保护功能,其文件扩展名是.wmv/.asf。

· MPEG(Moving Picture Experts Group):可以支持多个视频、音轨、字幕等,控制功能丰富,其文件扩展名是.mp4。

· Matroxska:提供非常好的交互功能,比MPEG更强大,其文件扩展名是.mkv。

· QuickTime File Farmat:由Apple开发,可存储内容丰富,支持视频、音频、图片、文字等,其文件扩展名是.mov。

· FLV(Flash Video):由Adobe Flash延伸而来的一种视频技术,主要用于网站。

· TS流(Transport Stream):传输流,将具有共同时间基准或独立时间基准的一个或多个PES组合(复合)而成的单一数据流(用于数据传输)。目前TS流广泛应用于广播电视中,如机顶盒等。

总结
本文简单介绍了视频的编码与封装,其是视频通信中重要的一步,如果这一步出了问题,很容易导致视频无法被读取或无法播放的状态。下一节,我们将来说一下视频通信中的音视频处理技术。from:https://mp.weixin.qq.com/s/9hClcofo8HEI8QqDpef12Q

一分钟理解TCP重传

为什么需要重传

任何信息在介质中传输可能丢失,这是由于传输介质的物理特性决定的,所以网络不可能被设计为“可靠的”(不是由于考虑“性能”原因而是压根做不到)。既然物理层无法提供可靠数据传输那么只能由协议提供可靠传输了,其中最有名的协议就是TCP了。

TCP是基于IP的网络协议,它提供可靠、有序的数据传输。在数据传输之前客户端和服务器端通过三次握手建立连接,建立连接的就是双方交换Seq(数据包序号)、MSS(每个TCP数据包大小) 、Win(滑动窗口,一次可以确认多少个TCP数据包),连接建立完成后每个TCP数据包都要被ACK(确认)。简单来说TCP通过确认/重传机制实现了“数据包可靠传输”。

重传原理

TCP数据包头部包含了两个字段——Seq表示数据包序号,ACK表示确认序号。下面演示了三次握手过程中Seq和ACK的变化过程。

640

客户端随机取一个值x作为Seq发送到服务器端;服务器端回复一个TCP数据包,头部包含Seq(随机值y),ACK=x+1。注意这里有一个常见的误区,ack确认的是当前数据包的“下一个”数据包,ack其实可以作为“期望得到的下一个seq”。客户端收到服务器端回复之后单独回复一个ack=y+1,就完成TCP的握手了。

后续数据包传递都会延续seq和ack的值,如果发送端某个数据包丢失了那么接收端不会发送ack(其实是duplicate ack),发送端在等待一段时间后发现没有ack,于是主动重发数据包。发送端的等待的时间叫RTO(Retransmission TimeOut)。

RTO的选择很重要,如果太大那么网络带宽利用率会特别低,发送端要过很久才知道要重传而此时要重传的数据是在太多严重浪费带宽资源。如果太小在高延时的网络高带宽(恩,你访问国外网站就属于这种网络)中也会浪费带宽资源。于是就有了Fast Retransmit机制,简单来说当发送端发现来自接收端的多个重复ACK(duplicate ack)的时候就不再等待RTO而是直接选择重发。

总结一下:经典TCP重发是发送端主动重发的,当数据包经历了一段时间后还没有被接收端确认此时发送端主动重发数据包。Fast Retransmit是由接收端主动要求重发的,当接收端收到了“不想要”的数据包时会重复ACK“上一个”数据包从而触发发送端的重发。这两种重发策略一般是同时使用,它们是互补的。

举个例子:发送端有D1(1-10)、D2(11-20)、D3(21-30)、D4(31-40)四个数据包要发送,每个数据包10bytes用括号内的数字表示。

  • 乱序的情况:接收端收到D1,发送ack=11(D2的序号)。如果在发送过程中D4在D1之后达由于D4携带的seq=31所以接收端会丢弃这个数据包然后再次发送ack=11。此时发送端会收到两个ack(duplicate ack)如果开启了Fast Retransmit特性那么发送端立即从D2开始重新发送。
  • 丢包的情况:接收端收到D1,发送ack=11(D2的序号)。如果在发送过程中D2丢失那么后续到达的包是D3,由于D3携带的seq=21所以接收端会丢弃这个数据包然后再次发送ack=11。此时发送端也会出现duplicate ack从而触发重传。

如果接收端的ACK数据包丢失了或者网络时延太高那么也会触发重传。因为发送端对每个数据包都设置了一个RTO,如果到时间没有收到ACK它会“主动”重发数据包。

Q&A

Q:多线程对一个Socket写入是否会触发TCP重发?程序上是否要考虑“乱序”?

A:首先要搞清楚一点,我们往Socket写入的数据是“应用层数据包”而不是TCP数据包。TCP/IP协议栈会把应用层数据包划分出多个TCP数据包发送出去,每次write都会生成N个连续的TCP数据包。所以即便我们多线程往Socket写入也不会出现TCP数据包的乱序(应用层数据包可能是乱序的)。

Q:重传和拥塞控制有什么关系?

A:TCP拥塞控制是指尽可能的利用带宽,它围绕4个核心概念展开:慢启动、拥塞避免和快速重传、快速恢复。其中快速重传、快速恢复属于TCP重传机制,慢启动是指对滑动窗口的控制,拥塞避免好重传机制有一定关系,如果存在大量重传那么网络上可能出现了拥塞(拥塞避免的关键是识别拥塞)。

Q:怎么看“替代TCP”的说法?

A:TCP最遭人诟病的就是它的重传机制不可控。如果网络延时比较高或者质量比较差有一定丢包(特别是移动网络),TCP的重传机制触发“不及时”这就导致应用体验很差。比如一个1000帧的视频丢了第100帧那么后续的900帧都要重传(即便已经收到了)。当然这只是一个例子,视频还是可以做一定“弥补”的),如果是手机游戏(比如王者荣耀、荒野行动)情况就没有这么乐观了。为了尽可能的让“重传”可控于是诞生了各种“替代TCP”的自制协议(大部分是基于UDP),比如Google的QUIC、kcp。我个人对这方面研究不多,总体而言它们牺牲了TCP的一些“通用特性”来换取一定的“灵活性”,所以并不是惊天地泣鬼神的“替代TCP”。

Q:怎么看TCP单边加速

A:TCP单边加速是指针对通讯的某一端做性能加速,市面上有很多这种产品。但是个人觉得这些都是骗人的,并没有一种算法适合所有网络情况。要根据不同的网络情况配置不同的拥塞控制算法。比如“国际链路”属于高延时高带宽,配置了Google的BBR算法“梯子”的速度至少能提高70-80%(你懂得)。

from:https://mp.weixin.qq.com/s?__biz=MzIxMjAzMDA1MQ==&mid=2648945945&idx=1&sn=f92e903929975e05978ba57be64ba2bc&chksm=8f5b5215b82cdb03c3f6f57ff63ee3f24bc1029dd147b7524d44baa36a10be65c24f6067adec#rd

IPC(Inter-process communication)进程间通讯

进程间通讯方式

Method Short Description Provided by (operating systems or other environments)
File A record stored on disk, or a record synthesized on demand by a file server, which can be accessed by multiple processes. Most operating systems
Signal; also Asynchronous System Trap A system message sent from one process to another, not usually used to transfer data but instead used to remotely command the partnered process. Most operating systems
Socket A data stream sent over a network interface, either to a different process on the same computer or to another computer on the network. Typically byte-oriented, sockets rarely preserve message boundaries. Data written through a socket requires formatting to preserve message boundaries. Most operating systems
Message queue A data stream similar to a socket, but which usually preserves message boundaries. Typically implemented by the operating system, they allow multiple processes to read and write to the message queue without being directly connected to each other. Most operating systems
Pipe A unidirectional data channel. Data written to the write end of the pipe is buffered by the operating system until it is read from the read end of the pipe. Two-way data streams between processes can be achieved by creating two pipes utilizing standard input and output. All POSIX systems, Windows
Named pipe A pipe implemented through a file on the file system instead of standard input and output. Multiple processes can read and write to the file as a buffer for IPC data. All POSIX systems, Windows, AmigaOS 2.0+
Semaphore A simple structure that synchronizes multiple processes acting on shared resources. All POSIX systems, Windows, AmigaOS
Shared memory Multiple processes are given access to the same block of memory which creates a shared buffer for the processes to communicate with each other. All POSIX systems, Windows
Message passing Allows multiple programs to communicate using message queues and/or non-OS managed channels, commonly used in concurrency models. Used in RPC, RMI, and MPI paradigms, Java RMI, CORBA, DDS, MSMQ, MailSlots, QNX, others
Memory-mapped file A file mapped to RAM and can be modified by changing memory addresses directly instead of outputting to a stream. This shares the same benefits as a standard file. All POSIX systems, Windows

The following are messaging and information systems that utilize IPC mechanisms, but don’t implement IPC themselves:

Interprocess communication for Windows in C#

refer:Inter-process communication