python – Exclusive queue: disadvantages of my solution

Question:

In The Little Book of Semaphores, the author discusses a problem called the Exclusive queue: you need to write a multithreaded program without active waiting, using semaphores, which emulates the behavior of dancers. There are two types of dancers – the leader and the follower, who must dance in pairs, that is, the leader must wait until the follower appears and vice versa. Each dancer corresponds to a flow, a dance corresponds to a call to the dance() function. Author's solution:

leaders = followers = 0
mutex = Semaphore(1)
leaderQueue = Semaphore(0)
followerQueue = Semaphore(0)
rendezvous = Semaphore(0)

def leader_thread():
   mutex.wait()
   if followers > 0:
      followers--
      followerQueue.signal()
   else:
      leaders++
      mutex.signal()
      leaderQueue.wait()

   dance()
   rendezvous.wait()
   mutex.signal()

def follower_thread():
   mutex.wait()
   if leaders > 0:
      leaders--
      leaderQueue.signal()
   else:
      followers++
      mutex.signal()
      followerQueue.wait()

   dance()
   rendezvous.signal()

The wait and signal operations in other implementations may be called P and V , acquire and release .

There is a much simpler solution in my opinion:

leader_mutex=Semaphore(1)
follower_mutex=Semaphore(1)
leader_rendezvous=Semaphore(0)
follower_rendezvous=Semaphore(0)

def leader_thread():
   leader_mutex.wait()
   leader_rendezvous.signal()
   follower_rendezvous.wait()
   dance()
   leader_mutex.signal()

def follower_thread():
   follower_mutex.wait()
   follower_rendezvous.signal()
   leader_rendezvous.wait()
   dance()
   follower_mutex.signal()

Since the solution is pretty obvious, it seems to me that its simplicity is compensated for by some drawbacks, for example, errors or poor performance. Are there really any drawbacks, and if so, which ones?

I even wrote a working program in Python 3, however, it does not give errors.

import threading
import time
import random
import sys

error=False
counter=0
counter_mutex=threading.Semaphore(1)

lead_mutex=threading.Semaphore(1)
foll_mutex=threading.Semaphore(1)
lead_rv=threading.Semaphore(0)
foll_rv=threading.Semaphore(0)

def leader(index):
    print("Leader started %d" % (index))

    lead_mutex.acquire()
    time.sleep(random.uniform(0, 0.1))
    lead_rv.release()
    time.sleep(random.uniform(0, 0.1))
    foll_rv.acquire()

    counter_mutex.acquire()
    global counter, error
    counter+=1
    print("Dancing leader %d %d" % (index, counter))
    if(counter>1 or counter<-1):
        print("ERROR!");
        error=True
        exit(1)
    counter_mutex.release()
    time.sleep(random.uniform(0, 0.1))
    lead_mutex.release()

    print("Leader ended %d" % (index))


def follower(index):
    print("Follower started %d" % (index))

    foll_mutex.acquire()
    time.sleep(random.uniform(0, 0.1))
    foll_rv.release()
    time.sleep(random.uniform(0, 0.1))
    lead_rv.acquire()

    counter_mutex.acquire()
    global counter, error
    counter-=1
    print("Dancing follower %d %d" % (index, counter))
    if(counter>1 or counter<-1):
        print("ERROR!");
        error=True
        exit(1)
    counter_mutex.release()
    time.sleep(random.uniform(0, 0.1))
    foll_mutex.release()

    print("Follower ended %d" % (index))

random.seed()
for i in range(0,50000):
    if(error):
        break
    rand_val=random.randint(0, 4)
    if(rand_val == 0):
        t=threading.Thread(target=leader, args=(i,))
        t.daemon=True
        t.start()
    elif(rand_val == 1  or rand_val == 3):
        t=threading.Thread(target=follower, args=(i,))
        t.daemon=True
        t.start()

    time.sleep(random.uniform(0,0.2))
print("End: %d" % (error) ) 

Answer:

You can come up with proof that my decision is also correct. Since the functions are symmetrical, it is possible to consider statements only for the leading dancers, then they will be true for the followers as well.

  1. When one leader has captured leader_mutex , the other obviously cannot. It follows from this that two leaders cannot dance at the same time.
  2. If one couple is dancing, then no one else can dance until that couple is finished. From the first statement it follows that one dancer must finish dancing. Have the host finish dancing first. Then the next presenter will be waiting on follower_rendezvous . Someone must execute follower_rendezvous.signal() , but until the follower_rendezvous.signal() is done dancing, the other follower_rendezvous.signal() cannot do it (statement 1).
  3. It is also necessary to exclude consecutive calls to dance() leading at the very beginning or after the couple has danced. Taking into account the first statement, this is possible only if one presenter has already completed. In the second assertion situation, let the moderator wait on follower_rendezvous . It is possible that the follower_rendezvous.signal() will execute follower_rendezvous.signal() , the leader will dance() and exit. Let the next leader come, then he will wait on the same semaphore. The only possible change in this situation is when the slave performs dance() . Further, it can be noted that the conditions of the second statement are again fulfilled.
Scroll to Top