并发

jjd枫长...大约 18 分钟

并发与并行的区别？

并发（Concurrency）

并发是指一个时间段内同时处理多个任务的能力。它强调的是任务之间的独立性，以及它们是如何在一个处理器或单个核心上交替执行的。并发的目标是在有限的资源下实现任务之间的有效调度，从而最大限度地提高系统的响应事件。并发并不意味着任务在同一时刻被执行，而是指它们在同一时间段内得到处理。

并行（Parallelism）

并行是指在同一时刻执行多个任务的能力。它要求系统具备多个处理器或多个计算核心，这样就可以同时处理多个任务。并行的目标是加速任务的完成速度，通过将任务分解为更小的部分并在多个处理器或核心上同时执行，以实现更快的任务执行速度。

区别

并发关注在一个时间段内处理多个任务，而并行关注在同一时刻执行多个任务。
并发适用于单处理器或单核心系统，通过任务调度实现多任务处理；并行则依赖于多处理器或多核心系统来实现任务的同时执行。
并发主要用于提高系统的响应速度和吞吐量，而并行则旨在加速任务的完成速度。

什么是互斥锁，自旋锁呢，底层是怎么实现的？

互斥锁（Mutex）和自旋锁（Spinlock）是两种用于同步和保护共享资源的锁机制，它们都可以防止多个线程或进程同时访问共享资源，从而避免竞态条件（Race Condition）和数据不一致等问题。

互斥锁（Mutex）：互斥锁是一种用于实现线程或进程间同步的机制。当一个线程获得互斥锁并访问共享资源时，其他试图获得该锁的线程将被阻塞，直到锁被释放。互斥锁可以保证同一时刻只有一个线程能够访问共享资源。互斥锁的底层实现通常依赖于操作系统的原语，例如在Linux系统中使用pthread库的pthread_mutex_t数据结构来实现互斥锁。

自旋锁（Spinlock）：自旋锁是一种低级的同步原语，通常用于多处理器或多核系统中。与互斥锁不同，当一个线程尝试获得自旋锁时，如果锁已经被其他线程持有，它将不断循环（“自旋”）检查锁是否可用，而不是进入阻塞状态。自旋锁适用于锁持有时间较短且线程不希望在等待锁时进入睡眠状态的场景。自旋锁的底层实现通常依赖于原子操作和CPU指令，如测试和设置（test-and-set）或比较和交换（compare-and-swap）等。

互斥锁和自旋锁的主要区别在于它们在等待锁时的行为：

当线程尝试获得已被占用的互斥锁时，它会进入阻塞状态，让出CPU资源，等待锁被释放。
当线程尝试获得已被占用的自旋锁时，它会不断循环检查锁是否可用，而不会让出CPU资源。

讲一讲死锁，死锁怎么处理？

死锁是指在多线程或多进程环境中，一组或多组线程/进程互相等待彼此持有的资源，导致这些线程/进程无法继续执行的情况。当死锁发生时，受影响的线程/进程无法完成任务，系统性能和吞吐量可能会受到严重影响。

死锁条件

互斥条件（Mutual Exclusion）：一个资源在同一时间只能被一个线程或进程占用。
占有且等待条件（Hold and Wait）：一个线程或进程在持有至少一个资源的同时，仍然尝试获取其他线程或进程所持有的资源。
不可抢占条件（No Preemption）：资源不能被强行从一个线程或进程中抢占，只能由占有它的线程或进程主动释放。
循环等待条件（Circular Wait）：存在一个线程/进程等待序列，其中每个线程/进程都在等待下一个线程/进程所持有的资源。

处理死锁

分为预防、避免和检测恢复三种策略：

预防死锁：预防死锁的方法是破坏死锁产生的四个条件中的一个或多个。例如：

破坏占有且等待条件：要求线程/进程在请求资源之前释放所有已经持有的资源，或者一次性请求所有需要的资源。
破坏循环等待条件：为所有资源分配一个全局的顺序，并要求线程/进程按照这个顺序请求资源。

避免死锁：避免死锁的方法是在运行时动态地检查资源分配情况，以确保系统不会进入不安全状态。银行家算法是一种著名的避免死锁的算法，通过模拟资源分配过程来判断是否会产生死锁，如果会产生死锁，则拒绝分配资源。

