线程与并发

线程

线程与进程的关系

回顾：什么是进程？

进程（Process）是程序运行的实例。一个进程由当前状态和系统资源组成。

  • 当前状态（Current State）

    包括 CPU 寄存器、栈指针、PC 指针等。

  • 系统资源（System Resources）

    地址空间、I/O 状态等。

每个进程的系统资源都是受到保护的。

什么是线程？

线程（Thread）是进程中的顺序执行流（Sequential execution stream），进程的一组线程共用进程的系统资源。

线程的生命周期

多线程 & TCB

多线程（Multithread）是一种技术，即一个程序的进程可以有多个不同的并发线程。

单线程进程和多线程进程

就如进程会将其信息存储在 PCB 中，每个线程也有一个维护自身信息的数据结构 —— TCB（Thread Control Block）

那些线程的私有状态会保存在 TCB 内，如：

  • CPU 寄存器（包括 PC 寄存器）
  • 程序执行的栈指针（Execution stack pointer）
  • 调度信息（包括状态、优先级、CPU 执行时间等）
  • ...

操作系统将 TCB 存储在内核内存中，以便能够轻松地访问和管理所有线程的信息。这样，操作系统可以在需要时对线程进行调度、切换线程的上下文以及管理线程的状态等操作，而这些操作需要访问 TCB 中存储的信息。

每个 PCB 都会指向多个 TCB：

线程切换可以分为两种：

  • 在同一个 PCB 内（Within a PCB），这种切换地址空间保持一致；
  • 在不同的 PCB 之间（Across PCBs），这种切换需要改变地址空间。

多线程的优点

  • 不同于进程的上下文切换，线程切换（Thread Switch）开销低很多；
  • 线程的创建和取消都比进程快很多；
  • 线程之间可以共享内存，更利于通信。

多核操作系统中的线程

多核操作系统中两种线程调度的方式：

  • 每个核维护自己的线程队列

    • 需要更有效的高速缓存
    • 需要平衡的调度策略

  • 所有线程都放置在一个单独的队列内

    image-20231208122701523

    • 有可能会导致竞态条件，需要锁机制

处理器亲和性（Processor Affinity）是计算机操作系统中的一个概念，它用于指定一个进程或线程在多核处理器系统中执行时应该绑定到哪个特定的处理器核心上。处理器亲和性允许开发者或系统管理员控制进程或线程的执行位置，以优化性能、降低延迟或满足特定的系统需求。

亲和性有两种类型：软亲和性（Soft Affinity）和硬亲和性（Hard Affinity）。

  • 软亲和性是指系统尝试将进程/线程保持在同一个处理器上运行的策略，但不保证一定能够做到。例如，由于处理器之间的负载平衡，进程可能会迁移到其他处理器。
  • 硬亲和性指的是某些系统提供的系统调用，允许进程指定一组处理器来运行。这意味着进程可以绑定在特定的处理器上，不会被系统迁移。

许多系统同时提供这两种类型的亲和性设置。

  • Linux系统中的 sched_setaffinity() 是一个系统调用，用于实现硬亲和性。通过这个调用，进程可以指定一个或多个处理器，以便系统将其调度到这些处理器上运行。

    sched_setaffinity() 函数接受三个参数：

    1. pid_t pid ：进程ID。如果该值为0，则表示当前进程。
    2. size_t cpusetsize ：cpu_set_t 结构大小，通常为系统 CPU 数量的字节大小。
    3. const cpu_set_t *mask ：指向 cpu_set_t 结构的指针，该结构定义了进程可以运行的 CPU 集合。使用 CPU 集合，可以指定一个或多个 CPU 核心。

ULT & KLT

