H2O 生成

标签: 多线程

难度: Medium

现在有两种线程，氧 oxygen 和氢 hydrogen，你的目标是组织这两种线程来产生水分子。

存在一个屏障（barrier）使得每个线程必须等候直到一个完整水分子能够被产生出来。

氢和氧线程会被分别给予 releaseHydrogen 和 releaseOxygen 方法来允许它们突破屏障。

这些线程应该三三成组突破屏障并能立即组合产生一个水分子。

你必须保证产生一个水分子所需线程的结合必须发生在下一个水分子产生之前。

换句话说:

如果一个氧线程到达屏障时没有氢线程到达，它必须等候直到两个氢线程到达。
如果一个氢线程到达屏障时没有其它线程到达，它必须等候直到一个氧线程和另一个氢线程到达。

书写满足这些限制条件的氢、氧线程同步代码。

示例 1:

输入: water = "HOH"
输出: "HHO"
解释: "HOH" 和 "OHH" 依然都是有效解。

示例 2:

输入: water = "OOHHHH"
输出: "HHOHHO"
解释: "HOHHHO", "OHHHHO", "HHOHOH", "HOHHOH", "OHHHOH", "HHOOHH", "HOHOHH" 和 "OHHOHH" 依然都是有效解。

提示：

3 * n == water.length
1 <= n <= 20
water[i] == 'O' or 'H'
输入字符串 water 中的 'H' 总数将会是 2 * n 。
输入字符串 water 中的 'O' 总数将会是 n 。

Submission

运行时间: 31 ms

内存: 16.4 MB

from threading import Semaphore, Lock

class H2O:
    def __init__(self):
        self.semaH = Semaphore(2)
        self.semaO = Semaphore(1)
        self.lock = Lock()
        pass

    def hydrogen(self, releaseHydrogen: 'Callable[[], None]') -> None:
        self.semaH.acquire()
        releaseHydrogen()
        self.lock.acquire()
        if self.semaH._value == 0 and self.semaO._value == 0:
            self.semaH.release()
            self.semaH.release()
            self.semaO.release()
        self.lock.release()

    def oxygen(self, releaseOxygen: 'Callable[[], None]') -> None:
        self.semaO.acquire()
        releaseOxygen()
        self.lock.acquire()
        if self.semaH._value == 0 and self.semaO._value == 0:
            self.semaH.release()
            self.semaH.release()
            self.semaO.release()
        self.lock.release()

Explain

本题解通过使用信号量（Semaphore）和互斥锁（Lock）来控制氢和氧线程的同步问题。初始化时，设定两个氢线程信号量（semaH）和一个氧线程信号量（semaO）。每个氢线程在执行前需要获取一个氢信号量，每个氧线程在执行前需要获取一个氧信号量。使用互斥锁确保在检查和重置信号量时不会有线程安全问题。当检测到两个氢信号量和一个氧信号量都被获取后，释放这些信号量，允许新的水分子生成的线程组合开始执行。

时间复杂度: O(1)

空间复杂度: O(1)

from threading import Semaphore, Lock

class H2O:
    def __init__(self):
        self.semaH = Semaphore(2)  # 氢原子的信号量，初始设置为2
        self.semaO = Semaphore(1)  # 氧原子的信号量，初始设置为1
        self.lock = Lock()  # 互斥锁，用于保护信号量的重置操作

    def hydrogen(self, releaseHydrogen: 'Callable[[], None]') -> None:
        self.semaH.acquire()  # 获取氢原子的信号量
        releaseHydrogen()  # 执行氢原子的放行操作
        self.lock.acquire()  # 获取锁进行状态检查和重置操作
        if self.semaH._value == 0 and self.semaO._value == 0:  # 检查是否两个氢信号量和一个氧信号量都已被获取
            self.semaH.release()  # 重置氢信号量
            self.semaH.release()  # 重置氢信号量
            self.semaO.release()  # 重置氧信号量
        self.lock.release()  # 释放锁

    def oxygen(self, releaseOxygen: 'Callable[[], None]') -> None:
        self.semaO.acquire()  # 获取氧原子的信号量
        releaseOxygen()  # 执行氧原子的放行操作
        self.lock.acquire()  # 获取锁进行状态检查和重置操作
        if self.semaH._value == 0 and self.semaO._value == 0:  # 检查是否两个氢信号量和一个氧信号量都已被获取
            self.semaH.release()  # 重置氢信号量
            self.semaH.release()  # 重置氢信号量
            self.semaO.release()  # 重置氧信号量
        self.lock.release()  # 释放锁

Explore

在这个题解中，使用了信号量来控制线程的执行。每次成功生成一个水分子（H2O），程序会重置两个氢信号量和一个氧信号量，以允许新的线程组合进行水分子的生成。若氢线程和氧线程的数量不匹配，例如氢线程过多，氢线程会因为氧信号量不足而阻塞，这是预期行为，不会导致死锁，因为随着氧线程的到达和执行，阻塞的氢线程能够继续执行。系统设计应确保氧线程最终到达，以避免长时间阻塞。

锁的使用是为了保护检查信号量状态和重置操作的线程安全。若没有及时加锁，确实可能引发竞态条件。例如，如果两个氢线程和一个氧线程几乎同时到达并尝试执行检查，可能会有多于预期的线程同时认为信号量已经满足条件。因此，锁应该在检查信号量之前就获得，以确保在修改信号量状态之前不会有其他线程干扰。

确实存在这样的风险。如果在信号量重置前新的线程到达，并尝试获取信号量，可能会导致信号量状态不正确，从而影响线程同步。理想的解决方案是在重置操作完成前，确保没有新的线程可以获取信号量，或者设计一种机制确保即使新线程到达，也不会在重置期间改变信号量状态。

信号量是一种简单而有效的线程同步机制，尤其适用于控制对共享资源的访问数量。在本题中，使用信号量可以直接限制可生成水分子的线程数量，符合题目需求的特定比例（2:1）。相比之下，条件变量可能需要更复杂的逻辑来保证线程唤醒和阻塞的正确性，而屏障通常用于等待所有线程到达一个点，不太适用于需要不同数量线程合作的场景。信号量提供了一种更直接、符合题目需求的同步方法。