检测和恢复死锁：检测和恢复死锁的方法是允许系统进入死锁状态，然后定期检测死锁，并在发现死锁后采取措施解决。常见的检测方法包括资源分配图（Resource Allocation Graph）和检测算法。恢复死锁的方法通常包括以下几种：

终止线程/进程：强制终止一个或多个死锁中的线程/进程，从而释放其持有的资源。这种方法可能会导致数据丢失或不一致，因此需要谨慎使用。
回滚线程/进程：将死锁中的线程/进程回滚到之前的某个状态，然后重新执行。这种方法需要系统支持事务和恢复功能，并且可能会影响系统性能。
动态资源分配：在检测到死锁后，尝试动态地分配资源，以解除死锁。例如，可以向系统请求更多资源，或者在不影响整体性能的情况下调整资源分配策略。
等待和重试：在某些情况下，可以让死锁中的线程/进程等待一段时间，以便其他线程/进程释放资源。等待一段时间后，重新尝试请求资源。这种方法可能会导致线程/进程长时间处于等待状态，从而影响系统性能。

什么是读写锁？

读写锁（Read-Write Lock）是一种用于同步访问共享资源的锁机制，适用于读操作远多于写操作的场景。与互斥锁（Mutex）不同，读写锁允许多个线程同时进行读操作，但在进行写操作时，只允许一个线程访问共享资源。这种锁机制可以提高多线程程序的性能，因为它允许多个线程在不互相干扰的情况下进行并发读操作。

读写锁具有以下特性：

共享读：多个线程可以同时获得读锁，共享读取共享资源。这意味着在没有写操作的情况下，读操作不会被阻塞。
独占写：当一个线程获得写锁时，其他线程无法获得读锁或写锁。这可以确保在写操作期间，共享资源不会被其他线程修改或访问。
优先级：实现读写锁时，可能需要处理读写操作之间的优先级。根据实现方式的不同，读写锁可能会更倾向于优先处理读操作，或者在某些情况下，优先处理写操作。这可能会导致写饥饿或读饥饿的问题，需要根据实际场景进行权衡。

读写锁在实现时通常依赖于底层的操作系统原语。例如，在Linux系统中，可以使用pthread库中的pthread_rwlock_t数据结构来实现读写锁。

总之，读写锁是一种适用于读操作远多于写操作场景的同步机制。通过允许多个线程同时进行读操作，读写锁可以提高多线程程序在访问共享资源时的性能。然而，根据实现方式的不同，读写锁可能需要处理读写操作之间的优先级问题。

Linux同步机制？

Linux系统提供了多种同步机制，以便在多线程或多进程环境中实现对共享资源的安全访问。常见同步机制如下：

互斥锁（Mutex）： Linux中的互斥锁是通过POSIX线程库（pthread）实现的。互斥锁（Mutex）用于保证同一时刻只有一个线程访问共享资源。pthread_mutex_t数据结构提供了互斥锁的实现，相关函数包括pthread_mutex_init、pthread_mutex_lock、pthread_mutex_trylock、pthread_mutex_unlock和pthread_mutex_destroy。

读写锁（Read-Write Lock）： 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。

条件变量（Condition Variables）：条件变量用于实现线程间的同步。当一个线程需要等待某个条件满足时，它可以使用条件变量进入休眠状态，直到另一个线程更改共享资源并通知条件变量。条件变量通常与互斥锁一起使用。pthread_cond_t数据结构提供了条件变量的实现，相关函数包括pthread_cond_init、pthread_cond_wait、pthread_cond_timedwait、pthread_cond_signal、pthread_cond_broadcast和pthread_cond_destroy。

信号量（Semaphore）：信号量是一种用于实现多线程和多进程同步的计数器。信号量用于限制对共享资源的访问数量。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操作）。

基本实现原理

初始化：信号量在创建时需要进行初始化，通常将计数器设置为允许同时访问共享资源的最大数量。
Wait（P）操作：当一个线程或进程想要访问共享资源时，会执行wait操作。在wait操作中，信号量的计数器减1。如果计数器的值为负数，表示没有可用的资源，执行wait操作的线程/进程将被阻塞，直到有资源可用。
Post（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）来实现。
缓冲区管理：需要实现一个适当的数据结构来存储缓冲区中的数据项，例如队列、栈或循环缓冲区。同时，需要考虑缓冲区的容量限制。

解决生产者消费者问题的常用方法是使用信号量和互斥锁。以下是一种典型的解决方案：