就像进程分为内核进程和用户进程一样，线程也有同样的分类：

  • 内核级别线程（Kernel Level Thread，KLT）

    KLT 是由操作系统内核管理和调度的线程。每个线程都有一个对应的内核线程。

    • 所有现代操作系统都支持 KLT
    • 直接被内核控制
    • 每个 KLT 都能独立运行或者被阻塞
    • 一个进程可以有多个 KLT 在等待不同的事件
    • 缺点
      • 相比于 ULT 更 “昂贵”，因为要经常和内核打交道

  • 用户级别线程（User Level Thread，ULT）

    ULT 是在用户空间中由应用程序或线程库管理的线程。操作系统对它们一无所知，只会认为应用程序只有一个线程在运行。

    • ULT 相比于 KLT 更加轻量级，用户的程序自身一般就能提供进 ULT 的线程调度，由于不需要内核的参与，ULT 的切换一般更快

    • ULT 在相对于彼此而言，可能会以非抢占（Non-preemptive）的方式进行调度

    • 缺点：

      • 一个线程处于 I/O 阻断，所有线程都会被阻断（多对一模式）

      • 内核无法干预 ULT 的调度，这意味着其不能利用多核处理器的优势

        由于操作系统对用户级线程一无所知，它无法将不同的 ULT 分配给不同的处理器核心并进行并行执行。因此，无论多核处理器上有多少个核心，操作系统只会认为应用程序只有一个线程在运行。这限制了 ULT 利用多核处理器的能力。

  • 三种线程模式（Threading Model）

    1. 一对一（One-to-One）：
    • 在这个模型中，每个用户级线程都直接映射到一个内核级线程。
    • 这种模型的优点是一个线程在执行系统调用或者进行阻塞操作时，不会影响到其他线程。
    • 这是 Linux 和 Windows 系统中常用的模型，它可以很好地利用多核处理器的并行处理能力。
    • 但是，因为每个线程都需要内核级的结构，所以线程的数量可能受到系统资源的限制。

    1. 多对一（Many-to-One）：
    • 在这个模型中，多个用户级线程映射到单个内核级线程。
    • 优点是线程切换和管理的开销很小，因为这些操作都在用户空间完成。
    • 缺点是如果任何一个线程执行阻塞系统调用，整个进程都会被阻塞，因为操作系统只看到一个线程。
    • 这种模型不适合多核处理器，因为它无法同时在多个核心上并行执行多个线程。

    1. 多对多（Many-to-Many）：
    • 这个模型结合了前两者的优点。
    • 允许多个用户级线程映射到多个内核级线程，提供了很大的灵活性。
    • 这种模型既可以防止一个线程的阻塞操作影响其他线程，也可以利用多核处理器的并行处理能力。
    • 但是，这种模型的管理相对复杂，调度也更为困难，因为需要在用户和内核空间之间协调线程的管理。

线程交错

线程交错（Thread Interleaving）是指在多线程编程中，多个线程的执行在时间上交错进行的现象。当一个计算机系统具有多个处理核心（例如多核处理器）或者操作系统采用分时调度策略时，多个线程之间会竞争执行权，导致它们交替运行，这就是线程交错。

并行与并发

二者区别

并行（Parallelism）和并发（Concurrency）是两个在多任务处理领域常被讨论的概念，它们描述了系统处理多个任务的方式，但它们指的并不是相同的情形。

并行（Parallelism）：

  • 并行处理指的是系统同时进行多个任务的能力。这通常涉及到多核或多处理器的系统，其中每个核或处理器可以同时执行不同的任务或同一个任务的不同部分。
  • 并行性的关键在于性能的提升，因为它可以显著减少完成多个任务的总时间。
  • 例如，在一个四核处理器上，四个独立的计算可以同时进行，每个核心处理一个计算。

并发（Concurrency）：

  • 并发处理是指系统能够处理多个任务的能力，但不一定是同时进行的。在单核处理器上，操作系统可以通过任务切换，使得用户感觉到多个任务似乎是同时执行的。
  • 并发性不一定提高性能（相对于单任务来说），而是关于多任务管理的效率。并发可以在单核或多核机器上实现。
  • 例如，一个服务器运行多个进程，通过快速切换来服务多个客户端，即使在任何给定的微秒内，只有一个进程在执行。

简而言之，并行是关于同时做多件事情（提高吞吐量），而并发是关于处理多件事情（管理共享资源的访问）。并行是并发的一个子集；所有并行系统都是并发的，但不是所有并发系统都是并行的。并发强调的是正确性和管理多个同时活动的任务，而并行强调的是性能和做相同的事情来加速计算。

并发中的一些概念

竞态条件

竞态条件（Race Condition）是指一种在并发程序中的错误，它出现在当程序的结果依赖于线程的调度顺序的情况，其强调结果的不可预判性。

互斥

互斥（Mutual Exclusion）指一个资源无法被多个线程共享，即一个线程在完成某个任务直到释放资源之前，其他进程都不能访问该资源。

临界区

临界区（Critical Region）就是程序中需要互斥的部分。

为了实现临界区，操作系统会给一些资源分配锁（Lock），当一个线程访问该资源时会拿到该资源的锁，此时其他线程均无法访问而被放置在一个入队列集合。

