Category Archives: 计算理论

每个程序员都应该了解的内存知识-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

 

简述百年计算机科学

计算机科学和数学的论文读起来向来很具有挑战性,但读完后收获也不小。我也并不总能够完全理解论文中的每一个批注,有时都无法完全明白作者的结论,但阅读它们仍然大大地开阔了我的眼界。

我是比较晚才开始意识到阅读学术论文的重要性的。当还是学生的时候,我记得我只读过两篇论文,其中一篇下面我会提到。作为程序员,我并没有很强的计算机理论背景。学术论文对我来说非常生涩和遥远。因而,我花了很长时间才意识到没有阅读这些论文对我的损失有多大。

我有些同事知道了我最近对学术论文有所研究后,都在问我建议他们从哪里开始。看了Michaels FeathersFogus做的一张类似的清单后,我也编辑了一份自认为代表了过去100年计算机科学发展历程的清单。在编辑的时候,我采用了如下的选择标准:

  • 这篇论文必须改变了世界
  • 这篇论文必须颠覆了我当时的既有观点
  • 每十年只能有一篇入选

这样的选择标准一定是非常苛刻也非常主观的。如果你认为我漏掉了什么,也许你也可以编辑一份你的论文清单。

论排中律在数学上,特别是函数理论中的重要性(1923)

直觉主义的建立早于“计算理论”,但前者对后者的建立至关重要。Luitzen Egbertus Jan Brouwer的早期构想其实是对证明法的一个批判,但是Arend Heyting在后来的工作中把直觉主义结合应用到了数理逻辑中。

我选择Brouwer的论文是因为它抛弃排中律强调价值的建设。Brouwer并不认为一个命题如果不为假,则必为真。他认为,命题必须要被严谨地正面证明为真才对。

作为一名程序员,计算一个值和仅仅表示这个值的存在两者之间之间的区别是非常紧密相关的。更重要的是,起源于Brouwer想法的构造数学在随后的类型论发展中起了至关重要的作用。

论可计算数及其在可判定性问题上的应用(1936)

Alan Turing之所以在编程社区之外被众所周知,是因为他在第二次世界大战中破解了密码系统,和他所遭到的迫害而且最后自杀身亡。这篇论文诞生于战争之前,当时他还是个年轻的博士生。

我发现自己很难用直觉来理解图灵所描述的一个现象——不可计算数。我对于认为计算本身有硬性限制,这种说法既让人费解,又充满魅力。

在著名的判定性问题上,尽管图灵机和Alonzo Church的λ演算都被证明了是不朽的模拟计算方法,Turing的文章还是因为勉强打败了Church提出的解决方案被出版。

通信的数学理论(1948)

我清楚得记得还在念大学的时候读到这篇论文时的震撼。我之前认为信息就跟幽默感和美感一样,是无形的。这篇论文让信息突然变成了准确而可量化的了。

Claude E. Shannon是信息论的鼻祖,他让现代信息和通讯技术成为了可能。

非合作博弈(1950)

这篇并不是跟计算相关的,严格意义上它甚至都不能算作一篇论文。John Nash的博士学位论文整整26页却只有2个引用,其中一个还是引用他自己以前的一篇论文。在这篇文章中,Nash阐述了一个基于非合作博弈的数学理论。这个理论在经济学和冷战策略上有着深远的影响,并且最终带给了Nash诺贝尔经济学奖。

就算你仅仅想看看Nash因为无法用当时的打字机打出来而手写的那些数学符号,这篇论文已经很值得一读了。

递归函数下的符号表达式及计算机器(第一部分)(1960)

给出John McCarthy)这篇Lisp的开山之作不足为奇。这篇文章把编程原理讲解地细致到了原子级别。

Carl Sagan说过要想完完全全从零开始做一个苹果派,你先得创造一个宇宙。McCarthy在这篇文章告诉我们,要想完完全全从零开始做计算,你只需要先创造S表达式。

