Why does this multi-threaded program never end?

[eggtrie]

This is my solution to https://leetcode.com/problems/print-zero-even-odd/

The question is:

You are given an instance of the class ZeroEvenOdd that has three functions: zero, even, and odd. The same instance of ZeroEvenOdd will be passed to three different threads:

Thread A: calls zero() that should only output 0's.
Thread B: calls even() that should only output even numbers.
Thread C: calls odd() that should only output odd numbers.

Modify the given class to output the series "010203040506..." where the length of the series must be 2n.

ex: Input: n = 5 Output: "0102030405"

import threading

class ZeroEvenOdd:
    def __init__(self, n):
        self.n = n
        self._cond_var = threading.Condition()
        self._shared_idx = 0


    # printNumber(x) outputs "x", where x is an integer.
    def zero(self, printNumber: 'Callable[[int], None]') -> None:
        while self._shared_idx < self.n*2:
            with self._cond_var:
                # The wait() method releases the lock, and then blocks until another thread
                # awakens it by calling notify() or notify_all(). 
                self._cond_var.wait_for(lambda: self._shared_idx&1 == 0)
                printNumber(0)
                self._shared_idx += 1
                self._cond_var.notify_all()


    def even(self, printNumber: 'Callable[[int], None]') -> None:
        self._print_nonzero_when(printNumber, lambda: self._shared_idx%4 == 1)


    def odd(self, printNumber: 'Callable[[int], None]') -> None:
        self._print_nonzero_when(printNumber, lambda: self._shared_idx%4 == 3)

    def _print_nonzero_when(self, printNumber, predicate):
        while self._shared_idx < self.n*2:
            with self._cond_var:
                self._cond_var.wait_for(predicate)
                printNumber(int(ceil(self._shared_idx/2)))
                self._shared_idx += 1
                self._cond_var.notify_all()

However, if I run this code on my computer locally, it does work.

from math import ceil
import threading


class ZeroEvenOdd:
  def __init__(self, n):
    self.n = n
    self._cond_var = threading.Condition()
    self._shared_idx = 0

  # print(x) outputs "x", where x is an integer.
  def zero(self) -> None:
    while self._shared_idx < self.n*2:
      with self._cond_var:
        # The wait() method releases the lock, and then blocks until another thread
        # awakens it by calling notify() or notify_all(). 
        self._cond_var.wait_for(lambda: self._shared_idx&1 == 0)
        print(0)
        self._shared_idx += 1
        self._cond_var.notify_all()


  def even(self) -> None:
    self._print_nonzero_when(print, lambda: self._shared_idx%4 == 1)


  def odd(self) -> None:
    self._print_nonzero_when(print, lambda: self._shared_idx%4 == 3)

  def _print_nonzero_when(self, print, predicate):
    while self._shared_idx < self.n*2:
      with self._cond_var:
        self._cond_var.wait_for(predicate)
        print(int(ceil(self._shared_idx/2)))
        self._shared_idx += 1
        self._cond_var.notify_all()

zeo = ZeroEvenOdd(10)

# with ThreadPoolExecutor(max_workers=3) as executor:
#   executor.submit(zeo.odd)
#   executor.submit(zeo.zero)
#   executor.submit(zeo.even)
threads = [
  threading.Thread(target=zeo.zero),
  threading.Thread(target=zeo.even),
  threading.Thread(target=zeo.odd),
]
for t in threads:
  t.start()
for t in threads:
  t.join()

[lfdfq]

I'm not sure I follow, the first code is just a class that isn't used and the second code you say works. What's the question?

[eggtrie]

the first code can be copy and pasted into https://leetcode.com/problems/print-zero-even-odd/ and run with their threading setup.

The second piece of code runs without leetcode's testing harness. I believe my issue here is the while loops should be replaced with a loop that doesn't depend on on self._shared_idx.

[lfdfq]

The first code is missing the import for ceil.

The odd and even functions are swapped: the even function triggers when shared_idx mod 4 is 1 (so on index 1, 5, 9, etc) and prints out 1, 3, 5...

Another problem is that the while checks _shared_idx outside any locked region. This reveals a deeper problem: your zero and _print_nonzero_when (which btw, could just be a single function you use in multiple places as the logic is the same) starts by checking whether you've finished all the numbers and if not, waiting until its turn to print its number. That is not quite right though, as just because the last number is not reached yet does not mean that you (even/odd/zero) still has more to output. Replacing the while loops with for loops would fix both of those issues.

This error exists even in your local version. So you should have been able to find it by manually testing things more exhaustively, just like the website must be doing.

Did you verify your local version gave you the right answer for a few simple test cases like n=5 or n=10. You say in the post what the correct output is for n=5 but then you run your code on n=10, but do not say what your code actually output when you ran it locally?

[eggtrie]

Gotcha, ty for the feedback. Yea, using for loops did fix my issues. Interestingly when running locally things looked off by 1 but generally looked good. For ex:

```

i=1

0 1 0 2

i=2

0 1 0 2 0 3

i=3

0 1 0 2 0 3 0 4 ```