初始化两个信号量：一个表示空闲缓冲区的数量（初始值为缓冲区的最大容量），另一个表示已使用的缓冲区数量（初始值为0）。
初始化一个互斥锁，用于保护对共享缓冲区的访问。
生产者在生产数据时：
a. 执行wait操作，等待空闲缓冲区信号量。
b. 获取互斥锁，保护共享缓冲区的访问。
c. 将数据项放入缓冲区。 d. 释放互斥锁。
e. 执行post操作，增加已使用缓冲区信号量。
消费者在消费数据时：
a. 执行wait操作，等待已使用缓冲区信号量。
b. 获取互斥锁，保护共享缓冲区的访问。
c. 从缓冲区中取出数据项。
d. 释放互斥锁。
e. 执行post操作，增加空闲缓冲区信号量。

通过这种方法，生产者和消费者可以实现对共享缓冲区的同步和互斥访问，从而解决生产者消费者问题。

另一种常见的解决方案是使用条件变量和互斥锁：

初始化一个互斥锁，用于保护对共享缓冲区的访问。
初始化两个条件变量：一个表示缓冲区非空（可以供消费者取出数据），另一个表示缓冲区非满（可以供生产者放入数据）。
生产者在生产数据时：
a. 获取互斥锁，保护共享缓冲区的访问。
b. 当缓冲区已满时，等待缓冲区非满的条件变量。
c. 将数据项放入缓冲区。
d. 通知缓冲区非空的条件变量，表示有数据可供消费者取出。
e. 释放互斥锁。
消费者在消费数据时：
a. 获取互斥锁，保护共享缓冲区的访问。
b. 当缓冲区为空时，等待缓冲区非空的条件变量。
c. 从缓冲区中取出数据项。
d. 通知缓冲区非满的条件变量，表示有空间可供生产者放入数据。
e. 释放互斥锁。

使用条件变量的方案更直接地表达了生产者和消费者之间的同步关系，且在某些情况下可能比使用信号量的方案具有更好的性能。

哲学家进餐问题？

哲学家进餐问题用于描述多线程间的同步和互斥问题。问题设定为有五位哲学家围坐在一个圆桌上，他们之间共享五根筷子。哲学家的生活包括两个行为：思考和进餐。当哲学家饿了，他们需要拿起左右两边的筷子才能开始进餐，进餐完毕后放下筷子继续思考。问题的关键在于如何设计一个并发算法，使得哲学家们能够同时进餐而不发生死锁或饿死的情况。

以下是哲学家进餐问题的一些解决方案：

顺序加锁：每个哲学家按照顺序先拿起左边的筷子，再拿起右边的筷子。这种方法可能导致死锁，因为每个哲学家都拿起了左边的筷子，却等不到右边的筷子。
资源分级：为每根筷子分配一个优先级，每个哲学家总是先拿起优先级较高的筷子，再拿起优先级较低的筷子。这种方法可以避免死锁，因为至少有一个哲学家可以拿到两根筷子。
限制同时进餐人数：限制同时进餐的哲学家数量，例如最多允许四位哲学家同时进餐。这种方法可以避免死锁，因为总是至少有一位哲学家能够拿到两根筷子。
奇偶分组：将哲学家分为奇数和偶数两组，每组哲学家在不同的时间段尝试拿起筷子。例如，奇数哲学家先拿起左边的筷子，再拿起右边的筷子；偶数哲学家先拿起右边的筷子，再拿起左边的筷子。这种方法可以避免死锁，因为每个时间段内总是有一位哲学家能够拿到两根筷子。
使用信号量或条件变量：可以使用信号量或条件变量来控制筷子的使用，确保在哲学家拿起两根筷子时不会发生死锁。例如，可以为每根筷子分配一个互斥锁，并使用条件变量来等待筷子的可用性。

哲学家进餐问题提供了一个很好的模型，用于研究并发编程中的死锁、饥饿和同步问题。实际上，哲学家进餐问题可以推广到更广泛的多线程或多进程同步问题，特别是涉及到多个共享资源的情况。

上述解决方案可以避免死锁，但并不一定能完全解决饥饿问题。例如，当某些哲学家持续拿不到筷子时，他们可能饿死。要解决饥饿问题，可以采用公平调度策略，例如轮询或优先级调度。此外，可以使用其他同步原语，如读写锁或监视器，来进一步优化解决方案。