入队列集合（Entry Set Queue）是一个数据结构，用于存储等待获取锁的线程。每当一个线程尝试获取锁但锁已经被其他线程占用时，该线程会被加入到集合中，等待锁释放。

很多编程语言给了这个抽象概念的具体实现方式，比如 Java 中的 synchronized 关键字。

死锁

死锁（Deadlock）是指在多线程或多进程环境中，两个或多个线程（或进程）由于相互等待对方释放资源而陷入无法继续执行的状态。在死锁状态下，每个线程都在等待其他线程释放资源，但由于相互之间的依赖关系，它们都无法继续执行下去。死锁是一种常见的并发编程问题，可以导致系统停滞，无法正常运行。

死锁通常涉及以下几个关键要素：

  1. 互斥（Mutual Exclusion）：多个线程或进程竞争获取某个资源，但同一时刻只能有一个线程或进程占有资源。
  2. 请求和保持（Hold and Wait）：线程在持有某些资源的同时，又请求其他资源，但由于资源被其他线程占有，请求线程必须等待。
  3. 不可抢占（No Preemption）：资源只能由占有它的线程主动释放，而不能被强制抢占。
  4. 循环等待（Circular Wait）：多个线程之间形成了一个循环链，每个线程都在等待下一个线程释放资源，从而造成了死锁。

以上四个条件是死锁的必要条件，缺一不可。

分配图

分配图（Allocation Graph）是一种检测死锁的方式，分配图中一共有两类节点：一是线程，而是资源，如下图。

分配图中所有的边都是有向的：

  • 从线程指向资源的边称为请求边（Request Edge），表示线程正在请求某个资源。
  • 从资源指向线程的边称为分配边（Assignment Edge），表示该资源正在被某个线程占有。

再上图中，资源和线程形成了一个回环，产生了死锁，但并不是有回环就一定会有死锁。关于线程分配图中的回环与死锁之间的关系，有以下几点需要了解：

  • 存在回环不一定意味着死锁：虽然死锁的一个典型特征是资源分配图中的回环，但并不是所有回环都表示死锁。关键在于这个回环是否包含了所有相关资源和线程。如果一个线程（或几个线程）在回环中，但是它们还可以访问其它资源来继续运行，那么这个回环就不一定代表死锁。

    • 如果都只有一个实例，那么回环意味着死锁
    • 如果回环中的资源有很多个实例，那么就不意味着死锁

    如下图：

    图中存在回环：\(T_1 \to R_1 \to T_3 \to R_2 \to T_1\)，但注意到 \(T_4\) 在这里没有请求，说明 \(T_4\) 可以正常运行，那么当 \(T_4\) 运行结束后 \(R_2\) 会被释放，\(T_3\) 便可以成功获得 \(R_2\) 的请求， 从而打破循环等待，所以不会产生死锁。

  • 没有回环通常意味着没有死锁：如果资源分配图中没有回环，那么一般可以认为系统中没有死锁。这是因为死锁的一个条件是循环等待，这在资源分配图中表现为回环。

因此，线程资源分配图存在回环是产生死锁的必要不充分条件。

如何避免死锁

要避免死锁，就要从死锁产生的四个条件入手，只要破除四个条件中的任何一个就可以成功解决死锁的问题。

  • 解决「互斥」

    一种解决方案是让资源可共享，这样就不会有互斥的需求。在某些情况下，这是可能的，例如，多个线程可以同时读取同一个只读文件，因为它们不会对文件内容进行修改，从而不会发生冲突。这个想法很理想，但多数时候不允许。

  • 解决「请求和保持」

    我们可以考虑一次性让一个线程拿到所有它请求的资源，阻断其他占取它资源的线程。这样也不现实，可能会导致每个线程在等待资源上浪费过多时间。

  • 解决「不可抢占」

    我们可以考虑运行线程抢占资源，从而打破循环请求。但这样又可能导致线程饥饿。

  • 解决「循环等待」

    我们可以定义一个严格的资源分配顺序，从而避免循环等待的情况。

    例如我们可以给资源进行编号，要求每个线程以递增的枚举顺序请求资源来解决这个问题。

    如上图所示，假如 \(i < j\)，那么线程 A 可以请求 \(j\)，但线程 \(B\) 无法请求 \(i\)，从而避免了死锁。

操作系统
#操作系统 #并发 #线程 #死锁
线程与并发
https://goer17.github.io/2023/12/06/线程与并发/
作者
Captain_Lee
发布于
2023年12月6日
许可协议