search

cosven / cosven.github.io

个人零碎笔记，博客草稿，阅读笔记
10 stars 0 forks source link

读《深入理解计算机系统》 #60

Open cosven opened 5 years ago

cosven commented 5 years ago

课程地址：https://ipads.se.sjtu.edu.cn/courses/ics/schedule.shtml

笔记进度：

cosven commented 5 years ago

LEC 1: Intro

三个阶段（以中国文化类比）

层级

image

读什么

However, the book is not well organized for Chinese students

LEC 2: C Programming Language, Bits & Bytes

LEC 3: Bit-level Ops

cosven commented 5 years ago

LEC 4: Logical Ops, Encodings

image

cosven commented 5 years ago

LEC 5: Arithmetic Operations

TODO

cosven commented 5 years ago

配合本章阅读，可以做的几件事

看书应该记录什么？

第 12 章：并发编程

概述

本章的第一段的这个定义非常的形象：

如果逻辑控制流在时间上重叠，那么它们就是并发的（concurrent）。这种常见的现象叫做并发（concurrency），出现在计算机系统的不同层面上。硬件异常处理程序、进程和 Linux 信号处理程序都是大家很熟悉的例子。

非常有启发性的一句话（信号也是并发的一种体现）：

并发不仅仅局限于内核，它也可以在应用程序中扮演重要角色。例如：我们已经看到 Linux 信号处理程序如何允许应用响应异步事件...

应用级并发在其他情况下也是很有用的：

  • 访问慢速 I/O 设备
  • 与人交互
  • 通过推迟工作以降低延迟（比如多个小操作合成一个大的操作来进行）
  • 服务多个网络客户端
  • 在多核机器上进行并行计算

从i下面的描述中可以领悟到并发与进程（线程）等概念的关系。

使用应用级并发的应用程序称为并发程序（concurrent program）。现代系统提供三种基本的构造并发程序的方法：进程；I/O 多路服用；线程。

基于进程的并发编程

这个部分书上也没有讲很多内容。它编写了一个基于进程的“并发服务器”的例子，顺便强调了两点：

  1. 资源管理的问题：fork 的时候，有的进程资源也会复制出来一份（比如：socket 文件描述符），这时候要记得父子进程用完都要关闭，否则会有内存泄漏
  2. 子进程管理：父进程要处理 SIGCHLD 来处理僵尸（zombie）子进程（关于 SIGCHLD，我感觉这篇博客讲的不错）

这两点看 gunicorn 的 SyncWorker 的源码也能感受到，为了学习，自己仿照 gunicorn 0.2 版本代码写了一个 web 服务器，非常残疾的那种，不过也体现了上面两点。我相信编写多进程程序，最基本的就是注意上面这两点。

最后讲了进程的优劣

进程有独立的地址空间，一个进程不可能不小心覆盖另外一个进程的虚拟内存，这就消除了许多令人疑惑的错误 - 这是明显的优点。 独立的地址空间使得进程共享状态信息变得更加困难。为了共享信息，必须使用显示的 IPC（进程间通信）机制。另外一个缺点是：它们往往比较慢，进程控制和 IPC 的开销很高。

书上还对 Unix IPC 进行一些旁注

waitpid 函数和信号是基本的 IPC 机制，它们允许进程发送小消息到同一主机上的其他进程。套接字接口是 IPC 的一种重要形式，它允许不同主机上的进程交换任意的字节流。 然而，术语 Unix IPC 通常指的是所有允许进程和同一台主机上其他进程进行通信的技术。其中包括管道、先进先出、系统 V 共享内存，以及系统 V 信号量（semaphore），这些机制超出了我们的讨论范围。

读后感：读完这一小结，看了 gunicorn 0.2 的部分代码，写了 medusa，我觉得自己终于敢动手写多进程的玩具了，但是如果要在生产环境写，我应该会去看看 multiprocessing 的源码，或者找个其他的项目再次学习下。

基于 I/O 多路复用的并发编程

