Concurrency

死锁 (Deadlocks) deadlocks (死锁) 所谓死锁 (Deadlock): 是指两个或两个以上的进程在执行过程中,因争夺资源而造成的一种互相等待的现象,若无外力作用,它们都将无法推进下去.此时称系统处于死锁状态或系统产生了死锁,这些永远在互相等待的进程称为死锁进程. 由于资源占用是互斥的，当某个进程提出申请资源后，使得有关进程在无外力协助下，永远分配不到必需的资源而无法继续运行，这就产生了一种特殊现象死锁。 一种情形，此时执行程序中两个或多个线程发生永久堵塞 (等待) ，每个线程都在等待被其他线程占用并堵塞了的资源。例如，如果线程A锁住了记录1并等待记录2，而线程B锁住了记录2并等待记录1，这样两个线程就发生了死锁现象。 计算机系统中,如果系统的资源分配策略不当，更常见的可能是程序员写的程序有错误等，则会导致进程因竞争资源不当而产生死锁的现象。 产生死锁的原因主要是: (1) 因为系统资源不足。 (2) 进程运行推进的顺序不合适。 (3) 资源分配不当等。 如果系统资源充足，进程的资源请求都能够得到满足，死锁出现的可能性就很低，否则 就会因争夺有限的资源而陷入死锁。其次，进程运行推进顺序与速度不同，也可能产生死锁。 产生死锁的四个必要条件: (1) 互斥条件: 一个资源每次只能被一个进程使用。 (2) 请求与保持条件: 一个进程因请求资源而阻塞时，对已获得的资源保持不放。 (3) 不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。 (4) 循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。 这四个条件是死锁的必要条件，只要系统发生死锁，这些条件必然成立，而只要上述条件之 一不满足，就不会发生死锁。 死锁的解除与预防: 理解了死锁的原因，尤其是产生死锁的四个必要条件，就可以最大可能地避免、预防和 解除死锁。所以，在系统设计、进程调度等方面注意如何不让这四个必要条件成立，如何确 定资源的合理分配算法，避免进程永久占据系统资源。此外，也要防止进程在处于等待状态 的情况下占用资源,在系统运行过程中，对进程发出的每一个系统能够满足的资源申请进行动态检查，并根据检查结果决定是否分配资源，若分配后系统可能发生死锁，则不予分配，否则予以分配 。因此，对资源的分配要给予合理的规划。 维护记录 时间 修改内容 原因 2026-10-09 修复本地 Hugo 构建的 Raw HTML 警告：代码/配置放入代码块，正文中的尖括号占位符改为行内代码；文件重命名为 deadlocks.md；url 改为 deadlocks；旧 url 加入 aliases；categories 改为 CS 正文中的 HTML/XML 片段被当作原始 HTML 丢弃；文件名/URL/标题按规范调整

