[译文]5分钟系列—快速理解Multithreading(多线程)

原文链接:A gentle introduction to multithreading

前言

随着计算机硬件 ( hardware ) 的更新迭代以及操作系统 ( operating systems ) 的智能化,使得现代计算机能够同时处理更多任务;从而让我们的应用程序执行速度更快,响应时间更短

因此编写软件的时候,我们可以利用并发处理越来越多的事情;但凡事都有代价,这要求我们对并发的实现原理要有更深入的了解。让我们用 threads (线程)来开启并发的魔法之旅吧

Processes and threads ( 进程与线程 ) : 字如其意

目前主流的操作系统都能同时运行多个程序,这也是为什么你能用 Chrome 浏览器看这篇文章的同时,还能用网易云音乐听歌。因为每个程序都运行在一个所谓 进程 的环境中;操作系统为每个进程提供不同的硬件支持 ( 包括 CPU,内存,显存,输入输出等)

让操作系统同一时间执行多个任务,并不是只有启动多个进程这一个办法。每个进程可以在其内部同时开启多个 线程 用来并发执行任务。你可以把线程看作是进程的一部分,每个进程启动的时候,至少会开启一个线程,一般称这个线程为:主线程。程序员可以根据实际需求,开启或者停止其他线程用来执行任务;我们经常说的多线程,指的就是在一个进程中,开启多个线程

我们用来听歌的网易云音乐,就是个多线程程序。主线程用来渲染UI界面,子线程1 用来播放音乐,子线程2 用来读取歌词并显示等。你可以通俗的把操作系统看成是进程的容器 ( 其实更像是管理员 ) ,进程是线程的容器,示例图如下:

进程和线程的区别

操作系统为每个进程分配一块独立的内存空间;默认情况下,进程之间不共享内存空间 ( 也就是不能相互访问 ) ,比如:Chrome浏览器无法访问网易云音乐的运行内存,反之亦然。除非使用进程通讯技术 inter-process communication (IPC)

与进程不同,线程能够共享父进程的内存空间。比如: 网易云音乐的UI界面线程可以访问音乐播放线程的内容,反之亦然。同时,线程占用资源更少,创建/切换 速度更快,也有人将线程称为:  lightweight processes (轻量级进程)

因此,相对启动多进程(通讯不方便,更消耗资源),启用多线程才是同时处理多任务的最佳实现,而且程序能运行的更快

多线程用处

为什么需要多线程?因为并发执行任务能大大节省时间提高效率。举个不太恰当的例子:比如你下载一部电影,如果单线程下载,需要1小时;但是多线程下载,就可以根据线程数去下载不同的片段,多任务同时进行,那么就可以很快下完

多线程太完美了,真的就这么简单吗?以下几个问题你要好好考虑:

  • 不是所有程序都要用到多线程。如果你的程序本身就需要顺序执行;或者频繁等待用户输入,那就没有必要多线程
  • 线程不是越多越好。要根据具体任务的类型思考和设计,是否增加线程
  • 多线程并不保证真正做到并发执行。这还要取决硬件是否支持

最后一点请注意,并不是所有硬件设备都支持同一时刻执行多任务,只不过操作系统让它看起来像,这个后面会介绍

我们先把 并发(Concurrency) 看作是多任务看起来是同时执行;而 并行(Parallelism) 是看作是同一时刻处理多任务。举个简单的例子来理解并发和并行

并发:吃饭的时候,来了电话;停止吃饭,接电话

并行:吃饭的时候,来了电话;边吃饭边打电话(并行也不一定高效,吃饭的时候说话对方有可能听不清楚,导致打电话时长增加)

并发(Concurrency),并行(Parallelism)

CPU是程序被执行的地方,它由很多部分组成,其中最核心的部分称之为:Core (核心),每个核心同一时刻只能执行一个操作。硬件设计如此,因此操作系统为了能最大化利用核心,发明了很多先进技术,使得用户能够运行多个进程,其中最重要的技术就是:抢占式多任务处理机制。抢占是指中断当前任务,切换到另一个任务,稍后再切回当前任务继续执行

