🟢 Concurrency¶
约 4641 个字 1 张图片 预计阅读时间 23 分钟
并发与并行的区别？¶
并发¶
并发是指一个时间段内同时处理多个任务的能力。它强调的是 任务之间的独立性，以及它们是如何在一个处理器或单个核心上 交替执行 的。并发的目标是在有限的资源下实现任务之间的有效调度，从而最大限度地提高系统的响应事件。并发 并不意味着任务在同一时刻被执行，而是指它们 在同一时间段内得到处理。
并行¶
并行是指在 同一时刻执行多个任务的能力。它要求系统具备多个处理器或多个计算核心，这样就可以 同时处理多个任务。并行的目标是加速任务的完成速度，通过将任务分解为更小的部分并在多个处理器或核心上同时执行，以实现更快的任务执行速度。
区别¶
- 并发关注在一个时间段内处理多个任务，而并行关注在同一时刻执行多个任务
- 并发适用于单处理器或单核心系统，通过任务调度实现多任务处理； 并行则依赖于多处理器或多核心系统 来实现任务的同时执行
- 并发主要用于提高系统的响应速度和吞吐量，而 并行则旨在加速任务的完成速度
什么是互斥锁，自旋锁呢，底层是怎么实现的？¶
互斥锁(Mutex) 和 自旋锁(Spinlock) 是两种用于同步和保护共享资源的锁机制，它们都可以防止多个线程或进程同时访问共享资源，从而避免 竞争条件(Race Condition) 和 数据不一致 等问题。
互斥锁¶
互斥锁是一种用于实现线程或进程间同步的机制。当一个线程获得互斥锁并访问共享资源时，其他试图获得该锁的线程将被阻塞，直到锁被释放。互斥锁可以保证同一时刻只有一个线程能够访问共享资源。互斥锁的底层实现通常依赖于操作系统的原语，例如在 Linux 系统中使用 pthread 库的 pthread_mutex_t 数据结构来实现互斥锁。
自旋锁¶
自旋锁是一种低级的同步原语，通常用于多处理器或多核系统中。与互斥锁不同，当一个线程尝试获得自旋锁时，如果锁已经被其他线程持有，它将 不断循环(“自旋”)检查锁是否可用，而不是进入阻塞状态。自旋锁适用于锁持有时间较短且线程不希望在等待锁时进入睡眠状态的场景。自旋锁的底层实现通常依赖于原子操作和 CPU 指令，如 测试和设置(test-and-set) 或 比较和交换(compare-and-swap) 等。
区别¶
- 当线程尝试获得已被占用的互斥锁时，它会 进入阻塞状态，让出 CPU 资源，等待锁被释放
- 当线程尝试获得已被占用的自旋锁时，它会 不断循环 检查锁是否可用，而不会让出 CPU 资源
讲一讲死锁，死锁怎么处理？¶
死锁是指在多线程或多进程环境中，一组或多组线程/进程互相等待彼此持有的资源，导致这些线程/进程无法继续执行的情况。当死锁发生时，受影响的线程/进程无法完成任务，系统性能和吞吐量可能会受到严重影响。
死锁条件¶
- 资源互斥：一个资源在同一时间只能被一个线程或进程占用
- 持有并等待：一个线程或进程在持有至少一个资源的同时，仍然尝试获取其他线程或进程所持有的资源
- 资源非抢占：资源不能被强行从一个线程或进程中抢占，只能由占有它的线程或进程主动释放
- 循环等待：存在一个线程/进程等待序列，其中每个线程/进程都在等待下一个线程/进程所持有的资源
处理死锁¶
分为 预防、避免和检测恢复 三种策略：
- 预防死锁：预防死锁的方法是 破坏死锁产生的四个条件中的一个或多个
- 避免死锁：避免死锁的方法是在 运行时动态地检查资源分配情况，以确保系统不会进入不安全状态。银行家算法 是一种著名的避免死锁的算法，通过模拟资源分配过程来判断是否会产生死锁，如果会产生死锁，则拒绝分配资源
-
检测和恢复死锁：检测和恢复死锁的方法是允许系统进入死锁状态，然后定期检测死锁，并在发现死锁后采取措施解决。常见的检测方法包括 资源分配图(Resource Allocation Graph) 和 检测算法。恢复死锁的方法通常包括以下几种：
- 终止线程/进程：强制终止一个或多个死锁中的线程/进程，从而释放其持有的资源。这种方法可能会导致数据丢失或不一致，因此需要谨慎使用
- 回滚线程/进程：将死锁中的线程/进程回滚到之前的某个状态，然后重新执行。这种方法需要系统支持事务和恢复功能，并且可能会影响系统性能
- 动态资源分配：在检测到死锁后，尝试动态地分配资源，以解除死锁。例如，可以向系统请求更多资源，或者在不影响整体性能的情况下调整资源分配策略
- 等待和重试：在某些情况下，可以让死锁中的线程/进程等待一段时间，以便其他线程/进程释放资源。等待一段时间后，重新尝试请求资源。这种方法可能会导致线程/进程长时间处于等待状态，从而影响系统性能
什么是读写锁？¶
读写锁(Read-Write Lock)是一种用于 同步访问共享资源的锁机制，适用于读操作远多于写操作的场景。与互斥锁(Mutex)不同，读写锁允许多个线程同时进行读操作，但在 进行写操作时，只允许一个线程访问共享资源。这种锁机制可以提高多线程程序的性能，因为它允许多个线程在不互相干扰的情况下进行并发读操作。
读写锁的特性¶
- 共享读：多个线程可以同时获得读锁，共享读取共享资源。这意味着在没有写操作的情况下，读操作不会被阻塞
- 独占写：当一个线程获得写锁时，其他线程无法获得读锁或写锁。这可以确保在写操作期间，共享资源不会被其他线程修改或访问
- 优先级：实现读写锁时，可能需要处理读写操作之间的优先级。根据实现方式的不同，读写锁可能会更倾向于优先处理读操作，或者在某些情况下，优先处理写操作。这可能会导致写饥饿或读饥饿的问题，需要 根据实际场景进行权衡
读写锁在实现时通常依赖于底层的操作系统原语。例如，在 Linux 系统中，可以 使用 pthread 库中的 pthread_rwlock_t 数据结构来实现读写锁。
总之，读写锁是一种适用于读操作远多于写操作场景的同步机制。通过允许多个线程同时进行读操作，读写锁可以提高多线程程序在访问共享资源时的性能。然而，根据实现方式的不同，读写锁可能需要处理读写操作之间的优先级问题。
Linux 同步机制？¶
Linux 系统提供了多种同步机制，以便在多线程或多进程环境中实现对共享资源的安全访问。常见同步机制如下：
- 互斥锁：Linux 中的互斥锁是通过 POSIX 线程库(pthread)实现的。互斥锁(Mutex)用于保证同一时刻只有一个线程访问共享资源。 pthread_mutex_t 数据结构提供了互斥锁的实现，相关函数包括 pthread_mutex_init、pthread_mutex_lock、pthread_mutex_trylock、pthread_mutex_unlock 和 pthread_mutex_destroy
- 读写锁：Linux 中的读写锁也是通过 POSIX 线程库(pthread)实现的。读写锁允许多个线程同时进行读操作，但在进行写操作时，只允许一个线程访问共享资源。 pthread_rwlock_t 数据结构提供了读写锁的实现，相关函数包括 pthread_rwlock_init、pthread_rwlock_rdlock、pthread_rwlock_wrlock、pthread_rwlock_tryrdlock、pthread_rwlock_trywrlock、pthread_rwlock_unlock 和 pthread_rwlock_destroy
- 条件变量：条件变量用于实现线程间的同步。当一个线程需要等待某个条件满足时，它可以使用条件变量进入休眠状态，直到另一个线程更改共享资源并通知条件变量。条件变量通常与互斥锁一起使用。 pthread_cond_t 数据结构提供了条件变量的实现，相关函数包括 pthread_cond_init、pthread_cond_wait、pthread_cond_timedwait、pthread_cond_signal、pthread_cond_broadcast 和 pthread_cond_destroy
- 信号量：信号量是一种用于实现多线程和多进程同步的计数器。信号量用于限制对共享资源的访问数量。Linux 系统 提供了 System V 信号量和 POSIX 信号量两种实现。POSIX 信号量使用 sem_t 数据结构，相关函数包括 sem_init、sem_wait、sem_trywait、sem_post 和 sem_destroy。System V 信号量使用了一组系统调用(如 semget、semop 和 semctl)实现
信号量是如何实现的？¶
信号量(Semaphore)是一种同步原语，用于实现多线程和多进程之间的同步和互斥。信号量的本质是一个整数计数器，通常用于限制对共享资源的访问数量。信号量的实现涉及到两个关键操作： wait(或称为 P 操作，消耗) 和 post(或称为 V 操作，生产)。
基本实现原理¶
- 初始化：信号量在创建时需要进行初始化，通常将计数器设置为允许同时访问共享资源的最大数量
- P 操作：当一个线程或进程想要访问共享资源时，会执行 wait 操作。在 wait 操作中，信号量的计数器减 1。如果计数器的值为负数，表示没有可用的资源，执行 wait 操作的线程/进程将被阻塞，直到有资源可用
- V 操作：当一个线程或进程完成对共享资源的访问后，会执行 post 操作。在 post 操作中，信号量的计数器加 1。如果计数器的值小于等于 0，表示有等待的线程/进程，此时会唤醒一个被阻塞的线程/进程
信号量的实现依赖于底层操作系统原语，以保证 wait 和 post 操作的原子性。在 Linux 系统中，信号量有两种实现方式：System V 信号量和 POSIX 信号量。
- System V 信号量：System V 信号量使用一组 系统调用(如 semget、semop 和 semctl)实现。这些系统调用提供了原子性操作，以保证信号量的正确性。System V 信号量具有更强的跨进程特性，可以在不相关的进程之间使用
- POSIX 信号量：POSIX 信号量使用 sem_t 数据结构，并通过一组函数(如 sem_init、sem_wait、sem_trywait、sem_post 和 sem_destroy)提供信号量操作。POSIX 信号量在现代 Linux 系统中较为常用，因为它们具有较好的可移植性和性能
在实际使用中，信号量可以帮助程序员控制对共享资源的访问，防止竞争条件和实现同步。
条件变量是如何实现的？¶
条件变量(Condition Variable)是一种用于实现线程间同步的原语。条件变量允许线程等待某个条件的满足，当条件满足时，其他线程会通知等待的线程。条件变量通常与互斥锁(Mutex)一起使用，以保护共享资源的访问和同步。
- 初始化：条件变量在创建时需要进行初始化。在 Linux 中，使用 pthread_cond_t 数据结构表示条件变量，并通过 pthread_cond_init 函数进行初始化
-
等待条件：当一个线程需要等待某个条件满足时，它会执行以下操作：
- 线程获取互斥锁，保护共享资源的访问
- 线程检查条件是否满足。如果条件不满足，线程会调用 pthread_cond_wait 或 pthread_cond_timedwait 函数，将自己阻塞并等待条件变量的通知。在进入阻塞状态之前，pthread_cond_wait 函数会自动释放关联的互斥锁，以允许其他线程访问共享资源
- 当条件变量收到通知时，阻塞在条件变量上的线程会被唤醒。pthread_cond_wait 函数返回时，会自动重新获取关联的互斥锁
- 唤醒后，线程需要重新检查条件是否满足，因为可能存在虚假唤醒(Spurious Wakeup)的情况。如果条件满足，线程继续执行；否则，线程将继续等待条件变量的通知
-
通知条件：当另一个线程改变了共享资源，并使得条件满足时，它需要执行以下操作：
- 线程获取互斥锁，保护共享资源的访问
- 线程修改共享资源，使得条件满足
- 线程调用 pthread_cond_signal 或 pthread_cond_broadcast 函数，通知等待条件变量的一个或所有线程
- 线程释放互斥锁，允许其他线程访问共享资源
在 Linux 中，条件变量的实现依赖于底层操作系统原语，以保证线程间的同步和通知操作的原子性
生产者消费者问题？¶
生产者消费者问题是一个经典的并发问题，用于描述多线程或多进程间的同步和互斥问题。在生产者消费者问题中， 有一组生产者线程/进程和一组消费者线程/进程，它们共享一个有限容量的缓冲区。生产者负责将数据项放入缓冲区，消费者则从缓冲区中取出数据项进行处理。问题的核心在于如何实现对共享缓冲区的同步访问，确保数据不会丢失或被重复处理。
以下是生产者消费者问题的一些关键点：
- 同步：需要确保当缓冲区为空时，消费者不能从中取出数据；当缓冲区已满时，生产者不能向其中添加数据。这需要使用同步原语(如互斥锁、信号量或条件变量)来实现。
- 互斥：多个生产者和消费者线程/进程需要互斥地访问共享缓冲区，防止同时修改缓冲区导致的数据不一致问题。这通常使用互斥锁(Mutex)来实现。
- 缓冲区管理：需要实现一个适当的数据结构来存储缓冲区中的数据项，例如队列、栈或循环缓冲区。同时，需要考虑缓冲区的容量限制
哲学家进餐问题？¶
哲学家进餐问题用于描述多线程间的同步和互斥问题。问题设定为 有五位哲学家围坐在一个圆桌上，他们之间共享五根筷子。哲学家的生活包括两个行为：思考和进餐。当哲学家饿了，他们需要拿起左右两边的筷子才能开始进餐，进餐完毕后放下筷子继续思考。问题的关键在于如何设计一个并发算法，使得哲学家们能够同时进餐而不发生死锁或饿死的情况。
以下是哲学家进餐问题的一些解决方案：
- 顺序加锁：每个哲学家按照顺序先拿起左边的筷子，再拿起右边的筷子。这种方法可能导致死锁，因为每个哲学家都拿起了左边的筷子，却等不到右边的筷子
- 资源分级：为每根筷子分配一个优先级，每个哲学家总是先拿起优先级较高的筷子，再拿起优先级较低的筷子。这种方法可以避免死锁，因为至少有一个哲学家可以拿到两根筷子
- 限制同时进餐人数：限制同时进餐的哲学家数量，例如最多允许四位哲学家同时进餐。这种方法可以避免死锁，因为总是至少有一位哲学家能够拿到两根筷子
- 奇偶分组：将哲学家分为奇数和偶数两组，每组哲学家在不同的时间段尝试拿起筷子。例如，奇数哲学家先拿起左边的筷子，再拿起右边的筷子；偶数哲学家先拿起右边的筷子，再拿起左边的筷子。这种方法可以避免死锁，因为每个时间段内总是有一位哲学家能够拿到两根筷子
- 使用信号量或条件变量：可以使用信号量或条件变量来控制筷子的使用，确保在哲学家拿起两根筷子时不会发生死锁。例如，可以为每根筷子分配一个互斥锁，并使用条件变量来等待筷子的可用性