这个小节和上一节套路基本相同，它编写的例子是基于 select 的。这一小节虽然篇幅较长，但它没有讲很多理论上的东西，主要是围绕“基于 I/O 多路复用的并发 echo 服务器”这个例子展开，没有什么值得特别说明的，它甚至连“什么是多路复用”也没有讲，而自己没有亲手实践，感觉学到的东西也很有限。

值得一记的就是 I/O 多路复用技术的优劣了

事件驱动设计的一个优点是，它比基于进程的设计给了程序员更多的对程序行为的控制。 另外一个优点是，一个基于 I/O 多路服用的事件驱动服务器是运行在单一进程上下文中的，因此，每个逻辑流都能访问该进程的全部地址空间。 最后，事件驱动设计常常比基于进程的设计要高效许多，因为它们不需要进程上下文切换来调度新的流。 事件驱动设计一个明显的缺点就是编码复杂（在这个例子，代码行数是基于进程的服务器的 3 倍多）

读后感：没啥太多收获。

基于线程的并发编程

线程（thread） 就是运行在进程上下文中的逻辑流

每个线程都有它自己的线程上下文（thread context），包括一个唯一的整数线程 ID（Thread ID，TID）、栈、栈指针、程序计数器、通用目的寄存器和条件码。线程共享进程的整个虚拟地址空间。

基于线程的逻辑流结合了基于进程和基于 I/O 多路复用的流的特性。

线程执行模型

每个进程开始生命周期时都是单一线程，这个线程称为主线程（main thread）。在某一时刻，主线程创建一个对等线程（peer thread），从这个时间点开始，两个线程就并发运行。最后，因为主线程执行一个慢速系统调用，例如 read 或者 sleep，或者因为被系统的间隔计时器中断，控制就会通过上下文切换传递到对等线程。对等线程会执行一段时间，然后控制传递回主线程，依次类推。

我感觉这段话描述有点诡异，讲道理抢占式调度的话，也不需要等有慢速系统调用才进行切换吧？另外，从调度层面讲，线程应该都是平等的，不分父子吧？下面这段话也佐证了我的这个想法：

在一些重要的方面，因为一个线程的上下文要比进程上下文小的多，线程上下文切换速度也就快很多。 另一个不同就是线程不像进程那样，不是按照严格的父子层次来组织的。和一个进程相关的线程组成一个对等（线程）池。对等（线程）池概念的主要影响是，一个线程可以杀死它的任何对等线程，或者等待它的任意对等线程终止。

Posix 线程

Posix 线程（Pthread）是在 C 程序中处理线程的i个标准接口。它最早出现在 1995 年，而且在所有的 Linux 系统上都可用。Pthread 定义了大约 60 个函数，允许函数创建、杀死和收回线程，与对等线程安全地共享数据，还可以通知对等线程系统状态的变化。

  • 创建线程 pthread_create
  • 终止线程 pthread_exit pthread_cancel
  • 回收已终止线程的资源 pthread_join。注意：和 Linux 的 wait 函数不同，pthread_join 函数只能等待一个指定的线程终止。没有办法让 pthread_wait 等待任意一个线程终止。
  • 分离线程 pthread_detach 在任何一个时间点上，线程是可结合的（joinable）或者是分离的（detached）。一个可结合的线程能够被其他线程收回和杀死。一个分离的线程是不能被其他线程回收或者杀死的。它的内存资源在它终止时由系统自动释放。
  • 初始化线程 pthread_once

自己没有使用过 pthread 等接口，平常也很少使用 Python 的 Thread，所以只对 pthread_join 函数有一定理解，另外 create 函数也相对好理解。exit/cancel 用来终止线程，终止后需要用 join 来回收资源。当然，detach 的线程就交给操作系统自动回收了。cancel/join 这类函数接受的参数都是 tid(pthread_t 结构体)，create 函数可以初始化一个 tid。

在网上摘抄一段关于 pthread_once 的解释：在多线程环境中，有些事仅需要执行一次。通常当初始化应用程序时，可以比较容易地将其放在main函数中。但当你写一个库时，就不能在main里面初始化了，你可以用静态初始化，但使用一次初始化（pthread_once）会比较容易些

多线程程序中的共享变量（重要）

线程内存模型 调用栈