信号量 Semaphore 信号量是 Edsger Dijkstra 发明的数据结构，在解决多种同步问题时很有用。其本质是一个整数，并关联两个操作： 申请 acquire（也称为 wait、decrement 或 P 操作） 释放 release（也称 signal、increment 或 V 操作） acquire操作将信号量减 1，如果结果值为负则线程阻塞，且直到其他线程进行了信号量累加为正数才能恢复。如结果为正数，线程则继续执行。 release操作将信号量加 1，如存在被阻塞的线程，此时他们中的一个线程将解除阻塞。 Go 运行时提供的 runtime_SemacquireMutex 和runtime_Semrelease 函数可用来实现sync.RWMutex互斥锁。 semaphore/信号量, mutex/互斥锁 Mutex 是一把钥匙，一个人拿了就可进入一个房间，出来的时候把钥匙交给队列的第一个。一般的用法是用于串行化对 critical section 代码的访问，保证这段代码不会被并行的运行。 Semaphore/信号量 是一件可以容纳 N 人的房间，如果人不满就可以进去，如果人满了, 就要等待有人出来. 对于N=1的情况，称为binary semaphore。一般的用法是，用于限制对于某一资源的同时访问。 Binary semaphore 与 Mutex 的差异 在 有的系统中 Binary semaphore 与 Mutex 是没有差异的。在有的系统上，主要的差异是mutex一定要由获得锁的进程来释放。而semaphore可以由其它进程释放 (这时的semaphore实际就是个原子的变量，大家可以加或减) ，因此semaphore可以用于进程间同步。Semaphore的同步功能是所有系统都支持的，而Mutex能否由其他进程释放则未定，因此建议mutex只用于保护critical section。而semaphore则用于保护某变量，或者同步。 关于semaphore和mutex的区别，网上有著名的厕所理论 (http://koti.mbnet.fi/niclasw/MutexSemaphore.html) : Mutex Mutex 的发音是 /mjuteks/ ，其含义为互斥(体)，这个词是Mutual Exclude的缩写。 Is a key to a toilet. One person can have the key - occupy the toilet - at the time. When finished, the person gives (frees) the key to the next person in the queue. Officially: “Mutexes are typically used to serialise access to a section of re-entrant code that cannot be executed concurrently by more than one thread. A mutex object only allows one thread into a controlled section, forcing other threads which attempt to gain access to that section to wait until the first thread has exited from that section.” ...

race condition 数据争用 (data race) 和竞态条件 (race condition) 在有关多线程编程的话题中，数据争用 (data race) 和竞态条件 (race condition) 是两个经常被提及的名词，它们两个有着相似的名字，也是我们在并行编程中极力避免出现的。但在处理实际问题时，我们应该能明确区分它们两个。 数据争用 (data race) 定义: 多个线程对于同一个变量、同时地、进行读/写操作的现象并且至少有一个线程进行写操作。 (也就是说，如果所有线程都是只进行读操作，那么将不构成数据争用) 后果: 如果发生了数据争用，读取该变量时得到的值将变得不可知，使得该多线程程序的运行结果将完全不可预测，可能直接崩溃。 如何防止: 对于有可能被多个线程同时访问的变量使用排他访问控制，具体方法包括使用mutex (互斥量) 和monitor (监视器) ，或者使用atomic变量。 竞态条件 (race condition) 竞态条件(race conditions)，多个线程以非一致性的顺序同时访问数据资源 相对于数据争用，竞态条件(race condition) 指的是更加高层次的更加复杂的现象，一般需要在设计并行程序时进行细致入微的分析，才能确定。 (也就是隐藏得更深) 定义: 受各线程上代码执行的顺序和时机的影响，程序的运行结果产生 (预料之外) 的变化。 后果: 如果存在竞态条件(race condition)，多次运行程序对于同一个输入将会有不同的结果，但结果并非完全不可预测，它将由输入数据和各线程的执行顺序共同决定。 如何预防: 竞态条件产生的原因很多是对于同一个资源的一系列连续操作并不是原子性的，也就是说有可能在执行的中途被其他线程抢占，同时这个“其他线程”刚好也要访问这个资源。解决方法通常是: 将这一系列操作作为一个 critical section (临界区) 。 代码示例 下面以C++实现的一个银行存款转账操作为例，说明数据争用(data race) 和竞态条件(race condition)的区别。 该系统的不変性条件: 存款余额≥0，不允许借款。 3.1.数据争用的例子 int my_account = 0; //我的账户余额 int your_account = 100; //你的账户余额 // 转账操作: 存在数据争用(data race)！ bool racy_transfer(int& src, int& dst, int m) { if (m <= src) { //操作结果不可预测 src -= m; //操作结果不可预测 dst += m; //操作结果不可预测 return true; } else { return false; } } // 将下面两个函数在两个线程分别运行 racy_transfer(your_account, my_account, 50); racy_transfer(your_account, my_account, 80); 运行上面的的代码后，不光我们双方账号的余额不可预测，甚至整个系统会发生什么事情都无法保证。 ...