交替打印 FooBar

难度: Medium

给你一个类：

class FooBar {
  public void foo() {
    for (int i = 0; i < n; i++) {
      print("foo");
    }
  }

  public void bar() {
    for (int i = 0; i < n; i++) {
      print("bar");
    }
  }
}

两个不同的线程将会共用一个 FooBar 实例：

线程 A 将会调用 foo() 方法，而
线程 B 将会调用 bar() 方法

请设计修改程序，以确保 "foobar" 被输出 n 次。

示例 1：

输入：n = 1
输出："foobar"
解释：这里有两个线程被异步启动。其中一个调用 foo() 方法, 另一个调用 bar() 方法，"foobar" 将被输出一次。

示例 2：

输入：n = 2
输出："foobarfoobar"
解释："foobar" 将被输出两次。

提示：

1 <= n <= 1000

Submission

运行时间: 36 ms

内存: 17.0 MB

import threading

class FooBar:
    def __init__(self, n):
        self.n = n
        self.fooLock = threading.Lock()
        self.barLock = threading.Lock()
        self.fooLock.acquire()


    def foo(self, printFoo: 'Callable[[], None]') -> None:
        
        for i in range(self.n):
            # with self.barLock: None
            self.barLock.acquire()

            # printFoo() outputs "foo". Do not change or remove this line.
            printFoo()

            self.fooLock.release()

    def bar(self, printBar: 'Callable[[], None]') -> None:
        
        for i in range(self.n):
            # with self.fooLock: None
            self.fooLock.acquire()

            # printBar() outputs "bar". Do not change or remove this line.
            printBar()

            self.barLock.release()

Explain

该题解采用了线程同步的方法来保证'foo'和'bar'按顺序交替打印。具体地，使用了两个互斥锁(fooLock和barLock)来控制打印的顺序。在初始化时，fooLock被锁定，而barLock是打开的。这样一来，在foo线程开始时，它会因为fooLock被锁定而等待，直到bar线程释放fooLock。同样，bar线程会因为barLock被锁定而等待，直到foo线程释放barLock。这样就实现了foo和bar的交替打印。

时间复杂度: O(n)

空间复杂度: O(1)

import threading

class FooBar:
    def __init__(self, n):
        self.n = n
        self.fooLock = threading.Lock()
        self.barLock = threading.Lock()
        self.fooLock.acquire()


    def foo(self, printFoo: 'Callable[[], None]') -> None:
        
        for i in range(self.n):
            self.barLock.acquire()
            printFoo()
            self.fooLock.release()

    def bar(self, printBar: 'Callable[[], None]') -> None:
        
        for i in range(self.n):
            self.fooLock.acquire()
            printBar()
            self.barLock.release()

Explore

在初始化时先锁定fooLock而不是barLock是为了确保'foo'首先打印。该程序设计要求'foo'和'bar'交替打印，从'foo'开始。因此，通过先锁定fooLock，初始化时保证了foo线程在开始打印前必须等待bar线程释放fooLock，而bar线程在开始时会检查fooLock是否释放，从而阻止bar线程先于foo线程运行。这确保了打印顺序始终以'foo'开头。

在这个特定的解决方案中，死锁的风险被有效地避免了，因为锁的获取和释放是以严格交替的方式进行的。具体来说，foo线程和bar线程各自持有一个锁，并且只在对方线程释放其锁之后才尝试获取锁。这种交替方式（foo获取fooLock后释放barLock，bar获取barLock后释放fooLock）避免了循环等待条件，这是死锁的必要条件之一。因此，只要遵循这种严格的顺序，就不会发生死锁。

互斥锁在这种情况下是简单且有效的选择，因为它们提供了一种易于理解和实现的方式来保证两个线程之间的严格交替执行。虽然信号量和条件变量也可以用于线程同步，但互斥锁在这个问题的上下文中提供了直接的控制和较少的开销。使用互斥锁可以直接控制线程的执行顺序，而信号量或条件变量通常用于更复杂的同步场景，如控制对一组资源的访问或当多个条件需要同时满足时。

在foo和bar方法中，锁的获取与释放顺序对程序的正确性至关重要。如果更改了获取或释放锁的顺序，可能会导致程序无法按预期工作，比如打印顺序错误或发生死锁。在当前实现中，foo方法先获取barLock，完成打印后释放fooLock；bar方法先获取fooLock，完成打印后释放barLock。这种顺序保证了每个线程在执行打印操作后会释放另一个线程需要的锁，从而使得打印操作能够交替进行。如果更改顺序，例如foo方法释放barLock之前尝试获取fooLock，将造成死锁，因为它们都在等待对方释放锁。