分布式系统中的时间,时钟和事件顺序(1978)

Leslie Lamport在这篇文章里研究了同步和因果关系的极限,可以说能让人想起爱因斯坦的相对论。虽然他的文章在互联网出现之前就有了(论文参考了ARPA net),但是这篇论文开始谈及到与现代分布式系统密切相关的协调问题。

Lamport在2013年获得了图灵奖。有个笑话是:每个人都知道他早就该得图灵奖了,但大家用了很长时间才达成了“同步”一致。

概率加密(1983)

现代加密方法往往依赖于陷门函数 —— 它们的计算量不大,但几乎无法被逆推。这使得人们可以花费很小的代价加密数据,并且可以很有信心的说这是不可逆转的过程,而且在不知道关键信息的情况下解密数据是不可能的。RSA非对称密码体系)就是一个著名的例子。

但这类方法有个漏洞,即它们仍然允许密码破译者获得加密数据的部分信息。在这篇文章中, Shafi GoldwasserSilvio Micali提出且证明了一种弥补这个漏洞的方法——用随机的方式使加密过程不确定。

编写自成长的语言(1998)

编写代码是非常有意思的,开发一门语言同样如此。在这篇论文中,Guy Steele一开始让单词只有一种意思,然后再让单词同时具有多种意思。他提出了一个很好的观点,成长是一门语言的关键,其能力应该能随着时间的推移而改变,在人们编写代码的时候就能够诞生新的特性。

这个论点最先是在一次演讲中被人们所知道的。

实用的拜占庭容错和实时恢复(2002)

互联网是个很可怕的地方。网络和服务不仅可能完全无法使用,有时也会出现各种奇怪或恶意的行为,甚至互相损害。

做一个可容错的分布式系统常常会被称为“拜占庭将军难题”——意思是假想好几只军队需要协同合作才能成功攻城,但领导他们的将军们却并不完全可靠。

在这篇文章里,Miguel CastroBarbara Liskov描述了一个很有效率的算法,来保证即使三分之一的节点以任何恶意的形式失效,系统仍然是健康的。

对今天的分布式系统而言,这类算法非常有用。比如比特币系统,用了这种算法它只要没失去一半以上的计算能力,都可保证可用。

命题类型(2014)

Philip Wadler的任何一篇论文都可以上榜。这篇论文在我写作的时候仍然是草稿,却可谓是新的经典之作,论文中Walder的引用范围从电影独立日乐团双杰,他揭露了Curry-Howard同构性这种精妙对称性的本质。

同构性记录了逻辑命题和函数式程序种类之间非同寻常的关系。更重要的是,论文的开篇引用了Brouwer在1923年的论文中提出的直觉主义,作为函数对应于传统的直觉主义的构造性证明,这篇论文验证了直觉主义的重要性。

本文在我心中占有特殊的地位,因为在Wadlerd发布最新起草的文章的那个早上,我正好在做关于Curry-Howard同构性的演讲。但幸运的是,其内容没有什么实质性的改变,因而我没有给观众过时的信息。)

总结

我开始写这篇文章的时候正在抱怨我所在行业的短视。尽管我们这个行业的历史不长,从业者仍然对历史很不熟悉。我之前听说,有人问Bjarne Stroustrup,把lambda表达式引入C++是不是因为lambda表达式是个新潮的玩意儿——lambda演算可以追溯到20世纪30年代,比C++要年纪大多了。

但当回顾这份清单上的计算机科学家们的背景时,我不得不为自己的短视感到惊讶。上面说的这12个科学家中,有10个都是男性,且为白人。

因此,我想总结说,除非我有严重的偏见,我们仅仅用到了人类才华总和中很小的一部分。当我思考过去百年我们在计算机科学里走了多远的时候,我无法想象如果能调用更多的聪明才智,下个百年我们会有多么伟大的成就。

from:http://www.techug.com/100-years-of-computer-science