如果一个线程以某种方法的到一个指向其他线程栈的指针，那么它就可以读写这个栈的任何部分。

可以结合这个问题 https://www.zhihu.com/question/266349340 来理解这句话。

将变量映射到内存

共享变量 我们说一个变量 v 是共享的，当且仅当它的一个实例被一个以上的线程引用。

用信号量同步线程

共享变量是十分方便，但是它们也引入了同步错误（synchronization error）的可能性。

经典问题有两个线程对一个 count 分别累加 n 次，结果不是 2n，而可能是 (n, 2n) 之间的一个数。有一种工具可以帮助这种问题进度图（progress graph）。

进度图

文章中把（累加）经典问题的汇编代码给写了出来，汇编代码的每条指令就是一个单位，于是，两个线程的执行过程就可以画出一个二维直方图。文章也给了一个进度图的概念，但我觉得并没有什么用。不过它以进度图为基础，引出了几个概念（没有进度图也完全可以引出来...）

操作共享变量 count 内容的指令构成了一个（关于共享变量 count 的）临界区（critical section），这个临界区不应该和其他进程的临界区交替执行。 换句话说，我们想要确保每个线程在执行它的临界区中的指令时，拥有对共享变量的互斥的访问（mutually exclusive access）。通常这种现象称为互斥（mutual exclusion）。 在进度图中，两个临界区交集形成的状态空间区域成为不安全区（unsafe region）。

注：文章把临界区看做一条执行路径，所有如果是两个线程，那么两个线程的临界区执行路径迭在一起，就形成了一个正方形，不安全区。 我搜了下，网上似乎都没有关于进度图的资料，所以这可能是作者想出来的一种帮助理解线程同步的一个方法。

信号量

Edsger Dijkstra，并发编程领域的先锋人物，提出了一种经典的解决同步不同执行线程问题的办法，这种方法是基于一种叫做信号量（semaphore）的特殊类型变量的。 信号量 s 是具有非负整数值的全局变量，只能由两种特殊的操作来处理，这两种操作称为 P 和 V。

Edsger Dijkstra 出生于荷兰。名字 P 和 V 来源于荷兰语单词 Proberen（测试）和 Verhogen（增加）。

使用信号量来实现互斥

二元信号量（binary semaphore）的值总是 0 或者 1。以提供互斥为目的的二元信号量常常也称为互斥锁（mutex）。 一个被用作一组可用资源的计数器的信号量被称为计数信号量。

利用信号量来调度共享资源

1. 生产者 - 消费者问题 这其实就是一个队列吧。书本中的例子是用一个 mutex + 两个 semaphore（一个表示空余的，一个表示可以消费的）。我看了 Python 的 Queue 实现，和这个逻辑基本一样，不过它是用一个 mutex + 两个条件变量（一个表示是否可生产，一个表示是否待消费）来实现的。

2. 读者 - 写者问题 读者-写者问题是互斥问题的一个概括。一组并发的线程要访问一个共享对象，有些线程只读对象，其他线程只修改对象。修改的线程叫写者，只读对象的线程叫做读者。写者必须拥有对对象独占的访问，读者可以和其他读者共享对象。

这个问题有几个变种，分别基于读者和写者的优先级。第一类：读者优先。第二类：写者优先。对这两种读者-写者问题的正确解答可能导致饥饿（starvation）。饥饿就是一个线程无限期地阻塞，无法进展。比如当读者优先级高时，如果读者源源不断，那么写者就可能一直等待。这个例子还听好玩的...

综合：基于预线程化的并发服务器

书中又写了一个例子：预线程化 + 生产者-消费者模型。 这种也叫作事件驱动，所以 I/O 多路服用不是编写事件驱动的唯一方法。

使用线程提供并行性

想起 pingcap talent plan 里面有个用 goroutine 写 merge sort 的题。

刻画并行程序的性能

理想情况下，我们期望运行时间随着核心数的增加线性下降。但实际上不会这样（书上的例子）是大于四个（四核）。他说线程多了，会有上下文切换的开销。并行程序常常被写为每个核上只运行一个线程。

