leetcode
leetcode 1001 ~ 1050
H2O 生成

H2O 生成

难度:

标签:

题目描述

代码结果

运行时间: 31 ms, 内存: 16.4 MB


/*
 * 思路:
 * 1. 使用流式 API 实现线程同步。创建两个流分别处理氢和氧的释放。
 * 2. 使用两个流控制每个原子对应的释放方法(releaseHydrogen 和 releaseOxygen)。
 * 3. 使用 Collectors.partitioningBy 进行分组,保证每次三个原子成组处理。
 */

import java.util.concurrent.Semaphore;
import java.util.stream.IntStream;

public class H2OStream {
    private Semaphore hydrogenSemaphore;
    private Semaphore oxygenSemaphore;
    private Semaphore barrier;

    public H2OStream() {
        hydrogenSemaphore = new Semaphore(2);
        oxygenSemaphore = new Semaphore(1);
        barrier = new Semaphore(0);
    }

    public void releaseHydrogen(Runnable releaseHydrogen) throws InterruptedException {
        hydrogenSemaphore.acquire();
        barrier.release();
        releaseHydrogen.run();
        if (barrier.availablePermits() == 3) {
            barrier.acquire(3);
            hydrogenSemaphore.release(2);
            oxygenSemaphore.release(1);
        }
    }

    public void releaseOxygen(Runnable releaseOxygen) throws InterruptedException {
        oxygenSemaphore.acquire();
        barrier.release();
        releaseOxygen.run();
        if (barrier.availablePermits() == 3) {
            barrier.acquire(3);
            hydrogenSemaphore.release(2);
            oxygenSemaphore.release(1);
        }
    }

    public void releaseWater(String water) {
        water.chars().forEach(ch -> {
            if (ch == 'H') {
                try {
                    releaseHydrogen(() -> System.out.print("H"));
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            } else if (ch == 'O') {
                try {
                    releaseOxygen(() -> System.out.print("O"));
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        });
    }
}

解释

方法:

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

时间复杂度:

O(1)

空间复杂度:

O(1)

代码细节讲解

🦆
如何确保在氢线程和氧线程的数量不匹配的情况下,程序不会导致死锁?
在这个题解中,使用了信号量来控制线程的执行。每次成功生成一个水分子(H2O),程序会重置两个氢信号量和一个氧信号量,以允许新的线程组合进行水分子的生成。若氢线程和氧线程的数量不匹配,例如氢线程过多,氢线程会因为氧信号量不足而阻塞,这是预期行为,不会导致死锁,因为随着氧线程的到达和执行,阻塞的氢线程能够继续执行。系统设计应确保氧线程最终到达,以避免长时间阻塞。
🦆
在题解中,锁的使用是在检查信号量值之后,这是否可能导致在多线程环境下出现竞态条件?
锁的使用是为了保护检查信号量状态和重置操作的线程安全。若没有及时加锁,确实可能引发竞态条件。例如,如果两个氢线程和一个氧线程几乎同时到达并尝试执行检查,可能会有多于预期的线程同时认为信号量已经满足条件。因此,锁应该在检查信号量之前就获得,以确保在修改信号量状态之前不会有其他线程干扰。
🦆
题解中提到,若氢和氧的信号量都被完全获取,则进行重置,但如果在重置前有新的线程到达呢?这样的处理逻辑是否可能导致线程同步问题?
确实存在这样的风险。如果在信号量重置前新的线程到达,并尝试获取信号量,可能会导致信号量状态不正确,从而影响线程同步。理想的解决方案是在重置操作完成前,确保没有新的线程可以获取信号量,或者设计一种机制确保即使新线程到达,也不会在重置期间改变信号量状态。
🦆
为什么选择使用信号量来控制线程同步,而不是使用其他同步机制,例如条件变量或者屏障?
信号量是一种简单而有效的线程同步机制,尤其适用于控制对共享资源的访问数量。在本题中,使用信号量可以直接限制可生成水分子的线程数量,符合题目需求的特定比例(2:1)。相比之下,条件变量可能需要更复杂的逻辑来保证线程唤醒和阻塞的正确性,而屏障通常用于等待所有线程到达一个点,不太适用于需要不同数量线程合作的场景。信号量提供了一种更直接、符合题目需求的同步方法。

相关问题