因此,如果你的硬件是单核CPU,那么操作系统的工作就是将单核的算力分配到不同的进程或线程上,这些进程或者线程会被轮询执行;这样就会给我们造成一个假象:同时多个程序被执行 或者一个程序同时执行多个任务(多线程)。虽然这满足了并发,但实际上并未真正并行

如今CPU早就多核心,每个核心同一时刻都能进行一个操作,这也意味着真正的 并行 是可能的。操作系统会自动检测CPU的核心数量,并为每个核心配置进程/线程。一个进程/线程运行在哪个CPU核心对我们来说是完全透明的,而且一旦所有核心都很忙,那么抢占式多任务处理就会启动。这也是为什么计算机能同时开启的进程数量远超CPU核心数的原因

对于单核CPU多线程有意义吗?

在单核CPU上,真正实现并行是不可能的。不过,多线程依然是有意义的,因为抢占式任务处理的存在,它可以使得应用程序保持响应,即使其中一个线程执行缓慢或阻塞的任务

举个例子:假如你的应用要从磁盘读取某个大文件,此时如果是单线程,那么整个应用会未响应状态。如果用多线程,那么就可以线程A去读取文件,线程B刷新UI界面(实时观测读取该文件的进度)

多线程,多问题

依上文可知,线程会共享其父进程的内存空间;这就使得同个进程内的多线程之间可以很方便的进行数据交互。多个线程从同一块内存地址中读取数据没有任何问题,但是一旦某个线程进行写操作,而其他线程进行读操作时就容易出现如下问题:

  • Data Race(数据竞争):线程A 对一块内存地址的内容形成写操作,而 线程B 又同时读取这块内存地址存储的值,那么就有可能读到的是脏数据
  • Race Condition(竞争条件):线程执行的顺序是不可控的,而我们程序又希望按照指定的顺序执行。比如:我们要求 线程B 只能在 线程A 完成写入操作后再读取数据

如果一段代码,很多线程同时调用它而且不会有 数据竞争 和 竞争条件 ,那么我们称这段代码 thread-safe(线程安全)

数据竞争的根本原因

CPU内核一次只能执行一条机器指令。因其不可分割性,我们称这种指令为 原子指令(它不能被分解成更多步骤的操作)。希腊单词 atom(ἄτομος;atomos)的意思是不可切割的

因不可分割的特性,原子操作天然的线程安全:当 线程A 的写操作具备原子性时,其他线程在 写操作指令 完成之前则无法执行 读操作指令;反之亦然,因此不会发生数据竞争

可问题就是,大部分的操作指令都不是原子指令。即使是像 i++ 这样简单赋值也是由多个原子指令组成 (可以思考以下,为什么它不是原子操作,面试官很喜欢问的一个问题),从而使赋值本身作为一个整体是非原子的。因此,如果一个线程B 读取 i 而线程A 执行赋值,就会触发数据竞争

竞争条件的根本原因

抢占式多任务处理机制使得操作系统能够完全掌控和管理线程:它可以根据调度算法启动、暂停和中止线程;作为程序的开发者,你并不能控制线程的执行时间和顺序。实际上,你并不能保证如下代码会按照指定的顺序执行(一般是指从上到下)

writer_thread.start()
reader_thread.start()

运行多次,你就会发现有时 writer 线程先启动,有时 reader 线程先启动。如果你的程序需要保证先执行写操作再执行读操作,那么你肯定会遇到竞争条件

这种行为被称为不确定性:结果每次都会改变,你无法预测。调试受竞争条件影响的程序非常烦人,因为产生的bug是非必现的,而且有可能在你的计算机运行不会出问题,而在别人的计算机上就会有问题

多线程与并发