绝对时间是衡量程序性能的终极标准，但是也有一些有用的相对衡量标准 并行程序的加速比（speedup）通常定义为 Sp = T1/Tp p 为处理器核心数，Tk 是在 k 个核上的运行时间。这个公式有时被称为强扩展（strong scaling）。当 T1 是程序顺序执行版本的执行时间时，Sp 称为绝对加速比（absolute speedup），当 T1 是程序并行版本在一个核上的执行时间时，Sp 称为相对加速比（relative speedup）。绝对加速比能更真实的衡量并行的好处。

一种相关的测量量称为效率（efficiency），定义为： Ep = Sp/p = T1/pTp

加速比还有另外一面，成为弱扩展（weak scaling），在增加处理器数量的同时，增加问题的规模，这样随着处理器数量的增加，每个处理器执行的工作量不变。在这种描述下，加速比和效率被表达为单位时间完成的总工作量。

其他并发问题

线程安全

一个函数被称为线程安全的（thread-safe），当且仅当被多个线程反复地调用时，他会一直产生正确的结果。 我们定义出四个（不相交的）线程不安全函数类：

  1. 不保护共享变量的函数
  2. 保持跨越多个调用的状态的函数（注：这个比较抽象，我看书上的例子是一个函数依赖了一个全局变量）
  3. 返回指向静态变量的指针的函数。结果可能会被另外一个线程覆盖（注：感觉还是全局变量）
  4. 调用线程不安全的函数（感觉有点废话）

个人感觉主要就一个点：保护共享变量。

可重入性

有一类重要的线程安全函数，叫做可重入函数（reentrant function），其特点在于它们具有这样一种属性：当它们被多个线程调用时，不会引用任何共享数据。

如果所有的函数参数都是值传递，并且所有的数据引用都是本地的自动栈变量，那么函数就是显示可重入的。

我没有很懂这个逻辑，书上说可重入是线程安全的真子集，网上很多博客说的不太一样。但是外面是这样描述可重入的：在任意时刻被中断然后操作系统调度执行另外一段代码，这段代码又调用了该子程序不会出错。感觉知乎上这个回答比较靠谱一点：异步可重入函数与线程安全函数等价吗？ - 陈硕的回答 - 知乎

竞争

当一个程序的正确性依赖于一个线程要在另外一个线程到达 y 点之前到达它的控制流中的 x 点时，就会发生竞争（race）。

死锁

信号量引入了一个潜在的令人厌恶的运行时错误，叫做死锁（deadlock），它指的是一组线程被阻塞了，等待一个永远不会为真的条件。

比如有两个信号量，两个信号量的禁止区有重叠，则重叠的区域就是死锁区域。 程序的死锁原因有很多，要避免死锁一般而言是很困难的。然而，当使用二元信号量来实现互斥时，我们有一个规则来避免死锁。

互斥锁加锁顺序规则：给定所有互斥操作的一个全序，如果每个线程都是以一种顺序获得互斥锁并以相反的顺序释放，那么这个程序就是无死锁的。

我记得有这样一个经典的死锁面试题，死锁发生的四个必要条件？

cosven commented 5 years ago

并发编程 - 实践

死锁案例 1 - Python import 死锁

#!/bin/bash
cat > test_module.py <<EOF
import threading
import requests
def make_request():
    print('before requests.get')
    requests.get('https://github.com/kennethreitz/requests')    # <-- program will get stuck here
    print('after requests.get')
thread = threading.Thread(target=make_request)
thread.start()
thread.join()
EOF
python -c 'import test_module'

详情见 https://github.com/kennethreitz/requests/issues/2925

解决这个死锁的办法：消除循环等待：不要在这里 join，否则主线程 import 时等待子线程完成，而子线程需要 import 锁。

一个“迷惑”的 Semaphore 使用实例

from threading import Thread, Semaphore

sem = Semaphore(0)

def job(name):
    with sem:
        print("I'm", name)

t1 = Thread(target=job, args=('job1', ))
t2 = Thread(target=job, args=('job2', ))
t1.start()
t2.start()
sem.release()
t1.join()
t2.join()

这样编写程序，结果会长这样：

/tmp > python3.7 t.py
I'm job1
I'm job2