多线程编程,数据竞争 和 竞争条件 是经常会出现的问题。容纳多个并发线程的技术称之为: concurrency control (并发控制),操作系统或者一些编程语言为我们提供了一些解决方案,比较通用的是如下几种:

  • synchronization 同步: 确保同一时刻仅有一个线程在使用资源。将代码的特定部分作上标记,这样多个并发线程就不会同时执行这段代码,也不会让共享数据变得混乱
  • atomic operations  原子操作: 借助操作系统提供特殊指令,将非原子操作(如:赋值操作)转化为原子操作 ( 比如C#的 Interlocked.Increment )
  • immutable data 不可变数据: 当数据被标记为不可变(ReadOnly),只允许线程从中读取数据,而不允许线程改变数据内容

以上三种只是比较常规的做法,C# 内关于多线程的解决,还有一些其他方案,比如:监视器(Monitor)、互斥锁(lock)、读写锁(ReadWriteLock)、互斥(Mutex)、信号量(Semaphore)、事件(AutoResetEvent/ManualResetEvent)等

[译文]5分钟系列-快速理解Hash Table(哈希表)

原文链接 : What is a Hash Table?

什么是哈希表?

哈希表是用来存储同种类型 键/值对 的数据结构,它使得存储在哈希表内的 键/值对 能被非常高效的查找到。最典型的哈希表就是衣柜内的抽屉 :假如 第一格存放袜子,第二格存放T恤,第三格存放内衣。那么要找某一双袜子,你只要去第一格就能快速找到。 key(键)就是抽屉索引,value (值) 就是抽屉内存放的衣物

了解哈希表有什么用处?

  • 你可以大概了解哈希映射(hash map)、关联数组( associative array )、字典 ( dictionary ) 等这些常用的数据结构如何实现
  • 可以明白哪些数据比较适合用哈希表来存储

5分钟带你走入哈希表

假如我们现在要存储用户信息,同时还可以根据名字查找到对应用户的信息

用户信息

我们大可以将这三个用户存在一个数组内,查找的时候遍历数组对比名字,就能找到。看起来没什么问题,假如有成千上万个用户呢?那最差情况是不是得遍历所有用户挨个对比名字才能找到我们想要的用户信息,这显然效率低下

创建哈希表

为了能使用哈希表,存储的对象必须要有一个 唯一 的东西当作key,我们称它为:ID,假设用户的名字作为 ID 。哈希表的工作原理是将对象存储在对应的桶(buckets)内

一个哈希表选择多少个桶,各种编程语言内的集合类存储结构对桶的数量都有着不同的考量,这是个很大的话题,本文暂且就用4个桶来阐述哈希表的基本原理

每个用户该存储在哪个桶内呢?这是很关键的一步。你当然可以随便放入一个桶内,但下次拿的时候,你能想起来你放在哪个桶内吗?所以,此时需要一种算法,能根据 ID 迅速找到对应的桶号( 这就是 Hash Function 哈希函数 )

假设 a= 0, b=1, c=2 依次类推(不区分大小写),Ada = 0+3+0 = 3 ,那么 用户ada 就放入3号桶

同理,当我们需要获取 Ada 的相关信息的时候,就可以根据相同的算法,快速定位到 3 号桶,从而拿到他/她的信息 。让我们来存放第二个用户:Grace

哦吼,29超过了我们最大的桶编号,咋个办 ? 一个比较通用的办法是将 29 与桶的数量进行求余运算

一群小朋友玩躲猫猫的游戏,但是一开始谁最先找呢?就用到 “点兵点将 骑马打仗 有钱喝酒 没钱滚蛋 ”这个顺口溜,小伙伴站一排,然后通过这个顺口溜,一个字一个人,从头到尾数,人数不够就又从头来,点到 谁是 “蛋” 字,谁就开始找,这就是最原始的”求余”

29 % 4 = 1(也可以表示为:29 mod 4 = 1),因此用户 Grace 放入1号桶内,结果如下:

冲突

一个好的哈希函数的终极目标就是让每一个桶内只存放一个用户信息,让我们来存放用户 Tim 试试

结果显示,用户 Tim 应该放入 3 号桶,但是 3 号桶已经存储了 Ada 的相关信息,这就是所谓冲突

针对冲突,常用的方法有如下方法:

  • 发现当前桶已经存储了信息,就存入下一号桶内,如果下一号桶也存储了信息,就继续下去直到有空的桶。上文 3 号桶已经存储了信息,那么我们就找下一号桶,因为没有4号桶,所以就跳到0号桶存入
  • 每个桶是一个数组/链表,可以存储多个对象,求余结果一样,放到同一个桶内
  • 增加桶的数量,这样就能大大降低冲突的概率

因此,哈希表最重要的是哈希函数,一个好的哈希函数能让信息均匀的存入每个桶内(但是冲突永远无法避免,只能减少概率)。最坏的哈希函数导致的结果可能是所有的对象都放在同一个桶内,这就跟直接放入数组内没有什么区别了

关于哈希表的更详细信息,可以参考我翻译的数据结构系列文章:数据结构

课外延申

[译文]5分钟系列-快速理解Huffman Coding(霍夫曼编码)

原文链接What is Huffman Coding?

什么是霍夫曼编码 ( Huffman Coding )

霍夫曼编码是很多压缩算法的基础,比如著名的 DEFLATE (常用的图片格式 png 就用到了 DEFLATE ) 和 Gzip

为什么要了解霍夫曼编码?

有没有偶然的瞬间,或是通勤途中的地铁上,抑或是入眠前的思绪畅游,脑海中有如下疑问:

  • 如果做到无损压缩数据?
  • 为什么同一个文件,不同的压缩算法会有不结果(压缩率,压缩/解压时间)?
  • Gzip 是如何工作的?

5 分钟带你走入哈夫曼编码

压缩

假设我们想压缩一段字符串 (哈夫曼编码可以压缩任意数据,本文只是讲解基本原理,选用字符串最容易理解)

通常一段文本中,有些字符出现的频率会比另外一些字符更高;而哈夫曼编码就正是利用了这一点,对这段文本中出现的全部字符重新编码,让出现频率更高的字符占用更少的空间从而达到压缩的目的

就用 Yoda 大师的经典名言 “do or do not” 来当作示例,这句话一共 12 个字符。按照计算机默认编码格式 (关于编码格式,你可以参考UTF百科),每个英文字符占用 8 比特 (bit) , 一共占用96比特 ;那么采用霍夫曼编码以后一共占用多少比特呢?

首先,我们得先构建哈夫曼树。出现频率最高的字符,就距离树的根节点最近。依次类推,下图就是字符串 “do or do not” 的哈夫曼树

最常见的字符 ‘o’和 ‘ ‘ (空格) 距离根节点只有 2 步,而最不常见的 t 则距离根节点有 3 步。哈夫曼编码最神奇的事情来了,我们存储的不再是字符本身,而且存储从根节点到达它的路径。具体什么意思呢?

我们从根节点开始,然后沿着树像要编码的字符前进。如果走了左侧路径,则标记为 0,走了右侧路径,我们则标记为 1

因此,字符 d 的编码为:’100′ ,而字符 d 的默认编码是:’ 01100100 ‘,整个字符串编码以后的结果如下:

最终需要消耗 96 比特的字符串,采用哈夫曼编码以后,只需要 29 字节,足足压缩了2/3

解压

怎么解压呢?就是照着存储路径,依次从哈夫曼树拿到该路径对应的真实字符

聪明的你是不是早已想到,如果我只把压缩后的数据发给别人,别人没有对应的哈夫曼树,就没法解压。是的,大概来说有 3 种办法:

  • 将哈夫曼树和压缩后的文本一起发给对方,就可以根据你发的哈夫曼树来解压
  • 可以双方都同意同一颗已知的哈夫曼树,压缩和解压就可以都用它
  • 发送足够的信息,对方可以根据这些信息构建出哈夫曼树从而达到解压的目的(Gzip的工作方式),但是请注意:同样的信息,也有可能构建出不同的哈夫曼树,因此发送的信息要确保构建的哈夫曼树一致

课堂疑问

  • 上面的示例,为什么哈夫曼树是 4 层 ?所有的哈夫曼树都是 4 层吗?
  • 一大段 中文文本 和 英文文本 ,压缩比例会一样吗 ?

课外延申